Stack maps vs the codegen shadow stack: viability experiment (Q1 passes; 0.44 MB text saved for 4.5-16.6 MB metadata) #7108

Scoped viability experiment, not a migration. No shadow-stack code was changed. Throwaway prototype on exp/stackmap-viability (worktree wt-stackmap), which is not intended to merge.

Verdict: Q1 passes, but on the numbers I would not migrate for size or speed. The correctness argument is the only one that survives contact with the measurements — and it is a strong one.

The headline trade, measured on a real dependency-heavy build:

That is 10–38× more cold metadata than hot text saved, and the metadata alone exceeds the app's entire generated code section (3.7 MB). Reported separately and deliberately not netted.

Perry's LLVM version

Perry has no LLVM crate dependency. perry-codegen writes textual .ll and shells out to clang -c (crates/perry-codegen/src/linker.rs:1). So "Perry's LLVM version" is whichever clang is resolved by find_clang(), floored at MINIMUM_CLANG_MAJOR = 15 (linker.rs:660).

• This host: Apple clang 21.0.0 (clang-2100.1.1.101), target arm64-apple-darwin25.5.0.
• Also present: Homebrew LLVM 22.1.4.
• Stackmap format emitted: v3. Darwin section: __LLVM_STACKMAPS,__llvm_stackmaps.

This matters for the whole assessment and is revisited under "migration cost" — the text-IR-plus-stock-clang architecture is what rules the cheapest design out.

Q1 — Can statepoint/stackmap machinery describe a NaN-boxed value?

Yes, by exactly one route out of four. All four were compiled, not read about.

The two traps worth naming

gc-live with a double compiles clean and records nothing. No warning, no verifier error. A prototype built this way would appear to work and would lose every root. Compare the location counts — 3 (header only) versus 5 for the pointer control.

The deopt bundle looks right and is not. It does record the double at an Indirect stack slot, which is why it is tempting. But the mutator does not read that slot:

str  d0, [sp]        ; LLVM's own spill for the live value
str  d0, [sp, #0x8]  ; the deopt record slot (what the stackmap points at)
bl   callee
ldr  d0, [sp]        ; reloads from [sp] — NOT the recorded slot

Collector-side rewrite of the recorded slot is a no-op. Deopt values are a read-only snapshot for a deoptimiser reconstructing an interpreter frame, not for resuming compiled code.

llvm.experimental.stackmap is not the promising lead it looks like. It records at its own location, not at the call's return address, so a stackmap placed after a call describes post-reload registers (Register R#64, R#65) — the wrong program point, and register locations a collector cannot rewrite. The call is the safepoint; only statepoint (or patchpoint) describes the frame during it. So "stackmap + collector-side rewrite" is not a viable simpler design, for a reason independent of NaN boxing.

The design that works

Carry the entire NaN box through the safepoint as ptr addrspace(1) — bitcast double → i64 → inttoptr — with no untagging. The collector inspects the tag and re-tags when it rewrites, which is what it already does for shadow slots today.

%ab  = bitcast double %a to i64
%ap  = inttoptr i64 %ab to ptr addrspace(1)
%tok = call token (...) @llvm.experimental.gc.statepoint.p0(...) [ "gc-live"(ptr addrspace(1) %ap) ]
%ar  = call ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token %tok, i32 0, i32 0)
%ai  = ptrtoint ptr addrspace(1) %ar to i64
%ad  = bitcast i64 %ai to double

Three NaN boxes live across a call at -O3 lower to two stores and two loads (stp/ldp pairs) — LLVM sees through the whole bitcast/inttoptr/ptrtoint/bitcast chain and keeps the values in FP registers. The address-space round trip costs zero instructions; there is no fmov GP↔FP shuffling.

Proven end-to-end at runtime, not just compiled. A collector that parses the real __llvm_stackmaps section, applies Perry's own tag discipline, and rewrites the recorded slots:

BEFORE: a=0x7ffd000001234000 (ptr box)  b=0x400921f9f01b866e (double 3.14159)
COLLECTOR:   loc#4 Indirect[R#31+8] bits=0x400921f9f01b866e  (not heap-tagged, left alone)
COLLECTOR:   loc#6 Indirect[R#31+0] bits=0x7ffd000001234000  -> REWROTE to 0x7ffd000001235000
AFTER : out[0]=0x7ffd000001235000  out[1]=0x400921f9f01b866e (=3.141590)

RESULT: relocated pointer observed by mutator: YES
RESULT: plain double survived untouched:        YES

