go shortcircuit 源码
golang shortcircuit 代码
文件路径：/src/cmd/compile/internal/ssa/shortcircuit.go
// 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]
}
相关信息
相关文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
6、 golang
-
7、 openharmony