背景介绍
本文档是基于LLVM 的寄存器分配系列科研笔记第一篇，以一个C语言程序为主干介绍LLVM在寄存器分配前做的一些主要工作，分析在寄存器分配前期可能的写操作来源，并记录了我在研究LLVM 后端中 SSA 形式的中间表示时的一些想法。
进入寄存器分配
我们以下述 C 语言源码为例开始本文的说明：
int foo(int a, int b, int e) { |
在经过 mem2reg pass后，最初Clang默认生成的Alloca/Load/Store形式的IR被转化成了完全SSA形式的IR。这时，源变量在 SSA IR中已经有了许多重命名，如下述代码所示，%add、%mul2、%mul3都是源程序变量（以下简称源变量）b 的重命名：
define i32 @foo(i32 %a, i32 %b, i32 %e) #0 { |
这个结果是很直观的，SSA IR中的每一条指令都与源程序中每一条语句一一对应。在此 SSA IR里，所有重命名都是虚拟寄存器，这些重命名在后面的 MIR 中是以 <%vreg + idx> (%vreg0、%vreg1…) 的虚拟寄存器形式表示的。但是，并不是 SSA IR中所有的重命名都会在 MIR 中生成相应的<%vreg + idx>。我们可以分析刚刚进入寄存器分配时此程序的 MIR，通过给 llc 添加-print-after=livevars 选项（给 llc 加上 -help-hidden 选项可以查看-print-after 支持的所有 pass 名称）可以观察做了活变量分析后的MIR，此阶段的 MIR 尚未做 PHI 指令消除和二地址转换：
Frame Objects: |
显然，我们注意到在该 MIR 中，最后两条 IMUL32rr 语句和源程序的 mul运算的操作数并不一致。这是后端在代码生成过程中做的特殊处理（即优化，vreg4可能就在这个过程中被优化掉了？），最终返回的结果是没有问题的。从这两句代码可以看出，MIR里的某些虚拟寄存器可能并不对应任何一个源变量，它是用于存放中间变量的。还有，MIR里的某些虚拟寄存器可能与 SSA IR中的重命名（虚拟寄存器）也不对应，如倒数第二条 IMUL32rr 指令中的%vreg6 在 SSA IR 中就找不到对应的重命名。
基于这种观察，我们知道在寄存器分配阶段要以虚拟寄存器为单位进行思考，而不再把思维局限在源程序中，不再按照分析源程序的思维来分析寄存器分配中的问题。虽然MIR 与 SSA IR 中的虚拟寄存器并不对应，但 MIR 与 SSA IR有个共同点，就是他们都是 SSA 形式的，每个虚拟寄存器仅仅进行了一次赋值。
注释：关于活跃分析，LLVM里的活跃分析与我们平时在教材里看到的不完全一样。在大多数编译原理教材里，活跃分析的内容是直接以源程序中的变量为基础进行分析的。但是在LLVM 里却不是这样，LLVM 里的活跃分析是后端的工作，换句话说，是基于 LLVM IR 做的。因此，LLVM收集到的活跃信息来源于所有的虚拟寄存器和少部分物理寄存器，后面的 LiveInterval 的计算便依赖于此活跃信息。由于 LLVM IR 采用的 SSA 形式，所有虚拟寄存器都是单一赋值，从而导致 LLVM里的活跃分析简单而高效。
寄存器分配的准备工作
下面开始讨论活跃分析后的流程，最关键的两个 pass 就是 PHI指令消除（PHIElimination pass）和二地址转换（TwoAddressInstructionPass pass），这两个 pass 引入了大量 COPY 指令。当然，在执行这两个 pass之前，编译器还要收集一些静态信息，比如支配结点树（MachineDominatorTree）和循环信息（MachineLoopInfo）等。
PHI 消除
SSA 解构阶段是做寄存器分配时的一个重要转换过程。虽然 SSA形式简化了作用在程序控制流图上的许多分析，但一般的指令集并没有包含 PHI指令的实现。因此，为了得到可执行的代码，编译器必须在不改变语义的前提下用其他指令来取代PHI 指令。
考虑如下场景：有三个基本块 B0, B1, B2，其中，B1、B2 是 B0 的前驱，即B1->B0，B2->B0。如果 B1、B2 中都有对同一变量 x 的定义 x1、x2，那么B0 中就需要插入 PHI 函数来决定选取哪个定义：x3 = PHI(x1, x2)。
B1: B2: |
由于目前的硬件平台都没有支持 PHI函数的指令，因此这个工作要交给编译器来做。在 LLVM中，是通过插入复制指令（COPY Instruction）来消除 PHI函数的，这一过程又叫做 Lower PHI。我们对上面场景中的 PHI 进行 lower可以得到下面这样的基本块：
B1: B2: |
二地址转换
除了很少一部分指令外（如函数调用），LLVM机器码指令都是三地址指令。也就是说，每条指令最多只能定义一个寄存器，并且最多使用两个寄存器。然而，很多架构普遍使用了双地址指令。在这种情况下，发生定义的寄存器同时也是被使用的寄存器之一。举个例子，X86中类似“ADD %EAX, %EBX”的指令实际上等同于“%EAX = %EAX + %EBX”。
为了正确生成代码，LLVM 必须把 LLVM中间表示中的三地址指令转化为真正的双地址指令。为此，LLVM 提供了TwoAddressInstructionPass pass，该 pass必须在做寄存器分配之前运行。在它运行完毕后，产出的代码就不再是 SSA形式了。以下述场景为例，三地址指令“%a = ADD %b%c”被转化为下面的两条指令：
%a = MOVE %b
%a = ADD %a %c上述代码块的第二条指令被表示为“ADD %a[def/use] %c”这样的形式，指令既使用了寄存器操作数 %a，又定义了它。本文的例子中的COPY 指令便是在二地址转换的过程中引入的，可以给 llc 加上-debug-only=twoaddrinstr 选项来观察该过程。
注释：对于X86等采用二地址指令的架构才需要执行本步骤，对于MIPS等采用三地址指令的架构则不需要本步骤。
回归例子
上述过程做完后，编译器就可以在此时的 MIR 基础上计算 LiveInterval了。我们来观察做了 PHI 消除和二地址转换过程后的 MIR，这也是打开-debug-only=regalloc 选项后最先输出的 MIR，如下：
Frame Objects: |
把上述 MIR 中各虚拟寄存器的 LiveInterval 打印出来：
%vreg0 [16r,80r:0) 0@16r |
这里，每一行代表一个LiveInterval，也就是一个虚拟寄存器。显然，由于虚拟寄存器与源变量没有关联，LiveInterval与源变量也没有关联。现在，我们从“虚拟寄存器/LiveInterval”的角度来考虑问题，而不是从源程序的角度来考虑问题。在上面的LiveInlterval 列表中，最右侧的信息给出的是该虚拟寄存器的定义点（def point），而不是源变量的定义点（def point）。
要注意的是，在寄存器分配初始阶段，每个寄存器的定义点除了 COPY赋值之外仅仅包含了一次赋值。这个不难理解，因为在 PHI 消除之前的 MIR 就是SSA 形式的，每个虚拟寄存器最多只包含一次赋值。而 PHI消除和二地址转换过程又各自引入了 COPY指令，添加了几次赋值。由于本例不存在 PHI指令，故上述赋值中只有二地址转换的过程会引入一次赋值操作，因此各个虚拟寄存器最多经历了两次赋值。
合并
从上面的 MIR 中，我们可以发现在源代码如此简短的情况下仍然生成了大量的COPY，从而引入了大量的虚拟寄存器，这对后续的物理寄存器分配带来了很大的压力。由于COPY指令的特殊性（它连接的两个虚拟寄存器的值相同），我们可以在一些特殊情况下合并LiveInterval 的生命期（liverange），这个过程叫做合并（coalesce）。以上面的 %vreg0 和 %vreg2 为例：
%vreg0 [16r,80r:0) 0@16r |
可以发现，这两个虚拟寄存器的生命期互不重叠，恰好错开了，同时它们生命期的交界处是COPY指令。显然，这样的两个寄存器生命期是可以进行合并的，这样可以把交界处的COPY指令消除掉。在所有合并工作完成后，源程序中的LiveInterval 为：
%vreg2 [16r,96r:0)[96r,192r:1) 0@16r 1@96r |
最终的寄存器分配是在这种做了合并后的 LiveInterval上做的，这个时候的虚拟寄存器经过了一系列 pass的处理，和源变量可以说是天壤之别了，基本没有什么联系。在虚拟寄存器发生spill时，栈槽上经受的操作是该虚拟寄存器本身会经受的操作，并不唯一对应哪个源变量。或者说，各个源变量都有可能在栈槽上发生写操作。
要注意的是，在消除了 COPY 指令之后，MIR 的 SSA结构已经被彻底破坏掉了（其实引入 COPY 时就已经不是 SSA了，但是不是很明显）。因此，最终做寄存器分配时的虚拟寄存器并非 SSA形式，可能会承担多次写操作。以这个例子为例，其最终进行寄存器分配的MIR如下：
Frame Objects: |
不难发现，此 MIR 中 %vreg2 和 %vreg3 都经受了多次写操作。最终做分配的LiveIntervals 求出来之后，LLVM 会执行一些pass，用于给接下来的寄存器分配做一些准备工作，例如执行MachineBlockFrequencyInfo pass 用于获取各个基本块频率、执行 VirtRegMap pass 用于设置一些虚拟寄存器的映射关系（Virt2PhysMap、Virt2StackSlotMap等），接下来就可以执行寄存器分配的 pass 了。
4 题外话
我在查阅 LLVM 寄存器分配的官方文档时看到了这样一段话：
Live Intervals are the ranges (intervals) where a variable is live.
They are used by some register allocator passes to determine if two or
more virtual registers which require the same physical register are
live at the same point in the program (i.e., they conflict). When this
situation occurs, one virtual register must be spilled.
我最开始以为虚拟寄存器和物理寄存器是一对一的关系，即在一个虚拟寄存器的live interval 范围内（包括 hole在内），相应的物理寄存器只能被它占有。但是看这段话的意思，虚拟寄存器和物理寄存器是存在多对一的关系的，即多个虚拟寄存器可以分配给同一个物理寄存器，只要他们的live interval不相交。这个映射关系，我尚未能在代码中发现，还需要继续研究。
根据资料 Register Allocation，设置这种多对一关系的原因是为了进一步压榨寄存器的性能。例如，假设有一变量x 的生命期为 [16, 80)[196, 208)，称区间 [16, 208) 为 live range，区间[16, 80) 和 [196, 208) 为 segment，区间 [80, 196) 为hole。按照我最开始理解的虚拟寄存器与物理寄存器的一一对应关系，在整个live range 内物理寄存器都被 x 霸占了。因为 hole 的存在，这就导致了 hole期间物理寄存器不能被充分使用。其实 hole期间物理寄存器是可以被其他变量使用的，只要它的生命期与 x 不相交，如变量y: [80, 196)。