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 <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Junyang Shao <shaojunyang@google.com>

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