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