ssa-phi-placement-minimality

Answer

I diagnosed the problem class from scratch (no existing project files in the workspace) and produced a verified, self-contained solution.

Deliverables

• ~/SOLUTION.md — the requested markdown (title, root-cause analysis, exact fix, verification).
• ~/ssa_phi.py — the complete, stdlib-only reference implementation, embedded byte-for-byte in the markdown.

Root-cause analysis (the failure class)

1. One DF pass is not enough. Once a phi is placed at y, y becomes a definition site, so DF(y) must also be processed — this is the iterated dominance frontier (DF+). A single pass produces ill-formed SSA.
2. Over-approximation. Placing phis at every join for every variable yields non-minimal counts.
3. No redundancy cleanup. IDF still contains trivially-dead phis (unused results) and same-value phis (all operands equal, including phi(x, self) == x), which a fixed-point pass removes.
4. Self-referential "verification." Re-running the same algorithm proves nothing; an independent frontier-witness check is required.

Exact fix

Cytron pipeline: iterative dominators → DF via idom runner-walk → IDF worklist → SSA renaming (unique versions, ⊥ for defs missing on a path) → fixed-point elimination (dead + same-value with copy propagation) → minimality verification.

Verification (all green)

• Every surviving phi has a concrete witness, e.g. phi 'x' at 'join' <- DF of ['else', 'then'], phi 'i' at 'header' <- DF of ['body', 'header'].
• Survivors are always a subset of the IDF placement.
• 300 randomized trials pass an independent exhaustive oracle that enumerates all block subsets and keeps those closed under { DF(x) : x ∈ defsites(v) ∪ P }; the least such set is the IDF by definition, confirming minimum cardinality.

cd ~ && python3 ssa_phi.py   # exit 0

One subtlety documented in the solution: IDF is the least fixed point of the Cytron placement (not liveness-pruned), which is why a phi for a one-armed variable is inserted and then removed by the trivially-dead rule.