有趣的编译器项目

Question

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

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

编辑：谢谢大家的好建议。我很抱歉这么长时间没有更新这篇文章。

我最后做的项目是LLVM上的一个简单的自动矢量化优化。LLVM有向量类型，但是如果不支持前端，似乎没有任何方法来利用它们。这种优化将普通标量码转换为矢量码。

由于自动矢量化是一个相当困难的优化实现，我们尽量限制我们的范围。首先，为了在代码中公开指令级并行性，我们寻找符合我们标准的一个块循环，然后将它们展开特定的次数，这样它们就可以方便地进行矢量化。然后，我们实现了由Larsen和Amarasinghe在利用多媒体指令集开发超级字级并行性中布局的包装算法。

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

Answer 1

如果您对优化感兴趣，那么使用SSE和MMX指令集对循环进行矢量化可能会很有趣。

Answer 2

有了8周的时间框架，你将需要小心“范围爬行”。不要太雄心勃勃(尤指)。如果这个项目包括编译器构造的其他方面(词法/解析)，或者你还在学习工具(调试器，yacc)和中间数据结构(DAG)。

也就是说，我的第一个建议是尝试一些动态变量分析。算法已经相当成熟，所以您只需将其编码到特定于您的数据结构，等等。

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

也可以帮助注册分配，所以如果有时间的话，您也可以处理这个问题，并且您应该能够重用一些为删除死代码而构建的内容。

Answer 3

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

它确实激发了我对解析器和编译器的兴趣，所以我一直在努力跟上编译器技术方面有趣的新发展。

关于优化，下面是我去年读到的一篇有趣的文章：

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

本文描述了一种在不需要专家编写一组特例代码的情况下自动发现窥视孔优化(超过几种流行的C++编译器后端的性能)的技术。他们的技术使用无监督的学习算法来发现高值的窥视孔替代物。

在阅读了它之后，我意识到他们的方法可以通过向算法提供一个“机器描述”来增强，它列出了目标处理器体系结构支持的所有指令(包括它们的主要效果和副作用)。然后，求解者可以更容易地找到这些序列，而不是使用蛮力的方法来寻找等价的指令序列。

机器学习算法仍将使用经验观测来确定最有效的指令序列(因为缓存效应、微操作和流水线几乎需要经验定时数据)，但结果等价性可以使用代数定理验证器来预测，并在机器描述的基础上操作。

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

总之..。当你完成那个项目的时候告诉我！别忘了在你的“感谢”一节中提到我！