path: root/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)
	}
}