1 files changed, 513 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/shortcircuit.go b/src/cmd/compile/internal/ssa/shortcircuit.go
new file mode 100644
index 0000000..c0b9eac
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/shortcircuit.go
@@ -0,0 +1,513 @@
+// Copyright 2016 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package ssa
+
+// Shortcircuit finds situations where branch directions
+// are always correlated and rewrites the CFG to take
+// advantage of that fact.
+// This optimization is useful for compiling && and || expressions.
+func shortcircuit(f *Func) {
+	// Step 1: Replace a phi arg with a constant if that arg
+	// is the control value of a preceding If block.
+	// b1:
+	//    If a goto b2 else b3
+	// b2: <- b1 ...
+	//    x = phi(a, ...)
+	//
+	// We can replace the "a" in the phi with the constant true.
+	var ct, cf *Value
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			if v.Op != OpPhi {
+				continue
+			}
+			if !v.Type.IsBoolean() {
+				continue
+			}
+			for i, a := range v.Args {
+				e := b.Preds[i]
+				p := e.b
+				if p.Kind != BlockIf {
+					continue
+				}
+				if p.Controls[0] != a {
+					continue
+				}
+				if e.i == 0 {
+					if ct == nil {
+						ct = f.ConstBool(f.Config.Types.Bool, true)
+					}
+					v.SetArg(i, ct)
+				} else {
+					if cf == nil {
+						cf = f.ConstBool(f.Config.Types.Bool, false)
+					}
+					v.SetArg(i, cf)
+				}
+			}
+		}
+	}
+
+	// Step 2: Redirect control flow around known branches.
+	// p:
+	//   ... goto b ...
+	// b: <- p ...
+	//   v = phi(true, ...)
+	//   if v goto t else u
+	// We can redirect p to go directly to t instead of b.
+	// (If v is not live after b).
+	fuse(f, fuseTypePlain|fuseTypeShortCircuit)
+}
+
+// shortcircuitBlock checks for a CFG in which an If block
+// has as its control value a Phi that has a ConstBool arg.
+// In some such cases, we can rewrite the CFG into a flatter form.
+//
+// (1) Look for a CFG of the form
+//
+//   p   other pred(s)
+//    \ /
+//     b
+//    / \
+//   t   other succ
+//
+// in which b is an If block containing a single phi value with a single use (b's Control),
+// which has a ConstBool arg.
+// p is the predecessor corresponding to the argument slot in which the ConstBool is found.
+// t is the successor corresponding to the value of the ConstBool arg.
+//
+// Rewrite this into
+//
+//   p   other pred(s)
+//   |  /
+//   | b
+//   |/ \
+//   t   u
+//
+// and remove the appropriate phi arg(s).
+//
+// (2) Look for a CFG of the form
+//
+//   p   q
+//    \ /
+//     b
+//    / \
+//   t   u
+//
+// in which b is as described in (1).
+// However, b may also contain other phi values.
+// The CFG will be modified as described in (1).
+// However, in order to handle those other phi values,
+// for each other phi value w, we must be able to eliminate w from b.
+// We can do that though a combination of moving w to a different block
+// and rewriting uses of w to use a different value instead.
+// See shortcircuitPhiPlan for details.
+func shortcircuitBlock(b *Block) bool {
+	if b.Kind != BlockIf {
+		return false
+	}
+	// Look for control values of the form Copy(Not(Copy(Phi(const, ...)))).
+	// Those must be the only values in the b, and they each must be used only by b.
+	// Track the negations so that we can swap successors as needed later.
+	ctl := b.Controls[0]
+	nval := 1 // the control value
+	var swap int64
+	for ctl.Uses == 1 && ctl.Block == b && (ctl.Op == OpCopy || ctl.Op == OpNot) {
+		if ctl.Op == OpNot {
+			swap = 1 ^ swap
+		}
+		ctl = ctl.Args[0]
+		nval++ // wrapper around control value
+	}
+	if ctl.Op != OpPhi || ctl.Block != b || ctl.Uses != 1 {
+		return false
+	}
+	nOtherPhi := 0
+	for _, w := range b.Values {
+		if w.Op == OpPhi && w != ctl {
+			nOtherPhi++
+		}
+	}
+	if nOtherPhi > 0 && len(b.Preds) != 2 {
+		// We rely on b having exactly two preds in shortcircuitPhiPlan
+		// to reason about the values of phis.
+		return false
+	}
+	if len(b.Values) != nval+nOtherPhi {
+		return false
+	}
+	if nOtherPhi > 0 {
+		// Check for any phi which is the argument of another phi.
+		// These cases are tricky, as substitutions done by replaceUses
+		// are no longer trivial to do in any ordering. See issue 45175.
+		m := make(map[*Value]bool, 1+nOtherPhi)
+		for _, v := range b.Values {
+			if v.Op == OpPhi {
+				m[v] = true
+			}
+		}
+		for v := range m {
+			for _, a := range v.Args {
+				if a != v && m[a] {
+					return false
+				}
+			}
+		}
+	}
+
+	// Locate index of first const phi arg.
+	cidx := -1
+	for i, a := range ctl.Args {
+		if a.Op == OpConstBool {
+			cidx = i
+			break
+		}
+	}
+	if cidx == -1 {
+		return false
+	}
+
+	// p is the predecessor corresponding to cidx.
+	pe := b.Preds[cidx]
+	p := pe.b
+	pi := pe.i
+
+	// t is the "taken" branch: the successor we always go to when coming in from p.
+	ti := 1 ^ ctl.Args[cidx].AuxInt ^ swap
+	te := b.Succs[ti]
+	t := te.b
+	if p == b || t == b {
+		// This is an infinite loop; we can't remove it. See issue 33903.
+		return false
+	}
+
+	var fixPhi func(*Value, int)
+	if nOtherPhi > 0 {
+		fixPhi = shortcircuitPhiPlan(b, ctl, cidx, ti)
+		if fixPhi == nil {
+			return false
+		}
+	}
+
+	// We're committed. Update CFG and Phis.
+	// If you modify this section, update shortcircuitPhiPlan corresponding.
+
+	// Remove b's incoming edge from p.
+	b.removePred(cidx)
+	b.removePhiArg(ctl, cidx)
+
+	// Redirect p's outgoing edge to t.
+	p.Succs[pi] = Edge{t, len(t.Preds)}
+
+	// Fix up t to have one more predecessor.
+	t.Preds = append(t.Preds, Edge{p, pi})
+	for _, v := range t.Values {
+		if v.Op != OpPhi {
+			continue
+		}
+		v.AddArg(v.Args[te.i])
+	}
+
+	if nOtherPhi != 0 {
+		// Adjust all other phis as necessary.
+		// Use a plain for loop instead of range because fixPhi may move phis,
+		// thus modifying b.Values.
+		for i := 0; i < len(b.Values); i++ {
+			phi := b.Values[i]
+			if phi.Uses == 0 || phi == ctl || phi.Op != OpPhi {
+				continue
+			}
+			fixPhi(phi, i)
+			if phi.Block == b {
+				continue
+			}
+			// phi got moved to a different block with v.moveTo.
+			// Adjust phi values in this new block that refer
+			// to phi to refer to the corresponding phi arg instead.
+			// phi used to be evaluated prior to this block,
+			// and now it is evaluated in this block.
+			for _, v := range phi.Block.Values {
+				if v.Op != OpPhi || v == phi {
+					continue
+				}
+				for j, a := range v.Args {
+					if a == phi {
+						v.SetArg(j, phi.Args[j])
+					}
+				}
+			}
+			if phi.Uses != 0 {
+				phielimValue(phi)
+			} else {
+				phi.reset(OpInvalid)
+			}
+			i-- // v.moveTo put a new value at index i; reprocess
+		}
+
+		// We may have left behind some phi values with no uses
+		// but the wrong number of arguments. Eliminate those.
+		for _, v := range b.Values {
+			if v.Uses == 0 {
+				v.reset(OpInvalid)
+			}
+		}
+	}
+
+	if len(b.Preds) == 0 {
+		// Block is now dead.
+		b.Kind = BlockInvalid
+	}
+
+	phielimValue(ctl)
+	return true
+}
+
+// shortcircuitPhiPlan returns a function to handle non-ctl phi values in b,
+// where b is as described in shortcircuitBlock.
+// The returned function accepts a value v
+// and the index i of v in v.Block: v.Block.Values[i] == v.
+// If the returned function moves v to a different block, it will use v.moveTo.
+// cidx is the index in ctl of the ConstBool arg.
+// ti is the index in b.Succs of the always taken branch when arriving from p.
+// If shortcircuitPhiPlan returns nil, there is no plan available,
+// and the CFG modifications must not proceed.
+// The returned function assumes that shortcircuitBlock has completed its CFG modifications.
+func shortcircuitPhiPlan(b *Block, ctl *Value, cidx int, ti int64) func(*Value, int) {
+	// t is the "taken" branch: the successor we always go to when coming in from p.
+	t := b.Succs[ti].b
+	// u is the "untaken" branch: the successor we never go to when coming in from p.
+	u := b.Succs[1^ti].b
+
+	// In the following CFG matching, ensure that b's preds are entirely distinct from b's succs.
+	// This is probably a stronger condition than required, but this happens extremely rarely,
+	// and it makes it easier to avoid getting deceived by pretty ASCII charts. See #44465.
+	if p0, p1 := b.Preds[0].b, b.Preds[1].b; p0 == t || p1 == t || p0 == u || p1 == u {
+		return nil
+	}
+
+	// Look for some common CFG structures
+	// in which the outbound paths from b merge,
+	// with no other preds joining them.
+	// In these cases, we can reconstruct what the value
+	// of any phi in b must be in the successor blocks.
+
+	if len(t.Preds) == 1 && len(t.Succs) == 1 &&
+		len(u.Preds) == 1 && len(u.Succs) == 1 &&
+		t.Succs[0].b == u.Succs[0].b && len(t.Succs[0].b.Preds) == 2 {
+		// p   q
+		//  \ /
+		//   b
+		//  / \
+		// t   u
+		//  \ /
+		//   m
+		//
+		// After the CFG modifications, this will look like
+		//
+		// p   q
+		// |  /
+		// | b
+		// |/ \
+		// t   u
+		//  \ /
+		//   m
+		//
+		// NB: t.Preds is (b, p), not (p, b).
+		m := t.Succs[0].b
+		return func(v *Value, i int) {
+			// Replace any uses of v in t and u with the value v must have,
+			// given that we have arrived at that block.
+			// Then move v to m and adjust its value accordingly;
+			// this handles all other uses of v.
+			argP, argQ := v.Args[cidx], v.Args[1^cidx]
+			u.replaceUses(v, argQ)
+			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
+			phi.AddArg2(argQ, argP)
+			t.replaceUses(v, phi)
+			if v.Uses == 0 {
+				return
+			}
+			v.moveTo(m, i)
+			// The phi in m belongs to whichever pred idx corresponds to t.
+			if m.Preds[0].b == t {
+				v.SetArgs2(phi, argQ)
+			} else {
+				v.SetArgs2(argQ, phi)
+			}
+		}
+	}
+
+	if len(t.Preds) == 2 && len(u.Preds) == 1 && len(u.Succs) == 1 && u.Succs[0].b == t {
+		// p   q
+		//  \ /
+		//   b
+		//   |\
+		//   | u
+		//   |/
+		//   t
+		//
+		// After the CFG modifications, this will look like
+		//
+		//     q
+		//    /
+		//   b
+		//   |\
+		// p | u
+		//  \|/
+		//   t
+		//
+		// NB: t.Preds is (b or u, b or u, p).
+		return func(v *Value, i int) {
+			// Replace any uses of v in u. Then move v to t.
+			argP, argQ := v.Args[cidx], v.Args[1^cidx]
+			u.replaceUses(v, argQ)
+			v.moveTo(t, i)
+			v.SetArgs3(argQ, argQ, argP)
+		}
+	}
+
+	if len(u.Preds) == 2 && len(t.Preds) == 1 && len(t.Succs) == 1 && t.Succs[0].b == u {
+		// p   q
+		//  \ /
+		//   b
+		//  /|
+		// t |
+		//  \|
+		//   u
+		//
+		// After the CFG modifications, this will look like
+		//
+		// p   q
+		// |  /
+		// | b
+		// |/|
+		// t |
+		//  \|
+		//   u
+		//
+		// NB: t.Preds is (b, p), not (p, b).
+		return func(v *Value, i int) {
+			// Replace any uses of v in t. Then move v to u.
+			argP, argQ := v.Args[cidx], v.Args[1^cidx]
+			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
+			phi.AddArg2(argQ, argP)
+			t.replaceUses(v, phi)
+			if v.Uses == 0 {
+				return
+			}
+			v.moveTo(u, i)
+			v.SetArgs2(argQ, phi)
+		}
+	}
+
+	// Look for some common CFG structures
+	// in which one outbound path from b exits,
+	// with no other preds joining.
+	// In these cases, we can reconstruct what the value
+	// of any phi in b must be in the path leading to exit,
+	// and move the phi to the non-exit path.
+
+	if len(t.Preds) == 1 && len(u.Preds) == 1 && len(t.Succs) == 0 {
+		// p   q
+		//  \ /
+		//   b
+		//  / \
+		// t   u
+		//
+		// where t is an Exit/Ret block.
+		//
+		// After the CFG modifications, this will look like
+		//
+		// p   q
+		// |  /
+		// | b
+		// |/ \
+		// t   u
+		//
+		// NB: t.Preds is (b, p), not (p, b).
+		return func(v *Value, i int) {
+			// Replace any uses of v in t and x. Then move v to u.
+			argP, argQ := v.Args[cidx], v.Args[1^cidx]
+			// If there are no uses of v in t or x, this phi will be unused.
+			// That's OK; it's not worth the cost to prevent that.
+			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
+			phi.AddArg2(argQ, argP)
+			t.replaceUses(v, phi)
+			if v.Uses == 0 {
+				return
+			}
+			v.moveTo(u, i)
+			v.SetArgs1(argQ)
+		}
+	}
+
+	if len(u.Preds) == 1 && len(t.Preds) == 1 && len(u.Succs) == 0 {
+		// p   q
+		//  \ /
+		//   b
+		//  / \
+		// t   u
+		//
+		// where u is an Exit/Ret block.
+		//
+		// After the CFG modifications, this will look like
+		//
+		// p   q
+		// |  /
+		// | b
+		// |/ \
+		// t   u
+		//
+		// NB: t.Preds is (b, p), not (p, b).
+		return func(v *Value, i int) {
+			// Replace any uses of v in u (and x). Then move v to t.
+			argP, argQ := v.Args[cidx], v.Args[1^cidx]
+			u.replaceUses(v, argQ)
+			v.moveTo(t, i)
+			v.SetArgs2(argQ, argP)
+		}
+	}
+
+	// TODO: handle more cases; shortcircuit optimizations turn out to be reasonably high impact
+	return nil
+}
+
+// replaceUses replaces all uses of old in b with new.
+func (b *Block) replaceUses(old, new *Value) {
+	for _, v := range b.Values {
+		for i, a := range v.Args {
+			if a == old {
+				v.SetArg(i, new)
+			}
+		}
+	}
+	for i, v := range b.ControlValues() {
+		if v == old {
+			b.ReplaceControl(i, new)
+		}
+	}
+}
+
+// moveTo moves v to dst, adjusting the appropriate Block.Values slices.
+// The caller is responsible for ensuring that this is safe.
+// i is the index of v in v.Block.Values.
+func (v *Value) moveTo(dst *Block, i int) {
+	if dst.Func.scheduled {
+		v.Fatalf("moveTo after scheduling")
+	}
+	src := v.Block
+	if src.Values[i] != v {
+		v.Fatalf("moveTo bad index %d", v, i)
+	}
+	if src == dst {
+		return
+	}
+	v.Block = dst
+	dst.Values = append(dst.Values, v)
+	last := len(src.Values) - 1
+	src.Values[i] = src.Values[last]
+	src.Values[last] = nil
+	src.Values = src.Values[:last]
+}