Back to search

University of Washington

Practical and Flexible Equality Saturation

Abstract

dc:description.abstract

Programming language tools like compilers, optimizers, verifiers, and synthesizers rely on term rewriting to effectively manipulate programs. While powerful and well-studied, term rewriting traditionally suffers from a critical stumbling block: users must choose when and how to apply the right rewrite, and the quality of the results hinges on this difficult decision. A recent technique called equality saturation mitigates this “rewrite choice” issue by allowing many rewrites to apply simultaneously. Despite its promise, the technique’s applicability has been limited by lack of flexibility and poor scalability. This thesis offers theoretical and practical advances that make equality saturation fast and flexible enough to use in real-world applications in any domain. On the theoretical side, this work contributes two techniques to make e-graphs, the data structure underlying equality saturation, better suited to the algorithm’s needs. 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. egg has been used to achieve state-of-the-art results in many domains, including floating point accuracy, automatic vectorization, deep learning compute graphs, 3D CAD decompilation, and linear algebra kernels, among others. We present case studies that highlight how egg’s performance and flexibility helped these projects succeed, making the case that equality saturation is ready for a wide variety of real-world use cases.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Willsey, Max
Advisor dc:contributor.advisor
  • Ceze, Luis

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • CC BY
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1773/47423

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Willsey, Max. Practical and Flexible Equality Saturation. 2021. http://hdl.handle.net/1773/47423