图着色与寄存器分配：从 DSatur 到 Chaitin-Briggs

图着色常被一句话概括：相邻顶点不能同色，目标是少用颜色。把它直接搬到编译器里也容易产生误解：既然一般图着色是 NP 完全的，寄存器分配是不是只能碰运气；又或者，既然 SSA 干涉图有弦图结构，现代编译器是不是已经能多项式最优分配。

两句话都不完整。寄存器分配确实可以用干涉图（interference graph）建模，但生产分配器还要处理寄存器类、预着色硬寄存器、调用约定、move 合并、活跃范围分裂和溢出代码插入。本文把问题拆成三层：图着色本身的可证性质，Chaitin 系列分配器如何把它变成可用启发式，以及 LLVM 18 与 GCC 14.2.0 源码里能亲眼看到的工程实现边界。

所有实验数据来自同目录 reproduce/graph_coloring_experiment.py。脚本只用 Python 标准库，固定 5 个随机种子，统计颜色数、\(K=8\) 时的溢出数量与加权溢出代价；三张图也由同一脚本生成。

一、图着色模型只给出约束，不给出工程答案

给定无向图 \(G=(V,E)\)，一个 \(k\)-着色是函数

\[ c:V\to \{0,1,\ldots,k-1\} \]

满足对每条边 \((u,v)\in E\) 都有 \(c(u)\ne c(v)\)。色数（chromatic number）\(\chi(G)\) 是可行着色所需的最小 \(k\)。几个边界足够支撑后文：

贪心着色的行为完全由顶点顺序决定。按自然编号着色可能很差，按最大度数优先（largest-first，也常被放在 Welsh-Powell 一类方法下讨论）通常好一些；最小末序（smallest-last ordering）给出退化度（degeneracy）加 1 的上界；DSatur 则在每一步选择“已着色邻居中不同颜色数”最多的未着色顶点。

DSatur 由 Daniel Brélaz 在 1979 年 CACM 论文中提出。它维护每个未着色顶点的饱和度（degree of saturation）：

\[ \operatorname{sat}(v)=|\{c(u):u\in N(v),\ u\text{ 已着色}\}|. \]

每步选择 \(\operatorname{sat}(v)\) 最大的顶点，平局常用原始度数或顶点编号打破，然后分配最小可用颜色。这个规则不保证一般图最优，但它把“当前最受约束的变量先决定”这件事做成了动态启发式，因此经常比固定顺序贪心少用颜色。

二、从活跃性到干涉图

在寄存器分配中，顶点不是地图区域，而是虚拟寄存器或 live range。若两个值在某个程序点同时活跃，它们不能放进同一个物理寄存器，于是在干涉图里连边。上图左侧是 7 个活跃区间，任意两个区间在时间轴上重叠，右侧就有一条边；右侧颜色表示一个合法分配。

这个模型来自 IBM Yorktown 编译器工作。Chaitin、Auslander、Chandra、Cocke、Hopkins 与 Markstein 的 1981 年 Computer Languages 论文题为“Register allocation via coloring”；Chaitin 1982 年 SIGPLAN Compiler Construction 论文进一步把 spilling 纳入同一框架。经典 Chaitin 分配器可以概括为四个动作：

1. Build：做活跃性分析，构建干涉图，给顶点附上使用频率或循环深度推导出的溢出代价。
2. Simplify：若某顶点当前度数小于物理寄存器数 \(K\)，移除并压栈；直觉是它弹栈时最多看到 \(K-1\) 个已着色邻居。
3. Spill candidate：若剩余顶点度数都至少为 \(K\)，选一个代价低的顶点移除。原始 Chaitin 风格会倾向于把它当成溢出候选。
4. Select：逆序弹栈并选颜色；若没有可用颜色，才真正溢出并在后续重写程序。

Briggs、Cooper、Torczon 1994 年 TOPLAS 论文的关键改进是乐观着色（optimistic coloring）：高于阈值的顶点先压栈，不急着承诺溢出；因为它的邻居未必会使用 \(K\) 种不同颜色，Select 阶段可能仍然能成功。下面的小例子由脚本按同一规则模拟，展示 \(K=3\) 时哪些顶点安全压栈，哪些只是乐观候选。

这里的“溢出代价”不是数学定理，而是工程模型。一个值在冷路径上使用 100 次，和在内层循环里使用 3 次，真实代价可能完全不同；目标机器是否有寻址模式、寄存器对、调用者保存寄存器，也会改变选择。因此寄存器分配论文里的图着色算法进入编译器后，很快就变成一组互相制约的启发式。

三、合并、分裂与 SSA 弦图特例

只把干涉边画出来还不够。真实机器码里有大量复制指令，例如 x = y、参数传递、PHI 消除后的并行复制。若两个 live range 不干涉，把它们放进同一个寄存器可以删除 move，这叫寄存器合并（register coalescing）。

