Equality saturation: a new approach to optimization
Equality saturation: a new approach to optimization
复制标题
平等饱和：一种新的优化方法
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Sorin Lerner
中科院分区：
文献类型：
--
作者：
R. Tate;M. Stepp;Zachary Tatlock;Sorin Lerner
顺序应用传统编译器中的优化，每个优化都破坏性地修改了程序以产生转换的程序，然后将其传递给下一个优化。我们提出了一种构建编译器优化阶段的新方法。在我们的方法中，优化采用平等分析的形式，这些平等分析将平等信息添加到通用中间表示形式中。优化器通过反复应用这些分析来推断程序片段之间的等价来起作用，从而使中间表示饱和。饱和后，中间表示将编码输入程序的多个优化版本。在这一点上，盈利能力启发式选择了饱和代表中代表的各种程序的最终优化程序。我们提出的构建优化器的方法比以前的方法具有多种好处：我们的方法消除了担心优化订购的需要，可以使用全球优化的启发式启发式启发式，该启发式启发式启发式启发式启发式启发式，可以在完全优化的程序中进行选择，并可以用于执行翻译验证，验证，验证，即使在我们自己的编译器上也是如此。我们介绍我们的方法，形式化并描述我们选择中间表示的选择。我们还提出了实验结果，表明我们的方法在时间和空间方面是实用的，在发现复杂的优化机会方面有效，并且有效地对现实的优化器执行翻译验证。
Optimizations in a traditional compiler are applied sequentially, with each optimization destructively modifying the program to produce a transformed program that is then passed to the next optimization. We present a new approach for structuring the optimization phase of a compiler. In our approach, optimizations take the form of equality analyses that add equality information to a common intermediate representation. The optimizer works by repeatedly applying these analyses to infer equivalences between program fragments, thus saturating the intermediate representation with equalities. Once saturated, the intermediate representation encodes multiple optimized versions of the input program. At this point, a profitability heuristic picks the final optimized program from the various programs represented in the saturated representation. Our proposed way of structuring optimizers has a variety of benefits over previous approaches: our approach obviates the need to worry about optimization ordering, enables the use of a global optimization heuristic that selects among fully optimized programs, and can be used to perform translation validation, even on compilers other than our own. We present our approach, formalize it, and describe our choice of intermediate representation. We also present experimental results showing that our approach is practical in terms of time and space overhead, is effective at discovering intricate optimization opportunities, and is effective at performing translation validation for a realistic optimizer.