Stream: git-wasmtime

Topic: wasmtime / PR #14211 cranelift: fix cubic compile time fo...

Wasmtime GitHub notifications bot (Aug 26 2026 at 14:31):

gfx opened PR #14211 from wado-lang:gfx/alias-analysis-rpo-worklist to bytecodealliance:main:

Fixes #14210.

AliasAnalysis::compute_block_input_states drains its worklist LIFO, so on a
branch it runs the entire tail of the function off of one successor before it
looks at the other, and then redoes that tail once the second predecessor
updates the join point. A module whose globals all allocate compiles to one
synthesized initializer that is a long chain of diamonds, where that means each
block is visited O(N) times and each visit walks O(N) alias regions. Ordering
the worklist by reverse postorder converges in a single pass instead.

Compiling a module of N struct.new global initializers under the copying
collector; compile times for ordinary modules are unchanged:

N	before	after
250	0.17 s	0.01 s
500	1.01 s	0.03 s
1000	8.6 s	0.08 s
2000	67.0 s	0.22 s

Note that visit order also affects the precision of the fixpoint, so this
changes generated code: tests/disas/gc/array-copy-with-fuel.wat now forwards
two loads it previously reloaded, and its expectation is updated here.

This does not make the pass linear. LastStores keeps a dense SecondaryMap
over alias regions, so it remains quadratic in the number of regions, which
starts to show again around N=8000.

Wasmtime GitHub notifications bot (Aug 26 2026 at 14:31):

gfx requested cfallin for a review on PR #14211.

Wasmtime GitHub notifications bot (Aug 26 2026 at 14:31):

gfx requested wasmtime-compiler-reviewers for a review on PR #14211.

Wasmtime GitHub notifications bot (Aug 26 2026 at 14:31):

gfx requested wasmtime-core-reviewers for a review on PR #14211.

Wasmtime GitHub notifications bot (Aug 26 2026 at 15:04):

cfallin commented on PR #14211:

Note that visit order also affects the precision of the fixpoint

This is pretty deeply concerning. The fixpoint should converge to exactly the same answer no matter the visit order, because we have defined a lattice and we reprocess blocks when their input states change. Can you detail your thoughts here?

Wasmtime GitHub notifications bot (Aug 26 2026 at 16:04):

gfx commented on PR #14211:

Sorry, that sentence was misleading.

The disagreement arm of LastStores::meet_from yields Some(loc) -- the
successor's own first instruction -- rather than a bottom element. Once a
slot holds that value, the meet yields it again against every other input,
and reports no change.

I instrumented compute_block_input_states to dump the converged
block_input and ran tests/disas/gc/array-copy-with-fuel.wat under both
orders. For u0:0 they converge to different states. block6 has exactly
one predecessor, block5, yet under the current LIFO order its last store
for regions 6 and 7 is inst102, block6's own first instruction; under RPO
it is inst154, block5's.

The two loads in the expectation follow from that. They read region6 v162
and region7 v163, exactly what block5 already loaded, so last_store is
the only part of the MemoryLoc key that differs.

I also ran a variant that keeps per-block out-states and recomputes in[B]
from all predecessors' current ones instead of meeting in place. block6
then agrees under both orders, but block1, block7, block8 and block9
still differ.

Three of those four configurations -- LIFO or RPO, meet-in-place or
recompute -- produce the new expectation for this test; only today's
LIFO/meet-in-place produces the two extra loads. observed_stores for
u0:0 is identical under both orders.

I'll reword the description accordingly: the fixpoint isn't unique, and the
old order picked a worse one.

Wasmtime GitHub notifications bot (Aug 26 2026 at 16:06):

gfx edited a comment on PR #14211:

Sorry, that sentence was misleading.

The disagreement arm of LastStores::meet_from yields Some(loc) -- the
successor's own first instruction -- rather than a bottom element. Once a
slot holds that value, the meet yields it again against every other input,
and reports no change.

I instrumented compute_block_input_states to dump the converged
block_input and ran tests/disas/gc/array-copy-with-fuel.wat under both
orders. For u0:0 they converge to different states. block6 has exactly
one predecessor, block5, yet under the current LIFO order its last store
for regions 6 and 7 is inst102, block6's own first instruction; under RPO
it is inst154, block5's.

The two loads in the expectation follow from that. They read region6 v162
and region7 v163, exactly what block5 already loaded, so last_store is
the only part of the MemoryLoc key that differs.

I also ran a variant that keeps per-block out-states and recomputes in[B]
from all predecessors' current ones instead of meeting in place. block6
then agrees under both orders, but block1, block7, block8 and block9
still differ.

Three of those four configurations -- LIFO or RPO, meet-in-place or
recompute -- produce the new expectation for this test; only today's
LIFO/meet-in-place produces the two extra loads. observed_stores for
u0:0 is identical under both orders.

What the description should have said: the fixpoint isn't unique, and the old order picked a worse one.

Wasmtime GitHub notifications bot (Aug 26 2026 at 18:17):

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

Last updated: Aug 30 2026 at 09:07 UTC