Stream: git-wasmtime

Topic: wasmtime / PR #14879 cranelift: fold divisibility tests b...

Wasmtime GitHub notifications bot (Oct 20 2026 at 04:48):

losewayy opened PR #14879 from losewayy:improve-divisibility-by-constant to bytecodealliance:main:

Fixes #14699.

Testing x % c == 0 currently computes the whole quotient and multiplies back to recover the remainder, even though only the zero test is used. On x86-64 that is a mull plus shift/imul sequence; LLVM emits a single multiply and compare for the same test.

The fold is not expressible today for a structural reason. urem and srem are modelled as skeleton instructions because they can trap, and a skeleton instruction's result is replaced by its rewrite before the icmp consuming it is visited, so a simplify rule can never see the icmp(urem x, c) pair. A remainder by a non-zero constant divisor cannot trap (srem only traps on a zero divisor and yields 0 for INT_MIN % -1), so those nodes are now pure and the existing remainder rewrites move from simplify_skeleton to simplify behind new urem_value/srem_value extractors. The constant folds subsume so they are not competed away by the magic-number sequences, and the extraction cost model prices integer division above the sequences that replace it.

The new rules cover signed and unsigned remainders, eq/ne, odd and even divisors, and 8/16/32/64-bit widths. Even divisors use a rotate to fold the low-bit requirement into the same compare, and signed tests add a bias so negative multiples land in the same range.

egraph/divisibility.clif shows the folded shape for each combination, and runtests/divisibility.clif checks the folded test against the interpreter and the host target.

Trap behaviour is unchanged: urem x, 0 still emits divl, srem x, -1 still emits the checked idiv sequence, and urem x, 8 still becomes band.

A function that only performs a divisibility test compiles from 64 bytes to 29 bytes. Separately, a 500M-iteration wasm loop that counts multiples of 7 runs in 301 ms instead of 491 ms, minimum of five runs. Both numbers were measured with the initial revision of this branch; the later fixes only affect signed remainders and constant folding, which that unsigned loop does not use.

The ISLE verifier passes for opt-fast and opt, the latter being what CI runs. No specifications are provided for the magic-number helpers, so the rules using them are tagged TODO and are not formally verified yet. u64_shl is tagged because its existing specification uses a match clause on a term the verifier treats as non-partial, and i64_is_any_sign_power_of_two because it is defined by priority-ordered rules the verifier does not negate. The tags are added here so the verification run can proceed.

Checks run: cargo test -p cranelift-tools --test filetests, cargo test -p cranelift-codegen, cargo clippy -p cranelift-codegen --all-targets -- -D warnings, rustfmt --check, and cranelift/isle/veri/verify.sh on opt-fast and opt.

Wasmtime GitHub notifications bot (Oct 20 2026 at 04:48):

losewayy removed the review request for wasmtime-compiler-reviewers from PR #14879.

Wasmtime GitHub notifications bot (Oct 20 2026 at 04:48):

losewayy requested fitzgen for a review on PR #14879.

Wasmtime GitHub notifications bot (Oct 20 2026 at 04:48):

losewayy requested wasmtime-compiler-reviewers for a review on PR #14879.

Wasmtime GitHub notifications bot (Oct 20 2026 at 06:30):

losewayy updated PR #14879.

Wasmtime GitHub notifications bot (Oct 20 2026 at 06:58):

losewayy updated PR #14879.

Wasmtime GitHub notifications bot (Oct 20 2026 at 08:51):

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

Wasmtime GitHub notifications bot (Oct 20 2026 at 08:51):

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

Wasmtime GitHub notifications bot (Oct 20 2026 at 09:50):

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

Subscribe to Label Action

cc @avanhatt, @cfallin, @fitzgen, @mmcloughlin

<details>
This issue or pull request has been labeled: "cranelift", "isle"

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

• avanhatt: isle
• cfallin: isle
• fitzgen: isle
• mmcloughlin: 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 (Oct 22 2026 at 19:13):

:memo: fitzgen submitted PR review.

Wasmtime GitHub notifications bot (Oct 22 2026 at 19:13):

:speech_balloon: fitzgen created PR review comment:

We should handle the overflow case as well, unless we are going to avoid the magic testing when d == -1, in which case we should assert that it is not -1 in the magic_test_s{32,64} functions. The semantics should match whatever WebAssembly does.

Wasmtime GitHub notifications bot (Oct 22 2026 at 19:13):

:speech_balloon: fitzgen created PR review comment:

Rather than talking about the specific way that this is used by some particular call sites, can we document the soundness requirements for using this instead? That is, it may only be used in optimizations where the divisor is guaranteed to be (or checked to be) non-zero.

Wasmtime GitHub notifications bot (Oct 22 2026 at 19:13):

:speech_balloon: fitzgen created PR review comment:

And this should also test n % -1 == 0 for various n including i32::MIN.

Wasmtime GitHub notifications bot (Oct 22 2026 at 19:13):

:speech_balloon: fitzgen created PR review comment:

We should also explicitly test n % 0 == 0 and n % -1 == 0 (and particularly srem and n = i32::MIN for the latter).

Wasmtime GitHub notifications bot (Oct 22 2026 at 19:13):

