Chaitin 寄存器分配算法：R 寄存器使用多少种颜色？

Question

在我关于寄存器分配/Chaitin's Algorithm的讲座中，似乎我们构造了一个干涉图，然后尝试找到该图的k着色，其中k=R，如果我们可以在目标架构中使用R寄存器。但是，如果我们溢出一个值，这是否意味着我们需要一个额外的寄存器来在指令中使用它们之前从内存中加载值，因此只能将 k=R-1 值用于 Chaitin 算法？

Answer 1

您仍然可以使用 k=R。当您溢出值时，您可以添加存储和检索值的溢出代码(通常在堆栈上，但也存在其他替代方法(。这将取代原始虚拟寄存器，对许多新的虚拟寄存器进行高度干扰，这些虚拟寄存器仅存在很短的时间并且(希望(程度较低。您现在可以再次尝试着色，如果仍然失败，则重复溢出过程，直到成功。