[go] internal/ssa: Implemented data driven live variable analysis.
8 views
Skip to first unread message
Frank Kuehnel (Gerrit)
Dec 20, 2025, 10:04:21 AM (2 days ago) Dec 20
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Frank Kuehnel has uploaded the change for review![]( "Open in Gerrit")
Commit message
internal/ssa: Implemented data driven live variable analysis.
Details are here: https://github.com/fkuehnel/golang-cfg/blob/main/cfg_realworld.pdf
Change-Id: I052e7d41133f1256802ab2c3cda918cbe083015c
Change diff
diff --git a/src/cmd/compile/internal/ssa/dom.go b/src/cmd/compile/internal/ssa/dom.go
index 1aa0c2d..1b7120e 100644
--- a/src/cmd/compile/internal/ssa/dom.go
+++ b/src/cmd/compile/internal/ssa/dom.go
@@ -21,6 +21,18 @@
// postorderWithNumbering provides a DFS postordering.
// This seems to make loop-finding more robust.
func postorderWithNumbering(f *Func, ponums []int32) []*Block {
+ valid := make([]bool, f.NumBlocks())
+ for i := 0; i < len(valid); i++ {
+ valid[i] = true
+ }
+ return poWithNumberingForValidBlocks(f.Entry, valid, ponums)
+}
+
+func poWithNumberingForValidBlocks(entry *Block, valid []bool, ponums []int32) []*Block {
+ f := entry.Func
+ if len(valid) != f.NumBlocks() {
+ f.Fatalf("length of valid blocks is expected to be %d", f.NumBlocks())
+ }
seen := f.Cache.allocBoolSlice(f.NumBlocks())
defer f.Cache.freeBoolSlice(seen)
@@ -31,8 +43,8 @@
// A constant bound allows this to be stack-allocated. 32 is
// enough to cover almost every postorderWithNumbering call.
s := make([]blockAndIndex, 0, 32)
- s = append(s, blockAndIndex{b: f.Entry})
- seen[f.Entry.ID] = true
+ s = append(s, blockAndIndex{b: entry})
+ seen[entry.ID] = true
for len(s) > 0 {
tos := len(s) - 1
x := s[tos]
@@ -40,7 +52,7 @@
if i := x.index; i < len(b.Succs) {
s[tos].index++
bb := b.Succs[i].Block()
- if !seen[bb.ID] {
+ if valid[bb.ID] && !seen[bb.ID] {
seen[bb.ID] = true
s = append(s, blockAndIndex{b: bb})
}
@@ -172,7 +184,7 @@
return n
}
-// compressOrig is the "simple" compress function from LT paper.
+// compressOrig is the "simple" compress function from LT paper
func compressOrig(v ID, ancestor, semi, label []ID) {
if ancestor[ancestor[v]] != 0 {
compressOrig(ancestor[v], ancestor, semi, label)
@@ -183,7 +195,7 @@
}
}
-// evalOrig is the "simple" eval function from LT paper.
+// evalOrig is the "simple" eval function from LT paper
func evalOrig(v ID, ancestor, semi, label []ID) ID {
if ancestor[v] == 0 {
return v
@@ -266,3 +278,22 @@
}
return b
}
+
+// finds postorder and reverse postorder within SCC.
+func sccAlternatingOrders(scc []*Block) (exitward, entryward []*Block) {
+ if len(scc) < 2 {
+ return scc, scc
+ }
+ entry := scc[0]
+ f := entry.Func
+
+ // limit the graph to only blocks within the SCC
+ valid := make([]bool, f.NumBlocks())
+ for _, b := range scc {
+ valid[b.ID] = true
+ }
+ exitward = poWithNumberingForValidBlocks(entry, valid, nil)
+ entryward = poWithNumberingForValidBlocks(exitward[0], valid, nil)
+
+ return exitward, entryward
+}
diff --git a/src/cmd/compile/internal/ssa/regalloc.go b/src/cmd/compile/internal/ssa/regalloc.go
index a0257f30..b52e8c2 100644
--- a/src/cmd/compile/internal/ssa/regalloc.go
+++ b/src/cmd/compile/internal/ssa/regalloc.go
@@ -2833,10 +2833,17 @@
// computeLive computes a map from block ID to a list of value IDs live at the end
// of that block. Together with the value ID is a count of how many instructions
// to the next use of that value. The resulting map is stored in s.live.
+//
+// Optimized liveness analysis exploiting real-world CFG distribution:
+// - 68% of CFGs are acyclic: single postorder pass, NO SCC computation
+// - 24% have exactly one non-trivial SCC: localized 3-pass iteration
+// - 8% have multiple SCCs: full SCC-based 3-pass iteration
+//
+// Key insight: sccPartition() is expensive and unnecessary for the majority case.
+// Based on empirical analysis of 290,000 functions from the Go toolchain.
func (s *regAllocState) computeLive() {
f := s.f
- // single block functions do not have variables that are live across
- // branches
+ // single block functions do not have variables that are live across branches
if len(f.Blocks) == 1 {
return
}
@@ -2845,8 +2852,6 @@
s.desired = make([]desiredState, f.NumBlocks())
s.loopnest = f.loopnest()
- rematIDs := make([]ID, 0, 64)
-
live := f.newSparseMapPos(f.NumValues())
defer f.retSparseMapPos(live)
t := f.newSparseMapPos(f.NumValues())
@@ -2854,172 +2859,255 @@
s.loopnest.computeUnavoidableCalls()
- // Liveness analysis.
- // This is an adapted version of the algorithm described in chapter 2.4.2
- // of Fabrice Rastello's On Sparse Intermediate Representations.
- // https://web.archive.org/web/20240417212122if_/https://inria.hal.science/hal-00761555/file/habilitation.pdf#section.50
- //
- // For our implementation, we fall back to a traditional iterative algorithm when we encounter
- // Irreducible CFGs. They are very uncommon in Go code because they need to be constructed with
- // gotos and our current loopnest definition does not compute all the information that
- // we'd need to compute the loop ancestors for that step of the algorithm.
- //
- // Additionally, instead of only considering non-loop successors in the initial DFS phase,
- // we compute the liveout as the union of all successors. This larger liveout set is a subset
- // of the final liveout for the block and adding this information in the DFS phase means that
- // we get slightly more accurate distance information.
- var loopLiveIn map[*loop][]liveInfo
- var numCalls []int32
- if len(s.loopnest.loops) > 0 && !s.loopnest.hasIrreducible {
- loopLiveIn = make(map[*loop][]liveInfo)
- numCalls = f.Cache.allocInt32Slice(f.NumBlocks())
- defer f.Cache.freeInt32Slice(numCalls)
- }
-
- for {
- changed := false
-
- for _, b := range po {
- // Start with known live values at the end of the block.
- live.clear()
- for _, e := range s.live[b.ID] {
- live.set(e.ID, e.dist, e.pos)
- }
- update := false
- // arguments to phi nodes are live at this blocks out
- for _, e := range b.Succs {
- succ := e.b
- delta := branchDistance(b, succ)
- for _, v := range succ.Values {
- if v.Op != OpPhi {
- break
- }
- arg := v.Args[e.i]
- if s.values[arg.ID].needReg && (!live.contains(arg.ID) || delta < live.get(arg.ID)) {
- live.set(arg.ID, delta, v.Pos)
- update = true
- }
- }
- }
- if update {
- s.live[b.ID] = updateLive(live, s.live[b.ID])
- }
- // Add len(b.Values) to adjust from end-of-block distance
- // to beginning-of-block distance.
- c := live.contents()
- for i := range c {
- c[i].val += int32(len(b.Values))
- }
-
- // Mark control values as live
- for _, c := range b.ControlValues() {
- if s.values[c.ID].needReg {
- live.set(c.ID, int32(len(b.Values)), b.Pos)
- }
- }
-
- for i := len(b.Values) - 1; i >= 0; i-- {
- v := b.Values[i]
- live.remove(v.ID)
- if v.Op == OpPhi {
- continue
- }
- if opcodeTable[v.Op].call {
- if numCalls != nil {
- numCalls[b.ID]++
- }
- rematIDs = rematIDs[:0]
- c := live.contents()
- for i := range c {
- c[i].val += unlikelyDistance
- vid := c[i].key
- if s.values[vid].rematerializeable {
- rematIDs = append(rematIDs, vid)
- }
- }
- // We don't spill rematerializeable values, and assuming they
- // are live across a call would only force shuffle to add some
- // (dead) constant rematerialization. Remove them.
- for _, r := range rematIDs {
- live.remove(r)
- }
- }
- for _, a := range v.Args {
- if s.values[a.ID].needReg {
- live.set(a.ID, int32(i), v.Pos)
- }
- }
- }
- // This is a loop header, save our live-in so that
- // we can use it to fill in the loop bodies later
- if loopLiveIn != nil {
- loop := s.loopnest.b2l[b.ID]
- if loop != nil && loop.header.ID == b.ID {
- loopLiveIn[loop] = updateLive(live, nil)
- }
- }
- // For each predecessor of b, expand its list of live-at-end values.
- // invariant: live contains the values live at the start of b
- for _, e := range b.Preds {
- p := e.b
- delta := branchDistance(p, b)
-
- // Start t off with the previously known live values at the end of p.
- t.clear()
- for _, e := range s.live[p.ID] {
- t.set(e.ID, e.dist, e.pos)
- }
- update := false
-
- // Add new live values from scanning this block.
- for _, e := range live.contents() {
- d := e.val + delta
- if !t.contains(e.key) || d < t.get(e.key) {
- update = true
- t.set(e.key, d, e.pos)
- }
- }
-
- if !update {
- continue
- }
- s.live[p.ID] = updateLive(t, s.live[p.ID])
- changed = true
- }
- }
-
- // Doing a traditional iterative algorithm and have run
- // out of changes
- if !changed {
- break
- }
-
- // Doing a pre-pass and will fill in the liveness information
- // later
- if loopLiveIn != nil {
- break
- }
- // For loopless code, we have full liveness info after a single
- // iteration
- if len(s.loopnest.loops) == 0 {
- break
- }
- }
- if f.pass.debug > regDebug {
- s.debugPrintLive("after dfs walk", f, s.live, s.desired)
- }
-
- // irreducible CFGs and functions without loops are already
- // done, compute their desired registers and return
- if loopLiveIn == nil {
- s.computeDesired()
+ // FAST PATH: Acyclic CFGs (68% of real-world functions)
+ // No loops = no cycles = single postorder pass suffices.
+ // Skip SCC computation entirely - it's wasted work for the majority case.
+ if len(s.loopnest.loops) == 0 {
+ s.computeLiveAcyclic(po, live, t)
return
}
- // Walk the loopnest from outer to inner, adding
- // all live-in values from their parent. Instead of
- // a recursive algorithm, iterate in depth order.
- // TODO(dmo): can we permute the loopnest? can we avoid this copy?
+ // FALLBACK: Irreducible CFGs
+ // Process all blocks together with 3-pass alternating iteration.
+ // SCC decomposition assumes reducible loops, so skip it here.
+ if s.loopnest.hasIrreducible {
+ s.computeLiveIrreducible(po, live, t)
+ return
+ }
+
+ // LOOP PATH: Reducible CFGs with loops (32% of functions)
+ // Use SCC decomposition with 3-pass convergence (empirical guarantee, no proof).
+ s.computeLiveWithLoops(po, live, t)
+}
+
+// computeLiveAcyclic handles the common case of acyclic CFGs.
+// A single postorder pass is sufficient - no iteration, no SCC computation.
+// This covers 68% of real-world functions.
+func (s *regAllocState) computeLiveAcyclic(po []*Block, live, t *sparseMapPos) {
+ f := s.f
+ rematIDs := make([]ID, 0, 64)
+
+ // Single pass in postorder (exits first, entry last).
+ // For backward analysis on DAGs, this visits each node after all its
+ // successors, which is optimal - no iteration needed.
+ for _, b := range po {
+ s.processBlock(b, live, t, rematIDs, nil)
+ }
+
+ if f.pass.debug > regDebug {
+ s.debugPrintLive("after single pass (acyclic)", f, s.live, s.desired)
+ }
+ s.computeDesired()
+}
+
+// computeLiveIrreducible handles irreducible CFGs by iterating over all blocks.
+// Uses 3-pass alternating traversal based on empirical convergence findings.
+func (s *regAllocState) computeLiveIrreducible(po []*Block, live, t *sparseMapPos) {
+ f := s.f
+ rematIDs := make([]ID, 0, 64)
+
+ // Compute reverse postorder for alternating passes
+ rpo := make([]*Block, len(po))
+ for i, b := range po {
+ rpo[len(po)-1-i] = b
+ }
+
+ // Three passes with alternating order suffice empirically:
+ // Pass 1: postorder (exits → entry)
+ // Pass 2: rev postorder (entry → exits)
+ // Pass 3: postorder (exits → entry)
+ orders := [3][]*Block{po, rpo, po}
+ for _, order := range orders {
+ for _, b := range order {
+ s.processBlock(b, live, t, rematIDs, nil)
+ }
+ }
+
+ if f.pass.debug > regDebug {
+ s.debugPrintLive("after 3-pass (irreducible)", f, s.live, s.desired)
+ }
+ s.computeDesired()
+}
+
+// computeLiveWithLoops handles reducible CFGs with loops using SCC decomposition.
+// Optimized for the common case of a single non-trivial SCC (24% of all functions).
+func (s *regAllocState) computeLiveWithLoops(po []*Block, live, t *sparseMapPos) {
+ f := s.f
+ rematIDs := make([]ID, 0, 64)
+
+ // Set up loop liveness tracking for post-processing
+ loopLiveIn := make(map[*loop][]liveInfo)
+ numCalls := f.Cache.allocInt32Slice(f.NumBlocks())
+ defer f.Cache.freeInt32Slice(numCalls)
+
+ // Compute SCCs - needed for loop cases
+ sccs := sccPartition(f)
+
+ // Process SCCs in reverse topological order
+ for j := len(sccs) - 1; j >= 0; j-- {
+ scc := sccs[j]
+
+ if len(scc) == 1 {
+ // SINGLETON SCC: Single pass suffices (no internal cycles)
+ b := scc[0]
+ s.processBlock(b, live, t, rematIDs, loopLiveIn)
+ continue
+ }
+
+ // NON-TRIVIAL SCC: Apply 3-pass algorithm with alternating order
+ // Empirical finding: ALL SCCs in our 290k-function dataset converge
+ // in exactly 3 passes with alternating traversal order.
+ exitward, entryward := sccAlternatingOrders(scc)
+
+ // Pass 1: postorder (exits → entry direction)
+ for _, b := range exitward {
+ s.processBlock(b, live, t, rematIDs, loopLiveIn)
+ }
+ // Pass 2: reverse direction (entry → exits)
+ for _, b := range entryward {
+ s.processBlock(b, live, t, rematIDs, loopLiveIn)
+ }
+ // Pass 3: postorder again
+ for _, b := range exitward {
+ s.processBlock(b, live, t, rematIDs, loopLiveIn)
+ }
+ }
+
+ if f.pass.debug > regDebug {
+ s.debugPrintLive("after SCC 3-pass", f, s.live, s.desired)
+ }
+
+ // Post-process: propagate loop liveness through loop bodies
+ s.propagateLoopLiveness(po, live, t, loopLiveIn, numCalls)
+}
+
+// processBlock performs the core liveness computation for a single block.
+// This is the inner loop to avoid duplication across strategies.
+func (s *regAllocState) processBlock(
+ b *Block,
+ live, t *sparseMapPos,
+ rematIDs []ID,
+ loopLiveIn map[*loop][]liveInfo,
+) {
+ // Start with known live values at the end of the block
+ live.clear()
+ for _, e := range s.live[b.ID] {
+ live.set(e.ID, e.dist, e.pos)
+ }
+
+ update := false
+
+ // Arguments to phi nodes in successors are live at this block's out
+ for _, e := range b.Succs {
+ succ := e.b
+ delta := branchDistance(b, succ)
+ for _, v := range succ.Values {
+ if v.Op != OpPhi {
+ break
+ }
+ arg := v.Args[e.i]
+ if s.values[arg.ID].needReg && (!live.contains(arg.ID) || delta < live.get(arg.ID)) {
+ live.set(arg.ID, delta, v.Pos)
+ update = true
+ }
+ }
+ }
+
+ if update {
+ s.live[b.ID] = updateLive(live, s.live[b.ID])
+ }
+
+ // Add len(b.Values) to adjust from end-of-block distance to beginning-of-block distance
+ c := live.contents()
+ for i := range c {
+ c[i].val += int32(len(b.Values))
+ }
+
+ // Mark control values as live
+ for _, ctrl := range b.ControlValues() {
+ if s.values[ctrl.ID].needReg {
+ live.set(ctrl.ID, int32(len(b.Values)), b.Pos)
+ }
+ }
+
+ // Walk instructions backward, updating liveness
+ rematIDs = rematIDs[:0]
+ for i := len(b.Values) - 1; i >= 0; i-- {
+ v := b.Values[i]
+ live.remove(v.ID)
+
+ if v.Op == OpPhi {
+ continue
+ }
+
+ if opcodeTable[v.Op].call {
+ c := live.contents()
+ for i := range c {
+ c[i].val += unlikelyDistance
+ vid := c[i].key
+ if s.values[vid].rematerializeable {
+ rematIDs = append(rematIDs, vid)
+ }
+ }
+ // Remove rematerializeable values - we don't spill them
+ for _, r := range rematIDs {
+ live.remove(r)
+ }
+ rematIDs = rematIDs[:0]
+ }
+
+ for _, a := range v.Args {
+ if s.values[a.ID].needReg {
+ live.set(a.ID, int32(i), v.Pos)
+ }
+ }
+ }
+
+ // Record loop header liveness for later propagation
+ if loopLiveIn != nil {
+ loop := s.loopnest.b2l[b.ID]
+ if loop != nil && loop.header.ID == b.ID {
+ loopLiveIn[loop] = updateLive(live, nil)
+ }
+ }
+
+ // Propagate liveness to predecessors
+ for _, e := range b.Preds {
+ p := e.b
+ delta := branchDistance(p, b)
+
+ // Start t off with the previously known live values at the end of p
+ t.clear()
+ for _, e := range s.live[p.ID] {
+ t.set(e.ID, e.dist, e.pos)
+ }
+
+ update := false
+ for _, e := range live.contents() {
+ d := e.val + delta
+ if !t.contains(e.key) || d < t.get(e.key) {
+ update = true
+ t.set(e.key, d, e.pos)
+ }
+ }
+
+ if update {
+ s.live[p.ID] = updateLive(t, s.live[p.ID])
+ }
+ }
+}
+
+// propagateLoopLiveness propagates liveness information through loop bodies.
+// This fills in loop-carried liveness after the main analysis.
+func (s *regAllocState) propagateLoopLiveness(
+ po []*Block,
+ live, t *sparseMapPos,
+ loopLiveIn map[*loop][]liveInfo,
+ numCalls []int32,
+) {
+ f := s.f
+
+ // Walk loopnest from outer to inner, adding live-in values from parent loops
loops := slices.Clone(s.loopnest.loops)
slices.SortFunc(loops, func(a, b *loop) int {
return cmp.Compare(a.depth, b.depth)
@@ -3027,6 +3115,7 @@
loopset := f.newSparseMapPos(f.NumValues())
defer f.retSparseMapPos(loopset)
+
for _, loop := range loops {
if loop.outer == nil {
continue
@@ -3047,14 +3136,11 @@
loopLiveIn[loop] = updateLive(loopset, livein)
}
}
- // unknownDistance is a sentinel value for when we know a variable
- // is live at any given block, but we do not yet know how far until it's next
- // use. The distance will be computed later.
+
+ // Sentinel for unknown distance (will be computed from successors)
const unknownDistance = -1
- // add live-in values of the loop headers to their children.
- // This includes the loop headers themselves, since they can have values
- // that die in the middle of the block and aren't live-out
+ // Add live-in values of loop headers to all blocks in their loop
for _, b := range po {
loop := s.loopnest.b2l[b.ID]
if loop == nil {
@@ -3076,13 +3162,12 @@
s.live[b.ID] = updateLive(loopset, s.live[b.ID])
}
}
+
if f.pass.debug > regDebug {
- s.debugPrintLive("after live loop prop", f, s.live, s.desired)
+ s.debugPrintLive("after loop propagation", f, s.live, s.desired)
}
- // Filling in liveness from loops leaves some blocks with no distance information
- // Run over them and fill in the information from their successors.
- // To stabilize faster, we quit when no block has missing values and we only
- // look at blocks that still have missing values in subsequent iterations
+
+ // Fill in unknown distances from successors
unfinishedBlocks := f.Cache.allocBlockSlice(len(po))
defer f.Cache.freeBlockSlice(unfinishedBlocks)
copy(unfinishedBlocks, po)
@@ -3137,14 +3222,7 @@
}
// computeDesired computes the desired register information at the end of each block.
-// It is essentially a liveness analysis on machine registers instead of SSA values
-// The desired register information is stored in s.desired.
func (s *regAllocState) computeDesired() {
-
- // TODO: Can we speed this up using the liveness information we have already
- // from computeLive?
- // TODO: Since we don't propagate information through phi nodes, can we do
- // this as a single dominator tree walk instead of the iterative solution?
var desired desiredState
f := s.f
po := f.postorder()
@@ -3156,15 +3234,10 @@
v := b.Values[i]
prefs := desired.remove(v.ID)
if v.Op == OpPhi {
- // TODO: if v is a phi, save desired register for phi inputs.
- // For now, we just drop it and don't propagate
- // desired registers back though phi nodes.
continue
}
regspec := s.regspec(v)
- // Cancel desired registers if they get clobbered.
desired.clobber(regspec.clobbers)
- // Update desired registers if there are any fixed register inputs.
for _, j := range regspec.inputs {
if countRegs(j.regs) != 1 {
continue
@@ -3172,13 +3245,7 @@
desired.clobber(j.regs)
desired.add(v.Args[j.idx].ID, pickReg(j.regs))
}
- // Set desired register of input 0 if this is a 2-operand instruction.
if opcodeTable[v.Op].resultInArg0 || v.Op == OpAMD64ADDQconst || v.Op == OpAMD64ADDLconst || v.Op == OpSelect0 {
- // ADDQconst is added here because we want to treat it as resultInArg0 for
- // the purposes of desired registers, even though it is not an absolute requirement.
- // This is because we'd rather implement it as ADDQ instead of LEAQ.
- // Same for ADDLconst
- // Select0 is added here to propagate the desired register to the tuple-generating instruction.
if opcodeTable[v.Op].commutative {
desired.addList(v.Args[1].ID, prefs)
}
@@ -3190,13 +3257,12 @@
changed = s.desired[p.ID].merge(&desired) || changed
}
}
- if !changed || (!s.loopnest.hasIrreducible && len(s.loopnest.loops) == 0) {
+ if !changed {
break
}
}
}
-// updateLive updates a given liveInfo slice with the contents of t
func updateLive(t *sparseMapPos, live []liveInfo) []liveInfo {
live = live[:0]
if cap(live) < t.size() {
@@ -3208,9 +3274,6 @@
return live
}
-// branchDistance calculates the distance between a block and a
-// successor in pseudo-instructions. This is used to indicate
-// likeliness
func branchDistance(b *Block, s *Block) int32 {
if len(b.Succs) == 2 {
if b.Succs[0].b == s && b.Likely == BranchLikely ||
@@ -3222,8 +3285,6 @@
return unlikelyDistance
}
}
- // Note: the branch distance must be at least 1 to distinguish the control
- // value use from the first user in a successor block.
return normalDistance
}
@@ -3236,10 +3297,11 @@
func (s *regAllocState) debugPrintLiveBlock(b *Block, live []liveInfo, desired *desiredState) {
fmt.Printf(" %s:", b)
- slices.SortFunc(live, func(a, b liveInfo) int {
+ sorted := slices.Clone(live)
+ slices.SortFunc(sorted, func(a, b liveInfo) int {
return cmp.Compare(a.ID, b.ID)
})
- for _, x := range live {
+ for _, x := range sorted {
fmt.Printf(" v%d(%d)", x.ID, x.dist)
for _, e := range desired.entries {
if e.ID != x.ID {
diff --git a/src/cmd/compile/internal/ssa/scc.go b/src/cmd/compile/internal/ssa/scc.go
new file mode 100644
index 0000000..1eede60
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/scc.go
@@ -0,0 +1,94 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package ssa
+
+import "iter"
+
+// This file implements strongly connected component (SCC) detection for
+// control-flow graphs using the Kosaraju-Sharir algorithm.
+//
+// Kosaraju-Sharir was chosen over Tarjan's single-pass algorithm because it is
+// straightforward to implement iteratively and requires no auxiliary data on
+// graph nodes. Additionally, the first DFS pass (postorder) is typically already
+// computed and cached, making this choice effectively free.
+//
+// sccPartition returns the strongly connected components of f's control-flow
+// graph, topologically sorted by the kernel DAG. Each SCC corresponds to a loop
+// (or trivial single-block component) in f.
+//
+// Properties:
+// - The first SCC contains only the entry block.
+// - Unreachable blocks are excluded from the result.
+// - The topological order of the kernel DAG may not be unique, but this does
+// not affect correctness for live range computation.
+// - Block order within each SCC is unspecified.
+//
+// The iterator pattern avoids allocating the result slice when callers
+// only need a single traversal.
+//
+// Example:
+//
+// Given: b1 → b2, b2 → [b3, b4], b3 → b2, b4 → b5
+// Result: [[b1], [b2, b3], [b4], [b5]]
+//
+// The second pass uses BFS with reversed edges for simplicity.
+func (f *Func) SCCs() iter.Seq[[]*Block] {
+ return func(yield func([]*Block) bool) {
+ // First DFS pass: compute postorder on original edges.
+ // The last element is the function entry block.
+ po := f.postorder()
+
+ // Track visited blocks and filter to reachable only.
+ seen := make([]bool, f.NumBlocks())
+ reachable := make([]bool, f.NumBlocks())
+ for _, b := range po {
+ reachable[b.ID] = true
+ }
+
+ // Second pass: traverse reversed edges in reverse postorder.
+ // Each connected component found is an SCC.
+ queue := make([]*Block, 0, len(po))
+
+ for i := len(po) - 1; i >= 0; i-- {
+ leader := po[i]
+ if seen[leader.ID] {
+ continue
+ }
+
+ // BFS to find all blocks in this SCC.
+ scc := make([]*Block, 0, 4)
+ queue = append(queue, leader)
+ seen[leader.ID] = true
+
+ for len(queue) > 0 {
+ b := queue[0]
+ queue = queue[1:]
+ scc = append(scc, b)
+
+ for _, e := range b.Preds {
+ pred := e.b
+ if reachable[pred.ID] && !seen[pred.ID] {
+ seen[pred.ID] = true
+ queue = append(queue, pred)
+ }
+ }
+ }
+
+ if !yield(scc) {
+ return
+ }
+ }
+ }
+}
+
+// sccPartition returns all SCCs as a slice for callers that need random access.
+// Prefer [Func.SCCs] when iterating once.
+func sccPartition(f *Func) [][]*Block {
+ var result [][]*Block
+ for scc := range f.SCCs() {
+ result = append(result, scc)
+ }
+ return result
+}
diff --git a/src/cmd/compile/internal/ssa/scc_test.go b/src/cmd/compile/internal/ssa/scc_test.go
new file mode 100644
index 0000000..b13b772
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/scc_test.go
@@ -0,0 +1,234 @@
+// Copyright 2022 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package ssa
+
+import (
+ "cmd/compile/internal/types"
+ "testing"
+)
+
+type sccFunc func(f *Func) [][]*Block
+
+// verifySccPartition verifies that the kernel DAG of an SCC are topologically sorted
+// and each SCC contains the proper set of nodes.
+func verifySccPartition(t *testing.T, fut fun, sccFn sccFunc, sccPartition [][]string) {
+ blockNames := map[*Block]string{}
+ for n, b := range fut.blocks {
+ blockNames[b] = n
+ }
+
+ calcScc := sccFn(fut.f)
+ expectedNscc := len(sccPartition)
+ actualNscc := len(calcScc)
+ if actualNscc != expectedNscc {
+ t.Errorf("expected %d SCC kernels, found %d", expectedNscc, actualNscc)
+ }
+
+ for n, scc := range calcScc {
+ expectedScc := sccPartition[n]
+ nc := len(scc)
+ if nc != len(expectedScc) {
+ t.Errorf("expected %v nodes in SCC, found %v", expectedScc, scc)
+ }
+
+ // verify that nodes in this SCC are as expected
+ nodeSet := make(map[string]bool)
+ for _, b := range scc {
+ nodeSet[blockNames[b]] = false
+ }
+
+ for _, expectedNode := range expectedScc {
+ if val, ok := nodeSet[expectedNode]; !ok {
+ nodes := make([]string, 0, len(nodeSet))
+ for k := range nodeSet {
+ nodes = append(nodes, k)
+ }
+ t.Errorf("expected node %s in %v", expectedNode, nodes)
+ } else if val {
+ t.Errorf("duplicate expected node %s is invalid", expectedNode)
+ }
+
+ nodeSet[expectedNode] = true
+ }
+
+ // test if any actual SCC nodes are not as expected
+ for k, v := range nodeSet {
+ if !v {
+ t.Errorf("actual block %s in SCC is unexpected", k)
+ }
+ }
+ }
+}
+
+func TestSccPartitionLinear(t *testing.T) {
+ c := testConfig(t)
+ fun := c.Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+ Goto("1")),
+ Bloc("1",
+ Goto("2")),
+ Bloc("2",
+ Goto("3")),
+ Bloc("3",
+ Goto("exit")),
+ Bloc("exit",
+ Exit("mem")))
+
+ expectedSccPartition := [][]string{
+ {"entry"},
+ {"1"},
+ {"2"},
+ {"3"},
+ {"exit"},
+ }
+
+ CheckFunc(fun.f)
+ verifySccPartition(t, fun, sccPartition, expectedSccPartition)
+}
+
+func TestSccPartitionOneLoop(t *testing.T) {
+ c := testConfig(t)
+ fun := c.Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+ Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
+ If("p", "a", "b")),
+ Bloc("a",
+ Goto("c")),
+ Bloc("b",
+ Goto("c")),
+ Bloc("c",
+ If("p", "b", "exit")),
+ Bloc("exit",
+ Exit("mem")))
+
+ expectedSccPartition := [][]string{
+ {"entry"},
+ {"a"},
+ {"b", "c"},
+ {"exit"},
+ }
+
+ CheckFunc(fun.f)
+ verifySccPartition(t, fun, sccPartition, expectedSccPartition)
+}
+
+func TestSccPartitionInfiniteLoop(t *testing.T) {
+ c := testConfig(t)
+ // note lack of an exit block
+ fun := c.Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+ Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
+ Goto("a")),
+ Bloc("a",
+ Goto("b")),
+ Bloc("b",
+ Goto("a")),
+ )
+
+ expectedSccPartition := [][]string{
+ {"entry"},
+ {"b", "a"},
+ }
+
+ CheckFunc(fun.f)
+ verifySccPartition(t, fun, sccPartition, expectedSccPartition)
+}
+
+func TestSccPartitionDeadCode(t *testing.T) {
+ c := testConfig(t)
+ fun := c.Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+ Valu("p", OpConstBool, types.Types[types.TBOOL], 0, nil),
+ If("p", "b3", "b5")),
+ Bloc("b2", Exit("mem")),
+ Bloc("b3", Goto("b2")),
+ Bloc("b4", Goto("b2")),
+ Bloc("b5", Goto("b2")))
+
+ // for this example, the topological order is not unique:
+ // order of b3 and b5 is interchangeable
+ expectedSccPartition := [][]string{
+ {"entry"},
+ {"b5"},
+ {"b3"},
+ {"b2"},
+ }
+
+ CheckFunc(fun.f)
+ verifySccPartition(t, fun, sccPartition, expectedSccPartition)
+}
+
+func TestSccPartitionTricky(t *testing.T) {
+ c := testConfig(t)
+ fun := c.Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+ Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
+ If("p", "6", "8")),
+ Bloc("1",
+ If("p", "exit", "5")),
+ Bloc("2",
+ If("p", "1", "3")),
+ Bloc("3",
+ If("p", "5", "2")),
+ Bloc("4",
+ If("p", "2", "3")),
+ Bloc("5",
+ Goto("4")),
+ Bloc("6",
+ If("p", "7", "4")),
+ Bloc("7",
+ If("p", "6", "8")),
+ Bloc("8",
+ If("p", "10", "9")),
+ Bloc("9",
+ Goto("11")),
+ Bloc("10",
+ If("p", "11", "4")),
+ Bloc("11",
+ Goto("8")),
+ Bloc("exit",
+ Exit("mem")))
+
+ expectedSccPartition := [][]string{
+ {"entry"},
+ {"6", "7"},
+ {"8", "9", "10", "11"},
+ {"1", "2", "3", "4", "5"},
+ {"exit"},
+ }
+
+ CheckFunc(fun.f)
+ verifySccPartition(t, fun, sccPartition, expectedSccPartition)
+}
+
+func TestSCCsEarlyExit(t *testing.T) {
+ c := testConfig(t)
+ fun := c.Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+ Goto("1")),
+ Bloc("1", Goto("2")),
+ Bloc("2", Goto("exit")),
+ Bloc("exit", Exit("mem")))
+
+ CheckFunc(fun.f)
+
+ count := 0
+ for scc := range fun.f.SCCs() {
+ count++
+ if len(scc) == 1 && scc[0] == fun.blocks["1"] {
+ break
+ }
+ }
+
+ if count != 2 { // entry, then "1"
+ t.Errorf("expected to stop after 2 SCCs, got %d", count)
+ }
+}
Change information
Files:
- M src/cmd/compile/internal/ssa/dom.go
- M src/cmd/compile/internal/ssa/regalloc.go
- A src/cmd/compile/internal/ssa/scc.go
- A src/cmd/compile/internal/ssa/scc_test.go
Change size: L
Delta: 4 files changed, 631 insertions(+), 210 deletions(-)
Related details
Attention set is empty
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Frank Kuehnel (Gerrit)
Dec 20, 2025, 10:32:19 AM (2 days ago) Dec 20
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Keith Randall and Martin Möhrmann
Frank Kuehnel uploaded new patchset![]( "Open in Gerrit")
Frank Kuehnel uploaded patch set #2 to this change.
Related details
Attention is currently required from:
- Keith Randall
- Martin Möhrmann
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
t hepudds (Gerrit)
Dec 20, 2025, 12:46:20 PM (2 days ago) Dec 20
to Frank Kuehnel, goph...@pubsubhelper.golang.org, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Frank Kuehnel, Keith Randall and Martin Möhrmann
t hepudds added 1 comment![]( "Open in Gerrit")
Patchset-level comments
File-level comment, Patchset 2 (Latest):
t hepudds . unresolved
It's nice that there is an auxiliary PDF with many details, but please write a more complete commit message. See https://go.dev/doc/contribute#commit_messages
As stated there, the commit message should elaborate and provide context for the change and explain what it does.
Having a more complete commit message also makes it easier for a reviewer to pick this up to review the code.
Also, the commit message for a change like this really should have at least some quantitative performance old vs. new results (e.g., comparing wall clock execution times or similar), which I did not immediately see in the PDF.
As noted in the Contribution Guide, the `benchstat` tool is conventionally used to format benchmark data for commit messages. In some cases, `compilebench` can be used.
For your particular case, I'm not sure the magnitude of the changes will be picked up by `compilebench`. Maybe you've already done something like this, but some chance you might need to instrument the code to report useful timing information, in which case you could likely feed that old vs. new timing information into `benchstat`.
Some links that might be helpful:
* https://pkg.go.dev/golang.org/x/perf/cmd/benchstat
* https://pkg.go.dev/golang.org/x/tools/cmd/compilebench
* https://github.com/golang/go/blob/master/src/cmd/compile/README.md#8-tips
Finally, this is based on just a quick look at the PDF. Sorry if I've missed something, and sorry if this is all things you already know.
Related details
Attention is currently required from:
- Frank Kuehnel
- Keith Randall
- Martin Möhrmann
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
t hepudds (Gerrit)
Dec 20, 2025, 12:48:42 PM (2 days ago) Dec 20
to Frank Kuehnel, goph...@pubsubhelper.golang.org, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Frank Kuehnel, Keith Randall and Martin Möhrmann
t hepudds voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
Attention is currently required from:
- Frank Kuehnel
- Keith Randall
- Martin Möhrmann
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Frank Kuehnel (Gerrit)
Dec 21, 2025, 11:20:26 PM (2 hours ago) Dec 21
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Frank Kuehnel, Keith Randall and Martin Möhrmann
Frank Kuehnel uploaded new patchset![]( "Open in Gerrit")
Frank Kuehnel uploaded patch set #3 to this change.
Following approvals got outdated and were removed:
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
Attention is currently required from:
- Frank Kuehnel
- Keith Randall
- Martin Möhrmann
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Reply all
Reply to author
Forward
0 new messages