从 SSA 到物理寄存器：活跃区间、干扰图着色与寄存器分配器的深度工程实战

从 SSA 到物理寄存器：活跃区间、干扰图着色与寄存器分配器的深度工程实战

执行摘要：编译器中端把程序变成 SSA，后端要把它变回"只能有 16 个名字"的机器。这一步叫寄存器分配，它是整个编译流水线中少数几个被证明为 NP-hard的工程问题：图着色可归约到 3-COLORABILITY，而"16 个寄存器够不够"是它的实例。更糟的是它不是一个孤立 pass——它和指令调度耦合（先调度可能把寄存器压力拉爆，先分配又会把调度锁死）、和 ABI 耦合（哪些寄存器调用者保存，哪些被调用者保存，直接决定 spill 放哪）、和调试信息耦合（-O0 的 spill 洪水不是优化没做，而是区间被强制切碎）。本文从 SSA 解构的并行复制语义讲起，给出可运行的线性扫描分配器、图着色的工程化简（Chaitin-Briggs / George-Appel）、spill cost 的加权模型，以及一份生产级调优清单。

一、先算笔账：为什么这件事值得做

寄存器的访问延迟和 L1 大致同量级（约 1 个周期量级），而一次 spill 后的 reload 命中 L1 也需要 4~5 个周期，落到 L2 就是十几个周期。也就是说，一个热循环里多两次 spill/reload，性能就能掉 20%。这就是为什么寄存器分配虽是老问题，却至今仍在被重写：LLVM 从线性扫描换到 Greedy（带区间分裂），HotSpot C2 几十年维持在图着色，V8 TurboFan 在 JIT 预算内用线性扫描，Cranelift 新一代 regalloc2 又回到 SSA 上的线性扫描。

问题的形式化定义很简单：

给定：虚拟寄存器集合 V（SSA 下通常成百上千）
     物理寄存器集合 R（x86-64 有 16 个通用寄存器，ARM64 有 31 个，RISC-V 有 32 个）
     干扰关系 I ⊆ V × V（两个变量在某点同时存活）
求：  映射 f: V → R，使得 ∀(a,b) ∈ I, f(a) ≠ f(b)
     不存在的部分放入内存（spill）

最小化 spill 数量 ≈ 图着色 = NP-hard。所有工业实现都是在编译时间预算内求近似解。

二、第一道坎：SSA 解构与并行复制

SSA 的美在于每个变量只赋值一次，但机器没有 phi 指令。解构 phi 时最容易写错的地方是：同一个基本块里的所有 phi 必须"同时"生效。

BB2:  x = φ(BB0: a, BB1: b)
      y = φ(BB0: b, BB1: a)     // a 和 b 互换

如果在 BB0 里按顺序生成 x = a; y = b;，当 x 和 y 恰好被分配到同一个物理寄存器时就错了——因为 x = a 已经把 a 覆盖了。正确做法是在前驱块末尾插入并行复制（parallel copy），再做顺序化。

并行复制的顺序化本质是打破依赖环。经典做法（Boissinot 等人的算法）分三步：先用"就绪"队列处理可直接赋值的目标，遇到环时插入一个临时寄存器打破它，最后处理环：

def sequentialize(pcopy, assigned):
    """pcopy: list[(dst, src)]，dst 保证互不相同
       assigned: dst -> 已占用的物理寄存器
       返回顺序化的 move 列表，必要时引入 temp"""
    ready, to_do, loc, pred = [], [], {}, {}
    for dst, src in pcopy:
        to_do.append(dst)
        loc[src] = src
        pred[dst] = src
        if dst not in assigned:      # dst 尚未被别的 move 覆盖
            ready.append(dst)

    out = []
    while to_do:
        while ready:
            b = ready.pop()
            a = loc[b]
            loc[b] = b
            out.append((b, a))       # b <- a
            if a in pred and pred[a] == b:
                pred.pop(a)
                ready.append(a)      # b 已腾空，a 现在安全了
        if to_do:
            # 存在环：挑一个未处理的 dst 用临时寄存器打破
            b = next(d for d in to_do if d in loc)
            t = fresh_temp()
            out.append((t, b))
            loc[b] = t
            ready.append(b)
            # b 现在"安全"，下一轮 while 会处理它
    return out

三个容易踩的坑：

1. 临界边（critical edge）：前驱有多个后继、后继有多个前驱时，不能把 move 直接插到前驱末尾，否则会污染另一条路径。必须先拆分临界边插入一个空块。
2. phi 的语义顺序：并行复制必须发生在前驱块执行完所有副作用之后，但不能在该块自己的分支指令之后。
3. coalescing 与解构的先后顺序：先解构再合并会丢失大量机会；工业做法是在 SSA 上直接做保守合并（value-based coalescing），因为 SSA 的干扰判定有线性时间算法，且合并后仍保持 SSA。Cranelift 的 regalloc2 正是这么做。

