图染色法的寄存器分配

1、图染色法的寄存器分配计算机科学与技术系98级吴汉唐摘要本文讲述了寄存器分配的图染色法理论。Chaitin 和他的同伴，在IBM 的Yorktown Heights研究中心，实现了第一个基于图染色法的全局的寄存器分配器。后来，Rice 大学的Preston Briggs对Chaitin的算法进行了改进和扩展。Chaitin的算法悲观地假设任何高度数的结点都不能被染色，只能被抛出（spilled）。Briggs的算法乐观地认为高度数的结点有可能被染色，从而获得更低的抛出开销（spill costs），和更快的代码。一 介绍（一） 编译器和优化一个优化编译器分为三个层次：l 前端把源语言转换为中间代

2、码。这个转换依赖于源语言的结构，需要几遍扫描（pass）代码才能完成。编译时的错误检查就在这一层。我们可以理想地认为前端是只与语言有关的、与机器无关的。l 优化器包含几遍的扫描（pass）， 每一遍扫描对中间代码执行特定的转换。我们感兴趣的是全局优化，就是从整个函数搜集有用信息，再去做优化。一般的全局优化包括强度削减（strength reduction），循环不变量移动（loop-invariant code motion）和公共子表达式消除（common subexpression elimination）。优化器最好是与语言和机器都无关的。l 后端把中间代码转换为针对特定机器的目标代码。

3、这个转换过程又称为代码生成，也需要几遍扫描才能完成。这几遍扫描包括指令选择（instruction selection）,指令调度（instruction scheduling）,寄存器分配（register allocation）。后端在很大程度上是与语言无关的，与机器有关的。这个划分简化了每一个层次的开发和维护，使得在不同的编译器中复用每个层次成为可能。例如，一个完全与机器无关的FORTRAN语言前端可以用到为不同机器设计的编译器中。当然，这还是一个理想的观点。在实际中，每个层次都表现出既与语言相关又与机器相关。这些相关限制复用和维护，也成为编译器设计人员努力要克服的难关。（二）优化和寄存

4、器分配寄存器是位于CPU内部的少量的高速存储器。寄存器与内存有很大的不同：l 寄存器很少。一个寄存器可以用几个比特直接定位。内存空间很大。内存的定位一般是通过间接的“寻址方式”，其中可能包含一个或多个对寄存器的引用。l 寄存器很快。在一个周期内，可以同时读两个寄存器，写第三个寄存器。内存要慢些，一次访问就需要几个周期。因为寄存器的个数受限和高速度，它们成为大多数计算机体系结构中的关键资源之一。寄存器分配器作为后端的一个模块，控制寄存器的分配和使用。寄存器很重要。最简单的情况，每条机器指令的操作数要放在寄存器里。在计算复杂表达式的过程中产生的中间结果也要在寄存器里。更复杂的编译器会把经常使用的变

5、量放在寄存器里，来避免反复地存取。如果是一个带优化的编译器，它会把公共子表达式消除或者循环不变量移动以后的重用值，放在寄存器里。分配寄存器的任务有几个层次l 寄存器只在一个表达式的范围内分配。这是一项为了减少寄存器需求量的指令调度的技术。l 更先进的分配器可以在一个基本块的范围内管理寄存器。l 全局分配器在一个函数的范围内工作。Chaitin 的分配器就在这样的例子。l 程序间的寄存器分配是对一些函数工作，通常是一个完整的程序。为了支持全局的优化，全局的寄存器分配是必须的。（三）寄存器分配和图染色法实现好的寄存器分配总是很困难。即使是最简单的实现也会因为机器的特殊细节变得复杂。可靠的分配器必要

