wasmtime / PR #14228 Cranelift: add opportunistic value d... · git-wasmtime

Stream: git-wasmtime

Topic: wasmtime / PR #14228 Cranelift: add opportunistic value d...

Wasmtime GitHub notifications bot (Aug 28 2026 at 20:34):

cfallin opened PR #14228 from cfallin:opportunistic-value-defs to bytecodealliance:main:

Add a new lowering primitive, an "opportunistic def", which allows a lowering that incidentally computes another value to register that value for possible later use. When the backward scan reaches the value's actual definition, if the use-count has not grown (no further uses appeared while scanning up), the definition can be skipped entirely and the value aliased to the opportunistically-computed regs.

Also add a value_used helper that reports whether a value still has uses, allowing skipping of some part of a lowering when not needed.

With these two features available in the lowering environment, this PR then adds new lowerings for brif-of-uadd_overflow, and bare uadd_overflow, on x86-64 and aarch64:

When uadd_overflow's overflow flag is used as a branch condition, the branch directly uses flags produced by the add instruction, skipping (slow and verbose) materialization of the bool overflow flag into a GPR.

If the sum is only used past the branch, then this add also produces that value; so only one add is ever emitted. Thus a add; SETcc; test; jnz sequence turns into (x64) add; jb / (aarch64) adds; b.hs.

If the sum is used below the uadd_overflow but above the branch, another add is also emitted. That's fine: adds are cheap; cheaper certainly than materializing flags with SETcc or CSET.

But to optimize that case further...

...when uadd_overflow is only used for its sum, and not its overflow flag, we now emit an add without a SETcc.

As a result of these lowerings, the case v1, v2 = uadd_overflow ...; brif v2, ... lowers to add; jb, and the case v1, v2 = uadd_overflow ...; (use v1); brif v2, ... lowers to add; (use sum); add; jb. The only remaining case where we use a slow SETcc is when the bool result is actually materialized and used as an integer value; or if the add and branch are pushed into separate blocks.

This resolves the same issue as #13919, following discussion in that PR and the Cranelift weekly meeting. In particular, (i) we do not build an ad-hoc separate scan (this mechanism works as part of the main lowering/instruction-selection scan); and (ii) we are resilient to instructions placed between the uadd_overflow and branch, which is likely to happen due to egraph demand-based elaboration, and which foils a simpler peephole-based approach.

Wasmtime GitHub notifications bot (Aug 28 2026 at 20:34):

cfallin requested alexcrichton for a review on PR #14228.

Wasmtime GitHub notifications bot (Aug 28 2026 at 20:34):

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

Wasmtime GitHub notifications bot (Aug 28 2026 at 20:35):

cfallin commented on PR #14228:

(This has been on my TODO list for a long time; sorry about the delay, @playX18, but hopefully this addresses your use-case!)

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:07):

:memo: alexcrichton submitted PR review:

Seems reasonable to me! Question on this: would it be possible to somehow determine, before fusing this into a branch, if the opportunistic def is going to be thrown away and re-calculated? For something like an addition it seems probably fine to always duplicate that, but for something like a multiplication it might be better to never duplicate that given its latency. (maybe? unsure). Basically it seems to me like a reasonable heuristic here would be to only fuse into branches where the opportunistic def actually works as the def, and in all other cases fall back to materializing the flag and then testing it later.

Although now that I actually write this down what I'm going for is to put the onus on CLIF producers to make sure the flag-and-branch are close together such that the opportunistic def always matches. In some sense that's no different from this PR as-is where it's still on them to do that to avoid the double-translate if it matters... Anyway, still curious on the question at least as a data point

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:07):

:speech_balloon: alexcrichton created PR review comment:

Would it be possible to fold this into is_nonzero_cmp instead of having a rule specifically for brif? That'd then additionally handle the condition flowing intp a trapz, trapnz, and select all at the same time. If this does work, could this be done for x64 too?

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:07):

