Stream: git-wasmtime

Topic: wasmtime / PR #14008 Do not eliminate inside-loop stores ...

Wasmtime GitHub notifications bot (Jul 28 2026 at 16:30):

fitzgen opened PR #14008 from fitzgen:dse-and-loops to bytecodealliance:main:

Stores inside a loop can be read on the next loop iteration by a load at the top of the loop, so they are not dead.

Because our main alias analysis pass happens online with its non-fix-point, single-iteration dataflow analysis, it cannot correctly handle loops on its own because its online nature doesn't delay rewrites until after loop back edges are discovered. The typical way to make a non-fixed-point analysis sound while keeping everything else in the system the same (i.e. not making the analysis require a full fixed point) would be to make the analysis more conservative, so that any store inside a loop is eagerly considered not dead. But this ends up being too pessimistic because of the online rewrites, which mean we can't wait until we actually see the backedge to conservatively mark such stores as potentially observed by future loop iterations; we have to effectively assume that every block has back edges we just haven't seen yet. This devolves into only doing dead-store elimination locally within a single block, never across blocks.

We can be more precise, without requiring fix-points, if we already know loop boundaries and nesting: we can reject a dead-store candidate whose overwriter lies outside a loop that contains the candidate, since that means, by definition, that the two are separated by a back edge, and the dead-store candidate might be observed by future iterations of the loop before the overwriter executes. Unlike the unduly pessimistic approach described previously, this still allows eliminating loop-free cross-block dead stores: if the dead-store candidate is not in a loop, or is in the same loop as its overwriter, then there is no back edge between them and our analysis's alias-region-observed bit is accurate.

And luckily, we do already have that loop information available via the LoopAnalysis that we already compute for the EgraphsPass to use during elaboration. This commit fixes the bug by reusing the LoopAnalysis inside AliasAnalysis.

Fixes #13990

<!--
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 (Jul 28 2026 at 16:30):

fitzgen requested cfallin for a review on PR #14008.

Wasmtime GitHub notifications bot (Jul 28 2026 at 16:30):

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

Wasmtime GitHub notifications bot (Jul 28 2026 at 16:47):

cfallin commented on PR #14008:

I think there may be a simpler approach: when we come to a back-edge, all stores in the carried flow-sensitive state are observed. That, too, (i) allows loop-free (within-loop) dead store elimination, (ii) fixes the soundness issue with a conservative approximation (but not too conservative), (iii) is single-pass. It's conceptually simpler, IMHO: rather than reasoning about where an analysis might be unsound post-hoc ("the conditions are otherwise met but they cross this kind of edge"), it covers the gap exactly where it comes in (edge to a block we've already analyzed and won't visit again, due to non-fix-point --> assume the worst).

And actually I think there's a related fixpoint soundness issue here that doesn't require loops at all:

        A
  /          \
C            D
 |  \      / |
 |   \   /   |
 |     X     |
 |  /     \  |
 E           F

in this CFG, we might process in order A, C, E, D, F; when processing D, we have the edge D->E but we've already processed E, so we won't re-process it and potentially mark stores in D as observed.

So I think we need to actually take any edge to a block we've already processed as a conservative "observes every store" edge. That both solves the loop issue in #13990 and addresses the CFG here. What do you think?

Wasmtime GitHub notifications bot (Jul 28 2026 at 18:05):

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

Wasmtime GitHub notifications bot (Jul 28 2026 at 21:10):

fitzgen commented on PR #14008:

when we come to a back-edge, all stores in the carried flow-sensitive state are observed.

The problem with this approach is that it involves large changes to the way that AliasAnalysis operates and integrates with the egraphs pass. Right now, it makes its changes online, as we analyze each instruction. By the time we see a back edge, and retroactively mark all the stores as observed, it's already too late because the rewrites happened already (the "dead" stores have already been removed).

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

cfallin commented on PR #14008:

I don't think I understand: how is "this edge observes all stores in the memory state" different from "the forward scan suddenly encountered lots of loads"? In other words, we are not going back and editing anything; we are setting a bit on downward-exposed stores, exactly those which have not yet encountered a possibly-overwriting store.

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

cfallin commented on PR #14008:

(I believe it's also necessary in the presence of the CFG I drew above -- even without loops)

Last updated: Jul 29 2026 at 05:03 UTC