这篇博客里面，我们来讨论编译器构造里面的一个重要的话题，寄存器分配。
寄存器分配
它描述的是这样的一个问题：在我们把前端语法转换成低级的机器序列后，操作数（operand）此时还没有物理实体，而是虚拟的，例如下面的简单代码：
fn demo() -> Int {
return 1 + 2 * 3
}
这样的代码在经过语法解析，IR转换，优化之后，紧接着会转换成机器指令，它在刚刚从高级IR转换成低级IR的时候，可能会是下面这种形态：
demo:
v0 = imove 1
v1 = imove 2
v2 = imove 3
v3 = imul v1, v2
v4 = iadd v0, v3
ret v4
假设我们现在有若干可选的物理寄存器，我们需要确定，这里的v0，v1, v2, v3, v4都被分配给谁，如果有一些虚拟寄存器无法被分配物理寄存器，那么我们就需要做溢出，将原有的指令序列进行变动，将一些值放到栈上去。
对于我们的例子而言，假设我们有三个寄存器r0, r1, r2，此时可以正好分配完全，只要做如下的分配策略即可：
v0 -> r0
v1 -> r1
v2 -> r2
v3 -> r1
v4 -> r0
但是，如果我们只有两个寄存器r0, r1，这个时候物理寄存器就不太够用了，此时需要决定溢出，原本保存在寄存器里的值，把它变换到栈上去，需要把指令序列变换一下，例如变换成下面的样子：
demo:
v0 = imove 1
storei sp, v0
v1 = imove 2
v2 = imove 3
v4 = imul v1, v2
v5 = iload sp
v6 = iadd v5, v4
ret v6
我们会多了一次store和load指令。这一次我们会发现，尽管代码中出现的虚拟寄存器多了，但是此时是可以被分配的了，我们的分配策略如下：
v0 -> r0
v1 -> r0
v2 -> r1
v4 -> r0
v5 -> r1
v6 -> r0
所谓寄存器分配问题，就是问这样一个问题，对于任意一个包含虚拟寄存器的指令序列，如何进行物理寄存器上的分配，把哪个寄存器分配到哪个物理寄存器上，选择哪个虚拟寄存器进行溢出，能够使得我们的程序运行效率更快？
寄存器分配问题是一个NP-Hard问题
需要注意的是，寄存器分配问题是一个np-hard问题，它不存在在多项式时间内可以找到的最优解，所以现有的在各种编译器里面所实现的寄存器分配算法，基本上都不是最优算法，这是工程权衡。使用brute force或者回溯图着色这样的算法虽然可以找到最优解，但是它的复杂度一般都在指数级，大约在O(2^n)左右，其中n可以看做是虚拟寄存器的数量，但是在软件工程下，一个函数内的指令数可能非常多，造成的虚拟寄存器的数量也非常多，数百个虚拟寄存器是常有的时，如果采用最优算法，编译速度无法保证，因此现存的在各种编译器内部实现的寄存器分配pass，基本上都是采用启发式算法，通常来看，主要是两种基础算法的变体：图着色，以及线性扫描。
从实践上来看，图着色一般可以生成质量较高的代码，但是运行速度比较慢，可能需要反复递归。线性扫描算法的运行效率比较高，但是生成代码的质量一般。
在一些追求编译速度的情景下，譬如说一些JIT场景，通常会采用线性扫描算法及其变体。在一些追求运行效率的情景下，例如AOT，或者高度优化的编译器（例如gcc），通常使用图着色算法及其变体。
稍微提一点的是，LLVM虽然也是高度优化的代码，但是却并没有采用图着色算法，高度优化的代码其实是PBQP，某种程度上来说，可以把它看成是一种线性扫描算法的变体，只是这种变体与最开始的线性扫描思路已经有很大不同了。
本博客会逐渐介绍多种寄存器分配算法，不过就这一篇而言，这一篇博客探讨的是线性扫描算法。但是需要注意的是，真实在工程中使用的线性扫描算法，其实比这篇博客里面讲的内容要复杂很多，真实工程中使用的线性扫描算法为了提升生成代码的效果，往往会在遍历的过程中收集更多的信息，然后根据业务场景设置更多的启发式因子。这篇博客只会探讨核心的思路。
线性扫描的基础思想
笼统地说，线性扫描的基础思路是这样，我有一段程序，使用了4个虚拟寄存器，v0, v1, v2, v3。然后我经过分析知道，v0在时刻0到时刻3被使用，v1在时刻1到时刻9被使用，v2在时刻5到时刻8被使用，v3在时刻7到时刻10被使用，那么问，这四个虚拟寄存器怎么分配物理寄存器？
时刻： 0 1 2 3 4 5 6 7 8 9 10
v0: |-----|
v1: |---------------|
v2: |-----|
v3: |------|
先考虑个简单情景，假设的目标机有3个寄存器r0, r1, r2。
我们可以这样想，首先，把v0分配给r0，把v1分配给r1。
对于v2来说，v0此时已经结束，所以不再占有r0寄存器，把v2分配给r0寄存器就好了。
接着对于v3来说，此时r0, r1寄存器都还被占用，幸好还剩下一个寄存器，那么就把v3分配到r2寄存器。完美。
最终的分配策略就是这样：
v0 -> r0
v1 -> r1
v2 -> r0
v3 -> r2
换一种情景，假设目标机只有2个寄存器，r0和r1呢？
这个时候我们一开始还是同样的心态，v0分配到r0, v1分配到r1, v2分配到r0，此时v3不好分配，因为这个时候，r0和r1都被占用了。
那么，最简单的策略出现了，直接溢出v3即可。因为没有寄存器了，所以就溢出呗。
所以，我们得到了下面的分配策略：
v0 -> r0
v1 -> r1
v2 -> r0
v3 -> spill to stack
改进策略:
不过，上面的策略其实不太好，溢出v3其实并不太好。因为我们更倾向于，把短命的值尽可能地直接分配寄存器。长命的值，尽可能分配到栈上去。因为这样一来，在后续遍历其它虚拟寄存器的时候，短命的值会更有可能空出寄存器。也就是说，对于上面的指令流而言，把v1溢出到栈上，实际上是一个比把v3溢出到栈上更好一些的操作。
单块简单形式的线性扫描
前面是一个基础思想的演示，现在我们来思考一个简单的例子，看下面的代码：
physical register: r0, r1
demo:
I0: v0 = imove 1
I1: v1 = imove 2
I2: v2 = iadd v0, v1
I3: ret v2
这个例子当然一眼就可以看出来结果。但我们需要思考整个的流程。首先的第一个问题是，我们怎么定义时刻？
如果你简单地认为I0就是0时刻，I1是1时刻，以此类推，那么你的结论就是v0在时刻0到时刻2上被使用，v1在时刻1到时刻2上被使用，v2在时刻2到时刻3上被使用。那么你会发现，当你分配v0 -> r0，v1 -> r1的时候，v2分配不了。因为这个时候r0和r1在时刻2上还没有结束，但是其实v2可以被分配到r0或者r1。
比较正确的方式是，对于一条指令而言，它存在两个时刻，一个use时刻一个def时刻，use时刻在前，def时刻在后，换句话说，它的时间线是这样：
demo: |use |def
I0: v0 = imove 1 |0 |1
I1: v1 = imove 2 |2 |3
I2: v2 = iadd v0, v1 |4 |5
I3: ret v2 |6 |7
在这个时刻表下，v0真正的使用时刻，实际上是时刻1到时刻4，它在时刻1被定义，在时刻4被使用。v1的使用时刻是时刻3到时刻4，v2的使用时刻是时刻5到时刻6。
时刻： 0 1 2 3 4 5 6 7
v0: |-----|
v1: |-|
v2: |-|
这么一来就清楚了，把r0分配给v0，r1分配给v1，轮到v2的时候，此时r0和r1都空了下来，因此r0和r1都可以分配，这里分配r0好了，那么最终的结果就是：
v0 -> r0
v1 -> r1
v2 -> r0
存在分支块的线性扫描
以上是只考虑单个块的，现在，让我们思考一个稍微复杂点的情况，如果是多个块。先来考虑最简单的情况：
对于简单的语句: cond? (1 + 2) * 3 : 2 * 4 + 5，生成的代码可能是这样：
physical register: r0, r1
demo:
I0: v1 = 1
I1: v2 = 2
I3: br cond, then, else
then:
T0: v3 = v1 + 2
T1: v5 = v3 * 3
T2: jmp merge
else:
E0: v4 = v2 * 4
E2: v5 = v5 + 5
E1: jmp merge
merge:
M0: ret v5
为了简化讨论，这里的cond假设不参与寄存器分配。
这里真正让人头疼的是，时刻似乎出现了并行的，因为指令流进入到了then块它就不可能进入到else块里面去。但是，其实我们其实仍然可以按照线性序来对时刻进行排序，就像下面这样：
entry: | use | def
I0: v1 = 1 | 0 | 1
I1: v2 = 2 | 2 | 3
I3: br cond, then, else | 4 | 5
then:
T0: v3 = v1 + 2 | 6 | 7
T1: v5 = v3 * 3 | 8 | 9
T2: jmp merge | 10 | 11
else:
E0: v4 = v2 * 4 | 12 | 13
E2: v5 = v4 + 5 | 14 | 15
E1: jmp merge | 16 | 17
merge:
M0: ret v5 | 18 | 19
一个粗暴的观点是这样认为的，v1的使用时刻是[1, 6]（时刻1到时刻6，后文以后都用这种记号），v2的使用时刻是[3, 12]等等，所以我们有：
v1: [1, 6]
v2: [3, 12]
v3: [7, 8]
v4: [13, 14]
v5: [9, 18]
这里额外提一下v5的问题，指令流里面v5被定义了两次，但是取最早被定义的时刻为初时刻，所以是9，而不是15。
如果我们这么来定义区间的话，我们很快会发现问题，当我们分配v1->r0, v2->r1，要分配v3的时候，我们就必须spill掉一个虚拟寄存器了。
但问题是，回到原先的指令序列里面，我们会发现其实分配v3->r1是没有问题的，因为走then块的时候，v2其实并不会被使用。
这个问题的根源在于我们时刻安排其实并不合理，then块和else块本来是并行的，但是我们的时刻安排却是串行的。要解决这个问题，我们需要允许一个虚拟寄存器的使用时刻可能会存在hole，或者说，使用时刻是多段时刻的组合。
就这个例子而言，v1的使用时刻应该这么看，它有两段，第一段是entry块里第一次定义的时刻到entry块终止的时刻，也就是[1, 5]，第二段是then块里，v1最后一次被使用的时刻，也就是[6]，换言之，v1的使用时刻，实际上是[1, 5] U [6]。
同理，v2的使用时刻实际上是[3, 5] U [12]，以此类推：
v1: [1, 5] U [6]
v2: [3, 5] U [12]
v3: [7, 8]
v4: [13, 14]
v5: [9, 11] U [15, 17] U [18]
一旦我们把区间这么来定义，我们就很自然地得到寄存器分配：
v1 -> r0
v2 -> r1
v3 -> r0
v4 -> r0
v5 -> r0
带循环的线性扫描
下面再考虑一个情景，思考一个斐波那契数列的例子，下面我们就直接列出时刻。
entry: | use | def
I0: v0 = 0 | 0 | 1
I1: v1 = 1 | 2 | 3
I2: v2 = 1 | 4 | 5
I3: jmp loop | 6 | 7
loop:
L0: cond = v0 < 10 | 8 | 9
L1: br cond, body, exit | 10 | 11
body:
B0: v3 = v2 | 12 | 13
B1: v2 = v1 + v2 | 14 | 15
B2: v1 = v3 | 16 | 17
B3: v0 = v0 + 1 | 18 | 19
B4: jmp loop | 20 | 21
exit:
E0: ret v2 | 22 | 23
如果我们按照先前的思路，我们会得到（cond不参与寄存器分配）：
v0 = [1, 7] U [8] U [18, 19]
v1 = [3, 7] U [14, 17]
v2 = [5, 7] U [14, 15]
v3 = [13, 16]
但是，很快会发现这个结果并不正确，典型的是v1的时刻，[14, 17]是因为第一次使用是14，最后一次定义是17，这显然是有些奇怪的。事实上，v1在body块内，它的起始段应该是body的起始时间，也就是12才比较合理，并且，结束时间，也应该是body的结束时间。
这里的核心区别，就在于循环结构，还影响了虚拟寄存器的活跃信息。body块在进入和出去的时候，v1寄存器都是活跃的，所以v1寄存器在body块内的，使用时刻实际上是整个[12, 19]，而并不是它第一次use和第一次def的时刻[14, 17]。
经过正确处理活跃区间后，我们会得到更合理的区间：
v0: [1, 7] U [8, 19] // 贯穿整个循环
v1: [3, 7] U [12, 19] // 在body内全程活跃
v2: [5, 7] U [12, 21] // 同理
v3: [13, 16] // 短命，只在body内短暂存在
此时再进行线性扫描，分配结果就会清晰很多：v3作为短命的临时值，很容易获得寄存器，而v0、v1、v2这些贯穿循环的长命值，则需要更谨慎地决定是否溢出。
线性扫描的核心算法流程
总结一下，经典线性扫描算法（Linear Scan Register Allocation）的基本步骤如下：
活跃区间分析（Live Interval Analysis） 对整个函数（考虑控制流，包括分支和循环）计算每个虚拟寄存器的活跃区间（Live Interval）。这是整个算法最关键也最复杂的一步，需要精确处理phi节点、循环回边、控制流合并点等情况。
按起始点排序 把所有虚拟寄存器的活跃区间按照起始时间排序。
线性扫描 + 活跃集合维护 维护一个当前活跃的物理寄存器集合（或已分配的虚拟寄存器集合）。 按顺序处理每一个虚拟寄存器：
- 首先把已经过期的（结束时间早于当前虚拟寄存器起始时间）的寄存器释放掉；
- 如果还有空闲物理寄存器，直接分配；
- 如果没有空闲寄存器，则需要选择一个“牺牲者”进行溢出（spill）。常见的启发式是选择当前活跃区间中结束时间最晚的那个（即“最远使用”策略）。
重写代码（Rewrite） 根据最终的分配结果，插入必要的store/load指令，把被溢出的虚拟寄存器存放到栈帧中，并在使用点重新加载。
整个过程只进行一次线性遍历，因此时间复杂度非常优秀，通常接近O(n)，其中n是虚拟寄存器的数量。这也是为什么线性扫描在JIT编译器中大受欢迎的原因。
线性扫描的优缺点与工程实践
线性扫描最大的优点是速度快，实现相对简单，在编译时间敏感的场景（JIT、快速调试构建等）中表现优秀。
但它的缺点也很明显：由于只做了一次线性遍历，缺乏全局视角，所以生成的代码质量通常不如图着色算法，尤其在寄存器压力大的函数中，可能会产生较多的溢出指令。
在实际工程中，现代的线性扫描实现往往会加入大量启发式改进，例如：
- 二次扫描（Second Chance Binning）
- 活跃区间分裂（Live Interval Splitting）
- 基于使用频率的溢出代价评估
- 与窥孔优化、指令调度相结合
这些改进让线性扫描在很多场景下的代码质量已经非常接近图着色，但编译速度仍然保持明显优势。
结语
寄存器分配是编译器后端中最优雅也最残酷的博弈之一：我们要在有限的物理寄存器资源与程序的复杂控制流之间，找到一个尽量好的平衡点。
线性扫描以其简洁直观的思想，成为了理解整个寄存器分配问题的最佳入门算法。它像一条清澈的小溪，虽然不像图着色那样深邃复杂，却以极高的效率流淌在无数现代编译器的血液里。
当你下次看到JIT编译器在毫秒级完成一次函数编译时，很可能背后就有线性扫描（或其变体）在默默工作。
至此，线性扫描算法的核心思想就介绍完了。