go/ssa: eliminate dead φ-nodes in cycles

The previous "dead φ" check was simple and naive but left cycles of
dead φ-nodes.  This confused some downstream static analysis tools.
This change makes the φ-nodes liveness check transitive.

+ Test.

Also, number phi nodes so they're not all called t0 during debugging.

Reduces memory consumption by  1%.
Increases execution time   by <1%.

Change-Id: I2908662c1478d455fdf4a179f4a12d6184a456c0
Reviewed-on: https://go-review.googlesource.com/37157
Reviewed-by: Robert Griesemer <gri@golang.org>

2 files changed, 163 insertions, 41 deletions

diff --git a/go/ssa/builder_test.go b/go/ssa/builder_test.go
index 8b186f397..c45f930b3 100644
--- a/go/ssa/builder_test.go
+++ b/go/ssa/builder_test.go
@@ -11,6 +11,7 @@ import (
 	"go/parser"
 	"go/token"
 	"go/types"
+	"os"
 	"reflect"
 	"sort"
 	"strings"
@@ -417,3 +418,83 @@ var (
 		t.Errorf("want func: %q: %q", fn, descr)
 	}
 }
+
+// TestPhiElimination ensures that dead phis, including those that
+// participate in a cycle, are properly eliminated.
+func TestPhiElimination(t *testing.T) {
+	const input = `
+package p
+
+func f() error
+
+func g(slice []int) {
+	for {
+		for range slice {
+			// e should not be lifted to a dead φ-node.
+			e := f()
+			h(e)
+		}
+	}
+}
+
+func h(error)
+`
+	// The SSA code for this function should look something like this:
+	// 0:
+	//         jump 1
+	// 1:
+	//         t0 = len(slice)
+	//         jump 2
+	// 2:
+	//         t1 = phi [1: -1:int, 3: t2]
+	//         t2 = t1 + 1:int
+	//         t3 = t2 < t0
+	//         if t3 goto 3 else 1
+	// 3:
+	//         t4 = f()
+	//         t5 = h(t4)
+	//         jump 2
+	//
+	// But earlier versions of the SSA construction algorithm would
+	// additionally generate this cycle of dead phis:
+	//
+	// 1:
+	//         t7 = phi [0: nil:error, 2: t8] #e
+	//         ...
+	// 2:
+	//         t8 = phi [1: t7, 3: t4] #e
+	//         ...
+
+	// Parse
+	var conf loader.Config
+	f, err := conf.ParseFile("<input>", input)
+	if err != nil {
+		t.Fatalf("parse: %v", err)
+	}
+	conf.CreateFromFiles("p", f)
+
+	// Load
+	lprog, err := conf.Load()
+	if err != nil {
+		t.Fatalf("Load: %v", err)
+	}
+
+	// Create and build SSA
+	prog := ssautil.CreateProgram(lprog, 0)
+	p := prog.Package(lprog.Package("p").Pkg)
+	p.Build()
+	g := p.Func("g")
+
+	phis := 0
+	for _, b := range g.Blocks {
+		for _, instr := range b.Instrs {
+			if _, ok := instr.(*ssa.Phi); ok {
+				phis++
+			}
+		}
+	}
+	if phis != 1 {
+		g.WriteTo(os.Stderr)
+		t.Errorf("expected a single Phi (for the range index), got %d", phis)
+	}
+}
diff --git a/go/ssa/lift.go b/go/ssa/lift.go
index 300f49832..091992f09 100644
--- a/go/ssa/lift.go
+++ b/go/ssa/lift.go
@@ -36,9 +36,6 @@ package ssa
 // Consider exploiting liveness information to avoid creating dead
 // φ-nodes which we then immediately remove.
 //
