登记册的分配和蔓延，最容易的方法？

StackOverflow https://stackoverflow.com/questions/1960888

题

我在寻找一种方式来分配本地的变量，为寄存器。我所知道的几个严肃的方法这样做(即所提及的那些 在维基百科的)，但是我被困在如何"溢出"是成功的。此外，相关文献是相当吓人。我希望有什么简单的就会满足我的优先事项：

  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图像确实需要一些直滚动，不幸的。

七个颜色都用。我想泄漏他们中的一个(或一组变量分配的颜色).方法的选择不太重要的。得到什么棘手，是如何处理溢出的变量。

我们说我溢出"粉红色"，这是一套变量 t, $t4, $t7.这意味着这些行动的参照这些变量之一将访问从其位置上堆框架，而不是通过一个登记册。这应该作为这种例子。

但是，如果该程序是：

...
a = a + b
...

和两个 a 和 b 必须溢?我不能发出一条指令 addl b, a 有两个存储的地址。我需要另一个备用的登记册暂时保持一个操作数，并且这意味着蔓延的另一种颜色。这表明一般方法：

  1. 如果所有的变量可能有彩色的 r 色彩，伟大的！
  2. 否则，溢油的一些色彩及其相关的变量。
  3. 如果一个操作存在访问两个洒变量溢出的另一种颜色和使用的备用寄存器的临时储存所有这类行动。

在这一点上，我就怀疑了很多东西是被溢出于必要，并想知道是否有一些聪明的方式蔓延的事情，例如蔓延的一部分变量的生命周期，而不是整个变量本身。有一些简单的(ish)技术，我可以用在这里？再次，我不瞄准特别高--肯定不会高到足以需要阅读任何东西太深。;-)

具体问题

主要的具体问题是：当一个变量溢出，这如何会影响的说明产生?做的所有指令使用，可变的需要访问它直接在存储器(从其堆的位置)?如何将这项工作，如果操作使用两个变量溢出的?(架构不允许指令访问两个不同的存储位置。)

次级问题：

  • 我如何确定在其中插入负/存储指令，对于正确性(及同样重要的是，效率的)?
  • 我可以泄漏一个变量只是一部分的其一生的时候它不是在立即使用，并unspill它以后呢？因此，所有指令行事unspilled寄存器。一个变量可能生活在不同的登记在不同的时间。
  • 我可以一个小小的更有效的特殊情况。例如， %eax 用于返回的价值，因此它是好的，如果变为可以返回发生在被分配给注册的时间返回遇到。同样，一些寄存器"被叫保存"，因此，如果较少的变量发生了能生活在一个功能的电话，让他们分配给非被叫保存寄存器将意味着我可以避免储存的那些寄存器。
  • 将福利金的形式有多大帮助(如果有)?能够消除公共子表达式和评估的常量可能会减少(?) 登记册的压力，但否则会有任何效果？

这方面我不关心(现在)：

  • 堆的分配和优化：这是实现天真，可以最优化的使用干扰图，如果需要的话。
  • 编译时间效率，只要它终止。(NP-完整性并不意味着一定的算法应该是可以避免的。)

更新

对不起有关的停机时间--我一直在思考关于给出的答案，并试图找到一个简单的方法采取开始实施的一些想法。说实话，我已经被拖延...:-\

我找到了很好的介绍(PPT，可悲的是):

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

其回答的问题是关于如何处理具体操作的需求(如使用相同的注册来源和目的地；或者需要一定的登记册对某些操作)。什么我不确定是否活跃-颜色分配周期终止。

我会尝试做一些实际工作很快，并希望密切的问题。

有帮助吗？

解决方案

我用一个贪婪的做法在一个JVM分配一次，它工作得很好。基本上，开始在上面的一个基本框所有价值观存在的叠。那么只是扫描的指示前，维持一个列表中的寄存器包含一种价值，以及是否值是肮脏的(需要编写)。如果一项指令使用的价值，这不是一个登记册(或不正确的登记)，问题负载(或者移动)，以把它放在一个免费注册之前的指令。如果指令写入一个价值，确保在登记和标记肮脏的后的指令。

如果你需要一个登记册，洒使用的登记册通过释放的价值，它写到堆如果这是肮脏的生活。在结束基本块，写信回来的任何肮脏和动机。

这种方案使得很清楚究竟在那里所有的载荷/店去，你生他们为你去。它很容易适应说明它采取一个数值在存储器，或可以采取两种论据存储，而不是两个。

如果你确定与具有所有的数据堆在每一个基本块边界，这个方案工作得很好。它应该得到的结果相类似的线扫描内的一个基本框，因为它基本上并非常类似的事情。

你可以得到任意的复杂关于如何决定哪些值溢和其寄存器来分配。一些预期可能是有用的，例如通过标记的每个值与一个特定的登记册，它需要在某一点基本区块(例如eax返回值，或ecx转变量)，和更愿意，登记时的价值是第一分配的(并避免注册的其他拨款).但是很容易分离出来的正确性算法从改进的启发。

我用这个分配在SSA的一个编译器，情况因人而异。

其他提示

第一:没有智能的方式来做到这一点。问题是NP-完成;-)

如何溢出是完成：

运行登记册分配的算法，并得到一个变量清单你要泄漏。现在你可以拨出一些空间，堆在开始你的功能。连接每个洒变量也上的一个地方堆。如果你想要的明智结合的记忆与非重叠的生活范围。每当你需要溢出一个登记册保存记忆和装载它，当它再次需要使用。

如何处理eax:

标记登记册作为填补，但不存储的任何变它(预先分配)。这将使代码生成显然，登记册。是聪明的商店的价值在另一个登记册，如果有益的。

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

只是泄漏的一切。这个假设每个变量的生活的范围是整个程序。这可以增强通过采用这样的东西LRU或使用计数以选择登记应被释放。

一个最好的事情要做的就是可能 直线扫描登记册的分配.它应该是很容易实现，甚至在使用预先分配。我建议你看看到联纸。

具体答案

  1. 什么是正确的意思是你吗？即使是简单的拨款额的算法是正确的，如果你不做一个编程的错误。校对(数学)的正确性是一个很大的困难。两种加载和存储需要之前插入价值/注册是必要的。这两种需要之后插入价值，是保存/创建的。

  2. 是的。如果你计划这种方式。如果你的算法可以处理的价值在多个注册过其livetime可以使用那些优化。

  3. 这是一次由你来实现某些改进。一个可能性是唯一的框eax需要的时候，不适用于整个程序。

  4. 在某些条件下SSA会的帮助。推断的图表SSA码是总是 弦, ，这意味的是，没有周期有超过3节点。这是一个特殊的情况下图着色，其中一个最小的着色，可以发现在多项式的时间。转换到公共福利金并不一定意味着或多或少注册的压力。同时SSA的形式通常更多的变量，这些往往具有较小livetimes.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top