问题标签 [register-allocation]

我有ML 中的龙书和现代编译器实现。我正在寻找有关编译器中代码生成的其他好的资源。你能推荐任何吗？

在编译器设计中，为什么调用者不能将其已用寄存器列表（在调用者保存安排的情况下它将推送）传递给被调用者，以便被调用者可以比较它的而不是调用者或被调用者寄存器保存安排使用的寄存器列表到调用者使用的寄存器。然后只有真正需要推送的寄存器才会被推送。我错过了什么吗？

在 C 中，我们不能使用 & 来找出寄存器变量的地址，但在 C++ 中我们可以这样做。为什么它在 C++ 中合法，但在 C 中不合法？有人可以深入解释这个概念。

我正在寻找一种将局部变量分配给寄存器的方法。我知道有几种严肃的方法可以做到这一点（即Wikipedia 上提到的那些），但我坚持“溢出”是如何完成的。此外，相关文献相当吓人。我希望有一些更简单的东西可以满足我的优先事项：

1. 正确性——无论有多少局部变量，都会生成正确代码的算法。
2. 简单——我不需要阅读太多文献就能理解的东西。
3. 效率——它需要比目前的方法更好，即：

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

由于我的目标是 Intel 386，一些相关的限制是：

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

编译器目前需要完成三个步骤：

• i386ification：所有操作都转换为一种形式a = a # b（或a = #a一元操作）。
• 活度分析：确定每次操作前后的活变量集。
• 寄存器分配：建立干扰图并着色。

And then the compiler throws its crayons in the air and doesn't know what to do next.

Example

Here's the rather pretty interference graph for the function, and the CFG with liveness information. The CFG image does require some vertical scrolling, unfortunately.

• Interference graph for a function on 14 variables
• Control-flow graph for a function, with liveness information

Seven colours were used. I would like to spill one of them (or the set of variables assigned that colour). The method of choosing which isn't too important. What gets tricky is how to deal with the spilt variables.

Let's say I spill "pink", which is the set of variables t, $t4, $t7. This means that those operations referring to one of these variables will access it from its position on the stack frame, rather than through a register. This should work for this example.

But what if the program was:

and both a and b had to be spilled? I can't emit an instruction addl b, a with two memory addresses. I would need another spare register to temporarily hold one of the operands, and that means spilling another colour. This suggests a general method of:

1. If all variables can be coloured with r colours, great!
2. Otherwise, spill some colours and their associated variables.
3. If an operation exists that accesses two spilled variables, spill another colour and use the spare register for temporary storage for all such operations.

At this point I would suspect that a lot more stuff is being spilled than necessary, and wonder if there is some smarter way to spill things, such as spilling part of a variable's lifetime, rather than the whole variable itself. Are there some simple(ish) techniques that I could use here? Again, I'm not aiming particularly high -- certainly not high enough to require reading anything too deep. ;-)

Specific problems

The main specific problem is: when a variable is spilled, how does this affect the instructions generated? Do all instructions using that variable need to access it directly in memory (from its stack position) ? How will this work if an operation uses two spilled variables? (The architecture does not permit instructions to access two distinct memory locations.)

Secondary problems are:

• How do I determine where to insert load/store instructions, for correctness (and less importantly, efficiency) ?
• Can I spill a variable for only that part of its lifetime when it is not in immediate use, and unspill it later? So that all instructions act on unspilled registers. A variable might live in different registers at different times.
• Can I be a little more efficient with special cases. For example, %eax is used for the return value, so it would be nice if the variable to be returned happened to be allocated to that register by the time the return was encountered. Similarly, some registers are "callee-save", so if fewer variables happened to be live at the time of a function call, having them allocated to non-callee-save registers would mean I can avoid storing those registers.
• Would SSA form help much (if at all) ? Being able to eliminate common subexpressions and evaluate constants might reduce(?) register pressure, but otherwise would it have any effect?

The aspects I'm not concerned about (right now) are:

• Stack allocation and optimisation: it's implemented naively already, and can be optimised using the interference graph if need be.
• Compile-time efficiency, just as long as it terminates. (NP-completeness does not imply a given algorithm should be avoided.)

Update

Sorry about the downtime -- I've been thinking about the answers given and trying to find an easy approach to take to start implementing some of the ideas. To be honest, I've been procrastinating... :-\

I found the very nice presentation (PPT, sadly):

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

Which answers the question about how to deal with specific operation needs (like using the same register for source and destination; or needing a certain register for some operations). What I'm not sure about is whether the Liveness-Colouring-Allocation cycle terminates.

