#compilers #优化
本页目录

寄存器分配

编译优化里最体现 NP 难度的一关:把无限虚拟寄存器映射到有限物理寄存器,映射不下时溢出到栈。图着色(Chaitin/Briggs)和线性扫描(Poletto/Sarkar)是两种近似解,SSA 的弦图性质让着色变得容易。

概述

SSA 形式和优化阶段使用无限虚拟寄存器⁠——每个新值都有独立的 %v1、%v2。真正的目标机器只有少量物理寄存器(x86-64 有 16 个通用寄存器,ARM64 有 31 个)且受 calling convention 约束。寄存器分配是把虚拟寄存器映射到物理寄存器——映射不下时溢出(spill)⁠到栈。这是编译优化中最能体现 NP 难度的一关——最优寄存器分配是 NP-complete（图着色）,所以实际用的是近似算法。

前置:活度分析

数据流分析 的 liveness 直接给寄存器分配提供输入:

对于两个虚拟寄存器 v1 和 v2:
  如果存在某个程序点, v1 和 v2 同时活跃(live)
    → v1 和 v2 不能共享同一物理寄存器
    → 在 interference graph 中 v1 和 v2 有一条边

活跃区间(live range)的构造:从每个定义点出发,沿 SSA 的 def-use 链,到所有使用点,这之间的"段"就是该虚拟寄存器的活跃区间。如果有 phi 合并,把 phi 来源和目标的活跃区间连起来。

图着色分配(Chaitin/Briggs)

构造干涉图

节点 = 虚拟寄存器; 边 = 两个虚拟寄存器在任一点同时活跃:

v1 定义于 BB1, 最后使用于 BB3
v2 定义于 BB2, 最后使用于 BB3
在 BB3 入口处 v1 和 v2 都活跃 → v1 — v2 有边

着色 = 给每个节点分配颜色(物理寄存器),相邻节点颜色不同

算法(Chaitin-style):

while 图中还有节点:
    if 存在节点 n, degree(n) < K (K = 可用物理寄存器数):
        从图中移除 n, 把 n 压入栈       ← n 一定能被着色 (邻接节点 < K)
    else:
        选一个 spill 代价最小的节点 s
        标记 s 为 spill, 从图中移除      ← 牺牲它, 放到栈上
        调用 spill_code(s): 生成 store/load 把 s 的值转移到栈

从栈中依次弹出, 给每个节点分配一个颜色 (不和已着色的邻接节点冲突)

Briggs 的改进⁠:不立即判定 degree < K 的节点一定可着色——先乐观地移除它们,在弹出阶段如果发现无法着色的节点,再做 spill。Briggs 的乐观着色在实践中产生的 spill 显著少于 Chaitin 的悲观算法(Chaitin 主动 spill 所有 degree≥K 的节点,很多本可着色的也被溢出了)。

Spill 代码生成

当寄存器不够时,把某个虚拟寄存器的值"溢"到栈:

spill 前:                         spill 后:
  v1 = ...                         v1 = ...
  ... = v1 (use)                   spill [v1_slot] = v1        ← 定义后立即 store
                                    v1_reload = load [v1_slot]  ← 使用前 load
                                    ... = v1_reload

但 spill 改变了活跃区间——原来 v1 只在 ... = v1 处使用,现在 spill 把它的活跃区间拆成两段(v1 和 v1_reload),可能让干涉图更稀疏,从而缓解着色压力。Spill 重新建干涉图并重新分配⁠——这是迭代的。

线性扫描(Poletto/Sarkar):更快但更多 spill

线性扫描用一个简化的活跃模型:不是点精确的干涉图,而是活跃区间的线性顺序⁠:

对所有虚拟寄存器的活跃区间按起始位置排序:
  维护一个"当前活跃"列表
  扫描每个区间:
    expire_old_intervals()  ← 移除已结束的区间, 释放它们占用的物理寄存器
    if 有空闲寄存器:
        分配它
    else:
        从当前活跃中选一个 spill 代价最小的, spill 它
        把腾出的寄存器分配给新区间

线性扫描的复杂度是 O(n log n)(排序),远快于图着色的 O(n²) 或更高。代价:它产生的 spill 比图着色多(因为它不看干涉图,可能 spill 了两个不干涉的区间)。线性扫描在 JIT 编译中常用——编译时间压倒一切,多几个 spill 可接受。

SSA 对寄存器分配的助益

SSA 形式下，变量之间的 def-use 关系天然形成弦图(chordal graph)⁠结构——弦图的着色可以用贪心算法(O(n))得到最优解。但注意：实际寄存器分配通常在 SSA 解构（插入 copy）之后进行，φ 解构引入的 copy 可能破坏弦图性质；不过 coalescing 阶段会尽量合并这些 copy，使着色仍然高效。

Coalescing:消除 copy

v1 = ...
v2 = v1           ← copy: 需要一条 mov 指令
... = v2

如果 v1 和 v2 分配同一寄存器 r:
  r = ...
  ... = r         ← copy 消掉了

coalescing 不是无代价的——把 v1 和 v2 合并成一个节点,可能增加它的 degree,使它变得不可着色。所以 coalescing 是保守的⁠:只 coalesce 在着色之后不会引入 spill 的 copy。Briggs 保守 coalescing 检查合并后的节点 degree < K(可用寄存器);George 保守 coalescing 检查 v1 的所有邻接节点是否"已经和 v2 不冲突或 degree < K"。

Calling Convention 与分配器的互相影响

物理寄存器不仅受虚拟寄存器争用,还受 calling convention 约束:

  • 参数寄存器⁠(x86-64: rdi, rsi, rdx, rcx, r8, r9):函数调用的前 6 个参数必须放在这些寄存器里。
  • 返回值寄存器⁠(rax):函数返回值在 rax。
  • 被调用者保存(callee-saved, x86-64: rbx, rbp, r12–r15):被调函数如果修改了这些寄存器,必须在返回前恢复。由被调函数 spill/restore,调用方不动作。
  • 调用者保存(caller-saved, x86-64: rax, rcx, rdx, rsi, rdi, r8–r11):调用方在 call 前后如果要用这些寄存器,必须自己 spill/restore。

寄存器分配器必须遵守这些约束:⁠函数 prologue 里 spill callee-saved 的物理寄存器到栈⁠,如果在分配过程中使用了它们;在 call 指令前后,不能假设 caller-saved 物理寄存器里的值在 call 之后仍然存活。

参考

  • Chaitin (1982): "Register Allocation and Spilling via Graph Coloring" — 图着色分配的原始论文
  • Poletto/Sarkar (1999): "Linear Scan Register Allocation" — 线性扫描的原始论文
  • LLVM: lib/CodeGen/RegAllocGreedy.cpp (默认分配器), lib/CodeGen/RegAllocBasic.cpp (baseline) — 工业级分配器,结合线性扫描和图着色的混合

Keywords: register allocation, interference graph, graph coloring, Chaitin, Briggs, optimistic coloring, linear scan, spilling, spill code, splitting, coalescing, copy elimination, liveness, live range, chordal graph, register pressure, caller-saved, callee-saved, calling convention, prologue, epilogue, SSA-based allocation

相关页面

© 2026 liz's doc