cmd/compile: share dominator tree among many passes

These passes do not modify the dominator tree too much.

% benchstat old.txt new.txt
name       old time/op     new time/op     delta
Template       335ms ± 3%      325ms ± 8%    ~             (p=0.074 n=8+9)
GoTypes        1.05s ± 1%      1.05s ± 3%    ~            (p=0.095 n=9+10)
Compiler       5.37s ± 4%      5.29s ± 1%  -1.42%         (p=0.022 n=9+10)
MakeBash       34.9s ± 3%      34.4s ± 2%    ~            (p=0.095 n=9+10)

name       old alloc/op    new alloc/op    delta
Template      55.4MB ± 0%     54.9MB ± 0%  -0.81%        (p=0.000 n=10+10)
GoTypes        179MB ± 0%      178MB ± 0%  -0.89%        (p=0.000 n=10+10)
Compiler       807MB ± 0%      798MB ± 0%  -1.10%        (p=0.000 n=10+10)

name       old allocs/op   new allocs/op   delta
Template        498k ± 0%       496k ± 0%  -0.29%          (p=0.000 n=9+9)
GoTypes        1.42M ± 0%      1.41M ± 0%  -0.24%        (p=0.000 n=10+10)
Compiler       5.61M ± 0%      5.60M ± 0%  -0.12%        (p=0.000 n=10+10)

Change-Id: I4cd20cfba3f132ebf371e16046ab14d7e42799ec
Reviewed-on: https://go-review.googlesource.com/21806
Run-TryBot: Alexandru Moșoi <alexandru@mosoi.ro>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>

1 files changed, 8 insertions, 10 deletions

diff --git a/src/cmd/compile/internal/ssa/loopbce.go b/src/cmd/compile/internal/ssa/loopbce.go
index c937ead1b2..9bd2d3f0de 100644
--- a/src/cmd/compile/internal/ssa/loopbce.go
+++ b/src/cmd/compile/internal/ssa/loopbce.go
@@ -31,7 +31,7 @@ type indVar struct {
 //
 //
 // TODO: handle 32 bit operations
-func findIndVar(f *Func, sdom sparseTree) []indVar {
+func findIndVar(f *Func) []indVar {
 	var iv []indVar
 
 nextb:
@@ -110,7 +110,7 @@ nextb:
 
 		// Second condition: b.Succs[entry] dominates nxt so that
 		// nxt is computed when inc < max, meaning nxt <= max.
-		if !sdom.isAncestorEq(b.Succs[entry], nxt.Block) {
+		if !f.sdom.isAncestorEq(b.Succs[entry], nxt.Block) {
 			// inc+ind can only be reached through the branch that enters the loop.
 			continue
 		}
@@ -160,20 +160,18 @@ nextb:
 
 // loopbce performs loop based bounds check elimination.
 func loopbce(f *Func) {
-	idom := dominators(f)
-	sdom := newSparseTree(f, idom)
-	ivList := findIndVar(f, sdom)
+	ivList := findIndVar(f)
 
 	m := make(map[*Value]indVar)
 	for _, iv := range ivList {
 		m[iv.ind] = iv
 	}
 
-	removeBoundsChecks(f, sdom, m)
+	removeBoundsChecks(f, m)
 }
 
 // removesBoundsChecks remove IsInBounds and IsSliceInBounds based on the induction variables.
-func removeBoundsChecks(f *Func, sdom sparseTree, m map[*Value]indVar) {
+func removeBoundsChecks(f *Func, m map[*Value]indVar) {
 	for _, b := range f.Blocks {
 		if b.Kind != BlockIf {
 			continue
@@ -202,7 +200,7 @@ func removeBoundsChecks(f *Func, sdom sparseTree, m map[*Value]indVar) {
 				goto skip1
 			}
 
-			if iv, has := m[ind]; has && sdom.isAncestorEq(iv.entry, b) && isNonNegative(iv.min) {
+			if iv, has := m[ind]; has && f.sdom.isAncestorEq(iv.entry, b) && isNonNegative(iv.min) {
 				if v.Args[1] == iv.max {
 					if f.pass.debug > 0 {
 						f.Config.Warnl(b.Line, "Found redundant %s", v.Op)
@@ -229,7 +227,7 @@ func removeBoundsChecks(f *Func, sdom sparseTree, m map[*Value]indVar) {
 				goto skip2
 			}
 
-			if iv, has := m[ind]; has && sdom.isAncestorEq(iv.entry, b) && isNonNegative(iv.min) {
+			if iv, has := m[ind]; has && f.sdom.isAncestorEq(iv.entry, b) && isNonNegative(iv.min) {
 				if v.Args[1].Op == OpSliceCap && iv.max.Op == OpSliceLen && v.Args[1].Args[0] == iv.max.Args[0] {
 					if f.pass.debug > 0 {
 						f.Config.Warnl(b.Line, "Found redundant %s (len promoted to cap)", v.Op)
@@ -250,7 +248,7 @@ func removeBoundsChecks(f *Func, sdom sparseTree, m map[*Value]indVar) {
 			}
 
 			// ind + add >= 0 <-> min + add >= 0 <-> min >= -add
-			if iv, has := m[ind]; has && sdom.isAncestorEq(iv.entry, b) && isGreaterOrEqualThan(iv.min, -add) {
+			if iv, has := m[ind]; has && f.sdom.isAncestorEq(iv.entry, b) && isGreaterOrEqualThan(iv.min, -add) {
 				if !v.Args[1].isGenericIntConst() || !iv.max.isGenericIntConst() {
 					goto skip3
 				}