MIR Codegen: Liveness Analysis

[gakonst]

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)

[dipanshuhappy]

Happy to work on this. I wrote a quick YUL compiler in Rust . I have been contributing to foundry (cast), and alloy. I started the YUL to HIR part also. But I can take this one also since its not too complex and I need to make sure of efficiency