cmd/compile: change phi location to be optimistic at backedges

This is:

(1) a simple trick that cuts the number of phi-nodes
(temporarily) inserted into the ssa representation by a factor
of 10, and can cut the user time to compile tricky inputs like
gogo/protobuf tests from 13 user minutes to 9.5, and memory
allocation from 3.4GB to 2.4GB.

(2) a fix to sparse lookup, that does not rely on
an assumption proven false by at least one pathological
input "etldlen".

These two changes fix unrelated compiler performance bugs,
both necessary to obtain good performance compiling etldlen.
Without them it takes 20 minutes or longer, with them it
completes in 2 minutes, without a gigantic memory footprint.

Updates #16407

Change-Id: Iaa8aaa8c706858b3d49de1c4865a7fd79e6f4ff7
Reviewed-on: https://go-review.googlesource.com/23136
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

2 files changed, 66 insertions, 43 deletions

diff --git a/src/cmd/compile/internal/gc/sparselocatephifunctions.go b/src/cmd/compile/internal/gc/sparselocatephifunctions.go
index e15f22123f..43cc50bd92 100644
--- a/src/cmd/compile/internal/gc/sparselocatephifunctions.go
+++ b/src/cmd/compile/internal/gc/sparselocatephifunctions.go
@@ -153,10 +153,13 @@ func (s *state) locatePotentialPhiFunctions(fn *Node) *sparseDefState {
 					p := e.Block()
 					dm.Use(t, p)                                // always count phi pred as "use"; no-op except for loop edges, which matter.
 					x := t.stm.Find(p, ssa.AdjustAfter, helper) // Look for defs reaching or within predecessors.
+					if x == nil {                               // nil def from a predecessor means a backedge that will be visited soon.
+						continue
+					}
 					if defseen == nil {
 						defseen = x
 					}
-					if defseen != x || x == nil { // TODO: too conservative at loops, does better if x == nil -> continue
+					if defseen != x {
 						// Need to insert a phi function here because predecessors's definitions differ.
 						change = true
 						// Phi insertion is at AdjustBefore, visible with find in same block at AdjustWithin or AdjustAfter.
diff --git a/src/cmd/compile/internal/ssa/sparsetreemap.go b/src/cmd/compile/internal/ssa/sparsetreemap.go
index 61276985b1..3e6f296796 100644
--- a/src/cmd/compile/internal/ssa/sparsetreemap.go
+++ b/src/cmd/compile/internal/ssa/sparsetreemap.go
@@ -14,8 +14,8 @@ import "fmt"
 // the nearest tree ancestor of a given node such that the
 // ancestor is also in the set.
 //
-// Given a set of blocks {B1, B2, B3} within the dominator tree, established by
-// stm.Insert()ing B1, B2, B3, etc, a query at block B
+// Given a set of blocks {B1, B2, B3} within the dominator tree, established
+// by stm.Insert()ing B1, B2, B3, etc, a query at block B
 // (performed with stm.Find(stm, B, adjust, helper))
 // will return the member of the set that is the nearest strict
 // ancestor of B within the dominator tree, or nil if none exists.
@@ -49,9 +49,9 @@ type SparseTreeMap RBTint32
 // packages, such as gc.
 type SparseTreeHelper struct {
 	Sdom   []SparseTreeNode // indexed by block.ID
-	Po     []*Block         // exported data
-	Dom    []*Block         // exported data
-	Ponums []int32          // exported data
+	Po     []*Block         // exported data; the blocks, in a post-order
+	Dom    []*Block         // exported data; the dominator of this block.
+	Ponums []int32          // exported data; Po[Ponums[b.ID]] == b; the index of b in Po
 }
 
 // NewSparseTreeHelper returns a SparseTreeHelper for use
@@ -79,11 +79,19 @@ func makeSparseTreeHelper(sdom SparseTree, dom, po []*Block, ponums []int32) *Sp
 // A sparseTreeMapEntry contains the data stored in a binary search
 // data structure indexed by (dominator tree walk) entry and exit numbers.
 // Each entry is added twice, once keyed by entry-1/entry/entry+1 and
-// once keyed by exit+1/exit/exit-1. (there are three choices of paired indices, not 9, and they properly nest)
+// once keyed by exit+1/exit/exit-1.
+//
+// Within a sparse tree, the two entries added bracket all their descendant
+// entries within the tree; the first insertion is keyed by entry number,
+// which comes before all the entry and exit numbers of descendants, and
+// the second insertion is keyed by exit number, which comes after all the
+// entry and exit numbers of the descendants.
 type sparseTreeMapEntry struct {
-	index *SparseTreeNode
-	block *Block // TODO: store this in a separate index.
-	data  interface{}
+	index        *SparseTreeNode // references the entry and exit numbers for a block in the sparse tree
+	block        *Block          // TODO: store this in a separate index.
+	data         interface{}
+	sparseParent *sparseTreeMapEntry // references the nearest ancestor of this block in the sparse tree.
+	adjust       int32               // at what adjustment was this node entered into the sparse tree? The same block may be entered more than once, but at different adjustments.
 }
 
 // Insert creates a definition within b with data x.
@@ -98,12 +106,25 @@ func (m *SparseTreeMap) Insert(b *Block, adjust int32, x interface{}, helper *Sp
 		// assert unreachable
 		return
 	}
-	entry := &sparseTreeMapEntry{index: blockIndex, data: x}
+	// sp will be the sparse parent in this sparse tree (nearest ancestor in the larger tree that is also in this sparse tree)
+	sp := m.findEntry(b, adjust, helper)
+	entry := &sparseTreeMapEntry{index: blockIndex, block: b, data: x, sparseParent: sp, adjust: adjust}
+
 	right := blockIndex.exit - adjust
 	_ = rbtree.Insert(right, entry)
 
 	left := blockIndex.entry + adjust
 	_ = rbtree.Insert(left, entry)
+
+	// This newly inserted block may now be the sparse parent of some existing nodes (the new sparse children of this block)
+	// Iterate over nodes bracketed by this new node to correct their parent, but not over the proper sparse descendants of those nodes.
+	_, d := rbtree.Lub(left) // Lub (not EQ) of left is either right or a sparse child
+	for tme := d.(*sparseTreeMapEntry); tme != entry; tme = d.(*sparseTreeMapEntry) {
+		tme.sparseParent = entry
+		// all descendants of tme are unchanged;
+		// next sparse sibling (or right-bracketing sparse parent == entry) is first node after tme.index.exit - tme.adjust
+		_, d = rbtree.Lub(tme.index.exit - tme.adjust)
+	}
 }
 
 // Find returns the definition visible from block b, or nil if none can be found.
@@ -118,45 +139,41 @@ func (m *SparseTreeMap) Insert(b *Block, adjust int32, x interface{}, helper *Sp
 //
 // Another way to think of this is that Find searches for inputs, Insert defines outputs.
 func (m *SparseTreeMap) Find(b *Block, adjust int32, helper *SparseTreeHelper) interface{} {
+	v := m.findEntry(b, adjust, helper)
+	if v == nil {
+		return nil
+	}
+	return v.data
+}
+
+func (m *SparseTreeMap) findEntry(b *Block, adjust int32, helper *SparseTreeHelper) *sparseTreeMapEntry {
 	rbtree := (*RBTint32)(m)
 	if rbtree == nil {
 		return nil
 	}
 	blockIndex := &helper.Sdom[b.ID]
+
+	// The Glb (not EQ) of this probe is either the entry-indexed end of a sparse parent
+	// or the exit-indexed end of a sparse sibling
 	_, v := rbtree.Glb(blockIndex.entry + adjust)
-	for v != nil {
-		otherEntry := v.(*sparseTreeMapEntry)
-		otherIndex := otherEntry.index
-		// Two cases -- either otherIndex brackets blockIndex,
-		// or it doesn't.
-		//
-		// Note that if otherIndex and blockIndex are
-		// the same block, then the glb test only passed
-		// because the definition is "before",
-		// i.e., k == blockIndex.entry-1
-		// allowing equality is okay on the blocks check.
-		if otherIndex.exit >= blockIndex.exit {
-			// bracketed.
-			return otherEntry.data
+
+	if v == nil {
+		return nil
+	}
+
+	otherEntry := v.(*sparseTreeMapEntry)
+	if otherEntry.index.exit >= blockIndex.exit { // otherEntry exit after blockIndex exit; therefore, brackets
+		return otherEntry
+	}
+	// otherEntry is a sparse Sibling, and shares the same sparse parent (nearest ancestor within larger tree)
+	sp := otherEntry.sparseParent
+	if sp != nil {
+		if sp.index.exit < blockIndex.exit { // no ancestor found
+			return nil
 		}
-		// In the not-bracketed case, we could memoize the results of
-		// walking up the tree, but for now we won't.
-		// Memoize plan is to take the gap (inclusive)
-		// from otherIndex.exit+1 to blockIndex.entry-1
-		// and insert it into this or a second tree.
-		// Said tree would then need adjusting whenever
-		// an insertion occurred.
-
-		// Expectation is that per-variable tree is sparse,
-		// therefore probe siblings instead of climbing up.
-		// Note that each sibling encountered in this walk
-		// to find a defining ancestor shares that ancestor
-		// because the walk skips over the interior -- each
-		// Glb will be an exit, and the iteration is to the
-		// Glb of the entry.
-		_, v = rbtree.Glb(otherIndex.entry - 1)
+		return sp
 	}
-	return nil // nothing found
+	return nil
 }
 
 func (m *SparseTreeMap) String() string {
@@ -165,5 +182,8 @@ func (m *SparseTreeMap) String() string {
 }
 
 func (e *sparseTreeMapEntry) String() string {
-	return fmt.Sprintf("index=%v, data=%v", e.index, e.data)
+	if e == nil {
+		return "nil"
+	}
+	return fmt.Sprintf("(index=%v, block=%v, data=%v)->%v", e.index, e.block, e.data, e.sparseParent)
 }