图染色法的寄存器分配

图染色法的寄存器分配计算机科学与技术系98级吴汉唐摘要本文讲述了寄存器分配的图染色法理论。

Chaitin 和他的同伴，在IBM 的Yorktown Heights研究中心，实现了第一个基于图染色法的全局的寄存器分配器。

后来，Rice 大学的Preston Briggs 对Chaitin的算法进行了改进和扩展。

Chaitin的算法悲观地假设任何高度数的结点都不能被染色，只能被抛出（spilled）。

Briggs的算法乐观地认为高度数的结点有可能被染色，从而获得更低的抛出开销（spill costs），和更快的代码。

一介绍（一）编译器和优化一个优化编译器分为三个层次：●前端把源语言转换为中间代码。

这个转换依赖于源语言的结构，需要几遍扫描（pass）代码才能完成。

编译时的错误检查就在这一层。

我们可以理想地认为前端是只与语言有关的、与机器无关的。

●优化器包含几遍的扫描（pass），每一遍扫描对中间代码执行特定的转换。

我们感兴趣的是全局优化，就是从整个函数搜集有用信息，再去做优化。

一般的全局优化包括强度削减（strength reduction），循环不变量移动（loop-invariant code motion）和公共子表达式消除（common subexpression elimination）。

优化器最好是与语言和机器都无关的。

●后端把中间代码转换为针对特定机器的目标代码。

这个转换过程又称为代码生成，也需要几遍扫描才能完成。

这几遍扫描包括指令选择（instruction selection）,指令调度（instruction scheduling）,寄存器分配（register allocation）。

后端在很大程度上是与语言无关的，与机器有关的。

这个划分简化了每一个层次的开发和维护，使得在不同的编译器中复用每个层次成为可能。

例如，一个完全与机器无关的FORTRAN语言前端可以用到为不同机器设计的编译器中。

当然，这还是一个理想的观点。

在实际中，每个层次都表现出既与语言相关又与机器相关。

这些相关限制复用和维护，也成为编译器设计人员努力要克服的难关。

（二）优化和寄存器分配寄存器是位于CPU内部的少量的高速存储器。

寄存器与内存有很大的不同：●寄存器很少。

一个寄存器可以用几个比特直接定位。

内存空间很大。

内存的定位一般是通过间接的“寻址方式”，其中可能包含一个或多个对寄存器的引用。

●寄存器很快。

在一个周期内，可以同时读两个寄存器，写第三个寄存器。

内存要慢些，一次访问就需要几个周期。

因为寄存器的个数受限和高速度，它们成为大多数计算机体系结构中的关键资源之一。

寄存器分配器作为后端的一个模块，控制寄存器的分配和使用。

寄存器很重要。

最简单的情况，每条机器指令的操作数要放在寄存器里。

在计算复杂表达式的过程中产生的中间结果也要在寄存器里。

更复杂的编译器会把经常使用的变量放在寄存器里，来避免反复地存取。

如果是一个带优化的编译器，它会把公共子表达式消除或者循环不变量移动以后的重用值，放在寄存器里。

分配寄存器的任务有几个层次●寄存器只在一个表达式的范围内分配。

这是一项为了减少寄存器需求量的指令调度的技术。

●更先进的分配器可以在一个基本块的范围内管理寄存器。

●全局分配器在一个函数的范围内工作。

Chaitin 的分配器就在这样的例子。

●程序间的寄存器分配是对一些函数工作，通常是一个完整的程序。

为了支持全局的优化，全局的寄存器分配是必须的。

（三）寄存器分配和图染色法实现好的寄存器分配总是很困难。

即使是最简单的实现也会因为机器的特殊细节变得复杂。

可靠的分配器必要能很好地对付复杂的程序和稀少的寄存器的情况。

图染色法提供了一种简化的抽象。

它建立一张表示分配过程中的各种限制的冲突图（interference graph），并对它染色，把许多表面上各异的细节纳入统一的模式。

图中的结点代表生命期（live range），边代表生命期之间的冲突关系。

一般说来，如果两个生命期在函数的某一点是同时活跃（live）的，它们就相互冲突，不能占有同一个寄存器。

假设k 就是机器中可供分配的寄存器数目，如果图中的所有结点可以用k 种或者更少的颜色染色，有边相连的一对顶点接受不同的颜色，那么这种图染色方案对应一种寄存器分配方案。

如果找不到一种k－染色方案，只好修改代码重新染色。

1.使寄存器使用率最小寄存器分配的目标是使不得不执行的load 和store指令的数目最小。

把寄存器分配问题化归到图染色问题巧妙地转移了目标：以前是最小化存取内存的开销，变成最小化寄存器使用率。

2.使被抛出代码最少即使有最好的染色算法和大量的寄存器，有时候也不得不把某些值抛到内存里。

这样就产生了几个难题。

首先我们希望插入load 和store 指令的动态开销最小。

我们必须设法选择抛出某些生命期，使得抛出开销低，又能减轻图中寄存器分配的压力。

还有，我们考虑最好在哪里插入load 和store 指令。

所有这些问题都很复杂，而且是互相关联的。

二背景(一)用图染色法来分配寄存器我们假设分配器工作在一种类似汇编代码的低级的中间代码上。

这种代码被优化器处理过，寻址模式和执行顺序是确定的。

当然，这些假设忽略了分配器和编译器其他部件之间可能的协同关联。

为了以后讨论的简化，我们还假设机器是load－store的体系结构。

在分配以前，中间代码可以引用无限数目的寄存器。

