E-Graphs as a Persistent Compiler Abstraction
2026-02-18 • Programming Languages
Programming Languages
AI summaryⓘ
The authors present a new way to use equality saturation, a method to optimize code by recognizing many equivalent forms, directly within a compiler's intermediate steps instead of as a separate tool. They built this approach on a Python-based framework called xDSL by creating a special component named eqsat that keeps track of these equalities as code is transformed. This lets the compiler apply equality saturation alongside other code changes, improving flexibility and coverage during optimization. Their work shows how this integrated approach can help compilers handle multiple levels of code representation all at once.
Equality SaturationCompiler OptimizationIntermediate RepresentationE-graphMLIRxDSLPattern RewritingPhase-Ordering ProblemDialect
Authors
Jules Merckx, Alexandre Lopoukhine, Samuel Coward, Jianyi Cheng, Bjorn De Sutter, Tobias Grosser
Abstract
Recent algorithmic advances have made equality saturation an appealing approach to program optimization because it avoids the phase-ordering problem. Existing work uses external equality saturation libraries, or custom implementations that are deeply tied to the specific application. However, these works only apply equality saturation at a single level of abstraction, or discard the discovered equalities when code is transformed by other compiler passes. We propose an alternative approach that represents an e-graph natively in the compiler's intermediate representation, facilitating the application of constructive compiler passes that maintain the e-graph state throughout the compilation flow. We build on a Python-based MLIR framework, xDSL, and introduce a new MLIR dialect, eqsat, that represents e-graphs in MLIR code. We show that this representation expands the scope of equality saturation in the compiler, allowing us to interleave pattern rewriting with other compiler transformations. The eqsat dialect provides a unified abstraction for compilers to utilize equality saturation across various levels of intermediate representations concurrently within the same MLIR flow.