三、活跃区间：把二维问题压成一维

图着色需要精确的干扰图，构建它代价不小。线性扫描（Linear Scan）的洞察是：如果代码是线性的，那么"同时存活"可以近似为"区间重叠"。

先给每条指令一个编号（linear order position），然后：

def build_intervals(blocks, live_out):
    intervals = {}          # vreg -> [start, end]
    for b in reversed(blocks):          # 逆序保证 def 之前先见到 use
        live = set(live_out[b])
        for instr in reversed(b.instrs):
            for d in instr.defs:
                if d in intervals:
                    intervals[d][0] = instr.pos      # 更新起点
                else:
                    intervals[d] = [instr.pos, None]
                live.discard(d)
            for u in instr.uses:
                if u not in live:
                    live.add(u)
                    intervals.setdefault(u, [instr.pos, None])
                    intervals[u][1] = instr.pos      # 首次见到 = 区间终点
    return {v: tuple(iv) for v, iv in intervals.items()}

注意 live_out 本身需要一次数据流迭代（向后可达 + use/def 传播）。这份"先做 liveness，再扫描"的套路是线性扫描的标准前置；很多人误以为线性扫描不需要数据流分析，其实它只是把干扰图的 O(n²) 边压缩成了 O(n) 的区间端点。

区间的精度直接决定分配质量。两个提升点：

• hole（空洞）感知：x 在位置 10 定义、100 使用，中间某段被 kill 掉又重新定义时，区间不是 [10,100]，而是 [10,40] ∪ [70,100]。LLVM 的 LiveInterval 就是区间列表而非单区间，这让"分裂"成为可能。
• 循环深度加权：spill 一个在三层循环里的变量，代价是外层变量的 10³ 倍。分配器必须把循环深度写进代价模型，否则会做出灾难性选择。

四、可运行的线性扫描分配器

下面是一个能真正跑起来的最小实现（约 60 行），输入是 (start, end) 区间表，输出分配结果与被 spill 的变量：

import heapq

def linear_scan_alloc(intervals, nregs):
    """intervals: {vreg: (start, end)}；返回 (alloc, spilled)"""
    active = []                       # 按 end 排序的最小堆：(end, vreg, reg)
    free_regs = list(range(nregs))
    alloc, spilled = {}, []

    for v, (s, e) in sorted(intervals.items(), key=lambda kv: kv[1][0]):
        # 1. 回收所有已经死掉的区间
        while active and active[0][0] <= s:
            _, dead_v, r = heapq.heappop(active)
            free_regs.append(r)
            del alloc[dead_v]

        if not free_regs:
            # 2. 没有空闲寄存器：spill 结束最晚的那个（经典启发式）
            victim_end, victim_v, victim_r = max(active, key=lambda x: x[0])
            if victim_end > e:        # 受害者比我活得久，spill 它
                active.remove((victim_end, victim_v, victim_r))
                heapq.heapify(active)
                spilled.append(victim_v)
                del alloc[victim_v]
                free_regs.append(victim_r)
            else:                     # 我最长，spill 我自己
                spilled.append(v)
                continue

        r = free_regs.pop()
        alloc[v] = r
        heapq.heappush(active, (e, v, r))
    return alloc, spilled

这个实现体现了线性扫描的全部性格：O(n log n)、单次前向遍历、无回溯。它天然适合 JIT，因为编译时间可以预测。它的弱点是"区间重叠"高估了干扰——x 和 y 的区间重叠不代表它们真的同时存活，在循环体较大时会浪费寄存器。

五、图着色：把质量要回来

AOT 编译器要的是代码质量，会用图着色。Briggs-Chaitin 的迭代框架是：

repeat
    build      —— 构建干扰图
    simplify   —— 反复移除度数 < k 的节点，压入栈（这些必然可着色）
    spill      —— 若不存在度数 < k 的节点，按 spill cost 选一个标记为 potential spill，继续 simplify
    select     —— 弹栈，为每个节点选一个与邻居不冲突的颜色
until 没有节点被 spill
若仍有 spill 节点 → 插入 load/store，重写代码，重跑整个流程

关键工程细节：