合并有风险：把两个顶点合成一个顶点会提高度数，可能让原本可着色的图变成需要溢出。Briggs 的保守合并规则要求合并后高度数邻居少于 \(K\)；George 与 Appel 1996 年 POPL/TOPLAS 的迭代合并把 simplify、coalesce、freeze、spill 交错执行，避免“一口气合并完再发现图爆炸”。Bouchez、Darte、Rastello 2007 年 CGO 论文从复杂度角度说明，coalescing 本身也不是一个可以随手最优解决的小问题。

SSA 形式带来另一条线索。Hack、Grund、Goos 2006 年 Compiler Construction 论文证明，在合适假设下 SSA 程序的干涉图是弦图；Pereira 与 Palsberg 2005 年 APLAS 论文也利用弦图着色做寄存器分配。弦图有完美消除序，最优着色可以在多项式时间完成。本文实验里的 chordal-k8 用生成式弦图验证了这一点：已知消除序的贪心颜色数等于最大团大小。

但是这不等于生产分配器已经“解决”寄存器分配。SSA 消除、move 合并、寄存器类、子寄存器、预着色硬寄存器、调用约定和溢出代码插入，都会把问题重新推回启发式组合优化。把“SSA 干涉图是弦图”理解成一个强结构化子问题，而不是完整后端的终点，更接近工程现实。

四、LLVM 18 与 GCC 14.2.0 源码里能确认什么

生产实现只能写钉住版本源码里看得到的事实。本文检查的是 LLVM 18.1.8 与 GCC 14.2.0。

LLVM 18.1.8 的 llvm/lib/CodeGen/RegAllocGreedy.cpp 注册了名为 greedy 的分配器：

• 文件中有 RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator)。
• RAGreedy 的 pass 依赖包括 LiveIntervals、RegisterCoalescer、LiveRegMatrix、SpillPlacement、VirtRegMap 等；这说明它不是“单纯 DSatur”或“单纯线性扫描”。
• 源码里的隐藏选项显示，split-spill-mode 默认是 SplitEditor::SM_Speed；last chance recoloring 的默认深度 lcr-max-depth 是 5，单次考虑的干涉数 lcr-max-interf 是 8；enable-deferred-spilling 默认是 false。
• 同版本 llvm/lib/CodeGen/LiveIntervals.cpp 的 LiveIntervals::runOnMachineFunction 会获取 SlotIndexes，计算虚拟寄存器 live interval、reg mask 和 live-in reg units。也就是说，greedy allocator 操作的主要对象是 live interval 与 live range matrix，而不是一张教材式静态邻接矩阵。

GCC 14.2.0 的 gcc/ira-color.cc 文件注释写明它包含“regional graph coloring, spill/restore code placement optimization”。同文件里 color_allocnos 有两条路径：IRA_ALGORITHM_PRIORITY 走优先级式分配，否则进入 Chaitin-Briggs 风格路径；该路径里能看到 colorable_allocno_bucket、uncolorable_allocno_bucket、allocno_stack_vec、push_allocnos_to_stack() 与 pop_allocnos_from_stack()。源码还用 calculate_allocno_spill_cost() 和 allocno_spill_priority() 给不可着色候选排序。

这两份源码共同说明一件事：现代 AOT 编译器仍然继承图着色语言，但真正的实现单位是 live interval、allocno、寄存器类和 spill/split/coalesce 决策，不是一段“调用 DSatur 得到颜色”的流程。

五、实验：颜色数与 \(K=8\) 溢出代价

运行方式：

cd post/algorithms/50-graph-coloring
python3 reproduce/graph_coloring_experiment.py

脚本生成 4 组图，每组 5 个种子：

• er-p006 与 er-p012：Erdős-Rényi 随机图 \(G(n,p)\)，\(n=120\)，分别取 \(p=0.06\) 与 \(p=0.12\)。
• chordal-k8：按“新顶点连接到一个既有 clique 的子集”生成的弦图，同时记录最大团大小 \(\omega\) 与可用于最优着色的顺序。
• interval：随机活跃区间重叠得到的区间图，模拟寄存器压力；区间图是弦图，但这里刻意只比较 largest-first、DSatur 与 \(K=8\) 分配，不把消除序喂给算法。

环境记录在 reproduce/results/environment.txt：Python 3.14.5，Linux 6.6.87.2 WSL2，GCC 16.1.1；脚本只依赖 Python 标准库。指标都是颜色数、溢出个数和加权溢出代价，与时钟无关。coloring-experiment.svg 和两个 CSV 由同一次运行生成。

这张表只支持三条有限结论。

第一，在两组随机图上，DSatur 比 largest-first 少用颜色，差距在较密的 er-p012 上更明显：平均 6.80 色对 8.00 色。它说明动态饱和度启发式有价值，但不能外推出“DSatur 总是最优”。

第二，弦图组里最大团大小、largest-first、DSatur、已知顺序贪心全部是 4.40。这个生成器构造的图很温和，所以 largest-first 也刚好达到下界；真正要引用的性质是“有完美消除序时弦图可最优着色”，不是“largest-first 对所有弦图都最优”。