6、能很好地对付复杂的程序和稀少的寄存器的情况。图染色法提供了一种简化的抽象。它建立一张表示分配过程中的各种限制的冲突图（interference graph），并对它染色，把许多表面上各异的细节纳入统一的模式。图中的结点代表生命期（live range），边代表生命期之间的冲突关系。一般说来，如果两个生命期在函数的某一点是同时活跃（live）的，它们就相互冲突，不能占有同一个寄存器。假设k 就是机器中可供分配的寄存器数目，如果图中的所有结点可以用k 种或者更少的颜色染色，有边相连的一对顶点接受不同的颜色，那么这种图染色方案对应一种寄存器分配方案。如果找不到一种k染色方案，只好修改代码重新染色。1

7、. 使寄存器使用率最小寄存器分配的目标是使不得不执行的load 和store指令的数目最小。把寄存器分配问题化归到图染色问题巧妙地转移了目标：以前是最小化存取内存的开销，变成最小化寄存器使用率。2. 使被抛出代码最少即使有最好的染色算法和大量的寄存器，有时候也不得不把某些值抛到内存里。这样就产生了几个难题。首先我们希望插入load 和store 指令的动态开销最小。我们必须设法选择抛出某些生命期，使得抛出开销低，又能减轻图中寄存器分配的压力。还有，我们考虑最好在哪里插入load 和store 指令。所有这些问题都很复杂，而且是互相关联的。二 背景(一)用图染色法来分配寄存器我们假设分配器工作在

8、一种类似汇编代码的低级的中间代码上。这种代码被优化器处理过，寻址模式和执行顺序是确定的。当然，这些假设忽略了分配器和编译器其他部件之间可能的协同关联。为了以后讨论的简化，我们还假设机器是loadstore的体系结构。在分配以前，中间代码可以引用无限数目的寄存器。我们把这些分配之前的不受限制的寄存器叫做“虚拟寄存器”。分配的目标就是重写中间代码，使它只使用目标机器提供的寄存器机器寄存器 。在寄存器分配中我们关心的是赋值（definition）和生命期（live range）。一个生命期是由共同的使用（use）连接的一个或多个赋值。所有组成一个生命期的赋值将用同一个虚拟寄存器命名。在分配之后，任意

9、一个机器寄存器通常对应几个生命期。为了把寄存器分配转化为图染色的模型，编译器首先构造一个冲突图G。G中的结点代表生命期，边代表冲突关系。这样，在图G中结点i与结点j有一条边相连当且仅当生命期l i 与生命期l j 冲突，就是它们在某一点同时是活跃的。与一个生命期li 冲突的那些生命期被称为l i的邻居。在图中邻居的数目就是l i 的度数，记做 l io 为了找到图G的一种寄存器分配，编译器首先寻找图G的一种k染色方案。如果机器寄存器的数目是k，我们就找到一种切实可行的寄存器分配方案。因为为任意一个图找到k染色方案是一个NP结问题，只能采用启发式算法来寻找染色方案，这就不能保证为每个可以k染色的

10、图找到k染色方案。(二)Yorktown 分配器Chaitin和他的同事在IBM的Yorktown Heights研究中心为PL8 编译器实现的分配器，是基于图染色法的全局的寄存器分配器的第一个实现。下图显示了Yorktown 分配器的流程。图 （1）Renumber 这个阶段找到函数中的所有生命期，并给它们以唯一的编号。Build 这一步要建立冲突图G。为了保证效率，G同时有两种表示形式：一个三角矩阵和一个相邻向量表。Coalesce 在这个阶段分配器删去不要的复制赋值，从代码中去掉对应的复制语句，合并源生命期和目标生命期。删去一个复制的前提是源和目标互相不冲突。我们把结点l i 和 l j

11、 的合并记为 l ij 。删去复制指令必然会改变冲突图，我们要重复build 和 coalesce直到再没有复制赋值。Spill Costs 在染色之前，对每个生命期 l 都要计算它的抛出开销。l 的抛出开销是对抛出l 后插入的load 和store指令造成的开销的评估。每条指令的开销用10 d加权，而d是这条指令的循环嵌套深度。Simplify 这个阶段，还有select ，一起对冲突图染色。simplify 反复地检查G中的结点，删去所有度数小于k的结点。当一个结点被删去时，与它关联的边也被删去，然后这个点被压入栈s。如果遇到G中剩下的每个结点的度数都大于k，就要选择其中一个抛出。但不会立

