Stream: git-wasmtime

Topic: wasmtime / PR #4909 Add the aegraph (acyclic e-graph) imp...

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 00:43):

cfallin opened PR #4909 from aegraph-crate to main:

This PR introduces the implementation of the aegraph data structure itself, as a new crate (cranelift-egraph).

This does not include any of the Cranelift-specific use of the aegraph (language/node definitions, egraph building, and lowering out of the egraph), nor any of the rule-rewriting on the egraph. That will come in subsequent PRs.

Stacks on top of #4908.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 00:43):

cfallin requested fitzgen for a review on PR #4909.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 02:56):

cfallin updated PR #4909 from aegraph-crate to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

I don't think NullCtx itself needs to be parameterized by V, just the CtxEq impl block.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

The thing that still isn't 100% clear to me, and I'd love an example of, is what kinds of expressions ae-graphs fail to fully optimize to the degree that e-graphs can.

I guess if you initially have this

class1

+-----------------+
| class 2         |
|                 |
| popcnt(class 1) |
+-----------------+

class 3

and then later add something to class 3 that allows you to realize you can merge it with class 1, that merging won't happen in an ae-graph but would in a traditional e-graph?

Or is it that the e-classes will still merge into a new, merged e-class, but the popcnt(class 1) node won't be updated to reference union(class 1, class 3) and so any optimization that relied on that (like say if class 3 contained a constant and we could const fold the popcnt) wouldn't trigger?

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

This should probably use a custom macro that we can make a true no-op unless a cargo feature is enabled, similar to what we did elsewhere in cranelift.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

Are these ListPool changes actually used? I don't see any uses...

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

Can self.parent just be a SecondaryMap?

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

If I'm reading this correctly, then an e-class containing n nodes will have O(n) "pointer" chases to enumerate its e-nodes? I suppose that is fine for small e-classes, and maybe most are small, but we might want to investigate those e-node counts in the future and maybe have a variant for when there are a bunch of e-nodes in an e-class that stores them together in a single contiguous region of memory. Or use HAMTs or something.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

nitpick: Missing [1] definition

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

Also, I kinda feel like the egraph module could just be in this file, since it is nearly empty as-is, and the egraph module's doc comment is much more useful than this one. I think those docs could just supplant these.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 14 2022 at 22:34):

fitzgen created PR review comment:

Should probably be called dedupe to match std::vec::Vec::dedupe

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:20):

cfallin updated PR #4909 from aegraph-crate to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:20):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:20):

cfallin created PR review comment:

Updated, thanks!

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:20):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:20):

cfallin created PR review comment:

I added a section to the doc-comment to address this; but in brief, yep, it's basically the example that you give.

It's pretty subtle though, as this only matters if the rewrite from class3 to class1 exists and if class3 is cheaper. In other words, if a rewrite takes a cheaper expression and rewrites it into a more expensive expression. Then it may happen to intern with an existing copy of that more expensive expression and union the cheaper version into it. That seems unlikely for the sorts of optimizations we plan to write. In the fullness of time this would still be a good question to investigate further, though!

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin created PR review comment:

Done!

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin created PR review comment:

Done -- everything is in lib.rs now.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin created PR review comment:

Yep, that makes things a lot cleaner -- thanks!

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin created PR review comment:

Ah, these changes are actually associated with another patch in the series -- the cranelift-codegen-side egraph glue uses them. I'll pull them out of this patch, thanks.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin created PR review comment:

(Removed as per above.)

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:21):

cfallin created PR review comment:

Yep, that's a reasonable optimization, I agree. In practice it didn't seem to matter for the benchmarks I was looking at but it's something to keep an eye on in the future.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 19 2022 at 23:37):

cfallin updated PR #4909 from aegraph-crate to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 20 2022 at 00:30):

cfallin updated PR #4909 from aegraph-crate to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 20 2022 at 00:45):

cfallin updated PR #4909 from aegraph-crate to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 23:42):

cfallin updated PR #4909 from aegraph-crate to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 23:43):

cfallin has enabled auto merge for PR #4909.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 22 2022 at 00:33):

cfallin merged PR #4909.

Last updated: Dec 23 2024 at 12:05 UTC