:speech_balloon: alexcrichton created PR review comment:

Is this rule needed for the codegen tests that were added, or was this opportunistically added mostly to prove this out?

Additionally, could this skip using adds and just use add instead? If so I think the ConsumesFlagsNop infrastructure can be removed.

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:07):

:speech_balloon: alexcrichton created PR review comment:

Additionally, since we might want to use this for a number of other things, could a new helper like produces_flags_with_opportunistic_def be added? That'd internally then use produces_flags_get_reg, call opportunistic_def, and then return a ProducesFlags created with produces_flags_ignore. Basically factoring out the boilerplate-y parts of this if possible

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:45):

cfallin requested pchickey for a review on PR #14228.

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:45):

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

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:45):

cfallin updated PR #14228.

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:45):

:memo: cfallin submitted PR review.

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:45):

:speech_balloon: cfallin created PR review comment:

Yes, this is what handles the "intermediate user" case (and removes the unused SETcc). But yeah great point, I dunno why I kept that bit (copy+paste I guess); this is really just a plain old add. Updated!

Wasmtime GitHub notifications bot (Aug 28 2026 at 21:48):

cfallin commented on PR #14228:

Seems reasonable to me! Question on this: would it be possible to somehow determine, before fusing this into a branch, if the opportunistic def is going to be thrown away and re-calculated? For something like an addition it seems probably fine to always duplicate that, but for something like a multiplication it might be better to never duplicate that given its latency. (maybe? unsure). Basically it seems to me like a reasonable heuristic here would be to only fuse into branches where the opportunistic def actually works as the def, and in all other cases fall back to materializing the flag and then testing it later.

Although now that I actually write this down what I'm going for is to put the onus on CLIF producers to make sure the flag-and-branch are close together such that the opportunistic def always matches. In some sense that's no different from this PR as-is where it's still on them to do that to avoid the double-translate if it matters... Anyway, still curious on the question at least as a data point

Unfortunately we can't really know "the future" during the backward lowering scan (or, well, we could, but that would be a separate scan). The conclusion I came to is that it's way simpler to build this opportunistic mechanism and just let the lowering fire twice if there is actually a user in the block in between the add and branch.

I also address this with "If the sum is used below the uadd_overflow but above the branch, another add is also emitted. That's fine: adds are cheap; cheaper certainly than materializing flags with SETcc or CSET.", I think: what we get here is actually still cheaper than what you're asking for (strictly one fewer instruction -- add; add; branch rather than add; setcc; test; branch; and the setcc is slow).

Wasmtime GitHub notifications bot (Aug 28 2026 at 22:18):

:memo: cfallin submitted PR review.

Wasmtime GitHub notifications bot (Aug 28 2026 at 22:18):

:speech_balloon: cfallin created PR review comment:

I played with this a bit, but IMHO it's not really that much simpler to fold this into ProducesFlags. It requires pulling apart all the pieces from the original inst anyway and stuffing them into the ProducesFlags (the other result value, the emitted result from the adds) and requires thinking about the emission combinations with various ConsumesFlags. Arguably more brittle, and distributes the logic over a larger area. In other words I don't think it actually avoids any boilerplate, it just explodes it into shards of boiler iron embedded in the walls...

Wasmtime GitHub notifications bot (Aug 28 2026 at 22:19):

:memo: cfallin submitted PR review.

Wasmtime GitHub notifications bot (Aug 28 2026 at 22:19):

:speech_balloon: cfallin created PR review comment:

(Happy to tackle this or see someone else tackle this in a followup of course if there are more ideas here -- but maybe good to get the building blocks in first regardless?)

Wasmtime GitHub notifications bot (Aug 28 2026 at 23:44):

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

Wasmtime GitHub notifications bot (Aug 28 2026 at 23:44):

github-actions[bot] added the label cranelift:area:machinst on PR #14228.

Wasmtime GitHub notifications bot (Aug 28 2026 at 23:44):