12、刻把结点对应的生命期抛出（也就是立刻更新代码和冲突图），只是把那个结点从G中删去，并标记为spilling。最后G会成为空图。如果有些结点被标记spilling，它们在spill code 阶段会被抛出，整个分配过程要重新来。否则，栈s被传递到select阶段。Select 按照在simplify阶段确定的顺序，把颜色分配给每一个结点。按顺序，每个结点从栈s中弹出来，重新插入到G中，并分配一个与它的邻居不同的颜色。Spill Code 以前我们假设了loadstore 体系结构，就要在每个被抛出的生命期的引用前面插入一条load指令，在每个被抛出的生命期的赋值后面插入一条store指令。1.

13、识别生命期(Discovering Live Ranges)在一个函数里，变量i 可能被多次使用，每次都有不同的意义。然而，没有必要让分配器为那些分离的使用（虽然有同样的变量名，却被分配了不同的虚拟寄存器）都安排同一个机器寄存器。事实上，这种行为还会限制可能的染色方案。每个分离的（对虚拟寄存器的）使用就是一个唯一的生命期，它们等待分配器来染色。因此，分配器的首要任务是识别函数中的生命期。在实现中，每个生命期被给予一个唯一的索引，按照生命期索引重写中间代码，代替原来的虚拟寄存器号。识别生命期首先要找到可以合并的def-use链。一根def-use链把一个虚拟寄存器的赋值和它所有的使用串联起来。如

14、果几根def-use链共享同一个使用（换句话说，几个赋值可以到达一个使用），这几根def-use链是可以合并的。当然，那些从一个给定的赋值出发的链都是可以合并的。2. 冲突(Interference)理解冲突的概念是理解图染色法分配器的关键。只要把两个生命期分配到同一个寄存器会改变程序的语义，这两个生命期就冲突。Chaitin给出了一些判断冲突的条件：如果两个生命期互相冲突，那么在函数中存在某些点满足下列的条件：1. 两个生命期都被赋值，2. 两个生命期都会被使用，而且3. 两个生命期有不同的值。这些条件不是独立，要联合起来使用。Chaitin 最终的办法是看在每一个表达式里那些生命期是既活跃

15、又可使用的。我们称一个关于变量v的生命期l在某条语句s是活跃的，如果存在一条路径从s到v的其他使用，而且在这条路径上不存在对v的赋值。类似的，称l在s是可使用的如果存在一条路径从v的赋值到s。事实上，可使用性和活跃性对应了上面的条件1和条件2。条件3要求小心地处理复制指令。复制赋值中的源生命期和目的生命期会有相同的值，它们就不会冲突。为了在以后能够合并（coalesce），它们也不应该冲突。但是，如果它们因为其他的原因冲突，比如在函数中另外一点冲突关系被添到冲突图中，合并要被禁止。3. 冲突图(The Interference Graph)在Yorktown 分配器中一个核心数据结构就是冲突图

16、。冲突图要提供5个操作。new(n) 返回一个n个结点的图，但是没有边。add(g,x,y) 返回图g，并在结点x和y之间添加一条边。interfere(g,x,y) 如果图g中结点x和y之间存在一条边就返回真。degree(g,x) 返回图g中结点x的度数。neighbors(g,x,f) 对图g中结点x的各个邻居应用函数f。在实现中，冲突图有两种表现形式：三角矩阵和相邻向量表。比特矩阵可以支持常数时间的add和interfere操作，而相邻向量表可以使neighbors更加有效率。构造冲突图是用两遍扫描完成，相邻表存储在一个连续的数组里。1. 开始，为比特矩阵分配空间和清零。对整个代码做一

