cmd/compile: fix phi-function updates for preemptible loops

Previous code failed to account for particular control flow
involving nested loops when updating phi function inputs.
Fix involves:
1) remove incorrect shortcut
2) generate a "better" order for children in dominator tree
3) note inner-loop updates and check before applying
   outer-loop updates.

Fixes #20675.

Change-Id: I2fe21470604b5c259e777ad8b15de95f7706894d
Reviewed-on: https://go-review.googlesource.com/45791
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>

1 files changed, 18 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/ssa/sparsetree.go b/src/cmd/compile/internal/ssa/sparsetree.go
index 8e5b9f3e5b..f7af85446b 100644
--- a/src/cmd/compile/internal/ssa/sparsetree.go
+++ b/src/cmd/compile/internal/ssa/sparsetree.go
@@ -70,6 +70,24 @@ func newSparseTree(f *Func, parentOf []*Block) SparseTree {
 	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 {
+		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
+}
+
 // treestructure provides a string description of the dominator
 // tree and flow structure of block b and all blocks that it
 // dominates.