[科普中国]-寄存器分配

简介寄存器分配原因

寄存器分配是编译器中一个历久弥新的问题，因为它是编译器在输出汇编代码前必须经历的阶段。寄存器分配算法的好坏，关系着生成代码的性能，大小。为了追求极致性能，很多编译器都在寄存器分配上做了很多文章，不惜引入非常复杂的算法。另一方面寄存器分配算法本身的性能也很关键， 在诸多的JIT编译器(Just-In-Time compiler)中，编译器的性能同时也是程序本身的性能，因此在JIT编译器中还需要关注寄存器分配算法本身的效率问题。另外，寄存器分配作为将无限多的逻辑单元映射到有限多的物理单元的典型问题，深入了解它也有助于对其他相关问题的理解，如操作系统中的页着色问题(Page Coloring)。

实际编译器中的寄存器分配问题在实际编译器中，为了尽可能的榨取性能，提升编译器的分配效率，寄存器分配算法都很复杂。万变不离其宗。不管是GCC，Open64还是LLVM，寄存器分配基本都是在靠近汇编代码输出阶段。Open64中在寄存器分配之后，几乎没有什么优化了。GCC中，在寄存器分配之后，还存在大约7个PASS(基本块重排序、收集用于调试的变量保存位置相关信息、延迟槽调度、长跳转转换、针对86387浮点寄存器的寄存器到栈变换、汇编代码输出、调试信息输出)，也没有优化了。LLVM不清楚，欢迎有了解的朋友补充。

这三个工业界级别的编译器中，到了寄存器分配阶段都已经从语法树形式的中间表示转换成了三地址形式的中间表示。 在GCC中，已经从GIMPLE转换成了RTL；在Open64中，已经从WHIRL转换成了CGIR；在LLVM中，已经从Clang阶段的AST(Abstract Syntax Tree,抽象语法树)转换成了LLVM IR。 在转换成三地址码之前，操作之间的操作数、结果的依赖关系都可以通过树形结构表达，展开成三地址形式之后，就需要大量创建临时变量来表达这种依赖关系。此时所有的变量(包括临时变量和原程序中的变量)，都会被分配伪寄存器(Pseudo Register伪寄存器和物理寄存器除了数量有区别：无限多个/有限多个外，其他都相同)。

寄存器分配即将这些伪寄存器映射到实际的物理寄存器上 ， 因此在寄存器分配之前，要保证指令序列基本不再变化。所以实际编译器中的寄存器分配阶段，基本都在最后阶段，此时都基本完成了几乎所有的底层次优化，如三地址形式的循环优化、指令调度、冗余代码删除、其他窥孔优化等等。但也有例外，比如寄存器分配时，需要额外增加一些访存指令，因此在寄存器分配结束后，可能还需要一些调整1。

寄存器分配原则寄存器分配的原则是：
1、当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中，直到寄存器不够分配时为止。
2、当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一个变量名在不同前驱结点的基本块内出口前存放的寄存器可能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中。
3、对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用效率。2

寄存器分配相关算法图着色算法图着色(graph coloring)方法是解决寄存器分配问题最常用的方法。
利用相交图（interference graph）来表示程序变量的生命期是否相交，将寄存器分配给变量的问题，可以近似地看成是给相交图着色：相交图中，相交的节点不能着同一颜色；每一种颜色对应一个寄存器。Chaitin等人最早提出了基于图着色的寄存器分配方法其着色思路采用了Kempe的着色方法，即任意一个邻居节点数目少于k的节点，都能够被k着色。判断一个图是否能够被k(k>=3)种颜色着色，即k着色问题，被Karp证明是一个NP-complete问题。
但是，寄存器分配不仅仅是图着色的问题。当寄存器数目不足以分配某些变量时，就必须将这些变量溢出到内存中，该过程成为spill。最小化溢出代价的问题，也是一个NP-complete问题。如果简化该问题——假设所有溢出代价相等，那么最小化溢出代价的问题，等价于k着色问题，仍然是NP-complete问题。
此外，如果两个变量的生命期仅仅因为出现在同一个拷贝指令中而相邻，那么，通过将这两个变量分配到同一个寄存器，就可以消除该拷贝指令，成为coalescing。这个方向的努力在Chaitin的文章以后的1/4个世纪，成为推动寄存器分配的主要动力之一，涌现出了包括aggressive coalescing,conservative coalescing和optimistic coalescing。但是，将两个变量分配到同一个寄存器，等价于将这两个变量合并成同一个变量，生命期合并，因而会加剧相交图的聚簇现象，降低相交图的可着色性。Bouchez等人证明了目前的coalescing问题都是NP-complete的。

为了降低相交图的聚簇现象，提高相交图的可着色性，可以通过将变量拷贝给一个临时变量，并将以后对该变量的使用替换成对该临时变量的使用，从而将一个变量的生命期分解成两个变量的生命期，称为live range splitting。显然，这是一个与coalescing的作用相反的过程。Bouchez等人考虑了该方法的复杂度。
此外，寄存器分配还需要考虑寄存器别名(aliasing)和预着色(pre-coloring)的问题。寄存器别名是指，在某些体系结构中，一个寄存器的赋值可能会影响到另外一个寄存器。比如，在x86中，对AX寄存器的赋值，会影响AL和AH寄存器。预着色是指，某些变量必须被分配到特定的寄存器。比如，许多体系结构会采用特定寄存器来传递函数参数。
George和Appel发展了Chaitin的算法，更好地考虑了coalescing过程和赋值过程，以及各过程之间的迭代，在基于图着色的寄存器分配方法中具有广泛的影响。2

线性扫描算法线性扫描算法是寄存器分配最快的算法。

线性扫描算法(linear scan)最早由Poletto和Sarkar提出，具有很大的影响力，在gcc、llvm和Java HotSpot编译器中得到了实现。线性扫描算法简化了基于图着色的分配问题，考虑的是对一个有序的生命期序列的着色，提高了寄存器分配的速度（线性速度），而没有过度降低对寄存器的利用。

整数线性规划算法Goodwin和Wilken提出了最早的对寄存器分配问题的整数线性规划算法(integer linear programming),虽然在最坏情况下具有指数级复杂度，但是能够更充分的利用寄存器。

PBQP算法在编译器领域，Partitioned Boolean Quadratic Problem被用于解决指令选择和寄存器分配问题。对于寄存器分配而言，PBQP算法的复杂度为VK^3，其中V是变量的数目，K是寄存器的数目。Hames等人的实验表明，他们的PBQP实现能够为SPEC CPU 2000中的97.4%的函数找到最优寄存器分配方案。

Multi-Flow Commodities算法Koes和Goldstein等人最先将寄存器分配视为Multi-Flow Commodities问题加以解决。

基于SSA的寄存器分配SSA是Static Single Assignment的简写。寄存器分配问题的一个重要突破发生在2005年，当时3个研究团队独立的证明了，采用SSA表示的程序的相交图是弦图（chordal graph）。而弦图是能够在多项式时间内着色的。基于SSA形式的寄存器分配方法，可以从三个方面获益：更小的寄存器压力；spilling和寄存器赋值过程之间的分离；更简单的寄存器赋值算法。2