Cranelift/ISLE/e-graphs: Add better observability into the chain of rewrites that produced the expressions we actually extracted

[fitzgen]

In traditional peephole passes, it is easy to add logging for each rewrite you perform on the IR.

In e-graphs, we perform all possible rewrites, producing many equivalent expressions, and then afterwards extract just the best version. This means that logging each rewrite we perform will emit a bunch of largely irrelevant logs for expressions that we didn't ultimately extract. And by the time we do extraction, we no longer know which chain of rewrites produced that expression. This makes debugging a series of rewrites quite difficult.

We should figure out some way to improve things here.

Straw person idea:

• when adding an e-node to an e-class, record in a secondary map:

  • the id of the rewrite that produced that e-node
  • the e-node that was the input to that rewrite

• when printing clif, optionally use this secondary map to add annotation comments like

  ; Rewrite chain:
  ;   v97 = simplify(v96) rule at remat.isle:12
  ;   v120 = simplify(v97) rule at bitops.isle:283
  ;   v123 = simplify(v120) rule at cprop.isle:84 
  v123 = iadd v42, v36
  

We would probably only want to do this when a compile-time cargo feature is enabled. We could enable this feature for the filetests crate, but not be default in cranelift-codegen, so we could even write filetests that assert that certain rules we expect to chain together, do in fact chain together.

I think there were plans to add names to rules (maybe support for this even already landed in ISLE? can't remember) and we could use these names in the comments if they exist. That would be something that we could test for in the filetest directives, since we wouldn't want to include the source locations, as those would be too noisy for filetests when adding, removing, and tweaking rules.

But anyways, the filetest support is ultimately a secondary priority. I really just want to have better debugging of the e-graph rewrites.

cc @elliottt

[github-actions[bot]]

Subscribe to Label Action

cc @cfallin, @fitzgen

This issue or pull request has been labeled: "isle"

Thus the following users have been cc'd because of the following labels:

• cfallin: isle
• fitzgen: isle

To subscribe or unsubscribe from this label, edit the .github/subscribe-to-label.json configuration file.

Learn more.

[avanhatt]

FWIW, egg's "explanation" construct (and the paper they reference) might be a useful place to look for inspiration.

[avanhatt]

We also have code to name ISLE rules in the Crocus codebase, I can try to split that off as a separate PR soon.