Rewrite rule inference using equality saturation
Rewrite rule inference using equality saturation
复制标题
DOI：
10.1145/3485496
复制
发表时间：
2021-08
影响因子：
--
通讯作者：
Chandrakana Nandi;Max Willsey;Amy Zhu;Y. Wang;Brett Saiki;Adam Anderson;Adriana Schulz;D. Grossman;Zach Tatlock
中科院分区：
文献类型：
--
作者：
Chandrakana Nandi;Max Willsey;Amy Zhu;Y. Wang;Brett Saiki;Adam Anderson;Adriana Schulz;D. Grossman;Zach Tatlock
许多编译器，合成器和定理都证明了重写规则来简化表达式或证明等效的规则。大型规则集也可以挑战应用：冗余规则降低了基于规则的搜索并挫败了调试，探讨了平等满意度，这是一种有前途的技术，该技术使用电子图表应用重写规则，也可以用于推断重写规则。 e-Graphs可以紧凑地代表枚举的大量列表，我们表明，相等性饱和度有效地缩小了这两个集合，从而使较小的，更一般的规则构成了更快的综合对于基于CVC4建造的类似工具，标尺合成了5.8×较小的规则集25×速度，而在端到端的案例研究中，均不受证明的能力。并在流行的开源工具中解决了一个长期存在的问题。
Many compilers, synthesizers, and theorem provers rely on rewrite rules to simplify expressions or prove equivalences. Developing rewrite rules can be difficult: rules may be subtly incorrect, profitable rules are easy to miss, and rulesets must be rechecked or extended whenever semantics are tweaked. Large rulesets can also be challenging to apply: redundant rules slow down rule-based search and frustrate debugging. This paper explores how equality saturation, a promising technique that uses e-graphs to apply rewrite rules, can also be used to infer rewrite rules. E-graphs can compactly represent the exponentially large sets of enumerated terms and potential rewrite rules. We show that equality saturation efficiently shrinks both sets, leading to faster synthesis of smaller, more general rulesets. We prototyped these strategies in a tool dubbed Ruler. Compared to a similar tool built on CVC4, Ruler synthesizes 5.8× smaller rulesets 25× faster without compromising on proving power. In an end-to-end case study, we show Ruler-synthesized rules which perform as well as those crafted by domain experts, and addressed a longstanding issue in a popular open source tool.