暫存器配置（register allocation）

在 IR 內部，編譯器假裝它有無限多個具名的值的槽位——虛擬暫存器，要多少有多少。但真實處理器只有一小組固定的快速暫存器（x86-64 上大約 16 個通用暫存器）。暫存器配置就是後端把那些無限的虛擬暫存器對應到少數幾個真實暫存器、決定哪些值能在任一時刻住在暫存器裡的工作。

核心困難在於：兩個值只有在不同時被需要時才能共用一個真實暫存器。編譯器計算每個值的活躍範圍（live range，從定義到最後一次使用之間的程式碼跨度）並問：哪些值同時活躍？重疊的值彼此衝突，必須拿到不同的暫存器。這天然地用圖著色（graph coloring）建模：把每個值當成一個節點，在活躍範圍重疊的值之間連一條邊，用「和暫存器數量一樣多」的顏色為圖著色，使任兩個相連節點不共用顏色。一般的著色很難，所以編譯器用啟發式。即時編譯器（JIT）用的較快替代法是線性掃描（linear scan），它依序掃過活躍範圍並貪婪地分配暫存器，以一些品質換取速度。當同時活躍的值就是多到暫存器不夠時，有些必須被溢出（spill）——存到堆疊的記憶體裡，需要時再載回來。

它重要在於：把一個值放在暫存器而非記憶體，是「遠少於一奈秒就執行完的指令」與「可能要等快取或記憶體存取的指令」之間的差別；良好的配置是 -O2 程式碼為何快的一大部分。一個提醒：暫存器配置在你的原始碼裡看不見，但在產生的組合語言裡非常明顯——這也是為什麼一個有許多同時活躍變數的函式，會產生你從沒要求過的堆疊載入與儲存（溢出）。它也與周遭一切互動：積極的內聯或會延長活躍範圍的 CSE 可能增加暫存器壓力、迫使更多溢出，所以一個在上游看似純勝的最佳化，可能在這裡讓你付出代價。