Hacker News Reader

Comment by convolvatron | Hacker News Reader

I've tried to look into this a couple times, including today. To me this looks alot like unification? but I don't really understand how operationally one gets from equivalence classes to instructions. is there an e-graphs for dummies writeup?

View on HN

The approach that Cranelift uses is what we call the "aegraph" (talk I gave about it: slides https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf, video https://vimeo.com/843540328). The basic idea is that eclasses hold sets of operator expressions (think sea-of-node IR), and we keep that alongside the CFG with a "skeleton" of side-effecting ops. We build that, do rewrites, then extract out of it back to a conventional CFG-of-basic-blocks for lowering. The "equivalence" part comes in when doing rewrites: the main difference between an egraph and a conventional sea-of-nodes IR with rewrite rules is that one keeps all representations in the equivalence class around, then chooses the best one later.

We had to solve a few novel problems in working out how to handle control flow, and we're still polishing off some rough edges (search recent issues in the repo for egraphs); but we're mostly happy how it turned out!

(Disclosure: tech lead of CL for a while; the e-graphs optimizer is "my fault")

If by instructions you mean machine instructions, you don't; it's used for internal optimization passes only.

that helps, so this is really an alternative to pushing analysis attributes aronud a dataflow graph

Reply on news.ycombinator.com