17、遍扫描，填充比特矩阵并计算每个结点的度数。2. 知道每个结点的度数以后，为相邻表分配空间，重新初始化比特矩阵。在第二遍扫描时，冲突关系被记入比特矩阵和相邻表。每一遍合并以后，冲突图要重建。第二步会多次重复。我们实现的时候，每一遍对流图中的每个基本块逆向扫描，动态维护一个当前活跃并且可使用的生命期的集合。每遇到一处赋值，为被赋值的生命期和s中的所有元素在图中添加边。彻底完成buildcoalesce循环后，比特矩阵占据的空间可以被释放。相邻表在以后的阶段simplify 和select中还需要。4. 合并(Coalescing)建立冲突图以后，我们就要执行合并。对每个复制指令，我们检查它的源生命

18、期和目的生命期是否冲突；若不冲突，它们可以被合并，复制指令也被删去。为了合并两个生命期l x和l y 成为l xy，我们在用到l x、l y每个地方用l xy代替。当两个生命期l x和l y被合并，我们必须更新冲突图，使得l xy和l x、l y的邻居冲突。合并阶段对中间代码做一遍完全的扫描，尽可能地合并，更新冲突图。任一个复制语句被删去，都会导致重建冲突图，并引起更多的合并。这个周期一直重复到没有更多的复制语句被删去才停止。5抛出(Spilling)最粗糙的对抛出的处理方案就是：抛出一个生命期l，然后在l的每处赋值后面插入store指令，在l的每处使用前面插入load指令。Chaitin在他

19、的论文提供了两种重要的改善。首先，某些生命期是很容易重新计算的；比如，一个是常数的生命期。这些生命期不必被写入内存又重新读出来；相反，在每次使用之前可以重新计算。其次，不必要在用到这个生命期的每处都抛出。Chaitin 描述了几种情况。l 如果被抛出的生命期的两个使用是紧相邻的，就不必要为第二次使用从内存中重新读入；为这两个使用分配同一个寄存器就行了。l 如果一个使用紧跟在被抛出的生命期的赋值的后面，也就不必要在使用前重新读入了。l 类似的，如果一个生命期的所有使用都紧跟着对它的赋值，这个生命期也不必被抛出。6. 染色(Coloring)Yorktown 分配器的核心就是它的染色算法。Chai

20、tin的算法分为两个部分simplify和select。Simplify不断地把结点从图中删去，压入栈中。在select阶段，结点被从栈中弹出来，重新加到图中去。当结点l i的度数小于k时，它被从图中移入栈中。以后l i从栈中移回图中时，它的邻居数目仍然小于k。显然l i 在图中是可以着色的。在simplify阶段，只有确认一个结点在当前图中会被染色，才把它删去。当每一个生命期被删去时，它的邻居的度数就会降低。在select阶段，结点按照被删去的逆序分配颜色。如果在simplify阶段遇到一个图中所有的结点的度数都大于k，有一个结点将被选中抛出。这个抛出结点被从图中删去，并被标记为spilli

21、ng。一个处理方案是在程序中的这一点立刻插入代码，重建冲突图，寻找新的染色方案。这个方案虽然精确但开销巨大。Chaitin提到另一种不很精确的处理方案：在选择抛出结点后，继续简化（simplification）直到走完这一遍，标记出所有的抛出结点。三 Briggs的改进（一）两个难题Chaitin的启发式算法是有缺陷的，它产生了不必要的抛出。两个例子，一小一大，可以展示算法的缺陷。假设我们要为图（2）找到一个2染色方案。显然存在这样的方案；比如，x和y染红色，w和z染绿色。图 （2）如果运用Chaitin的算法，因为图中没有度数小于2的结点，必然有一个结点要被抛出。再看下一个例图 （3）。图

22、（3）SVD的结构图Briggs用上图的例程做测试的时候，发现分配器总是把小而短的生命期（M，N，I，J）抛出去，而不是大而长的生命期。尽管当时还有可分配的寄存器，但循环计数变量和循环计数的上界被抛出了。最后的结果就是：那段复制数组的循环代码几乎就没有利用寄存器。（二）改进的染色Briggs对Chaitin的算法做了两处修正：1. 在simplify阶段只要发现剩下的结点的度数都不小于k，就从中间选择一个抛出。这个结点被从图中删去，但是并没有被标记为spilling。它被压入栈，以后有可能获得一个颜色。2. 在select阶段发现不能为某些结点染色时，就放弃那个结点，继续对下面的结点染色。那些

