Wasmtime GitHub notifications bot (Apr 14 2025 at 23:33): Wasmtime GitHub notifications bot (Apr 14 2025 at 23:33):cfallin opened PR #10579 from cfallin:fix-isle-2 to bytecodealliance:main:
This arrived as a fuzzbug [1] with some very interesting optimization behavior. The test case has sequences of
(select _ x x)operators -- that is, conditional selects with both inputs the same -- that are chained together sequentially. A few aspects of the egraph framework and our optimization rules conspired to create exponential blowup:
We have a rewrite rule for
(select _ x x) -> x, but we do not subsume; this means that we create an eclass for both. This in itself is not a problem; however...We have some other rules that look through the inputs to the select to detect other cases (e.g.: select between constants 1 and 0, or 0 and 0, or ...), so we traverse both inputs;
And we also do nested rewrites, so when the rewrite rule for
(select _ x x) -> xfires, and thexis itself another select in a long chain of selects, we traverse all possible paths (through first or second args) to the roots. In effect we get an eclass that has the ultimate root and then 2^n combinations ofselectnodes on top of that.This got worse with the recent change to canonicalize less (for simpler/cheaper compilation), hence the fuzzbug timeouts.
This PR includes a few fixes, all complementary to each other:
The
(select _ x x) -> xrule now subsumes; this is another case where we have a strictly better rewrite and so we should short-circuit the eclass blowup.The rewrite runner sorts and dedups returned value numbers; in debugging the above I noticed we were getting two rules producing the same rewritten value and we were adding the same value twice with two union nodes.
The rewriter keeps a total eclass size per root and limits the total eclass size to a fixed limit (currently 5). We thus now have limits in three different axes: depth of eager rewrites (5); number of returned matches (also 5); and total size of eclass (5). The first two don't necessarily imply the third because we otherwise can keep unioning on top of an eclass and (as seen above) see exponential blowup.
[1]: https://oss-fuzz.com/testcase-detail/4806924172591104
<!--
Please make sure you include the following information:
If this work has been discussed elsewhere, please include a link to that
conversation. If it was discussed in an issue, just mention "issue #...".Explain why this change is needed. If the details are in an issue already,
this can be brief.Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.htmlPlease ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->
Wasmtime GitHub notifications bot (Apr 14 2025 at 23:33):cfallin requested fitzgen for a review on PR #10579.
Wasmtime GitHub notifications bot (Apr 14 2025 at 23:33):cfallin requested wasmtime-compiler-reviewers for a review on PR #10579.
Wasmtime GitHub notifications bot (Apr 14 2025 at 23:33):cfallin requested wasmtime-core-reviewers for a review on PR #10579.
Wasmtime GitHub notifications bot (Apr 15 2025 at 02:17):github-actions[bot] commented on PR #10579:
Subscribe to Label Action
cc @cfallin, @fitzgen
<details>
This issue or pull request has been labeled: "cranelift", "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 <code>.github/subscribe-to-label.json</code> configuration file.
Learn more.
</details>
Wasmtime GitHub notifications bot (Apr 15 2025 at 16:30):fitzgen submitted PR review.
Wasmtime GitHub notifications bot (Apr 15 2025 at 16:52):fitzgen merged PR #10579.
Last updated: Dec 06 2025 at 06:05 UTC