Wasmtime GitHub notifications bot (May 15 2026 at 20:55): Wasmtime GitHub notifications bot (May 15 2026 at 20:55):fitzgen opened PR #13391 from fitzgen:issue-13365-branch-optimizations-bug-take-2 to bytecodealliance:main:
We previously removed a block from the CFG if it was not marked as reachable by the time the egraph pass visited it. The pass's traversal is both (1) a depth-first pre-order dominator traversal, and (2) a reverse post-order CFG traversal. This traversal visits all of a block's non-back edge predecessors before visiting the block itself. For reducible control flow, this is all that is necessary because we've already visited every back edge's target block already.
However, for irreducible control flow, blocks can be reachable only through back edges, and so the traversal's property alone was not sufficient. (The
EgraphBlockIter's proof is still correct, at least to the best of my knowledge since we haven't mechanically proven it, but the implicit assumption that its proven property is sufficient for our reachability-based block removal is incorrect in the face of irreducible control flow.)This commit's fix is to stop removing newly-unreachable blocks in the middle of the egraphs pass, and instead simply call
eliminate_unreachable_codeafter the egraph pass completes to remove any code that became unreachable after branch simplification.Fixes https://github.com/bytecodealliance/wasmtime/issues/13365
<!--
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.htmlPlease ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->
Wasmtime GitHub notifications bot (May 15 2026 at 20:55):fitzgen requested wasmtime-compiler-reviewers for a review on PR #13391.
Wasmtime GitHub notifications bot (May 15 2026 at 20:55):fitzgen requested wasmtime-core-reviewers for a review on PR #13391.
Wasmtime GitHub notifications bot (May 15 2026 at 20:55):fitzgen requested cfallin for a review on PR #13391.
Wasmtime GitHub notifications bot (May 15 2026 at 21:19)::repeat: cfallin submitted PR review:
Thanks. I think we'll need to change the design here: this is making elaboration more complex (to be tolerant of unreachable code) and then doing DCE; I would have expected us not to elaborate unreachable blocks, instead.
Wasmtime GitHub notifications bot (May 15 2026 at 21:19)::speech_balloon: cfallin created PR review comment:
This also feels somewhat like a papered-over issue: why are we calling
elaborate_eclass_useon a value that ends up coming from an unreachable block? Isn't that a case of invalid IR (or incorrect unreachable-calculation)?
Wasmtime GitHub notifications bot (May 15 2026 at 21:19)::speech_balloon: cfallin created PR review comment:
Ah, maybe this is the source of the confusion above; I had assumed we would eliminate unreachable blocks by calculating which blocks are unreachable, and not elaborating them. Here we're trying to make elaboration unreachable-proof (with a lot of
None-case handling) and then deleting code later; that feels somewhat backwards to me.
Wasmtime GitHub notifications bot (May 15 2026 at 21:19)::speech_balloon: cfallin created PR review comment:
Is this (
reserved_valuefor a use) reachable? I would have expected the topo-sort not to even queue up unreachable/removed values during this computation...
Wasmtime GitHub notifications bot (May 15 2026 at 21:27)::memo: fitzgen submitted PR review.
Wasmtime GitHub notifications bot (May 15 2026 at 21:27)::speech_balloon: fitzgen created PR review comment:
Yeah we could effectively duplicate and inline
eliminate_unreachable_codein the egraph pass, before elaboration. I opted not to, preferring to reuse existing passes, but that does introduce its own problems. Can look into tweaking this next week.
Wasmtime GitHub notifications bot (May 16 2026 at 00:01):github-actions[bot] added the label cranelift on PR #13391.
Wasmtime GitHub notifications bot (May 18 2026 at 17:57):fitzgen updated PR #13391.
Wasmtime GitHub notifications bot (May 18 2026 at 17:58):fitzgen commented on PR #13391:
@cfallin I updated the PR to call
eliminate_unreachable_codein the middle of the egraph pass, after optimizing and removing instructions, but before elaboration. Probably easiest to look at the complete diff, rather than per-commit.
Wasmtime GitHub notifications bot (May 18 2026 at 17:58):fitzgen requested cfallin for a review on PR #13391.
Wasmtime GitHub notifications bot (May 18 2026 at 18:08)::thumbs_up: cfallin submitted PR review:
LGTM, thanks!
Wasmtime GitHub notifications bot (May 18 2026 at 18:08):cfallin added PR #13391 Handle irreducible control flow in branch simplification to the merge queue.
Wasmtime GitHub notifications bot (May 18 2026 at 18:33)::check: cfallin merged PR #13391.
Wasmtime GitHub notifications bot (May 18 2026 at 18:33):cfallin removed PR #13391 Handle irreducible control flow in branch simplification from the merge queue.
Last updated: Jun 01 2026 at 09:49 UTC