注册分配和溢出,简单方法？

Question

我正在寻找一种方法来将局部变量分配给寄存器.我知道有几种严肃的方法(即维基百科上提到的方法),但我仍然坚持如何"溢出"完成.此外,相关文献相当令人生畏.我希望有一些更简单的东西可以满足我的优先事项:

1. 正确性 - 一种算法,无论有多少局部变量,都会生成正确的代码.
2. 简单 - 我无需阅读太多文献即可理解.
3. 效率 - 它需要比现有方法更好,即:

将操作转换x = y # z为:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

由于我的目标是英特尔386,因此一些相关的限制是:

• 二进制操作有两个参数,其中一个是源和目标.一元操作只需一个参数.
• 操作只能访问一个内存位置; 因此,二进制运算需要寄存器中至少有一个参数.
• 最多有六个寄存器:%eax %ebx %ecx %edx %esi %edi.(%ebp也可作为最后手段.)
• 有一些特殊情况,例如整数除法和返回寄存器,但我现在可以忽略它们.

编译器目前有三个步骤:

• i386ification:所有操作都转换为表单a = a # b(或a = #a用于一元操作).
• 活力分析:确定每个操作之前和之后的活变量集.
• 寄存器分配:构建干扰图并着色.

然后编译器抛出它的蜡笔,不知道接下来该做什么.

例

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

这是函数的相当漂亮的干涉图,以及带有活跃度信息的CFG.遗憾的是,CFG图像确实需要一些垂直滚动.

• 14个变量函数的干扰图
• 具有活动信息的功能的控制流图

使用七种颜色.我想泄漏其中一个(或指定该颜色的变量集).选择哪种方法并不太重要.棘手的是如何处理溢出的变量.

比方说,我洒"粉红",这是一组变量t,$t4,$t7.这意味着引用这些变量之一的那些操作将从它在堆栈帧上的位置访问它,而不是通过寄存器.这适用于此示例.

但如果该计划是:

...
a = a + b
...

两者a并b已被打翻？我无法发出addl b, a带有两个内存地址的指令.我需要另一个备用寄存器暂时保存其中一个操作数,这意味着溢出另一种颜色.这表明了一种通用的方法:

1. 如果所有变量都可以用r颜色着色,那就太好了!
2. 否则,溢出一些颜色及其相关变量.
3. 如果存在访问两个溢出变量的操作,则溢出另一种颜色并使用备用寄存器进行所有此类操作的临时存储.

在这一点上,我怀疑有更多的东西溢出而不是必要的,并且想知道是否有更聪明的方法来溢出事物,例如溢出变量生命周期的一部分,而不是整个变量本身.我可以在这里使用一些简单的(ish)技术吗？再一次,我的目标并不是特别高 - 当然不够高,不需要读太深的东西.;-)

具体问题

主要的具体问题是:当变量溢出时,这会如何影响生成的指令？使用该变量的所有指令是否需要直接在内存中访问它(从其堆栈位置)？如果操作使用两个溢出变量,这将如何工作？(该体系结构不允许指令访问两个不同的内存位置.)

次要问题是:

• 如何确定插入加载/存储指令的位置,以确保正确性(以及不太重要的效率)？
• 如果变量没有立即使用,我可以仅将其生命周期的那一部分溢出,并在以后取消它吗？因此,所有指令都作用于未填充的寄存器.变量可能在不同的时间存在于不同的寄存器中.
• 在特殊情况下,我可以更有效率吗？例如,%eax用于返回值,因此如果要返回的变量恰好在遇到返回时分配给该寄存器,那将会很好.类似地,一些寄存器是"被调用者保存",因此如果在函数调用时碰巧存在较少的变量,将它们分配给非被调用者保存寄存器意味着我可以避免存储这些寄存器.
• SSA会形成多大帮助(如果有的话)？能够消除常见的子表达式并评估常数可能会降低(？)套准压力,但否则会产生任何影响？

我不关心的方面(现在)是:

