Search papers, labs, and topics across Lattice.
This paper introduces a novel approach to program optimization by representing e-graphs natively within a compiler's intermediate representation using MLIR, enabling equality saturation across multiple levels of abstraction. By creating a new MLIR dialect, eqsat, the authors facilitate the application of constructive compiler passes that maintain e-graph state throughout the compilation flow, addressing limitations of existing approaches that apply equality saturation at a single level or discard discovered equalities. Experiments demonstrate that this representation expands the scope of equality saturation, allowing interleaving of pattern rewriting with other compiler transformations within the same MLIR flow.
E-graphs, typically confined to isolated optimization steps, can now persist as a first-class citizen within the compiler's intermediate representation, unlocking broader and more flexible program optimization.
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.
ETH