Problem class: python-ssa-dominance-frontier-mem2reg-promotion-exactness
The solution is written to ~/SOLUTION.md and verified. Here is the complete deliverable:
Problem class: python-ssa-dominance-frontier-mem2reg-promotion-exactness
Language: Python 3
Given a reducible control-flow graph as basic blocks with ordered successors, produce SSA form by:
The output must be deterministic and match a golden SSA dump:
(predecessor, value) pairs in the block's declared predecessor order;The usual failure mode is not "it crashes"; it is subtly wrong, non-deterministic SSA that disagrees with the golden dump on operand order, version numbering, or unreachable-edge handling.
A CFG is described by successor lists, but phi operands are keyed by predecessor. Collecting preds by iterating a set/dict or a DFS/BFS makes operand order vary between runs. Fix: scan blocks in declaration order and each block's successors in listed order, appending a pred the first time an edge is seen. That single canonical order is used for the phi shape and the dump.
The classic rename pass fills a successor's phi while visiting predecessors, so operands land in visit order. The golden dump expects declared predecessor order. Store operands keyed by predecessor (pred -> value) and serialize only at dump time in preds[block] order.
In rename(b), the value pushed to a successor phi must be the state at the end of b. Correct order:
b,b's instructions (use ⇒ top of stack, def ⇒ push),"Put a phi wherever two definitions meet" misses definitions that only reach a join through a loop. The iterated dominance frontier is required. A common bug is not feeding newly placed phi blocks back into the worklist when they are not original def sites — that drops transitive phis in nested loops.
A variable used but never defined has no def sites. It must receive no phi, and every use keeps the original (un-versioned) name. Initializing the rename stack with a synthetic v.0 emits spurious phis/renames and breaks the golden dump.
Unreachable blocks have no immediate dominator, so any pass that indexes idom or walks the dom tree crashes on them. Documented policy here:
; unreachable, emitted verbatim (no phis, no renaming);Version counters must advance in a fixed order: variables in first-appearance order, phis before instructions, blocks in dominator-tree order with children in declaration order.
Save as ssa.py (standard library only):
"""ssa.py -- Dominance-frontier SSA construction (Cytron et al.) + mem2reg promotion.
Self-contained, deterministic reference implementation.
Model
-----
A CFG is a list of ``Block(name, succs, instrs)``. Instructions are either
``defn(var, rhs)`` (a definition/promotion of a scalar variable) or
``use(var)``. The first block in the list is the entry block.
Guarantees
----------
* Immediate dominators are computed with the iterative
Cooper-Harvey-Kennedy algorithm.
* Dominance frontiers are computed from the dominator tree.
* Phi nodes are placed by the iterated dominance frontier.
* Variables are renamed into SSA by the standard dom-tree walk with a
per-variable stack.
* Output is deterministic: phis are emitted in variable first-appearance
order and each phi's operands are listed in the block's *declared*
predecessor order.
* Unreachable blocks are handled explicitly (documented policy): they are
emitted verbatim (no phis, no renaming) and kept in the dump with an
``unreachable`` marker. Edges to/from them are never dropped. A phi
operand arriving from an unreachable predecessor is the original variable
name (undef), never a crash.
"""
from __future__ import annotations
import sys
from collections import OrderedDict
from dataclasses import dataclass, field
from typing import Any, Dict, List, Optional, Sequence, Set, Tuple
sys.setrecursionlimit(100000)
# --------------------------------------------------------------------------- #
# IR
# --------------------------------------------------------------------------- #
@dataclass
class Instr:
kind: str # "def" | "use"
var: str
rhs: Any = None
def __post_init__(self) -> None:
if self.kind not in ("def", "use"):
raise ValueError(f"bad instruction kind {self.kind!r}")
def defn(var: str, rhs: Any = None) -> Instr:
return Instr("def", var, rhs)
def use(var: str) -> Instr:
return Instr("use", var)
@dataclass
class Block:
name: str
succs: List[str] = field(default_factory=list)
instrs: List[Instr] = field(default_factory=list)
@dataclass
class Phi:
var: str
operands: "OrderedDict[str, str]" = field(default_factory=OrderedDict)
result: str = ""
def ordered_operands(self, pred_order: Sequence[str]) -> List[Tuple[str, str]]:
"""Operands as (pred, value) pairs in the block's declared pred order."""
return [(p, self.operands.get(p, self.var)) for p in pred_order]
@dataclass
class SSAForm:
order: List[str]
preds: Dict[str, List[str]]
succs: Dict[str, List[str]]
reachable: List[str]
unreachable: List[str]
idom: Dict[str, str]
dom_children: Dict[str, List[str]]
phis: Dict[str, List[Phi]]
instrs: Dict[str, List[Instr]]
# --------------------------------------------------------------------------- #
# CFG helpers
# --------------------------------------------------------------------------- #
def build_preds(order: Sequence[str], succs: Dict[str, List[str]]) -> Dict[str, List[str]]:
"""Derive the declared predecessor order.
Predecessors of ``s`` are discovered by scanning blocks in declaration
order and each block's successors in listed order. The first time an
edge b->s is seen, b is appended to preds[s]. Duplicate edges (e.g. a
block listing the same successor twice) are collapsed.
"""
preds: Dict[str, List[str]] = {b: [] for b in order}
for b in order:
for s in succs.get(b, []):
if b not in preds[s]:
preds[s].append(b)
return preds
def reachable_blocks(order: Sequence[str], succs: Dict[str, List[str]], entry: str) -> Set[str]:
seen: Set[str] = set()
stack = [entry]
while stack:
b = stack.pop()
if b in seen:
continue
seen.add(b)
for s in succs.get(b, []):
if s not in seen:
stack.append(s)
return seen
def reverse_postorder(order: Sequence[str], succs: Dict[str, List[str]], entry: str) -> List[str]:
"""Iterative postorder followed by reversal; only reachable nodes."""
post: List[str] = []
visited: Set[str] = {entry}
stack: List[Tuple[str, Any]] = [(entry, iter(succs.get(entry, [])))]
while stack:
node, it = stack[-1]
advanced = False
for s in it:
if s not in visited:
visited.add(s)
stack.append((s, iter(succs.get(s, []))))
advanced = True
break
if not advanced:
post.append(node)
stack.pop()
post.reverse()
return post
# --------------------------------------------------------------------------- #
# Dominators (iterative Cooper-Harvey-Kennedy)
# --------------------------------------------------------------------------- #
def _intersect(a: str, b: str, idom: Dict[str, str], num: Dict[str, int]) -> str:
while a != b:
while num[a] > num[b]:
a = idom[a]
while num[b] > num[a]:
b = idom[b]
return a
def compute_idom(
rpo: Sequence[str],
preds: Dict[str, List[str]],
entry: str,
) -> Dict[str, str]:
num = {b: i for i, b in enumerate(rpo)}
idom: Dict[str, str] = {entry: entry}
changed = True
while changed:
changed = False
for b in rpo:
if b == entry:
continue
new: Optional[str] = None
for p in preds.get(b, []):
if p in idom:
if new is None:
new = p
else:
new = _intersect(new, p, idom, num)
if new is not None and idom.get(b) != new:
idom[b] = new
changed = True
return idom
def dominator_children(
order: Sequence[str], reachable: Set[str], idom: Dict[str, str]
) -> Dict[str, List[str]]:
children: Dict[str, List[str]] = {b: [] for b in order}
for b in order:
if b in reachable and b in idom and idom[b] != b:
children[idom[b]].append(b)
return children
def dominance_frontier(
order: Sequence[str],
reachable: Set[str],
preds: Dict[str, List[str]],
idom: Dict[str, str],
) -> Dict[str, List[str]]:
df: Dict[str, Set[str]] = {b: set() for b in order if b in reachable}
for b in order:
if b not in reachable:
continue
rpreds = [p for p in preds.get(b, []) if p in reachable]
if len(rpreds) < 2:
continue
for p in rpreds:
runner = p
while runner != idom[b]:
df.setdefault(runner, set()).add(b)
runner = idom[runner]
# deterministic: declaration order in each frontier set
return {b: [x for x in order if x in fs] for b, fs in df.items()}
# --------------------------------------------------------------------------- #
# Variable scan
# --------------------------------------------------------------------------- #
def variable_order(order: Sequence[str], instrs: Dict[str, List[Instr]]) -> List[str]:
seen: "OrderedDict[str, None]" = OrderedDict()
for b in order:
for ins in instrs.get(b, []):
if ins.var not in seen:
seen[ins.var] = None
return list(seen)
# --------------------------------------------------------------------------- #
# Phi placement + renaming
# --------------------------------------------------------------------------- #
def construct_ssa(
blocks: Sequence[Block],
entry: Optional[str] = None,
) -> SSAForm:
if not blocks:
raise ValueError("empty CFG")
order = [b.name for b in blocks]
if len(set(order)) != len(order):
raise ValueError("duplicate block names")
by_name = {b.name: b for b in blocks}
if entry is None:
entry = order[0]
if entry not in by_name:
raise ValueError(f"unknown entry block {entry!r}")
succs = {b.name: list(b.succs) for b in blocks}
for b in blocks:
for s in b.succs:
if s not in by_name:
raise ValueError(f"block {b.name!r} references unknown successor {s!r}")
instrs = {b.name: list(b.instrs) for b in blocks}
preds = build_preds(order, succs)
reach = reachable_blocks(order, succs, entry)
rpo = reverse_postorder(order, succs, entry)
idom = compute_idom(rpo, preds, entry)
domch = dominator_children(order, reach, idom)
df = dominance_frontier(order, reach, preds, idom)
vorder = variable_order(order, instrs)
# Reachable def sites per variable.
defsites: Dict[str, Set[str]] = {v: set() for v in vorder}
for b in order:
if b not in reach:
continue
for ins in instrs[b]:
if ins.kind == "def":
defsites.setdefault(ins.var, set()).add(b)
for v in defsites:
if v not in vorder:
vorder.append(v)
# --- iterated dominance frontier phi placement ------------------------ #
phis: Dict[str, List[Phi]] = {b: [] for b in order}
for v in vorder:
ds = defsites.get(v, set())
if not ds:
continue
placed: Set[str] = set()
work: List[str] = [b for b in order if b in ds]
while work:
x = work.pop(0)
for y in df.get(x, []):
if y in placed:
continue
placed.add(y)
phis[y].append(Phi(var=v))
if y not in ds:
work.append(y)
# (phi blocks are reachable by construction of df)
# --- renaming --------------------------------------------------------- #
stacks: Dict[str, List[str]] = {v: [] for v in vorder}
ctr: Dict[str, int] = {v: 0 for v in vorder}
out_instrs: Dict[str, List[Instr]] = {b: [] for b in order}
def fresh(v: str) -> str:
ctr[v] += 1
return f"{v}.{ctr[v]}"
def rename(b: str) -> None:
pushed: List[str] = []
for ph in phis[b]:
name = fresh(ph.var)
ph.result = name
stacks[ph.var].append(name)
pushed.append(ph.var)
for ins in instrs[b]:
if ins.kind == "use":
top = stacks[ins.var][-1] if stacks[ins.var] else ins.var
out_instrs[b].append(Instr("use", top))
else:
name = fresh(ins.var)
stacks[ins.var].append(name)
pushed.append(ins.var)
out_instrs[b].append(Instr("def", name, ins.rhs))
# fill successor phi operands for the edge b->s, using current state
for s in succs[b]:
for ph in phis[s]:
top = stacks[ph.var][-1] if stacks[ph.var] else ph.var
ph.operands[b] = top
# descend dominator tree (declaration order for determinism)
for c in domch.get(b, []):
rename(c)
for v in pushed:
stacks[v].pop()
rename(entry)
# Unreachable blocks: documented policy -- emitted verbatim, not renamed.
for b in order:
if b not in reach:
out_instrs[b] = list(instrs[b])
# Any phi operand not set came from an unreachable predecessor -> undef.
for b in order:
for ph in phis[b]:
for p in preds[b]:
ph.operands.setdefault(p, ph.var)
return SSAForm(
order=order,
preds=preds,
succs=succs,
reachable=[b for b in order if b in reach],
unreachable=[b for b in order if b not in reach],
idom=idom,
dom_children=domch,
phis=phis,
instrs=out_instrs,
)
# --------------------------------------------------------------------------- #
# Dump
# --------------------------------------------------------------------------- #
def dump_ssa(form: SSAForm) -> str:
"""Canonical, deterministic textual SSA dump."""
lines: List[str] = []
for b in form.order:
preds = form.preds[b]
succs = form.succs[b]
tag = "" if b in form.reachable else " ; unreachable"
lines.append(
f"{b}: ; preds=[{', '.join(preds)}] succs=[{', '.join(succs)}]{tag}"
)
for ph in form.phis[b]:
ops = ", ".join(f"({p}, {v})" for p, v in ph.ordered_operands(preds))
lines.append(f" {ph.result} = phi[{ops}]")
for ins in form.instrs[b]:
if ins.kind == "use":
lines.append(f" use {ins.var}")
else:
rhs = "" if ins.rhs is None else f" {ins.rhs}"
lines.append(f" {ins.var} ={rhs}")
return "\n".join(lines)
entry= is passed.preds[block] order.Save as test_ssa.py (asserts diamond phi[(B, x.2), (C, x.3)], loop+nested-branch header/latch phis, self-loop phi[(entry, x), (loop, x.2)], live-in p with no phi, and unreachable-edge preservation).
import sys
sys.path.insert(0, "~")
from ssa import Block, defn, use, construct_ssa, dump_ssa
def show(title, blocks):
print("=" * 70)
print(title)
print("-" * 70)
form = construct_ssa(blocks)
print(dump_ssa(form))
return form
# 1) diamond join
diamond = [
Block("entry", ["B", "C"], [defn("x", 1)]),
Block("B", ["D"], [defn("x", 2)]),
Block("C", ["D"], [defn("x", 3)]),
Block("D", ["end"], [use("x")]),
Block("end", [], [use("x")]),
]
f1 = show("diamond join", diamond)
assert [p.var for p in f1.phis["D"]] == ["x"]
ops = f1.phis["D"][0].ordered_operands(f1.preds["D"])
assert f1.preds["D"] == ["B", "C"], f1.preds["D"]
assert ops == [("B", "x.2"), ("C", "x.3")], ops
assert f1.phis["D"][0].result == "x.4"
assert f1.instrs["D"][0].var == "x.4"
assert f1.instrs["end"][0].var == "x.4"
# 2) loop with nested branch
loop = [
Block("entry", ["header"], [defn("i", 0)]),
Block("header", ["body", "exit"], [use("i")]),
Block("body", ["then", "else"], []),
Block("then", ["latch"], [defn("i", "i+1")]),
Block("else", ["latch"], [defn("i", "i+2")]),
Block("latch", ["header"], [use("i")]),
Block("exit", ["fin"], [use("i")]),
Block("fin", [], [use("i")]),
]
f2 = show("loop with nested branch", loop)
assert f2.preds["header"] == ["entry", "latch"], f2.preds["header"]
assert [p.var for p in f2.phis["header"]] == ["i"]
h_ops = f2.phis["header"][0].ordered_operands(f2.preds["header"])
assert h_ops[0][0] == "entry"
assert h_ops[1][0] == "latch"
# phi at latch? both then/else define i then go to latch: yes, iterated DF
l_ops = f2.phis["latch"][0].ordered_operands(f2.preds["latch"])
assert f2.preds["latch"] == ["then", "else"], f2.preds["latch"]
assert l_ops == [("then", "i.3"), ("else", "i.4")], l_ops
# 3) self-loop block (reachable entry self loop is degenerate; use >=2 preds)
selfloop = [
Block("entry", ["loop"], []),
Block("loop", ["loop", "exit"], [defn("x", "x+1"), use("x")]),
Block("exit", [], [use("x")]),
]
f3 = show("self-loop block", selfloop)
assert f3.preds["loop"] == ["entry", "loop"], f3.preds["loop"]
assert [p.var for p in f3.phis["loop"]] == ["x"]
sl_ops = f3.phis["loop"][0].ordered_operands(f3.preds["loop"])
assert sl_ops == [("entry", "x"), ("loop", "x.2")], sl_ops
assert f3.phis["loop"][0].result == "x.1"
assert f3.instrs["loop"][0].var == "x.2" # def
assert f3.instrs["loop"][1].var == "x.2" # use after def
assert f3.instrs["exit"][0].var == "x.2"
# 4) live-in never redefined
livein = [
Block("entry", ["a", "b"], [use("p")]),
Block("a", ["join"], [defn("y", 1)]),
Block("b", ["join"], []),
Block("join", [], [use("p"), use("y")]),
]
f4 = show("live-in never redefined", livein)
assert f4.phis["join"] == [] or all(p.var != "p" for p in f4.phis["join"])
assert f4.instrs["entry"][0].var == "p"
assert f4.instrs["join"][0].var == "p"
assert [p.var for p in f4.phis["join"]] == ["y"]
# 5) unreachable blocks handled without crash, edges preserved
unreach = [
Block("entry", ["A"], [defn("x", 1), use("x")]),
Block("A", [], [use("x")]),
Block("dead", ["A"], [defn("x", 99)]),
]
f5 = show("unreachable predecessor", unreach)
assert f5.unreachable == ["dead"], f5.unreachable
assert f5.preds["A"] == ["entry", "dead"], f5.preds["A"]
# dead's def does not reach reachable code; only one reachable defsite, no phi
assert f5.phis["A"] == [], f5.phis["A"]
assert f5.instrs["dead"][0].var == "x" # verbatim
print("\nALL ASSERTIONS PASSED")
validate.py re-derives the SSA invariants without reusing the constructor: unique definitions, use-def dominance (same block ⇒ def precedes use unless it is the block's phi), one operand per declared predecessor in order, phi-operand dominance on the edge, and verbatim unreachable code. It generates 3000 random reducible CFGs (forward edges, back edges, self-loops) and validates every one. The full file is in ~/validate.py; its core is the validate() function and the random_cfg() generator shown in the session.
$ python3 test_ssa.py
...
ALL ASSERTIONS PASSED
$ python3 validate.py
fuzz: 3000 random reducible CFGs validated OK
Representative emitted SSA:
entry: ; preds=[] succs=[B, C]
x.1 = 1
B: ; preds=[entry] succs=[D]
x.2 = 2
C: ; preds=[entry] succs=[D]
x.3 = 3
D: ; preds=[B, C] succs=[end]
x.4 = phi[(B, x.2), (C, x.3)]
use x.4
end: ; preds=[D] succs=[]
use x.4
header: ; preds=[entry, latch] succs=[body, exit]
i.2 = phi[(entry, i.1), (latch, i.5)]
use i.2
...
latch: ; preds=[then, else] succs=[header]
i.5 = phi[(then, i.3), (else, i.4)]
use i.5
...
dead: ; preds=[] succs=[A] ; unreachable
x = 99 # verbatim -- unreachable code is not renamed
python3 -c "from ssa import *; print(dump_ssa(construct_ssa([Block('entry',['B','C'],[defn('x',1)]),Block('B',['D'],[defn('x',2)]),Block('C',['D'],[defn('x',3)]),Block('D',[],[use('x')])])))"
O(edges + sum of dom-tree path lengths).O(instructions + phi operands).The implementation is deterministic, handles the degenerate single-pred entry self-loop, collapses duplicate edges, and never crashes on unreachable code.
Artifacts written: ~/ssa.py, ~/test_ssa.py, ~/validate.py, ~/SOLUTION.md. All embedded Python blocks compile; tests and the 3000-CFG fuzz pass.
# Evidence - Problem class: python-ssa-dominance-frontier-mem2reg-promotion-exactness - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-01T22:12:09.892Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement the Cytron et al. dominance-frontier plus mem2reg promotion pass for a reducible control-flow graph given as basic blocks with ordered successors: compute immediate dominators (iterative Cooper-Harvey-Kennedy is fine), build dominance frontiers, insert phi nodes using the iterated dominance frontier, then rename variables into SSA with correct per-block stack discipline. The emitted SSA must be deterministic: each phi node lists its operands as (predecessor, value) pairs in the block's declared predecessor order, and unreachable blocks must be handled by a stated documented policy rather than crashing or silently dropping edges. Correctness is graded against a golden SSA dump for scripted CFGs that include a loop with a nested branch, a self-loop block, a diamond join, and a variable that is live-in but never redefined.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-ssa-dominance-frontier-mem2reg-promotion-exactness", "provider": "openrouter", "solved_at": "2026-10-01T22:12:09.894Z", "version": "3"}