@cfallin @mwillsey @ztatlock Okay, the slides were definitely also informative by themselves.

One thing I struggled with when I tried to read the previous materials about acyclic e-graphs (mostly the cranelift RFC), is how you can avoid rebuilding the congruence closure without having to arbitrarily pick one of the representatives for the hash-consing table in some rare situations. I think I got it now, though.

If I understand correctly:

• you do away with any invariants of the form “the hash-consing table always refers to the latest version of an e-class”
• instead, you have the invariant that the hash-consing table points to the version of the e-class that includes exactly those nodes that would’ve been rediscovered if you re-ran the rewrites from scratch on this particular representation
  • there is one exception to this: rules like (sub x x) => 0 can use information from the union-find that has been discovered “accidentally” when simplifying earlier expressions
• you continue maintaining the union-find data structure like a traditional e-graph, but you avoid ever looking anything up by the canonical id assigned by the union-find, instead only ever checking whether two particular nodes are equivalent

Does this sound right? If so, it is interesting how you recovered some of the directionality of the rewrites that e-graphs usually lack.

Also, have you considered the possibility of some limited normalization on the e-nodes before looking them up in the hash-cons? I’m mostly thinking of stuff like: for commutative operators, make sure the LHS has a lower e-class id. This seems like a good way of merging a + b with b + a without having to introduce full commutativity into the rewrites.