From a6c48f2ca9efdf6c45d434767a30b9d25824497d Mon Sep 17 00:00:00 2001 From: Daniel Morsing Date: Thu, 5 Feb 2026 12:44:32 +0000 Subject: [PATCH] cmd/compile: make the cached sdom always return the reverse PO The sdom tree has a feature where the ordering of child nodes could be customized, but in actuality, we only ever used one ordering: reverse postorder. This order has a nice property that walking the tree will always visit the source block of any non-retreating edge before the destination block. Make this ordering the default and document it. This allows passes that use it to use the cached sdom tree instead of calculating it from scratch each time. Change-Id: I907b8ff7cc722e94bf364c183f26ead66a6a6964 Reviewed-on: https://go-review.googlesource.com/c/go/+/742340 Reviewed-by: Keith Randall LUCI-TryBot-Result: Go LUCI Auto-Submit: Keith Randall Reviewed-by: Keith Randall Reviewed-by: Junyang Shao --- .../compile/internal/ssa/loopreschedchecks.go | 5 +--- src/cmd/compile/internal/ssa/sparsetree.go | 24 ++++--------------- 2 files changed, 6 insertions(+), 23 deletions(-) diff --git a/src/cmd/compile/internal/ssa/loopreschedchecks.go b/src/cmd/compile/internal/ssa/loopreschedchecks.go index 125c468217..f9b91676da 100644 --- a/src/cmd/compile/internal/ssa/loopreschedchecks.go +++ b/src/cmd/compile/internal/ssa/loopreschedchecks.go @@ -75,10 +75,7 @@ func insertLoopReschedChecks(f *Func) { idom := f.Idom() po := f.postorder() - // The ordering in the dominator tree matters; it's important that - // the walk of the dominator tree also be a preorder (i.e., a node is - // visited only after all its non-backedge predecessors have been visited). - sdom := newSparseOrderedTree(f, idom, po) + sdom := f.Sdom() if f.pass.debug > 1 { fmt.Printf("before %s = %s\n", f.Name, sdom.treestructure(f.Entry)) diff --git a/src/cmd/compile/internal/ssa/sparsetree.go b/src/cmd/compile/internal/ssa/sparsetree.go index 6f2bd04037..1e0f460134 100644 --- a/src/cmd/compile/internal/ssa/sparsetree.go +++ b/src/cmd/compile/internal/ssa/sparsetree.go @@ -56,27 +56,13 @@ const ( type SparseTree []SparseTreeNode // newSparseTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID). +// The children of a given node are in reverse postorder. +// This has the nice property that for a given tree walk, the source block of all +// non-retreating edges are visited before their destination block. func newSparseTree(f *Func, parentOf []*Block) SparseTree { + po := f.postorder() t := make(SparseTree, f.NumBlocks()) - for _, b := range f.Blocks { - n := &t[b.ID] - if p := parentOf[b.ID]; p != nil { - n.parent = p - n.sibling = t[p.ID].child - t[p.ID].child = b - } - } - t.numberBlock(f.Entry, 1) - return t -} - -// newSparseOrderedTree creates a SparseTree from a block-to-parent map (array indexed by Block.ID) -// children will appear in the reverse of their order in reverseOrder -// in particular, if reverseOrder is a dfs-reversePostOrder, then the root-to-children -// walk of the tree will yield a pre-order. -func newSparseOrderedTree(f *Func, parentOf, reverseOrder []*Block) SparseTree { - t := make(SparseTree, f.NumBlocks()) - for _, b := range reverseOrder { + for _, b := range po { n := &t[b.ID] if p := parentOf[b.ID]; p != nil { n.parent = p -- 2.52.0