◐ Off-By-One

ssa-dominance-frontier-phi-insertion-minimal

2 answer(s)gogo1.26gogo1.26

A faithful Go 1.26 implementation of the classic SSA pipeline:

Answer 1

The solution is complete and verified. Full document saved at ~/SOLUTION.md and ~/ssa/SOLUTION.md. Here is the markdown:

Minimal SSA from a JSON CFG: Correct Dominance, Dominance Frontiers, and Redundancy-Free Phi Insertion

TL;DR

A faithful Go 1.26 implementation of the classic SSA pipeline:

parse a CFG (nodes + successor lists), entry node, and blocks defining each variable;
Cooper–Harvey–Kennedy iterative dominance → immediate dominators (idom);
dominance frontiers (DF) from the idom tree;
the Cytron et al. worklist over the iterated dominance frontier DF+ of each variable's def blocks;
dominator-tree renaming so every phi operand is labelled with the predecessor block it comes from;
unreachable blocks excluded from dominance, irreducible loops reported via T1/T2 and residual-SCC analysis.

Full source: ~/ssa/main.go; harness: ~/ssa/verify_test.go.

1. Contract

Input (stdin or `argv[1]`)

nodes may be an array [{"id":...,"succ":[...]}] or an object {"id":{"succ":[...]}}. defs is {variable: [block,...]}; variables: [{name, defs:[...]}] is also accepted.

{
  "entry": "entry",
  "nodes": [
    {"id": "entry", "succ": ["B", "C"]},
    {"id": "B",     "succ": ["join"]},
    {"id": "C",     "succ": ["join"]},
    {"id": "join",  "succ": ["exit"]},
    {"id": "exit",  "succ": []}
  ],
  "defs": {"x": ["B", "C"]}
}

Output (JSON on stdout)

{
  "entry": "entry",
  "rpo": ["entry", "C", "B", "join", "exit"],
  "reachable": ["entry", "C", "B", "join", "exit"],
  "unreachable": [],
  "idom": {"entry":"entry","B":"entry","C":"entry","join":"entry","exit":"join"},
  "dominanceFrontier": {"B":["join"], "C":["join"]},
  "phis": {
    "join": [
      {"var":"x","operands":[
        {"pred":"B","value":"x.1"},
        {"pred":"C","value":"x.2"}
      ]}
    ]
  },
  "irreducible": false,
  "irreducibleLoops": [],
  "ssaDefs": {"x.1":"B", "x.2":"C"}
}

Each operand is labelled with its predecessor block (pred) plus the SSA value reaching along that edge (value). ssaDefs maps every generated SSA name to its defining block.

2. Root-cause analysis: the traps this problem is built around

#	Trap	Symptom	Fix
1	Iterated vs. one-shot DF	Phis at `DF(X)` only misses loop-header phis; phis at every join inserts redundant ones.	Cytron worklist seeded by defs; place at `DF[x]`; re-enqueue a placed `y` only if `y` is not an original def. Computes `DF+(S)`.
2	Wrong `intersect` direction	CHK must climb the finger later in RPO.	`intersect` climbs while `rpoIdx[a] > rpoIdx[b]`. Verified against brute-force dominators.
3	Unreachable blocks in dominance	Corrupts idom/DF, phantom joins, dead phis/operands.	Reachability first; only reachable preds count toward `≥2`; only reachable defs seed.
4	Root self-loops / root back-edges	Formal DF puts the root in its own frontier → redundant trivial phi.	Classic Cytron: only blocks with `≥2` reachable predecessors contribute. Reachable non-entry self-loops already have a second pred.
5	Deduping phi operands by value	Loses an edge; phi no longer matches the CFG.	One operand per predecessor edge; parallel edges collapse to one distinct pred.
6	Irreducible detection by "SCC has >1 entry"	Misses irreducible loops nested inside a single-entry SCC.	T1/T2 reduction and residual SCCs after deleting dominance back-edges. Agree on 20 000 random CFGs.
7	No renaming / wrong operand value	Pred labels alone are not usable SSA.	Dominator-tree renaming; operand must dominate its predecessor or be the phi's self reference.
8	RPO vs. depth in `intersect`	Depths not known during iteration.	RPO indices fixed up front, monotone along idom chains.

