MIR Codegen: Full Stack Scheduling with Spilling

[gakonst]

Summary

Extend the stack scheduler to handle arbitrary control-flow and >16 live values with spilling into memory.

Parent issue: #687

Context

When more than 16 values are live simultaneously, we exceed the EVM's DUP/SWAP visibility window. Values must be spilled to memory (MSTORE) and reloaded (MLOAD) when needed.

Additionally, at control-flow merge points (block boundaries), we need consistent stack shapes so that jumps land with the expected stack layout.

This is the most complex piece of the codegen pipeline.

Tasks

Canonical stack shape at block boundaries

• Define boundary stack signature: ordered list of live-in values and positions
• Compute consistent signatures using fixpoint algorithm across CFG
• Propagate through successors, merge with minimal reshuffling

Prolog/epilog reshuffles

• At block entries/exits, emit reshuffling sequences (DUP/SWAP/drop/reload)
• Use Venom-style heuristics to minimize shuffles
• Treat stack like permuted list, generate near-optimal swaps

Memory spilling

• Choose memory region for spills (function-local "stack frame")
• Maintain mapping: SpillSlotId → memory_offset
• Extend AbstractStack:
  • When depth > 16 or heuristics suggest: pick value to spill
  • Emit MSTORE to spill slot, remove from abstract stack (keep logically live)
  • When spilled value needed: emit MLOAD, push to stack

Spilling heuristics

• Use next_use data from liveness to guide spilling
• Prefer spilling cold/long-lived values (used far in future)
• Avoid spilling values needed in multiple immediate successors

Loop and complex CFG handling

• Ensure boundary signatures converge in loops (worklist with limit)
• Verify stack shape identical on all paths entering loop header
• Handle early returns, multi-branch switches

Patterns to follow

From Venom:

• Full stack scheduler handling cross-block layouts and spilling
• Dataflow + abstract interpretation of stack state for jump-compatible layouts
• Liveness-driven dead value elimination

From Sonatina:

• Separation of analysis (compute signatures, next-use) from transformation (insert spills)

Example: Spilling

; 17 values live simultaneously
v0 = ...
v1 = ...
...
v16 = ...
v17 = ...      ; Stack overflow!

; With spilling:
v16 = ...
PUSH <spill_slot_0>
MSTORE         ; Spill v0 to memory[spill_slot_0]

; Later when v0 needed:
PUSH <spill_slot_0>
MLOAD          ; Reload v0

Acceptance Criteria

• Broad Solidity programs compile (nested conditionals, loops, early returns)
• No stack under/overflows in compiled code
• Debug assertions verify:
  • Stack depth and value ordering identical across predecessors at jumps
  • Spilled values always reloaded before use
  • No use of dead values

Estimated Complexity

Extra Large - This is the hardest piece of the codegen pipeline

Dependencies

• MIR Codegen: Stack Model & Basic Scheduling (≤16 values) #696 (Basic stack scheduling)
• MIR Codegen: Liveness Analysis #694 (Liveness analysis)
• MIR Codegen: Phi Elimination Pass #695 (Phi elimination)

Risks

• CFG complexity explosion: Keep assertion-heavy debug mode, check stack shape at every branch
• Gas inefficiency: Start with correct-but-naive spilling, optimize heuristics later