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