Efficient Extraction for Effectful E-graphs

Abstract

E-graphs have enabled recent advances in program optimization, synthesis, and verification, yet remain difficult to apply to effectful programs whose memory and I/O operations must respect execution order. Existing effect-aware extraction algorithms rely on integer linear programming (ILP) and dominate total runtime. We introduce statewalk DP, a new extraction algorithm that enforces effect ordering efficiently without external solvers. We prove that finding any effect-safe extraction is NP-complete, but show that statewalk DP is tractable in statewalk width, a parameter that measures the complexity of dataflow interactions among effects. In practice, statewalk width generally remains small, enabling statewalk DP to achieve order-of-magnitude speedups over ILP extraction while producing programs comparable to LLVM across our benchmarks. We implement the algorithm in eggcc, a prototype e-graph-based compiler for imperative Bril programs, and demonstrate that effect-aware extraction is no longer a bottleneck.

BibTeX

@article{2026-oopsla-eggcc,
  author     = {Flatt, Oliver and Pal, Anjali and Zhang, Yihong and Tjoa, Ryan and Graham, Kirsten and Fischman, Alex and Nandi, Chandrakana and Rosenthal, Eli and Tatlock, Zachary and Ni, Haobin},
  title      = {Efficient Extraction for Effectful E-graphs},
  year       = {2026},
  month      = oct,
  journal    = {Proceedings of the ACM on Programming Languages},
  volume     = {10},
  number     = {OOPSLA2},
  articleno  = {398},
  numpages   = {28},
  publisher  = {Association for Computing Machinery},
  url        = {https://doi.org/10.1145/3839530},
  doi        = {10.1145/3839530}
}

📝 publications index