From accf9b5951f14a7a62cfe9ec5c59d6dc880c1bba Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Sat, 11 Jul 2015 15:43:35 -0700 Subject: [PATCH] [dev.ssa] cmd/compile/internal/ssa: comment why replacing phi with copy is ok Change-Id: I3e2e8862f2fde4349923016b97e8330b0d494e0e Reviewed-on: https://go-review.googlesource.com/12092 Reviewed-by: Josh Bleecher Snyder --- src/cmd/compile/internal/ssa/deadcode.go | 33 +++++++++++++++++++++++- 1 file changed, 32 insertions(+), 1 deletion(-) diff --git a/src/cmd/compile/internal/ssa/deadcode.go b/src/cmd/compile/internal/ssa/deadcode.go index 1b1ae27e58..04e5b71ceb 100644 --- a/src/cmd/compile/internal/ssa/deadcode.go +++ b/src/cmd/compile/internal/ssa/deadcode.go @@ -132,9 +132,40 @@ func (f *Func) removePredecessor(b, c *Block) { v.Args = v.Args[:n] if n == 1 { v.Op = OpCopy + // Note: this is trickier than it looks. Replacing + // a Phi with a Copy can in general cause problems because + // Phi and Copy don't have exactly the same semantics. + // Phi arguments always come from a predecessor block, + // whereas copies don't. This matters in loops like: + // 1: x = (Phi y) + // y = (Add x 1) + // goto 1 + // If we replace Phi->Copy, we get + // 1: x = (Copy y) + // y = (Add x 1) + // goto 1 + // (Phi y) refers to the *previous* value of y, whereas + // (Copy y) refers to the *current* value of y. + // The modified code has a cycle and the scheduler + // will barf on it. + // + // Fortunately, this situation can only happen for dead + // code loops. So although the value graph is transiently + // bad, we'll throw away the bad part by the end of + // the next deadcode phase. + // Proof: If we have a potential bad cycle, we have a + // situation like this: + // x = (Phi z) + // y = (op1 x ...) + // z = (op2 y ...) + // Where opX are not Phi ops. But such a situation + // implies a cycle in the dominator graph. In the + // example, x.Block dominates y.Block, y.Block dominates + // z.Block, and z.Block dominates x.Block (treating + // "dominates" as reflexive). Cycles in the dominator + // graph can only happen in an unreachable cycle. } } - if n == 0 { // c is now dead--recycle its values for _, v := range c.Values { -- 2.48.1