070107107范有卉-图着色寄存器分配方法深入探讨.doc

070107107范有卉-图着色寄存器分配方法深入探讨图着色寄存器分配方法深入探讨070107107图着色寄存器分配方法深入探讨作者姓名:范有卉指导老师:王一宾摘要:本文讲述了寄存器分配的图着色法理论。首先对寄存器分配方法的基本理论及其相关理论进行了介绍,然后分析了基于图着色的寄存器分配方法,其次进一步分析Chaitin的算法及其优化后的Briggs的算法,最后得出结论从而获得更低的抛出开销和更快的代码。关键词:寄存器分配,图着色法,冲突,抛出开销随着技术的不断发展,高性能处理器的结构越来越复杂,编译器在发挥这一类处理器性能上所扮演的角色也越来越重要。寄存器作为机器硬件结构中有限的宝贵资源,这就使得寄存器分配技术成为编而一译器后端最为重要的优化技术之一。寄存器分配的目的是将程序中的变量尽可能保存在寄存器中,旦寄存器不够用,就要把变量保存到内存中去。从八十年代到九十年代,对全局寄存器分配研究得最多的是图着色的分配方法。。寄存器是计算体系结构中最快的存储空间,同时也是最为稀缺和宝贵的存储资源。因此,编译器所生成的可执行代码对寄存器的充分利用成为代码执行时性能及编译优化效果的重要因素。寄存器分配是代码生成的一个阶段,由它决定在程序的不同执行点上,哪些变量应该放在寄存器中。一个优化编译器分为三个层次:,前端把源语言转换为中间代码。这个转换依赖于源语言的结构,需要几遍扫描(pass)代码才能完成。编译时的错误检查就在这一层。我们可以理想地认为前端是只与语言有关的、与机器无关的。,优化器包含几遍的扫描(pass),每一遍扫描对中间代码执行特定的转换。我们感兴趣的是全局优化,就是从整个函数搜集有用信息,再去做优化。一般的全局优化包括强度削减(strengthreduction),循环不变量移动(loop-invariantcodemotion)monsub-expressionelimination)。优化器最好是与语言和机器都无关的。,后端把中间代码转换为针对特定机器的目标代码。这个转换过程又称为代码生成,也需要几遍扫描才能完成。这几遍扫描包括指令选择(instructionselection),指令调度(instructionscheduling),寄存器分配(registerallocation)。后端在很大程度上是与语言无关的,与机器有关的。这个划分简化了每一个层次的开发和维护,使得在不同的编译器中复用每个层次成为可能。例如,[1]一个完全与机器无关的FORTRAN语言前端可以用到为不同机器设计的编译器中。当然,这还是一个理想的观点。在实际中,每个层次都表现出既与语言相关又与机器相关。这些相关限制复用和维护,也成为编译器设计人员努力要克服的难关。。寄存器与内存有很大的不同:,寄存器很少。一个寄存器可以用几个比特直接定位。内存空间很大。内存的定位一般是通过间接的“寻址方式”,其中可能包含一个或多个对寄存器的引用。,寄存器很快。在一个周期内,可以同时读两个寄存器,写第三个寄存器。内存要慢些,一次访问就需要几个周期。因为寄存器的个数受限和高速度,它们成为大多数计算机体系结构中的关键资源之一。寄存器分配器作为后端的一个模块,控制寄存器的分配和使用。寄存器很重要。最简单的情况,每条机器指令的操作数要放在寄存器里。在计算复杂表达式的过程中产生的中间结果也要在寄存器里。更复杂的编译器会把经常使用的变量放在寄存器里,来避免反复地存取。如果是一个带优化的编译器,它会把公共子表达式消除或者循环不变量移动以后的重用值,放在寄存器里。分配寄存器的任务有几个层次,寄存器只在一个表达式的范围内分配。这是一项为了减少寄存器需求量的指令调度的技术。,更先进的分配器可以在一个基本块的范围内管理寄存器。,全局分配器在一个函数的范围内工作。Chaitin的分配器就在这样的例子。,程序间的寄存器分配是对一些函数工作,通常是一个完整的程序。[2]为了支持全局的优化,全局的寄存器分配是必须的。。即使是最简单的实现也会因为机器的特殊细节变得复杂。可靠的分配器必要能很好地对付复杂的程序和稀少的寄存器的情况。图着色法提供了一种简化的抽象。它建立一张表示分配过程中的各种限制的冲突图(interferencegraph),并对它着色,把许多表面上各异的细节纳入统一的模式。图中的结点代表生命期(liverange),边代表生命期之间的冲突关系。一般说来,如果两个生命期在函数的某一点是同时活跃(live)的,它们就相互冲突,不能占有同一个寄存器