There has been significant interest in the e-graph approach to optimization in recent years, for good reason: an e-graph with rewrite rules serves as a unifying framework and can produce better code by composing optimizations more effectively. However, most of this recent interest has arisen amongst compilers that are special in one way or another: no control-flow graph, or else compiling a domain-specific language only, or targeting a non-traditional architecture, or else able to spend significant compute time during compilation, et cetera. The toolbox of techniques for efficient and effective e-graph-based compilation has grown considerably, but until recently was not sufficient for a traditional compiler accepting arbitrary code with tight compile-time requirements.

Cranelift is a modern general-purpose compiler that accepts an SSA-based IR and generates machine code. It is in use in production in industry to compile untrusted WebAssembly modules, and so has rigorous correctness and reliability requirements. It has a unique focus on verifiability, which has led to use of rewrite rules to express instruction lowerings. In addition, it needs to achieve JIT-class compile times, which it does by performing a core set of key optimizations only.

We decided in 2022 to rearchitect Cranelift’s mid-end to use an e-graph representation. This solved a pre-existing pass-ordering problem, and provided us an architecture to use our rewrite-rule DSL for mid-end optimizations as well. In the process, we had to solve a number of problems: representing control flow and translating between an e-graph and a CFG, applying rewrites efficiently, avoiding blow-ups in memory or time, and ideally avoiding a fix-point loop or cascading merge step. Our novel “acyclic e-graph” approach replaces all of our separate machine-independent optimization passes, does GVN, LICM, and rematerialization “for free” during translation to/from the e-graph, and takes only a few linear passes over the code. This talk will describe the problems and our solutions, and will discuss the tradeoffs and caveats to our approach.

Principal software engineer at Fastly, interested in compilers and runtimes. I work on the Cranelift compiler and related infrastructure.