编译原理与实践：图着色方法分配寄存器

当计算中需要一个寄存器，但所有可用寄存器都在使用时，某个正被使用的寄存器的内容必须被保存到一个内存位置上，以便释放出一个寄存器。图着色方法是一个可用于分配寄存器和管理寄存器的值保存到内存里的技术。

这个方法需要进行两趟处理。第一趟处理中选择目标机器指令，处理时假设有无穷多个符号化寄存器。经过这次处理，中间代码中使用的名字变成了寄存器的名字，而三地址指令变成了机器指令。如果对变量的访问要求一些指令使用栈指针、基址寄存器等辅助访问，均假设具有这些量并已经存放好。在选择好了指令之后，第二趟处理把物理寄存器指派给符号化寄存器。这一次处理的目标是寻找到一个溢出代价量小的指派方法。

在第二趟处理中，对每个过程都构造一个寄存器冲突图。图中的结点是符号化寄存器。对于任意两个结点，如果一个结点在另一个被定值的地方是活跃的，那么这两个结点之间就有一条边。然后就可以尝试用k种颜色对寄存器冲突图进行着色，其中k是可指派的寄存器的个数。一个图被称为已着色（colored）当且仅当每个结点都被着了一个颜色，并且没有两个相邻的结点的颜色相同。一种颜色代表一个寄存器。着色方案保证不会把同一个物理寄存器指派给两个可能相互冲突的符号化寄存器。(www.xing528.com)

确定一个图是否k-可着色是一个NP问题，但在实践中常常可以使用启发式技术进行快速着色。假设图G中有一个结点n，通过一条边连接到n的结点个数少于k个。把n及和n相连的边从G中删除后得到一个新图。对新图的一个k着色方案可以扩展成为一个对G的k着色方案，只要给n指派一个尚未指派给它的邻居的颜色就可以了。

通过不断地从寄存器冲突图中删除边数少于k的结点，最终得到一个空图，或者得到的图中每个结点都至少有k个相邻的结点。在第一种情况下，可以依照结点被删除的相反顺序对结点进行着色，从而得到一个原图的k着色方案。在第二种情况下已经不存在k着色方案了。