github-actions[bot] added the label cranelift:area:aarch64 on PR #14228.

Wasmtime GitHub notifications bot (Aug 28 2026 at 23:44):

github-actions[bot] added the label cranelift:area:x64 on PR #14228.

Wasmtime GitHub notifications bot (Aug 31 2026 at 14:34):

alexcrichton commented on PR #14228:

but for something like a multiplication it might be better to never duplicate that given its latency

Do you have thoughts on this?

Also something else I was thinking of recently, if an operation is loop-invariant we'd previously calculate it once outside of a loop and then reuse the flags/result within the loop, but now this'll force the arguments to the opertion to stay live for the entire loop. That in theory could add to register pressure which could have knock-on effects beyond the cost of the operation itself.

Maybe a heuristic that could be added is that the brif folding only happens when the flag brif is consuming was defined in the same basic block as the brif itself? That doesn't fully eliminate the double-translation but might help ward off pathological loop-like cases and I believe should also be pretty easy to implement.

Wasmtime GitHub notifications bot (Aug 31 2026 at 14:39):

:memo: alexcrichton submitted PR review.

Wasmtime GitHub notifications bot (Aug 31 2026 at 14:39):

:speech_balloon: alexcrichton created PR review comment:

Sorry but to clarify, which comment are you responding to of mine? The is_nonzero_cmp part or the produces_flags_with_opportunistic_def part?

For the helper part, to clarify I'm not asking for what I believe is anything too invovled, brittle, or fancy here. I'm envisioning:

diff --git a/cranelift/codegen/src/isa/aarch64/lower.isle b/cranelift/codegen/src/isa/aarch64/lower.isle
index 10a1f01c31..aca4ee5e12 100644
--- a/cranelift/codegen/src/isa/aarch64/lower.isle
+++ b/cranelift/codegen/src/isa/aarch64/lower.isle
@@ -3170,10 +3170,14 @@
                        (second_result
                         uadd_inst @ (uadd_overflow (ty_32_or_64 ty) x y)) _ _) (two_targets taken not_taken))
         (if-let (first_result v1) uadd_inst)
-        (let ((producer ProducesFlags (alu_rrr_with_flags_paired ty x y (ALUOp.AddS)))
-              (sum Reg (produces_flags_get_reg producer))
-              (_ Unit (opportunistic_def v1 sum)))
-          (emit_side_effect (br_cond_result (CondResult.Cond (produces_flags_ignore producer) (Cond.Hs)) taken not_taken))))
+        (let ((producer ProducesFlags (alu_rrr_with_flags_paired ty x y (ALUOp.AddS))))
+          (emit_side_effect (br_cond_result (CondResult.Cond (produces_flags_with_opportunistic_def v1 producer) (Cond.Hs)) taken not_taken))))
+
+(decl produces_flags_with_opportunistic_def (Value ProducesFlags) ProducesFlags)
+(rule (produces_flags_with_opportunistic_def val producer)
+  (let ((def Reg (produces_flags_get_reg producer))
+         (_ Unit (opportunistic_def val def)))
+    (produces_flags_ignore producer)))

 ;; Helper to emit a branching instruction based on  a `CondResult`
 (decl br_cond_result (CondResult MachLabel MachLabel) SideEffectNoResult)

Personally I think a helper like that when other instances of this are added for subtract-with-overflow and multiply-with-overflow as it's less to juggle and duplicate across rules.

Wasmtime GitHub notifications bot (Aug 31 2026 at 15:19):

:memo: cfallin submitted PR review.

Wasmtime GitHub notifications bot (Aug 31 2026 at 15:19):

:speech_balloon: cfallin created PR review comment:

Ah, OK, I was trying to push the side-effects all to the with_flags emitter; so the opportunistic def itself would occur only when used. Cleaner in some sense but also exploded in complexity. I'll try to push this direction instead, thanks!

Wasmtime GitHub notifications bot (Aug 31 2026 at 15:19):