The pointer-tagged box was relocated and the mutator observed the new value after the safepoint; the plain double 3.14159 — bit pattern indistinguishable from a pointer to anything but a tag check — was correctly left alone. This is precisely the semantics a moving collector needs, and it composes with Perry's existing tag-inspection logic rather than replacing it.

Supporting facts, all compiled

• Inlining survives. An internal function containing a statepoint inlines fully at -O3 with its gc-live bundle intact. Statepoints do not block Perry's reliance on LLVM inlining.
• The linker concatenates per-object stackmaps. Three objects → three sub-stackmaps at offsets 0/200/400, no dedup. A 133-module app yields 133 sub-maps; the runtime parser must iterate them (mine does).
• LLVM prunes dead roots automatically. A gc-live value whose relocate is unused is dropped from the record entirely. Liveness precision comes free — and it is also why a naive size model overestimates.
• No built-in GC strategy avoids the base/derived doubling. statepoint-example, coreclr and shadow-stack all emit 3 + 2N locations; erlang/ocaml have no GCMetadataPrinter on this target. The 2× on the dominant metadata term is unavoidable with stock clang.

Q2 — What the metadata weighs

Application: test-drizzle-pg — drizzle-orm + @perryts/postgres compiled natively via compilePackages. 133 modules, 4,735 emitted functions, 1,535 (32.4%) with GC roots, 4,808 reserved root slots, 62,731 candidate safepoints. Chosen because benchmarks/app-patterns is 435 lines total across 12 kernels — far too small, exactly the smallness that hid the size axis before.

Host: Apple M1 Max, 10 core, macOS 26.5. All Q2/Q3 figures are static section sizes and are independent of machine load (which ranged 35–137 during the session, from two other agents building).

The size model is exactly validated against a compiled 20-function × 7-safepoint × 3-root module: modelled 19,536 B, measured 19,536 B, 0.00% error.

bytes = 16·objects + 24·functions + 64·safepoints + 24·(safepoint,root) pairs

The 24 B per root per safepoint is the dominant term — 2 locations × 12 B, because every root is recorded as a base/derived pair.

