MIR Codegen: Stack Model & Basic Scheduling (≤16 values)
C-enhancementP-highE-hardA-codegen
## 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
- #694 (Liveness analysis)
- #695 (Phi elimination)
关闭于 2026-05-16 1 条评论