6.3 图着色寄存器分配实战

6.3 图着色寄存器分配实战

本节摘要：本节把 6.2 的 Chaitin-Briggs 图着色从伪代码变成一次完整的手工推演：8 个活期、3 个物理寄存器，从活跃分析建干涉图开始，走完简化、潜在溢出、选择、着色四步，再演示溢出回炉与拷贝合并（coalescing）如何顺手消灭 De-SSA 留下的拷贝指令。全程纸笔可复算。读完你应当能独立完成 10 结点以内干涉图的分配，并对"简化顺序影响结果吗""溢出谁最划算""合并为什么可能有害"这三个高频疑问给出确切答案。

6.2 给了算法骨架，本节填进真实数字。设定：目标机器 3 个通用寄存器（k=3），一段优化后的代码，共 8 个活期。开始之前确认单位——着色对象是活期（值），不是变量名。

一、样例代码与干涉图构建

b1: a = 1          # a 活: b1..b3（最后用在 b3）
    c = 2          # c 活: b1..b2
    d = a + c      # d 活: b1..b2
    e = d * 2      # e 活: b1..b1
b2: f = a + d      # f 活: b2..b3
    g = c + 1      # g 活: b2
b3: h = a + f      # h 活: b3
    return h
​

按活期区间两两求交（6.2 的定义：寿命重叠即干涉，拷贝端点留白），建出干涉表。为便于手算，先列区间，再连边：

区间: a:[b1,b3] c:[b1,b2] d:[b1,b2] e:[b1,b1] f:[b2,b3] g:[b2,b2] h:[b3,b3]

b1 同时活: a,c,d,e → e 与 a,c,d 互干；a,c,d 互干
b2 同时活: a,c,d,f,g（d 与 f 在 d 定值处交接：定值点使用旧值不算干涉 → d-f 不连）
b3 同时活: a,f,h → a,f,h 互干
边集: a-c a-d a-e a-f a-h  c-d c-e c-g  d-e  f-h  （e-d 与 c-d 等已列；e 与 f/g/h 不重叠）
​

核对几个易错处：e 只在 b1 活，与 b2 之后的 f/g/h 无缘；g 与 d 同块，但 g 的定值不使用 d，且 d 在 g 定值后即死——同块相邻定值是否干涉取决于"定值点是否互相引用"，本例 g = c + 1 不碰 d，d 的活期在 g 之前结束，不连。这张图就是分配的全部输入。

图：干涉图着色全过程——简化栈与选择序

二、逐步解说：每一步在防什么错

简化阶段（度 < k 反复拔）：e(3)、g(1)、h(2)、f(2)、c(2)、d(2) 依次入栈。注意度的动态性——拔掉 e 后 c 的度从 4 降到 2，"拔低度"会连锁解锁新的低度结点，所以要循环到拔无可拔。剩下的 a 度 4 ≥ 3，按 Briggs 规则不立刻判溢出：标记为潜在溢出，照常入栈（栈底）。这步的哲学：高结点只在"邻居最终占满 k 色"时才真溢出，而邻居们互相抢色的情况并不罕见——早判早错。

选择阶段（出栈回填）：a 先上 R1。c 邻 a，取 R2；d 邻 a、c，取 R3；f 邻 a、h（h 未上色），取 R2；h 邻 a、f，取 R3；g 邻 c，取 R1；e 邻 a、c、d——三个邻居恰好占满 R1/R2/R3，真溢出！本例走到了 k=3 的极限：e 必须进栈槽。

溢出回炉：e 拆成 store e; ...; load e 两段短活期，重新建图分配。e 恰好只活一个块（最冷的值），拆分后新活期各度 ≤2，重分配轻松通过。这个结局呼应 6.2 的代价模型：要溢就溢冷值——e 是全图唯一"零循环频度"的活期，代价模型里它本来就该排第一个。

三、拷贝合并：分配器的第二职业

De-SSA（3.5）留下成堆 x3 = x1 式拷贝。干涉图上，拷贝两端若不干涉（6.2 的"留白"），可以把两个结点合并成一个——两个名字共用一个物理寄存器，拷贝指令即成空操作，选择阶段自动消失：

合并前: x1 → R2, x3 → R2, 保留 mov x3, x1   （1 条指令）
合并后: x1∪x3 → R2, mov 被删除             （0 条指令）
​

但合并是危险的交易：合并后的超级结点度数 = 两结点邻居并集，度 ≥k 的可能性变大，可能把本来可染的图推过悬崖。所以现代分配器做保守合并：只合并"合并后度 < k"或"邻居中存在度 < k 者（Briggs 准则）"的对子——保证合并不会让可染图变得不可染。6.2 说"激进合并把不相连的结点焊死"，本节给出了焊死的准确条件与安全线。

三个高频疑问收尾。简化顺序影响结果吗：影响颜色的具体指派（对称换色），不影响"能否 k 染"的判定——低度结点的存在是结构性保险；但启发式顺序会影响哪些结点被判潜在溢出，工程实现用"溢出代价低者优先"排序。同色邻居为什么不会出现：选择时查的是"已上色的邻居"，未上色者不计——这正是简化序的用意：栈里后上的先出，出栈时它的"危险邻居"还没上色。什么时候必须真溢出：团数 > k（比如 k+1 个值互为邻居）时无解，与顺序无关——染色失败下界的快速检查法就是找大团。

本节要点回顾：

• 建图三规则：寿命重叠连边、定值点使用旧值不算干涉、拷贝端点留白；
• 简化：反复拔度 <k 结点入栈，连锁解锁；剩余高结点缓判潜在溢出；
• 选择：出栈上色，只查已上色邻居；上色失败者溢出，拆活期回炉；
• 保守合并：拷贝端点不干涉才合并，且合并后不推高可染性——拷贝指令的免费消除；
• 溢出排序：按代价模型（循环频度加权），先溢冷值。

值们住进了寄存器，但指令的次序还欠打磨：依赖没满足会算错，次序不佳会空转。下一节在依赖 DAG 上排出好次序。

常见问题三则

问：6.2 讲的线性扫描与这里的图着色，差距到底多大？ 量级取决于代码形态。直线代码为主、活期短（多数业务代码），两者产物几乎无差；活期长且大量重叠（寄存器密集的数值内核、深度内联后的代码），图着色的全局权衡能省下可观的溢出流量。分层编译的策略正是据此设计：基线档用线性扫描抢编译速度，热点档用图着色抢运行质量——两种算法各司其职，不存在谁淘汰谁。

问：简化顺序影响颜色分配吗？ 影响具体谁拿哪个寄存器（对称换色），不影响"能否 k 染"的判定本身——低度结点的存在是结构性保险。但顺序会改变哪些结点被标记为潜在溢出，工程实现因此用溢出代价排序：冷值先入栈、热值殿后，让"被迫溢出"的板子打到最不疼的位置。

问：合并（coalescing）会做过了头吗？ 会，这就是 6.2 提到的激进合并陷阱。把大量拷贝端点全部焊成超级结点，干涉图的团 size 上升，本来可染的图被推成溢出——省了三条 mov，赔进两次访存。保守合并（只合"合并后不推高可染性"的对子）是理论上的安全线，现代分配器还会加一层频度权重：热路径上的拷贝优先合并，冷路径上的放过。