wasmtime / PR #13919 feat(x64): fuse *_overflow + brif to... · git-wasmtime

Stream: git-wasmtime

Topic: wasmtime / PR #13919 feat(x64): fuse *_overflow + brif to...

Wasmtime GitHub notifications bot (Jul 21 2026 at 12:23):

playX18 opened PR #13919 from playX18:ap/fuse-overflow to bytecodealliance:main:

Was discussed shortly (#cranelift > Overflow flag is not used for branches?)

Why?

At the moment Cranelift to check for overflow generates something like add + seto + test and then jumps on the result of test. While this works, it is not optimal lowering. Better lowering is add + jo which removes ~2uops and reduces register pressure as we do not need to store overflow value if it can be fused.

Wasmtime GitHub notifications bot (Jul 21 2026 at 12:23):

playX18 requested cfallin for a review on PR #13919.

Wasmtime GitHub notifications bot (Jul 21 2026 at 12:23):

playX18 requested wasmtime-compiler-reviewers for a review on PR #13919.

Wasmtime GitHub notifications bot (Jul 21 2026 at 12:23):

playX18 updated PR #13919.

Wasmtime GitHub notifications bot (Jul 21 2026 at 15:20):

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

Wasmtime GitHub notifications bot (Jul 21 2026 at 15:20):

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

Wasmtime GitHub notifications bot (Jul 21 2026 at 15:20):

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

Wasmtime GitHub notifications bot (Jul 21 2026 at 15:20):

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

Wasmtime GitHub notifications bot (Jul 21 2026 at 15:21):

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

Subscribe to Label Action

cc @cfallin, @fitzgen

<details>
This issue or pull request has been labeled: "cranelift", "cranelift:area:machinst", "cranelift:area:x64", "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 (Jul 21 2026 at 15:48):

:repeat: cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jul 21 2026 at 15:48):

:speech_balloon: cfallin created PR review comment:

Unfortunately I don't think we'll want to take this as-is: it's too complex, in an area where we've already had some really subtle and difficult-to-reason-about bugs.

This set of conditions crosses several abstraction levels: it reasons about flag materialization, and especially about "another use of the same value", and then does code-motion if not. That kind of just-so optimization is both precarious (it's distributed invariant maintenance: the main lowering algorithm is responsible for putting defs before uses, but we're overriding that logic on the result of the overflow-checking op because we think it shouldn't matter to do it late in some blocks) and brittle (instruction order can suddenly influence things in unexpected and spooky-action-at-a-distance ways).

For that reason I think this "absorption" is an antipattern, a patch on top of the design that does not fit well with it, and we should instead try to use mechanisms we already have and/or come up with a more general framework that is less brittle and can be more fully integrated into the lowering algorithm.

Would you be willing to attend the next Cranelift meeting? I'd be happy to discuss further and we can try to come up with better approaches here...

Wasmtime GitHub notifications bot (Jul 22 2026 at 01:33):

:memo: playX18 submitted PR review.

Wasmtime GitHub notifications bot (Jul 22 2026 at 01:33):

:speech_balloon: playX18 created PR review comment:

Yes, I would like to join the next Cranelift meeting. How do I get an invite? :)

Wasmtime GitHub notifications bot (Jul 22 2026 at 02:18):

:memo: cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jul 22 2026 at 02:18):

:speech_balloon: cfallin created PR review comment:

cc @fitzgen for a calendar invite

Wasmtime GitHub notifications bot (Jul 22 2026 at 18:02):

fitzgen commented on PR #13919:

I think the correct way to do this is to formalize a classic, sliding-window-style peephole pass for vcode with a new set of ISLE rules, rather than attempting to, but only half-succeeding to, force it into our existing lowering and rules. This new peephole pass could reuse our existing value use counts from lowering to determine whether the condition needs to be materialized because it is used in other places as well or not. And, fwiw, that issue talks a lot about automata and such, but we could certainly start with a very naive matching strategy and then improve it in tree.

Also cc https://github.com/bytecodealliance/wasmtime/issues/4124

Wasmtime GitHub notifications bot (Jul 24 2026 at 16:23):

alexcrichton commented on PR #13919:

Another possible idea, which most certainly isn't perfect: add new CLIF instructions. For example we could add br_if_uadd_overflow v0, v1, no_overflow(ret0), overflow(ret0). Similar to try_call the result of the operation could be modeled as a "ret" of the instruction and be conditionally defined in each of the destination blocks. The downside of this is that it'd be a lot of CLIF instructions: {br_if,trapz,trapnz,select}_{u,s}{add,mul,sub}_overflow.{i8,i16,i32,i64} (2x3x4x4=96 new lowerings across N backends, this would in theory subsume uadd_overflow_trap or model more instructions after that). Whether this is more or less work than a peephole pass + lowering heuristics to ensure the peephole pass fires in most cases, I'm not sure. It would definitely make CLIF "less orthogonal" as this would be a natural combination of other instructions.

