基本介紹
- 中文名：暫存器分配
- 外文名： register assignment
- 操作：代碼指令
- 作用：提高程式執行速度
- 常用算法：圖著色算法
- 套用學科：電腦程式編譯
分配原因,實際分配問題,分配原則,相關算法,
分配原因
暫存器分配是編譯器中一個歷久彌新的問題，因為它是編譯器在輸出彙編代碼前必須經歷的階段。暫存器分配算法的好壞，關係著生成代碼的性能，大小。為了追求極致性能，很多編譯器都在暫存器分配上做了很多文章，不惜引入非常複雜的算法。另一方面暫存器分配算法本身的性能也很關鍵， 在諸多的JIT編譯器(Just-In-Time compiler)中，編譯器的性能同時也是程式本身的性能，因此在JIT編譯器中還需要關注暫存器分配算法本身的效率問題。另外，暫存器分配作為將無限多的邏輯單元映射到有限多的物理單元的典型問題，深入了解它也有助於對其他相關問題的理解，如作業系統中的頁著色問題(Page Coloring)。
實際分配問題
在實際編譯器中，為了儘可能的榨取性能，提升編譯器的分配效率，暫存器分配算法都很複雜。萬變不離其宗。不管是GCC，Open64還是LLVM，暫存器分配基本都是在靠近彙編代碼輸出階段。Open64中在暫存器分配之後，幾乎沒有什麼最佳化了。GCC中，在暫存器分配之後，還存在大約7個PASS(基本塊重排序、收集用於調試的變數保存位置相關信息、延遲槽調度、長跳轉轉換、針對86387浮點暫存器的暫存器到棧變換、彙編代碼輸出、調試信息輸出)，也沒有最佳化了。LLVM不清楚，歡迎有了解的朋友補充。
這三個工業界級別的編譯器中，到了暫存器分配階段都已經從語法樹形式的中間表示轉換成了三地址形式的中間表示。 在GCC中，已經從GIMPLE轉換成了RTL；在Open64中，已經從WHIRL轉換成了CGIR；在LLVM中，已經從Clang階段的AST(Abstract Syntax Tree,抽象語法樹)轉換成了LLVM IR。 在轉換成三地址碼之前，操作之間的運算元、結果的依賴關係都可以通過樹形結構表達，展開成三地址形式之後，就需要大量創建臨時變數來表達這種依賴關係。此時所有的變數(包括臨時變數和原程式中的變數)，都會被分配偽暫存器(Pseudo Register偽暫存器和物理暫存器除了數量有區別：無限多個/有限多個外，其他都相同)。
暫存器分配即將這些偽暫存器映射到實際的物理暫存器上 ， 因此在暫存器分配之前，要保證指令序列基本不再變化。所以實際編譯器中的暫存器分配階段，基本都在最後階段，此時都基本完成了幾乎所有的底層次最佳化，如三地址形式的循環最佳化、指令調度、冗餘代碼刪除、其他窺孔最佳化等等。但也有例外，比如暫存器分配時，需要額外增加一些訪存指令，因此在暫存器分配結束後，可能還需要一些調整。
分配原則
相關算法
圖著色算法
圖著色(graph coloring)方法是解決暫存器分配問題最常用的方法。
利用相交圖（interference graph）來表示程式變數的生命期是否相交，將暫存器分配給變數的問題，可以近似地看成是給相交圖著色：相交圖中，相交的節點不能著同一顏色；每一種顏色對應一個暫存器。Chaitin等人最早提出了基於圖著色的暫存器分配方法其著色思路採用了Kempe的著色方法，即任意一個鄰居節點數目少於k的節點，都能夠被k著色。判斷一個圖是否能夠被k(k>=3)種顏色著色，即k著色問題，被Karp證明是一個NP-complete問題。
但是，暫存器分配不僅僅是圖著色的問題。當暫存器數目不足以分配某些變數時，就必須將這些變數溢出到記憶體中，該過程成為spill。最小化溢出代價的問題，也是一個NP-complete問題。如果簡化該問題——假設所有溢出代價相等，那么最小化溢出代價的問題，等價於k著色問題，仍然是NP-complete問題。
此外，如果兩個變數的生命期僅僅因為出現在同一個拷貝指令中而相鄰，那么，通過將這兩個變數分配到同一個暫存器，就可以消除該拷貝指令，成為coalescing。這個方向的努力在Chaitin的文章以後的1/4個世紀，成為推動暫存器分配的主要動力之一，湧現出了包括aggressive coalescing,conservative coalescing和optimistic coalescing。但是，將兩個變數分配到同一個暫存器，等價於將這兩個變數合併成同一個變數，生命期合併，因而會加劇相交圖的聚簇現象，降低相交圖的可著色性。Bouchez等人證明了目前的coalescing問題都是NP-complete的。
利用相交圖（interference graph）來表示程式變數的生命期是否相交，將暫存器分配給變數的問題，可以近似地看成是給相交圖著色：相交圖中，相交的節點不能著同一顏色；每一種顏色對應一個暫存器。Chaitin等人最早提出了基於圖著色的暫存器分配方法其著色思路採用了Kempe的著色方法，即任意一個鄰居節點數目少於k的節點，都能夠被k著色。判斷一個圖是否能夠被k(k>=3)種顏色著色，即k著色問題，被Karp證明是一個NP-complete問題。
但是，暫存器分配不僅僅是圖著色的問題。當暫存器數目不足以分配某些變數時，就必須將這些變數溢出到記憶體中，該過程成為spill。最小化溢出代價的問題，也是一個NP-complete問題。如果簡化該問題——假設所有溢出代價相等，那么最小化溢出代價的問題，等價於k著色問題，仍然是NP-complete問題。
此外，如果兩個變數的生命期僅僅因為出現在同一個拷貝指令中而相鄰，那么，通過將這兩個變數分配到同一個暫存器，就可以消除該拷貝指令，成為coalescing。這個方向的努力在Chaitin的文章以後的1/4個世紀，成為推動暫存器分配的主要動力之一，湧現出了包括aggressive coalescing,conservative coalescing和optimistic coalescing。但是，將兩個變數分配到同一個暫存器，等價於將這兩個變數合併成同一個變數，生命期合併，因而會加劇相交圖的聚簇現象，降低相交圖的可著色性。Bouchez等人證明了目前的coalescing問題都是NP-complete的。
為了降低相交圖的聚簇現象，提高相交圖的可著色性，可以通過將變數拷貝給一個臨時變數，並將以後對該變數的使用替換成對該臨時變數的使用，從而將一個變數的生命期分解成兩個變數的生命期，稱為live range splitting。顯然，這是一個與coalescing的作用相反的過程。Bouchez等人考慮了該方法的複雜度。
此外，暫存器分配還需要考慮暫存器別名(aliasing)和預著色(pre-coloring)的問題。暫存器別名是指，在某些體系結構中，一個暫存器的賦值可能會影響到另外一個暫存器。比如，在x86中，對AX暫存器的賦值，會影響AL和AH暫存器。預著色是指，某些變數必須被分配到特定的暫存器。比如，許多體系結構會採用特定暫存器來傳遞函式參數。
George和Appel發展了Chaitin的算法，更好地考慮了coalescing過程和賦值過程，以及各過程之間的疊代，在基於圖著色的暫存器分配方法中具有廣泛的影響。
此外，暫存器分配還需要考慮暫存器別名(aliasing)和預著色(pre-coloring)的問題。暫存器別名是指，在某些體系結構中，一個暫存器的賦值可能會影響到另外一個暫存器。比如，在x86中，對AX暫存器的賦值，會影響AL和AH暫存器。預著色是指，某些變數必須被分配到特定的暫存器。比如，許多體系結構會採用特定暫存器來傳遞函式參數。
George和Appel發展了Chaitin的算法，更好地考慮了coalescing過程和賦值過程，以及各過程之間的疊代，在基於圖著色的暫存器分配方法中具有廣泛的影響。
線性掃描算法
線性掃描算法是暫存器分配最快的算法。
線性掃描算法(linear scan)最早由Poletto和Sarkar提出，具有很大的影響力，在gcc、llvm和Java HotSpot編譯器中得到了實現。線性掃描算法簡化了基於圖著色的分配問題，考慮的是對一個有序的生命期序列的著色，提高了暫存器分配的速度（線性速度），而沒有過度降低對暫存器的利用。
整數線性規划算法
Goodwin和Wilken提出了最早的對暫存器分配問題的整數線性規劃算法(integer linear programming),雖然在最壞情況下具有指數級複雜度，但是能夠更充分的利用暫存器。
PBQP算法
在編譯器領域，Partitioned Boolean Quadratic Problem被用於解決指令選擇和暫存器分配問題。對於暫存器分配而言，PBQP算法的複雜度為VK^3，其中V是變數的數目，K是暫存器的數目。Hames等人的實驗表明，他們的PBQP實現能夠為SPEC CPU 2000中的97.4%的函式找到最優暫存器分配方案。
Multi-Flow Commodities算法
Koes和Goldstein等人最先將暫存器分配視為Multi-Flow Commodities問題加以解決。
基於SSA的暫存器分配
SSA是Static Single Assignment的簡寫。暫存器分配問題的一個重要突破發生在2005年，當時3個研究團隊獨立的證明了，採用SSA表示的程式的相交圖是弦圖（chordal graph）。而弦圖是能夠在多項式時間內著色的。基於SSA形式的暫存器分配方法，可以從三個方面獲益：更小的暫存器壓力；spilling和暫存器賦值過程之間的分離；更簡單的暫存器賦值算法。
