E-Graphs as a Persistent Compiler Abstraction
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908839993933824 |
|---|---|
| author | Merckx, Jules Lopoukhine, Alexandre Coward, Samuel Cheng, Jianyi De Sutter, Bjorn Grosser, Tobias |
| author_facet | Merckx, Jules Lopoukhine, Alexandre Coward, Samuel Cheng, Jianyi De Sutter, Bjorn Grosser, Tobias |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_16707 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | E-Graphs as a Persistent Compiler Abstraction Merckx, Jules Lopoukhine, Alexandre Coward, Samuel Cheng, Jianyi De Sutter, Bjorn Grosser, Tobias Programming Languages 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. |
| title | E-Graphs as a Persistent Compiler Abstraction |
| topic | Programming Languages |
| url | https://arxiv.org/abs/2602.16707 |