2025-10-23
自 2004 年以来，线性扫描一直是 LLVM 中的默认寄存器分配器。对于如此简单的算法来说，它的表现好得出奇。直到 2011 年的 LLVM 3.0 ，它才被贪心寄存器分配算法所取代。实际上，简单的设计使得算法的调整很容易，便于对生成的代码进行小的改进。更先进的寄存器分配算法通常需要构建昂贵的数据结构，或者它们假设活跃区间是不可变的。这使得在分配过程中某些动态改变机器代码的操作变得困难，例如即时交换双地址指令，或者重计算常量加载而不是将其溢出到堆栈。
线性扫描算法在分配完成后，需要通过一个重写器来把虚拟寄存器改写成物理寄存器。一般来说，这是足够简单的，但是如果要加入一些优化的话，会比较吃力。在做近引用复用优化（当两次 load/store 比较接近时可以直接复用寄存器，省去重新加载的过程）的时候，它只能处理基本块内的局部重加载，而超出基本块区间的则爱莫能助，即使优化实际上可行。重写器总是通过移除明显的错误来挽救局面。然而，这是用高昂的代价换来的。它约占线性扫描编译时间的一半，并且其大量的复杂技巧使得代码非常难以维护。
顾名思义，线性扫描通过按线性顺序遍历活跃区间来工作。它维护一个在当前函数位置处于活跃状态的活跃区间列表，这就是它在不计算完整冲突图的情况下检测冲突关系的方式。活跃区间列表是线性扫描速度的关键，但也是其最大的弱点。当所有物理寄存器都被活跃区间列表中的冲突活跃区间占用时，会将一个活跃区间溢出到栈。未经分割就直接溢出活跃区间会导致重写器需要花更大的功夫做清理工作，而如果能够把大的区间分割成更小的、可能可分配的片段，事情会好很多。但这就样需要线性扫描算法进行回溯了。而其代价非常昂贵，完整的活跃区间分割在线性扫描中实际上是不可行的。
新的基础分配器抛弃了线性扫描算法对按线性顺序遍历活跃区间的依赖。相反，它使用优先级队列按溢出代价降序遍历活跃区间。用于冲突检查的活跃列表被一组活跃区间并（Live Interval Union）所取代。这些区间并为每个物理寄存器构建一个 B+ 树来检查活跃区间的冲突。与活跃列表不同，活跃区间并适用于任何遍历顺序。
当一个活跃区间无法被分配到对应寄存器类中的物理寄存器时，它将被溢出到栈上。因为活跃区间是按溢出代价降序排序的，所以活跃区间并中所有与之冲突的活跃区间都具有比它更高的溢出代价，更不应该被溢出，因此无需寻找更好的溢出候选。
在 CISC 架构上，栈槽内存访问通常可以折叠到现有指令中。而在 RISC 架构上，必须显式插入加载和存储指令，这就会导致在溢出代码和使用被溢出活跃区间的原始指令之间再创造出新的小活跃区间。这些新的活跃区间也会被放回优先级队列，并具有无限的溢出代价，以防止无限溢出。
技术上说，这些具有高溢出代价的小活跃区间其实应该首先被分配，但基础分配器从不回溯。因此，可能会发生这样的情况：这样的活跃区间可能与具有较小溢出代价的已分配活跃区间相冲突。这种情况下，分配器会选择一个物理寄存器，并溢出原先分配给该寄存器的冲突活跃区间。
基础分配器生成的代码与线性扫描的输出非常相似，并且它也用虚拟寄存器重写器来清理代码。它没有提供比线性扫描显著的优势，其主要目的是用于测试优先队列和活跃区间并的框架。这一算法非常简单，可供调整的空间还很大。贪心算法正是它的一个改进。
关于基本算法，首先要注意的是其优先队列顺序并不能给出最佳的寄存器着色。溢出代价是按照使用密度来计算的，是除掉区间长度的。更小的活跃区间往往具有更高的溢出代价。这意味着所有微小的活跃区间会被首先分配。它们占满了寄存器类中的前几个寄存器，而更大的活跃区间则不得不争夺剩下的寄存器。它们中的大多数最终会被溢出。
贪心算法通过首先分配大的活跃区间来避免这个问题。这使得大的活跃区间可以使用寄存器类中的大部分寄存器，而小的活跃区间通常可以塞入其空隙之中。但是这样就会导致一个问题：有些函数有太多大活跃区间，因此没有足够的寄存器容纳所有小的活跃区间，就会把它们溢出。因此，可以从活跃区间并中驱逐已分配的、具有较低溢出代价的活跃区间，取消其分配，并将其放回优先队列。它们获得第二次被分配到别处的机会，或者进入到活跃区间分割阶段。
当一个活跃区间找不到可以驱逐的冲突活跃区间时，它不会立即被溢出。如果可能的话，它会被分割成更小的片段，并放回优先队列。这是一个非常重要的优化。一个大的活跃区间可能在很多时候是空闲的，但是只在一个热循环中被密集使用。通过拆分出一个覆盖热循环的单独活跃区间，它很有可能会被分配到寄存器上。剩下的活跃区间可能会在循环外部被溢出，反正它在循环外也是空闲的。只有当分割器认为没有必要分割它使，一个活跃区间才会被溢出。这通常发生在热点区域都被分割出来，并且剩下的区间中只包含少量与热点寄存器之间的复制之后。
活跃区间分割和驱逐之间的相互作用创造了一个逐步优化的过程。随着活跃区间在热点区域周围被分割，它们获得更高的溢出代价，也就可以驱逐在此区域中比较冷门的旧活跃区间，从而给它分配寄存器了。而被驱逐的区间又会被分割，依此类推。
这种渐进的分割过程通常在活跃区间变得非常小之前终止，最终结果会是一组覆盖多条指令、甚至多个基本块的活跃区间。这就意味着重写器不需要做太多清理善后工作了。事实上，贪心算法使用了一个完全简单的重写器，只有 85 行代码，而旧的重写器有 2600 行。
贪心算法生成的代码几乎总是比线性扫描更好。通常这是因为活跃区间分割能够消除循环中的溢出代码。同时，贪心算法还允许更进一步的优化。它可以灵活地在分配算法运行过程中动态修改生成的机器代码和活跃区间。
这种灵活性允许对寄存器分配器进行许多调整：
寄存器偏好。 函数参数遵守 ABI 约束在特定的物理寄存器中传递。LLVM 通过在函数调用前后在物理和虚拟寄存器之间进行拷贝来表示这一点。寄存器分配时将这些虚拟寄存器分配给同一个物理寄存器就可以消除这些复制。线性扫描从来就不太擅长这方面——首选的物理寄存器通常已被先前的分配占用。而贪心算法在这种情况发生时，可以直接驱逐先前的分配。
小编码偏好。 在像 ARM Thumb2 和 x86-64 这样的架构上，某些寄存器需要更长的指令编码。贪心算法在分配一个昂贵的寄存器之前，会优先先从更廉价的寄存器中驱逐不太重要的活跃范围。这意味着可以减少较大的指令编码的使用，让整体代码体积更小。
死代码消除。 像重计算这样的优化可以有效缩短活跃区间，甚至完全消除它们。贪心算法会精确地重计算活跃区间，并递归地消除死代码。
寄存器类膨胀。 活跃区间分割创建了被更少指令使用的虚拟寄存器。这有时会解除寄存器类约束，从而虚拟寄存器可以被分配到更大的寄存器类。根据架构的不同，这有时可以使新活跃区间可选用的寄存器数量翻倍。
贪心寄存器分配器仍有很大的改进空间。这正是用其替代线性扫描的意义所在。
Greedy Register Allocation in LLVM 3.0 by Jakob Stoklund Olesen