图染色法的寄存器分配-iBrarian.PDF

图染色法的寄存器分配 计算机科学与技术系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）。后端在很大程度上是与语言无关 的，与机器有关的。 这个划分简化了每一个层次的开发和维护，使得在不同的