I'll try to do some actual work soon and hopefully close the question.

如何构建干扰图以便在寄存器分配中使用它？如何确定生存范围？

我一直在构建自己的编译器，其中很大一部分显然是寄存器分配器，它尽可能有效地将临时变量与机器寄存器匹配。在诸如 x86 之类的架构上，寄存器并不多，因此存在大量溢出，其中变量必须存储在内存（堆栈）中。还有一些变量存储在内存中，因为它们太大而无法放入寄存器中。

实际上再次调用寄存器分配器以有效地分配内存中的变量，以便尽可能多地共享空间。真正的问题是没有办法限制寄存器分配器将两个变量放在内存中彼此相邻（因为我可以给它更大的变量作为一些较小的变量）并允许分配器移动较小的变量这样更大的变量可以适应，我想知道是否有任何算法可以处理这个问题，否则我必须将内存分成不同的区域，每个区域都保存不同大小的变量。

下面是一个例子来证明这一点：

出于示例的目的，这里有一些假设......变量没有被优化掉，一旦定义了 c 并且所有变量都分配到堆栈内存，a 和 b 就不再有用了。显然，我希望“c”使用与刚刚使用的“a”和“b”相同的内存，因此只分配 8 个字节，但是我的编译器的当前版本将分配完整的 16 个字节。

我的问题是，如何有效地在不同大小的内存中分配变量？

我正在尝试使用图形着色对寄存器分配进行研究/项目，我将在其中测试不同优化寄存器分配算法在不同场景中的效率。

我该如何开始？我可以测试它们的先决条件和依据是什么？我可以使用哪些算法？

加法：

我实际上想要一个快速的方法来解决这个问题，我没有做更深入的研究，但想（无耻地）向我的项目提交一个现成的分析，对“效率”有一点压力。即哪种类型的优化技术最适合不同的任务/编译器/解释器。

所以我的主要任务是（如何）在我的程序中实现寄存器分配。我在 Core2 Duo 机器上使用 64 位 Linux 系统。我知道 C、C++ 和 Java。

谢谢！

在 gcc 中内联汇编时，我发现自己经常不得不添加空的 asm 块以使变量在早期块中保持活动状态，例如：

另一个奇怪的例子是，下面的代码在没有优化的情况下工作得很好，但是使用 -O3 它会出现段错误：

我认为这与它使用了这么多寄存器有关。这里有什么我遗漏的东西，还是 gcc 内联汇编的寄存器分配真的有问题？

我制作了一些 ARM 内联汇编代码。
查看 Semaphore.s，我看到 gcc 对两个变量都使用寄存器 r3：“成功”和“更改”。我想知道我的约束是否有问题？
首先最相关的代码行：

asm 内联：

约束：

符号文件：

更多来源和生成的符号如下。

符号文件中的相关文本：

我正在尝试使用 SSE 或新的 AVX 指令为 Windows x64 目标编写一些计算密集型代码，在 GCC 4.5.2 和 4.6.1、MinGW64（TDM GCC 构建和一些自定义构建）中编译。我的编译器选项是-O3 -mavx. （-m64暗示）

简而言之，我想对 4 个打包浮点数的 3D 向量执行一些冗长的计算。这需要 4x3=12 xmm 或 ymm 寄存器用于存储，以及 2 或 3 个寄存器用于临时结果。恕我直言，这应该恰好适合 64 位目标可用的 16 个可用 SSE（或 AVX）寄存器。然而，GCC 产生了一个非常次优的带有寄存器溢出的代码，只使用寄存器xmm0-xmm10并将数据从堆栈中移入和移入堆栈。我的问题是：

有没有办法说服 GCC 使用所有的寄存器xmm0-xmm15？

要修正想法，请考虑以下 SSE 代码（仅用于说明）：

这里vect<__m128>只是简单的 a struct of 3 __m128，通过标量进行自然加法和乘法运算。当该行a2 -= v被注释掉时，即我们只需要 3x3 寄存器来存储，因为我们忽略a2了 ，生成的代码确实很简单，没有移动，一切都在寄存器中执行xmm0-xmm10。当我删除评论a2 -= v时，代码非常糟糕，寄存器和堆栈之间有很多改组。即使编译器可以只使用寄存器xmm11-xmm13或其他东西。

实际上，我还没有看到 GCCxmm11-xmm15在我的所有代码中的任何地方使用任何寄存器。我究竟做错了什么？我知道它们是被调用者保存的寄存器，但是通过简化循环代码，这种开销是完全合理的。