23、被放弃的结点在Chaitin的算法中一定被抛出。Briggs改进后的分配器的流程见下图。图 （4）这样就可以解决前面提到的两个难题。推迟抛出产生两个结果。首先，它消除了一些无效的抛出。在Chaitin的方法中，抛出是在染色以前的simplify阶段就决定了。一旦一个结点被抛出，它对应的生命期也被抛出。在Briggs的方法中，那些结点放在栈里只是抛出的候选者，由select阶段才决定它们是否真的被抛出。其次，它提供了一个更强大的染色算法。在为结点x选择颜色的时候，它检查x的当前所有邻居的颜色。如果有两个或者多个x的邻居收到同样的颜色，即使x的度数不小于k，它也可以被染色。这就比Chaitin简单

24、地用“x的度数是否小于k”作为判据要准确。这样实现的分配器可以为图（2）产生一个2染色方案。再考虑图（3）的SVD例程。生命期I，J，M和N较早成为抛出的候选者，因为它们的抛出开销小。然而，抛出它们并不会减轻循环内部的寄存器分配的压力。分配器应该抛出那些大而长的生命期。等到这些小的生命期从栈中弹出来，已经有些大的生命期被抛出了。分配器很容易地为在循环中的小生命期分配颜色。Briggs只对Chaitin的算法做了些许的改动，没有增加它的实现难度，却取得显著的效果。致谢程旭老师是我的指导老师。他在实验室倡导的团队合作的精神，营造的勤奋上进的氛围，让我很受熏陶。他几次和我的谈话，都给了我深刻的启发。

25、我想向他表示诚挚的感谢和崇高的尊敬。我衷心地感谢两位师兄，朱德新博士和韩果凌硕士。他们具体管理和指导了我的工作，并在方法上给出了很中肯的意见。我曾经在中期报告中提到我实际上在一个小组中，后来关于寄存器分配的工作也不是我独自承担的。我衷心地向曾和我合作的高翊同学、陈江枫同学、聂书忻同学表示感谢，正是大家的讨论和协作促进了工作的进展。最后，我要感谢这个实验室的其他老师、研究生和本科实习同学。他们虽然与我的工作没有关系，但是他们形成的氛围对我产生了很深的影响。参考文献（1） Preston Briggs, Register Allocation via Grapth Coloring, April

26、1992;（2） Steven S. Muchnick, Advanced compiler design implementation;作者简介吴汉唐，男。1998年从湖南省考入北京大学计算机科学技术系学习，属于计算机科学与技术专业。2000年11月接受“北京大学泰兆大学生科学研究奖助金”的资助，在北京大学微处理器研究开发中心（它的前身是北京大学计算机科学与技术系系统结构教研室）工作。先后参与对SUIF系统的分析工作，针对JBCore32编译器的寄存器分配优化算法的实现工作。我学习勤奋，主动思考，本专业约130名学生，我在三年的绩点排名中是第41名，已经顺利保送本系读研究生。感悟与寄语我的前一部分工作是分析SUIF系统。在搜集资料的过程中，我看到了美国在编译领域的最新进展，他们已经建立NCI（国家编译基础设施），并在这个基础上开展了一系列的教学、实习、研究工作。反观国内编译研究的声势不大。后来我参加实现寄存器分配算法。虽然编译理论、优化算法已经成熟，但实现一个优化编译器仍是困难的事，需要一个大团队持久不懈的工作。实现寄存器分配算法时候的难点不是图染色法，而是怎么完善地处理与目标机器、编译器前端相关的细节问题。编译器的研究总是与微处理器、操作系统的发展相同步，祝愿我国能早日在