Wasmtime GitHub notifications bot (May 15 2026 at 12:45): Wasmtime GitHub notifications bot (May 15 2026 at 12:45):fitzgen requested cfallin for a review on PR #13385.
Wasmtime GitHub notifications bot (May 15 2026 at 12:45):fitzgen opened PR #13385 from fitzgen:issue-13365-branch-optimization-bug 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 only remove blocks when they haven't been marked reachable and all of its predecessors have been visited (this latter bit being the thing that irreducible control flow broke). To implement this, we pass in the already-computed
ControlFlowGraphfrom theContextinto theEgraphPassso that we can easily iterate of a block's predecessors.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 12:45):fitzgen requested wasmtime-compiler-reviewers for a review on PR #13385.
Wasmtime GitHub notifications bot (May 15 2026 at 16:18):github-actions[bot] added the label cranelift on PR #13385.
Wasmtime GitHub notifications bot (May 15 2026 at 16:43):cfallin commented on PR #13385:
I guess I come back to the point I made here: we now have a pretty complex approach (with a very intricate proof, to your credit!) that only mostly satisfies the requirements, but (with this patch) will sometimes not fully DCE dead branches. On the other hand, if we had a separate DFS-over-blocks to find reachable blocks, we would (with a pretty simple implementation we could be pretty certain about) have correct reachable-code computation in all cases, without having to conservatively over-approximate and leave some dead code in place. Perhaps we should consider that approach again? Can we at least measure its compile-time impact?
Wasmtime GitHub notifications bot (May 15 2026 at 17:01):fitzgen commented on PR #13385:
Yeah, I thought about that too. I'll investigate a little.
Wasmtime GitHub notifications bot (May 15 2026 at 20:56):fitzgen commented on PR #13385:
I guess I come back to the point I made here: we now have a pretty complex approach (with a very intricate proof, to your credit!) that only _mostly_ satisfies the requirements, but (with this patch) will sometimes not fully DCE dead branches. On the other hand, if we had a separate DFS-over-blocks to find reachable blocks, we would (with a pretty simple implementation we could be pretty certain about) have correct reachable-code computation in all cases, without having to conservatively over-approximate and leave some dead code in place. Perhaps we should consider that approach again? Can we at least measure its compile-time impact?
https://github.com/bytecodealliance/wasmtime/pull/13391
Haven't done any perf measurements yet though.
Wasmtime GitHub notifications bot (May 18 2026 at 18:16)::cross_mark: fitzgen closed without merge PR #13385.
Wasmtime GitHub notifications bot (May 18 2026 at 18:16):fitzgen commented on PR #13385:
Closing in favor of https://github.com/bytecodealliance/wasmtime/pull/13391
Last updated: Jun 01 2026 at 09:49 UTC