phiopt.go

     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  		// reverse is the predecessor from which the truth value comes.
    50  		var reverse int
    51  		if b0.Succs[0].b == pb0 && b0.Succs[1].b == pb1 {
    52  			reverse = 0
    53  		} else if b0.Succs[0].b == pb1 && b0.Succs[1].b == pb0 {
    54  			reverse = 1
    55  		} else {
    56  			b.Fatalf("invalid predecessors\n")
    57  		}
    58  
    59  		for _, v := range b.Values {
    60  			if v.Op != OpPhi {
    61  				continue
    62  			}
    63  
    64  			// Look for conversions from bool to 0/1.
    65  			if v.Type.IsInteger() {
    66  				phioptint(v, b0, reverse)
    67  			}
    68  
    69  			if !v.Type.IsBoolean() {
    70  				continue
    71  			}
    72  
    73  			// Replaces
    74  			//   if a { x = true } else { x = false } with x = a
    75  			// and
    76  			//   if a { x = false } else { x = true } with x = !a
    77  			if v.Args[0].Op == OpConstBool && v.Args[1].Op == OpConstBool {
    78  				if v.Args[reverse].AuxInt != v.Args[1-reverse].AuxInt {
    79  					ops := [2]Op{OpNot, OpCopy}
    80  					v.reset(ops[v.Args[reverse].AuxInt])
    81  					v.AddArg(b0.Controls[0])
    82  					if f.pass.debug > 0 {
    83  						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
    84  					}
    85  					continue
    86  				}
    87  			}
    88  
    89  			// Replaces
    90  			//   if a { x = true } else { x = value } with x = a || value.
    91  			// Requires that value dominates x, meaning that regardless of a,
    92  			// value is always computed. This guarantees that the side effects
    93  			// of value are not seen if a is false.
    94  			if v.Args[reverse].Op == OpConstBool && v.Args[reverse].AuxInt == 1 {
    95  				if tmp := v.Args[1-reverse]; sdom.IsAncestorEq(tmp.Block, b) {
    96  					v.reset(OpOrB)
    97  					v.SetArgs2(b0.Controls[0], tmp)
    98  					if f.pass.debug > 0 {
    99  						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
   100  					}
   101  					continue
   102  				}
   103  			}
   104  
   105  			// Replaces
   106  			//   if a { x = value } else { x = false } with x = a && value.
   107  			// Requires that value dominates x, meaning that regardless of a,
   108  			// value is always computed. This guarantees that the side effects
   109  			// of value are not seen if a is false.
   110  			if v.Args[1-reverse].Op == OpConstBool && v.Args[1-reverse].AuxInt == 0 {
   111  				if tmp := v.Args[reverse]; sdom.IsAncestorEq(tmp.Block, b) {
   112  					v.reset(OpAndB)
   113  					v.SetArgs2(b0.Controls[0], tmp)
   114  					if f.pass.debug > 0 {
   115  						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
   116  					}
   117  					continue
   118  				}
   119  			}
   120  		}
   121  	}
   122  	// strengthen phi optimization.
   123  	// Main use case is to transform:
   124  	//   x := false
   125  	//   if c {
   126  	//     x = true
   127  	//     ...
   128  	//   }
   129  	// into
   130  	//   x := c
   131  	//   if x { ... }
   132  	//
   133  	// For example, in SSA code a case appears as
   134  	// b0
   135  	//   If c -> b, sb0
   136  	// sb0
   137  	//   If d -> sd0, sd1
   138  	// sd1
   139  	//   ...
   140  	// sd0
   141  	//   Plain -> b
   142  	// b
   143  	//   x = (OpPhi (ConstBool [true]) (ConstBool [false]))
   144  	//
   145  	// In this case we can also replace x with a copy of c.
   146  	//
   147  	// The optimization idea:
   148  	// 1. block b has a phi value x, x = OpPhi (ConstBool [true]) (ConstBool [false]),
   149  	//    and len(b.Preds) is equal to 2.
   150  	// 2. find the common dominator(b0) of the predecessors(pb0, pb1) of block b, and the
   151  	//    dominator(b0) is a If block.
   152  	//    Special case: one of the predecessors(pb0 or pb1) is the dominator(b0).
   153  	// 3. the successors(sb0, sb1) of the dominator need to dominate the predecessors(pb0, pb1)
   154  	//    of block b respectively.
   155  	// 4. replace this boolean Phi based on dominator block.
   156  	//
   157  	//     b0(pb0)            b0(pb1)          b0
   158  	//    |  \               /  |             /  \
   159  	//    |  sb1           sb0  |           sb0  sb1
   160  	//    |  ...           ...  |           ...   ...
   161  	//    |  pb1           pb0  |           pb0  pb1
   162  	//    |  /               \  |            \   /
   163  	//     b                   b               b
   164  	//
   165  	var lca *lcaRange
   166  	for _, b := range f.Blocks {
   167  		if len(b.Preds) != 2 || len(b.Values) == 0 {
   168  			// TODO: handle more than 2 predecessors, e.g. a || b || c.
   169  			continue
   170  		}
   171  
   172  		for _, v := range b.Values {
   173  			// find a phi value v = OpPhi (ConstBool [true]) (ConstBool [false]).
   174  			// TODO: v = OpPhi (ConstBool [true]) (Arg <bool> {value})
   175  			if v.Op != OpPhi {
   176  				continue
   177  			}
   178  			if v.Args[0].Op != OpConstBool || v.Args[1].Op != OpConstBool {
   179  				continue
   180  			}
   181  			if v.Args[0].AuxInt == v.Args[1].AuxInt {
   182  				continue
   183  			}
   184  
   185  			pb0 := b.Preds[0].b
   186  			pb1 := b.Preds[1].b
   187  			if pb0.Kind == BlockIf && pb0 == sdom.Parent(b) {
   188  				// special case: pb0 is the dominator block b0.
   189  				//     b0(pb0)
   190  				//    |  \
   191  				//    |  sb1
   192  				//    |  ...
   193  				//    |  pb1
   194  				//    |  /
   195  				//     b
   196  				// if another successor sb1 of b0(pb0) dominates pb1, do replace.
   197  				ei := b.Preds[0].i
   198  				sb1 := pb0.Succs[1-ei].b
   199  				if sdom.IsAncestorEq(sb1, pb1) {
   200  					convertPhi(pb0, v, ei)
   201  					break
   202  				}
   203  			} else if pb1.Kind == BlockIf && pb1 == sdom.Parent(b) {
   204  				// special case: pb1 is the dominator block b0.
   205  				//       b0(pb1)
   206  				//     /   |
   207  				//    sb0  |
   208  				//    ...  |
   209  				//    pb0  |
   210  				//      \  |
   211  				//        b
   212  				// if another successor sb0 of b0(pb0) dominates pb0, do replace.
   213  				ei := b.Preds[1].i
   214  				sb0 := pb1.Succs[1-ei].b
   215  				if sdom.IsAncestorEq(sb0, pb0) {
   216  					convertPhi(pb1, v, 1-ei)
   217  					break
   218  				}
   219  			} else {
   220  				//      b0
   221  				//     /   \
   222  				//    sb0  sb1
   223  				//    ...  ...
   224  				//    pb0  pb1
   225  				//      \   /
   226  				//        b
   227  				//
   228  				// Build data structure for fast least-common-ancestor queries.
   229  				if lca == nil {
   230  					lca = makeLCArange(f)
   231  				}
   232  				b0 := lca.find(pb0, pb1)
   233  				if b0.Kind != BlockIf {
   234  					break
   235  				}
   236  				sb0 := b0.Succs[0].b
   237  				sb1 := b0.Succs[1].b
   238  				var reverse int
   239  				if sdom.IsAncestorEq(sb0, pb0) && sdom.IsAncestorEq(sb1, pb1) {
   240  					reverse = 0
   241  				} else if sdom.IsAncestorEq(sb1, pb0) && sdom.IsAncestorEq(sb0, pb1) {
   242  					reverse = 1
   243  				} else {
   244  					break
   245  				}
   246  				if len(sb0.Preds) != 1 || len(sb1.Preds) != 1 {
   247  					// we can not replace phi value x in the following case.
   248  					//   if gp == nil || sp < lo { x = true}
   249  					//   if a || b { x = true }
   250  					// so the if statement can only have one condition.
   251  					break
   252  				}
   253  				convertPhi(b0, v, reverse)
   254  			}
   255  		}
   256  	}
   257  }
   258  
   259  func phioptint(v *Value, b0 *Block, reverse int) {
   260  	a0 := v.Args[0]
   261  	a1 := v.Args[1]
   262  	if a0.Op != a1.Op {
   263  		return
   264  	}
   265  
   266  	switch a0.Op {
   267  	case OpConst8, OpConst16, OpConst32, OpConst64:
   268  	default:
   269  		return
   270  	}
   271  
   272  	negate := false
   273  	switch {
   274  	case a0.AuxInt == 0 && a1.AuxInt == 1:
   275  		negate = true
   276  	case a0.AuxInt == 1 && a1.AuxInt == 0:
   277  	default:
   278  		return
   279  	}
   280  
   281  	if reverse == 1 {
   282  		negate = !negate
   283  	}
   284  
   285  	a := b0.Controls[0]
   286  	if negate {
   287  		a = v.Block.NewValue1(v.Pos, OpNot, a.Type, a)
   288  	}
   289  	v.AddArg(a)
   290  
   291  	cvt := v.Block.NewValue1(v.Pos, OpCvtBoolToUint8, v.Block.Func.Config.Types.UInt8, a)
   292  	switch v.Type.Size() {
   293  	case 1:
   294  		v.reset(OpCopy)
   295  	case 2:
   296  		v.reset(OpZeroExt8to16)
   297  	case 4:
   298  		v.reset(OpZeroExt8to32)
   299  	case 8:
   300  		v.reset(OpZeroExt8to64)
   301  	default:
   302  		v.Fatalf("bad int size %d", v.Type.Size())
   303  	}
   304  	v.AddArg(cvt)
   305  
   306  	f := b0.Func
   307  	if f.pass.debug > 0 {
   308  		f.Warnl(v.Block.Pos, "converted OpPhi bool -> int%d", v.Type.Size()*8)
   309  	}
   310  }
   311  
   312  // b is the If block giving the boolean value.
   313  // v is the phi value v = (OpPhi (ConstBool [true]) (ConstBool [false])).
   314  // reverse is the predecessor from which the truth value comes.
   315  func convertPhi(b *Block, v *Value, reverse int) {
   316  	f := b.Func
   317  	ops := [2]Op{OpNot, OpCopy}
   318  	v.reset(ops[v.Args[reverse].AuxInt])
   319  	v.AddArg(b.Controls[0])
   320  	if f.pass.debug > 0 {
   321  		f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
   322  	}
   323  }
   324
View as plain text