Problem class: go-loop-rotation-ssa-licm-preheader-invalidation
Below is the verified solution. I created and ran a standalone reference implementation (~/work/lr, all tests passing) plus a full write-up at ~/work/SOLUTION.md.
Problem class: go-loop-rotation-ssa-licm-preheader-invalidation
Environment: go1.26 (linux/amd64), cmd/compile/internal/ssa
Go 1.26 already has a pass called loopRotate (src/cmd/compile/internal/ssa/looprotate.go), but it only reorders basic blocks to put the loop-predecessor first; it does not synthesize a preheader, rewrite the header's terminating branch, or clone the header. The task is a stronger, CFG-mutating rotation:
before after
P -> H P -> G (synthesized preheader/guard)
H: phis; c=cond(phi); G: c0=cond(init); if c0 -> B else X
if c -> B else X ... B (phis re-pointed) ... L ...
... B ... L ... H: c1=cond(update); if c1 -> B else X (cloned header)
L -> H X: phis gain an operand from G
The pass must keep SSA, the dominator tree, the dominance frontier and the loop nest consistent, and it must keep the LICM / PRE passes that run after it correct.
Rotation is not a local edit; it changes which blocks dominate which. The failures come from independent invariants that a naive pass breaks.
When the loop-carried phis move from the header H to the loop entry B, every use of the old phi must be rewritten: the loop body (which now runs before H on the first iteration), the cloned header H (bottom test must use the updated value), and every exiting block reachable from the loop, including secondary exits from inside the body. An exit phi that keeps In[H] = oldPhi names a value that was deleted or does not dominate the edge. Go's checkFunc catches this: for OpPhi it checks the argument against b.Preds[i].b and reports arg %d of value %s does not dominate, arg=%s (check.go).
// func.go
func (f *Func) invalidateCFG() {
f.cachedPostorder = nil
f.cachedIdom = nil
f.cachedSdom = nil
f.cachedLoopnest = nil
}
Idom(), Sdom() and loopnest() consult those caches. Any analysis that cached a loop's preheader or a SparseTree before rotation and reuses it after rotation decides hoisting/insertion against a graph that no longer exists. LICM hoists to the old preheader; PRE computes dominance-frontier insertion points from stale DF. The fix is to treat the synthesized guard as the only legal preheader and rebuild every placement decision from a fresh tree.
After rotation the guard G is the real preheader and defines the entry condition c0 (and possibly other invariant values cloned from the header). A body value w whose operands come from G is loop-invariant but not hoistable above G: k (defined in G) does not dominate the block before G. The invariant test must be preheader dominates every operand definition, and the hoisted value must be appended after the guard's own instructions.
for i := 0; i < n; i++ { body } runs body zero times when n <= 0. A naive rotation into do { body } while (...) executes body once. The guard must be evaluated before the first body execution, and the bottom test must test the updated value, not the incoming phi.
Rotation needs a unique loop entry (preheader) and a unique back edge. In an irreducible cycle neither block dominates the other, so there is no natural loop, no header, and no single preheader to clone. The pass must detect this via the dominator tree and skip it.
For one loop with header H, unique latch L, unique outside predecessor P, loop edge H.Succs[0] == B, exit edge H.Succs[1] == X:
G := clone of H's non-phi instructions + condition, substituting each header phi by its In[P] value. P.Succs becomes G; G.Succs = {B, X}.B with In[G] = In_H[P] and In[H] = update.H as the bottom test: H.Cond is cond(update). Remove H's phis.H use update, from the new guard edge use init, otherwise use the relocated phi.invalidateCFG in the real compiler).// rotate.go -- core of the transform
func (f *Func) rotateOne(H, L, P *Block, body map[*Block]bool) bool {
if len(H.Phis) == 0 { return false }
for _, ph := range H.Phis {
if ph.In[P] == nil || ph.In[L] == nil { return false }
}
B := H.Succs[0]; X := H.Succs[1]
if !body[B] || body[X] || B == H || X == H { return false }
initOf := map[*Value]*Value{}
for _, ph := range H.Phis { initOf[ph.V] = ph.In[P] }
// (1) clone the header test into the guard
G := f.NewBlock(KIf, H.Name+".guard")
gm := f.cloneInto(G, H, initOf) // cloneInto never mutates H
G.Cond = gm[H.Cond]
if G.Cond == nil { return false }
// (2) relocated phis in the loop entry
newPhi := map[*Value]*Phi{}
for _, ph := range H.Phis {
nv := f.NewValue(OpPhi, ph.V.Name, 0)
newPhi[ph.V] = B.AddPhi(nv, map[*Block]*Value{})
}
// (3) rebuild the body; this produces the new `update` value
substBody := map[*Value]*Value{}
for old, np := range newPhi { substBody[old] = np.V }
for old, g := range gm { substBody[old] = g }
var bodyBlocks []*Block
for b := range body { if b != H { bodyBlocks = append(bodyBlocks, b) } }
bm := f.rebuildBlocks(bodyBlocks, substBody)
update2 := map[*Value]*Value{}
for _, ph := range H.Phis {
u := ph.In[L]
switch {
case bm[u] != nil: update2[ph.V] = bm[u]
case substBody[u] != nil: update2[ph.V] = substBody[u]
default: update2[ph.V] = u
}
newPhi[ph.V].In[G] = ph.In[P]
newPhi[ph.V].In[H] = update2[ph.V]
}
// (4) re-point every phi outside H/G that named an old header phi
for _, b := range f.Blocks {
if b == H || b == G { continue }
for _, q := range b.Phis {
for p, val := range q.In {
if _, isOld := initOf[val]; isOld {
switch p {
case H: q.In[p] = update2[val]
case G: q.In[p] = initOf[val]
default: q.In[p] = newPhi[val].V
}
}
}
}
}
for _, q := range X.Phis { // X gains the guard edge
for _, old := range keyVals(initOf) {
if q.In[H] == update2[old] { q.In[G] = initOf[old] }
}
}
// (5) header -> bottom test, testing the updated value
substH := map[*Value]*Value{}
for old := range newPhi { substH[old] = update2[old] }
f.rebuildBlocks([]*Block{H}, substH)
H.Phis = nil
// (6) rewire and let callers invalidate CFG-derived caches
f.ReplaceSucc(P, H, G)
G.Succs = []*Block{B, X}
return true
}
rebuildBlocks has one subtle rule: a value produced by subst is defined elsewhere, so it is not re-homed into the rebuilt block (a Value has a single defining block). Re-adding a guard clone to the body would silently change its Block and move it out of dominance:
for _, v := range old {
nv := cl(v)
if nv.Block == nil { // freshly cloned here
b.AddInst(nv)
} // else: shared / guard clone
}
func (f *Func) hoistable(v *Value, pre *Block, body map[*Block]bool) bool {
if v.Op == OpConst || v.Op == OpPhi { return false }
for _, a := range v.Args {
if a.Op == OpConst { continue } // freely rematerializable
if body[a.Block] && a.Block != pre { // still loop-carried
return false
}
if !f.dominates(pre, a.Block) { // e.g. guard-defined operand
return false
}
}
return true
}
and the move appends to the end of the preheader, after the guard's own computations:
v.Block = P
P.Insts = append(P.Insts, v)
The buggy variant (HoistNaive) inserts at Preds(P)[0]; the verifier then reports that w uses k defined in the guard which does not dominate the insertion point.
func (f *Func) PreInsertNCD(blocks []*Block) (*Block, bool) {
idom := f.Idom() // MUST be rebuilt after rotation
a := blocks[0]
for _, b := range blocks[1:] { a = ncd(f, idom, a, b) }
return a, true
}
After rotation the nearest common dominator of two loop-body uses is the guard, not the old preheader. Building idom from a pre-rotation cache gives the old answer; the real compiler recomputes because AddEdgeTo/removeSucc call invalidateCFG.
cmd/compile/internal/ssa| reference model | cmd/compile/internal/ssa |
|---|---|
f.Preds(b) from Succs |
cross-linked b.Preds / b.Succs (block.go) |
f.dominates / f.Idom |
f.Idom(), f.Sdom(), SparseTree.IsAncestorEq (dom.go) |
f.DF() |
DominanceFrontier, rebuilt via newSparseTree (dom.go) |
f.findLoop / naturalLoop |
f.loopnest(), loopnest.forst, hasIrreducible (dom.go) |
f.ReplaceSucc |
Block.AddEdgeTo, removePred, removeSucc (block.go) |
f.rebuildBlocks |
Value.copyInto, Edge/phi fixups in shortcircuit.go |
| cache invalidation | f.invalidateCFG() (func.go) |
| verifier | checkFunc (check.go) |
An integration must call f.invalidateCFG() (or AddEdgeTo) after rewiring and re-run f.loopnest() before LICM/PRE.
TestRotatePreservesSemantics — result and dynamic execution counts unchanged for n = 0, 1, 3, 7; zero-trip loop executes the body zero times after rotation (loop-carried / do-while regression).TestRotateMultipleExits — body contains an early exit; checks results and per-block counts before/after.TestRotateSkipsIrreducible — the two-entry cycle is left untouched and stays valid.TestPhiAndDominatorConsistency — relocated phis name the guard and cloned header; DF[cloned header] contains the loop entry and the exit; CheckSSA passes.TestGuardAwareHoisting — w is hoisted into the guard after the guard-defined k; the naive placement above the guard fails CheckSSA.TestPreInsertAfterRotation — the PRE insertion point dominates all inputs.The verifier enforces the exact invariants:
// every phi operand must dominate the edge it flows along
if !f.dominates(v.Block, p) {
return fmt.Errorf("phi %s in %s: operand %s defined in %s does not dominate pred %s", ...)
}
// instruction operands must dominate the block or be earlier in it;
// phi results count as defined-before-instructions
$ cd ~/work/lr
$ go vet ./...
$ go test -count=1 -v ./...
=== RUN TestRotatePreservesSemantics
--- PASS: TestRotatePreservesSemantics (0.00s)
=== RUN TestRotateMultipleExits
--- PASS: TestRotateMultipleExits (0.00s)
=== RUN TestRotateSkipsIrreducible
--- PASS: TestRotateSkipsIrreducible (0.00s)
=== RUN TestPhiAndDominatorConsistency
--- PASS: TestPhiAndDominatorConsistency (0.00s)
=== RUN TestGuardAwareHoisting
--- PASS: TestGuardAwareHoisting (0.00s)
=== RUN TestPreInsertAfterRotation
--- PASS: TestPreInsertAfterRotation (0.00s)
PASS
ok lr 0.003s
To exercise the same shape of test against the real (read-only) compiler package, use a Go build overlay:
$ cat > /tmp/overlay.json <<'EOF'
{"Replace": {
"/usr/lib/go-1.26/src/cmd/compile/internal/ssa/zz_rotate_test.go":
"~/work/lr/zz_rotate_test.go"
}}
EOF
$ go test -overlay=/tmp/overlay.json cmd/compile/internal/ssa
CheckFunc then plays the role of CheckSSA.
invalidateCFG) after every edge mutation.The verified reference implementation is at ~/work/lr/ (ssa.go, rotate.go, lr_test.go); the full write-up is ~/work/SOLUTION.md.
# Evidence - Problem class: go-loop-rotation-ssa-licm-preheader-invalidation - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-29T22:13:35.412Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a loop-rotation pass over an SSA IR that synthesizes a dedicated preheader, rewrites the header's back-edge condition into a loop-entry guard, and clones the original header so the rotated body executes at least once. Then make subsequent LICM and SSA-based partial-redundancy-elimination passes correct on the rotated CFG: phi operands must be re-pointed to the cloned header, the dominator tree and dominance-frontier sets must stay consistent, and hoisting candidates whose operands are defined only inside the rotated guard must never be promoted above it. Include regression cases for irreducible CFGs, loops with multiple exiting blocks, and loop-carried dependencies where naive rotation silently changes the number of dynamic executions.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-loop-rotation-ssa-licm-preheader-invalidation", "provider": "openrouter", "solved_at": "2026-09-29T22:13:35.429Z", "version": "1.26"}Below is the verified solution. I created and ran a standalone reference implementation (~/work/lr, all tests passing) plus a full write-up at ~/work/SOLUTION.md.
Problem class: go-loop-rotation-ssa-licm-preheader-invalidation
Environment: go1.26 (linux/amd64), cmd/compile/internal/ssa
Go 1.26 already has a pass called loopRotate (src/cmd/compile/internal/ssa/looprotate.go), but it only reorders basic blocks to put the loop-predecessor first; it does not synthesize a preheader, rewrite the header's terminating branch, or clone the header. The task is a stronger, CFG-mutating rotation:
before after
P -> H P -> G (synthesized preheader/guard)
H: phis; c=cond(phi); G: c0=cond(init); if c0 -> B else X
if c -> B else X ... B (phis re-pointed) ... L ...
... B ... L ... H: c1=cond(update); if c1 -> B else X (cloned header)
L -> H X: phis gain an operand from G
The pass must keep SSA, the dominator tree, the dominance frontier and the loop nest consistent, and it must keep the LICM / PRE passes that run after it correct.
Rotation is not a local edit; it changes which blocks dominate which. The failures come from independent invariants that a naive pass breaks.
When the loop-carried phis move from the header H to the loop entry B, every use of the old phi must be rewritten: the loop body (which now runs before H on the first iteration), the cloned header H (bottom test must use the updated value), and every exiting block reachable from the loop, including secondary exits from inside the body. An exit phi that keeps In[H] = oldPhi names a value that was deleted or does not dominate the edge. Go's checkFunc catches this: for OpPhi it checks the argument against b.Preds[i].b and reports arg %d of value %s does not dominate, arg=%s (check.go).
// func.go
func (f *Func) invalidateCFG() {
f.cachedPostorder = nil
f.cachedIdom = nil
f.cachedSdom = nil
f.cachedLoopnest = nil
}
Idom(), Sdom() and loopnest() consult those caches. Any analysis that cached a loop's preheader or a SparseTree before rotation and reuses it after rotation decides hoisting/insertion against a graph that no longer exists. LICM hoists to the old preheader; PRE computes dominance-frontier insertion points from stale DF. The fix is to treat the synthesized guard as the only legal preheader and rebuild every placement decision from a fresh tree.
After rotation the guard G is the real preheader and defines the entry condition c0 (and possibly other invariant values cloned from the header). A body value w whose operands come from G is loop-invariant but not hoistable above G: k (defined in G) does not dominate the block before G. The invariant test must be preheader dominates every operand definition, and the hoisted value must be appended after the guard's own instructions.
for i := 0; i < n; i++ { body } runs body zero times when n <= 0. A naive rotation into do { body } while (...) executes body once. The guard must be evaluated before the first body execution, and the bottom test must test the updated value, not the incoming phi.
Rotation needs a unique loop entry (preheader) and a unique back edge. In an irreducible cycle neither block dominates the other, so there is no natural loop, no header, and no single preheader to clone. The pass must detect this via the dominator tree and skip it.
For one loop with header H, unique latch L, unique outside predecessor P, loop edge H.Succs[0] == B, exit edge H.Succs[1] == X:
G := clone of H's non-phi instructions + condition, substituting each header phi by its In[P] value. P.Succs becomes G; G.Succs = {B, X}.B with In[G] = In_H[P] and In[H] = update.H as the bottom test: H.Cond is cond(update). Remove H's phis.H use update, from the new guard edge use init, otherwise use the relocated phi.invalidateCFG in the real compiler).// rotate.go -- core of the transform
func (f *Func) rotateOne(H, L, P *Block, body map[*Block]bool) bool {
if len(H.Phis) == 0 { return false }
for _, ph := range H.Phis {
if ph.In[P] == nil || ph.In[L] == nil { return false }
}
B := H.Succs[0]; X := H.Succs[1]
if !body[B] || body[X] || B == H || X == H { return false }
initOf := map[*Value]*Value{}
for _, ph := range H.Phis { initOf[ph.V] = ph.In[P] }
// (1) clone the header test into the guard
G := f.NewBlock(KIf, H.Name+".guard")
gm := f.cloneInto(G, H, initOf) // cloneInto never mutates H
G.Cond = gm[H.Cond]
if G.Cond == nil { return false }
// (2) relocated phis in the loop entry
newPhi := map[*Value]*Phi{}
for _, ph := range H.Phis {
nv := f.NewValue(OpPhi, ph.V.Name, 0)
newPhi[ph.V] = B.AddPhi(nv, map[*Block]*Value{})
}
// (3) rebuild the body; this produces the new `update` value
substBody := map[*Value]*Value{}
for old, np := range newPhi { substBody[old] = np.V }
for old, g := range gm { substBody[old] = g }
var bodyBlocks []*Block
for b := range body { if b != H { bodyBlocks = append(bodyBlocks, b) } }
bm := f.rebuildBlocks(bodyBlocks, substBody)
update2 := map[*Value]*Value{}
for _, ph := range H.Phis {
u := ph.In[L]
switch {
case bm[u] != nil: update2[ph.V] = bm[u]
case substBody[u] != nil: update2[ph.V] = substBody[u]
default: update2[ph.V] = u
}
newPhi[ph.V].In[G] = ph.In[P]
newPhi[ph.V].In[H] = update2[ph.V]
}
// (4) re-point every phi outside H/G that named an old header phi
for _, b := range f.Blocks {
if b == H || b == G { continue }
for _, q := range b.Phis {
for p, val := range q.In {
if _, isOld := initOf[val]; isOld {
switch p {
case H: q.In[p] = update2[val]
case G: q.In[p] = initOf[val]
default: q.In[p] = newPhi[val].V
}
}
}
}
}
for _, q := range X.Phis { // X gains the guard edge
for _, old := range keyVals(initOf) {
if q.In[H] == update2[old] { q.In[G] = initOf[old] }
}
}
// (5) header -> bottom test, testing the updated value
substH := map[*Value]*Value{}
for old := range newPhi { substH[old] = update2[old] }
f.rebuildBlocks([]*Block{H}, substH)
H.Phis = nil
// (6) rewire and let callers invalidate CFG-derived caches
f.ReplaceSucc(P, H, G)
G.Succs = []*Block{B, X}
return true
}
rebuildBlocks has one subtle rule: a value produced by subst is defined elsewhere, so it is not re-homed into the rebuilt block (a Value has a single defining block). Re-adding a guard clone to the body would silently change its Block and move it out of dominance:
for _, v := range old {
nv := cl(v)
if nv.Block == nil { // freshly cloned here
b.AddInst(nv)
} // else: shared / guard clone
}
func (f *Func) hoistable(v *Value, pre *Block, body map[*Block]bool) bool {
if v.Op == OpConst || v.Op == OpPhi { return false }
for _, a := range v.Args {
if a.Op == OpConst { continue } // freely rematerializable
if body[a.Block] && a.Block != pre { // still loop-carried
return false
}
if !f.dominates(pre, a.Block) { // e.g. guard-defined operand
return false
}
}
return true
}
and the move appends to the end of the preheader, after the guard's own computations:
v.Block = P
P.Insts = append(P.Insts, v)
The buggy variant (HoistNaive) inserts at Preds(P)[0]; the verifier then reports that w uses k defined in the guard which does not dominate the insertion point.
func (f *Func) PreInsertNCD(blocks []*Block) (*Block, bool) {
idom := f.Idom() // MUST be rebuilt after rotation
a := blocks[0]
for _, b := range blocks[1:] { a = ncd(f, idom, a, b) }
return a, true
}
After rotation the nearest common dominator of two loop-body uses is the guard, not the old preheader. Building idom from a pre-rotation cache gives the old answer; the real compiler recomputes because AddEdgeTo/removeSucc call invalidateCFG.
cmd/compile/internal/ssa| reference model | cmd/compile/internal/ssa |
|---|---|
f.Preds(b) from Succs |
cross-linked b.Preds / b.Succs (block.go) |
f.dominates / f.Idom |
f.Idom(), f.Sdom(), SparseTree.IsAncestorEq (dom.go) |
f.DF() |
DominanceFrontier, rebuilt via newSparseTree (dom.go) |
f.findLoop / naturalLoop |
f.loopnest(), loopnest.forst, hasIrreducible (dom.go) |
f.ReplaceSucc |
Block.AddEdgeTo, removePred, removeSucc (block.go) |
f.rebuildBlocks |
Value.copyInto, Edge/phi fixups in shortcircuit.go |
| cache invalidation | f.invalidateCFG() (func.go) |
| verifier | checkFunc (check.go) |
An integration must call f.invalidateCFG() (or AddEdgeTo) after rewiring and re-run f.loopnest() before LICM/PRE.
TestRotatePreservesSemantics — result and dynamic execution counts unchanged for n = 0, 1, 3, 7; zero-trip loop executes the body zero times after rotation (loop-carried / do-while regression).TestRotateMultipleExits — body contains an early exit; checks results and per-block counts before/after.TestRotateSkipsIrreducible — the two-entry cycle is left untouched and stays valid.TestPhiAndDominatorConsistency — relocated phis name the guard and cloned header; DF[cloned header] contains the loop entry and the exit; CheckSSA passes.TestGuardAwareHoisting — w is hoisted into the guard after the guard-defined k; the naive placement above the guard fails CheckSSA.TestPreInsertAfterRotation — the PRE insertion point dominates all inputs.The verifier enforces the exact invariants:
// every phi operand must dominate the edge it flows along
if !f.dominates(v.Block, p) {
return fmt.Errorf("phi %s in %s: operand %s defined in %s does not dominate pred %s", ...)
}
// instruction operands must dominate the block or be earlier in it;
// phi results count as defined-before-instructions
$ cd ~/work/lr
$ go vet ./...
$ go test -count=1 -v ./...
=== RUN TestRotatePreservesSemantics
--- PASS: TestRotatePreservesSemantics (0.00s)
=== RUN TestRotateMultipleExits
--- PASS: TestRotateMultipleExits (0.00s)
=== RUN TestRotateSkipsIrreducible
--- PASS: TestRotateSkipsIrreducible (0.00s)
=== RUN TestPhiAndDominatorConsistency
--- PASS: TestPhiAndDominatorConsistency (0.00s)
=== RUN TestGuardAwareHoisting
--- PASS: TestGuardAwareHoisting (0.00s)
=== RUN TestPreInsertAfterRotation
--- PASS: TestPreInsertAfterRotation (0.00s)
PASS
ok lr 0.003s
To exercise the same shape of test against the real (read-only) compiler package, use a Go build overlay:
$ cat > /tmp/overlay.json <<'EOF'
{"Replace": {
"/usr/lib/go-1.26/src/cmd/compile/internal/ssa/zz_rotate_test.go":
"~/work/lr/zz_rotate_test.go"
}}
EOF
$ go test -overlay=/tmp/overlay.json cmd/compile/internal/ssa
CheckFunc then plays the role of CheckSSA.
invalidateCFG) after every edge mutation.The verified reference implementation is at ~/work/lr/ (ssa.go, rotate.go, lr_test.go); the full write-up is ~/work/SOLUTION.md.
# Evidence - Problem class: go-loop-rotation-ssa-licm-preheader-invalidation - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-29T22:13:35.412Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a loop-rotation pass over an SSA IR that synthesizes a dedicated preheader, rewrites the header's back-edge condition into a loop-entry guard, and clones the original header so the rotated body executes at least once. Then make subsequent LICM and SSA-based partial-redundancy-elimination passes correct on the rotated CFG: phi operands must be re-pointed to the cloned header, the dominator tree and dominance-frontier sets must stay consistent, and hoisting candidates whose operands are defined only inside the rotated guard must never be promoted above it. Include regression cases for irreducible CFGs, loops with multiple exiting blocks, and loop-carried dependencies where naive rotation silently changes the number of dynamic executions.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-loop-rotation-ssa-licm-preheader-invalidation", "provider": "openrouter", "solved_at": "2026-09-29T22:13:35.429Z", "version": "1.26"}