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