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  			// Replaces
   123  			//   if a { x = value } else { x = a } with x = a && value.
   124  			// Requires that value dominates x.
   125  			if v.Args[1-reverse] == b0.Controls[0] {
   126  				if tmp := v.Args[reverse]; sdom.IsAncestorEq(tmp.Block, b) {
   127  					v.reset(OpAndB)
   128  					v.SetArgs2(b0.Controls[0], tmp)
   129  					if f.pass.debug > 0 {
   130  						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
   131  					}
   132  					continue
   133  				}
   134  			}
   135  
   136  			// Replaces
   137  			//   if a { x = a } else { x = value } with x = a || value.
   138  			// Requires that value dominates x.
   139  			if v.Args[reverse] == b0.Controls[0] {
   140  				if tmp := v.Args[1-reverse]; sdom.IsAncestorEq(tmp.Block, b) {
   141  					v.reset(OpOrB)
   142  					v.SetArgs2(b0.Controls[0], tmp)
   143  					if f.pass.debug > 0 {
   144  						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
   145  					}
   146  					continue
   147  				}
   148  			}
   149  		}
   150  	}
   151  	// strengthen phi optimization.
   152  	// Main use case is to transform:
   153  	//   x := false
   154  	//   if c {
   155  	//     x = true
   156  	//     ...
   157  	//   }
   158  	// into
   159  	//   x := c
   160  	//   if x { ... }
   161  	//
   162  	// For example, in SSA code a case appears as
   163  	// b0
   164  	//   If c -> b, sb0
   165  	// sb0
   166  	//   If d -> sd0, sd1
   167  	// sd1
   168  	//   ...
   169  	// sd0
   170  	//   Plain -> b
   171  	// b
   172  	//   x = (OpPhi (ConstBool [true]) (ConstBool [false]))
   173  	//
   174  	// In this case we can also replace x with a copy of c.
   175  	//
   176  	// The optimization idea:
   177  	// 1. block b has a phi value x, x = OpPhi (ConstBool [true]) (ConstBool [false]),
   178  	//    and len(b.Preds) is equal to 2.
   179  	// 2. find the common dominator(b0) of the predecessors(pb0, pb1) of block b, and the
   180  	//    dominator(b0) is a If block.
   181  	//    Special case: one of the predecessors(pb0 or pb1) is the dominator(b0).
   182  	// 3. the successors(sb0, sb1) of the dominator need to dominate the predecessors(pb0, pb1)
   183  	//    of block b respectively.
   184  	// 4. replace this boolean Phi based on dominator block.
   185  	//
   186  	//     b0(pb0)            b0(pb1)          b0
   187  	//    |  \               /  |             /  \
   188  	//    |  sb1           sb0  |           sb0  sb1
   189  	//    |  ...           ...  |           ...   ...
   190  	//    |  pb1           pb0  |           pb0  pb1
   191  	//    |  /               \  |            \   /
   192  	//     b                   b               b
   193  	//
   194  	var lca *lcaRange
   195  	for _, b := range f.Blocks {
   196  		if len(b.Preds) != 2 || len(b.Values) == 0 {
   197  			// TODO: handle more than 2 predecessors, e.g. a || b || c.
   198  			continue
   199  		}
   200  
   201  		for _, v := range b.Values {
   202  			// find a phi value v = OpPhi (ConstBool [true]) (ConstBool [false]).
   203  			// TODO: v = OpPhi (ConstBool [true]) (Arg <bool> {value})
   204  			if v.Op != OpPhi {
   205  				continue
   206  			}
   207  			if v.Args[0].Op != OpConstBool || v.Args[1].Op != OpConstBool {
   208  				continue
   209  			}
   210  			if v.Args[0].AuxInt == v.Args[1].AuxInt {
   211  				continue
   212  			}
   213  
   214  			pb0 := b.Preds[0].b
   215  			pb1 := b.Preds[1].b
   216  			if pb0.Kind == BlockIf && pb0 == sdom.Parent(b) {
   217  				// special case: pb0 is the dominator block b0.
   218  				//     b0(pb0)
   219  				//    |  \
   220  				//    |  sb1
   221  				//    |  ...
   222  				//    |  pb1
   223  				//    |  /
   224  				//     b
   225  				// if another successor sb1 of b0(pb0) dominates pb1, do replace.
   226  				ei := b.Preds[0].i
   227  				sb1 := pb0.Succs[1-ei].b
   228  				if sdom.IsAncestorEq(sb1, pb1) {
   229  					convertPhi(pb0, v, ei)
   230  					break
   231  				}
   232  			} else if pb1.Kind == BlockIf && pb1 == sdom.Parent(b) {
   233  				// special case: pb1 is the dominator block b0.
   234  				//       b0(pb1)
   235  				//     /   |
   236  				//    sb0  |
   237  				//    ...  |
   238  				//    pb0  |
   239  				//      \  |
   240  				//        b
   241  				// if another successor sb0 of b0(pb0) dominates pb0, do replace.
   242  				ei := b.Preds[1].i
   243  				sb0 := pb1.Succs[1-ei].b
   244  				if sdom.IsAncestorEq(sb0, pb0) {
   245  					convertPhi(pb1, v, 1-ei)
   246  					break
   247  				}
   248  			} else {
   249  				//      b0
   250  				//     /   \
   251  				//    sb0  sb1
   252  				//    ...  ...
   253  				//    pb0  pb1
   254  				//      \   /
   255  				//        b
   256  				//
   257  				// Build data structure for fast least-common-ancestor queries.
   258  				if lca == nil {
   259  					lca = makeLCArange(f)
   260  				}
   261  				b0 := lca.find(pb0, pb1)
   262  				if b0.Kind != BlockIf {
   263  					break
   264  				}
   265  				sb0 := b0.Succs[0].b
   266  				sb1 := b0.Succs[1].b
   267  				var reverse int
   268  				if sdom.IsAncestorEq(sb0, pb0) && sdom.IsAncestorEq(sb1, pb1) {
   269  					reverse = 0
   270  				} else if sdom.IsAncestorEq(sb1, pb0) && sdom.IsAncestorEq(sb0, pb1) {
   271  					reverse = 1
   272  				} else {
   273  					break
   274  				}
   275  				if len(sb0.Preds) != 1 || len(sb1.Preds) != 1 {
   276  					// we can not replace phi value x in the following case.
   277  					//   if gp == nil || sp < lo { x = true}
   278  					//   if a || b { x = true }
   279  					// so the if statement can only have one condition.
   280  					break
   281  				}
   282  				convertPhi(b0, v, reverse)
   283  			}
   284  		}
   285  	}
   286  }
   287  
   288  func phioptint(v *Value, b0 *Block, reverse int) {
   289  	a0 := v.Args[0]
   290  	a1 := v.Args[1]
   291  	if a0.Op != a1.Op {
   292  		return
   293  	}
   294  
   295  	switch a0.Op {
   296  	case OpConst8, OpConst16, OpConst32, OpConst64:
   297  	default:
   298  		return
   299  	}
   300  
   301  	negate := false
   302  	switch {
   303  	case a0.AuxInt == 0 && a1.AuxInt == 1:
   304  		negate = true
   305  	case a0.AuxInt == 1 && a1.AuxInt == 0:
   306  	default:
   307  		return
   308  	}
   309  
   310  	if reverse == 1 {
   311  		negate = !negate
   312  	}
   313  
   314  	a := b0.Controls[0]
   315  	if negate {
   316  		a = v.Block.NewValue1(v.Pos, OpNot, a.Type, a)
   317  	}
   318  	v.AddArg(a)
   319  
   320  	cvt := v.Block.NewValue1(v.Pos, OpCvtBoolToUint8, v.Block.Func.Config.Types.UInt8, a)
   321  	switch v.Type.Size() {
   322  	case 1:
   323  		v.reset(OpCopy)
   324  	case 2:
   325  		v.reset(OpZeroExt8to16)
   326  	case 4:
   327  		v.reset(OpZeroExt8to32)
   328  	case 8:
   329  		v.reset(OpZeroExt8to64)
   330  	default:
   331  		v.Fatalf("bad int size %d", v.Type.Size())
   332  	}
   333  	v.AddArg(cvt)
   334  
   335  	f := b0.Func
   336  	if f.pass.debug > 0 {
   337  		f.Warnl(v.Block.Pos, "converted OpPhi bool -> int%d", v.Type.Size()*8)
   338  	}
   339  }
   340  
   341  // b is the If block giving the boolean value.
   342  // v is the phi value v = (OpPhi (ConstBool [true]) (ConstBool [false])).
   343  // reverse is the predecessor from which the truth value comes.
   344  func convertPhi(b *Block, v *Value, reverse int) {
   345  	f := b.Func
   346  	ops := [2]Op{OpNot, OpCopy}
   347  	v.reset(ops[v.Args[reverse].AuxInt])
   348  	v.AddArg(b.Controls[0])
   349  	if f.pass.debug > 0 {
   350  		f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
   351  	}
   352  }
   353
View as plain text