Home | History | Annotate | Download | only in ssa 
      1 // Copyright 2016 The Go Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style
      3 // license that can be found in the LICENSE file.
      4 
      5 package ssa
      6 
      7 // phiopt eliminates boolean Phis based on the previous if.
      8 //
      9 // Main use case is to transform:
     10 //   x := false
     11 //   if b {
     12 //     x = true
     13 //   }
     14 // into x = b.
     15 //
     16 // In SSA code this appears as
     17 //
     18 // b0
     19 //   If b -> b1 b2
     20 // b1
     21 //   Plain -> b2
     22 // b2
     23 //   x = (OpPhi (ConstBool [true]) (ConstBool [false]))
     24 //
     25 // In this case we can replace x with a copy of b.
     26 func phiopt(f *Func) {
     27 	sdom := f.sdom()
     28 	for _, b := range f.Blocks {
     29 		if len(b.Preds) != 2 || len(b.Values) == 0 {
     30 			// TODO: handle more than 2 predecessors, e.g. a || b || c.
     31 			continue
     32 		}
     33 
     34 		pb0, b0 := b, b.Preds[0].b
     35 		for len(b0.Succs) == 1 && len(b0.Preds) == 1 {
     36 			pb0, b0 = b0, b0.Preds[0].b
     37 		}
     38 		if b0.Kind != BlockIf {
     39 			continue
     40 		}
     41 		pb1, b1 := b, b.Preds[1].b
     42 		for len(b1.Succs) == 1 && len(b1.Preds) == 1 {
     43 			pb1, b1 = b1, b1.Preds[0].b
     44 		}
     45 		if b1 != b0 {
     46 			continue
     47 		}
     48 		// b0 is the if block giving the boolean value.
     49 
     50 		// reverse is the predecessor from which the truth value comes.
     51 		var reverse int
     52 		if b0.Succs[0].b == pb0 && b0.Succs[1].b == pb1 {
     53 			reverse = 0
     54 		} else if b0.Succs[0].b == pb1 && b0.Succs[1].b == pb0 {
     55 			reverse = 1
     56 		} else {
     57 			b.Fatalf("invalid predecessors\n")
     58 		}
     59 
     60 		for _, v := range b.Values {
     61 			if v.Op != OpPhi {
     62 				continue
     63 			}
     64 
     65 			// Look for conversions from bool to 0/1.
     66 			if v.Type.IsInteger() {
     67 				phioptint(v, b0, reverse)
     68 			}
     69 
     70 			if !v.Type.IsBoolean() {
     71 				continue
     72 			}
     73 
     74 			// Replaces
     75 			//   if a { x = true } else { x = false } with x = a
     76 			// and
     77 			//   if a { x = false } else { x = true } with x = !a
     78 			if v.Args[0].Op == OpConstBool && v.Args[1].Op == OpConstBool {
     79 				if v.Args[reverse].AuxInt != v.Args[1-reverse].AuxInt {
     80 					ops := [2]Op{OpNot, OpCopy}
     81 					v.reset(ops[v.Args[reverse].AuxInt])
     82 					v.AddArg(b0.Control)
     83 					if f.pass.debug > 0 {
     84 						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
     85 					}
     86 					continue
     87 				}
     88 			}
     89 
     90 			// Replaces
     91 			//   if a { x = true } else { x = value } with x = a || value.
     92 			// Requires that value dominates x, meaning that regardless of a,
     93 			// value is always computed. This guarantees that the side effects
     94 			// of value are not seen if a is false.
     95 			if v.Args[reverse].Op == OpConstBool && v.Args[reverse].AuxInt == 1 {
     96 				if tmp := v.Args[1-reverse]; sdom.isAncestorEq(tmp.Block, b) {
     97 					v.reset(OpOrB)
     98 					v.SetArgs2(b0.Control, tmp)
     99 					if f.pass.debug > 0 {
    100 						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
    101 					}
    102 					continue
    103 				}
    104 			}
    105 
    106 			// Replaces
    107 			//   if a { x = value } else { x = false } with x = a && value.
    108 			// Requires that value dominates x, meaning that regardless of a,
    109 			// value is always computed. This guarantees that the side effects
    110 			// of value are not seen if a is false.
    111 			if v.Args[1-reverse].Op == OpConstBool && v.Args[1-reverse].AuxInt == 0 {
    112 				if tmp := v.Args[reverse]; sdom.isAncestorEq(tmp.Block, b) {
    113 					v.reset(OpAndB)
    114 					v.SetArgs2(b0.Control, tmp)
    115 					if f.pass.debug > 0 {
    116 						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
    117 					}
    118 					continue
    119 				}
    120 			}
    121 		}
    122 	}
    123 }
    124 
    125 func phioptint(v *Value, b0 *Block, reverse int) {
    126 	a0 := v.Args[0]
    127 	a1 := v.Args[1]
    128 	if a0.Op != a1.Op {
    129 		return
    130 	}
    131 
    132 	switch a0.Op {
    133 	case OpConst8, OpConst16, OpConst32, OpConst64:
    134 	default:
    135 		return
    136 	}
    137 
    138 	negate := false
    139 	switch {
    140 	case a0.AuxInt == 0 && a1.AuxInt == 1:
    141 		negate = true
    142 	case a0.AuxInt == 1 && a1.AuxInt == 0:
    143 	default:
    144 		return
    145 	}
    146 
    147 	if reverse == 1 {
    148 		negate = !negate
    149 	}
    150 
    151 	switch v.Type.Size() {
    152 	case 1:
    153 		v.reset(OpCopy)
    154 	case 2:
    155 		v.reset(OpZeroExt8to16)
    156 	case 4:
    157 		v.reset(OpZeroExt8to32)
    158 	case 8:
    159 		v.reset(OpZeroExt8to64)
    160 	default:
    161 		v.Fatalf("bad int size %d", v.Type.Size())
    162 	}
    163 
    164 	a := b0.Control
    165 	if negate {
    166 		a = v.Block.NewValue1(v.Pos, OpNot, a.Type, a)
    167 	}
    168 	v.AddArg(a)
    169 
    170 	f := b0.Func
    171 	if f.pass.debug > 0 {
    172 		f.Warnl(v.Block.Pos, "converted OpPhi bool -> int%d", v.Type.Size()*8)
    173 	}
    174 }
    175