有趣的编译器项目

我目前正在选择一个项目,以便在接下来的8周内完成毕业级编译器课程.我想做一些与优化相关的事情,因为我以前在那个领域没有多少工作,但是该领域的任何事情都是公平的.

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

编辑:谢谢大家的好建议.我很抱歉没有更新这个问题.

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

由于自动矢量化是一个相当难以实现的优化,因此我们尽可能地限制了我们的范围.首先,为了在代码中公开指令级并行性,我们寻找符合我们标准的单块循环,然后将它们展开特定次数,以便它们可以方便地进行矢量化.然后,我们实现了Larsen和Amarasinghe 在利用多媒体指令集开发超级词级并行中所规定的打包算法.

即使是这种优化的简化版本也非常复杂.有很多限制; 例如,您不希望对存在于循环之外的变量进行矢量化,因为程序的其余部分期望它是标量.我们在过去几周里花了很多时间.虽然这个项目很有趣,但我们学到了很多东西.

在8周的时间范围内,您需要注意"范围蔓延".这不是太野心勃勃,尤其是 如果这个项目包括编译器构造的其他方面(lexing/parsing),或者你还在学习工具(debugger,yacc)和中间数据结构(DAG).

也就是说,我的第一个建议是尝试一些实时变量分析.这些算法已经很好地建立了,所以你几乎只需要根据数据结构等编写代码.

这将允许您执行有限形式的死代码删除.也就是说,如果您检测到某个变量已声明但从未使用过,请不要为其分配空间.如果检测到某个值已设置但从未读取过,请不要生成该集.

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

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

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

关于优化,这是我去年读到的一篇有趣的文章:

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

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

阅读之后,我发现他们的方法可以通过为算法提供"机器描述"来增强,该"机器描述"列出目标处理器体系结构支持的所有指令(及其主要效果和副作用).然后,求解器可以更容易地找到这些序列,而不是使用强力方法来寻找等效的指令序列.

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

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

Anyhoo ...当你完成那个项目时告诉我!别忘了在"致谢"栏目中提及我!;-)

我认为编写自己的简单嵌入式脚本语言是我所做过的最有趣的编译器相关项目之一.它教会了我从设计到概念的过程的每个方面,因为我从头开始,我可以使它像我需要的那样简单或复杂,这使我能够理解具有大量噪音的概念,修改既定的项目可能有.

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

对于学习编译器,端到端的做法是最好的主意.使用一个简单的后端机器,而不是一个x86,而是选择一些简单的机器,如一个简单的MIPS.我完成了针对PDP-11模拟器的本科编译器项目,这是一个很好的目标,因为它使事情变得非常简单.感谢一些示例代码,我们可以在大约四周内完成一个简单的命令式语言编译器.在C!

今天,使用像ML这样强大的语言,编写编译器应该会容易得多.

你所做的应该真正取决于你的兴趣所在.如果它是在优化中,找到一些简单的框架,你需要关注的就是这些.

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