Answer

I've built, debugged, and verified a complete solution. The self-contained document is at ~/work/SOLUTION.md (1,116 lines), with the engine in ssa_ra.py and the adversarial verification suite in harness.py.

SSA Liveness & Register Allocation with Edge-Specific Phi Uses, Critical Edges, and Exceptional Exits

Root-cause analysis

Three silent-miscompile defects surface when implementing this class of allocator:

1. Phi operands are edge-specific uses. d = phi(v_A from A, v_B from B) uses v_A on edge A→S, not inside S. The correct equations are live_out[P] = ⋃_{S∈succ(P)} ( (live_in[S] \ phi_defs(S)) ∪ phi_uses(P,S) ) live_in[B] = uses(B) ∪ (live_out[B] \ defs(B)) Dropping phi_uses(P,S) makes an operand look dead, so a later definition in the same predecessor reuses its register and clobbers it. Reproducer: A: x=1; z=9; jmp M, M: p=phi(x from A, …); ret p → correct ret 1, naïve ret 9.

2. Terminator uses must seed the backward interference walk. Branch conditions and ret/raise operands are uses at the end of a block. Starting the walk from live_out[B] alone lets a late def share a register with them (caught by differential test as ret 3 vs ret 2).

3. Phis are processed last in a backward walk. Program order is [phis][instrs][term], so backward order is term → instrs → phis. Processing phis first misses values made live by instructions (caught as ret 24 vs ret 4).

Plus: critical-edge splitting must retarget phi predecessor labels from P to the inserted E; a correct block-level solver then carries live values through E automatically. raise is just a terminator use.

Exact fix

Core liveness adds the phi_uses_edge(n, s) term. Interference walks live = live_out[n] | terminator_uses(n), then reversed instructions, then phis (adding the full parallel-copy conflict clique). split_critical_edges inserts E and rewrites phi preds. Allocation is Chaitin–Briggs colouring into K-2 registers with two reserved spill-scratch registers; spill priority is spill_cost(v)/(degree+1) with spill_cost weighted by 10^loop_depth. Full code is embedded in SOLUTION.md.

Verification

mkdir -p ssa && cd ssa   # save the two code blocks from SOLUTION.md as
                         # ssa_ra.py and harness.py
python3 harness.py

Expected:

root-cause demo: (('ret', 1), ('ret', 9))
split-edge demo: ({('ret', 0), ('ret', 1), ('ret', 5)}, 1)
differential   : {'programs': 60, 'checks': 2160, 'naive_diffs': 49, 'spill_seen': 300}
optimality     : {'cases': 38, 'heuristic_optimal': 6}
ALL TESTS PASSED

• 2,160 differential checks compare a canonical SSA interpreter against the allocated interpreter for every budget K=2..6; 0 mismatches; 49/60 programs expose naïve-vs-correct liveness differences; spills exercised 300 times.
• Extended sweep: 250 adversarial CFGs, K=2..8, 30k-step limit → 8,750 checks, 1,748 spill scenarios, 224 liveness-difference programs, 190 with back edges, 0 mismatches.
• Optimality: brute-force optimum over all spill subsets confirms the heuristic cost is always ≥ optimum.
• Self-containment proof: I extracted the two fenced code blocks from SOLUTION.md into a clean directory and ran harness.py → ALL TESTS PASSED.