Module stack_depth 

RQ-71-STACKDEPTH (#1341): a SOUND per-export maximum native stack depth for a --relocatable object.

WHY THIS IS A SIBLING PASS AND NOT A FIELD ON THE WCET INTERMEDIATE. The reporter proposed reusing --emit-wcet’s traversal, and the TRAVERSAL is right — a memoized DFS over the direct call graph with honest declines for recursion, cycles, call_indirect and external callees. Two things are not:

1. THE ARITHMETIC. crate::wcet_compose composes total = own + Σ_site multiplier × total(callee), where multiplier is the site’s PROVEN EXECUTION COUNT. A callee invoked 1000 times inside a proven loop costs 1000× the cycles and once the stack: frames are popped between calls. Stack depth is a MAX over the call tree, never a trip-weighted sum. Reusing the composer unchanged would over-report by orders of magnitude, and over-reporting is not the safe direction — an embedder told to reserve 2 MB for a 2.3 KB requirement stops believing the number, which is its own failure.

2. THE DECLINE SET. WcetDecline includes Loop, LoopedExpansion, UnmodeledOp and UnresolvedBranch. None of those affect stack depth: a data-dependent loop is WCET-unbounded and perfectly stack-bounded, because the loop body’s frame is the same frame every trip. Riding on the WCET decline would refuse a bound for most real modules — including the reporter’s, whose control loop is exactly that shape.

WHAT A FRAME ACTUALLY COSTS, measured rather than assumed. The prologue moves SP in up to three separate steps:

  push.w { r4-r8, lr }      24 B   DIRECT_PROLOGUE_BYTES — ALWAYS present
  vpush  { d8-d15 }         64 B   only when the AAPCS VFP half is in play
  sub.w  sp, sp, #0x20      32 B   only when frame_size > 0

Summing only the sub sp — the obvious reading, and the one #1341 reports — misses the callee-saved push entirely AND misses every function whose frame_size is 0, which emits no sub sp at all while still consuming 8 or 24 bytes. On stack_depth_branch_1341.wat that method gives 96 B against a true 120 B: a 20 % UNDER-report, in the direction that corrupts memory. (The immediate is also printed in HEX — #0x20 is 32, and a #[0-9]+ regex silently reads it as 0.)

So this pass walks the EMITTED STREAM — the artifact we ship, not a model of it — and tracks the running SP delta, taking the maximum over every instruction boundary. That covers transient PUSH/POP inside encoder expansions (I64Popcnt, I64Rotl, I64Rotr really do emit them) without enumerating which ops those are, and it is why the answer is a maximum rather than a prologue reading.

ANY SP MOVEMENT THIS WALKER CANNOT PRICE DECLINES. The give-up direction is StackDecline::UnknownSpMove; a silent lower bound would reproduce the exact defect being reported.

Structs

StackFrame

One function’s own stack behaviour, before composition.

Enums

StackDecline

Why no finite stack bound exists. Deliberately NOT WcetDecline: the two sets differ (see the module docs), and sharing the enum would silently tie a stack refusal to a cycle-counting one.

StackResult

The settled answer for one function.

Functions

analyze_function

Walk one function’s FINAL emitted stream and record its own stack profile.

compose

Compose per-function profiles into a per-function maximum over the call tree: total(f) = own(f) + MAX over call sites of total(callee).