ITADN

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

#696Closedgakonst 创建于 2026-01-14
C-enhancementP-highE-hardA-codegen
G
gakonstcommented
## 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 条评论