Stream: git-wasmtime

Topic: wasmtime / PR #14080 Do not DSE on paths that can diverge

Wasmtime GitHub notifications bot (Aug 05 2026 at 15:10):

fitzgen opened PR #14080 from fitzgen:issue-14053 to bytecodealliance:main:

Divergent blocks (i.e. blocks that are part of an infinite loop) cannot exit the function via the CFG by definition, so our CFG-based post-domination check says that stores in divergent blocks cannot be observed outside the function and can be eliminated. However, divergent blocks can contain memory operations that implicitly trap, which is a function exit that is not expressed in the CFG and its post-dominator tree, so DSE cannot rely solely upon CFG-based post-dominance.

This commit lazily computes the set of blocks that can lead to divergence (computed at the same time as when we force computation of the post-dominator tree) and if the DSE candidate store is on a block that diverges, or can lead to divergence, we decline to perform DSE. This is conservative: we could additionally check for implicitly trapping instructions on the diverging path, and only disallow DSE when we see such an instruction. This commit doesn't do that because divergence is already rare, and the over approximation is simpler to implement. If, in the future, we find test cases that diverge, do not have loads or stores that implicitly trap on the diverging paths, and we care about their performance, then we can revisit this decision at that time.

As an alternative approach, we could modify PostDominatorTree to consider divergent blocks as additional reverse-CFG roots, i.e. function "exits", by adding virtual edges to the virtual sink node. This would "fix" post-dominance for DSE candidates in divergent blocks. But finding divergent blocks in the first place requires computing the post-dominator tree as we do today and enumerating blocks which are unreachable from the root in the reversed CFG, and afterwards we would then need to recompute the post-dominator tree with those nodes as roots the second time around. For what it's worth, this recomputation could be avoided by functions without divergence (which is most functions), and we could possibly do that recomputation incrementally, preserving the work that the first computation already did. This approach would avoid the lazily-computed can_diverge hash set in alias analysis and its allocation, but would still require an O(v) pass over the CFG, and I personally find it a bit more subtle/complex. Therefore, I've opted not to implement it in this commit, especially since the can_diverge set is already lazily computed, but we can always implement it in the future.

Fixes #14053

<!--
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 (Aug 05 2026 at 15:10):

fitzgen requested alexcrichton for a review on PR #14080.

Wasmtime GitHub notifications bot (Aug 05 2026 at 15:10):

fitzgen requested wasmtime-compiler-reviewers for a review on PR #14080.

Wasmtime GitHub notifications bot (Aug 05 2026 at 15:10):

fitzgen requested wasmtime-core-reviewers for a review on PR #14080.

Wasmtime GitHub notifications bot (Aug 05 2026 at 15:11):

fitzgen requested cfallin for a review on PR #14080.

Wasmtime GitHub notifications bot (Aug 05 2026 at 15:11):

fitzgen unassigned alexcrichton from PR #14080 Do not DSE on paths that can diverge.

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

cfallin commented on PR #14080:

Thanks for this -- very subtle bug here.

I think I have some concerns about the way in which we're reasoning carefully about divergent blocks, and patching conclusions on top of the core analysis, rather than getting the core analysis to give us the right answer from-first-principles. I worry that (especially given the chain of subtle bugs we've had here) we may miss something else, too; and even if not, it's very subtle and difficult to reason about and maintain.

Instead I think the crux of this comes back to this comment that describes why not to do the "store observes last store that it replaces in the abstract state" step I mentioned here (last point).