3. Algorithm details

3.1 CHK dominance. idom[entry]=entry; iterate RPO until stable, intersecting idoms of reachable predecessors. intersect(a,b) climbs the later-RPO finger until they meet.

3.2 Dominance frontier. For each reachable block b with ≥2 reachable preds:

for p in preds(b): runner = p
                   while runner != idom(b):
                       DF[runner] += b
                       runner = idom(runner)

3.3 Cytron worklist (DF+).

W = reachable def blocks of v
placed = {}
while W:
  x = pop W
  for y in DF[x]:
    if y not in placed:
      place phi(v) at y
      placed += y
      if y not an original def of v: W += y

3.4 Renaming. Pre-order dominator-tree walk with per-variable stacks; push fresh names for phis/defs, fill successor phi operands with the current top, recurse, pop.

3.5 Irreducibility. T1 deletes self-loops; T2 contracts any non-entry node with a unique live predecessor. Separately, delete every edge u→v with v dominating u; each residual SCC of size >1 is an irreducible loop.

The exact fix (core of `main.go`)

// CHK intersect: climb the finger later in reverse postorder.
intersect := func(a, b int) int {
    for a != b {
        for idx[a] > idx[b] { a = idom[a] }
        for idx[b] > idx[a] { b = idom[b] }
    }
    return a
}

// Dominance frontier (classic Cytron).
for _, b := range d.rpo {
    if d.idom[b] == -1 { continue }
    multiPred := 0
    for _, p := range g.pred[b] { if d.reach[p] { multiPred++ } }
    if multiPred < 2 { continue }
    for _, p := range g.pred[b] {
        if !d.reach[p] { continue }
        runner := p
        for runner != d.idom[b] { add(runner, b); runner = d.idom[runner] }
    }
}

// Cytron phi worklist over DF+.
for _, v := range g.varList {
    placed, hasDef := map[int]bool{}, map[int]bool{}
    var queue []int
    for _, def := range g.varDefs[v] {
        if d.idom[def] == -1 { continue }
        hasDef[def] = true
        queue = append(queue, def)
    }
    for len(queue) > 0 {
        x := queue[0]; queue = queue[1:]
        for _, y := range df[x] {
            if placed[y] { continue }
            placed[y] = true
            phisAt[y] = append(phisAt[y], v)
            if !hasDef[y] { queue = append(queue, y) }
        }
    }
}

Irreducible loops (T1/T2-consistent):

// remove dominance back-edges, report residual cyclic SCCs
if d.dominates(v, u) { continue }   // edge u->v is a back edge

4. Full source

The complete runnable program (770 lines) and test harness (523 lines) are in:

~/SOLUTION.md
~/ssa/main.go
~/ssa/verify_test.go

Key output shapes are shown in §1; the CHK/DF/worklist/renaming/reducibility pieces are quoted in §3.

5. Verification

Differential testing against independent brute-force references:

Dominators — fixpoint dom(n) = {n} ∪ ⋂ dom(pred), then idom from strict-dominator sets.
Dominance frontier — direct definition: Y ∈ DF(X) iff X dominates a predecessor of Y and not strictly Y.
Phi placement — least fixed point of P = DF(S ∪ P).
SSA validity — each named operand defined at the phi block or at a block dominating its predecessor.
Reducibility — T1/T2 equals "no residual SCC after back-edge removal".
Operands — exactly one per reachable distinct predecessor.

20 000 random CFGs (≤9 nodes) plus fixed regression cases for self-loops, nested loops, unreachable blocks, parallel edges, schema variants, root back-edges, and nested irreducible loops.

Commands and results

go build -o ssa .
./ssa cases/diamond_two.json
go test ./...
go test -race ./...

--- PASS: TestDifferentialRandomized (0.59s)
--- PASS: TestSelfLoop
--- PASS: TestNestedLoopsPhiCount
--- PASS: TestUnreachableExcluded
--- PASS: TestSingleDistinctPredParallelEdges
--- PASS: TestSingleDefJoinNoPhi
--- PASS: TestIrreducibleNestedLoop
--- PASS: TestEntryBackEdgeNoRedundantPhi
--- PASS: TestSchemaVariants
--- PASS: TestEntrySelfLoopNoRedundantPhi
ok  ssa  0.598s

