Chaitin · spill

寄存器分配：着色的工程闭环

一段中间代码里的变量往往比机器的寄存器多。哪些变量可以共用一个寄存器、哪些必须各占一个，是每个编译器后端都要回答的问题。Chaitin 等人在 1981 年给出的答案沿用至今：这是一个图着色问题 [1]。本页用一个五变量的循环程序走完这条工程闭环，从活跃性分析建图，到化简着色，到着不动时的溢出与重建。

1 · 冲突图建模

一个变量在某程序点活跃 (live)，指它此刻持有的值之后还会被读到。两个变量若在同一个程序点同时活跃，两个值都得留着，不能塞进同一个寄存器；反之，活跃期不相交的变量可以放心共用。把变量画成顶点、「在某处同时活跃」画成边，得到冲突图 (interference graph)； $k$ 个物理寄存器对应 $k$ 种颜色，寄存器分配即冲突图的 $k$ -着色 [1]。

样本程序求 $0$ 到 $n-1$ 的平方和，四个基本块、5 个变量 $n$ 、 $s$ 、 $i$ 、 $c$ 、 $t$ ：

entry:  n = arg0
        s = 0
        i = 0
loop:   c = i < n
        br c, body, exit
body:   t = i * i
        s = s + t
        i = i + 1
        jmp loop
exit:   ret s

2 · 活跃性分析

「同时活跃」不能靠目测，要做活跃性分析 (liveness analysis)：一趟反向数据流，对每个基本块 $b$ 迭代

\text{live-in}(b) \;=\; \text{use}(b) \;\cup\; \bigl(\text{live-out}(b) \setminus \text{def}(b)\bigr)

直到不动点，其中 live-out 取所有后继块 live-in 的并。循环的回边会把集合带回上游，一遍扫不完，必须迭代。样本程序上算出的结果里，循环头 loop 的 live-in 是 $i$ 、 $n$ 、 $s$ 三个变量：计数器、上界与累加器都要跨过回边存活， $c$ 与 $t$ 都不在其中。

连边不必逐个程序点枚举，用 def 点规则即可：定义 $x$ 的那一刻， $x$ 与该指令 live-out 集合里的其余变量两两连边。理由是，任何一对真冲突总有后定义的一方，在那个定义点，先活的一方必然还留在 live-out 里，所以只扫 def 点不漏边。

3 · 冲突图的形状

动手算边之前，预期并不乐观：5 个变量全程纠缠在同一个循环里，冲突图多半是完全图 $K_5$ ，一人一个、要 5 个寄存器。实测建出的图只有 9 条边： $K_5$ 该有的 10 条里，唯独 $c$ – $t$ 一条缺席。回到活跃区间找原因， $c$ 在循环头定义、立刻被 br 消费，只活在循环头； $t$ 在循环体定义、下一行就并进 $s$ ，只活在循环体。两段活跃期恰好错峰，于是 $\chi = 4 < 5$ ：四个寄存器装得下五个变量。图着色比「数变量」省下的每一个寄存器，都来自这样的错峰。

4 · Chaitin 化简循环

给冲突图做 $k$ -着色是 NP-hard，Chaitin 的化简循环用一条足够便宜的不变式绕开搜索：度 $< k$ 的顶点可以先摘下压栈，因为无论剩下的图怎么着色，它回来时邻居至多占掉 $\deg < k$ 种颜色，必有空位。摘掉一个点，邻居的度跟着降，常常解锁下一个可摘的点；图摘空后逆序弹栈，每个点取邻居未用的最小编号颜色，一遍完成分配。

化简卡死时（剩余顶点的度全部 $\ge k$ ），挑一个变量溢出 (spill) 到内存：候选按 cost/deg 最小，cost 是该变量在程序里被读写的次数（踢它去内存，每次读写都多一趟访存），deg 是它在冲突图里的度（摘掉它能给多少邻居减负）。

样本程序上两种 $k$ 的对比。 $k = 4$ 时，度为 3 的 $c$ 与 $t$ 打开缺口，全图顺利摘空，零溢出、恰用满 4 个寄存器。 $k = 3$ 时化简第一步就卡死：五个点的度全部 $\ge 3$ ，没有可摘的点。按 cost/deg 挑溢出对象， $n$ 被读写仅 2 次（对照 $i$ 的 5 次、 $s$ 的 4 次）而度是 4，比值全场最小，溢出的是它。

图 4-1 · Chaitin 化简循环在样本程序冲突图上的单步执行。可选寄存器数

k

（2 / 3 / 4）与冲突图（原图，或溢出

n

后重建的图），观察化简压栈、卡死溢出与逆序选色三个阶段；左侧程序清单每行标注该指令的 live-out 集合。

5 · 溢出后的闭环

溢出不是着色的失败收场，而是闭环的下一圈：把 $n$ 踢到内存后它退出寄存器竞争，冲突图重建，剩下 4 个变量 5 条边， $\chi = 3$ ， $k = 3$ 的化简循环一遍走通。真实编译器在这一步会给 $n$ 的每处读写插入 load/store，新的短命临时变量随之出现，所以「分析、建图、化简」要整个重跑，直到某一轮零溢出为止 [1]。

本页的重建省略了 load/store 引入的临时变量：重载进来的值用完即死，活跃期极短，在这张小图上不改变「3 色可行」的结论；真实编译器必须把它们算进去，闭环因此可能不止转一圈。

6 · 结构的回声

若程序是直线代码（没有分支与循环），每个变量从定义到最后一次使用的活跃范围就是一段连续区间，冲突图是区间图，着色多项式最优（见区间图上的会议室分配）。编译器里与之对应的是 linear scan 分配器 [2]：不建冲突图，把活跃区间按起点排序、扫一遍就完成分配，代价是把变量的多段活跃范围合并成一整段区间，可能比图着色多用寄存器，JIT 编译器普遍拿这点精度换编译速度。带上循环与分支之后，活跃范围碎成多段、区间结构不再成立，一般图着色与 Chaitin 闭环才成为必要。区间图在完美图谱系里的理论位置，见着色：顶点、边、列表与完美图。

7 · 参考文献

Chaitin, G. J., Auslander, M. A., Chandra, A. K., Cocke, J., Hopkins, M. E., & Markstein, P. W. (1981). Register allocation via coloring. Computer Languages, 6(1), 47–57.
Poletto, M., & Sarkar, V. (1999). Linear scan register allocation. ACM Transactions on Programming Languages and Systems, 21(5), 895–913.