cmd/compile: sort partitions by dom to speed up cse

We do two O(n) scans of all values in an eqclass when computing
substitutions for CSE.

In unfortunate cases, like those found in #15112, we can have a large
eqclass composed of values found in blocks none of whom dominate the
other.  This leads to O(n^2) behavior. The elements are removed one at a
time, with O(n) scans each time.

This CL removes the linear scan by sorting the eqclass so that dominant
values will be sorted first.  As long as we also ensure we don't disturb
the sort order, then we no longer need to scan for the maximally
dominant value.

For the code in issue #15112:

Before:
real    1m26.094s
user    1m30.776s
sys     0m1.125s

Aefter:
real    0m52.099s
user    0m56.829s
sys     0m1.092s

Updates #15112

Change-Id: Ic4f8680ed172e716232436d31963209c146ef850
Reviewed-on: https://go-review.googlesource.com/21981
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
Run-TryBot: Todd Neal <todd@tneal.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>

1 files changed, 12 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/ssa/sparsetree.go b/src/cmd/compile/internal/ssa/sparsetree.go
index cae91e7ddb..45c7897496 100644
--- a/src/cmd/compile/internal/ssa/sparsetree.go
+++ b/src/cmd/compile/internal/ssa/sparsetree.go
@@ -116,6 +116,9 @@ func (t sparseTree) Child(x *Block) *Block {
 
 // isAncestorEq reports whether x is an ancestor of or equal to y.
 func (t sparseTree) isAncestorEq(x, y *Block) bool {
+	if x == y {
+		return true
+	}
 	xx := &t[x.ID]
 	yy := &t[y.ID]
 	return xx.entry <= yy.entry && yy.exit <= xx.exit
@@ -123,7 +126,16 @@ func (t sparseTree) isAncestorEq(x, y *Block) bool {
 
 // isAncestor reports whether x is a strict ancestor of y.
 func (t sparseTree) isAncestor(x, y *Block) bool {
+	if x == y {
+		return false
+	}
 	xx := &t[x.ID]
 	yy := &t[y.ID]
 	return xx.entry < yy.entry && yy.exit < xx.exit
 }
+
+// maxdomorder returns a value to allow a maximal dominator first sort.  maxdomorder(x) < maxdomorder(y) is true
+// if x may dominate y, and false if x cannot dominate y.
+func (t sparseTree) maxdomorder(x *Block) int32 {
+	return t[x.ID].entry
+}