-// Integrate lifting with scalar replacement of aggregates (SRA) since
-// the two are synergistic.
-//
 // Also see many other "TODO: opt" suggestions in the code.
 
 import (
@@ -49,8 +46,8 @@ import (
 	"os"
 )
 
-// If true, perform sanity checking and show diagnostic information at
-// each step of lifting.  Very verbose.
+// If true, show diagnostic information at each step of lifting.
+// Very verbose.
 const debugLifting = false
 
 // domFrontier maps each block to the set of blocks in its dominance
@@ -122,7 +119,7 @@ func removeInstr(refs []Instruction, instr Instruction) []Instruction {
 	return refs[:i]
 }
 
-// lift attempts to replace local and new Allocs accessed only with
+// lift replaces local and new Allocs accessed only with
 // load/store by SSA registers, inserting φ-nodes where necessary.
 // The result is a program in classical pruned SSA form.
 //
@@ -178,6 +175,11 @@ func lift(fn *Function) {
 	// instructions.
 	usesDefer := false
 
+	// A counter used to generate ~unique ids for Phi nodes, as an
+	// aid to debugging.  We use large numbers to make them highly
+	// visible.  All nodes are renumbered later.
+	fresh := 1000
+
 	// Determine which allocs we can lift and number them densely.
 	// The renaming phase uses this numbering for compact maps.
 	numAllocs := 0
@@ -188,7 +190,7 @@ func lift(fn *Function) {
 			switch instr := instr.(type) {
 			case *Alloc:
 				index := -1
-				if liftAlloc(df, instr, newPhis) {
+				if liftAlloc(df, instr, newPhis, &fresh) {
 					index = numAllocs
 					numAllocs++
 				}
@@ -211,29 +213,13 @@ func lift(fn *Function) {
 	// Renaming.
 	rename(fn.Blocks[0], renaming, newPhis)
 
-	// Eliminate dead new phis, then prepend the live ones to each block.
-	for _, b := range fn.Blocks {
+	// Eliminate dead φ-nodes.
+	removeDeadPhis(newPhis)
 
-		// Compress the newPhis slice to eliminate unused phis.
-		// TODO(adonovan): opt: compute liveness to avoid
-		// placing phis in blocks for which the alloc cell is
-		// not live.
+	// Prepend remaining live φ-nodes to each block.
+	for _, b := range fn.Blocks {
 		nps := newPhis[b]
-		j := 0
-		for _, np := range nps {
-			if !phiIsLive(np.phi) {
-				// discard it, first removing it from referrers
-				for _, newval := range np.phi.Edges {
-					if refs := newval.Referrers(); refs != nil {
-						*refs = removeInstr(*refs, np.phi)
-					}
-				}
-				continue
-			}
-			nps[j] = np
-			j++
-		}
-		nps = nps[:j]
+		j := len(nps)
 
 		rundefersToKill := b.rundefers
 		if usesDefer {
@@ -245,8 +231,8 @@ func lift(fn *Function) {
 		}
 
 		// Compact nps + non-nil Instrs into a new slice.
-		// TODO(adonovan): opt: compact in situ if there is
-		// sufficient space or slack in the slice.
+		// TODO(adonovan): opt: compact in situ (rightwards)
+		// if Instrs has sufficient space or slack.
 		dst := make([]Instruction, len(b.Instrs)+j-b.gaps-rundefersToKill)
 		for i, np := range nps {
 			dst[i] = np.phi
@@ -263,9 +249,6 @@ func lift(fn *Function) {
 			dst[j] = instr
 			j++
 		}
-		for i, np := range nps {
-			dst[i] = np.phi
-		}
 		b.Instrs = dst
 	}
 
@@ -284,15 +267,67 @@ func lift(fn *Function) {
 	fn.Locals = fn.Locals[:j]
 }
 
-func phiIsLive(phi *Phi) bool {
-	for _, instr := range *phi.Referrers() {
-		if instr == phi {
-			continue // self-refs don't count
+// removeDeadPhis removes φ-nodes not transitively needed by a
+// non-Phi, non-DebugRef instruction.
+func removeDeadPhis(newPhis newPhiMap) {
+	// First pass: compute reachability from non-Phi/DebugRef instructions.
+	livePhis := make(map[*Phi]bool)
+	for _, npList := range newPhis {
+		for _, np := range npList {
+			phi := np.phi
+			if !livePhis[phi] && phiHasDirectReferrer(phi) {
+				markLivePhi(livePhis, phi)
+			}
+		}
+	}
+
+	// Second pass: eliminate unused phis from newPhis.
+	for block, npList := range newPhis {
+		j := 0
+		for _, np := range npList {
+			if livePhis[np.phi] {
+				npList[j] = np
+				j++
+			} else {
+				// discard it, first removing it from referrers
+				for _, val := range np.phi.Edges {
+					if refs := val.Referrers(); refs != nil {
+						*refs = removeInstr(*refs, np.phi)
+					}
+				}
+				// This may leave DebugRef instructions referring to
+				// Phis that aren't in the control flow graph.
+				// TODO(adonovan): we should delete them.
+			}
+		}
+		newPhis[block] = npList[:j]
+	}
+}
+
+// markLivePhi marks phi, and all φ-nodes transitively reachable via
+// its Operands, live.
+func markLivePhi(livePhis map[*Phi]bool, phi *Phi) {
+	livePhis[phi] = true
+	for _, rand := range phi.Operands(nil) {
+		if q, ok := (*rand).(*Phi); ok {
+			if !livePhis[q] {
+				markLivePhi(livePhis, q)
+			}
 		}
-		if _, ok := instr.(*DebugRef); ok {
-			continue // debug refs don't count
+	}
+}
+
+// phiHasDirectReferrer reports whether phi is directly referred to by
+// a non-Phi, non-DebugRef instruction.  Such instructions are the
+// roots of the liveness traversal.
+func phiHasDirectReferrer(phi *Phi) bool {
+	for _, instr := range *phi.Referrers() {
+		switch instr.(type) {
+		case *Phi, *DebugRef:
+			// ignore
+		default:
+			return true
 		}
-		return true
 	}
 	return false
 }
@@ -337,7 +372,9 @@ type newPhiMap map[*BasicBlock][]newPhi
 // and if so, it populates newPhis with all the φ-nodes it may require
 // and returns true.
 //
-func liftAlloc(df domFrontier, alloc *Alloc, newPhis newPhiMap) bool {
+// fresh is a source of fresh ids for phi nodes.
+//
+func liftAlloc(df domFrontier, alloc *Alloc, newPhis newPhiMap, fresh *int) bool {
 	// Don't lift aggregates into registers, because we don't have
 	// a way to express their zero-constants.
 	switch deref(alloc.Type()).Underlying().(type) {
@@ -420,6 +457,10 @@ func liftAlloc(df domFrontier, alloc *Alloc, newPhis newPhiMap) bool {
 					Edges:   make([]Value, len(v.Preds)),
 					Comment: alloc.Comment,
 				}
+				// This is merely a debugging aid:
+				phi.setNum(*fresh)
+				*fresh++
+
 				phi.pos = alloc.Pos()
 				phi.setType(deref(alloc.Type()))
 				phi.block = v