egg: Fast and extensible equality saturation
Authors:
Top Cited Papers
Open Access
- 4 January 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 5 (POPL) , 1-29
Abstract
An e-graph efficiently represents a congruence relation over many expressions. Although they were originally developed in the late 1970s for use in automated theorem provers, a more recent technique known as equality saturation repurposes e-graphs to implement state-of-the-art, rewrite-driven compiler optimizations and program synthesizers. However, e-graphs remain unspecialized for this newer use case. Equality saturation workloads exhibit distinct characteristics and often require ad-hoc e-graph extensions to incorporate transformations beyond purely syntactic rewrites. This work contributes two techniques that make e-graphs fast and extensible, specializing them to equality saturation. A new amortized invariant restoration technique called rebuilding takes advantage of equality saturation's distinct workload, providing asymptotic speedups over current techniques in practice. A general mechanism called e-class analyses integrates domain-specific analyses into the e-graph, reducing the need for ad hoc manipulation. We implemented these techniques in a new open-source library called egg. Our case studies on three previously published applications of equality saturation highlight how egg's performance and flexibility enable state-of-the-art results across diverse domains.Keywords
All Related Versions
Funding Information
- National Science Foundation (1813166,1749570)
This publication has 25 references indexed in Scilit:
- Z3: An Efficient SMT Solver2008
- Simplify: a theorem prover for program checkingJournal of the ACM, 2005
- Proof-Producing Congruence Closure2005
- Compiling language definitionsACM Transactions on Programming Languages and Systems, 2002
- DenaliACM SIGPLAN Notices, 2002
- A taste of rewrite systems1993
- Variations on the Common Subexpression ProblemJournal of the ACM, 1980
- Fast Decision Procedures Based on Congruence ClosureJournal of the ACM, 1980
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960