• 合并（coalescing）：消除 a = b 这类复制指令。Briggs 的保守合并规则是"合并后节点的高度数邻居少于 k"；George 的迭代合并则是"a 的所有高度数邻居都已被 b 干扰"。LLVM 用后者，因为它不要求预先判断度数，实现更简单。
• spill cost：不是简单计数，而是 cost(v) = Σ_{use/def} 10^loop_depth(v) / interval_length(v)。分子惩罚热循环，分母奖励长区间——一个在循环外定义、循环内使用一次的变量，spill 它比 spill 循环计数器划算得多。
• 活跃区间分裂（splitting）：与其把整个变量 spill 出去，不如在区间中段的"空洞"处切成两半，让两半拿到不同寄存器。这是 LLVM Greedy 相对于老线性扫描最大的收益来源，也是它能把寄存器压力打散到整个函数的原因。
• 重新物化（rematerialization）：如果一个值可以由一条廉价指令重算（比如加载常量、lea 算地址），就不要 spill 它，直接在使用点重算。这条优化在 SSA 上判断非常简单：看定义指令是否 rematerializable 且操作数在use点存活。

一个用 Rust 表达的着色核心（邻接位集 + 贪心选择）：

fn select_color(v: VReg, adj: &[BitSet], colors: &mut HashMap<VReg, usize>, k: usize) -> Option<usize> {
    let mut used = BitSet::empty();
    for n in adj[v.index()].iter() {
        if let Some(&c) = colors.get(&n) { used.insert(c); }
    }
    (0..k).find(|c| !used.contains(*c))
}

真实实现里，k 不是固定的：它要按寄存器类（GPR / FPR / 向量）分别计算，还要扣除 ABI 保留的寄存器（帧指针、栈指针、临时寄存器）。x86-64 上 16 个 GPR 里，扣掉 rsp/rbp 和几个调用者保存的临时寄存器，实际可用往往只有 12~13 个。

六、现实约束：分配器不是活在真空里

1. ABI 与调用约定。caller-saved 寄存器（x86 的 rax/rcx/rdx/rsi/rdi/r8-r11）跨越调用就被破坏，callee-saved（rbx/rbp/r12-r15）则需要被调方保存恢复。一个成熟分配器会在叶子函数里优先使用 caller-saved，把 callee-saved 留给不含调用的热点路径——因为后者保存/恢复的代价是每次函数进入都要付。
2. 固定约束指令。x86 的 div 隐含使用 rdx:rax，返回值固定 rax，ARM64 的 x0-x7 传参。这些是"预着色区间"（fixed interval），必须先在干扰图里固定，再让其他区间绕开。
3. 寄存器对与对齐。ARM64 的 ldp/stp、RISC-V 的压缩指令、x86 的 xmm 对齐要求，都会让"一个值占一个寄存器"的假设失效。
4. 调度与分配的鸡生蛋问题。先做指令调度（提升 ILP）会拉长活跃区间、抬高寄存器压力；先分配会把调度锁死。工业方案是迭代：先调度，分配失败（spill 过多）则回滚并降低调度激进程度，或反过来。LLVM 的 -O2 与 -O3 在这一点上的差异，往往比优化级别本身的差异更能解释性能波动。

七、生产级调优清单

• 先看 spill 在哪，再调参数。用 llc -debug-only=regalloc 或直接看 -print-after=greedy 的 spill 统计；目标是让热循环的 spill 数为 0，而不是全局 spill 数最少。
• 寄存器压力是代码结构的函数。过长的表达式、内联展开过深、循环体内同时持有多个数组基址，都会把压力推高。手写汇编或 intrinsics 时，把循环体的同时存活值控制在 12 以内比任何编译器选项都有效。
• -O0 的 spill 洪水是设计使然。调试构建要求每个源变量都能在任意断点被读，区间被强制在每个语句边界切断，无法合并。不要用 -O0 的性能做任何结论。
• JIT 的预算是微秒级。这也是 V8/C2 分层编译里 baseline 层干脆不做分配（全 spill 到栈）的原因——先跑起来，热了再交给优化层。
• 评估指标要量化：spill bytes / 函数、热循环寄存器压力 p99、reload 次数、编译时间 p99。没有这四项，任何分配器改动都是玄学。

八、结论

寄存器分配是编译后端里少有的"理论硬度"与"工程手感"各占一半的问题：它既需要图着色的复杂度认知，又需要对 ABI、调度、缓存层次的具体判断。判断一支团队是否真正掌握了后端，可以问三个问题：

1. 你的分配器在热循环上的 spill 率是多少？（目标：0）
2. 从发现一个值需要 spill 到决定 spill 谁，你的代价模型是否包含循环深度？
3. 一次区间分裂重写，会触发多少次干扰图重建？有没有增量维护？

答不上来，就说明性能还建立在"编译器应该会处理好"这个假设上——而这个假设，恰恰是生产环境里最贵的一种。