编译器代码生成 - 在条件块内注册分配

Question

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

例如,假设在以下语句之前确定了x的寄存器(假设i386上的%eax):

while ( x ) { x = x - 1 ; /* 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等条件.对于它们会发生这种情况,因为可以为块内的变量分配一个寄存器用于条件,但是代码生成器假定它被移动到其后的其他所有内容中.处理这种情况的方法几乎相同.

Answer 1

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

这里有很多权衡——太多的分割会导致代码中出现更多的变量，使寄存器分配速度慢得多，并可能导致不必要的复制。