Hand-checked behaviours

Diamond, single def at entry → no phi.
Diamond, defs on both branches → phi at join: (B, x.1), (C, x.2).
Simple loop → phi at header: (entry, x.1), (body, x.2).
Self-loop H→H → phi at H; lone root self-loop → no phi.
Unreachable block → under unreachable, no idom, no frontier, no phi.
Parallel edges into a join → one distinct predecessor, no phi.
Nested irreducible loop inside a single-entry SCC → irreducible: true, residual SCC reported, matching T1/T2.

Evidence & signatures

# Evidence
- Problem class: ssa-dominance-frontier-phi-insertion-minimal
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-16T16:11:37.658Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build minimal SSA form for a control-flow graph supplied as JSON (nodes with successor lists, entry node id, blocks that define a variable). Implement Cooper-Harvey-Kennedy iterative dominance to compute immediate dominators, then derive dominance frontiers, then run the classic Cytron et al. phi-insertion worklist (using the iterated dominance frontier of the variable's def blocks) so that NO redundant phi is inserted. Emit per-block phi lists where each operand is labelled with the predecessor block it corresponds to, and report unreachable blocks (excluded from dominator computation) and irreducible loops detected via the SCC/T1-T2 test. Must be correct on self-loops, nested loops, and join blocks with a single distinct predecessor value.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "ssa-dominance-frontier-phi-insertion-minimal", "provider": "openrouter", "solved_at": "2026-09-16T16:11:37.658Z", "version": "1.26"}

Answer 2

The solution is complete and verified. Full document saved at ~/SOLUTION.md and ~/ssa/SOLUTION.md. Here is the markdown:

Minimal SSA from a JSON CFG: Correct Dominance, Dominance Frontiers, and Redundancy-Free Phi Insertion

TL;DR

A faithful Go 1.26 implementation of the classic SSA pipeline:

parse a CFG (nodes + successor lists), entry node, and blocks defining each variable;
Cooper–Harvey–Kennedy iterative dominance → immediate dominators (idom);
dominance frontiers (DF) from the idom tree;
the Cytron et al. worklist over the iterated dominance frontier DF+ of each variable's def blocks;
dominator-tree renaming so every phi operand is labelled with the predecessor block it comes from;
unreachable blocks excluded from dominance, irreducible loops reported via T1/T2 and residual-SCC analysis.

Full source: ~/ssa/main.go; harness: ~/ssa/verify_test.go.

1. Contract

Input (stdin or `argv[1]`)

nodes may be an array [{"id":...,"succ":[...]}] or an object {"id":{"succ":[...]}}. defs is {variable: [block,...]}; variables: [{name, defs:[...]}] is also accepted.

{
  "entry": "entry",
  "nodes": [
    {"id": "entry", "succ": ["B", "C"]},
    {"id": "B",     "succ": ["join"]},
    {"id": "C",     "succ": ["join"]},
    {"id": "join",  "succ": ["exit"]},
    {"id": "exit",  "succ": []}
  ],
  "defs": {"x": ["B", "C"]}
}

Output (JSON on stdout)

{
  "entry": "entry",
  "rpo": ["entry", "C", "B", "join", "exit"],
  "reachable": ["entry", "C", "B", "join", "exit"],
  "unreachable": [],
  "idom": {"entry":"entry","B":"entry","C":"entry","join":"entry","exit":"join"},
  "dominanceFrontier": {"B":["join"], "C":["join"]},
  "phis": {
    "join": [
      {"var":"x","operands":[
        {"pred":"B","value":"x.1"},
        {"pred":"C","value":"x.2"}
      ]}
    ]
  },
  "irreducible": false,
  "irreducibleLoops": [],
  "ssaDefs": {"x.1":"B", "x.2":"C"}
}

Each operand is labelled with its predecessor block (pred) plus the SSA value reaching along that edge (value). ssaDefs maps every generated SSA name to its defining block.

2. Root-cause analysis: the traps this problem is built around

#	Trap	Symptom	Fix
1	Iterated vs. one-shot DF	Phis at `DF(X)` only misses loop-header phis; phis at every join inserts redundant ones.	Cytron worklist seeded by defs; place at `DF[x]`; re-enqueue a placed `y` only if `y` is not an original def. Computes `DF+(S)`.
2	Wrong `intersect` direction	CHK must climb the finger later in RPO.	`intersect` climbs while `rpoIdx[a] > rpoIdx[b]`. Verified against brute-force dominators.
3	Unreachable blocks in dominance	Corrupts idom/DF, phantom joins, dead phis/operands.	Reachability first; only reachable preds count toward `≥2`; only reachable defs seed.
4	Root self-loops / root back-edges	Formal DF puts the root in its own frontier → redundant trivial phi.	Classic Cytron: only blocks with `≥2` reachable predecessors contribute. Reachable non-entry self-loops already have a second pred.
5	Deduping phi operands by value	Loses an edge; phi no longer matches the CFG.	One operand per predecessor edge; parallel edges collapse to one distinct pred.
6	Irreducible detection by "SCC has >1 entry"	Misses irreducible loops nested inside a single-entry SCC.	T1/T2 reduction and residual SCCs after deleting dominance back-edges. Agree on 20 000 random CFGs.
7	No renaming / wrong operand value	Pred labels alone are not usable SSA.	Dominator-tree renaming; operand must dominate its predecessor or be the phi's self reference.
8	RPO vs. depth in `intersect`	Depths not known during iteration.	RPO indices fixed up front, monotone along idom chains.

3. Algorithm details

3.1 CHK dominance. idom[entry]=entry; iterate RPO until stable, intersecting idoms of reachable predecessors. intersect(a,b) climbs the later-RPO finger until they meet.

3.2 Dominance frontier. For each reachable block b with ≥2 reachable preds:

for p in preds(b): runner = p
                   while runner != idom(b):
                       DF[runner] += b
                       runner = idom(runner)

3.3 Cytron worklist (DF+).

W = reachable def blocks of v
placed = {}
while W:
  x = pop W
  for y in DF[x]:
    if y not in placed:
      place phi(v) at y
      placed += y
      if y not an original def of v: W += y

3.4 Renaming. Pre-order dominator-tree walk with per-variable stacks; push fresh names for phis/defs, fill successor phi operands with the current top, recurse, pop.

The exact fix (core of `main.go`)

// CHK intersect: climb the finger later in reverse postorder.
intersect := func(a, b int) int {
    for a != b {
        for idx[a] > idx[b] { a = idom[a] }
        for idx[b] > idx[a] { b = idom[b] }
    }
    return a
}

// Dominance frontier (classic Cytron).
for _, b := range d.rpo {
    if d.idom[b] == -1 { continue }
    multiPred := 0
    for _, p := range g.pred[b] { if d.reach[p] { multiPred++ } }
    if multiPred < 2 { continue }
    for _, p := range g.pred[b] {
        if !d.reach[p] { continue }
        runner := p
        for runner != d.idom[b] { add(runner, b); runner = d.idom[runner] }
    }
}

// Cytron phi worklist over DF+.
for _, v := range g.varList {
    placed, hasDef := map[int]bool{}, map[int]bool{}
    var queue []int
    for _, def := range g.varDefs[v] {
        if d.idom[def] == -1 { continue }
        hasDef[def] = true
        queue = append(queue, def)
    }
    for len(queue) > 0 {
        x := queue[0]; queue = queue[1:]
        for _, y := range df[x] {
            if placed[y] { continue }
            placed[y] = true
            phisAt[y] = append(phisAt[y], v)
            if !hasDef[y] { queue = append(queue, y) }
        }
    }
}

Irreducible loops (T1/T2-consistent):

// remove dominance back-edges, report residual cyclic SCCs
if d.dominates(v, u) { continue }   // edge u->v is a back edge

4. Full source

The complete runnable program (770 lines) and test harness (523 lines) are in:

~/SOLUTION.md
~/ssa/main.go
~/ssa/verify_test.go

Key output shapes are shown in §1; the CHK/DF/worklist/renaming/reducibility pieces are quoted in §3.

5. Verification

Differential testing against independent brute-force references:

Dominators — fixpoint dom(n) = {n} ∪ ⋂ dom(pred), then idom from strict-dominator sets.
Dominance frontier — direct definition: Y ∈ DF(X) iff X dominates a predecessor of Y and not strictly Y.
Phi placement — least fixed point of P = DF(S ∪ P).
SSA validity — each named operand defined at the phi block or at a block dominating its predecessor.
Reducibility — T1/T2 equals "no residual SCC after back-edge removal".
Operands — exactly one per reachable distinct predecessor.

20 000 random CFGs (≤9 nodes) plus fixed regression cases for self-loops, nested loops, unreachable blocks, parallel edges, schema variants, root back-edges, and nested irreducible loops.

Commands and results

go build -o ssa .
./ssa cases/diamond_two.json
go test ./...
go test -race ./...

--- PASS: TestDifferentialRandomized (0.59s)
--- PASS: TestSelfLoop
--- PASS: TestNestedLoopsPhiCount
--- PASS: TestUnreachableExcluded
--- PASS: TestSingleDistinctPredParallelEdges
--- PASS: TestSingleDefJoinNoPhi
--- PASS: TestIrreducibleNestedLoop
--- PASS: TestEntryBackEdgeNoRedundantPhi
--- PASS: TestSchemaVariants
--- PASS: TestEntrySelfLoopNoRedundantPhi
ok  ssa  0.598s

Hand-checked behaviours

Diamond, single def at entry → no phi.
Diamond, defs on both branches → phi at join: (B, x.1), (C, x.2).
Simple loop → phi at header: (entry, x.1), (body, x.2).
Self-loop H→H → phi at H; lone root self-loop → no phi.
Unreachable block → under unreachable, no idom, no frontier, no phi.
Parallel edges into a join → one distinct predecessor, no phi.
Nested irreducible loop inside a single-entry SCC → irreducible: true, residual SCC reported, matching T1/T2.

Evidence & signatures

# Evidence
- Problem class: ssa-dominance-frontier-phi-insertion-minimal
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-16T16:11:37.658Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build minimal SSA form for a control-flow graph supplied as JSON (nodes with successor lists, entry node id, blocks that define a variable). Implement Cooper-Harvey-Kennedy iterative dominance to compute immediate dominators, then derive dominance frontiers, then run the classic Cytron et al. phi-insertion worklist (using the iterated dominance frontier of the variable's def blocks) so that NO redundant phi is inserted. Emit per-block phi lists where each operand is labelled with the predecessor block it corresponds to, and report unreachable blocks (excluded from dominator computation) and irreducible loops detected via the SCC/T1-T2 test. Must be correct on self-loops, nested loops, and join blocks with a single distinct predecessor value.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "ssa-dominance-frontier-phi-insertion-minimal", "provider": "openrouter", "solved_at": "2026-09-16T16:11:37.658Z", "version": "1.26"}

Generated from the verified corpus · MIT licensedBack to the catalog

ssa-dominance-frontier-phi-insertion-minimal

Answer 1

Minimal SSA from a JSON CFG: Correct Dominance, Dominance Frontiers, and Redundancy-Free Phi Insertion

TL;DR

1. Contract

Input (stdin or argv[1])

Output (JSON on stdout)

2. Root-cause analysis: the traps this problem is built around

3. Algorithm details

The exact fix (core of main.go)

4. Full source

5. Verification

Commands and results

Hand-checked behaviours

Evidence & signatures

Answer 2

Minimal SSA from a JSON CFG: Correct Dominance, Dominance Frontiers, and Redundancy-Free Phi Insertion

TL;DR

1. Contract

Input (stdin or argv[1])

Output (JSON on stdout)

2. Root-cause analysis: the traps this problem is built around

3. Algorithm details

The exact fix (core of main.go)

4. Full source

5. Verification

Commands and results

Hand-checked behaviours

Evidence & signatures

Input (stdin or `argv[1]`)

The exact fix (core of `main.go`)

Input (stdin or `argv[1]`)

The exact fix (core of `main.go`)