编译代码生成 - 条件块内部的寄存器分配

Question

我正在编写一门课程的编译器。我遇到了一些优化问题，我不确定如何处理最佳。假设输入语言有一个while循环，它使用必须保存在寄存器中的N个局部变量（或者应该为了快速计算）。假设N> K，寄存器的数量。在while循环结束时有可能改变条件寄存器。

例如，假设x的寄存器（比方说，在i386％EAX）确定之前发表声明如下：

while (x) { x = x - 1 ; /* more statements */ } 

在多个语句代码，它有可能被溢出的X回到栈上。当代码跳回到while循环的开始以重新计算x时，它将尝试使用％eax - 但这可能甚至不会保存x的值。所以我们可以有像我使用的是强制代码while语句（所以寄存器被视为空从代码生成的角度来看）之前，溢出所有修改寄存器

 movl -8(%ebp), %eax  # eax <- x 
     ....      # do stuff but let x stay in %eax 
_LOOP1: cmpl $0, %eax 
     .... 
     movl -12(%ebp), %eax  #eax now holds something else 
     .... 
     jmp _LOOP1 

一种解决方案。在while循环的标签之后，代码必须根据需要将所有内容加载到寄存器中。

我的解决办法是这样的：

 movl -8(%ebp), %eax  # eax <- x 
     ....      # do stuff but let x stay in %eax 
     movl %eax, -8(%ebp)  # spilling and clearing all registers 
_LOOP1: movl -8(%ebp), %eax  # get a register for x again 
     cmpl $0, %eax 
     .... 
     movl -12(%ebp), %eax  # eax now holds something else 
     .... 
     movl %eax, -8(%ebp)  # spill to prevent overwrite 
     jmp _LOOP1 

好像我的解决办法是有点多余的或不必要的。有没有我在这里忘记的一些一般优化技巧？

编辑：我还想指出类似的情况发生的条件，如if和if else。发生这种情况是因为一个寄存器可能被分配给条件块内的一个变量，但代码生成器假定它被移动到那里以后的其他所有内容中。我处理这个案件的方法几乎相同。

Answer 1

您在这里寻找的一般技术通常称为“活动范围分裂”。该术语的Google Search会给你指向一堆不同的论文。基本上这个想法是，你想要将一个变量（在你的例子中是x）分成多个变量，这些变量具有不相交的活动范围，每个变量都被复制到分割点的下一个变量中。所以你需要在循环之前有x.0，它在while之前被复制到x.1中，并在循环中用作它。然后在循环之后，您将x.1复制到x.2并在循环之后使用它。每个拆分变量都可能被分配到不同的寄存器（或栈槽）。

这里有很多折衷 - 太多的分割会导致代码中（更多）更多的变量，从而导致寄存器分配速度变慢，并可能导致不必要的副本。