问题标签 [compiler-theory]

在几个哈希表实现中，我已经看到对存储桶中的项目使用诸如“转置”或“移到前面”之类的启发式方法。

1. 使用这种启发式方法有什么好处？我自己想不通。
2. 可以在哈希表/存储桶级别进行哪些其他优化，为什么以及在什么情况下？

请先优化散列函数。

我正在寻找一种将局部变量分配给寄存器的方法。我知道有几种严肃的方法可以做到这一点（即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.

我正在编写一个玩具编译器，如果结果仅取决于参数的值，它可以优化函数调用。所以像 xor 和 concatenate 这样的函数只依赖于它们的输入，用相同的输入调用它们总是给出相同的输出。但是像 time 和 rand 这样的函数依赖于“隐藏”的程序状态，使用相同的输入调用它们可能会产生不同的输出。我只是想弄清楚区分这两种功能的形容词是什么，例如“同构”或“可重入”之类的。有人能告诉我我要找的词吗？

我正在使用 Kenneth Louden 的 Compiler Construction 书，但它缺少示例，而且说明如何进行的规则真的很难遵循。我不确定如何进入 LR(1) 状态。此外，不知道如何从 LR(1) 状态转到 LALR(1) 状态。

例如，这些 LR(1) 状态：

我了解“S -> .XX, $”是如何到达那里的，但接下来看看“X -> .aX, a/b”。为什么 $ 不是其中的一部分？它不是从一个有 $ 的规则生成的，所以它不是必须有一个 $ 吗？a/b是怎么出现的？根据这本书，如果 A -> alpha.Bgama,a 和 B 是非终结符，则 B -> .beta, b 为每个 B -> beta 添加 b 在第一个（gamaalpha）中。所以，据我了解：

S -> .XX, $ and X -> aX and X -> b => X -> aX, $ and X -> b, $
X -> .aX, $ and X -> b, $ => 没有任何反应
A -> .a, $ => 没有任何反应

但鉴于上面的例子，这似乎完全错误。

即将到来的夏天，我希望开始写我的硕士论文，我一直在忙着寻找论文主题。我现在有一个我感兴趣的主题池，最让我印象深刻的是为微型 C 编译器（图形着色或线性扫描）实现全局寄存器分配器。

所以我想顺便问一下你们中是否有人做过这个，这对于硕士论文是否可行，或者是否太难了。如果您能指导我阅读有关该主题的任何优秀文献，我也会非常高兴（我已经有了龙书）。

为了好玩而努力：http ://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/

可空值的计算示例首先使用定点计算。（见第 3.8 节）

我在 Scheme 中做事并且非常依赖递归。

如果您尝试实现可为空的或首先通过递归实现，那么很明显您将在像这样的生产中无限地重复

N -> N a b

其中 N 是非终结符，a,b 是终结符。

这是否可以通过维护一组在生产规则左侧看到的非终结符递归地解决，并在我们考虑它们一次后忽略它们？

这似乎适用于可为空的。先说什么呢？

编辑：这是我从玩耍中学到的。源代码链接在底部。

非终结符在 first 的计算中不能被忽略，除非它们可以为空。

考虑：

在这里我们可以忽略N，N a因为它可以N为空。我们可以替换N -> N a为N -> a并推断它a是 的成员first(N)。

在这里我们不能忽视N：

如果我们忽略Nin，N -> N a我们会推断出a哪个first(N)是假的。相反，我们看到 N 不可为空，因此在首先计算时，我们可以省略任何N在 RHS 中作为第一个符号找到的产生式。

这产生：

这告诉我们b在first(N).

源代码： http: //gist.github.com/287069

所以……这听起来好吗？

我对向导书都很熟悉：

计算机程序的结构和解释

和龙书：

编译器：原理技术和工具

但是，我很想知道还有哪些经典的学术教科书人们会认为是程序员的必备读物。

函数的返回值通常存储在堆栈或寄存器中。但是对于大型结构，它必须在堆栈上。这段代码在真正的编译器中必须进行多少复制？还是优化了？

例如：

（假设函数不能内联..）

越位语言是一种

...该语言中声明（块）的范围由它们的缩进表示。

此类语言的示例包括 Python、Boo、Nemerle、YAML 等等。

所以我的问题是：我如何真正解析这些？如何解决制表符与空格的问题（两个制表符或 8 个空格是否等效）？解析器生成器在这里有什么帮助吗，还是我必须自己手动编写词法分析器/解析器？

首先看看下面的代码（在这个代码中shape是基类，line是派生类）

当我们编译这个程序时，首先会调用 shape 的 draw 方法，然后程序终止。为什么它终止？为什么我们不能在没有基类指针或引用的情况下实现多态性这是什么技术原因？如果我们试图用对象数组实现多态性，编译器会做什么？请通过示例以易于理解的方式进行解释。我将非常感激。