src/cmd/compile/internal/ssa/shortcircuit.go - go - Git at Google

 // 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)
 	n := len(b.Preds)
 	ctl.Args[cidx].Uses--
 	ctl.Args[cidx] = ctl.Args[n]
 	ctl.Args[n] = nil
 	ctl.Args = ctl.Args[:n]

 	// 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

 	// 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]
 }
	// 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)
	n := len(b.Preds)
	ctl.Args[cidx].Uses--
	ctl.Args[cidx] = ctl.Args[n]
	ctl.Args[n] = nil
	ctl.Args = ctl.Args[:n]

	// 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

	// 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]
	}