编译原理与技术是计算机科学中最古老、最高度发达、也是成果应用最广泛 的课题之一。编译器原理涉及的知识体系非常广且繁杂，和计算机科学的许多学 科分支，如形式语言与自动机、类型系统、算法设计分析、程序设计语言、最优化 理论、指令集体系结构等，都有密切联系；同时，编译器工程又涉及到非常丰富的 算法数据结构、软件工程、软件测试等领域知识，包含非常多的编程技巧和各种工程 优化。编译器做为重要基础软件之一，向上支持各类丰富的程序设计语言，向下支持 各种目标指令集体系结构；深入理解和掌握编译原理相关知识和实现技术，对于学生 深入系统理解和掌握相关领域具有重要作用。

但另一方面，目前已经有的编译原理和技术方面相关的教材、参考书和专著，大都把讲授 重点放在相对成熟的编译器前端和中端部分，对编译器后端技术尤其是寄存器分配技术 介绍偏少；这给学生学习和掌握相关课题带来了挑战和困难：一方面，后端的寄存器分配是 编译器非常重要的组成部分，甚至被认为是编译器中最重要的一种编译器优化 （Hennessy和Patterson）；更重要的是，寄存器分配问题集中体现了编译原理整个学科 最鲜明的一些特点---针对一个特别困难的问题（NP完全）、研究实际能行的解法（各种 启发式算法）、并给出精美的实现（对数据结构和算法的仔细工程）。从寄存器 分配这个具体课题出发，我们才有机会看到编译原理有别于其他学科的显著特点。

本书对编译器原理后端的寄存器分配问题，进行了系统讨论，有好几个原则指导 了本书的准备过程：第一个原则是完整性。初学者在学习寄存器分配这个课题时，遇到 的最大困难之一是背景知识的广泛性和复杂性，因此，本书对涉及的相关背景知识，如 图着色、弦图、SSA、整数线性规划、二次分配问题等，都做了必要的讨论；对相关 问题的历史背景研究进展，在每章的深入阅读部分，给出了参考文献，本书争取做到自容。

第二个原则是通用性，即本书重点讨论适用于所有目标指令集体系结构的寄存器 分配通用技术，在这些通用技术和特定体系结构的具体技术特性如寄存器数量、调用约定等 底层细节间取得一个平衡。

第三个原则是实践性，考虑到编译原理理论和实践紧密结合的学科特点，本书除了对 相关理论的深入讨论之外，还特别强调了对实现技术的介绍，对所讨论的每个数据结构和 算法都给出了类C语言的算法描述；这样，学生不仅能够深入理解寄存器分配的基本 原理，还能基于这些算法亲自动手实践。

本书内容共分七章，第一章研究 寄存器分配必备的基础知识，包括控制流图数据结构、活跃数据流分析、干涉图 数据结构、以及对寄存器分配问题的整体介绍；第二章讨论基于 图着色的寄存器分配算法，具体内容包括图着色的基本思想、Kempe定理及其 应用、溢出、接合以及接合策略；第三章讨论线性扫描寄存器 分配，论题包括活跃区间分析与构建、线性扫描寄存器分配算法、溢出和接合等；第 四章讨论弦图分配，论题包括弦图及其性质、基于完美消去序列 的弦图分配算法等；第五章讨论基于SSA形式的寄存器分配；第 六章讨论基于整数线性规划的寄存器分配；最后，第七章 讨论PBQP寄存器分配算法。

本书是笔者在中国科学技术大学软件学院，所讲授的相关课程资料的基础上综合整理 而成，感谢科大的相关同学在选修这些课程时的积极参与，以及对课程所反馈的建议意见。

限于作者的知识水平和时间，不妥甚或谬误之处在所难免，敬请读者指正。

华保健
于中国科学技术大学软件学院