cfallin commented on PR #14228:

but for something like a multiplication it might be better to never duplicate that given its latency

Do you have thoughts on this?

Yep, agreed; this PR doesn't do the thing for multiply-with-overflow and IMHO it's probably good to keep it that way.

Also something else I was thinking of recently, if an operation is loop-invariant we'd previously calculate it once outside of a loop and then reuse the flags/result within the loop, but now this'll force the arguments to the opertion to stay live for the entire loop. That in theory could add to register pressure which could have knock-on effects beyond the cost of the operation itself.

Maybe a heuristic that could be added is that the brif folding only happens when the flag brif is consuming was defined in the same basic block as the brif itself? That doesn't fully eliminate the double-translation but might help ward off pathological loop-like cases and I believe should also be pretty easy to implement.

Yeah, this is an interesting tradeoff space, and unfortunately is NP-hard. Basically what you're asking is can we combine instruction selection and regalloc to be aware of each other with their cost heuristics, i.e. don't fuse or choose different instructions if it would result in register pressure; there are PhD theses on this (see e.g. David Koes from CMU).

What I would say is that example-driven thinking I think will not necessarily lead us to a globally optimal place here; for any heuristic we come up with, we can come up with a counterexample. (For example: the same-block-only heuristic is brittle in the face of code motion or CFG edits that might otherwise be totally reasonable: GVN hoisting a common add that occurs in two sub-branches; or, a CLIF-level edge splitting that a producer might do; or ...)

I think that if we want to relitigate instruction fusion in general, we should have the discussion at a high level and evaluate it objectively. Experience has shown so far that a "maximal" instruction fusion approach generally results in better code and perf. Someone else is welcome to run experiments changing these heuristics globally and see what it does on Sightglass; naively I'd expect some negative movement but we'd have to see.

Wasmtime GitHub notifications bot (Aug 31 2026 at 15:20):

cfallin edited a comment on PR #14228:

but for something like a multiplication it might be better to never duplicate that given its latency

Do you have thoughts on this?

Yes -- this PR doesn't do the thing for multiply-with-overflow and IMHO it's probably good to keep it that way.

Also something else I was thinking of recently, if an operation is loop-invariant we'd previously calculate it once outside of a loop and then reuse the flags/result within the loop, but now this'll force the arguments to the opertion to stay live for the entire loop. That in theory could add to register pressure which could have knock-on effects beyond the cost of the operation itself.

Maybe a heuristic that could be added is that the brif folding only happens when the flag brif is consuming was defined in the same basic block as the brif itself? That doesn't fully eliminate the double-translation but might help ward off pathological loop-like cases and I believe should also be pretty easy to implement.

Yeah, this is an interesting tradeoff space, and unfortunately is NP-hard. Basically what you're asking is can we combine instruction selection and regalloc to be aware of each other with their cost heuristics, i.e. don't fuse or choose different instructions if it would result in register pressure; there are PhD theses on this (see e.g. David Koes from CMU).

What I would say is that example-driven thinking I think will not necessarily lead us to a globally optimal place here; for any heuristic we come up with, we can come up with a counterexample. (For example: the same-block-only heuristic is brittle in the face of code motion or CFG edits that might otherwise be totally reasonable: GVN hoisting a common add that occurs in two sub-branches; or, a CLIF-level edge splitting that a producer might do; or ...)

I think that if we want to relitigate instruction fusion in general, we should have the discussion at a high level and evaluate it objectively. Experience has shown so far that a "maximal" instruction fusion approach generally results in better code and perf. Someone else is welcome to run experiments changing these heuristics globally and see what it does on Sightglass; naively I'd expect some negative movement but we'd have to see.

Wasmtime GitHub notifications bot (Aug 31 2026 at 15:41):

alexcrichton commented on PR #14228:

