Cranelift: compiling a module with many allocating global initializers is superlinear under the copying collector, and v48 makes it several times worse

[gfx]

Test Case (with a WAT generator)

A module that is nothing but N globals whose initializers allocate a GC struct. No functions, no imports, no data segments.

// gen.mjs — node gen.mjs <N> > repro.wat
const n = Number(process.argv[2] ?? 500);
const out = ['(module', '  (type $node (struct (field $val i32) (field $tag i32)))'];
for (let i = 0; i < n; i++) {
  out.push(`  (global $g${i} (ref $node) (struct.new $node (i32.const ${i}) (i32.const 0)))`);
}
out.push(')');
process.stdout.write(out.join('\n') + '\n');

Steps to Reproduce

• node gen.mjs 1000 > repro.wat
• wasmtime compile -o /dev/null repro.wat — all defaults; since Kotlin benchmarks fails with memory allocation when collector is not drc #13756 the default collector is copying, so nothing needs to be turned on.
• Repeat for N = 250, 500, 1000, 2000, and compare against -C collector=drc.

Expected Results

Compile time grows linearly in N, as it does with -C collector=drc.

Actual Results

Compile time is superlinear in N. Wall time of wasmtime compile, aarch64 macOS, release build of main (0ac37df998):

N	copying	drc	copying, per doubling
250	0.17 s	0.01 s	—
500	1.01 s	0.01 s	5.9x
1000	8.6 s	0.04 s	8.5x
2000	67.0 s	0.12 s	7.8x

Module::new on x86_64 Linux, OptLevel::Speed, comparing releases:

N	47.0.3 copying	48.0.1 copying	48.0.1 drc	48 / 47
250	0.082 s	0.244 s	0.015 s	3.0x
500	0.424 s	1.63 s	0.031 s	3.8x
1000	2.65 s	12.5 s	0.065 s	4.7x
2000	21.96 s	96.4 s	0.134 s	4.4x

drc is linear; copying is superlinear on both 47 and 48 — the superlinearity is not new in 48, but 48 raises both the constant and the exponent, and that is what takes a real module from "slow" to "does not finish":

Real 1.8 MB component	Component::new
47.0.3 copying	5.2 s
48.0.1 copying	not finished after 14 min (killed)
48.0.1 drc	8.0 s

That component is a generated SQLite-grammar parser whose constant data is globalized into ~2500 struct.new and ~2500 array.new global initializers. Stubbing every function body in it to unreachable leaves the blowup intact, which is what pointed at the globals.

Versions and Environment

Wasmtime version or commit: 48.0.1 (cranelift-codegen 0.135.1) and main at 0ac37df998, compared against 47.0.3 (0.134.3)

Operating system: Linux (48.0.1 / 47.0.3 numbers), macOS 26 (main numbers)

Architecture: x86_64 and aarch64

Extra Info

Where the time goes. Effectively every sample of the compiling thread lands in the alias-analysis fixpoint. sample on main at N=2000, top of stack:

cranelift_codegen::alias_analysis::observe               1803
cranelift_codegen::alias_analysis::LastStores::meet_from  880
cranelift_codegen::alias_analysis::LastStores::update     718
cranelift_codegen::alias_analysis::AliasAnalysis::new      72

all under AliasAnalysis::new ← Context::optimize. On the real component the time is in LastStores::update rather than meet_from — same pass, same caller. -O opt-level=0 skips optimize, and the blowup with it; -C collector=null does not show it either.

Reading of the cause. LastStores.regions is a SecondaryMap<AliasRegion, PackedOption<Inst>>, and both consumers walk every region:

• LastStores::observe_others (cranelift/codegen/src/alias_analysis.rs) iterates self.regions for each trapping store.
• LastStores::meet_from (cranelift/codegen/src/alias_analysis.rs) iterates 0..max(regions.keys().len(), rhs.regions.keys().len()) for each CFG edge.

AliasRegion is an unbounded u32 entity, and since #14115 Wasmtime gives each statically-known entity its own region — AliasRegionKey::DefinedGlobal { module, index } in crates/cranelift/src/alias_region.rs — so N globals means N regions. All of the initializers land in one synthesized function (FuncEnvironment::module_initialize_global, crates/cranelift/src/func_environ.rs), giving N stores × N regions before the block fixpoint multiplies it again.

That also fits the copying/drc split: the copying collector's allocation sequence stores through a trapping path, so each one takes the full observe_others walk, while drc's barriers stay out of it.

The 48-specific part is presumably the dead-store elimination landed in #13806 / #13947 (closing #4167): the pass grew a whole-function observed_stores map that observe now writes on every one of those walks. #13806 measured a small compile-time cost on some Sightglass benchmarks and #13947 reports that recovered; a module with thousands of globals is far outside what those benchmarks cover.

[cfallin]

cc @fitzgen

@gfx, a few thoughts:

• I'd ask you to please review our AI usage policy and confirm here that the body of this issue is not written by an LLM.
• The O(|regions| * |program|) cost is kind of fundamental to the alias analysis now that we've added an arbitrary number of regions; we need to track last-writer for every region at every program point. There are always constant factors to improve and perhaps if the information is sparse (most regions don't have a non-default last-writer in most locations) we could use different data structures. I'll bring this up in the Cranelift meeting today to see if folks have thoughts.
  • To make a fine point of this, "superlinear in program size" is going to be a fundamental property of an optimizing compiler. Restricting ourselves to linear-time algorithms only would result in something like a baseline compiler, which we already have (Winch).
• I see your companion PR cranelift: fix cubic compile time for modules with many allocating globals #14211 that claims to fix this via a traversal-order change. It seems to improve convergence time but not change the asymptotics of the data structure size. I think the above data-structure optimizations are still important.

[gfx]

@cfallin

I've read the policy. The body of this issue was AI-assisted, so no.

I hit this in my own project, the narrowing (with wasm-tools shrink) and the measurements in it are mine, and I can answer questions about them.

The PR (#14211) is a different matter. It is also AI-assisted, and I don't have enough understanding of Cranelift to defend its design in review. Please treat it as a data point rather than as a contribution, and close it if it isn't useful to you. I'm here as a wasmtime user trying to get my project working again.