go/ssa: fix regression in φ-elimination
https://go-review.googlesource.com/37157 introduced a bug that caused
some live φ-nodes to be removed from the CFG. The cause was that
reachability traversal considered edges only among "new" φ-nodes
(those introduced during SSA renaming) but not existing φ-nodes from
&& and || expressions. The fix is to mark existing phis, and thus
other phis reachable from them, as live. We also clear the Phi.block
field when eliminating a φ-node.
Also, during reachability, we treat DebugRef instructions as roots
like any other non-Phi instruction. This eliminates a related known
bug whereby the operand of a DebugRef may be a dead φ.
This change also adds a sanity check that all operands of an SSA value
that are themselves instructions must belong to a block. The sanity
check would fail 7 times on the standard library without the fix.
Fixes golang/go#19622
Change-Id: If3a897a6a593a17bc3f0f8228d1edf483be7a3d0
Reviewed-on: https://go-review.googlesource.com/45832
Run-TryBot: Dominik Honnef <dominik@honnef.co>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Dominik Honnef <dominik@honnef.co>
diff --git a/go/ssa/lift.go b/go/ssa/lift.go
index 00c8a72..048e9b0 100644
--- a/go/ssa/lift.go
+++ b/go/ssa/lift.go
@@ -214,7 +214,7 @@
rename(fn.Blocks[0], renaming, newPhis)
// Eliminate dead φ-nodes.
- removeDeadPhis(newPhis)
+ removeDeadPhis(fn.Blocks, newPhis)
// Prepend remaining live φ-nodes to each block.
for _, b := range fn.Blocks {
@@ -269,8 +269,14 @@
// 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.
+func removeDeadPhis(blocks []*BasicBlock, newPhis newPhiMap) {
+ // First pass: find the set of "live" φ-nodes: those reachable
+ // from some non-Phi instruction.
+ //
+ // We compute reachability in reverse, starting from each φ,
+ // rather than forwards, starting from each live non-Phi
+ // instruction, because this way visits much less of the
+ // Value graph.
livePhis := make(map[*Phi]bool)
for _, npList := range newPhis {
for _, np := range npList {
@@ -281,6 +287,14 @@
}
}
+ // Existing φ-nodes due to && and || operators
+ // are all considered live (see Go issue 19622).
+ for _, b := range blocks {
+ for _, phi := range b.phis() {
+ markLivePhi(livePhis, phi.(*Phi))
+ }
+ }
+
// Second pass: eliminate unused phis from newPhis.
for block, npList := range newPhis {
j := 0
@@ -295,9 +309,7 @@
*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.
+ np.phi.block = nil
}
}
newPhis[block] = npList[:j]
@@ -318,14 +330,11 @@
}
// phiHasDirectReferrer reports whether phi is directly referred to by
-// a non-Phi, non-DebugRef instruction. Such instructions are the
+// a non-Phi 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:
+ if _, ok := instr.(*Phi); !ok {
return true
}
}
diff --git a/go/ssa/print.go b/go/ssa/print.go
index 0c1b270..3333ba4 100644
--- a/go/ssa/print.go
+++ b/go/ssa/print.go
@@ -89,8 +89,12 @@
b.WriteString(", ")
}
// Be robust against malformed CFG.
+ if v.block == nil {
+ b.WriteString("??")
+ continue
+ }
block := -1
- if v.block != nil && i < len(v.block.Preds) {
+ if i < len(v.block.Preds) {
block = v.block.Preds[i].Index
}
fmt.Fprintf(&b, "%d: ", block)
diff --git a/go/ssa/sanity.go b/go/ssa/sanity.go
index 638a2c4..9e49e3b 100644
--- a/go/ssa/sanity.go
+++ b/go/ssa/sanity.go
@@ -351,7 +351,10 @@
// Check that Operands that are also Instructions belong to same function.
// TODO(adonovan): also check their block dominates block b.
if val, ok := val.(Instruction); ok {
- if val.Parent() != s.fn {
+ if val.Block() == nil {
+ val.String()
+ s.errorf("operand %d of %s is an instruction (%s) that belongs to no block", i, instr, val)
+ } else if val.Parent() != s.fn {
s.errorf("operand %d of %s is an instruction (%s) from function %s", i, instr, val, val.Parent())
}
}
