詳解
許多程式語言,程式設計師會有任意地配置過多變數的錯誤觀念,然而在編譯時,編譯器必須決定在一個較小及有限暫存器的系統中如何分配這些變數,並非所有變數都是在同一時間運行,所以有些暫存器可能被分配超過一個變數。 然而,兩個被分配在同一暫存器的變數,若在同一時間使用,若是不破壞他的數值就無法被分配在相同的暫存器。無法被分配在相同的暫存器的變數必須被保留在隨機存取存儲器,在需要讀取或寫入時才會被載入,這個過程稱之為 溢出(spilling)。存儲器訪問速度比訪問暫存器還慢,這會降低程式的運行速度,所以一個最最佳化的編譯器會儘可能的將更多的變數放置在暫存器。 暫存器壓力(Register pressure)這個詞被使用在當硬體暫存器數量比起理想數量還少的狀況,高壓的情況通常代表會產生更多溢出以及更多重載的情況發生。
除此之外,程式可以被進一步的最最佳化,只要可行,任何地方都能透過move指令來使一個暫存器的數值可以被移進移出,這在編譯器中相當重要,這被使用在一些最最佳化技術,例如靜態單賦值形式,他會在中間碼額外產生move指令。
溢出
在多數的暫存器分配,每個變數會存在暫存器或是存儲器,換句話說,如果一個變數無法被分配到一個暫存器,那么當這個變數要被使用時就會從存儲器載入。一個溢出的變數(Spilled Variable)代表一個變數在存儲器中而不在CPU的暫存器。舉例來說,一個32位的變數溢出到存儲器,他會獲取32位的堆疊空間,而所有使用到這個變數的位置將會指到存儲器,這樣的變數的處理速度相較於暫存器的變數就會比較慢,所以要決定哪些變數必須溢出,就必須考慮到運行時間、代碼占用空間以及數據空間等因素。
疊代暫存器接合
暫存器分配有很多類型,疊代暫存器接合(Iterated Register Coalescing,IRC)則是常用的一種,IRC是由LAL George及Andrew Appel在1996年提出,IRC基於一些原理所運作,第一,如果在圖中存在無法被移動的節點,而這些與這些節點的連線的數量小於K,則這些圖可以直接移除掉這些節點,因為一旦這些節點被加回去,則可以保證找到他們的顏色(簡化)。第二,兩個節點共享一個優先邊,而他們鄰近集合的連線總數小於K,那么這兩個點可以被結合為一個節點(接合),如果上述兩個步驟可以簡化圖,簡化的程式在移動相關節點時(凍結時),可以再運行一次。最後,如果沒有任何其他工作了,節點可以被標示為可能溢出並且從圖中移除(溢出)。以上步驟用以減少圖中節點的連線數,節點的連線數可能從大於K的情況降為低連線數,使節點可以被簡化或是接合。這個階段的算法被疊代,以確保簡化及接合的質量。