寄存器分配

IR 可以为每个中间值起一个新名字，目标机器却只有有限且功能不同的寄存器。寄存器分配决定值在各段执行中位于哪个寄存器或栈槽，并插入必要的数据移动。

它不是一次性给所有变量选一个永久位置。一个值可以先在寄存器里、跨调用暂存到栈、再重载到另一个寄存器。实际质量常取决于如何切分这些区间。

活跃范围与干涉

若未来某条路径会在覆盖前使用某值，该值在当前位置活跃。不同值若必须同时保留且不能共享表示，就对同一物理寄存器产生竞争。干涉图用边表达此类限制。

CFG 中的活跃范围可能有分支和空洞，不等于源码行号上的一个连续段。SSA 的 φ 输入在对应前驱边上使用，不能把不同前驱的输入一律视作在汇合块入口同时使用，更不能无条件把所有 φ 来源与结果活跃范围连成一个整体。

图着色：先用简化模型理解

在 K 个可互换寄存器、只考虑两两干涉的模型中，寄存器是颜色，相邻节点必须异色。一般 K 着色判定是困难问题，优化 spill 成本又是进一步问题；不能把整个现实分配过程简单等同于一个 NP-complete 决策题。

简化算法反复移除当前度数小于 K 的节点并压栈。恢复时，其已着色邻居最多 K−1 个，总有一个颜色可用。这个推理依赖可互换颜色等假设，固定寄存器与类别限制需要扩展处理。

乐观着色：高连接度不代表一定无法分配

当剩余图没有低度节点时，可选择一个潜在 spill 候选继续移除，但暂不立即生成 spill。恢复着色时，若仍有颜色就正常分配，确实无色才溢出。

这就是乐观的关键：⁠对高于或等于 K 度的候选暂缓判定⁠，不是怀疑低于 K 度节点的可着色性。高度节点的邻居可能共用颜色，因此邻居数量多不等于已经占满所有颜色。

实际候选成本通常结合使用频率、循环权重、重载成本与活跃范围。把热循环里反复用的值溢出，往往比冷路径上的值更贵。

四边形反例：所有节点度数等于 K，仍可用 K 个颜色

取 K=2，图的边为 A—B、B—C、C—D、D—A。每个节点度数都是 2，按“度数严格小于 K”规则没有可立即简化的节点；但 A/C 共用一个寄存器、B/D 共用另一个就足够。

乐观分配可以先把 A 当作潜在 spill 候选移走。剩余路径 B—C—D 的端点度数为 1，能够继续简化；恢复时 B 和 D 可以共用颜色，因此 A 仍有另一颜色。候选标记的含义是暂时无法用低度证明保证成功，不是已经证明必须生成访存。

下面用小图穷举作为结果核对工具，不用它模拟工业分配器的性能。四边形能二着色，三角形不能；“高度节点不一定失败”和“资源确实可能不足”在同一模型中都成立。

from itertools import product


def coloring(nodes, edges, k):
    for colors in product(range(k), repeat=len(nodes)):
        assigned = dict(zip(nodes, colors))
        if all(assigned[a] != assigned[b] for a, b in edges):
            return assigned
    return None


square = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A")]
assert coloring("ABCD", square, 2) is not None
triangle = [("A", "B"), ("B", "C"), ("C", "A")]
assert coloring("ABC", triangle, 2) is None
assert coloring("ABC", triangle, 3) is not None

这张四边形是一般干涉图模型的例子，不作为后文“严格 SSA 的弦图性质”的例子。四边形没有弦，不能一面用它解释一般图的乐观简化，一面又声称它满足严格 SSA 模型的全部前提。

每个节点度数都很高，就一定需要 spill 吗？

度数条件提供的是一种充分保证，不是不可分配的判决。四边形在 K=2 时没有低度节点，但把两个不相邻节点放入同一寄存器即可合法分配。下面既允许手动试颜色，也用小图穷举给出独立的可行性结论；手工分配冲突与整个图确实不能 K 着色，应当分开读。

Spill、拆分与重计算

Spill 在需要时把值保存到栈，在后续使用前重载。保存和加载的位置可以优化，不必永远“定义后立即写、每次使用前立即读”。插入的新指令产生新的短期值与约束，可能需要继续分配。

活跃范围拆分允许热区段留在寄存器，冷区段暂存。Rematerialization 对便宜、可安全重建的值重新计算，例如某些常量或地址，避免内存读写。重计算也要遵守异常、副作用和目标成本。

