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  	indVarCountDown                         // if set the iteration starts at max and count towards min (default: min towards max)
    19  )
    20  
    21  type indVar struct {
    22  	ind   *Value // induction variable
    23  	nxt   *Value // the incremented variable
    24  	min   *Value // minimum value, inclusive/exclusive depends on flags
    25  	max   *Value // maximum value, inclusive/exclusive depends on flags
    26  	entry *Block // entry block in the loop.
    27  	flags indVarFlags
    28  	// Invariant: for all blocks strictly 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  func findIndVar(f *Func) []indVar {
    87  	var iv []indVar
    88  	sdom := f.Sdom()
    89  
    90  	for _, b := range f.Blocks {
    91  		if b.Kind != BlockIf || len(b.Preds) != 2 {
    92  			continue
    93  		}
    94  
    95  		var ind *Value   // induction variable
    96  		var init *Value  // starting value
    97  		var limit *Value // ending value
    98  
    99  		// Check that the control if it either ind </<= limit or limit </<= ind.
   100  		// TODO: Handle unsigned comparisons?
   101  		c := b.Controls[0]
   102  		inclusive := false
   103  		switch c.Op {
   104  		case OpLeq64, OpLeq32, OpLeq16, OpLeq8:
   105  			inclusive = true
   106  			fallthrough
   107  		case OpLess64, OpLess32, OpLess16, OpLess8:
   108  			ind, limit = c.Args[0], c.Args[1]
   109  		default:
   110  			continue
   111  		}
   112  
   113  		// See if this is really an induction variable
   114  		less := true
   115  		init, inc, nxt, loopReturn := parseIndVar(ind)
   116  		if init == nil {
   117  			// We failed to parse the induction variable. Before punting, we want to check
   118  			// whether the control op was written with the induction variable on the RHS
   119  			// instead of the LHS. This happens for the downwards case, like:
   120  			//     for i := len(n)-1; i >= 0; i--
   121  			init, inc, nxt, loopReturn = parseIndVar(limit)
   122  			if init == nil {
   123  				// No recognized induction variable on either operand
   124  				continue
   125  			}
   126  
   127  			// Ok, the arguments were reversed. Swap them, and remember that we're
   128  			// looking at an ind >/>= loop (so the induction must be decrementing).
   129  			ind, limit = limit, ind
   130  			less = false
   131  		}
   132  
   133  		if ind.Block != b {
   134  			// TODO: Could be extended to include disjointed loop headers.
   135  			// I don't think this is causing missed optimizations in real world code often.
   136  			// See https://go.dev/issue/63955
   137  			continue
   138  		}
   139  
   140  		// Expect the increment to be a nonzero constant.
   141  		if !inc.isGenericIntConst() {
   142  			continue
   143  		}
   144  		step := inc.AuxInt
   145  		if step == 0 {
   146  			continue
   147  		}
   148  		// step == minInt64 cannot be safely negated below, because -step
   149  		// overflows back to minInt64. The later underflow checks need a
   150  		// positive magnitude, so reject this case here.
   151  		if step == minSignedValue(ind.Type) {
   152  			continue
   153  		}
   154  
   155  		// startBody is the edge that eventually returns to the loop header.
   156  		var startBody Edge
   157  		switch {
   158  		case sdom.IsAncestorEq(b.Succs[0].b, loopReturn.b):
   159  			startBody = b.Succs[0]
   160  		case sdom.IsAncestorEq(b.Succs[1].b, loopReturn.b):
   161  			// if x { goto exit } else { goto entry } is identical to if !x { goto entry } else { goto exit }
   162  			startBody = b.Succs[1]
   163  			less = !less
   164  			inclusive = !inclusive
   165  		default:
   166  			continue
   167  		}
   168  
   169  		// Increment sign must match comparison direction.
   170  		// When incrementing, the termination comparison must be ind </<= limit.
   171  		// When decrementing, the termination comparison must be ind >/>= limit.
   172  		// See issue 26116.
   173  		if step > 0 && !less {
   174  			continue
   175  		}
   176  		if step < 0 && less {
   177  			continue
   178  		}
   179  
   180  		// Up to now we extracted the induction variable (ind),
   181  		// the increment delta (inc), the temporary sum (nxt),
   182  		// the initial value (init) and the limiting value (limit).
   183  		//
   184  		// We also know that ind has the form (Phi init nxt) where
   185  		// nxt is (Add inc nxt) which means: 1) inc dominates nxt
   186  		// and 2) there is a loop starting at inc and containing nxt.
   187  		//
   188  		// We need to prove that the induction variable is incremented
   189  		// only when it's smaller than the limiting value.
   190  		// Two conditions must happen listed below to accept ind
   191  		// as an induction variable.
   192  
   193  		// First condition: loop entry has a single predecessor, which
   194  		// is the header block.  This implies that b.Succs[0] is
   195  		// reached iff ind < limit.
   196  		if len(startBody.b.Preds) != 1 {
   197  			// the other successor must exit the loop.
   198  			continue
   199  		}
   200  
   201  		// Second condition: startBody.b dominates nxt so that
   202  		// nxt is computed when inc < limit.
   203  		if !sdom.IsAncestorEq(startBody.b, nxt.Block) {
   204  			// inc+ind can only be reached through the branch that enters the loop.
   205  			continue
   206  		}
   207  
   208  		// Check for overflow/underflow. We need to make sure that inc never causes
   209  		// the induction variable to wrap around.
   210  		// We use a function wrapper here for easy return true / return false / keep going logic.
   211  		// This function returns true if the increment will never overflow/underflow.
   212  		ok := func() bool {
   213  			if step > 0 {
   214  				if limit.isGenericIntConst() {
   215  					// Figure out the actual largest value.
   216  					v := limit.AuxInt
   217  					if !inclusive {
   218  						if v == minSignedValue(limit.Type) {
   219  							return false // < minint is never satisfiable.
   220  						}
   221  						v--
   222  					}
   223  					if init.isGenericIntConst() {
   224  						// Use stride to compute a better lower limit.
   225  						if init.AuxInt > v {
   226  							return false
   227  						}
   228  						// TODO(1.27): investigate passing a smaller-magnitude overflow limit to addU
   229  						// for addWillOverflow.
   230  						v = addU(init.AuxInt, diff(v, init.AuxInt)/uint64(step)*uint64(step))
   231  					}
   232  					if addWillOverflow(v, step, maxSignedValue(ind.Type)) {
   233  						return false
   234  					}
   235  					if inclusive && v != limit.AuxInt || !inclusive && v+1 != limit.AuxInt {
   236  						// We know a better limit than the programmer did. Use our limit instead.
   237  						limit = f.constVal(limit.Op, limit.Type, v, true)
   238  						inclusive = true
   239  					}
   240  					return true
   241  				}
   242  				if step == 1 && !inclusive {
   243  					// Can't overflow because maxint is never a possible value.
   244  					return true
   245  				}
   246  				// If the limit is not a constant, check to see if it is a
   247  				// negative offset from a known non-negative value.
   248  				knn, k := findKNN(limit)
   249  				if knn == nil || k < 0 {
   250  					return false
   251  				}
   252  				// limit == (something nonnegative) - k. That subtraction can't underflow, so
   253  				// we can trust it.
   254  				if inclusive {
   255  					// ind <= knn - k cannot overflow if step is at most k
   256  					return step <= k
   257  				}
   258  				// ind < knn - k cannot overflow if step is at most k+1
   259  				return step <= k+1 && k != maxSignedValue(limit.Type)
   260  			} else { // step < 0
   261  				if limit.isGenericIntConst() {
   262  					// Figure out the actual smallest value.
   263  					v := limit.AuxInt
   264  					if !inclusive {
   265  						if v == maxSignedValue(limit.Type) {
   266  							return false // > maxint is never satisfiable.
   267  						}
   268  						v++
   269  					}
   270  					if init.isGenericIntConst() {
   271  						// Use stride to compute a better lower limit.
   272  						if init.AuxInt < v {
   273  							return false
   274  						}
   275  						// TODO(1.27): investigate passing a smaller-magnitude underflow limit to subU
   276  						// for subWillUnderflow.
   277  						v = subU(init.AuxInt, diff(init.AuxInt, v)/uint64(-step)*uint64(-step))
   278  					}
   279  					if subWillUnderflow(v, -step, minSignedValue(ind.Type)) {
   280  						return false
   281  					}
   282  					if inclusive && v != limit.AuxInt || !inclusive && v-1 != limit.AuxInt {
   283  						// We know a better limit than the programmer did. Use our limit instead.
   284  						limit = f.constVal(limit.Op, limit.Type, v, true)
   285  						inclusive = true
   286  					}
   287  					return true
   288  				}
   289  				if step == -1 && !inclusive {
   290  					// Can't underflow because minint is never a possible value.
   291  					return true
   292  				}
   293  			}
   294  			return false
   295  
   296  		}
   297  
   298  		if ok() {
   299  			flags := indVarFlags(0)
   300  			var min, max *Value
   301  			if step > 0 {
   302  				min = init
   303  				max = limit
   304  				if inclusive {
   305  					flags |= indVarMaxInc
   306  				}
   307  			} else {
   308  				min = limit
   309  				max = init
   310  				flags |= indVarMaxInc
   311  				if !inclusive {
   312  					flags |= indVarMinExc
   313  				}
   314  				flags |= indVarCountDown
   315  				step = -step
   316  			}
   317  			if f.pass.debug >= 1 {
   318  				printIndVar(b, ind, min, max, step, flags)
   319  			}
   320  
   321  			iv = append(iv, indVar{
   322  				ind:   ind,
   323  				nxt:   nxt,
   324  				min:   min,
   325  				max:   max,
   326  				entry: startBody.b,
   327  				flags: flags,
   328  			})
   329  			b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
   330  		}
   331  
   332  		// TODO: other unrolling idioms
   333  		// for i := 0; i < KNN - KNN % k ; i += k
   334  		// for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2
   335  		// for i := 0; i < KNN&(-k) ; i += k // k a power of 2
   336  	}
   337  
   338  	return iv
   339  }
   340  
   341  // subWillUnderflow checks if x - y underflows the min value.
   342  // y must be positive.
   343  func subWillUnderflow(x, y int64, min int64) bool {
   344  	if y < 0 {
   345  		base.Fatalf("expecting positive value")
   346  	}
   347  	return x < min+y
   348  }
   349  
   350  // addWillOverflow checks if x + y overflows the max value.
   351  // y must be positive.
   352  func addWillOverflow(x, y int64, max int64) bool {
   353  	if y < 0 {
   354  		base.Fatalf("expecting positive value")
   355  	}
   356  	return x > max-y
   357  }
   358  
   359  // diff returns x-y as a uint64. Requires x>=y.
   360  func diff(x, y int64) uint64 {
   361  	if x < y {
   362  		base.Fatalf("diff %d - %d underflowed", x, y)
   363  	}
   364  	return uint64(x - y)
   365  }
   366  
   367  // addU returns x+y. Requires that x+y does not overflow an int64.
   368  func addU(x int64, y uint64) int64 {
   369  	if y >= 1<<63 {
   370  		if x >= 0 {
   371  			base.Fatalf("addU overflowed %d + %d", x, y)
   372  		}
   373  		x += 1<<63 - 1
   374  		x += 1
   375  		y -= 1 << 63
   376  	}
   377  	// TODO(1.27): investigate passing a smaller-magnitude overflow limit in here.
   378  	if addWillOverflow(x, int64(y), maxSignedValue(types.Types[types.TINT64])) {
   379  		base.Fatalf("addU overflowed %d + %d", x, y)
   380  	}
   381  	return x + int64(y)
   382  }
   383  
   384  // subU returns x-y. Requires that x-y does not underflow an int64.
   385  func subU(x int64, y uint64) int64 {
   386  	if y >= 1<<63 {
   387  		if x < 0 {
   388  			base.Fatalf("subU underflowed %d - %d", x, y)
   389  		}
   390  		x -= 1<<63 - 1
   391  		x -= 1
   392  		y -= 1 << 63
   393  	}
   394  	// TODO(1.27): investigate passing a smaller-magnitude underflow limit in here.
   395  	if subWillUnderflow(x, int64(y), minSignedValue(types.Types[types.TINT64])) {
   396  		base.Fatalf("subU underflowed %d - %d", x, y)
   397  	}
   398  	return x - int64(y)
   399  }
   400  
   401  // if v is known to be x - c, where x is known to be nonnegative and c is a
   402  // constant, return x, c. Otherwise return nil, 0.
   403  func findKNN(v *Value) (*Value, int64) {
   404  	var x, y *Value
   405  	x = v
   406  	switch v.Op {
   407  	case OpSub64, OpSub32, OpSub16, OpSub8:
   408  		x = v.Args[0]
   409  		y = v.Args[1]
   410  
   411  	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
   412  		x = v.Args[0]
   413  		y = v.Args[1]
   414  		if x.isGenericIntConst() {
   415  			x, y = y, x
   416  		}
   417  	}
   418  	switch x.Op {
   419  	case OpSliceLen, OpStringLen, OpSliceCap:
   420  	default:
   421  		return nil, 0
   422  	}
   423  	if y == nil {
   424  		return x, 0
   425  	}
   426  	if !y.isGenericIntConst() {
   427  		return nil, 0
   428  	}
   429  	if v.Op == OpAdd64 || v.Op == OpAdd32 || v.Op == OpAdd16 || v.Op == OpAdd8 {
   430  		return x, -y.AuxInt
   431  	}
   432  	return x, y.AuxInt
   433  }
   434  
   435  func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
   436  	mb1, mb2 := "[", "]"
   437  	if flags&indVarMinExc != 0 {
   438  		mb1 = "("
   439  	}
   440  	if flags&indVarMaxInc == 0 {
   441  		mb2 = ")"
   442  	}
   443  
   444  	mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
   445  	if !min.isGenericIntConst() {
   446  		if b.Func.pass.debug >= 2 {
   447  			mlim1 = fmt.Sprint(min)
   448  		} else {
   449  			mlim1 = "?"
   450  		}
   451  	}
   452  	if !max.isGenericIntConst() {
   453  		if b.Func.pass.debug >= 2 {
   454  			mlim2 = fmt.Sprint(max)
   455  		} else {
   456  			mlim2 = "?"
   457  		}
   458  	}
   459  	extra := ""
   460  	if b.Func.pass.debug >= 2 {
   461  		extra = fmt.Sprintf(" (%s)", i)
   462  	}
   463  	b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
   464  }
   465  
   466  func minSignedValue(t *types.Type) int64 {
   467  	return -1 << (t.Size()*8 - 1)
   468  }
   469  
   470  func maxSignedValue(t *types.Type) int64 {
   471  	return 1<<((t.Size()*8)-1) - 1
   472  }
   473
View as plain text