6

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

例如，假设 x 的寄存器（比如 i386 上的 %eax）在以下语句之前确定：

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

在 more statements 代码中，x 可能会溢出回堆栈。当代码跳回到 while 循环的开头重新计算 x 时，它会尝试使用 %eax——但这现在可能甚至没有保存 x 的值。所以我们可以有类似的东西

        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 语句之前溢出所有已修改的寄存器（因此从代码生成器的角度来看，寄存器被视为空）。在 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 等条件句中。这发生在他们身上，因为可以为条件块内的变量分配一个寄存器，但代码生成器假定它被移到那里用于之后的所有其他事情。我处理这种情况的方法几乎相同。

4

1 回答 1

4

您在这里寻找的一般技术通常称为“实时范围分割”。对该术语的Google 搜索将为您提供指向一堆不同论文的指针。基本上，这个想法是您希望将单个变量（在您的示例中为 x）拆分为具有不相交生存范围的多个变量，每个变量在拆分点被复制到下一个。所以你在循环之前有 x.0，它被复制到 x.1 之前，while并用作循环中的那个。然后在循环之后，您将 x.1 复制到 x.2 并在循环之后使用它。每个拆分变量都可能被分配到不同的寄存器（或堆栈槽）。

这里有很多权衡 - 太多的拆分会导致代码中的（许多）更多变量，使寄存器分配更慢，并可能导致不必要的副本。

于 2010-09-26T21:33:04.217 回答