• 堆栈分配和优化:它已经天真地实现,并且如果需要可以使用干扰图进行优化.
• 编译时效率,只要它终止.(NP完全性并不意味着应该避免使用给定的算法.)

更新

抱歉停机 - 我一直在考虑给出的答案,并试图找到一个简单的方法来开始实现一些想法.说实话,我一直在拖延......: -

我发现了非常好的演示文稿(PPT,遗憾的是):

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

这回答了关于如何处理特定操作需求的问题(比如对源和目标使用相同的寄存器;或者某些操作需要某个寄存器).我不确定的是Liveness-Coloring-Allocation循环是否终止.

我会尽快做一些实际的工作,希望能够解决这个问题.

Answer 1

我曾经在JVM分配器中使用了一种贪婪的方法,效果非常好.基本上从基本块的顶部开始,所有值都存储在堆栈中.然后只需向前扫描指令,维护一个包含值的寄存器列表,以及值是否为脏(需要写回).如果指令使用的值不在寄存器中(或者不在正确的寄存器中),则在指令之前发出加载(或移动)以将其置于空闲寄存器中.如果指令写入值,请确保它在寄存器中并在指令后将其标记为脏.

如果您需要一个寄存器,请通过从中取消分配值来溢出已使用的寄存器,如果它是脏的并且存在,则将其写入堆栈.在基本块结束时,回写任何脏和实时寄存器.

这个方案清楚地说明了所有加载/存储的确切位置,您可以随时生成它们.它很容易适应在内存中取值的指令,或者可以在内存中取两个参数中的任何一个,但不能同时取两者.

如果您可以在每个基本块边界处拥有堆栈上的所有数据,则此方案可以很好地工作.它应该给出类似于基本块内的线性扫描的结果,因为它基本上做了非常相似的事情.

关于如何确定要溢出的值和要分配的寄存器,您可能会有任意的复杂性.一些前瞻可能是有用的,例如通过在基本块中的某个点(例如,eax表示返回值,或ecx表示移位量)标记每个值,并且优先选择该值.首先分配(并避免该寄存器用于其他分配).但是很容易将算法的正确性与改进启发式分开.

我在SSA编译器YMMV中使用了这个分配器.

Answer 2

第一:没有明智的方法可以做到这一点.问题是NP完全;-)

如何溢出:

您运行您的寄存器分配算法并获取您必须溢出的变量列表.现在,您可以在函数开头的堆栈中分配一些空间.将每个溢出变量链接到堆栈上的某个位置.如果你想要智能合并内存与非重叠的有效范围.每当需要溢出寄存器时,将其保存到内存中并在需要时再加载它.

如何处理eax:

将寄存器标记为已填充,但不在其中存储任何变量(预分配).这将使代码生成器清除该寄存器.如果有益,要将值存储在另一个寄存器中.

处理溢出的简单而正确的方法:

只是溢出一切.这假设每个变量的有效范围都是整个程序.这可以通过使用LRU或使用计数等内容来选择应该释放哪些寄存器来增强.

下一个要做的最好的事情可能是线性扫描寄存器分配.即使使用预分配,它也应该很容易实现.我建议你查看链接的文件.

具体答案

1. 正确性对你意味着什么？如果不编程错误,即使是简单的分配算法也是正确的.打样(数学)正确性要困难得多.在再次需要值/寄存器之前,需要插入加载和存储.在存储/创建值之后需要插入两者.

2. 是.如果你这样编程.如果您的算法可以在其实时时间内处理多个寄存器中的值,则可以使用这些优化.

3. 您可以再次实施某些改进.一种可能性是仅在需要时阻止eax,而不是整个程序.

4. 在某些条件下,SSA确实有帮助.SSA代码的推理图总是和弦的,这意味着没有超过3个节点的循环.这是图着色的一种特殊情况,其中可以在多项式时间中找到最小着色.转换为SSA并不一定意味着更多或更少的注册压力.虽然SSA表单通常有更多变量,但这些变量往往具有较小的生存时间.