cmd/compile: move phi args which are constants closer to the phi

entry:
   x = MOVQconst [7]
   ...
b1:
   goto b2
b2:
   v = Phi(x, y, z)

Transform that program to:

entry:
   ...
b1:
   x = MOVQconst [7]
   goto b2
b2:
   v = Phi(x, y, z)

This CL moves constant-generating instructions used by a phi to the
appropriate immediate predecessor of the phi's block.

We used to put all constants in the entry block.  Unfortunately, in
large functions we have lots of constants at the start of the
function, all of which are used by lots of phis throughout the
function.  This leads to the constants being live through most of the
function (especially if there is an outer loop).  That's an O(n^2)
problem.

Note that most of the non-phi uses of constants have already been
folded into instructions (ADDQconst, MOVQstoreconst, etc.).

This CL may be generally useful for other instances of compiler
slowness, I'll have to check.  It may cause some programs to run
slower, but probably not by much, as rematerializeable values like
these constants are allocated late (not at their originally scheduled
location) anyway.

This CL is definitely a minimal change that can be considered for 1.7.
We probably want to do a better job in the tighten pass generally, not
just for phi args.  Leaving that for 1.8.

Update #16407

Change-Id: If112a8883b4ef172b2f37dea13e44bda9346c342
Reviewed-on: https://go-review.googlesource.com/25046
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>

2 files changed, 24 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go
index b3c7544ad1..d8b0b0a5c1 100644
--- a/src/cmd/compile/internal/ssa/compile.go
+++ b/src/cmd/compile/internal/ssa/compile.go
@@ -270,6 +270,7 @@ var passes = [...]pass{
 	{name: "checkLower", fn: checkLower, required: true},
 	{name: "late phielim", fn: phielim},
 	{name: "late copyelim", fn: copyelim},
+	{name: "phi tighten", fn: phiTighten},
 	{name: "late deadcode", fn: deadcode},
 	{name: "critical", fn: critical, required: true}, // remove critical edges
 	{name: "likelyadjust", fn: likelyadjust},
diff --git a/src/cmd/compile/internal/ssa/tighten.go b/src/cmd/compile/internal/ssa/tighten.go
index ecb43c101d..2f7c30929d 100644
--- a/src/cmd/compile/internal/ssa/tighten.go
+++ b/src/cmd/compile/internal/ssa/tighten.go
@@ -86,3 +86,26 @@ func tighten(f *Func) {
 		}
 	}
 }
+
+// phiTighten moves constants closer to phi users.
+// This pass avoids having lots of constants live for lots of the program.
+// See issue 16407.
+func phiTighten(f *Func) {
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			if v.Op != OpPhi {
+				continue
+			}
+			for i, a := range v.Args {
+				if !a.rematerializeable() {
+					continue // not a constant we can move around
+				}
+				if a.Block == b.Preds[i].b {
+					continue // already in the right place
+				}
+				// Make a copy of a, put in predecessor block.
+				v.SetArg(i, a.copyInto(b.Preds[i].b))
+			}
+		}
+	}
+}