compiler-construction - Chaitin 的寄存器分配算法：R 寄存器使用了多少种颜色？

Question

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

标签： compiler-constructionregister-allocation

Answer 1

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