26

我目前正在为未来 8 周内完成的研究生级编译器课程选择一个项目。我想做一些与优化相关的事情，因为我以前在该领域工作不多，但该领域的任何事情都是公平的。

你做过的最有趣的编译器相关项目是什么？你从中学到最多的是什么？

编辑：谢谢大家的好建议。我很抱歉这么久没有更新这个。

我最终做的项目是在 LLVM 上进行简单的自动向量化优化。LLVM 有向量类型，但似乎没有任何方法可以在不支持前端的情况下利用它们。此优化将普通标量代码转换为矢量代码。

由于自动矢量化是一个相当难以实现的优化，我们尽可能地限制了我们的范围。首先，为了在代码中展示指令级并行性，我们寻找符合我们标准的单块循环，然后将它们展开特定次数，以便它们可以方便地向量化。然后，我们实现了Larsen 和 Amarasinghe在Exploiting Superword Level Parallelism with Multimedia Instruction Sets中提出的打包算法。

即使是这种优化的简化版本也相当复杂。有很多限制；例如，您不想向量化一个存在于循环之外的变量，因为程序的其余部分希望它是标量的。在过去的几周里，我们投入了很多时间。不过这个项目很有趣，我们学到了很多东西。

4

18 回答 18

13

在 8 周的时间范围内，您需要小心“范围蔓延”。那是不要太雄心勃勃，尤其是。如果这个项目包括编译器构造的其他方面（词法分析/解析），或者如果您仍在学习工具（调试器、yacc）和中间数据结构（DAG）。

也就是说，我的第一个建议是尝试一些实时变量分析。算法已经很成熟了，所以你几乎只需要针对你的数据结构等进行编码。

这将使您可以进行有限形式的死代码删除。也就是说，如果您检测到一个变量已声明但从未使用过，请不要为它分配空间。如果您检测到一个值已设置但从未读取，请不要生成该集合。

实时变量分析也可以帮助进行寄存器分配，因此如果有时间，您也可以解决这个问题，并且您应该能够重新使用为死代码删除构建的一些内容。

于 2008-10-08T18:16:48.923 回答
8

几年前，我为我公司生产的产品设计了一个 DSL 并编写了编译器。DSL 使用了声明性规则、事件驱动逻辑和组合继承的奇怪组合。这是一个非常有趣的项目，我学到了很多东西。

它真的激起了我对解析器和编译器的兴趣，所以我试图跟上编译器技术有趣的新发展。

关于优化，这是我去年读过的一篇有趣的文章：

http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf

在本文中，作者描述了一种自动发现窥视孔优化的技术（超过了几个流行的 C++ 编译器后端的性能），而无需专家编写一堆特殊情况的代码。他们的技术使用无监督学习算法来发现高价值的窥视孔替代品。

读完之后，我想到他们的方法可以通过为算法提供一个“机器描述”来增强，其中列出了目标处理器架构支持的所有指令（及其主要效果和副作用）。然后，求解器可以更容易地找到这些序列，而不是使用蛮力方法来找到等效的指令序列。

机器学习算法仍将使用经验观察来确定最有效的指令序列（因为缓存效果、微操作和流水线几乎需要经验时序数据），但可以使用代数定理证明器来预测结果等效性，操作机器说明。

在论文中，他们讨论了他们的优化器如何只能发现两个或三个指令的窥孔替换序列（因为否则，蛮力搜索将花费太长时间并消耗太多内存）。将智能求解器放在算法中的正确位置可以使其能够处理更长的替换序列。

Anyhoo...当你完成那个项目时告诉我！别忘了在“致谢”部分提及我！！;-)

于 2008-10-08T18:37:47.773 回答
7

我认为编写自己的简单嵌入式脚本语言是我做过的最有趣的编译器相关项目之一。它教会了我从设计到概念的整个过程的各个方面，并且由于我是从头开始做的，所以我可以根据需要将其变得简单或复杂，这使我能够在没有很多噪音的情况下理解概念，即修改已建立的项目可能有。

于 2008-10-08T17:33:27.107 回答
7

如果您对优化感兴趣，使用 SSE 和 MMX 指令集的循环向量化可能会很有趣。

于 2008-10-08T17:56:47.030 回答
5

对于学习编译器，端到端进行是最好的主意。使用简单的后端机器，而不是 x86，而是选择一些简单的机器，如准系统 MIPS。我的本科编译器项目针对的是 PDP-11 模拟器，这是一个很好的目标，因为它让事情变得非常简单。多亏了一些示例代码，我们可以在大约四个星期内完成一个简单的命令式语言编译器。在 C 中！

今天，有了像机器学习这样强大的语言，编译器应该会容易得多。

你做什么应该取决于你的兴趣。如果是优化，找到一些你需要关心的简单框架。

我认为今天最富有成果的领域是为线程目标编译或即时编译。

于 2008-10-08T17:53:44.820 回答
5

