暫存器（Register），是中央處理器內的其中組成部分，暫存器訪問速度最快，完全能與 CPU 協調工作，但價格卻十分昂貴，因此容量不可能做得很大。暫存器是有限存貯容量的高速存貯部件，它們可用來暫存指令、數據和地址。暫存器分配程式是指對暫存器的分配、回收以及提供在存儲層次間的數據移動的管理機制的程式。
基本介紹
- 中文名：暫存器分配程式
- 外文名：Register Allocation Program
- 學科：計算機
- 定義：暫存器管理程式
- 有關術語：暫存器
- 領域：設備管理
簡介,暫存器,概述,暫存器的種類,暫存器分配步驟,生成MOVE指令,指令調度（The instruction scheduler）,尋找暫存器類,局部分配,全局分配,reload階段,postreload階段,
在作業系統中，存儲器管理的主要任務是為多道程式的運行提供良好的求嚷辨環境，方便用戶使用存儲器，提高存儲器的利用率以及能從邏輯上擴充記憶體。暫存器的管理是存儲器管理的重要內容。暫存器訪問速度十分快，速度接近CPU運行速度，但暫存器的價格十分昂貴。為了充分利用暫存器資源，暫存器分配程式是指暫存器分配、回收等操作管理的程式。暫存器分配程式主要目的是使系統中在單位時間運行更多的作業，提高系統效率。
暫存器，是積體電路中非常重要的一種存儲單元，通常由觸發器組成。在積體電路設計中，暫存器可分為電路內部使用的暫存器和充當內外部接口的暫存器這兩類。內部暫存器不能被外部電路或軟體訪問，只是為內部電路的實現存儲功能或滿足電路的時序要求。而接口暫存放夜嚷器可以同時被內部電路和外部電路或軟體訪問，CPU中的暫存器就是其中一種，作為軟硬體的接口，為廣泛的通用編程用戶所熟知。
在計算機領域，暫存器是CPU內部的元件，包括通用暫存器、專用恥巴府蒸暫存器和控制暫存器。暫存器擁有非常高的讀寫速度，所以在暫存器之間的數據傳送非常快。
用來存儲整數數字（參考以下的浮點暫存器）。在某些簡單（或舊）的CPU，特別的數據暫存器是累加器，作為數學計算之用。
持有記憶體地址，以及用來訪問記憶體。在某些簡單/舊的CPU里，特別的地址暫存器是索引暫存器（可能出現一個或多個）。
通用目的暫存器
（GPRs）- 可以保存數據或地址兩者，也就是說他們是結合 數據/地址 暫存器的功用。
浮點暫存器
（FPRs）- 用來存儲浮點數字。
常數暫存器
用來持有隻讀的數值（例如0、1、圓周率等等）。
向量暫存器
用來存儲由向量處理器運行SIMD指令所得到的數據。
特殊目的暫存器
指令暫存器 - 存儲現在正在被運行的指令頁騙淋
變址暫存器 - 是在程式運行時用來更改運算對象地址之用。
當目的暫存器和源暫存器應該相同時，生成MOVE指令，以滿足雙運算元指令的約束。
降低“暫存器壓力”（即講紙犁分配過程中硬暫存器短缺的現象）。
為每個待分配的偽暫存器找到首選的（preferred）和候選的（alternative）暫存器類。
暗中執行代碼選擇（code selection）。
掃描偽暫存器的一般信息（引用次數、賦值次數、引用偽暫存器的第一條和最後一條指令）。
對活躍在一個基本塊內的偽殼估嚷龍暫存器分配硬暫存器。結果存到全局數組reg_renumber中。
執行一些暫存器拼接工作，例如，如果二個或更多個不衝突的偽暫存器被若干MOVE指令攪亂了，它們通常能夠分配給相同的硬暫存器。執行簡單的複製傳播和常量傳播。
對活躍於多個基本塊內的偽暫存器分配硬暫存器。當它找到比局部分配更有利的硬暫存器時，它可能會改變局部分配的結果。為每個偽暫存器生成一個位向量，該向量包含與偽暫存器衝突的硬暫存器，為每個偽暫存器構建一個衝突圖，並根據下面的優先權值對所有偽暫存器排序：
( log2(Nrefs) * Freq / Live_Length ) * Size
這裡Nrefs是偽暫存器出現的次數，Freq是它使用的頻率，Live_Length是偽暫存器在指令中活躍範圍的長度，Size是它在硬暫存器中的大小。之後，全局分配器試圖按由高到低的優先權順序將硬暫存器分配給偽暫存器。
如果當前偽暫存器獲得了一個硬暫存器，該硬暫存器被加入（與該偽暫存器衝突的所有偽暫存器的）硬暫存器衝突向量。通過將偽暫存器賦給硬暫存器，試圖將MOVE指令中遇到的偽暫存器與硬暫存器接合起來。
( log2(Nrefs) * Freq / Live_Length ) * Size
這裡Nrefs是偽暫存器出現的次數，Freq是它使用的頻率，Live_Length是偽暫存器在指令中活躍範圍的長度，Size是它在硬暫存器中的大小。之後，全局分配器試圖按由高到低的優先權順序將硬暫存器分配給偽暫存器。
如果當前偽暫存器獲得了一個硬暫存器，該硬暫存器被加入（與該偽暫存器衝突的所有偽暫存器的）硬暫存器衝突向量。通過將偽暫存器賦給硬暫存器，試圖將MOVE指令中遇到的偽暫存器與硬暫存器接合起來。
如果RTL中的運算元的不滿足約束，那么就轉換使其滿足這些約束。這裡的偽暫存器可能會被轉換為硬暫存器、記憶體或常量。
reload遍跟在全局和局部分配之後，根據需要它可能會改變前二者的賦值。
例如：如果硬暫存器A分配給了偽暫存器V1，但引用V1的指令要求用其它暫存器類，則會生成
MOVE A to C
MOVE C to B
其中B是滿足V1指令暫存器類采凳的硬暫存器，而C可能是記憶體。如果B或C已被偽暫存器V2占用，則調用global.c中的retry_global函式為V2分配其它的硬暫存器，如果分配失敗，則V2被放於程式的堆疊中。
消除虛擬的硬暫存器（如實參指針）、和實際的硬暫存器（如幀指針）。
對那些溢出的硬暫存器，以及最終未獲得硬暫存器的偽暫存器，將堆疊槽賦給它們。
根據基本塊上下文，刪除reload階段生成的多餘的move, load, store等指令。
暗中執行代碼選擇（code selection）。
掃描偽暫存器的一般信息（引用次數、賦值次數、引用偽暫存器的第一條和最後一條指令）。
局部分配
對活躍在一個基本塊內的偽暫存器分配硬暫存器。結果存到全局數組reg_renumber中。
執行一些暫存器拼接工作，例如，如果二個或更多個不衝突的偽暫存器被若干MOVE指令攪亂了，它們通常能夠分配給相同的硬暫存器。執行簡單的複製傳播和常量傳播。
全局分配
對活躍於多個基本塊內的偽暫存器分配硬暫存器。當它找到比局部分配更有利的硬暫存器時，它可能會改變局部分配的結果。為每個偽暫存器生成一個位向量，該向量包含與偽暫存器衝突的硬暫存器，為每個偽暫存器構建一個衝突圖，並根據下面的優先權值對所有偽暫存器排序：
( log2(Nrefs) * Freq / Live_Length ) * Size
這裡Nrefs是偽暫存器出現的次數，Freq是它使用的頻率，Live_Length是偽暫存器在指令中活躍範圍的長度，Size是它在硬暫存器中的大小。之後，全局分配器試圖按由高到低的優先權順序將硬暫存器分配給偽暫存器。
如果當前偽暫存器獲得了一個硬暫存器，該硬暫存器被加入（與該偽暫存器衝突的所有偽暫存器的）硬暫存器衝突向量。通過將偽暫存器賦給硬暫存器，試圖將MOVE指令中遇到的偽暫存器與硬暫存器接合起來。
( log2(Nrefs) * Freq / Live_Length ) * Size
這裡Nrefs是偽暫存器出現的次數，Freq是它使用的頻率，Live_Length是偽暫存器在指令中活躍範圍的長度，Size是它在硬暫存器中的大小。之後，全局分配器試圖按由高到低的優先權順序將硬暫存器分配給偽暫存器。
如果當前偽暫存器獲得了一個硬暫存器，該硬暫存器被加入（與該偽暫存器衝突的所有偽暫存器的）硬暫存器衝突向量。通過將偽暫存器賦給硬暫存器，試圖將MOVE指令中遇到的偽暫存器與硬暫存器接合起來。
reload階段
如果RTL中的運算元的不滿足約束，那么就轉換使其滿足這些約束。這裡的偽暫存器可能會被轉換為硬暫存器、記憶體或常量。
reload遍跟在全局和局部分配之後，根據需要它可能會改變前二者的賦值。
例如：如果硬暫存器A分配給了偽暫存器V1，但引用V1的指令要求用其它暫存器類，則會生成
MOVE A to C
MOVE C to B
其中B是滿足V1指令暫存器類的硬暫存器，而C可能是記憶體。如果B或C已被偽暫存器V2占用，則調用global.c中的retry_global函式為V2分配其它的硬暫存器，如果分配失敗，則V2被放於程式的堆疊中。
消除虛擬的硬暫存器（如實參指針）、和實際的硬暫存器（如幀指針）。
對那些溢出的硬暫存器，以及最終未獲得硬暫存器的偽暫存器，將堆疊槽賦給它們。
postreload階段
根據基本塊上下文，刪除reload階段生成的多餘的move, load, store等指令。
