MIR Codegen: Phi Elimination Pass

[gakonst]

Summary

Remove phi nodes from SSA MIR and convert to an assignment form suitable for stack allocation, using parallel copy insertion and coalescing.

Parent issue: #687

Context

SSA form uses φ (phi) nodes to merge values at control flow join points. The EVM has no direct equivalent—we need to convert phis into explicit move/copy instructions inserted at block boundaries.

Example:

; Before (SSA with phi)
entry:
  v0 = const 1
  branch cond, then_block, else_block

then_block:
  v1 = const 10
  jump merge

else_block:
  v2 = const 20
  jump merge

merge:
  v3 = phi [v1, then_block], [v2, else_block]  ; ← phi node
  return v3

; After (phi eliminated)
then_block:
  v1 = const 10
  v3 = move v1    ; ← inserted copy
  jump merge

else_block:
  v2 = const 20
  v3 = move v2    ; ← inserted copy
  jump merge

merge:
  return v3

Tasks

Parallel copy insertion

• For each block with phi nodes, for each predecessor P:
  • Generate assignments phi_result := incoming_from_P
  • Insert as parallel copy sequence at end of P (before terminator)

Parallel copy resolution

• Transform parallel copies into sequential Move instructions
• Handle cycles via temporary values (e.g., swap a, b = b, a needs a temp)
• Coalesce moves when possible (no conflict)

Phi removal

• Replace all phi result uses with the new value sources
• Delete phi instructions from MIR
• Update MIR invariants documentation

Patterns to follow

From Sonatina:

• Simple phi elimination pass with parallel copies at block entries/predecessor exits
• Cycle-breaking using temp register/value

From Venom:

• Post-phi form convenient for stack allocation: all values now have standard instruction definitions

Acceptance Criteria

• MIR pretty-printer shows no Phi instructions post-pass
• Tests for diamonds, loops, nested conditionals retain semantic equivalence
• Specific tests for phi cycles (e.g., swap of two values across branches)

Estimated Complexity

Medium - Well-understood algorithm, but cycle handling requires care

Dependencies

• MIR Codegen: Liveness Analysis #694 (Liveness analysis) - recommended for optimization but not strictly required
• MIR structure (done)