6.3 寄存器分配：图着色实战

6.3 寄存器分配：图着色实战

本节摘要：寄存器分配把变量映射到有限的物理寄存器：活跃区间重叠的变量互相冲突，构成冲突图；K 个可用寄存器即 K 种颜色，图着色成功则人人有寄存器，失败则选牺牲者溢出到栈内存。本节给主线语句参与的一段代码完整走一遍冲突图构造、启发式着色与溢出重写。

阅读完本节，你应当能够：

1. 由活跃区间构造冲突图
2. 执行简化、溢出、选择的着色算法循环
3. 描述溢出后的重写与再分配流程
4. 说明寄存器合并如何消除 φ 引入的复制

冲突图：谁不能同住

两个变量不能共用寄存器，当且仅当它们的活跃区间重叠——其中一方活跃时另一方也活跃，同时都要有值。第 5.4 节的活跃变量分析在这里兑现：先算出每个变量每条指令处的活跃性，再两两检查重叠，连边成图。

代码与活跃区间（temp 系列为临时变量）：
1  t1 = price * qty        t1:[1,3]  price:[1,1] qty:[1,1]
2  t2 = t1 - discount      t2:[2,4]  t1 到 3 是因为下一行还在用
3  t3 = t2 * rate          t3:[3,5]
4  t4 = t1 + t3            t4:[4,6]  t1 在此最后一次用
5  total = t4 * 2.0        total:[5,7]

冲突判定（重叠即连边）：
t1 与 t2 重叠（2 到 3）→ 连边
t1 与 t3 重叠（3）→ 连边
t1 与 t4 重叠（4）→ 连边
t2 与 t3、t4 重叠 → 连边；t3 与 t4 重叠 → 连边
total 与 t4 重叠 → 连边；total 与 t3 不重叠 → 不连边

冲突图邻接表：
t1: t2 t3 t4
t2: t1 t3 t4
t3: t1 t2 t4
t4: t1 t2 t3 total
total: t4
price qty 互不冲突且与谁都几乎不重叠
​

着色：三步循环

设可用 3 个寄存器（扣除约定保留后）。算法三步循环：

简化：删去度数小于 K 的节点入栈（它总有颜色可用）
溢出候选：若所有节点度数都不小于 K，选一个牺牲者（启发式：
          度数除以使用次数，代价收益比最差的先扔）标记溢出
选择：栈弹出节点依次着色（避开邻居已用色）

本例（K=3）：
total 度 1 < 3 → 入栈
t2 度 3？3 不小于 3，但删边后度数会降：
  删 total 后 t4 度 3，仍不小于 3？K=3 时"小于 K"是 0、1、2
  t4 度 3 → 不满足；看 t1 t2 t3 度均 3 → 进入溢出抉择
  启发式选中 t2（用得最少）标记溢出，从图中移除
继续简化：t1 度 2、t3 度 2、t4 度 2 → 依次入栈
选择：t4 得 r1，t3 得 r2，t1 得 r1（与 t4 不冲突？t1-t4 有边！改 r3）
      t2 溢出 → 重写后再分配（见下）
      total 得 r1（t4 已弹出？total 与 t4 有边，但 total 在 t4 之后
      着色，避开 t4 的 r1，得 r2）
​

溢出：重写与再来

被标记溢出的 t2 不是直接进内存完事——插两条访存指令，给它在栈帧开一个槽：

重写：
2  t2 = t1 - discount
   spill_t2 = t2          ← 新增：存入栈槽（store，代价 2）
3' t3 = spill_t2 * rate   ← 原来引用 t2 处改为重载（load，代价 2）
4' t4 = t1 + t3

重写后 t2 的活跃区间被打碎成两个短区间，
各自与其他变量的重叠大幅缩小 → 重新构造冲突图、重新着色
新图大概率 3 色可解：碎片 t2a 只在 2 到 2' 活跃，与 t3 不再重叠

最终分配（示意）：
t1→r3  t2a→r2  t2b→r2  t3→r2  t4→r1  total→r1  price→r1  qty→r1
代价账：溢出多付 4（两次访存），换来其余全员寄存器
​

溢出循环可能跑几轮（每轮可能产生新的溢出），工业实现设上限并接受次优。哪个变量当牺牲者的启发式很有讲究：用得少的、区间长的、不在循环里的优先扔——循环里的溢出每圈都要付两次访存，是双倍亏。

图 冲突图着色：简化、溢出、选择的循环

φ 的善后与寄存器合并

第 5.5 节留下的伏笔在此结账。φ 消解的朴素做法是前驱块尾插复制指令，而复制要花钱。寄存器合并（coalescing）是更聪明的路：φ 的输入输出若活跃区间不重叠（即冲突图中无边），直接分同一个颜色，复制指令整个消失。合并让图更稠密（合并节点继承两边的边），可能引发新的溢出——激进的合并省复制但挤寄存器，保守的合并反之，这个度是各编译器调优的保留节目。Chaitin 式经典分配器偏激进，LLVM 的贪婪分配器走保守路线并配合优先级队列，热循环里的变量优先保住寄存器。

⚠️ 常见坑：在循环里溢出热点变量。溢出的代价不是常数而是"圈数乘访存"，内层循环每圈多两次访存，一百万圈就是两百万次。启发式必须把使用密度与循环深度算进牺牲者评分，只看度数会犯大错。

💡 关键直觉：寄存器分配的视角转换很妙——"变量分寄存器"这个工程问题，被抽象成"图着色"这个数学问题，四十年的图论工具立刻全部可用（可 K 着色性判定本身就是 NP 完全，所以启发式，但理论与工具的接口已经打开）。编译器里这样的"问题翻译"还有多处，识别它们是欣赏这门学科的关键。

分配器的进阶话题

问：32 个寄存器怎么还会不够用？ 三个原因叠加。调用约定先切走一块（传参、保留寄存器）；浮点与向量有独立的寄存器族各算各的；最关键的是活跃区间——长寿命变量横跨整个函数，与所有后来者冲突，一两个大数组下标的计算就能把冲突图撑成几乎完全图。着色失败的根源从来不是变量个数，是活跃区间的重叠结构。

问：线性扫描分配是什么，为什么即时编译偏爱它？ 把活跃区间按起点排序后一次线性扫描，区间重叠才抢寄存器，溢出即时决定。它放弃了图着色的最优性，换来快一个数量级的分配速度——即时编译的编译时间预算以毫秒计，等不起图着色的多轮迭代。编译速度与代码质量的交换，在这里又一次明码标价。

本节要点回顾

• 冲突图：活跃区间重叠连边，活跃变量分析提供原料
• 三步循环：简化入栈、溢出候选、弹出着色，K 色对应 K 寄存器
• 溢出重写：栈槽加存取指令，区间打碎后重跑，代价是访存税
• 牺牲者启发式：使用密度与循环深度进评分，循环内慎溢
• 寄存器合并：φ 相连且不冲突者同色，复制消失；激进保守有度

后端收官，主线语句已是带寄存器的汇编。下一章进入运行时环境：这些指令加载后，栈帧如何搭、参数如何传、它如何真正算出 total 的值。