6.2 寄存器分配

6.2 寄存器分配

本节摘要：寄存器分配把 IR 里的无限个虚拟寄存器映射到目标的有限个物理寄存器：同时活跃的值超过物理寄存器数时，多余的必须"溢出"——搬进栈槽，用前再取。这个映射的质量决定内存流量，进而决定程序速度的大盘；它也是公认最难的编译器子问题之一（最优情形是 NP 完全的图染色）。本节定义活期、干涉与溢出三大概念，给出两大家族——图着色（离线全局最优逼近）与线性扫描（在线快速）——的总览与取舍，并用一段代码演示溢出决策的代价模型。读完你应当能建出干涉图、算出给定代码的溢出压力，并按场景选对分配算法。

指令选择后的 IR 依然活在理想国里：t1、t2、t3……虚拟寄存器要多少有多少。真实芯片只有 16 个通用寄存器（x86-64 还要去掉栈指针等专用者）。分配器的全部工作就是这场"无限到有限"的降落。

一、三个核心概念：活期、干涉、溢出

活期（live range）：一个值的定义点到最后一次使用点之间的区间。注意单位是"值"不是"变量"——SSA 上每个名字天然一个活期（3.2 的红利再次兑现：活期直接从 def-use 链读出，不需要迭代分析），普通形式上则由 4.2 的活跃变量分析切出。

干涉（interference）：两个活期在某个程序点上同时活跃——它们的寿命重叠，不能共用一个物理寄存器。把值当结点、干涉当边，得到干涉图：分配问题被翻译成"给图染色，相邻结点不同色，颜色数 = 物理寄存器数"。图 k-染色是 NP 完全的，这是"寄存器分配是难问题"的数学出处。干涉图的连边规则有个容易想当然的细节：同一值的定义与使用不构成干涉（自己是自己），拷贝指令 a = b 的两端初始不连边——这条"留白"是 6.3 拷贝合并的物理基础。

溢出（spilling）：干涉图的团 size 超过物理寄存器数时，染色失败，必须挑一些值搬出寄存器。被溢出的值拆成两段活期：定义处写栈槽、使用处读栈槽，每段活期重新参赛。溢出代码不是免费的：一次 store + 一次 load（x86 上各约 1–3 拍，还占 load 单元），热循环里每圈各付一次。

二、图着色家族：Chaitin-Briggs 循环

图着色分配的经典形态（6.3 实战详解）分四步循环：

建图 → 简化（度 < k 的结点先拔掉，入栈）
     → 潜在溢出（度 ≥ k 的结点按代价挑出来标记）
     → 选择（出栈逐个上色，邻色可用即可）
     → 真溢出（上色失败者）→ 拆活期插访存 → 回到建图重来
​

它的智能在"简化"上：度小于 k 的结点必然能上色（邻居最多占 k−1 种色），先拔掉不影响可解性；只有"拔无可拔"时才真的面对溢出抉择。Briggs 对 Chaitin 的改进正在此：早期版本把高结点直接判死（悲观溢出），Briggs 版留到选择阶段再判——实践里高结点常因邻居同色而幸存，误判率大幅下降。这个"先拔确定安全的、缓判不确定的"思想，值得超出本领域记住。

三、线性扫描家族：一遍排序一趟扫描

JIT 与快速编译场景等不起图着色的多轮循环。线性扫描（Poletto-Sarkar）把活期投影到数轴，按起点排序，一趟扫描维护"当前占用寄存器集合"：

LinearScan(活期列表 按起点排序, R 个物理寄存器):
    active = 空集（按终点排序）
    for 每个 interval i:
        清理 active 中终点 < i.起点的 → 释放其寄存器
        if active.size == R:                 # 满了
            spill = active 中终点最大者      # 挑"剩余寿命最短"的
            if spill.终点 > i.终点:
                i 拿走 spill 的寄存器; spill 溢出
            else:
                i 溢出
        else:
            i 领一个空闲寄存器
        active.add(i)
​

策略只有一句话：寄存器留给"还要活最久"的值。它不保证最优（不做全局权衡、不管循环内外有别），但复杂度 O(n log n) 且常数极小。两个补丁值得知道：活期分裂（把长活期切成几段分别安置，LLVM 的 greedy 分配器即"带分裂的线性扫描 + 溢出权重"，是 LLVM 默认分配器）与循环感知权重（循环深 1 层溢出代价 ×10，热值优先留守——5.2 说"循环是热点"在分配器里的直接体现）。

两家族的选型对号入座：AOT 编译器（C/C++/Rust 生产构建）用图着色或其现代变体，多花编译时间换运行质量；JIT 基线档（方法第一次被编译）用纯线性扫描，先把代码跑起来，热点再由优化编译器（含图着色）重编——分层编译把"快"与"好"按需分配，是 Java/JavaScript 运行时的标准架构。

四、溢出的代价模型与三个工程观察

溢出谁、留谁，靠代价模型拍板。一次溢出的成本 ≈ (访存次数 × 循环执行频度)，收益 ≈ 腾出的寄存器救活多少其他值。工程上三个观察：

1. 分配质量由最热的循环决定。冷路径溢出 10 次不如热循环溢出 1 次疼——权重函数里循环深度是指数项（深度每加一层，频度乘以典型迭代数）。
2. 优化与分配互相出题。5.2 的外提让值跨圈存活（活期变长、压力变大），内联（5.3）让函数体变大（活期重叠变多）——上游每个优化都在改分配器的输入。
3. 寄存器数量不是唯一变量。部分架构有寄存器窗口/旋转寄存器（分配简化）、x86 的部分写寄存器惩罚（伪依赖）会让"复用寄存器"反而变慢——目标特性进入代价模型，通用教科书模型要按架构校准。

⚠️ 易错点：把溢出当成失败而非设计空间。受控溢出（该溢的溢：冷值、大聚合体、地址重计算便宜者）是好分配的一部分；拼命零溢出反而可能把热值挤出而损害更大。分配器的目标是总时间最短，不是溢出计数为零。

本节要点回顾：

• 活期是值的寿命，SSA 名字直接给出活期；干涉 = 寿命重叠，干涉图是分配的战场；
• k-染色 NP 完全，实践靠"简化优先、缓判溢出"逼近；
• 图着色四步循环：简化 → 潜在溢出 → 选择 → 真溢出回炉，质量优先；
• 线性扫描：按起点排序 + 寄存器留给活得久的，O(n log n)，JIT 基线档标配；
• 代价模型说了算：循环深度是指数项，上游优化改输入，目标特性要校准。

干涉图与简化-着色循环值得逐结点走一遍——下一节全程手算，把这套算法从伪代码变成肌肉记忆。