The acyclic e-graph: Cranelift's mid-end optimizer
Summary
The post details Cranelift's acyclic e-graph (aegraph) and sea-of-nodes-with-CFG approach for the mid-end optimizer, describing canonicalization, rewrites, and eager-evaluation strategies. It discusses how lifting pure operators to a sea of nodes, hash-consing, and union nodes enable code motion, canonicalization, and rewrites to be performed in a unified framework, with evaluation showing a modest execution-time improvement and a small compile-time cost. It also outlines future directions and practical considerations for using e-graphs in a fast compiler.