第8章 寄存器分配（有限的硬件资源）
一、导读
1.1 本章学习目标
理解寄存器分配问题的本质：在有限的寄存器资源约束下最小化内存访问开销
掌握活跃变量分析（Live Variable Analysis）在寄存器分配中的核心作用
深入理解图着色（Graph Coloring）算法的原理：从变量活跃性到干涉图（Interference Graph）的构建
掌握 Chaitin-Briggs 图着色寄存器分配算法的完整流程：构建、简化、溢出、选择
理解线性扫描（Linear Scan）寄存器分配算法的原理、优势与局限
掌握溢出（Spill）策略：溢出代价评估、溢出位置选择和溢出代码插入
了解寄存器共指（Coalescing）技术：消除冗余复制指令与干涉图的平衡
理解寄存器分配与其他后端 Pass（指令调度、指令选择）的协同优化
1.2 为什么本章如此重要
寄存器分配是编译器后端中最关键的优化问题之一。CPU 寄存器是计算机中最快的存储单元——访问一个寄存器只需要一个时钟周期，而访问主存可能需要数百个时钟周期。在高性能计算场景中，一次内存访问的延迟可能需要执行数百条指令来弥补。因此，将尽可能多的变量分配到寄存器中，最大限度地减少内存访问（溢出），是提升程序性能的关键手段。
寄存器分配问题的本质是一个资源约束下的优化问题。程序中的变量数量通常远多于可用的寄存器数量——一个中等规模的函数可能有数百个变量，但 x86-64 架构只有 16 个通用寄存器。编译器需要在这些有限的寄存器资源中做出最优的分配决策：哪些变量应该优先分配到寄存器？哪些变量需要溢出到内存？何时溢出、溢出到哪里？这些决策直接影响生成代码的性能。
从理论角度来看，寄存器分配问题（最小化溢出的最优分配）被证明是 NP 完全的，这意味着不存在多项式时间的精确算法（除非 P=NP）。这一理论结果推动了多种近似算法的发展——图着色算法将问题建模为图论中的经典问题，线性扫描算法利用程序顺序性实现高效分配，这些算法在理论和实践之间找到了优雅的平衡点。
从工程实践角度来看，寄存器分配是编译器后端中最后也是最具挑战性的优化环节。它需要与指令选择、指令调度紧密协作——指令选择决定了哪些操作可以使用寄存器-内存形式（影响寄存器压力），指令调度影响变量的活跃区间（影响分配质量）。三者的协同优化是编译器后端工程中最复杂的问题之一。
1.3 核心问题引导
为什么寄存器分配问题被归类为 NP 完全问题？这在实际工程中意味着什么？
活跃变量分析与寄存器分配之间是什么关系？如何从活跃变量信息构建干涉图？
图着色算法如何保证在 K 个寄存器的约束下找到可行的分配方案？当图不可着色时怎么办？
线性扫描算法为什么比图着色算法更快？它在分配质量上做出了什么牺牲？
溢出代价如何评估？选择哪个变量进行溢出才能使性能损失最小？
寄存器共指（Coalescing）为什么可能导致图不可着色？如何平衡共指的收益和风险？
预分配寄存器（Pre-colored Registers）如何处理？函数调用约定对寄存器分配有什么影响？
二、核心概念详解
2.1 活跃变量分析与干涉图构建
寄存器分配的第一步是确定每个变量在程序的哪些位置是"活跃的"（Live）。一个变量在程序某点是活跃的，当且仅当它在该点已经被定值（Assigned），并且在从该点出发的某条执行路径上还会被使用。活跃变量分析是一种经典的数据流分析，通过后向迭代算法求解。
活跃变量的信息直接决定了变量之间的"干涉"（Interference）关系。如果两个变量在程序的某个点上同时活跃，则它们不能分配到同一个寄存器——否则一个变量的写入会覆盖另一个变量的值。这种"不能共享寄存器"的关系称为干涉关系。
干涉图（Interference Graph）是寄存器分配的核心数据结构。干涉图是一个无向图，节点是程序中的变量（或虚拟寄存器），边连接所有存在干涉关系的变量对。寄存器分配问题等价于对干涉图进行 K-着色（K-Coloring）——用 K 种颜色（K 为可用寄存器数量）为图的每个节点着色，使得相邻节点的颜色不同。如果图可以 K-着色，则所有变量都可以分配到寄存器；如果不能，则某些节点需要"溢出"（分配颜色失败），对应的变量需要溢出到内存。
构建干涉图的规则如下：对于每条指令 d: x = y + z，变量 x 在 d 点被定值，y 和 z 在 d 点被使用。x 与所有在 d 点之后（直到 x 下次被定值之前）活跃的变量存在干涉关系。特殊规则：如果 x 在 d 点之后不再活跃（即 x 的最后一次使用在 d 点），则 x 不与 d 点的活跃变量干涉（这称为"死定值"优化）。
2.2 图着色寄存器分配算法
图着色寄存器分配算法由 Gregory Chaitin 于 1982 年提出，是寄存器分配领域最经典的算法。该算法将寄存器分配建模为图着色问题，通过一系列启发式步骤来寻找近似最优的着色方案。
Chaitin 算法的核心思想基于一个图论观察：如果图中存在一个度数小于 K 的节点（K 为颜色数量），则该节点一定可以被着色。因为即使它的所有邻居都使用了不同的颜色，最多占用了 deg(v) < K 种颜色，至少还剩一种颜色可供使用。基于这一观察，简化（Simplify）阶段反复从图中移除度数小于 K 的节点，将它们压入栈中。当图中所有节点的度数都大于等于 K 时，选择一个节点进行溢出（Spill）——将其标记为需要溢出到内存，从图中移除该节点及其所有边，继续简化过程。
选择（Select）阶段从栈中弹出节点，依次为它们分配颜色。对于每个弹出的节点，检查其已着色的邻居使用的颜色，选择一个未被使用的颜色分配给该节点。如果所有 K 种颜色都被邻居使用，则该节点溢出失败。
Briggs 的改进（Chaitin-Briggs 算法）引入了保守共指（Conservative Coalescing）策略，在简化之前尝试合并不干涉的源变量和目标变量（消除复制指令），但只在合并后不会导致不可着色时才执行。这种"保守"策略避免了过度合并导致的溢出增加。
完整的 Chaitin-Briggs 算法流程为：构建干涉图 -> 保守共指 -> 简化（移除低度数节点）-> 如果图不为空则选择溢出节点并重复 -> 选择（弹出节点并着色）-> 插入溢出代码 -> 重新构建干涉图（如果发生了溢出）。这个过程可能需要多次迭代才能收敛。
2.3 线性扫描寄存器分配
线性扫描（Linear Scan）寄存器分配算法由 Poletto 和 Sarkar 于 1999 年提出，是一种比图着色更快但分配质量稍逊的替代方案。该算法不使用干涉图，而是按照程序顺序（或变量的活跃区间起点顺序）线性地处理每个变量。
线性扫描算法的核心数据结构是活跃列表（Active List，按活跃区间终点排序的已分配寄存器的变量集合）和空闲列表（Free List，当前可用的物理寄存器集合）。算法按活跃区间起点递增的顺序处理每个变量：首先，将所有活跃区间终点在当前变量起点之前的变量从活跃列表中移除，释放其寄存器到空闲列表；然后，如果空闲列表非空，分配一个寄存器给当前变量；如果空闲列表为空，选择活跃列表中活跃区间终点最远的变量进行溢出（如果该终点比当前变量的终点更远，则溢出该变量并将寄存器分配给当前变量；否则溢出当前变量）。
线性扫描的时间复杂度为 O(n)，其中 n 是变量数量，远优于图着色算法的 O(n²) 或更高。这使得线性扫描特别适合 JIT 编译器等对编译速度要求极高的场景。Java 的 HotSpot JVM、JavaScript 的 V8 引擎、.NET 的 RyuJIT 都使用线性扫描或其变体。
线性扫描的主要局限在于它不构建全局的干涉图，因此无法捕获变量之间的复杂干涉关系。这可能导致次优的分配决策——两个变量虽然在干涉图上不相邻（可以共享寄存器），但由于活跃区间的重叠方式，线性扫描可能错误地将它们分配到不同的寄存器。扩展的线性扫描算法（如 Linear Scan with Lifetime Holes）通过考虑活跃区间中的"空洞"来改善分配质量。
2.4 溢出策略与代价评估
当寄存器不足时，某些变量需要溢出到内存。溢出策略的设计直接影响生成代码的性能——每次溢出需要在变量定值后插入存储指令（Store），在变量使用前插入加载指令（Load），这些额外的内存访问会显著降低程序性能。
溢出代价（Spill Cost）的评估是决定哪个变量应该溢出的关键。每个变量有一个溢出代价值，表示将该变量溢出到内存的"代价"。代价的常见计算方式包括：基于使用频率——变量在循环中被使用的次数越多，溢出代价越高（因为每次循环迭代都需要额外的加载/存储）；基于执行频率——变量所在的程序块的执行频率越高，溢出代价越高（利用分支概率分析的信息）；基于活跃区间长度——活跃区间越长的变量占用寄存器的时间越长，溢出的收益越大。
溢出位置的选择同样重要。理想的溢出位置是在变量最后一次使用之后立即存储，在变量下一次使用之前立即加载，最小化溢出代码对程序性能的影响。在 SSA 形式下，溢出位置的选择更加精确——每个变量只有一个定值点，加载和存储的位置可以直接从定义-使用链推导。
溢出代码的插入需要更新干涉图——溢出变量不再占用寄存器，因此它与其他变量的干涉关系被移除，可能使得其他原本需要溢出的变量可以分配到寄存器。这就是为什么图着色算法在发生溢出后需要重新构建干涉图并重新执行分配过程。
2.5 寄存器共指与预分配
寄存器共指（Register Coalescing）是消除 SSA 形式中 Phi 函数对应的复制指令的优化技术。在 SSA 解构过程中，每个 Phi 函数需要被替换为复制指令（如 x = y），这些复制指令在运行时消耗执行时间但不产生有用的计算。寄存器共指通过将 x 和 y 分配到同一个寄存器来消除复制指令。
然而，共指可能增加干涉图的着色难度。将 x 和 y 合并为同一个节点后，新节点的邻居是 x 和 y 的邻居的并集，度数增加，可能导致原本可着色的图变为不可着色。保守共指策略只在合并后新节点的度数仍然小于 K 时才执行合并，避免引入额外的溢出。
预分配寄存器（Pre-colored Registers）处理函数调用约定（Calling Convention）的约束。调用约定规定了哪些寄存器用于参数传递（如 x86-64 的 rdi、rsi、rdx、rcx）、哪些寄存器用于返回值（rax）、哪些寄存器是调用者保存的（Caller-saved）、哪些是被调用者保存的（Callee-saved）。这些寄存器已经被"预分配"了特定的角色，在寄存器分配时需要尊重这些约束。
预分配寄存器在干涉图中表现为永远不能被移除或溢出的节点——它们的颜色已经确定。与预分配节点相邻的变量不能使用相同的颜色。处理函数调用时，调用者保存的寄存器在调用点与所有在调用后仍然活跃的变量干涉（因为调用可能覆盖这些寄存器的值），这增加了寄存器压力。
三、深入分析与讨论
3.1 图着色与线性扫描的工程选择
图着色和线性扫描是两种主流的寄存器分配算法，它们在编译时间和分配质量之间形成权衡。
图着色算法通过分析全局的干涉关系来做出更优的分配决策。它能够捕获变量之间的复杂干涉模式，避免线性扫描可能犯下的局部最优错误。在寄存器数量有限的架构（如 x86 的 16 个通用寄存器）上，图着色的分配质量优势更加明显——每减少一次溢出，就可能减少数百个时钟周期的内存访问延迟。GCC 使用图着色算法作为其主要的寄存器分配方法。
然而，图着色的编译时间显著高于线性扫描。干涉图的构建需要 O(n²) 的时间和空间（n 为变量数量），着色过程可能需要多次迭代（每次溢出后重新构建），共指优化进一步增加了算法的复杂度。对于大型函数（数千个变量），图着色的编译时间可能成为瓶颈。
线性扫描以其 O(n) 的时间复杂度和简单的实现成为编译速度敏感场景的首选。JIT 编译器需要在运行时快速编译代码，编译延迟直接影响应用的启动时间和响应速度。线性扫描的编译速度比图着色快 5-10 倍，虽然分配质量稍逊，但在 JIT 场景下，编译速度的收益通常超过分配质量的损失。
现代编译器的趋势是混合使用两种算法——在 AOT（Ahead-of-Time）编译中使用图着色以获得最优的代码质量，在 JIT 编译中使用线性扫描以最小化编译延迟。某些编译器（如 LLVM）还支持可配置的寄存器分配器，允许用户根据需求选择算法。
3.2 寄存器分配与指令调度的协同
寄存器分配和指令调度之间存在复杂的交互关系。指令调度通过重新排列指令顺序来优化流水线效率，但指令的重排会改变变量的活跃区间，从而影响寄存器分配的质量。反过来，寄存器分配的溢出决策会插入额外的加载/存储指令，影响指令调度的效果。
这种交互导致了"先调度后分配"还是"先分配后调度"的经典困境。先调度后分配（Schedule-before-Allocate）允许调度器自由地重排指令，但可能增加活跃区间的长度和寄存器压力，导致更多的溢出。先分配后调度（Allocate-before-Schedule）保证了寄存器分配的质量，但限制了调度器的自由度，可能无法达到最优的流水线效率。
现代编译器采用多种策略来解决这一困境。迭代方法交替执行调度和分配，逐步收敛到较好的解。集成方法将调度和分配统一在一个优化框架中，同时考虑流水线效率和寄存器压力。预调度（Pre-scheduling）在寄存器分配之前进行轻量级的调度，只重排不会显著影响寄存器压力的指令。
四、实践案例
4.1 图着色算法的完整执行示例
以一个简单的代码段为例，展示图着色寄存器分配的完整流程。代码包含 5 个变量 a、b、c、d、e，可用寄存器数量 K=3。
通过活跃变量分析，构建干涉图：a 与 b、c 干涉；b 与 a、c、d 干涉；c 与 a、b、d、e 干涉；d 与 b、c、e 干涉；e 与 c、d 干涉。
简化阶段：检查各节点度数。a 的度数为 2（<3），移除 a 并压栈；b 的度数为 3（>=3），不移除；c 的度数为 4（>=3），不移除；d 的度数为 3（>=3），不移除；e 的度数为 2（<3），移除 e 并压栈。移除 e 后，d 的度数降为 2（<3），移除 d 并压栈。移除 d 后，c 的度数降为 2（<3），移除 c 并压栈。移除 c 后，b 的度数降为 1（<3），移除 b 并压栈。栈中顺序为：a、e、d、c、b。
选择阶段：弹出 b，无已着色邻居，分配颜色 1（寄存器 R1）。弹出 c，邻居 b 使用颜色 1，分配颜色 2（R2）。弹出 d，邻居 b(1)、c(2)，分配颜色 3（R3）。弹出 e，邻居 c(2)、d(3)，分配颜色 1（R1）。弹出 a，邻居 b(1)、c(2)，分配颜色 3（R3）。所有变量成功分配，无溢出。
4.2 线性扫描算法的执行示例
以相同的变量集合为例，展示线性扫描的执行过程。变量的活跃区间为：a=[1,5]、b=[2,8]、c=[3,10]、d=[6,12]、e=[9,15]。K=3。
按起点排序：a、b、c、d、e。处理 a[1,5]：空闲列表={R1,R2,R3}，分配 R1，活跃列表={a(end=5)}。处理 b[2,8]：无过期变量，分配 R2，活跃列表={a(5),b(8)}。处理 c[3,10]：无过期变量，分配 R3，活跃列表={a(5),b(8),c(10)}。处理 d[6,12]：a(end=5)<6，过期移除 a，释放 R1。空闲列表={R1}，分配 R1 给 d，活跃列表={b(8),c(10),d(12)}。处理 e[9,15]：b(end=8)<9，过期移除 b，释放 R2。空闲列表={R2}，分配 R2 给 e，活跃列表={c(10),d(12),e(15)}。
所有变量成功分配到寄存器，无溢出。分配结果：a=R1, b=R2, c=R3, d=R1, e=R2。注意 a 和 d 共享 R1（它们的活跃区间不重叠），b 和 e 共享 R2。
五、常见误区与注意事项
5.1 误区一：寄存器越多越好
虽然更多的寄存器可以减少溢出，但寄存器数量并非越多越好。过多的寄存器增加了上下文切换的开销（函数调用时需要保存/恢复更多寄存器），增加了硬件实现的复杂度和芯片面积，还可能降低处理器的时钟频率。x86-64 从 x86-32 的 8 个寄存器扩展到 16 个，是在寄存器压力和硬件复杂度之间权衡的结果。
5.2 误区二：图着色一定比线性扫描好
虽然图着色在分配质量上通常优于线性扫描，但差距并不总是很大。在某些情况下（如变量活跃区间较短且重叠较少），两者的分配质量几乎相同。考虑到图着色的编译时间远高于线性扫描，在编译速度敏感的场景下，线性扫描可能是更好的选择。
5.3 误区三：溢出越少越好
溢出次数并非衡量寄存器分配质量的唯一标准。溢出的位置同样重要——在循环外溢出一次比在循环内溢出十次的影响小得多。此外，溢出变量的选择也很关键——溢出使用频率低的变量比溢出使用频率高的变量对性能的影响更小。因此，溢出代价的加权总和（而非简单计数）是更好的质量指标。
5.4 注意事项：SSA 形式对寄存器分配的简化
在 SSA 形式下进行寄存器分配具有显著优势。每个变量只有一个定值点，活跃区间的计算更加精确，干涉图的构建更加简单。Phi 函数的处理可以通过寄存器共指来优化，减少不必要的复制指令。许多现代编译器（如 LLVM、Swift 的编译器）选择在 SSA 形式上进行寄存器分配，然后在分配完成后解构 SSA。
5.5 注意事项：寄存器分配的验证
寄存器分配的正确性至关重要——一个错误的分配可能导致变量的值被意外覆盖，产生难以调试的错误。编译器应当在寄存器分配后验证分配的正确性：检查每个变量的活跃区间内是否始终分配到同一个寄存器，检查是否存在两个干涉变量共享同一寄存器的情况。LLVM 提供了寄存器分配验证 Pass，可以在开发过程中捕获这类错误。
六、本章小结
本章系统讲解了寄存器分配的理论与实践。寄存器分配的本质是在有限的寄存器资源约束下，最小化内存访问带来的性能损失。活跃变量分析为寄存器分配提供了基础数据，干涉图将变量之间的冲突关系建模为图结构。图着色算法通过简化和选择两个阶段寻找近似最优的着色方案，分配质量较高但编译时间较长。线性扫描算法按程序顺序线性处理变量，编译速度快但分配质量稍逊。溢出策略通过代价评估选择最优的溢出候选，寄存器共指消除冗余复制指令但需要保守处理以避免增加溢出。寄存器分配与指令调度的协同优化是后端工程的核心挑战。选择合适的寄存器分配算法，需要在编译时间、代码质量和目标架构特性之间做出综合权衡。
七、思考题与练习
对给定的代码段进行活跃变量分析，构建干涉图，并使用图着色算法（K=4）完成寄存器分配。
使用线性扫描算法对相同的代码段进行寄存器分配，比较两种算法的分配结果和溢出次数。
实现一个溢出代价计算模块，考虑变量的使用频率、所在块的执行频率和活跃区间长度。
分析寄存器共指对干涉图的影响，解释为什么保守共指策略只在合并后度数小于 K 时才执行合并。
调研 LLVM 的寄存器分配器实现（PBQP、Fast、Basic、Greedy），比较它们的设计理念和适用场景。
分析函数调用约定对寄存器分配的影响：调用者保存寄存器和被调用者保存寄存器在分配策略上有什么区别？
设计一个迭代式的寄存器分配与指令调度协同优化方案，分析其收敛性和性能效果。
证明：寄存器分配问题（最小化溢出的最优 K-着色）是 NP 完全问题。提示：可以从图 K-着色问题的 NP 完全性出发进行归约。