MIR Codegen: Liveness Analysis

## Summary Implement precise SSA-based liveness analysis as a reusable analysis that stack allocation, DCE, and spilling passes depend on. **Parent issue:** #687 ## Context The MIR is SSA-based, which means we can use standard dataflow analysis techniques. Liveness analysis tells us which values are "live" (will be used later) at each program point. This is essential for: - Stack scheduling (knowing when to drop values) - Dead code elimination (removing unused computations) - Stack spilling (choosing which values to spill when >16 live) ## Tasks ### Per-block local use/def sets - [ ] For each `Inst`, compute `uses(inst)` and `def(inst)` (single SSA result or none) - [ ] For each `BasicBlock`, precompute `block_uses` and `block_defs` ### Global backward dataflow liveness - [ ] Implement classic equations: - `live_out[B] = ⋃ live_in[succ]` - `live_in[B] = block_uses[B] ∪ (live_out[B] \ block_defs[B])` - [ ] Use worklist algorithm until fixed point - [ ] Represent sets using dense bitsets indexed by `ValueId` ### Per-instruction liveness - [ ] Walk instructions backward within each block to get `live_in_inst` and `live_out_inst` - [ ] Store results efficiently (on-demand recomputation vs. caching tradeoff) ### APIs for later passes - [ ] `fn live_in(block, inst_idx) -> &BitSet<ValueId>` - [ ] `fn live_out(block, inst_idx) -> &BitSet<ValueId>` - [ ] `fn last_use(value) -> InstId` helper for scheduling heuristics ## Patterns to follow **From Sonatina:** - Generic dataflow framework with lattice + transfer function - Efficient bitset-based representation with function-local indexing **From Venom:** - Per-instruction liveness used during code generation for dead value elimination ## Acceptance Criteria - [ ] Unit tests for toy functions: straight-line, branches, loops - [ ] Sanity property: if `value` is used at `inst`, then `value ∈ live_in(inst)` - [ ] Integration with pass manager (can be requested by other passes) ## Estimated Complexity **Medium** - Standard dataflow algorithm, but needs careful implementation for efficiency ## Dependencies - MIR structure (done) - Pass manager infrastructure (can be minimal initially)