:speech_balloon: fitzgen created PR review comment:

This sentence

No specifications are provided for the magic-number constructors, so the rules that use them are tagged TODO and are not formally verified yet.

is irrelevant to the item that the comment is documenting (u32_is_power_of_two).

It is also redundant with the claimed TODOs, so I don't think it is necessary to include.

It also reads a bit like exactly the kind of random fact an LLM would just throw in, without any idea of how important that fact actually is. Please be more rigorous reviewing and polishing LLM output in the future.

Wasmtime GitHub notifications bot (Oct 22 2026 at 19:13):

:speech_balloon: fitzgen created PR review comment:

I am not sure we want to do this whole check for every value in the function, especially since it is incomplete because the divisor might not be a constant now but might later be rewritten into a constant after optimization.

I think a better approach would be to leave the urem/srem in the side-effectful skeleton during egraph construction (i.e. remove_pure_and_optimize, which is what makes use of is_pure_for_egraph) and then define this commit's optimizations as simplify_skeleton rules rather than regular simplify rules, which matches the other division/remainder optimizations. This miiight also remove the need to have the footgun-y {u,s}rem_value ISLE terms.

Wasmtime GitHub notifications bot (Oct 23 2026 at 05:52):

losewayy updated PR #14879.

Wasmtime GitHub notifications bot (Oct 23 2026 at 05:52):

losewayy edited PR #14879:

Fixes #14699.

This adds constant-divisibility tests for x % c == 0 and x % c != 0, using precomputed multipliers, bit operations and comparisons instead of computing the full remainder. Unsigned even divisors use a rotate; signed tests use a bias and check the low bits separately.

The rules stay in simplify_skeleton, alongside the existing remainder optimizations. Before forward rewriting, a use scan records remainders whose results are only compared with zero. This is needed because the skeleton pass visits the remainder before its comparison consumers. The set is rebuilt for each pass and is only consulted when rewriting a remainder. If another use needs the actual remainder, the normal remainder calculation is retained.

The implementation handles signed and unsigned 8-, 16-, 32- and 64-bit integers. Existing power-of-two handling is retained. Zero divisors keep their trapping operations, and signed MIN % -1 retains its zero result.

Validation on Windows x86-64: 209 codegen library tests and 86 filetests passed, covering the egraph suite and the relevant division/remainder runtime files. Added cases include i8 comparisons with zero on either side, zero divisors in optimized IR, signed -1 with MIN inputs, MIN divisors, mixed uses and block arguments. Division-by-zero was checked in optimized IR, not executed in the runtime harness. Crate formatting and git diff --check pass.

The current VeriISLE configuration verifies simplify; it does not support these simplify_skeleton rules.

Wasmtime GitHub notifications bot (Oct 23 2026 at 05:53):

losewayy commented on PR #14879:

Thanks for the careful review, and sorry I didn't review and polish the changes thoroughly enough before sending them.

I've moved the remainder rewrites back to simplify_skeleton and removed the purity changes, remainder extractors and cost-model changes. Before forward rewriting, a use scan identifies remainders used only in comparisons with zero, since the skeleton pass reaches each remainder before its consumers. Other uses keep the normal remainder calculation.

I've also added the zero-divisor and signed MIN/-1 cases you requested, and cleaned up the comments to match the surrounding code.

Wasmtime GitHub notifications bot (Oct 26 2026 at 16:44):

:memo: fitzgen submitted PR review.

Wasmtime GitHub notifications bot (Oct 26 2026 at 16:44):

:speech_balloon: fitzgen created PR review comment:

Ah okay, I see the issue is that the urem is the skeleton instruction, but the rule to match needs to be rooted in the icmp.

I don't think this current iteration of the PR is what we want to do either. What we want to be able to do is effectively replace urem with a hypothetical urem_notrap instruction and remove it from the side-effectful skeleton at the same time, so that it doesn't remain an elaboration root. We don't have any machinery to do that right now, and I think its something that deserves wider discussion at the next Cranelift meeting. Please join if you'd like, otherwise I can summarize the discussion here on Wednesday.

Wasmtime GitHub notifications bot (Oct 26 2026 at 16:44):

:speech_balloon: fitzgen created PR review comment:

        let x = n.cast_unsigned();

Wasmtime GitHub notifications bot (Oct 26 2026 at 16:44):

:speech_balloon: fitzgen created PR review comment:

        let x = n.cast_unsigned();

Wasmtime GitHub notifications bot (Oct 26 2026 at 16:44):

:speech_balloon: fitzgen created PR review comment:

Why do we have to do this? I wouldn't expect that we would need to pre-walk every instruction. I'd think that ISLE matching is good enough here.

I also expect this will impose a measurable slowdown to compilation. Can you do a Sightglass benchmarking run comparing with and without this commit?

Wasmtime GitHub notifications bot (Oct 26 2026 at 17:56):

:speech_balloon: losewayy created PR review comment:

Thanks for putting this on the agenda! I won't be able to join this time, but I'd appreciate a summary here afterward. I'm happy to help with the implementation once there's a clearer direction.

Wasmtime GitHub notifications bot (Oct 26 2026 at 17:56):

:memo: losewayy submitted PR review.

Last updated: Oct 31 2026 at 23:03 UTC