预着色节点

如之前展示的例子所示，指令选择中虽然基本上都使用虚拟寄存器，但是也有部分指令需要用到机器寄存器，机器寄存器的出现意味着平台相关信息，例如：

• mips调用约定中，$v0和$v1用于存放返回值；x86调用约定中，eax用于存放返回值

• 部分指令只能用特定的寄存器作为操作数，例如x86中的idiv reg指令，使用edx:eax作为被除数，源操作数reg作为除数，除法结果存放于eax中，模结果存放于edx中

• 函数调用需要使用指定的寄存器传递参数，例如mips调用约定中，$a0-3用于存放前四个参数，后续的参数则利用$sp通过栈传递

如果只允许生成只包含虚拟寄存器的汇编代码，是无法正确描述这些信息的。

汇编指令中的机器寄存器在干涉图中对应于一个预着色节点。与普通节点类似，它也会因为冲突而其他节点连边，特殊之处在于预着色节点间一定两两冲突。这就让着色算法没有必要从图中删除预着色节点：如果它的度数小于$K$，那么只能是$K - 1$，邻居只有其它预着色节点，把它删掉不会对图的其他部分的着色有任何贡献。

此外，George认为预着色节点可能与很多节点冲突(至少预着色节点间两两冲突)，为效率起见，不显式构造预着色节点的边列表。