Exploring the Acyclic E-Graph in Cranelift's Optimizer

In this article, I delve into the concept of the aegraph, or acyclic e-graph, which is central to Cranelift's mid-end optimizer. Since its introduction in 2022, the aegraph has undergone significant evolution, including a full rewrite and numerous discussions within the e-graph community. The aim is to explain why we use e-graphs, how we overcame challenges like full equality saturation, and how we made this approach efficient enough for production in Cranelift.

## Initial Context: Fixpoint Loops and Pass-Ordering

In 2022, I introduced alias analysis and related optimizations in Cranelift, which led to performance improvements but also raised questions about integrating these optimizations with existing passes like GVN and LICM. This challenge, known as the pass-ordering problem, required a unified framework to interleave optimizations more effectively.

## Three Building Blocks

We categorize optimizations into three types: rewrites, code motion, and canonicalization. Code motion involves moving computations without changing them, canonicalization merges identical computations, and rewrites replace expressions with equivalent ones. These categories help us build a framework for simple optimizations.

## Sea-of-Nodes IR

The sea-of-nodes IR eliminates the sequential order of instructions, creating a graph of operators with edges denoting dependencies. This approach allows us to unify code motion, canonicalization, and rewrites. By keeping the CFG for side-effectful instructions and using a sea-of-nodes for the rest, we can optimize pure operators efficiently.

## Implementing Sea-of-Nodes-with-CFG

To implement this in Cranelift, we lift pure operators out of the CFG, deduplicate them, perform rewrites, and convert back to sequential IR. This process, called elaboration, ensures efficient optimization by computing values only once and reusing them where possible.

## Optimizing Pure Expression Nodes

We use a rewrite framework to apply algebraic and other rewrites to the sea-of-nodes. By pattern-matching and replacing expressions, we achieve optimizations like GVN, DCE, LICM, and rematerialization.

## E-graphs: Representing Many Possible Rewrites

E-graphs allow us to represent many equivalent forms of a program simultaneously. This approach, known as equality saturation, enables us to explore a vast space of possible optimizations and choose the best representation based on a cost metric.

## Practical Efficiency and Challenges

Classical e-graphs face challenges like blowup and inefficiency. To address these, we redefine the existing IR into an implicit e-graph, avoiding data movement and leveraging union nodes to represent e-classes. Eager rewriting ensures acyclicity and efficient optimization.

## Evaluation and Future Directions

Our evaluation shows that while aegraphs improve code quality, their multi-value representation doesn't significantly impact performance. Future work includes exploring better extraction algorithms and handling more complex rewrites. Despite the challenges, aegraphs offer a promising framework for optimizing Cranelift's mid-end.