This would resolve the bug in a principled way because, entering any divergent loop, either a still-downward-exposed store meets a trapping op and is observed, or no traps ever occur and it is just an infinite loop (so is truly not observed). Basically we turn the last-store state into a may-alias rather than must-alias kind of state: any store that could actually be the most recent to a given memory location is either observed (so "committed" in some sense -- we won't remove it) or is in the flow-sensitive state of every path outward from it. The current lossy situation creates the hole that we have to plug instead, and I'm not confident that that's simple enough to reason about that we want to go there.

A question though: the comment linked above mentions some optimization opportunities that observe-store-we-overwrote-in-abstract-state would miss. Are there examples of that case that we know about?

Wasmtime GitHub notifications bot (Aug 05 2026 at 16:18):

fitzgen commented on PR #14080:

Instead I think the crux of this comes back to this comment that describes why not to do the "store observes last store that it replaces in the abstract state" step I mentioned here (last point).

This would resolve the bug in a principled way because, entering any divergent loop, either a still-downward-exposed store meets a trapping op and is observed, or no traps ever occur and it is just an infinite loop (so is truly not observed). Basically we turn the last-store state into a _may-alias_ rather than _must-alias_ kind of state: any store that _could_ actually be the most recent to a given memory location is either observed (so "committed" in some sense -- we won't remove it) or is in the flow-sensitive state of _every_ path outward from it. The current lossy situation creates the hole that we have to plug instead, and I'm not confident that that's simple enough to reason about that we want to go there.

A question though: the comment linked above mentions some optimization opportunities that observe-store-we-overwrote-in-abstract-state would miss. Are there examples of that case that we know about?

If I understand correctly, what you are proposing ultimately just entails removing that comment and observing the last-store instruction for the region at that comment's old location, correct?

modified   cranelift/codegen/src/alias_analysis.rs
@@ -211,40 +211,17 @@ impl LastStores {
         }
         // Store instructions: update the last-store information for this
         // instruction's alias region, or, if it has no alias region, treat it
         // as a fence.
         else if opcode.can_store() {
             if let Some(memflags) = func.dfg.insts[inst].memflags() {
                 match func.dfg.mem_flags[memflags].alias_region() {
                     Some(region) => {
-                        // NB: The old last-store instruction is *not* observed
-                        // here, even though this new store instruction may not
-                        // fully overwrite it. First, a new store in a block
-                        // does not itself observe an old store in the same
-                        // block. Second, the old store will never be an
-                        // optimization candidate again from here on out:
-                        //
-                        // * We won't consider it again as we process the rest
-                        //   of this block, as it won't be in the last-store
-                        //   slot anymore.
-                        //
-                        // * What if we re-process this block in our initial
-                        //   fixed point loop? That implies this block is a
-                        //   member of a cycle in the CFG, but `meet_from` only
-                        //   propagates a store instruction when all
-                        //   predecessors agree on the same last-store
-                        //   instruction, but the predecessors already won't
-                        //   agree it is the old store since this block (which
-                        //   is on that path and therefore some kind of
-                        //   transitive predecessor) has already overridden it.
-                        //
-                        // Therefore, marking the old last-store as observed
-                        // here is unnecessary (and, in fact, doing so would
-                        // only inhibit optimization).
+                        observe(func, observed_stores, self.regions[region]);
                         self.regions[region] = inst.into();

                         // If this store can trap, then we need to observe
                         // all other alias regions, to ensure that their state
                         // is preserved in the case that this store traps
                         // (similar to the `can_trap()` handling above).
                         //
                         // This prevents removing the first store in the

That diff does fix #14053 and passes the new tests added in this PR.

However, it fails with missed optimizations on 10 of our alias analysis filetests (maybe even more individual test failures than that, since filetests can have multiple functions/checks, but the runner bails on the first failure).

<details>

<summary>Full alias filetest failures</summary>

$ cargo run -p cranelift-tools -- test cranelift/filetests/filetests/alias/
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.41s
     Running `target/debug/clif-util test cranelift/filetests/filetests/alias/`
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
FAIL cranelift/filetests/filetests/alias/dead-store-cross-block.clif: optimize

Caused by:
    compilation of function on line 5 does not match
    the text expectation

    --- expected
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
    +++ actual
    @@ -2,6 +2,7 @@
         region0 = 0 "R0"

     block0(v0: i64, v1: i32, v2: i32):
    +    store notrap aligned region0 v1, v0
         jump block1

     block1:


    This test assertion can be automatically updated by setting the
    CRANELIFT_TEST_BLESS=1 environment variable when running this test.

[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: optimize
[2026-08-05T15:55:13Z ERROR cranelift_filetests::concurrent] FAIL: alias-analysis
FAIL cranelift/filetests/filetests/alias/stale-last-store-after-dead-store.clif: alias-analysis

Caused by:
    filecheck failed for function on line 10:
    #0 not: store notrap aligned region0 v1, v0
    #1 not: store notrap aligned region0 v2, v0
    #2 check: store notrap aligned region0 v3, v0
    #3 check: store notrap aligned region0 v3, v0+8
    #4 not: store
    > function %stale_after_dead_store(i64, i32, i32, i32) fast {
    >     region0 = 0 "R0"
    >
    > block0(v0: i64, v1: i32, v2: i32, v3: i32):
    >     store notrap aligned region0 v1, v0
          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Matched #0 not: \bstore notrap aligned region0 v1, v0\b
    >     store notrap aligned region0 v2, v0
    >     store notrap aligned region0 v3, v0
          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Matched #2: \bstore notrap aligned region0 v3, v0\b
    >     store notrap aligned region0 v3, v0+8
    >     return
    > }

FAIL cranelift/filetests/filetests/alias/crossing-merges.clif: optimize

Caused by:
    compilation of function on line 85 does not match
    the text expectation

    --- expected
    +++ actual
    @@ -2,6 +2,7 @@
         region0 = 0 "R0"

     block0(v0: i64, v1: i32, v2: i32, v3: i32):
    +    store notrap aligned region0 v1, v0
         brif v1, block1, block2

     block1:


    This test assertion can be automatically updated by setting the
    CRANELIFT_TEST_BLESS=1 environment variable when running this test.

FAIL cranelift/filetests/filetests/alias/idempotent-store.clif: optimize

Caused by:
    compilation of function on line 41 does not match
    the text expectation

    --- expected
    +++ actual
    @@ -2,6 +2,7 @@
         region0 = 0 "heap"

     block0(v0: i64, v1: i32, v2: i32):
    +    store region0 v1, v0+8
         store region0 v2, v0+8
         return
     }


    This test assertion can be automatically updated by setting the
    CRANELIFT_TEST_BLESS=1 environment variable when running this test.

FAIL cranelift/filetests/filetests/alias/dead-store-chain.clif: optimize

Caused by:
    compilation of function on line 6 does not match
    the text expectation

    --- expected
    +++ actual
    @@ -2,6 +2,9 @@
         region0 = 0 "R"

     block0(v0: i64, v1: i32, v2: i32, v3: i32, v4: i32):
    +    store notrap aligned region0 v1, v0
    +    store notrap aligned region0 v2, v0
    +    store notrap aligned region0 v3, v0
         store notrap aligned region0 v4, v0
         return
     }


    This test assertion can be automatically updated by setting the
    CRANELIFT_TEST_BLESS=1 environment variable when running this test.

FAIL cranelift/filetests/filetests/alias/dead-store-other-region.clif: optimize

Caused by:
    compilation of function on line 6 does not match
    the text expectation

    --- expected
    +++ actual
    @@ -3,6 +3,7 @@
         region1 = 1 "R1"

     block0(v0: i64, v1: i64, v2: i32, v3: i32, v4: i32):
    +    store notrap aligned region0 v2, v0
         store notrap aligned region1 v4, v1
         store notrap aligned region0 v3, v0
         return


    This test assertion can be automatically updated by setting the
    CRANELIFT_TEST_BLESS=1 environment variable when running this test.

FAIL cranelift/filetests/filetests/alias/no-region.cli
[message truncated]

Wasmtime GitHub notifications bot (Aug 05 2026 at 17:24):

cfallin commented on PR #14080:

Nick and I discussed briefly offline; to record for posterity:

• The issue is that the analysis runs in a separate phase before the editing pass, so store B overwriting store A also overwrites, hence observes, A, so nothing ever actually opts.
• My proposed tweak is to record which instruction observes; all we need for this is a 0-1-many lattice. If a given store is only ever observed by one other store (and all the other conditions are met) then we should be able to do the opt. We still want the general "removing from flow-sensitive state observes" for other cases for correctness, I think.

Wasmtime GitHub notifications bot (Aug 05 2026 at 18:37):

fitzgen updated PR #14080.

Last updated: Aug 30 2026 at 10:08 UTC