Sorry I think I'm being misinterpreted, I'm not asking for intertwining regalloc and instruction selection as I'm familiar with how you've said a number of times historically that it's basically not practical. I'm additionally not asking to relitigate anything here.

What I'm trying to poke at is that this change isn't being made in isolation, but I view this as a solution to the problem of fusing oveflow-producing things with conditional branches. This is one of a possible number of ways to solve this, and in reviewing this I'm pointing out how I don't believe that this is a universal solution as-is. For example I understand you're not proposing adding multiplication here, and nor am I proposing that multiplication be added here. Despite that though I want to point out that I'm not sure it would make sense to use this infrastructure to add multiplication handling because of the risk of duplicating instructions and the latency of multiplication.

In terms of evaluation, the original PR https://github.com/bytecodealliance/wasmtime/pull/13919 here points to this zulip conversation which was specifically about multiplication overflow for example. In the spirit of objective evaluation, should this perhaps be benchmarked in the context of the original project to see how much this helps things? Not by you @cfallin but @playX18 would you be able to help out benchmarking this change? I'd be surprised if Sightglass were set up to take advantage of these new lowering rules since wasm doesn't really use *_overflow instructions.

In the absence of benchmarks I agree I don't know how best to evaluate this -- is duplication of the add always the right option, or are there edge cases that would push the heursitics in a different direction? Is the same-block-definition rule too brittle to miss out on enough optimizations, or does it cover most of the intended use cases? I'm not sure myself...

Wasmtime GitHub notifications bot (Aug 31 2026 at 15:55):

cfallin commented on PR #14228:

In the absence of benchmarks I agree I don't know how best to evaluate this -- is duplication of the add always the right option, or are there edge cases that would push the heursitics in a different direction? Is the same-block-definition rule too brittle to miss out on enough optimizations, or does it cover most of the intended use cases? I'm not sure myself...

Right, and I'm claiming that this is itself relitigating our consensus on instruction fusion (whether or not you mean to). It's true in far more cases than just here that fusing producer instructions into consumers can extend liveranges.[^1] We've accepted this, and we've generally seen better code as a result.

The unique bit here is that we potentially codegen add twice (as we do for other kinds of flag producers, too, BTW -- every use of an icmp that fuses will codegen a cmp, which uses the same ALU as add). But that's already addressed by the argument above that the dynamic instruction path length is actually shorter with this PR: add; add; jo for the case with use-in-the-middle is strictly better than add; seto; test; jnz.

I don't believe that this is a universal solution as-is.

Nothing is, I believe; that's the frustrating bit about compilers! :-)