栈槽同样可以在生命周期不重叠时复用，但对齐、大小、GC 引用映射与调试信息必须正确更新。

线性扫描：按程序布局处理区间

基础线性扫描把活跃范围近似为区间并按起点排序，维护当前占用寄存器的 active 集合。新区间开始时释放已结束区间；资源不足则选择新区间或现有区间的一部分溢出。

基础近似可能把真实生命周期中的空洞也算作活跃，增加不必要压力。改进版本可以处理空洞、固定区间、分裂和位置约束。它常用于重视编译延迟的场景，但不能断言任何线性扫描都比任何图分配器更差或更快。

复杂度取决于排序、区间数据结构与拆分策略。比较应基于具体实现、编译时间和最终 spill，而不是给两个算法各贴一个无条件复杂度标签。

Coalescing：消除 copy，也可能增加压力

若 v2=v1 两侧可使用同一寄存器，copy 可以消失。但合并两个节点会合并其邻接约束，可能让原本容易着色的图更困难。

经典 Briggs 保守判据关注合并邻居中度数至少 K 的高风险节点数量是否少于 K，并不是简单要求合并后的总度数小于 K。George 风格判据则检查一个节点的邻居是否低度或已与另一节点相邻等条件，常结合预着色处理。

这些判据是在特定图着色模型中的充分条件，不是所有机器约束下都适用的万能公式。实现也可以在分配后做 copy 消除，或通过分裂减少过度合并造成的压力。

没有直接干涉的两个节点，合并后也可能提高颜色数

先看路径 A—B—C—D，它可以交替用两个颜色。A 与 D 没有边，如果某个候选 copy 合并想让两者永久共用位置，将它们合成 M 后，原有边变成 M—B、B—C、C—M，得到必须用三个颜色的三角形。

from itertools import product


def can_color(nodes, edges, k):
    for values in product(range(k), repeat=len(nodes)):
        colors = dict(zip(nodes, values))
        if all(colors[a] != colors[b] for a, b in edges):
            return True
    return False


path = [("A", "B"), ("B", "C"), ("C", "D")]
assert can_color("ABCD", path, 2)
rename = {"A": "M", "B": "B", "C": "C", "D": "M"}
merged = [(rename[a], rename[b]) for a, b in path]
assert not can_color("MBC", merged, 2)
assert can_color("MBC", merged, 3)

这里把 copy 候选与干涉边分开看：候选表示希望消除的移动，边表示禁止共享位置的约束。没有 A—D 边只说明两者不直接冲突，没有证明将二者的其他约束合起来仍能用同样数量的寄存器。保守合并判据正是为避免这种间接压力增加；拒绝合并也不意味着 copy 一定永久保留，后续分裂或局部消除仍可能处理它。

没有直接冲突，合并后为什么反而不够分？

合并节点时必须带走它们全部的邻接约束。下面将 A、D 的两个名字折成同一个 M，原先分处两端的约束就闭合成三角形。这个反例说明“没有直接干涉”不足以批准永久合并；是否拒绝某次 coalescing，仍应由所用判据与目标约束决定，不能反过来理解为所有 copy 都应该保留。

SSA 为什么有帮助，又为什么没有消除全部困难

严格 SSA 下、按正确 φ 边语义构建的干涉图具有可利用的弦图性质。在理想寄存器模型中，可通过合适顺序高效求得最少颜色；这说的是干涉图⁠，不是 def-use 图本身。SSA 寄存器分配论文

现实还有 spill 选择、copy 合并、寄存器类别、预着色、子寄存器重叠和指令约束。SSA 解构中的并行 copy 也需要正确调度；最优理想着色并不等于整套目标分配已经解决。

ABI 与指令约束

跨调用存活值不能无保护地放在 caller-saved 寄存器中。可以选择 callee-saved、保存重载或拆分；使用 callee-saved 又可能引入本函数的保存恢复成本。

参数和返回值规则依类型及 ABI 分类，不能把所有 x86-64 值都按“前六个整数寄存器、返回 RAX”处理。二地址指令、隐式寄存器和向量寄存器组还会引入额外绑定。见目标代码与 ABI。

观察分配质量

最终应检查机器码与目标负载。改变内联、调度或循环展开会改变活跃范围，因此寄存器分配是整条后端流水线的一部分。

参考

• Register Allocation for Programs in SSA-Form。
• LLVM Code Generator。
• 数据流分析。

Keywords: register allocation, interference graph, coloring, optimistic coloring, linear scan, spill, splitting, rematerialization, coalescing