cmd/compile: speed up dom checking in cse

Process a slice of equivalent values by setting replaced values to nil
instead of removing them from the slice to eliminate copying.  Also take
advantage of the entry number sort to break early once we reach a value
in a block that is not dominated.

For the code in issue #15112:

Before:
real    0m52.603s
user    0m56.957s
sys     0m1.213s

After:
real    0m22.048s
user    0m26.445s
sys     0m0.939s

Updates #15112

Change-Id: I06d9e1e1f1ad85d7fa196c5d51f0dc163907376d
Reviewed-on: https://go-review.googlesource.com/22068
Reviewed-by: David Chase <drchase@google.com>

1 files changed, 17 insertions, 9 deletions

diff --git a/src/cmd/compile/internal/ssa/cse.go b/src/cmd/compile/internal/ssa/cse.go
index 76db9d5467..e3f1a1d07d 100644
--- a/src/cmd/compile/internal/ssa/cse.go
+++ b/src/cmd/compile/internal/ssa/cse.go
@@ -138,21 +138,29 @@ func cse(f *Func) {
 	rewrite := make([]*Value, f.NumValues())
 	for _, e := range partition {
 		sort.Sort(sortbyentry{e, f.sdom})
-		for len(e) > 1 {
+		for i := 0; i < len(e)-1; i++ {
 			// e is sorted by entry value so maximal dominant element should be
 			// found first in the slice
-			v := e[0]
-			e = e[1:]
+			v := e[i]
+			if v == nil {
+				continue
+			}
+
+			e[i] = nil
 			// Replace all elements of e which v dominates
-			for i := 0; i < len(e); {
-				w := e[i]
+			for j := i + 1; j < len(e); j++ {
+				w := e[j]
+				if w == nil {
+					continue
+				}
 				if f.sdom.isAncestorEq(v.Block, w.Block) {
 					rewrite[w.ID] = v
-					// retain the sort order
-					copy(e[i:], e[i+1:])
-					e = e[:len(e)-1]
+					e[j] = nil
 				} else {
-					i++
+					// since the blocks are assorted in ascending order by entry number
+					// once we know that we don't dominate a block we can't dominate any
+					// 'later' block
+					break
 				}
 			}
 		}