编译器如何知道变量是否在代码生成中溢出?

Question

我正在实现一个使用访问者模式的编译器。

这是我使用的一般算法。

regs给出了所需的寄存器数，top给出了下一个空闲的寄存器数。

generate(T,n) =
if T is a leaf write ``load top(), T"
if T is an internal node with children l and r then
if regs(r) = 0 then { generate(l); write ``op top(), r" }
else{
generate(l,n)//Stored in Rn
generate(r,n+1)//Stored in Rn+1
write "op Rn, Rn+1" // rresult is stored in Rn
push(R) }

但是在没有足够的寄存器的情况下，我们需要溢出变量。假设我们使用贪婪分配器溢出最后使用的寄存器． 这意味着，当我们执行generate(r)操作时，如果没有剩余的寄存器来存储结果，我们将压入Rn将结果存储在Rn中，然后检索溢出的变量来计算操作。

完整的模式变成:

generate(l,n)//Stored in Rn
push Rn // push to stack
generate(r,n)//Stored in Rn 
mov Rn R0 // move
pop Rn // retrieve from stack
write ``op Rn, R0" // result is stored in Rn

我所尝试的是修改函数top，使其返回一个寄存器，如果有任何可用，并在没有人可用的情况下返回它之前推送最后一个寄存器，所以当生成r子时，我们可以保存堆栈，如果没有空间…

generate(l,top())//Stored in Rn
generate(r,top())//Spill if no space and store in Rn 
mov Rn R0 <--- my problem is here
pop Rn <--- my problem is here
write ``op Rn, R0" <---my problem here

但是在生成l和r之后，操作怎么知道它需要unspill*一些变量(如果必须)?

我的问题是:

在编程上，我如何在编译器中实现它，使其对操作代码无关。

理想……代码应该像这样:

generate(l,something())//Stored in Rn
generate(r,something())
write ``op somethingelse(), againsomethingelse()" <--- taking into account when space is available or not

Answer 1

contificate的评论是对的。我再详细解释一下。

首先，我建议您阅读以下幻灯片:https://web.cs.wpi.edu/~kal/courses/compilers/module6/RastislavBodikregalloc.PDF

在幻灯片28上，你可以看到溢出是如何工作的。你进入一个循环:尝试通过着色来分配寄存器。如果失败了，洒出寄存器，然后再试着着色。重复，直到你成功。

您如何跟踪哪些变量被溢出或没有?你不。当您重写代码以适应溢出时，您可以免费获得跟踪。幻灯片28上写着

在每次使用f的操作之前，插入f:= load fa

在每个定义f的操作之后插入存储f, fa

如果你的程序中有

t2 = t0 + t1
...
t10 = t2 + t3

无论什么原因，你不能为临时t2分配寄存器，这意味着它的干涉图被太多的边过载。你需要消除一些边缘。你是怎么做到的?通过让一个变量存活更短的时间。你如何做到这一点?通过在需要使用变量时插入加载和存储。所以我给的例子变成了:

t2 = t0 + t1
store t2    // immediately stores t2 after its use
...
// loads t2 just right before it is used
t2 = load t2
t10 = t2 + t3

这样t2就会在很短的时间内存活。这将减少干扰图中的压力，从而允许新一轮尝试将寄存器分配给干扰较少的图中的临时寄存器。如果不能再次找到颜色，选择另一个临时的，溢出(插入负载和存储在需要的地方)，并重复。

这不是唯一的方法，但我相信这是最简单的方法之一。