基本介紹
- 中文名：暫存器配置
- 外文名：Register Allocation
- 目的：編譯器最最佳化
- 領域：計算機
簡介,圖著色性的同構,溢出,疊代暫存器接合,近期發展,
簡介
許多程式語言，程式設計師會有任意地配置過多變數的錯誤觀念，然而在編譯時，編譯器必須決定在一個較小及有限暫存器的系統中如何分配這些變數，並非所有變數都是在同一時間運行，所以有些暫存器可能被分配超過一個變數。然而，兩個被分配在同一暫存器的變數，若在同一時間使用，若是不破壞他的數值就無法被分配在相同的暫存器。無法被分配在相同的暫存器的變數必須被保留在隨機存取存儲器，在需要讀取或寫入時才會被載入，這個過程稱之為溢出（spilling）。存儲器訪問速度比訪問暫存器還慢，這會降低程式的運行速度，所以一個最最佳化的編譯器會儘可能的將更多的變數放置在暫存器。暫存器壓力（Register pressure）這個詞被使用在當硬體暫存器數量比起理想數量還少的狀況，高壓的情況通常代表會產生更多溢出以及更多重載的情況發生。
除此之外，程式可以被進一步的最最佳化，只要可行，任何地方都能透過move指令來使一個暫存器的數值可以被移進移出，這在編譯器中相當重要，這被使用在一些最最佳化技術，例如靜態單賦值形式，他會在中間碼額外產生move指令。
圖著色性的同構
透過活躍變數分析（Live variable analysis），編譯器可以決定哪個變數的集合在同一時間是活躍的，也就是涉入move指令的變數。使用這些信息，編譯器可以建構一張圖，使每個點（Vertex）在程式中代表一個獨立的變數。當變數被同時使用時，則利用干擾邊（Interference edges）連結兩個節點，當變數同時涉入move指令時，則創建優先邊（preference edges）。可以透過K-coloring用來解決暫存器配置的問題（K為暫存器可用的數量）。兩個共享一個干擾邊的節點不會被分配相同的顏色，而共享一個優先邊的節點可能會被分配相同的顏色，有些節點可能一開始就會被上色，代表這些變數因為慣例或是模組間溝通的因素而必須留在某些特定的暫存器，圖著色問題廣義來說是NP完全問題，然而一個好的算法必須平衡性能以及代碼的品質。
圖著色技術是相當有效率，因為它不只考慮到變數的暫存器配置，還考慮在同時間運行的變數，邏輯上，如果變數V所有活躍的鄰近變數可以被配置暫存器，那么通過V則可以訪問到所有鄰近的變數，所以這是一個遞歸的案例，目的是移除活躍變數集合中的變數。這個循環將持續進行，直到所有活躍變數都可以被配置，而其他的變數則溢出到存儲器。
溢出
在多數的暫存器分配，每個變數會存在暫存器或是存儲器，換句話說，如果一個變數無法被分配到一個暫存器，那么當這個變數要被使用時就會從存儲器載入。一個溢出的變數（Spilled Variable）代表一個變數在存儲器中而不在CPU的暫存器。舉例來說，一個32位的變數溢出到存儲器，他會獲取32位的堆疊空間，而所有使用到這個變數的位置將會指到存儲器，這樣的變數的處理速度相較於暫存器的變數就會比較慢，所以要決定哪些變數必須溢出，就必須考慮到運行時間、代碼占用空間以及數據空間等因素。
疊代暫存器接合
暫存器分配有很多類型，疊代暫存器接合（Iterated Register Coalescing，IRC）則是常用的一種，IRC是由LAL George及Andrew Appel在1996年提出，IRC基於一些原理所運作，第一，如果在圖中存在無法被移動的節點，而這些與這些節點的連線的數量小於K，則這些圖可以直接移除掉這些節點，因為一旦這些節點被加回去，則可以保證找到他們的顏色（簡化）。第二，兩個節點共享一個優先邊，而他們鄰近集合的連線總數小於K，那么這兩個點可以被結合為一個節點（接合），如果上述兩個步驟可以簡化圖，簡化的程式在移動相關節點時（凍結時），可以再運行一次。最後，如果沒有任何其他工作了，節點可以被標示為可能溢出並且從圖中移除（溢出）。以上步驟用以減少圖中節點的連線數，節點的連線數可能從大於K的情況降為低連線數，使節點可以被簡化或是接合。這個階段的算法被疊代，以確保簡化及接合的品質。虛擬代碼如下：
function IRC_color g K : repeat if ∃v s.t. !moveRelated(v) ∧ degree(v) < K then simplify v else if ∃e s.t. cardinality(neighbors(first e) ∪ neighbors(second e)) < K then coalesce e else if ∃v s.t. moveRelated(v) then deletePreferenceEdges v else if ∃v s.t. !precolored(v) then spill v else return loop
在IRC中進行接合是相當穩定的，因為一個積極的接合可能會導致圖的溢出，然而這同時啟發了像是George coalescing接合了更多的節點，更可確保沒有額外的溢出發生，Work-lists被使用在這個算法來確保每個IRC的疊代皆需要sub-quadratic time。
近期發展
利用圖著色來改進的代碼的效率雖然有效，但是配置的時間仍然很長，在靜態編譯的案例中，配置時間並不是那么被在意，但是在動態編譯的案例中，例如即時編譯（Just-in-time，JIT）編譯器，快速的暫存器配置是很重要的，Poletto及Sarkar提出一個的有效技術線性掃描配置，這個技術僅需要一個階段獲取活躍變數的區間列表，較短生命周期區間的變數將會被分配到暫存器，而較長生命周期的變數將會被溢出，這個結果的性能平均只比圖著色降低12%。
線性掃描算法的步驟如下：
- 運行數據流程分析，用以獲取活躍度信息。持續紀錄所有變數的活躍間隔於一個列表並以遞減排序，這個間隔代表在這段時間內變數是活躍的，我們認為變數以及他們的間隔在這個算法中是可以交換的。
- 反覆通過活躍度的開始點，並且配置一個暫存器給每個活躍的變數
- 在每個步驟維護一張在間隔內運作的列表，以活躍間隔的結束點進行排序（注意到插入有序的節點到一個平衡的二叉樹，可使這張列表的維護成本為線性成本）。移除所有的逾期間隔，並且釋放這些逾期的暫存器。
- 當列表大小R，我們無法配置暫存器時，從運作列表中溢出間隔距離最遠的點，並且分配給目前的間隔。如果目前的間隔是一個溢出的間隔，則不改變暫存器的分配。
Cooper及Dasgupta近期開發了一個有損的Chaitin-Briggs圖著色算法，適用於JIT。有損代表這個算法所提出的干擾圖並不是那么精確，這個最最佳化減少了圖創建的步驟，Chaitin-Briggs使它適合運行時期的編譯。實驗中顯示，這個有損的暫存器配置比起線性掃描效率來得好。
理想的暫存器配置算法是基於Goodwin及Wilken所開發的線性規划算法，這些算法已經被Kong及Wilken延伸到更多架構。
