着色算法

一般的图着色问题是NP困难的，这里使用一种简单的启发式算法：任意选择图中的一个度数$< K$的节点移除，压入栈中，如果这个过程能够一直继续，那么当图为空时再依次弹出栈中的节点，逐节点将图恢复，为之任意赋予一个与当前的邻居不冲突的颜色。当一个节点被弹出栈的时候它的邻居一定$< K$个，所以总能选出它的颜色。

然而，如果压栈的过程不能继续下去，即当前图中不存在任何度数$< K$的节点，则表示这个图可能不能$K$着色了，这称为一次"可能溢出"。这时可以根据某种启发式的策略任意选择某个节点强行移除，压入栈中，然后继续尝试，如果仍然没有度数$< K$的节点则继续强行移除节点。最终仍然依次弹出栈中的节点，尝试为之任意赋予一个与当前的邻居不冲突的颜色，如果这样的颜色不存在，表明着色算法没法为它分配颜色了，这称为一次"实际溢出"。

如果着色中发生了实际溢出，则需要把对溢出的节点的引用转化为访存操作。显然这样会导致程序发生改变，所以逻辑上着色过程必须再次进行，如此迭代直到没有任何实际溢出发生为止。

Chaitin提出了一些关于选择强行移除的节点启发式的策略，目的是尽量减少循环中的溢出和尽量让溢出后的图容易着色，例如检测流图中的循环，一个节点在循环内部的引用将为它增加更多代价，然后综合考虑这个代价和节点的度数来选择节点。关于在什么地方插入访存指令也有一些启发式的方法，例如可以在一个基本块首插入对于这个基本块中需要使用的被spill的变量的读指令，基本块尾插入这个基本块中需要写的被spill的变量的存指令。

将虚拟寄存器spill到内存中的什么位置也有值得优化的地方。考虑所有被spill的虚拟寄存器，它们之间也可以依据是否冲突来构造干涉图，任何不冲突的两个虚拟寄存器都可以被分配到栈帧上的同一个地方来保存。这也可以转化成一个着色问题，只是因为内存的大小往往远大于虚拟寄存器的数量，这里就不再有色数的上限了，只要尝试寻找可能的最小的色数即可。

不过以上这些复杂的方法我们都没有用到：对于节点的选择，直接选择图中度数最大的节点强行移除；对于访存指令的插入，直接为每次引用都生成一个新的虚拟寄存器，读之前从内存加载到新的虚拟寄存器，写之后把新的虚拟寄存器写入只属于自己的栈内存。