jameysharp requested cfallin for a review on PR #7968.
jameysharp opened PR #7968 from jameysharp:egraph-chaos
to bytecodealliance:main
:
First of all, thread a "chaos mode" control-plane into Context::optimize and from there into EgraphPass, OptimizeCtx, and Elaborator.
In this commit we use the control-plane to change the following behaviors in ways which shouldn't cause incorrect results:
- Dominator-tree block traversal order for both the rule application and elaboration passes
- Order of evaluating optimization alternatives from
simplify
- Choose worst values instead of best in each eclass
@lpereira and I wrote this together.
jameysharp requested wasmtime-fuzz-reviewers for a review on PR #7968.
jameysharp requested wasmtime-compiler-reviewers for a review on PR #7968.
jameysharp requested alexcrichton for a review on PR #7968.
alexcrichton commented on PR #7968:
I don't think I'm qualified to review this (deferring to @cfallin tagged here as well), but nevertheless I wanted to ask a question about this as well:
Choose worst values instead of best in each eclass
From the discussion in the recent egraph issue I thought we settled on the opposite conclusion, that the minimum value must be chosen. I suspect though you've already considered that and it's already accounted for here, leading me to my question. I suspect my understanding of the outcome of that discussion is probably no longer accurate, so is there a tl;dr; or why that issue won't resurface if we choose any value within an eclass? (if there's not a tl;dr; that's also totally ok, happy to go hunting elsewhere too!)
cfallin submitted PR review:
Thanks a bunch for tackling this; hopefully it helps us validate things!
cfallin submitted PR review:
Thanks a bunch for tackling this; hopefully it helps us validate things!
cfallin created PR review comment:
I wonder if there' a way to encapsulte this? I realize it's a bit tricky because the order relation actually changes based on
use_worst
(reserved values come "last" when picking mins, and "first" when picking maxes). Maybe something likepick_non_reserved_with_cmp(|x, y| x <= y)
or something like that, thenpicked_non_reserved_with_cmp
takes two(Cost, Value)
tuples and has the if-ladder?Maybe that's just the same complexity as before, I dunno; just code-golfing a bit to see if we can make it prettier :-)
cfallin edited PR review comment.
lpereira submitted PR review.
lpereira created PR review comment:
We discussed this briefly while writing, and decided on this as it's more explicit and it's used only here.
jameysharp commented on PR #7968:
Yeah, that's absolutely a fair question, @alexcrichton. In ongoing discussion we're currently thinking that we need to establish an invariant that it is always correct to choose any value from an eclass. We should only use the cost function to indicate a preference for some values over others, not to encode correctness constraints.
So this PR is part of checking that we've done that correctly. I believe that with #7879 we currently have this invariant, but it's currently fragile because it relies on rewrite-rule authors strictly following new guidelines about using
subsume
. In #7891, we've been discussing how to better enforce the invariant.
jameysharp commented on PR #7968:
I've been running the cranelift-fuzzgen on this branch locally for over an hour without finding any failures, so that's a good start.
Also I forced
use_worst
totrue
in the cost function and ran the filetests. Several egraph tests and precise-output compile tests failed due to selecting longer sequences of instructions, which is what I would hope would happen. Other than that, everything passed, which is also reassuring.
jameysharp merged PR #7968.
Last updated: Dec 23 2024 at 12:05 UTC