寻求帮助 Shed Skin 项目，该项目将 Python 编译为 C++。我想在夏天，有人发出求助电话。确定改进 C++ 编译的方法将为 python 程序提供惊人的优化！

http://code.google.com/p/shedskin/

于 2008-10-08T19:06:07.387 回答
4

我曾经写过一种编程语言和一个虚拟机来运行它。该语言能够与 16 位 Windows 上的 DLL（这是在 OLE 自动化之前）中包含的专门编写的函数进行接口。

从头到尾的整个过程让我对一门语言的两端都有了很好的理解。当时我读过各种编译器书籍（例如臭名昭​​著的 Dragon 书籍），但直到我写了一些具体的东西，它才真正沉入其中。现在，多年过去了，我所做的工作让我对 Java VM 和 CLR 等工作有了更丰富的认识和理解。

于 2008-10-08T17:43:57.710 回答
4

在我本科的编译器课程中，我们首先从头开始为类似 Pascal 的语言编写了一个递归下降（自上而下）解析器：词法分析器，解析器，一切。

大约在学期中途，我们转向了解析器/扫描器生成器，例如 lex/yacc 或 flex/bison。我们构建了一个编译器，它将我们的 Pascal 子集编译为我们给定的堆栈机器的汇编（堆栈机器非常简单，但原理仍然相同）。

如果您对编译器感兴趣，我不能高度推荐Dragon Book。它旨在用于 1 个学期的本科课程，下半部分用作研究生课程，涵盖了您可能希望的所有理论和优化。连乔尔都喜欢。=)

干杯

于 2008-10-08T18:04:40.350 回答
4

考虑现有动态类型语言的类型推断。

于 2008-10-08T18:08:47.363 回答
4

除了“龙书”的建议之外，我还强烈推荐 Steven S. Muchnick 的“Advanced Compiler Design & Implementation”，它侧重于中间表示、代码生成和优化技术。

于 2008-10-08T18:51:58.757 回答
3

这是另一个想法......虽然它仍然有点模糊：

大多数优化是在编译时完成的（除了在运行时优化的 JIT 编译器）。但是在链接时和安装时也有很多优化机会。

我对一个平台的想法特别感兴趣，在这个平台上你直到安装时才需要链接。但是在安装时链接过程中，您会采取积极的优化策略，因为您了解有关机器架构的大量详细信息，并且可以做出更微妙和更明智的优化决策。

于 2008-10-08T19:24:37.240 回答
2

循环检测和参数化展开应该足够困难以使其变得有趣。不是很性感，但在 8 周内变得太性感会让你沉沦。

于 2008-10-08T18:00:20.953 回答
2

您可以为 IronScheme 编写一个优化器，因为它目前可以很好地打击所有内容，除了一些“内在”功能。 :)

于 2008-10-08T18:26:49.713 回答
2

其他有趣的项目可能包括：

  • 向开源 Sun JVM 添加尾调用优化。

  • 将命名返回值优化 (NRVO) 添加到 Python 或 Ruby VM。

  • 为您最喜欢的目标添加即时正则表达式到字节码的编译（.Net 已经有了它。我很确定 Java 没有。）

于 2008-10-08T18:45:53.013 回答
2

虽然编写自己的语言是一项有趣且传统的学术活动，但已经有太多实施不佳的编译器相关项目。此外，8 周的时间不足以完成一个完整的语言实现。

如果您对“与优化相关的东西”感兴趣，请选择一种已经存在的语言或 VM，并针对性能、大小或两者进行优化。这将避免您不得不重新发明整个语言实现，让您专注于优化问题，将产生对其他人有用的产品，而不仅仅是另一个学术练习，甚至可以用于找工作。

我相信 Parrot 字节码解释器和各种 .Net Iron 语言解析器甚至可以从简单的优化中受益。

于 2008-10-08T18:49:35.020 回答
2

我在自己的教学中“早在何时”就做到了这一点。我不会像其他事情那样强调优化，比如类型推断或 JIT 或字节编码或对象格式/调试支持。

专注于优化并没有什么坏处，只要你也传达出它远没有人们想象的那么重要。仅在代码中很重要：

  • 在调用堆栈底部的紧密循环中运行（即没有显式或隐式调用函数）
  • 实际上占据了应用程序时间的很大一部分（即，如果代码很少运行，优化它不会有太大帮助）。

这只是编译器将看到的所有代码的一小部分。

编辑：可悲的是，我无法逃避使用 Fortran 编译器，它们无情地扰乱代码，使其非常难以调试，同时对性能产生 epsilon 影响。

于 2009-01-06T20:13:16.013 回答
1

使用启发式测试自动生成内联代码以权衡大小/速度。

于 2009-01-06T19:52:00.377 回答
0

B::CC perl 编译器将受益于添加和分析类型。我只是还没有足够的时间。

最近时间充裕。http://blogs.perl.org/users/rurban/2011/02/use-types.html

于 2010-10-22T01:35:21.190 回答