Stream: git-wasmtime

Topic: wasmtime / PR #13081 Cranelift: revert rules added in #12...

Wasmtime GitHub notifications bot (Apr 13 2026 at 20:47):

cfallin requested alexcrichton for a review on PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 20:47):

cfallin opened PR #13081 from cfallin:revert-12926 to bytecodealliance:main:

These rules appear to be correct, but for an as-yet-undiagnosed reason, cause rewrite blowups. The proper fix is probably to use subsume but I'd like for us to bottom out why the blowup is happening first (cc @myunbin).

In the meantime, this removes the rules so we get back to a workable state on main. Tests are retained and re-blessed with the now-less-optimized output.

Fixes #13068.

<!--
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.html

Please ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->

Wasmtime GitHub notifications bot (Apr 13 2026 at 20:47):

cfallin requested wasmtime-compiler-reviewers for a review on PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 20:50):

cfallin updated PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 20:53):

alexcrichton submitted PR review.

Wasmtime GitHub notifications bot (Apr 13 2026 at 20:55):

alexcrichton has enabled auto merge for PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 22:59):

github-actions[bot] added the label isle on PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 22:59):

github-actions[bot] added the label cranelift on PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 22:59):

github-actions[bot] commented on PR #13081:

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 13 2026 at 23:18):

cfallin requested pchickey for a review on PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 23:18):

cfallin requested wasmtime-core-reviewers for a review on PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 23:18):

cfallin updated PR #13081.

Wasmtime GitHub notifications bot (Apr 13 2026 at 23:18):

cfallin unassigned pchickey from PR #13081 Cranelift: revert rules added in #12926..

Wasmtime GitHub notifications bot (Apr 13 2026 at 23:32):

alexcrichton added PR #13081 Cranelift: revert rules added in #12926. to the merge queue

Wasmtime GitHub notifications bot (Apr 14 2026 at 00:02):

alexcrichton merged PR #13081.

Wasmtime GitHub notifications bot (Apr 14 2026 at 00:02):

alexcrichton removed PR #13081 Cranelift: revert rules added in #12926. from the merge queue

Wasmtime GitHub notifications bot (Apr 14 2026 at 00:23):

MaxGraey submitted PR review.

Wasmtime GitHub notifications bot (Apr 14 2026 at 00:23):

MaxGraey created PR review comment:

My two cents. Can’t you just decompose this into two simple rules, which I’m sure already exist:
x + y --> y + x
x == x --> true

Wasmtime GitHub notifications bot (Apr 14 2026 at 02:43):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Apr 14 2026 at 02:43):

cfallin created PR review comment:

@MaxGraey x + y -> y + x is commutativity, which is a valid rewrite but is known to cause huge blowup in rewrite systems in general (at least 2x blowup for all commutative binary operators, combinatorially more when nested).

In general we have a philosophy in Cranelift not to have commutativity as a rule, but to explicitly unfold left-hand sides in commutative combinations, because writing more rules is more efficient than doing the commutative rewrites always (just in case something would match) at runtime.

Wasmtime GitHub notifications bot (Apr 14 2026 at 07:07):

MaxGraey submitted PR review.

Wasmtime GitHub notifications bot (Apr 14 2026 at 07:07):

MaxGraey created PR review comment:

Yeah, commutative rewrites like x + y -> y + x cause blow-up in e-graphs because they explicitly generate equivalent forms. For a1 + a2 + ... + an, commutativity alone gives up to n! permutations, and associativity adds even more shapes like (a + b) + c <-> a + (b + c). This inflates e-nodes and match counts even though the semantics are unchanged.

The usual fix is to not encode a+b <-> b+a as a rewrite at all, but to canonicalize, e.g. add_CT[b, a, ...] -> add_CT[a, b, ...], and for AC ops use flatten+sort: (((c + a) + b) + ...) -> add_AC[a,b,c,..]. add_CT & add_AC are special canonized constructors of e-graph's defs. And during matching, they must already have some canonical form (sorted for instance), or be rearranged very carefully, for example, by grouping constants and rearranging them as a group within an associative expression, limiting the number of rearrangements, and conservatively stopping them if this does not reduce the cost in terms of the new subgraph (e-class), and so on.

What’s more, in my view, this will reduce the amount of boilerplate code in your ISLE and the number of isoforms for the same rule and now there’ll be no need to wonder whether it will explode or not.

WDYT?

````

Wasmtime GitHub notifications bot (Apr 14 2026 at 07:07):

MaxGraey edited PR review comment.

Wasmtime GitHub notifications bot (Apr 14 2026 at 07:08):

MaxGraey edited PR review comment.

Wasmtime GitHub notifications bot (Apr 14 2026 at 07:15):

MaxGraey edited PR review comment.

Wasmtime GitHub notifications bot (Apr 14 2026 at 07:15):

MaxGraey edited PR review comment.

Wasmtime GitHub notifications bot (Apr 14 2026 at 07:16):

MaxGraey edited PR review comment.

Wasmtime GitHub notifications bot (Apr 14 2026 at 09:57):

MaxGraey edited PR review comment.

Wasmtime GitHub notifications bot (Apr 14 2026 at 10:09):

MaxGraey edited PR review comment.

Wasmtime GitHub notifications bot (Apr 14 2026 at 15:29):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Apr 14 2026 at 15:44):

MaxGraey edited PR review comment.

Wasmtime GitHub notifications bot (Apr 14 2026 at 15:55):

cfallin created PR review comment:

@MaxGraey canonicalization is something we've talked about in the past, but does add a good amount of complexity of course. In the commutativity-of-binary-operator case it's "just" custom hash+eq but for associativity this implies an N-input operator form which is a much much bigger change to the whole Cranelift backend (we could rewrite into this form and then out of it, but (i) that's out-of-line storage for args, (ii) that's a lot of memory traffic churn when the common case doesn't need this). We also have sort of competing notions of canonicity: e.g. the const-folding rules put constants to the right but that conflicts with SSA ordering, so we'd have to get a bit finicky with heuristic engineering here in a way that feels a little brittle.

So: nice in theory and we've thought about it but the details are tricky. If you actually want to play with this in a branch (it's likely none of us have time), measure results, and report back, that'd be very interesting of course!

Wasmtime GitHub notifications bot (Apr 14 2026 at 15:59):

MaxGraey submitted PR review.

Wasmtime GitHub notifications bot (Apr 14 2026 at 15:59):

MaxGraey created PR review comment:

If I were a student, I might sign up for such an adventure. Unfortunately, I’m not a student, and my budget constraints doesn’t allow me to spend much free time on anything beyond a few ideas and pull requests to LLVM, mostly focused on improving analysis and optimization in the floating-point domain, which I consider one of the most under-optimized areas in modern compilers, as well as trying to find remote job, which takes a significant amount of time and effort these days.

Last updated: May 03 2026 at 22:13 UTC