把寄存器分配搬进 CFG：一次把「图着色」玩成线上火焰图的实战

背景
6 月份给自家 DSL 后端换 LLVM 14，顺手把寄存器分配算法从「简单线性扫描」升级成「基于 CFG 的 Chaitin-Briggs」。结果：同一批脚本 CPU 降 12 %，寄存器溢出指令少 28 %，但调优过程连踩 4 个坑。今天把过程拆成 4 个片段——CFG 构建、活跃变量分析、图着色、溢出修复——所有数字来自 perf stat 与 llvm-mca，表是我手敲的，放心抄。

1. CFG：不是画个箭头就完事

1.1 基本块切分

一开始用 LLVM IR 自带的 MachineBasicBlock，结果碰到 8 MB 的巨型规则脚本，.ll 文件 40 万行，CFG dot 图直接 700 MB，Graphviz 当场 OOM。

结论：别把每条 IR 当节点，顺序指令无脑合并，否则后面算法全白搭。

1.2 临界边分裂

Chaitin 算法要求 CFG 是「可归约图」，但我们手写的 DSL 会生成 switch 嵌套 goto，存在临界边。LLVM 的 SplitCriticalEdge 默认关，需要手动开：

PM.add(createCFGSimplificationPass());
PM.add(createCriticalEdgeSplittingPass());

不开的后果：活跃变量分析漏掉跨边的 φ-node，寄存器分配后莫名多出 6 % mov 指令。

2. 活跃变量：别把死变量当活人

2.1 数据流方程

经典 IN/OUT 方程：

IN[B] = use[B] ∪ (OUT[B] - def[B])
OUT[B] = ∪ IN[succ]

DSL 里大量使用 64-bit mask，结果掩码变量生命周期极短，却占了一个整型寄存器。第一次跑算法时 38 % 的变量被误判为活跃。

办法：在数据流之前跑一次「掩码死码消除」，把只参与位运算、最终结果不使用的变量直接标记 dead。

3. 图着色：贪心 + 合并才是正解

3.1 冲突图规模

一开始用 O(n²) 暴力建图，45 k 个变量直接炸内存。后面改成邻接表 + bucket 排序，内存从 3.2 GB 降到 220 MB。

3.2 合并启发

Chaitin-Briggs 的 coalescing 阶段默认保守，结果 DSL 里大量 mov r1, r2; use r2 被禁止合并，白白多 5 k 条指令。
把 coalescing-threshold 从 1 调到 3（即允许 3 度以内合并），溢出数再降 18 %。

4. 溢出修复：别把栈当无限仓库

4.1 溢出算法

溢出阶段默认 spill everywhere，结果 64-bit 栈槽对齐后多吃了 40 % 内存。我们改写成「按需分段溢出」：

• 只在 def 和 use 点插 load/store；
• 连续使用区间复用同一槽位。

4.2 回滚保护

线上灰度时曾出现寄存器压力极端场景（> 95 % 变量冲突），着色失败回退到「全部栈变量」。为了兜底，在编译期插桩：

if (coloring_failed) {
    emit_trap("REG_SPILL_BACKUP");
}

上线一个月，触发了 3 次，全部落在测试流量，没炸生产。

5. 上线效果总览

6. 血泪 checklist（现场手抄）