Efficient Extraction for Effectful E-graphs
Summary
Researchers introduce statewalk DP, a new extraction algorithm for effectful e-graphs that enforces effect ordering without external solvers. The paper proves NP-completeness for finding any effect-safe extraction but shows tractability with a small statewalk width, delivering substantial speedups over ILP and competitive results with LLVM. Implemented in eggcc for imperative Bril programs, this work reduces the extraction bottleneck in compiler pipelines.