我们把这些分配之前的不受限制的寄存器叫做“虚拟寄存器”。

分配的目标就是重写中间代码，使它只使用目标机器提供的寄存器——机器寄存器。

在寄存器分配中我们关心的是赋值（definition）和生命期（live range）。

一个生命期是由共同的使用（use）连接的一个或多个赋值。

所有组成一个生命期的赋值将用同一个虚拟寄存器命名。

在分配之后，任意一个机器寄存器通常对应几个生命期。

为了把寄存器分配转化为图染色的模型，编译器首先构造一个冲突图G。

G 中的结点代表生命期，边代表冲突关系。

这样，在图G中结点i与结点j有一条边相连当且仅当生命期l i 与生命期l j冲突，就是它们在某一点同时是活跃的。

与一个生命期l i冲突的那些生命期被称为l i的邻居。

在图中邻居的数目就是l 的度数，记做l i oi为了找到图G的一种寄存器分配，编译器首先寻找图G的一种k染色方案。

如果机器寄存器的数目是k，我们就找到一种切实可行的寄存器分配方案。

因为为任意一个图找到k染色方案是一个NP结问题，只能采用启发式算法来寻找染色方案，这就不能保证为每个可以k－染色的图找到k－染色方案。

(二)Yorktown 分配器Chaitin和他的同事在IBM的Yorktown Heights研究中心为PL8 编译器实现的分配器，是基于图染色法的全局的寄存器分配器的第一个实现。

下图显示了Yorktown 分配器的流程。

图（1）Renumber 这个阶段找到函数中的所有生命期，并给它们以唯一的编号。

Build 这一步要建立冲突图G。

为了保证效率，G同时有两种表示形式：一个三角矩阵和一个相邻向量表。

Coalesce 在这个阶段分配器删去不要的复制赋值，从代码中去掉对应的复制语句，合并源生命期和目标生命期。

删去一个复制的前提是源和目标互相不冲突。

我们把结点l i和l j 的合并记为l ij。

删去复制指令必然会改变冲突图，我们要重复build和coalesce直到再没有复制赋值。

Spill Costs 在染色之前，对每个生命期l 都要计算它的抛出开销。

l 的抛出开销是对抛出l 后插入的load 和store指令造成的开销的评估。

每条指令的开销用10 d加权，而d是这条指令的循环嵌套深度。

Simplify 这个阶段，还有select ，一起对冲突图染色。

simplify 反复地检查G中的结点，删去所有度数小于k的结点。

当一个结点被删去时，与它关联的边也被删去，然后这个点被压入栈s。

如果遇到G中剩下的每个结点的度数都大于k，就要选择其中一个抛出。

但不会立刻把结点对应的生命期抛出（也就是立刻更新代码和冲突图），只是把那个结点从G中删去，并标记为spilling。

最后G会成为空图。

如果有些结点被标记spilling，它们在spill code 阶段会被抛出，整个分配过程要重新来。

否则，栈s被传递到select阶段。

Select按照在simplify阶段确定的顺序，把颜色分配给每一个结点。

按顺序，每个结点从栈s中弹出来，重新插入到G中，并分配一个与它的邻居不同的颜色。

Spill Code以前我们假设了load－store 体系结构，就要在每个被抛出的生命期的引用前面插入一条load指令，在每个被抛出的生命期的赋值后面插入一条store 指令。

1. 识别生命期(Discovering Live Ranges)在一个函数里，变量i 可能被多次使用，每次都有不同的意义。

然而，没有必要让分配器为那些分离的使用（虽然有同样的变量名，却被分配了不同的虚拟寄存器）都安排同一个机器寄存器。

事实上，这种行为还会限制可能的染色方案。

每个分离的（对虚拟寄存器的）使用就是一个唯一的生命期，它们等待分配器来染色。

因此，分配器的首要任务是识别函数中的生命期。

在实现中，每个生命期被给予一个唯一的索引，按照生命期索引重写中间代码，代替原来的虚拟寄存器号。

识别生命期首先要找到可以合并的def-use链。

一根def-use链把一个虚拟寄存器的赋值和它所有的使用串联起来。

如果几根def-use链共享同一个使用（换句话说，几个赋值可以到达一个使用），这几根def-use链是可以合并的。

当然，那些从一个给定的赋值出发的链都是可以合并的。

2. 冲突(Interference)理解冲突的概念是理解图染色法分配器的关键。

只要把两个生命期分配到同一个寄存器会改变程序的语义，这两个生命期就冲突。

Chaitin给出了一些判断冲突的条件：如果两个生命期互相冲突，那么在函数中存在某些点满足下列的条件：1.两个生命期都被赋值，2.两个生命期都会被使用，而且3.两个生命期有不同的值。

这些条件不是独立，要联合起来使用。

Chaitin 最终的办法是看在每一个表达式里那些生命期是既活跃又可使用的。

我们称一个关于变量v的生命期l在某条语句s是活跃的，如果存在一条路径从s到v的其他使用，而且在这条路径上不存在对v的赋值。

类似的，称l在s是可使用的如果存在一条路径从v的赋值到s。

事实上，可使用性和活跃性对应了上面的条件1和条件2。

条件3要求小心地处理复制指令。

复制赋值中的源生命期和目的生命期会有相同的值，它们就不会冲突。

为了在以后能够合并（coalesce），它们也不应该冲突。

但是，如果它们因为其他的原因冲突，比如在函数中另外一点冲突关系被添到冲突图中，合并要被禁止。