1981-圖著色暫存器分配#

案件摘要#

暫存器是 CPU 最快的儲存單元，但數量稀少——x86 只有個位數通用暫存器。哪個變數能住在哪個暫存器裡，是編譯器優化的「最後一哩」，長久以來靠手工啟發式勉強應付。1981 年，IBM Watson 研究中心的 Gregory Chaitin 做出一個漂亮的洞察：把「變數生命週期重疊者不可共用暫存器」畫成一張圖，暫存器分配就等價於圖著色問題。這個建模讓混亂變成數學，成為此後四十年所有主流編譯器（GCC、LLVM）的標配心法。

前因 -- 為什麼會有這個案子#

• 暫存器的稀缺性：暫存器存取約 1 個時脈週期，主記憶體卻要上百週期。把愈多活躍變數放進暫存器，程式就愈快——但暫存器只有 \(K\) 個，變數卻動輒數百個。
• 啟發式時代的困境：1960-70 年代的分配法（如 FORTRAN H 編譯器）靠「使用頻率加權」等啟發式逐個挑選，缺乏全局視野，常在相鄰決策間自相矛盾。
• 圖論工具已備：四色定理（Appel-Haken, 1976）、NP-完全理論（Karp, 1971）已成熟；Chaitin 意識到「同時活躍 ⇒ 不能共用」正是圖著色的「相鄰 ⇒ 不同色」。
• IBM 的優化編譯器計畫：Chaitin 在 IBM Watson 參與 PL/I 優化編譯器（PL.8）開發，需要一個能與全域優化器整合的暫存器分配器，這就是作案現場。

線索與推理 -- 數學式、程式、理論#

干涉圖：把生命週期畫成圖#

Chaitin 的核心觀察：若變數 \(a\) 與 \(b\) 的活躍區間（live range）在某個程式點同時存活，它們就不能共用同一暫存器。定義干涉圖 \(G = (V, E)\) ：

• \(V\) ：每個待分配的臨時變數是一個節點；
• \(E\) ：若 \(\exists\) 程式點 \(p\) ， \(a\) 與 \(b\) 在 \(p\) 同時活躍（以活躍變數分析判定），則 \((a, b) \in E\) 。

於是暫存器分配問題等價於圖著色問題：

其中色數 \(\chi(G)\) 是把圖著色所需的最少顏色數， \(K\) 是目標機器的暫存器數。

NP-完全性：沒有捷徑，但有退路#

判定一張圖是否 \(K\) -著色是 NP-完全問題（ \(K \ge 3\) 時； \(K=2\) 可用二分圖判定在線性時間解決）。編譯器要在秒級內處理數萬節點，精確解不可行。Chaitin 的戰術是簡化（simplify）：

反覆移除 \(\deg < K\) 的節點壓入堆疊；若圖中剩餘節點全部 \(\deg \ge K\) ，則選擇一個「溢出代價最小」的節點 spill——把它踢出暫存器、存回記憶體，並在其活躍區間插入載入/儲存指令，重跑流程。這是啟發式，不保證找到存在的著色，但實務上極為有效。

Python 模擬：Chaitin 式 simplify + assign#

import random

# 干涉圖：節點 = 臨時變數，邊 = 同時活躍（不可共用暫存器）
# 模擬程式碼: a=1; b=2; c=a+b; d=b*2; e=c+d
# 活躍區間：a:[1,3), b:[2,5), c:[3,5), d:[4,5), e:[5,5]
interference = {
    "a": {"b", "c"}, "b": {"a", "c", "d", "e"},
    "c": {"a", "b", "d", "e"}, "d": {"b", "c", "e"},
    "e": {"b", "c", "d"},
}
K = 3                      # 假設只有 3 個通用暫存器

def chaitin_allocate(graph, K, spill_cost=None):
    stack, spilled = [], []
    g = {v: set(ns) for v, ns in graph.items()}
    while g:
        # simplify：移除所有 deg < K 的節點
        candidates = [v for v in g if len(g[v]) < K]
        if candidates:
            v = min(candidates, key=lambda x: len(g[x]))
            stack.append(v)
            for n in g[v]: g[n].discard(v)
            del g[v]
        else:
            # 全部 deg >= K：溢出代價最小的節點踢到記憶體
            cost = spill_cost or (lambda x: random.random())
            v = min(g, key=cost)
            spilled.append(v)
            for n in g[v]: g[n].discard(v)
            del g[v]
    # assign：反序彈出，貪心挑一個鄰居未用的顏色
    color = {}
    for v in reversed(stack):
        used = {color[n] for n in interference[v] if n in color}
        color[v] = next(c for c in range(K) if c not in used)
    return color, spilled

color, spilled = chaitin_allocate(interference, K)
print("暫存器分配:", {v: f"R{c}" for v, c in color.items()})
print("溢出到記憶體:", spilled)
# 典型輸出：分配 {'a':'R0','c':'R1','d':'R0','e':'R2'}，溢出 ['b']
# b 干涉最多（deg=4 >= K=3），被判定溢出——全域視野自動找出犧牲者

這個 30 行的模擬完整重現了 Chaitin 演算法的兩大階段：simplify（線性時間化簡，把圖拆到可著色）與 assign（反序回填顏色）。注意 d 與 a 同色（R0）——因為 d 定義時 a 已死亡，它們的生命週期不重疊，可共用暫存器，這正是干涉圖編碼的資訊。

溢出代價的數學#

spill 選擇並非任意，Chaitin 定義溢出代價：

其中 \(d(p)\) 是程式點 \(p\) 的迴圈巢狀深度（迴圈內的存取代價以 10 的冪次放大），除以 \(\deg(v)\) 則偏好溢出「干涉少」的節點。代價低者先犧牲——這讓分配器在效能上近乎最優。

結案 -- 後果與影響#

• 成為四十年標配：Chaitin-Briggs 演算法（1988-89 Briggs 改良為樂觀著色：先假設可著色、失敗再 spill）成為業界標準；GCC 與 LLVM 至今都以圖著色或其線性掃描變體做暫存器分配。
• NP-難問題的工程化解法典範：圖著色分配展示了「把優化問題建模成圖論 + 用簡化啟發式求解」的方法學，影響了指令排程、暫存器合併（coalescing）等一整族編譯器問題。
• Chaitin 的跨界名聲：Chaitin 日後以演算法資訊理論（AIT）與「Ω 常數」聞名數學界——暫存器分配是他工程生涯中最被廣泛使用的遺產。
• 理論落地：活躍變數分析（資料流分析，見 1977 龍書）+ 圖著色（離散數學）在這一案中合流，證明編譯器優化是應用數學的舞台。

關鍵人物與文獻#

• Gregory Chaitin（IBM Watson）：1981-82 提出圖著色分配與溢出代價模型。
• Preston Briggs（Rice）：1988 樂觀著色改良，博士論文成為教科書級文獻。
• 文獻：
• G. J. Chaitin, "Register Allocation & Spilling via Graph Coloring," SIGPLAN Symp. Compiler Construction, 1982.
• G. J. Chaitin et al., "Register Allocation via Coloring," Computer Languages 6, 47 (1981).
• P. Briggs, K. Cooper, L. Torczon, "Improvements to Graph Coloring Register Allocation," ACM TOPLAS 16, 428 (1994).
• R. M. Karp, "Reducibility among Combinatorial Problems," 1971（圖著色 NP-完全性）.