Per the brief: this is the worst case and I am saying so explicitly. Representation selection currently promotes zero locals on real application code (#7034), so essentially every recorded slot is "might be a pointer". If repsel lands, the root count — and therefore the dominant term — falls proportionally. The realistic band today is 4.5–11 MB, and the true figure sits toward the lower end because LLVM's own liveness prunes dead roots (proven above).

For scale: the app's entire generated __text is 3.7 MB. The root metadata is 1.2× to 4.5× the size of all the code it describes.

Q3 — What __text shrinks by

Same application, same compiler binary, differing only by PERRY_SHADOW_STACK — which already exists (crates/perry-codegen/src/codegen/helpers.rs:66). Measured at e2557c1a9 (current main, includes #7088).

Generated code only, by compiling the 133 traced .ll modules directly, so the ~9.6 MB Rust runtime is excluded rather than diluting the ratio:

Whole-binary __text delta for the same pair: 387,376 B (21,806,836 → 21,419,460). The two differ because the linker dead-strips and because I compiled every traced module at -O3 whereas Perry varies opt-level per module size; both land in the same range.

A statepoint build's text would sit at approximately the OFF arm: across 1–16 roots live across a call, the statepoint form costs ≈0 extra instructions versus not rooting at all (at 8 and 16 roots it is actually fewer, because forced stack slots beat callee-saved register preservation). Values live across a call must be spilled regardless; statepoints make the spill the only cost.

Not measured: I did not build a statepoint backend, so the statepoint arm's app __text is inferred from the OFF-arm floor plus the microbenchmark, not measured directly. Stated plainly rather than dressed up.

An unrelated finding that the brief predicted

#7088's inline slot store costs +189,892 B of __text on this app (21,806,836 with PERRY_INLINE_SHADOW_SLOT default vs 21,616,944 with it off). That is 43% of the shadow stack's entire text footprint, spent to make it faster — and it merged with no size measurement of any kind, because binary-size never runs on PRs. The brief called this axis unobserved; it was, and here is the number. Worth a separate look independent of anything in this experiment.

The correctness argument — the strongest one here

Supported, and it is the reason to keep this alive.

The bug class is not hypothetical, and the codebase already documents it against itself. crates/perry-codegen/src/expr/shadow_slot.rs:14, on %this_closure (#7055):

The parameter is a register value the collector cannot see: an evacuating young collection at a loop back-edge poll inside the body relocates the closure, rewrites every root it knows about, and then resets from-space — after which the register points at recycled memory […] and every subsequent boxed-capture read/write silently no-ops.

Every one of #7055 and #7066 is a human forgetting to bind a slot. With statepoints, LLVM enumerates its own live SSA values: a value live across a call is in the gc-live set because it is live, not because someone remembered. %this_closure is an ordinary LLVM parameter and would be covered automatically. Probe G confirms the enumeration is precise in both directions — dead roots are dropped, so the mechanism does not over-root either.

Two honest qualifications:

1. Hand-emitted statepoints reintroduce a different human-error class. After a safepoint, every downstream use must reference the relocated value. Miss one and you have a stale pointer — the same shape of bug, relocated to a new place. My own first inlining probe made exactly this mistake within minutes of writing it.
2. Only RewriteStatepointsForGC removes that class too. RS4GC takes naive IR with addrspace(1) values and inserts the statepoint, the gc.result, the gc.relocate, and rewrites all downstream uses. Perry would only need to mark GC-capable values and tag functions gc "statepoint-example".

So the full correctness win requires RS4GC. Which brings the problem:

What a real migration would cost

Toolchain is the binding constraint, not the codegen.

• clang exposes no flag that runs RS4GC — -mllvm -passes=… is rejected outright.
• Xcode ships no opt. Only Homebrew LLVM has it.
• The opt -passes=rewrite-statepoints-for-gc | clang -c pipeline does work end-to-end (verified, correct stackmap with Indirect locations).

Perry today requires only a clang ≥ 15 on PATH. The cheap, correctness-maximal design requires shipping or requiring opt — a new hard dependency on a ~100 MB binary that must version-match. That is a distribution decision, not an engineering one, and it is the single biggest cost.

Roughly, and only enough for a go/no-go:

1. Ship/require opt, mark values addrspace(1), let RS4GC do the rest — smallest codegen change, full correctness win, new toolchain dependency. Weeks.
2. Hand-emit statepoints in perry-codegen — no new dependency. Call emission is already centralised (LlBlock::call/call_void, block.rs:830/:844) and liveness already tracked (FnCtx::shadow_slots_bound), so the emission side is tractable. But Perry must do the SSA relocation rewiring itself, which is where the correctness win partly evaporates. Months, and it re-opens the bug class it was meant to close.
3. Link LLVM as a library — contradicts the text-IR architecture wholesale. Not costed.

Beyond the toolchain, one hard requirement applies to every option: the collector needs a stack walker. Today js_shadow_frame_enter/pop maintain an explicit list the collector reads directly. With statepoints the collector must unwind from wherever GC triggered (deep in a Rust helper) back through native frames to compiled frames, and map each return address to a stackmap record. That needs guaranteed frame pointers through the Rust runtime (-Cforce-frame-pointers=yes; arm64 macOS already has them, x86-64 Linux does not by default), a sorted return-address index built at startup across all sub-stackmaps, and correct SP reconstruction per frame. This is new, load-bearing, platform-sensitive machinery with no current equivalent, and conservative scanning is not available as a fallback (SkipDisabled in production, being removed).

Not measured — stated rather than estimated:

• No statepoint backend was built, so no app-level statepoint __text, and no runtime performance number of any kind. The +26.7% instruction figure motivating this line was not re-measured or contested here.
• Whether Perry's setjmp-based EH (setjmp_abi.rs, volatile_setjmp.rs) composes with statepoints — untested, and a plausible source of trouble given values live across setjmp have memory constraints.
• Stack-walker cost, both the startup index build and per-collection walk.
• Non-Darwin behaviour. Everything here is arm64 macOS; the __LLVM_STACKMAPS section spelling and frame-pointer availability both differ elsewhere.

Where I think this lands

Q1 passes cleanly and the design is real — but on the numbers, stack maps are not a size win and not a speed win. They trade 0.44 MB of hot text for 4.5–16.6 MB of cold metadata, and the "avoids the size trade-off" premise that made them attractive does not survive measurement: the metadata is larger than all the code it describes. It is a different size problem, not the absence of one.

What does survive is correctness. Making an entire bug class structurally impossible is worth real cost, and #7055/#7066 are evidence that cost is already being paid in bugs. But the version that actually delivers it (RS4GC) requires a toolchain dependency Perry has deliberately avoided, and the version that avoids the dependency re-opens the bug class it was meant to close.

Suggested disposition: do not migrate now. Revisit if either premise changes — if repsel (#7034) starts promoting locals, the dominant metadata term shrinks proportionally; or if Perry ever links LLVM directly, at which point RS4GC is free and the calculus is entirely different. The PERRY_SHADOW_STACK=0 A/B and the size model are cheap to re-run against either.