[go] cmd/compile/internal/ssa: add dominance frontier algorithm
3 views
Skip to first unread message
Daniel Morsing (Gerrit)
May 5, 2026, 8:11:31 AMMay 5
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Daniel Morsing has uploaded the change for review![]( "Open in Gerrit")
Commit message
cmd/compile/internal/ssa: add dominance frontier algorithm
This was originally part of CL 751841, but I found myself using it in
other places.
Change-Id: I04311ccaf46600cde0510828f142584f6a6a6964
Change diff
diff --git a/src/cmd/compile/internal/ssa/dfplus.go b/src/cmd/compile/internal/ssa/dfplus.go
new file mode 100644
index 0000000..9555f0e
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/dfplus.go
@@ -0,0 +1,180 @@
+// Copyright 2026 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 (
+ "fmt"
+ "slices"
+)
+
+const debugDFPlus = false
+
+// dfPlus calculates the iterated dominance frontier of a function.
+func dfPlus(f *Func) [][]*Block {
+ // Our SSA construction code doesn't expose the dominance frontier to the backend passes
+ // and it only constructs DF+ sets for individual variables. Even if it did expose this information,
+ // the CFG may have changed and invalidated the result. We have to calculate it here ourselves.
+ //
+ // We use the TDMSC-I algorithm from Das and Ramakrishna here: https://dl.acm.org/doi/epdf/10.1145/1065887.1065890
+ // It is a linear time algorithm for calculating the DF+ set of every single
+ // block. This means that we can construct arbitrary DF+ sets over variables as we insert them
+ // into the function.
+ //
+ // The original TDMSC-I algorithm uses an explicit set to keep track of which edges have already been
+ // visited during a given iteration. Here, we instead order our processing so
+ // that we can determine whether we've visited a node by checking our current position
+ // in the processing
+ //
+ // TODO: We can probably use the DF+ for something elsewhere. Consider caching it
+ // like we do the dominator information.
+
+ dfplus := make([][]*Block, f.NumBlocks())
+ sdom := f.Sdom()
+ // TODO(dmo): Does a numbering in sparsetree allow
+ // for looking up the bID to BFS order already?
+ // We have to keep a queue anyway, so it's not a big loss
+ bidToBFS := f.Cache.allocIntSlice(f.NumBlocks())
+ defer f.Cache.freeIntSlice(bidToBFS)
+ bfsOrder := f.Cache.allocBlockSlice(f.NumBlocks())
+ defer f.Cache.freeBlockSlice(bfsOrder)
+
+ bfsOrder = bfsOrder[:0]
+ bfsOrder = append(bfsOrder, f.Entry)
+ parent := f.Entry
+ bidToBFS[parent.ID] = 0
+
+ i := 0
+ for i < len(bfsOrder) {
+ parent := bfsOrder[i]
+ // TODO(dmo): the order we visit the dom tree impacts whether we need
+ // to do consistency checking. Right now, we use the post-order
+ // that sparseTree gives us, but is there an alternate order that minimizes
+ // the number of consistency checks or iterations until stabilization?
+ for child := sdom.Child(parent); child != nil; child = sdom.Sibling(child) {
+ bidToBFS[child.ID] = len(bfsOrder)
+ bfsOrder = append(bfsOrder, child)
+ }
+ i++
+ }
+ if debugDFPlus {
+ fmt.Println(f.Name)
+ fmt.Println(bfsOrder)
+ fmt.Println(sdom.treestructure(f.Entry))
+ }
+ dfpSet := f.Cache.allocSparseSet(f.NumBlocks())
+ defer f.Cache.freeSparseSet(dfpSet)
+ pass := 1
+ for {
+ if debugDFPlus {
+ fmt.Printf("%s pass %d\n", f.Name, pass)
+ }
+ pass++
+ consistent := true
+ for bfsIdx, b := range bfsOrder {
+ for outerPredIdx, e := range b.Preds {
+ pred := e.b
+ // only consider incoming J edges
+ if sdom.isAncestor(pred, b) {
+ continue
+ }
+ if debugDFPlus {
+ fmt.Printf("[edge %v(%v)->%v(%v)]\n", pred, bidToBFS[pred.ID], b, bfsIdx)
+ }
+ // Walk up the dominator tree of the incoming
+ // edge's source, adding DF+(b) ∪ b to their
+ // DF+ set.
+ var lastParent *Block
+ parent := pred
+ for sdom.NumAncestors(parent) >= sdom.NumAncestors(b) {
+ if debugDFPlus {
+ fmt.Printf("\tadding DF+(%v) (l:%v) %v+[%v] to DF+(%v) (l:%v) %v\n", b, sdom.NumAncestors(b), dfplus[b.ID], b, parent, sdom.NumAncestors(parent), dfplus[parent.ID])
+ }
+ dfplus[parent.ID] = updateDFPlus(dfpSet, dfplus[parent.ID], b, dfplus[b.ID])
+ lastParent = parent
+ parent = sdom.Parent(parent)
+ }
+ // consistency checking is fairly cheap but not entirely free.
+ // Skip it if we've already found an inconsistency
+ if consistent {
+ if debugDFPlus {
+ fmt.Printf("lastParent %v\n", lastParent)
+ }
+ check:
+ for predIdx, e := range lastParent.Preds {
+ pred := e.b
+ // again, only consider incoming J edges.
+ if sdom.IsAncestorEq(pred, lastParent) {
+ continue
+ }
+ if debugDFPlus {
+ fmt.Printf("\t[%v(%v)->%v(%v)] ", pred, bidToBFS[pred.ID], lastParent, bidToBFS[lastParent.ID])
+ }
+ if bidToBFS[lastParent.ID] > bfsIdx ||
+ (b.ID == lastParent.ID && outerPredIdx < predIdx) {
+ if debugDFPlus {
+ fmt.Printf("not visited\n")
+ }
+ continue
+ }
+ if debugDFPlus {
+ fmt.Printf("checking df+(pred) = %v, df+(lastParent) = %v\n", dfplus[pred.ID], dfplus[lastParent.ID])
+ }
+ dfpSet.clear()
+ for _, d := range dfplus[pred.ID] {
+ dfpSet.add(d.ID)
+ }
+ for _, d := range dfplus[lastParent.ID] {
+ if !dfpSet.contains(d.ID) {
+ if debugDFPlus {
+ fmt.Printf("found inconsistent\n")
+ }
+ consistent = false
+ // No need to check the other predecessors
+ break check
+ }
+ }
+ }
+ }
+ }
+ }
+ if consistent {
+ break
+ }
+ }
+ return dfplus
+}
+
+func updateDFPlus(dfpSet *sparseSet, old []*Block, b *Block, add []*Block) []*Block {
+ // allocating in a loop is a significant part of the cost
+ // of running the algorithm. Figure out how big the array needs to be
+ // before we allocate a right sized slice.
+ dfpSet.clear()
+ for _, d := range old {
+ dfpSet.add(d.ID)
+ }
+ nAdd := 0
+ if !dfpSet.contains(b.ID) {
+ nAdd += 1
+ }
+ for _, d := range add {
+ if !dfpSet.contains(d.ID) {
+ nAdd += 1
+ }
+ }
+ if nAdd == 0 {
+ return old
+ }
+ new := slices.Grow(old, nAdd)
+ if !dfpSet.contains(b.ID) {
+ new = append(new, b)
+ dfpSet.add(b.ID)
+ }
+ for _, d := range add {
+ if !dfpSet.contains(d.ID) {
+ new = append(new, d)
+ }
+ }
+ return new
+}
diff --git a/src/cmd/compile/internal/ssa/sparsetree.go b/src/cmd/compile/internal/ssa/sparsetree.go
index 1e0f460..4cabe20 100644
--- a/src/cmd/compile/internal/ssa/sparsetree.go
+++ b/src/cmd/compile/internal/ssa/sparsetree.go
@@ -23,6 +23,12 @@
// This simplifies life if we wish to query information about x
// when x is both an input to and output of a block.
entry, exit int32
+
+ // Every block has a level in the tree corresponding to the number of ancestors
+ // it has. This is used to quickly calculate the iterated dominance frontier
+ // of a set of blocks, using the dominator tree and block structure to form
+ // an ad-hoc DJ-graph.
+ level int32
}
func (s *SparseTreeNode) String() string {
@@ -70,7 +76,7 @@
t[p.ID].child = b
}
}
- t.numberBlock(f.Entry, 1)
+ t.numberBlock(f.Entry, 1, 1)
return t
}
@@ -81,7 +87,7 @@
return t.treestructure1(b, 0)
}
func (t SparseTree) treestructure1(b *Block, i int) string {
- s := "\n" + strings.Repeat("\t", i) + b.String() + "->["
+ s := "\n" + strings.Repeat("\t", i) + b.String() + fmt.Sprintf("(l:%v)", t[b.ID].level) + "->["
for i, e := range b.Succs {
if i > 0 {
s += ","
@@ -130,14 +136,15 @@
// root left left right right root
// 1 2e 3 | 4 5e 6 | 7 8x 9 | 10 11e 12 | 13 14x 15 | 16 17x 18
-func (t SparseTree) numberBlock(b *Block, n int32) int32 {
+func (t SparseTree) numberBlock(b *Block, n int32, level int32) int32 {
// reserve n for entry-1, assign n+1 to entry
n++
+ t[b.ID].level = level
t[b.ID].entry = n
// reserve n+1 for entry+1, n+2 is next free number
n += 2
for c := t[b.ID].child; c != nil; c = t[c.ID].sibling {
- n = t.numberBlock(c, n) // preserves n = next free number
+ n = t.numberBlock(c, n, level+1) // preserves n = next free number
}
// reserve n for exit-1, assign n+1 to exit
n++
@@ -180,6 +187,12 @@
return xx.entry <= yy.entry && yy.exit <= xx.exit
}
+// NumAncestors return which level a given block is in
+// the sparse tree.
+func (t SparseTree) NumAncestors(x *Block) int32 {
+ return t[x.ID].level
+}
+
// isAncestor reports whether x is a strict ancestor of y.
func (t SparseTree) isAncestor(x, y *Block) bool {
if x == y {
Change information
Files:
- A src/cmd/compile/internal/ssa/dfplus.go
- M src/cmd/compile/internal/ssa/sparsetree.go
Change size: M
Delta: 2 files changed, 197 insertions(+), 4 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. |
Keith Randall (Gerrit)
May 8, 2026, 8:50:24 PMMay 8
to Daniel Morsing, goph...@pubsubhelper.golang.org, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Daniel Morsing and Martin Möhrmann
Keith Randall added 1 comment![]( "Open in Gerrit")
Patchset-level comments
File-level comment, Patchset 1 (Latest):
Keith Randall . resolved
I'm still working on this one, sorry for the delay. I downloaded the Das and Ramakrishna paper and read it a few weeks ago. Still trying to get my head space back into dominance frontiers so I can figure this out.
Will try to get this reviewed and in for 1.27.
Related details
Attention is currently required from:
- Daniel Morsing
- 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. |
Daniel Morsing (Gerrit)
May 9, 2026, 4:30:22 AMMay 9
to goph...@pubsubhelper.golang.org, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Keith Randall and Martin Möhrmann
Daniel Morsing added 1 comment![]( "Open in Gerrit")
Patchset-level comments
Keith Randall . resolved
I'm still working on this one, sorry for the delay. I downloaded the Das and Ramakrishna paper and read it a few weeks ago. Still trying to get my head space back into dominance frontiers so I can figure this out.
Will try to get this reviewed and in for 1.27.
Daniel Morsing
There's a more understandable, but very pithy writeup up the algorithm in SSA-based Compiler Design, Section 4.3 that I've been working off. I like to cite primary sources just because they tend to be more readily available, but I can send you a printout if you'd like. I would imagine that book being available in the corp library.
A thing to note about this algorithm: It is linear time but in practice, I've found it slightly slower (I remember 10% ish, but would have to recheck) than the one Junyang wrote in CL 713300, which is O(n^2). Eventually, I imagine we land both and switch between them based on some heuristic, but it might just be that Go code doesn't generate CFGs that really hit the edge cases and we can use Junyang's algorithm outright.
As for landing this in 1.27, It'd be nice, but the current uses are CL 751841 and an unpublished prototype for the `prove` pass. Those are definitely aimed at 1.28 at the earliest, so don't sweat it too much.
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. |
Daniel Morsing (Gerrit)
Jul 27, 2026, 4:42:09 AM (12 days ago) Jul 27
to goph...@pubsubhelper.golang.org, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Keith Randall and Martin Möhrmann
Daniel Morsing voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
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. |
Daniel Morsing (Gerrit)
2:04 PM (9 hours ago) 2:04 PM
to goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Keith Randall and Martin Möhrmann
Daniel Morsing added 1 comment![]( "Open in Gerrit")
Patchset-level comments
File-level comment, Patchset 3 (Latest):
Daniel Morsing . resolved
Alright, have hit a point where I'm having to use this for #80146, so even if we don't go for CL 751841, might be worth looking at.
So far, I've tested this essentially by using it in CL 751841, and verifying that it was correct via the whole-tree tests, but I don't think that'll quite cut it. What's a good way of testing this? a couple of decently picked examples?
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. |
Daniel Morsing (Gerrit)
2:04 PM (9 hours ago) 2:04 PM
to goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, Keith Randall, Martin Möhrmann, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Keith Randall and Martin Möhrmann
Daniel Morsing voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Reply all
Reply to author
Forward
0 new messages