暫存器配置

許多編程語言，程序員會有任意地配置過多變量的錯誤觀念，然而在編譯時，編譯器必須決定在一個較小及有限寄存器的系統中如何分配這些變量，並非所有變量都是在同一時間運行，所以有些寄存器可能被分配超過一個變量。 ^[1]  然而，兩個被分配在同一寄存器的變量，若在同一時間使用，若是不破壞他的數值就無法被分配在相同的寄存器。無法被分配在相同的寄存器的變量必須被保留在隨機存取存儲器，在需要讀取或寫入時才會被加載，這個過程稱之為溢出（spilling）。存儲器訪問速度比訪問寄存器還慢，這會降低程序的運行速度，所以一個最優化的編譯器會盡可能的將更多的變量放置在寄存器。寄存器壓力（Register pressure）這個詞被使用在當硬件寄存器數量比起理想數量還少的狀況，高壓的情況通常代表會產生更多溢出以及更多重載的情況發生。

除此之外，程序可以被進一步的最優化，只要可行，任何地方都能透過move指令來使一個寄存器的數值可以被移進移出，這在編譯器中相當重要，這被使用在一些最優化技術，例如靜態單賦值形式，他會在中間碼額外產生move指令。

在多數的寄存器分配，每個變量會存在寄存器或是存儲器，換句話説，如果一個變量無法被分配到一個寄存器，那麼當這個變量要被使用時就會從存儲器加載。一個溢出的變量（Spilled Variable）代表一個變量在存儲器中而不在CPU的寄存器。舉例來説，一個32位的變量溢出到存儲器，他會獲取32位的堆棧空間，而所有使用到這個變量的位置將會指到存儲器，這樣的變量的處理速度相較於寄存器的變量就會比較慢，所以要決定哪些變量必須溢出，就必須考慮到運行時間、代碼佔用空間以及數據空間等因素。

寄存器分配有很多類型，迭代寄存器接合（Iterated Register Coalescing，IRC）則是常用的一種，IRC是由LAL George及Andrew Appel在1996年提出，IRC基於一些原理所運作，第一，如果在圖存在無法被移動的節點，而這些與這些節點的連接的數量小於K，則這些圖可以直接移除掉這些節點，因為一旦這些節點被加回去，則可以保證找到他們的顏色（簡化）。第二，兩個節點共享一個優先邊，而他們鄰近集合的連接總數小於K，那麼這兩個點可以被結合為一個節點（接合），如果上述兩個步驟可以簡化圖，簡化的程序在移動相關節點時（凍結時），可以再運行一次。最後，如果沒有任何其他工作了，節點可以被標示為可能溢出並且從圖移除（溢出）。以上步驟用以減少圖節點的連接數，節點的連接數可能從大於K的情況降為低連接數，使節點可以被簡化或是接合。這個階段的算法被迭代，以確保簡化及接合的質量。