MIR Codegen: Stack Model & Basic Scheduling (≤16 values)

[gakonst]

Summary

Replace the current "PUSH0 placeholder" codegen with a Venom-style stack scheduler that maps MIR values to explicit EVM stack operations, assuming ≤16 live values.

Parent issue: #687

Context

The EVM is a stack machine with a 16-slot visibility window (DUP1-16, SWAP1-16). Currently, codegen emits PUSH0 as a placeholder for non-immediate values—this produces broken bytecode.

We need an abstract stack model that:

1. Tracks which MIR values are at which stack positions
2. Emits DUP/SWAP sequences to arrange operands correctly before each instruction
3. Drops dead values from the stack

This issue covers the simpler case: functions where we never exceed 16 live values simultaneously.

Tasks

Abstract stack machine model

• Define StackSlot abstraction tracking which ValueId is at which depth
• Implement AbstractStack with operations:
  • push(value) - add value to top
  • pop() - remove top
  • ensure_on_top(value) -> Vec<Opcode> - emit DUP/SWAP to bring value to TOS
  • drop(value) - remove value from stack
  • get_depth(value) -> Option<usize> - find value position

Per-block linear scheduling

• For each block, start with empty or incoming abstract stack
• Walk instructions in order:
  • For each use: call ensure_on_top(value), emit DUP/SWAP
  • For each def: update stack with new value at top
  • For dead results (from liveness): drop from abstract stack

Integration with codegen

• Replace placeholder PUSH0 emissions with scheduler calls
• Emit actual DUP/SWAP opcodes from scheduler
• Assert max concurrent live values ≤ 16 (debug build)

Limitation handling

• Document that this phase only handles ≤16 live values
• Graceful error when limit exceeded (defer to spilling issue)

Patterns to follow

From Venom:

• Abstract virtual stack state per instruction
• ensure_on_top generating optimal DUP/SWAP instead of ad-hoc patterns
• Separation between scheduling pass and assembler emission

From Sonatina:

• Pass structure: implement as transformation/annotation pass over MIR

Example

MIR:
  v0 = arg(0)
  v1 = arg(1)
  v2 = add(v0, v1)
  v3 = mul(v2, v0)
  return v3

Stack scheduling trace:
  [v0, v1]           ; after loading args
  DUP2               ; copy v0 for later use
  [v0, v1, v0]
  ADD                ; consumes top 2, produces v2
  [v0, v2]
  SWAP1              ; bring v0 to top for mul
  [v2, v0]
  DUP2               ; copy v2
  [v2, v0, v2]
  SWAP1
  [v2, v2, v0]
  MUL                ; produces v3
  [v2, v3]
  SWAP1, POP         ; drop v2
  [v3]
  RETURN

Acceptance Criteria

• Simple functions emit valid EVM bytecode (no PUSH0 placeholders)
• Correct evaluation order verified via execution tests
• At most DUP16/SWAP16 used; no stack underflows
• Tests confirming abstract stack never exceeds 16 entries

Estimated Complexity

Large - Core algorithm is manageable but many edge cases

Dependencies

• MIR Codegen: Liveness Analysis #694 (Liveness analysis)
• MIR Codegen: Phi Elimination Pass #695 (Phi elimination)