第三，区间图的平均 clique pressure 是 11.20，若只有 \(K=8\) 个寄存器，Chaitin-Briggs 风格分配器必须溢出：平均 5.40 个顶点、加权代价 37.80。颜色数实验和溢出实验回答的是两个问题：前者问“图本身需要多少颜色”，后者问“给定硬件寄存器不足时，牺牲哪些 live range”。

六、工程选型：什么时候看图，什么时候看区间

把图着色用于寄存器分配时，最容易犯的错是把“颜色数最少”当成唯一目标。编译器真正关心的是生成代码的总代价：多一次 spill load/store、少一条 move、破坏一个 callee-saved 寄存器、延长一个热点循环里的 live range，代价都不相同。

因此几个经验边界要分开：

• 若目标是解释约束，干涉图是最清晰的模型：同时活跃就连边，物理寄存器数就是颜色上限 \(K\)。
• 若目标是做一般图着色实验，DSatur 是强基线；但在大图上要注意朴素实现会反复扫描未着色顶点。
• 若目标是 AOT 编译器质量，Chaitin-Briggs、iterated coalescing、live range splitting 和目标相关 spill cost 比“换一个颜色选择规则”更重要。
• 若目标是 JIT 编译速度，Poletto 与 Sarkar 1999 年 TOPLAS 的线性扫描（linear scan）仍然是核心谱系；现代 JIT 会再加上 interval splitting、hole 处理和目标约束。
• 若输入保持 SSA 且机器约束较弱，弦图结果给出了强理论支撑；一旦进入后端约束和 coalescing，仍要回到启发式。

开放问题不在于“有没有一个更聪明的 DSatur 变体”。真正难的是在多目标代价模型下做稳定决策：少 spill、少 copy、尊重寄存器类、控制编译时间，并且在不同目标架构上都不过拟合。LLVM 与 GCC 源码里大量与 split、coalesce、spill placement、hard register preference 相关的代码，正是这个工程间隙的体现。

七、参考资料

源码

• LLVM 18.1.8, llvm/lib/CodeGen/RegAllocGreedy.cpp：RAGreedy pass、greedy 注册、split/spill/recolor 选项与 pass 依赖。
• LLVM 18.1.8, llvm/lib/CodeGen/LiveIntervals.cpp 与 llvm/include/llvm/CodeGen/LiveIntervals.h：LiveIntervals::runOnMachineFunction、computeVirtRegInterval、SlotIndexes 相关接口。
• GCC 14.2.0, gcc/ira-color.cc：regional graph coloring、Chaitin-Briggs bucket/stack、color_allocnos、push_allocnos_to_stack、pop_allocnos_from_stack、spill priority 相关代码。

核心论文

• Daniel Brélaz, “New methods to color the vertices of a graph,” Communications of the ACM, 1979. DOI: https://doi.org/10.1145/359094.359101。
• Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, Peter W. Markstein, “Register allocation via coloring,” Computer Languages, 1981. DOI: https://doi.org/10.1016/0096-0551(81)90048-5。
• Gregory J. Chaitin, “Register allocation & spilling via graph coloring,” SIGPLAN Symposium on Compiler Construction, 1982. DOI: https://doi.org/10.1145/800230.806984。
• Preston Briggs, Keith D. Cooper, Linda Torczon, “Improvements to graph coloring register allocation,” ACM Transactions on Programming Languages and Systems, 1994. DOI: https://doi.org/10.1145/177492.177575。
• Lal George, Andrew W. Appel, “Iterated register coalescing,” ACM Transactions on Programming Languages and Systems 18(3):300–324, 1996（会议版见 POPL 1996，DOI 10.1145/237721.237777）. DOI: https://doi.org/10.1145/229542.229546。
• Massimiliano Poletto, Vivek Sarkar, “Linear scan register allocation,” ACM Transactions on Programming Languages and Systems, 1999. DOI: https://doi.org/10.1145/330249.330250。
• Sebastian Hack, Daniel Grund, Gerhard Goos, “Register Allocation for Programs in SSA-Form,” Compiler Construction, LNCS 3923, 2006. DOI: https://doi.org/10.1007/11688839_20。
• Fernando Magno Quintão Pereira, Jens Palsberg, “Register Allocation Via Coloring of Chordal Graphs,” APLAS, LNCS 3780, 2005. DOI: https://doi.org/10.1007/11575467_21。
• Florent Bouchez, Alain Darte, Fabrice Rastello, “On the Complexity of Register Coalescing,” CGO, 2007. DOI: https://doi.org/10.1109/CGO.2007.26。

实验

• reproduce/graph_coloring_experiment.py：生成随机图、弦图、区间图，运行 largest-first、DSatur 与 Chaitin-Briggs 风格 \(K=8\) 分配，输出 reproduce/results/graph_coloring_raw.csv、graph_coloring_summary.csv 和三张 SVG。

上一篇: PageRank 与随机游走：从链接投票到工程实现

下一篇: 用户态内存分配器：size class、线程缓存与碎片边界

相关阅读: - 寄存器分配：图着色与线性扫描 - SSA 形式与编译器优化 - Tarjan 算法族：SCC、割点、桥的统一框架