loopbce.go

     1  // Copyright 2018 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  import (
     8  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/types"
    10  	"fmt"
    11  )
    12  
    13  type indVarFlags uint8
    14  
    15  const (
    16  	indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive)
    17  	indVarMaxInc                         // maximum value is inclusive (default: exclusive)
    18  )
    19  
    20  type indVar struct {
    21  	ind   *Value // induction variable
    22  	nxt   *Value // the incremented variable
    23  	min   *Value // minimum value, inclusive/exclusive depends on flags
    24  	max   *Value // maximum value, inclusive/exclusive depends on flags
    25  	entry *Block // the block where the edge from the succeeded comparison of the induction variable goes to, means when the bound check has passed.
    26  	step  int64  // it will always be positive.
    27  	flags indVarFlags
    28  	// Invariant: for all blocks dominated by entry:
    29  	//	min <= ind <  max    [if flags == 0]
    30  	//	min <  ind <  max    [if flags == indVarMinExc]
    31  	//	min <= ind <= max    [if flags == indVarMaxInc]
    32  	//	min <  ind <= max    [if flags == indVarMinExc|indVarMaxInc]
    33  }
    34  
    35  // parseIndVar checks whether the SSA value passed as argument is a valid induction
    36  // variable, and, if so, extracts:
    37  //   - the minimum bound
    38  //   - the increment value
    39  //   - the "next" value (SSA value that is Phi'd into the induction variable every loop)
    40  //   - the header's edge returning from the body
    41  //
    42  // Currently, we detect induction variables that match (Phi min nxt),
    43  // with nxt being (Add inc ind).
    44  // If it can't parse the induction variable correctly, it returns (nil, nil, nil).
    45  func parseIndVar(ind *Value) (min, inc, nxt *Value, loopReturn Edge) {
    46  	if ind.Op != OpPhi {
    47  		return
    48  	}
    49  
    50  	if n := ind.Args[0]; (n.Op == OpAdd64 || n.Op == OpAdd32 || n.Op == OpAdd16 || n.Op == OpAdd8) && (n.Args[0] == ind || n.Args[1] == ind) {
    51  		min, nxt, loopReturn = ind.Args[1], n, ind.Block.Preds[0]
    52  	} else if n := ind.Args[1]; (n.Op == OpAdd64 || n.Op == OpAdd32 || n.Op == OpAdd16 || n.Op == OpAdd8) && (n.Args[0] == ind || n.Args[1] == ind) {
    53  		min, nxt, loopReturn = ind.Args[0], n, ind.Block.Preds[1]
    54  	} else {
    55  		// Not a recognized induction variable.
    56  		return
    57  	}
    58  
    59  	if nxt.Args[0] == ind { // nxt = ind + inc
    60  		inc = nxt.Args[1]
    61  	} else if nxt.Args[1] == ind { // nxt = inc + ind
    62  		inc = nxt.Args[0]
    63  	} else {
    64  		panic("unreachable") // one of the cases must be true from the above.
    65  	}
    66  
    67  	return
    68  }
    69  
    70  // findIndVar finds induction variables in a function.
    71  //
    72  // Look for variables and blocks that satisfy the following
    73  //
    74  //	 loop:
    75  //	   ind = (Phi min nxt),
    76  //	   if ind < max
    77  //	     then goto enter_loop
    78  //	     else goto exit_loop
    79  //
    80  //	   enter_loop:
    81  //		do something
    82  //	      nxt = inc + ind
    83  //		goto loop
    84  //
    85  //	 exit_loop:
    86  //
    87  // We may have more than one induction variables, the loop in the go
    88  // source code may looks like this:
    89  //
    90  //	for i >= 0 && j >= 0 {
    91  //		// use i and j
    92  //		i--
    93  //		j--
    94  //	}
    95  //
    96  // So, also look for variables and blocks that satisfy the following
    97  //
    98  //	loop:
    99  //	  i = (Phi maxi nxti)
   100  //	  j = (Phi maxj nxtj)
   101  //	  if i >= mini
   102  //	    then goto check_j
   103  //	    else goto exit_loop
   104  //
   105  //	check_j:
   106  //	  if j >= minj
   107  //	    then goto enter_loop
   108  //	    else goto exit_loop
   109  //
   110  //	enter_loop:
   111  //	  do something
   112  //	  nxti = i - di
   113  //	  nxtj = j - dj
   114  //	  goto loop
   115  //
   116  //	exit_loop:
   117  func findIndVar(f *Func) []indVar {
   118  	var iv []indVar
   119  	sdom := f.Sdom()
   120  
   121  nextblock:
   122  	for _, b := range f.Blocks {
   123  		if b.Kind != BlockIf {
   124  			continue
   125  		}
   126  		c := b.Controls[0]
   127  		for idx := range 2 {
   128  			// Check that the control if it either ind </<= limit or limit </<= ind.
   129  			// TODO: Handle unsigned comparisons?
   130  			inclusive := false
   131  			switch c.Op {
   132  			case OpLeq64, OpLeq32, OpLeq16, OpLeq8:
   133  				inclusive = true
   134  			case OpLess64, OpLess32, OpLess16, OpLess8:
   135  			default:
   136  				continue nextblock
   137  			}
   138  
   139  			less := idx == 0
   140  			// induction variable, ending value
   141  			ind, limit := c.Args[idx], c.Args[1-idx]
   142  			// starting value, increment value, next value, loop return edge
   143  			init, inc, nxt, loopReturn := parseIndVar(ind)
   144  			if init == nil {
   145  				continue // this is not an induction variable
   146  			}
   147  
   148  			// This is ind.Block.Preds, not b.Preds. That's a restriction on the loop header,
   149  			// not the comparison block.
   150  			if len(ind.Block.Preds) != 2 {
   151  				continue
   152  			}
   153  
   154  			// Expect the increment to be a nonzero constant.
   155  			if !inc.isGenericIntConst() {
   156  				continue
   157  			}
   158  			step := inc.AuxInt
   159  			if step == 0 {
   160  				continue
   161  			}
   162  			// step == minInt64 cannot be safely negated below, because -step
   163  			// overflows back to minInt64. The later underflow checks need a
   164  			// positive magnitude, so reject this case here.
   165  			if step == minSignedValue(ind.Type) {
   166  				continue
   167  			}
   168  
   169  			// startBody is the edge that eventually returns to the loop header.
   170  			var startBody Edge
   171  			switch {
   172  			case sdom.IsAncestorEq(b.Succs[0].b, loopReturn.b):
   173  				startBody = b.Succs[0]
   174  			case sdom.IsAncestorEq(b.Succs[1].b, loopReturn.b):
   175  				// if x { goto exit } else { goto entry } is identical to if !x { goto entry } else { goto exit }
   176  				startBody = b.Succs[1]
   177  				less = !less
   178  				inclusive = !inclusive
   179  			default:
   180  				continue
   181  			}
   182  
   183  			// Increment sign must match comparison direction.
   184  			// When incrementing, the termination comparison must be ind </<= limit.
   185  			// When decrementing, the termination comparison must be ind >/>= limit.
   186  			// See issue 26116.
   187  			if step > 0 && !less {
   188  				continue
   189  			}
   190  			if step < 0 && less {
   191  				continue
   192  			}
   193  
   194  			// Up to now we extracted the induction variable (ind),
   195  			// the increment delta (inc), the temporary sum (nxt),
   196  			// the initial value (init) and the limiting value (limit).
   197  			//
   198  			// We also know that ind has the form (Phi init nxt) where
   199  			// nxt is (Add inc nxt) which means: 1) inc dominates nxt
   200  			// and 2) there is a loop starting at inc and containing nxt.
   201  			//
   202  			// We need to prove that the induction variable is incremented
   203  			// only when it's smaller than the limiting value.
   204  			// Two conditions must happen listed below to accept ind
   205  			// as an induction variable.
   206  
   207  			// First condition: the entry block has a single predecessor.
   208  			// The entry now means the in-loop edge where the induction variable
   209  			// comparison succeeded. Its predecessor is not necessarily the header
   210  			// block. This implies that b.Succs[0] is reached iff ind < limit.
   211  			if len(startBody.b.Preds) != 1 {
   212  				// the other successor must exit the loop.
   213  				continue
   214  			}
   215  
   216  			// Second condition: startBody.b dominates nxt so that
   217  			// nxt is computed when inc < limit.
   218  			if !sdom.IsAncestorEq(startBody.b, nxt.Block) {
   219  				// inc+ind can only be reached through the branch that confirmed the
   220  				// induction variable is in bounds.
   221  				continue
   222  			}
   223  
   224  			// Check for overflow/underflow. We need to make sure that inc never causes
   225  			// the induction variable to wrap around.
   226  			// We use a function wrapper here for easy return true / return false / keep going logic.
   227  			// This function returns true if the increment will never overflow/underflow.
   228  			ok := func() bool {
   229  				if step > 0 {
   230  					if limit.isGenericIntConst() {
   231  						// Figure out the actual largest value.
   232  						v := limit.AuxInt
   233  						if !inclusive {
   234  							if v == minSignedValue(limit.Type) {
   235  								return false // < minint is never satisfiable.
   236  							}
   237  							v--
   238  						}
   239  						if init.isGenericIntConst() {
   240  							// Use stride to compute a better lower limit.
   241  							if init.AuxInt > v {
   242  								return false
   243  							}
   244  							// TODO(1.27): investigate passing a smaller-magnitude overflow limit to addU
   245  							// for addWillOverflow.
   246  							v = addU(init.AuxInt, diff(v, init.AuxInt)/uint64(step)*uint64(step))
   247  						}
   248  						if addWillOverflow(v, step, maxSignedValue(ind.Type)) {
   249  							return false
   250  						}
   251  						if inclusive && v != limit.AuxInt || !inclusive && v+1 != limit.AuxInt {
   252  							// We know a better limit than the programmer did. Use our limit instead.
   253  							limit = f.constVal(limit.Op, limit.Type, v, true)
   254  							inclusive = true
   255  						}
   256  						return true
   257  					}
   258  					if step == 1 && !inclusive {
   259  						// Can't overflow because maxint is never a possible value.
   260  						return true
   261  					}
   262  					// If the limit is not a constant, check to see if it is a
   263  					// negative offset from a known non-negative value.
   264  					knn, k := findKNN(limit)
   265  					if knn == nil || k < 0 {
   266  						return false
   267  					}
   268  					// limit == (something nonnegative) - k. That subtraction can't underflow, so
   269  					// we can trust it.
   270  					if inclusive {
   271  						// ind <= knn - k cannot overflow if step is at most k
   272  						return step <= k
   273  					}
   274  					// ind < knn - k cannot overflow if step is at most k+1
   275  					return step <= k+1 && k != maxSignedValue(limit.Type)
   276  
   277  					// TODO: other unrolling idioms
   278  					// for i := 0; i < KNN - KNN % k ; i += k
   279  					// for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2
   280  					// for i := 0; i < KNN&(-k) ; i += k // k a power of 2
   281  				} else { // step < 0
   282  					if limit.isGenericIntConst() {
   283  						// Figure out the actual smallest value.
   284  						v := limit.AuxInt
   285  						if !inclusive {
   286  							if v == maxSignedValue(limit.Type) {
   287  								return false // > maxint is never satisfiable.
   288  							}
   289  							v++
   290  						}
   291  						if init.isGenericIntConst() {
   292  							// Use stride to compute a better lower limit.
   293  							if init.AuxInt < v {
   294  								return false
   295  							}
   296  							// TODO(1.27): investigate passing a smaller-magnitude underflow limit to subU
   297  							// for subWillUnderflow.
   298  							v = subU(init.AuxInt, diff(init.AuxInt, v)/uint64(-step)*uint64(-step))
   299  						}
   300  						if subWillUnderflow(v, -step, minSignedValue(ind.Type)) {
   301  							return false
   302  						}
   303  						if inclusive && v != limit.AuxInt || !inclusive && v-1 != limit.AuxInt {
   304  							// We know a better limit than the programmer did. Use our limit instead.
   305  							limit = f.constVal(limit.Op, limit.Type, v, true)
   306  							inclusive = true
   307  						}
   308  						return true
   309  					}
   310  					if step == -1 && !inclusive {
   311  						// Can't underflow because minint is never a possible value.
   312  						return true
   313  					}
   314  				}
   315  				return false
   316  			}
   317  
   318  			if ok() {
   319  				flags := indVarFlags(0)
   320  				var min, max *Value
   321  				if step > 0 {
   322  					min = init
   323  					max = limit
   324  					if inclusive {
   325  						flags |= indVarMaxInc
   326  					}
   327  				} else {
   328  					min = limit
   329  					max = init
   330  					flags |= indVarMaxInc
   331  					if !inclusive {
   332  						flags |= indVarMinExc
   333  					}
   334  					step = -step
   335  				}
   336  				if f.pass.debug >= 1 {
   337  					printIndVar(b, ind, min, max, step, flags)
   338  				}
   339  
   340  				iv = append(iv, indVar{
   341  					ind: ind,
   342  					nxt: nxt,
   343  					min: min,
   344  					max: max,
   345  					// This is startBody.b, where startBody is the edge from the comparison for the
   346  					// induction variable, not necessarily the in-loop edge from the loop header.
   347  					// Induction variable bounds are not valid in the loop before this edge.
   348  					entry: startBody.b,
   349  					step:  step,
   350  					flags: flags,
   351  				})
   352  				b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
   353  			}
   354  		}
   355  	}
   356  
   357  	return iv
   358  }
   359  
   360  // subWillUnderflow checks if x - y underflows the min value.
   361  // y must be positive.
   362  func subWillUnderflow(x, y int64, min int64) bool {
   363  	if y < 0 {
   364  		base.Fatalf("expecting positive value")
   365  	}
   366  	return x < min+y
   367  }
   368  
   369  // addWillOverflow checks if x + y overflows the max value.
   370  // y must be positive.
   371  func addWillOverflow(x, y int64, max int64) bool {
   372  	if y < 0 {
   373  		base.Fatalf("expecting positive value")
   374  	}
   375  	return x > max-y
   376  }
   377  
   378  // diff returns x-y as a uint64. Requires x>=y.
   379  func diff(x, y int64) uint64 {
   380  	if x < y {
   381  		base.Fatalf("diff %d - %d underflowed", x, y)
   382  	}
   383  	return uint64(x - y)
   384  }
   385  
   386  // addU returns x+y. Requires that x+y does not overflow an int64.
   387  func addU(x int64, y uint64) int64 {
   388  	if y >= 1<<63 {
   389  		if x >= 0 {
   390  			base.Fatalf("addU overflowed %d + %d", x, y)
   391  		}
   392  		x += 1<<63 - 1
   393  		x += 1
   394  		y -= 1 << 63
   395  	}
   396  	// TODO(1.27): investigate passing a smaller-magnitude overflow limit in here.
   397  	if addWillOverflow(x, int64(y), maxSignedValue(types.Types[types.TINT64])) {
   398  		base.Fatalf("addU overflowed %d + %d", x, y)
   399  	}
   400  	return x + int64(y)
   401  }
   402  
   403  // subU returns x-y. Requires that x-y does not underflow an int64.
   404  func subU(x int64, y uint64) int64 {
   405  	if y >= 1<<63 {
   406  		if x < 0 {
   407  			base.Fatalf("subU underflowed %d - %d", x, y)
   408  		}
   409  		x -= 1<<63 - 1
   410  		x -= 1
   411  		y -= 1 << 63
   412  	}
   413  	// TODO(1.27): investigate passing a smaller-magnitude underflow limit in here.
   414  	if subWillUnderflow(x, int64(y), minSignedValue(types.Types[types.TINT64])) {
   415  		base.Fatalf("subU underflowed %d - %d", x, y)
   416  	}
   417  	return x - int64(y)
   418  }
   419  
   420  // if v is known to be x - c, where x is known to be nonnegative and c is a
   421  // constant, return x, c. Otherwise return nil, 0.
   422  func findKNN(v *Value) (*Value, int64) {
   423  	var x, y *Value
   424  	x = v
   425  	switch v.Op {
   426  	case OpSub64, OpSub32, OpSub16, OpSub8:
   427  		x = v.Args[0]
   428  		y = v.Args[1]
   429  
   430  	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
   431  		x = v.Args[0]
   432  		y = v.Args[1]
   433  		if x.isGenericIntConst() {
   434  			x, y = y, x
   435  		}
   436  	}
   437  	switch x.Op {
   438  	case OpSliceLen, OpStringLen, OpSliceCap:
   439  	default:
   440  		return nil, 0
   441  	}
   442  	if y == nil {
   443  		return x, 0
   444  	}
   445  	if !y.isGenericIntConst() {
   446  		return nil, 0
   447  	}
   448  	if v.Op == OpAdd64 || v.Op == OpAdd32 || v.Op == OpAdd16 || v.Op == OpAdd8 {
   449  		return x, -y.AuxInt
   450  	}
   451  	return x, y.AuxInt
   452  }
   453  
   454  func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
   455  	mb1, mb2 := "[", "]"
   456  	if flags&indVarMinExc != 0 {
   457  		mb1 = "("
   458  	}
   459  	if flags&indVarMaxInc == 0 {
   460  		mb2 = ")"
   461  	}
   462  
   463  	mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
   464  	if !min.isGenericIntConst() {
   465  		if b.Func.pass.debug >= 2 {
   466  			mlim1 = fmt.Sprint(min)
   467  		} else {
   468  			mlim1 = "?"
   469  		}
   470  	}
   471  	if !max.isGenericIntConst() {
   472  		if b.Func.pass.debug >= 2 {
   473  			mlim2 = fmt.Sprint(max)
   474  		} else {
   475  			mlim2 = "?"
   476  		}
   477  	}
   478  	extra := ""
   479  	if b.Func.pass.debug >= 2 {
   480  		extra = fmt.Sprintf(" (%s)", i)
   481  	}
   482  	b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
   483  }
   484  
   485  func minSignedValue(t *types.Type) int64 {
   486  	return -1 << (t.Size()*8 - 1)
   487  }
   488  
   489  func maxSignedValue(t *types.Type) int64 {
   490  	return 1<<((t.Size()*8)-1) - 1
   491  }
   492
View as plain text