Wasmtime GitHub notifications bot (Jul 24 2026 at 16:53):

cfallin commented on PR #13919:

Yep, Nick and I talked about this offline a few days ago; that's the straightforward alternative, represent the concept in a durable way in the IR, but our conclusion was that it goes against the general design direction we've been pushing in CLIF, namely small orthogonal operators. And adding new control-flow ops is especially unfortunate because every bit of logic that deals with control flow would now have to handle those ops; e.g. if we ever do branch folding that becomes much more complex than just brif.

Although, that said, I just had a rather interesting idea: the key bit that avoids the need to have complex recovery logic (this PR, or a peephole, or something else) is to have the structural invariant in the IR itself that allows clean codegen; that's what the single-instruction idea is getting at. What if instead we had a structural notion in the IR of a single-use "subordinate" instruction? In other words, represent something like (conceptually, we may not want to actually build the parser/printer for this, see below)
let v0, v1 = uadd_overflow v2, v3 in
brif v1, block1(v0), block2
this essentially scopes v0 and v1 to only the following instruction. (Open question: arbitrary nesting? For now, just one level...) Then we can have an extractor in the lowering rules that can match "exclusive" instructions and do more with them.

The key bit that avoids wild complexity throughout the compiler is: "inst1 is subordinate to inst2" is a side-table in the Layout, and (i) we can compute it with a value-use-count scan, (ii) we can always remove the fact if violated. So most of the compiler remains agnostic to this, in fact the user wouldn't have to generate IR like this at all, but we could set up subordinates just before lowering. In essence it's a "treeification" of the linear IR so that we can do special things with only-locally-used instructions.

Then we could have matching rules like
(rule lower_branch (brif (exclusive flag @ (uadd_overflow ...))) ...)
that do the right thing. So maybe this is more properly seen as a pure value-count analysis that feeds etor conditions, but I guess I like the syntactic rendering of it as a way of seeing what's going on as well.

And one could ask: how is this different from the present PR? The key bit is that it works based on exclusive use; note also that the other output of uadd_overflow is also used only in the brif, as a blockparam to feed to the successor. So we don't need the brittle logic that depends on code layout and "no uses between here and there". Thoughts?

Wasmtime GitHub notifications bot (Jul 24 2026 at 18:01):

fitzgen commented on PR #13919:

What if instead we had a structural notion in the IR of a single-use "subordinate" instruction?

It seems to me that the key property is the single-use part. Does the "subordinate" stuff and let-scoping give us anything that adding a linear or once or whatever attribute to values does not?
v3, linear v4 = uadd_overflow(v1, v2)
br_if v4, block2(v3), block4
The key bit that avoids wild complexity throughout the compiler is: "inst1 is subordinate to inst2" is a side-table in the Layout,

I guess this is the trick that allows us to avoid teaching every pass/optimization/analysis that could add new uses of values to avoid doing so for linear values, and instead rematerialize them, if necessary.

But let-scoping and the side table still feels unsatisfying to me, in terms of the design point we end up at, because it feels like we are compromising on our ideal CLIF design based on incidental properties of our existing implementation of a previous version of the CLIF language. In some sense, we do this all the time, e.g. I have been generalizing alias regions instead of adding ghost effect values to CLIF because the latter would require very large implementation changes to our egraphs that we aren't even sure how to do, but still something keeps nagging me about this particular case...

Are you imagining that let-scoped values only live in the side table and not in the DFG's regular values map? That seems like it would be necessary in order to have the property of "avoid teaching every pass not to create new uses of the value". But it seems like we would still have to teach our passes to look at the side table or else they will see values without definitions, and I have no confidence they will happen to do the right thing in this case (i.e. we would still need to do a deep manual audit).

On the other hand, if let-scoped values do appear in the DFG's regular values map, then it seems like every pass that can create new uses (e.g. GVN/LICM in the egraph) needs to be manually updated as well.

So in either case it seems like we aren't avoiding a painful transition in our implementation.

(i) we can compute it with a value-use-count scan, (ii) we can always remove the fact if violated. So most of the compiler remains agnostic to this, in fact the user wouldn't have to generate IR like this at all, but we could set up subordinates just before lowering.

If the frontend isn't responsible for producing the annotations, and, even if it does produce them, we might not abide by the annotations and remove them, then why even have the annotation as part of the CLIF language in the first place?

