golang phiopt 代码
文件路径：/src/cmd/compile/internal/ssa/phiopt.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
/ phiopt eliminates boolean Phis based on the previous if.
/
/ Main use case is to transform:
/
/ x := false
/ if b {
/ x = true
/ }
/
/ into x = b.
/
/ In SSA code this appears as
/
/ b0
/ If b -> b1 b2
/ b1
/ Plain -> b2
/ b2
/ x = (OpPhi (ConstBool [true]) (ConstBool [false]))
/
/ In this case we can replace x with a copy of b.
func phiopt(f *Func) {
sdom := f.Sdom()
for _, b := range f.Blocks {
if len(b.Preds) != 2 || len(b.Values) == 0 {
/ TODO: handle more than 2 predecessors, e.g. a || b || c.
continue
}
pb0, b0 := b, b.Preds[0].b
for len(b0.Succs) == 1 && len(b0.Preds) == 1 {
pb0, b0 = b0, b0.Preds[0].b
}
if b0.Kind != BlockIf {
continue
}
pb1, b1 := b, b.Preds[1].b
for len(b1.Succs) == 1 && len(b1.Preds) == 1 {
pb1, b1 = b1, b1.Preds[0].b
}
if b1 != b0 {
continue
}
/ b0 is the if block giving the boolean value.
/ reverse is the predecessor from which the truth value comes.
var reverse int
if b0.Succs[0].b == pb0 && b0.Succs[1].b == pb1 {
reverse = 0
} else if b0.Succs[0].b == pb1 && b0.Succs[1].b == pb0 {
reverse = 1
} else {
b.Fatalf("invalid predecessors\n")
}
for _, v := range b.Values {
if v.Op != OpPhi {
continue
}
/ Look for conversions from bool to 0/1.
if v.Type.IsInteger() {
phioptint(v, b0, reverse)
}
if !v.Type.IsBoolean() {
continue
}
/ Replaces
/ if a { x = true } else { x = false } with x = a
/ and
/ if a { x = false } else { x = true } with x = !a
if v.Args[0].Op == OpConstBool && v.Args[1].Op == OpConstBool {
if v.Args[reverse].AuxInt != v.Args[1-reverse].AuxInt {
ops := [2]Op{OpNot, OpCopy}
v.reset(ops[v.Args[reverse].AuxInt])
v.AddArg(b0.Controls[0])
if f.pass.debug > 0 {
f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
}
continue
}
}
/ Replaces
/ if a { x = true } else { x = value } with x = a || value.
/ Requires that value dominates x, meaning that regardless of a,
/ value is always computed. This guarantees that the side effects
/ of value are not seen if a is false.
if v.Args[reverse].Op == OpConstBool && v.Args[reverse].AuxInt == 1 {
if tmp := v.Args[1-reverse]; sdom.IsAncestorEq(tmp.Block, b) {
v.reset(OpOrB)
v.SetArgs2(b0.Controls[0], tmp)
if f.pass.debug > 0 {
f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
}
continue
}
}
/ Replaces
/ if a { x = value } else { x = false } with x = a && value.
/ Requires that value dominates x, meaning that regardless of a,
/ value is always computed. This guarantees that the side effects
/ of value are not seen if a is false.
if v.Args[1-reverse].Op == OpConstBool && v.Args[1-reverse].AuxInt == 0 {
if tmp := v.Args[reverse]; sdom.IsAncestorEq(tmp.Block, b) {
v.reset(OpAndB)
v.SetArgs2(b0.Controls[0], tmp)
if f.pass.debug > 0 {
f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
}
continue
}
}
}
}
/ strengthen phi optimization.
/ Main use case is to transform:
/ x := false
/ if c {
/ x = true
/ ...
/ }
/ into
/ x := c
/ if x { ... }
/
/ For example, in SSA code a case appears as
/ b0
/ If c -> b, sb0
/ sb0
/ If d -> sd0, sd1
/ sd1
/ ...
/ sd0
/ Plain -> b
/ b
/ x = (OpPhi (ConstBool [true]) (ConstBool [false]))
/
/ In this case we can also replace x with a copy of c.
/
/ The optimization idea:
/ 1. block b has a phi value x, x = OpPhi (ConstBool [true]) (ConstBool [false]),
/ and len(b.Preds) is equal to 2.
/ 2. find the common dominator(b0) of the predecessors(pb0, pb1) of block b, and the
/ dominator(b0) is a If block.
/ Special case: one of the predecessors(pb0 or pb1) is the dominator(b0).
/ 3. the successors(sb0, sb1) of the dominator need to dominate the predecessors(pb0, pb1)
/ of block b respectively.
/ 4. replace this boolean Phi based on dominator block.
/
/ b0(pb0) b0(pb1) b0
/ | \ / | / \
/ | sb1 sb0 | sb0 sb1
/ | ... ... | ... ...
/ | pb1 pb0 | pb0 pb1
/ | / \ | \ /
/ b b b
/
var lca *lcaRange
for _, b := range f.Blocks {
if len(b.Preds) != 2 || len(b.Values) == 0 {
/ TODO: handle more than 2 predecessors, e.g. a || b || c.
continue
}
for _, v := range b.Values {
/ find a phi value v = OpPhi (ConstBool [true]) (ConstBool [false]).
/ TODO: v = OpPhi (ConstBool [true]) (Arg <bool> {value})
if v.Op != OpPhi {
continue
}
if v.Args[0].Op != OpConstBool || v.Args[1].Op != OpConstBool {
continue
}
if v.Args[0].AuxInt == v.Args[1].AuxInt {
continue
}
pb0 := b.Preds[0].b
pb1 := b.Preds[1].b
if pb0.Kind == BlockIf && pb0 == sdom.Parent(b) {
/ special case: pb0 is the dominator block b0.
/ b0(pb0)
/ | \
/ | sb1
/ | ...
/ | pb1
/ | /
/ b
/ if another successor sb1 of b0(pb0) dominates pb1, do replace.
ei := b.Preds[0].i
sb1 := pb0.Succs[1-ei].b
if sdom.IsAncestorEq(sb1, pb1) {
convertPhi(pb0, v, ei)
break
}
} else if pb1.Kind == BlockIf && pb1 == sdom.Parent(b) {
/ special case: pb1 is the dominator block b0.
/ b0(pb1)
/ / |
/ sb0 |
/ ... |
/ pb0 |
/ \ |
/ b
/ if another successor sb0 of b0(pb0) dominates pb0, do replace.
ei := b.Preds[1].i
sb0 := pb1.Succs[1-ei].b
if sdom.IsAncestorEq(sb0, pb0) {
convertPhi(pb1, v, 1-ei)
break
}
} else {
/ b0
/ / \
/ sb0 sb1
/ ... ...
/ pb0 pb1
/ \ /
/ b
/
/ Build data structure for fast least-common-ancestor queries.
if lca == nil {
lca = makeLCArange(f)
}
b0 := lca.find(pb0, pb1)
if b0.Kind != BlockIf {
break
}
sb0 := b0.Succs[0].b
sb1 := b0.Succs[1].b
var reverse int
if sdom.IsAncestorEq(sb0, pb0) && sdom.IsAncestorEq(sb1, pb1) {
reverse = 0
} else if sdom.IsAncestorEq(sb1, pb0) && sdom.IsAncestorEq(sb0, pb1) {
reverse = 1
} else {
break
}
if len(sb0.Preds) != 1 || len(sb1.Preds) != 1 {
/ we can not replace phi value x in the following case.
/ if gp == nil || sp < lo { x = true}
/ if a || b { x = true }
/ so the if statement can only have one condition.
break
}
convertPhi(b0, v, reverse)
}
}
}
}
func phioptint(v *Value, b0 *Block, reverse int) {
a0 := v.Args[0]
a1 := v.Args[1]
if a0.Op != a1.Op {
return
}
switch a0.Op {
case OpConst8, OpConst16, OpConst32, OpConst64:
default:
return
}
negate := false
switch {
case a0.AuxInt == 0 && a1.AuxInt == 1:
negate = true
case a0.AuxInt == 1 && a1.AuxInt == 0:
default:
return
}
if reverse == 1 {
negate = !negate
}
a := b0.Controls[0]
if negate {
a = v.Block.NewValue1(v.Pos, OpNot, a.Type, a)
}
v.AddArg(a)
cvt := v.Block.NewValue1(v.Pos, OpCvtBoolToUint8, v.Block.Func.Config.Types.UInt8, a)
switch v.Type.Size() {
case 1:
v.reset(OpCopy)
case 2:
v.reset(OpZeroExt8to16)
case 4:
v.reset(OpZeroExt8to32)
case 8:
v.reset(OpZeroExt8to64)
default:
v.Fatalf("bad int size %d", v.Type.Size())
}
v.AddArg(cvt)
f := b0.Func
if f.pass.debug > 0 {
f.Warnl(v.Block.Pos, "converted OpPhi bool -> int%d", v.Type.Size()*8)
}
}
/ b is the If block giving the boolean value.
/ v is the phi value v = (OpPhi (ConstBool [true]) (ConstBool [false])).
/ reverse is the predecessor from which the truth value comes.
func convertPhi(b *Block, v *Value, reverse int) {
f := b.Func
ops := [2]Op{OpNot, OpCopy}
v.reset(ops[v.Args[reverse].AuxInt])
v.AddArg(b.Controls[0])
if f.pass.debug > 0 {
f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
}
}