[^1]: For a simple example: on aarch64, we can fuse shifts and extends into addressing modes. If someone else also uses the result of the shift/extend directly, we'll also codegen that op separately. That's fine; ALU ops are cheap; doing better is (again) an NP-hard weighted-set-cover problem. The idea of "maximal munch" (Muchnick book's term) is that it's a pretty good heuristic on average.

Wasmtime GitHub notifications bot (Aug 31 2026 at 16:19):

alexcrichton commented on PR #14228:

Ok I see what you mean yeah, and I think it's fine to set aside the double-translation issue. I'd still like to see if it's possible to integrate with is_nonzero_cmp, though, and poking through the genesis of the feature request shows that this may not actually solve the original request as it was via multiplication, but that doesn't mean that this can't land separately. (although the point about maybe-lowering-two-mul-is-net-worse I feel is still open)

Wasmtime GitHub notifications bot (Aug 31 2026 at 16:39):

cfallin commented on PR #14228:

this may not actually solve the original request as it was via multiplication

FWIW, thinking about it some more, we could include *mul_overflow too, with the following reasoning: it's a separate opcode, so it's allowed to have a separate cost profile. And "will be exactly as cheap as a normal multiply as long as you don't also use it between the op and the branch-on-overflow" seems like a reasonable rule. Keeping in mind that the not-fused case has a cost on the materialized overflow path as well, the matrix is:

no fusion, no in-the-middle use of product output: 4 insts, 6 cycles (mul; seto; test; jnz)

no fusion, in-the-middle use of product output: 4 insts, 6 cycles min, partial register stall(*) (mul; seto; ...; test; jnz)

fusion, no in-the-middle use of product output: 2 insts, 4 cycles (mul; jo)

fusion, in-the-middle use of product output: 3 insts, 7 cycles (mul; ...; mul; jo)

(*) partial register stall: seto %al (or any 8-bit reg) has an input dependency on whatever was previously in that register, since the upper 56 bits are unchanged; so it potentially waits longer in the OoO scheduling for that previous producer to finish, even though it's unused by the test %al, %al later.

So it seems almost always better to me to do the fusion; (i) the producer can know the cost profile, (ii) it's a big win in the good case, (iii) it's 1 cycle penalty in the bad case, still avoids the unknown partial-register stall penalty, and it's still statically shorter code.

Wasmtime GitHub notifications bot (Aug 31 2026 at 17:44):

alexcrichton commented on PR #14228:

Oh I sort of naively expected multiplication to be 50-100 cycles, if it's just 3 then it seems fine to me to lump it in the same bucket as adds

Wasmtime GitHub notifications bot (Aug 31 2026 at 22:49):

cfallin updated PR #14228.

Wasmtime GitHub notifications bot (Aug 31 2026 at 22:52):

:memo: cfallin submitted PR review.

Wasmtime GitHub notifications bot (Aug 31 2026 at 22:52):

:speech_balloon: cfallin created PR review comment:

OK, pushed it all to the produces/consumes-flags mechanism, including the side-effect itself (emitted by with_flags), which turns out to be needed to make the nice folding work with a flags consumer that also consumes the other value (e.g., uadd_overflow + select -- hypothetically useful for a saturating add?), because of the ordering of the opportunistic def + processing of args in the outermost consumer.

Wasmtime GitHub notifications bot (Aug 31 2026 at 22:53):

cfallin commented on PR #14228:

Updated all, but I'll push a umul/smul case too.

Also the deeper surgery to ProducesFlags from review feedback meant I had to go (one-level-)recursive, and now I need to fix verification -- TBD, hopefully not too bad.

Wasmtime GitHub notifications bot (Aug 31 2026 at 23:06):

cfallin updated PR #14228.

Wasmtime GitHub notifications bot (Aug 31 2026 at 23:12):

:thumbs_up: alexcrichton submitted PR review:

Oh I'd be fine with what I sketched to avoid more ProducesFlags variants, but if you feel this is better that seems ok too

Wasmtime GitHub notifications bot (Aug 31 2026 at 23:14):

cfallin commented on PR #14228:

Yeah, I went further with putting the effect inside with_flags once I saw the uadd_overflow + select case have an extra add; we really should be able to do that (and now we do). It's a one-time cost and the proper framework solution so I'm fine with it now that it's done :-)

Wasmtime GitHub notifications bot (Aug 31 2026 at 23:41):

cfallin commented on PR #14228:

OK, actually I'll do muls in a separate PR -- they're getting kind of nontrivial (new variants since the sequences are not just a mul + branch). I'll go ahead and merge this now on your r+ -- thanks!

Wasmtime GitHub notifications bot (Aug 31 2026 at 23:41):

cfallin has enabled auto merge for PR #14228.

Wasmtime GitHub notifications bot (Aug 31 2026 at 23:42):

cfallin added PR #14228 Cranelift: add opportunistic value defs, use for uadd_overflow + brif folds. to the merge queue

Wasmtime GitHub notifications bot (Sep 01 2026 at 04:35):

:check: cfallin merged PR #14228.

Wasmtime GitHub notifications bot (Sep 01 2026 at 04:35):

cfallin removed PR #14228 Cranelift: add opportunistic value defs, use for uadd_overflow + brif folds. from the merge queue

Last updated: Sep 20 2026 at 20:07 UTC