It seems like, in practice, it would be no different from implementing the value-use-count scan ourselves as an analysis, rather than a language feature, and then using the results of this analysis in lowering. And this would avoid introducing a whole lot of complexity into the CLIF language (that wouldn't even give any guarantees to frontends!)

FWIW, to avoid adding a whole new scan over the IR, I think we could compute the use counts during elaboration and return them from the egraph pass, passing them into lowering.

And I think this would work, allowing us to implement the desired lowerings. But, because it is still operating at a data-flow graph level, before the code has been fully scheduled into a linear sequence, and pre- instead of post-regalloc, it doesn't help us with the other kinds of optimizations that are kind of hard to do until the code is scheduled and regalloc'd:

fusing mov rdx, [rsp+8]; add rax, rdx into add rax, [rsp+8] when the mov is a regalloc-inserted reload of a previous spill and rdx is not otherwise read again until it is overwritten

turning pairs of loads or stores into stp/ldp on aarch64

The post-regalloc sliding-window peephole approach does enable those optimizations, in addition to the flags reuse.

That said, while the post-regalloc sliding-window peephole pass would enable the flags reuse, it wouldn't make the register that the flags were materialized into available for allocating other values into, since it happens after regalloc. Computing use counts in elaboration and using them in lowering would allow that otherwise-would-have-held-materialized-flags register to be used for other values by regalloc. So maybe we ultimately would want both approaches?

Wasmtime GitHub notifications bot (Jul 24 2026 at 18:07):

cfallin commented on PR #13919:

So I think my writeup was misunderstood: I am not proposing that the frontend add these annotations and that we have to abide by them throughout the compiler. The key bit is

in fact the user wouldn't have to generate IR like this at all, but we could set up subordinates just before lowering. In essence it's a "treeification" of the linear IR so that we can do special things with only-locally-used instructions.

(admittedly that came later in a train-of-thought but...)

In essence I think this is what you later describe: an analysis that gives us a reliable bit saying "only use is here".

That said, the one important distinction is that it's not linear (single use) on the value but on the instruction. We need to know that both outputs of uadd_overflow are only used by the one subordinating instruction (brif). That is important to avoid the gnarliest part of this PR, namely the scan for other uses of that value so we can "absorb" safely; if we have the structural property that the whole instruction and all its defs are used only by one other instruction, then we know for sure that we can codegen it just before, or codegen as a unit. And by examining the producer and the only consumer of all values, we can know for sure that (e.g.) we don't need to materialize the bool at all.

Wasmtime GitHub notifications bot (Jul 24 2026 at 18:14):

fitzgen commented on PR #13919:

_That_ said, the one important distinction is that it's not linear (single use) on the _value_ but on the _instruction_. We need to know that _both_ outputs of uadd_overflow are only used by the one subordinating instruction (brif). That is important to avoid the gnarliest part of this PR, namely the scan for other uses of that value so we can "absorb" safely; if we have the structural property that the _whole instruction and all its defs_ are used only by one other instruction, then we know for sure that we can codegen it just before, or codegen as a unit. And by examining the producer and the only consumer of all values, we can know for sure that (e.g.) we don't need to materialize the bool at all.

Ah, value vs instruction use count is a good catch. But I don't think that ultimately changes anything about what I said regarding "why make this part of the CLIF language if it is effectively just an analysis?": We can still compute instruction use counts during elaboration (or wherever else) and use those counts during lowering without changing CLIF. And it doesn't seem like it would be worth changing CLIF, and adding all that new complexity, if we aren't expecting frontends to add the annotations and are allowing cranelift to remove the annotation whenever convenient.

Wasmtime GitHub notifications bot (Jul 24 2026 at 18:18):

fitzgen commented on PR #13919:

I guess without let-scoping, we would need to additionally ensure that, even when both values returned from uadd_overflow are single use, they are used by the same instruction (or otherwise can be scheduled such that the flags won't be overwritten, but this is pretty hairy).

I think even so, I still prefer an analysis that determines these facts, to changing the CLIF language.

Wasmtime GitHub notifications bot (Jul 24 2026 at 18:21):

cfallin commented on PR #13919:

OK, maybe we're over-indexing on that part. In my mind it was a nice way to write the representation, but I did not intend that we should add this to the parser or anything like that. Functionally it's a bit of state that is computed and fed into lowering, so yes, it's an analysis; one could think of it syntactically and see the analysis as a rewrite within the IR language, but that's not necessary to the idea. "Structural property" either way. The important part is that we have a notion that an instruction is only ever used by one other instruction, with matchers to that effect.

Wasmtime GitHub notifications bot (Jul 24 2026 at 18:23):

cfallin commented on PR #13919:

(And yes, the "by one other instruction" bit is what makes it a structural property beyond just use-counts -- we need to know which other instruction, so it's more or less a HashMap<Inst, Inst> indicating "which instruction am I subordinate under")

Last updated: Jul 29 2026 at 05:03 UTC