5.2 暫存器配置與圖著色問題#

問題本質#

目標機器的暫存器數量有限（x86-64 有 16 個整數暫存器，其中 rbp/rsp 另有用途），而程式的「同時活躍」變數往往更多。暫存器配置（register allocation） 要決定每個變數（或 SSA 值）何時住暫存器、何時溢出（spill）到記憶體。這是 NP-完備的圖著色問題，且直接決定產出碼的速度——一次額外的 load/store 可能是數十個週期。

歷史：Chaitin 的突破#

1981 年，IBM 的 Gregory Chaitin 與 Marc Auslander、Ashok Chandra、John Cocke、Martin Hopkins、Peter Markstein 發表《Register Allocation via Coloring》，把暫存器配置化約為圖著色：這是編譯器理論最漂亮的化約之一。其靈感源自 Cocke 在 IBM PL.8 編譯器（為 801 RISC 設計，1970s 末）的工作。在此之前，配置多以區域性貪心或線性掃描為主，全域品質不佳。

圖著色配置（Chaitin–Briggs）#

五個步驟：

活躍範圍建構：對 SSA/中間碼做活躍變數分析，將每個變數的「連續活躍區間」視為一個單位（live range）。在 SSA 上改用 live range 是 web（def-use 鏈的傳遞閉包）。
建立干涉圖（interference graph）：兩個活躍範圍同時活躍 ⇒ 連邊。若機器有 \(R\) 個可用暫存器，問題即：圖可否 \(R\) -著色？
著色： \(R\) -著色 NP-完備，用啟發式：
溢出：無法著色時犧牲某變數，插入 load/store，重跑分析。
合併（coalescing）：mov x, y 之類的複製，若 \(x, y\) 可共用同一暫存器，刪除該 mov（干涉圖中加「偏好邊」）。

Chaitin–Briggs 著色演算法#

simplify:
  while 圖中有度數 < R 的節點:
    從圖移除之, 壓入堆疊
  if 全部節點度數 >= R:
    (可能的溢出候選) 選一個 spill cost/degree 比最小的節點,
      標記為 spill candidate, 移除並壓入堆疊
select:
  依堆疊反序回填顏色:
    節點的鄰居已用顏色之外, 挑任一可用色
  若 spill candidate 實際上湊得到色 => 樂觀著色成功 (Briggs, 1992)
  否則 => 真溢出: 插入 load/store, 重跑全流程

樂觀著色（Briggs et al., 1994）：度數 ≥ R 不必然不能著色，先假設能，最後再驗證——大幅減少不必要的溢出。

溢出成本估計： \(cost = \sum \text{use/def 的頻率} \times 10^{\text{loop depth}}\) ，迴圈內的變數優先保留在暫存器。

溢出的處理#

split & spill：只把「最冷」的區段溢出，而不是整個活躍範圍（Chow & Hennessy 的 priority-based spilling, 1984）。
rematerialization：常數或簡單計算（lea）不必存記憶體，重算更便宜。
live range splitting：把長範圍切成兩段，一段住暫存器一段住記憶體。

線性掃描（Linear Scan）#

Poletto & Sarkar（1999） 提出線性掃描：把活躍區間視為一維線段，以貪心方式分配——複雜度 \(O(n \log n)\) ，品質略遜但速度極快。這是 JIT 的標配：

HotSpot Client Compiler、LuaJIT、V8 的舊 TurboFan 後端皆用線性掃描。
Massimino & Wimmer（2020） 提出改進版 linear scan，接近圖著色品質。

SSA 上的新方法#

SSA 的性質使干涉圖是 chordal graph（Sebastian Hack, 2006 的理論結果），可多項式時間著色，且不需要再拆「web」：

SSA-based allocation (Hack, 2006):
  1. SSA 形式下做活躍分析
  2. chordal 干涉圖 -> 完美消除序著色 (貪心即最優)
  3. 再做 phi 消解 (parallel copies) 與合併

LLVM 的 Greedy allocator、GCC 的新版 RA（IRA）都吸收了 SSA 思想。

與其他階段的耦合#

指令選擇：x86 的 lea 可同時做加法與乘 2/4/8，選對指令能省暫存器。
指令排程：暫存器壽命越短，干涉圖越稀疏；但重排可能拉長壽命——兩者互相牽制（integrated scheduling & allocation 是開放問題）。
呼叫慣例：caller-saved/callee-saved 的選擇影響 call 前後的保存成本。
ABI 與 debug 資訊：DWARF 需要記錄每個變數在各程式點的位置（暫存器或堆疊槽）。

小結#

Chaitin（1981）把暫存器配置化約為圖著色，干涉圖是其核心資料結構。
simplify/select 兩階段＋樂觀著色是經典演算法；溢出以成本模型取捨。
線性掃描服務 JIT，SSA-chordal 理論（Hack 2006）開啟新世代配置器。