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>
diff --git a/go/ssa/builder_test.go b/go/ssa/builder_test.go
index 8b186f3..c45f930 100644
--- a/go/ssa/builder_test.go
+++ b/go/ssa/builder_test.go
@@ -11,6 +11,7 @@
"go/parser"
"go/token"
"go/types"
+ "os"
"reflect"
"sort"
"strings"
@@ -417,3 +418,83 @@
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 300f498..091992f 100644
--- a/go/ssa/lift.go
+++ b/go/ssa/lift.go
@@ -36,9 +36,6 @@
// 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 @@
"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 @@
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 @@
// 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 @@
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 @@
// 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 @@
}
// 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 @@
dst[j] = instr
j++
}
- for i, np := range nps {
- dst[i] = np.phi
- }
b.Instrs = dst
}
@@ -284,15 +267,67 @@
fn.Locals = fn.Locals[:j]
}
-func phiIsLive(phi *Phi) bool {
+// 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)
+ }
+ }
+ }
+}
+
+// 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() {
- if instr == phi {
- continue // self-refs don't count
+ switch instr.(type) {
+ case *Phi, *DebugRef:
+ // ignore
+ default:
+ return true
}
- if _, ok := instr.(*DebugRef); ok {
- continue // debug refs don't count
- }
- return true
}
return false
}
@@ -337,7 +372,9 @@
// 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 @@
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
