src/cmd/compile/internal/ssa/loopbce.go - go.git - Git at Google

 // Copyright 2018 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 package ssa

 import (
 	"cmd/compile/internal/base"
 	"cmd/compile/internal/types"
 	"fmt"
 )

 type indVarFlags uint8

 const (
 	indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive)
 	indVarMaxInc                         // maximum value is inclusive (default: exclusive)
 )

 type indVar struct {
 	ind   *Value // induction variable
 	nxt   *Value // the incremented variable
 	min   *Value // minimum value, inclusive/exclusive depends on flags
 	max   *Value // maximum value, inclusive/exclusive depends on flags
 	entry *Block // the block where the edge from the succeeded comparison of the induction variable goes to, means when the bound check has passed.
 	step  int64  // it will always be positive.
 	flags indVarFlags
 	// Invariant: for all blocks dominated by entry:
 	//	min <= ind <  max    [if flags == 0]
 	//	min <  ind <  max    [if flags == indVarMinExc]
 	//	min <= ind <= max    [if flags == indVarMaxInc]
 	//	min <  ind <= max    [if flags == indVarMinExc|indVarMaxInc]
 }

 // parseIndVar checks whether the SSA value passed as argument is a valid induction
 // variable, and, if so, extracts:
 //   - the minimum bound
 //   - the increment value
 //   - the "next" value (SSA value that is Phi'd into the induction variable every loop)
 //   - the header's edge returning from the body
 //
 // Currently, we detect induction variables that match (Phi min nxt),
 // with nxt being (Add inc ind).
 // If it can't parse the induction variable correctly, it returns (nil, nil, nil).
 func parseIndVar(ind *Value) (min, inc, nxt *Value, loopReturn Edge) {
 	if ind.Op != OpPhi {
 		return
 	}

 	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) {
 		min, nxt, loopReturn = ind.Args[1], n, ind.Block.Preds[0]
 	} 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) {
 		min, nxt, loopReturn = ind.Args[0], n, ind.Block.Preds[1]
 	} else {
 		// Not a recognized induction variable.
 		return
 	}

 	if nxt.Args[0] == ind { // nxt = ind + inc
 		inc = nxt.Args[1]
 	} else if nxt.Args[1] == ind { // nxt = inc + ind
 		inc = nxt.Args[0]
 	} else {
 		panic("unreachable") // one of the cases must be true from the above.
 	}

 	return
 }

 // findIndVar finds induction variables in a function.
 //
 // Look for variables and blocks that satisfy the following
 //
 //	 loop:
 //	   ind = (Phi min nxt),
 //	   if ind < max
 //	     then goto enter_loop
 //	     else goto exit_loop
 //
 //	   enter_loop:
 //		do something
 //	      nxt = inc + ind
 //		goto loop
 //
 //	 exit_loop:
 //
 // We may have more than one induction variables, the loop in the go
 // source code may looks like this:
 //
 //	for i >= 0 && j >= 0 {
 //		// use i and j
 //		i--
 //		j--
 //	}
 //
 // So, also look for variables and blocks that satisfy the following
 //
 //	loop:
 //	  i = (Phi maxi nxti)
 //	  j = (Phi maxj nxtj)
 //	  if i >= mini
 //	    then goto check_j
 //	    else goto exit_loop
 //
 //	check_j:
 //	  if j >= minj
 //	    then goto enter_loop
 //	    else goto exit_loop
 //
 //	enter_loop:
 //	  do something
 //	  nxti = i - di
 //	  nxtj = j - dj
 //	  goto loop
 //
 //	exit_loop:
 func findIndVar(f *Func) []indVar {
 	var iv []indVar
 	sdom := f.Sdom()

 nextblock:
 	for _, b := range f.Blocks {
 		if b.Kind != BlockIf {
 			continue
 		}
 		c := b.Controls[0]
 		for idx := range 2 {
 			// Check that the control if it either ind </<= limit or limit </<= ind.
 			// TODO: Handle unsigned comparisons?
 			inclusive := false
 			switch c.Op {
 			case OpLeq64, OpLeq32, OpLeq16, OpLeq8:
 				inclusive = true
 			case OpLess64, OpLess32, OpLess16, OpLess8:
 			default:
 				continue nextblock
 			}

 			less := idx == 0
 			// induction variable, ending value
 			ind, limit := c.Args[idx], c.Args[1-idx]
 			// starting value, increment value, next value, loop return edge
 			init, inc, nxt, loopReturn := parseIndVar(ind)
 			if init == nil {
 				continue // this is not an induction variable
 			}

 			// This is ind.Block.Preds, not b.Preds. That's a restriction on the loop header,
 			// not the comparison block.
 			if len(ind.Block.Preds) != 2 {
 				continue
 			}

 			// Expect the increment to be a nonzero constant.
 			if !inc.isGenericIntConst() {
 				continue
 			}
 			step := inc.AuxInt
 			if step == 0 {
 				continue
 			}
 			// step == minInt64 cannot be safely negated below, because -step
 			// overflows back to minInt64. The later underflow checks need a
 			// positive magnitude, so reject this case here.
 			if step == minSignedValue(ind.Type) {
 				continue
 			}

 			// startBody is the edge that eventually returns to the loop header.
 			var startBody Edge
 			switch {
 			case sdom.IsAncestorEq(b.Succs[0].b, loopReturn.b):
 				startBody = b.Succs[0]
 			case sdom.IsAncestorEq(b.Succs[1].b, loopReturn.b):
 				// if x { goto exit } else { goto entry } is identical to if !x { goto entry } else { goto exit }
 				startBody = b.Succs[1]
 				less = !less
 				inclusive = !inclusive
 			default:
 				continue
 			}

 			// Increment sign must match comparison direction.
 			// When incrementing, the termination comparison must be ind </<= limit.
 			// When decrementing, the termination comparison must be ind >/>= limit.
 			// See issue 26116.
 			if step > 0 && !less {
 				continue
 			}
 			if step < 0 && less {
 				continue
 			}

 			// Up to now we extracted the induction variable (ind),
 			// the increment delta (inc), the temporary sum (nxt),
 			// the initial value (init) and the limiting value (limit).
 			//
 			// We also know that ind has the form (Phi init nxt) where
 			// nxt is (Add inc nxt) which means: 1) inc dominates nxt
 			// and 2) there is a loop starting at inc and containing nxt.
 			//
 			// We need to prove that the induction variable is incremented
 			// only when it's smaller than the limiting value.
 			// Two conditions must happen listed below to accept ind
 			// as an induction variable.

 			// First condition: the entry block has a single predecessor.
 			// The entry now means the in-loop edge where the induction variable
 			// comparison succeeded. Its predecessor is not necessarily the header
 			// block. This implies that b.Succs[0] is reached iff ind < limit.
 			if len(startBody.b.Preds) != 1 {
 				// the other successor must exit the loop.
 				continue
 			}

 			// Second condition: startBody.b dominates nxt so that
 			// nxt is computed when inc < limit.
 			if !sdom.IsAncestorEq(startBody.b, nxt.Block) {
 				// inc+ind can only be reached through the branch that confirmed the
 				// induction variable is in bounds.
 				continue
 			}

 			// Check for overflow/underflow. We need to make sure that inc never causes
 			// the induction variable to wrap around.
 			// We use a function wrapper here for easy return true / return false / keep going logic.
 			// This function returns true if the increment will never overflow/underflow.
 			ok := func() bool {
 				if step > 0 {
 					if limit.isGenericIntConst() {
 						// Figure out the actual largest value.
 						v := limit.AuxInt
 						if !inclusive {
 							if v == minSignedValue(limit.Type) {
 								return false // < minint is never satisfiable.
 							}
 							v--
 						}
 						if init.isGenericIntConst() {
 							// Use stride to compute a better lower limit.
 							if init.AuxInt > v {
 								return false
 							}
 							// TODO(1.27): investigate passing a smaller-magnitude overflow limit to addU
 							// for addWillOverflow.
 							v = addU(init.AuxInt, diff(v, init.AuxInt)/uint64(step)*uint64(step))
 						}
 						if addWillOverflow(v, step, maxSignedValue(ind.Type)) {
 							return false
 						}
 						if inclusive && v != limit.AuxInt || !inclusive && v+1 != limit.AuxInt {
 							// We know a better limit than the programmer did. Use our limit instead.
 							limit = f.constVal(limit.Op, limit.Type, v, true)
 							inclusive = true
 						}
 						return true
 					}
 					if step == 1 && !inclusive {
 						// Can't overflow because maxint is never a possible value.
 						return true
 					}
 					// If the limit is not a constant, check to see if it is a
 					// negative offset from a known non-negative value.
 					knn, k := findKNN(limit)
 					if knn == nil || k < 0 {
 						return false
 					}
 					// limit == (something nonnegative) - k. That subtraction can't underflow, so
 					// we can trust it.
 					if inclusive {
 						// ind <= knn - k cannot overflow if step is at most k
 						return step <= k
 					}
 					// ind < knn - k cannot overflow if step is at most k+1
 					return step <= k+1 && k != maxSignedValue(limit.Type)

 					// TODO: other unrolling idioms
 					// for i := 0; i < KNN - KNN % k ; i += k
 					// for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2
 					// for i := 0; i < KNN&(-k) ; i += k // k a power of 2
 				} else { // step < 0
 					if limit.isGenericIntConst() {
 						// Figure out the actual smallest value.
 						v := limit.AuxInt
 						if !inclusive {
 							if v == maxSignedValue(limit.Type) {
 								return false // > maxint is never satisfiable.
 							}
 							v++
 						}
 						if init.isGenericIntConst() {
 							// Use stride to compute a better lower limit.
 							if init.AuxInt < v {
 								return false
 							}
 							// TODO(1.27): investigate passing a smaller-magnitude underflow limit to subU
 							// for subWillUnderflow.
 							v = subU(init.AuxInt, diff(init.AuxInt, v)/uint64(-step)*uint64(-step))
 						}
 						if subWillUnderflow(v, -step, minSignedValue(ind.Type)) {
 							return false
 						}
 						if inclusive && v != limit.AuxInt || !inclusive && v-1 != limit.AuxInt {
 							// We know a better limit than the programmer did. Use our limit instead.
 							limit = f.constVal(limit.Op, limit.Type, v, true)
 							inclusive = true
 						}
 						return true
 					}
 					if step == -1 && !inclusive {
 						// Can't underflow because minint is never a possible value.
 						return true
 					}
 				}
 				return false
 			}

 			if ok() {
 				flags := indVarFlags(0)
 				var min, max *Value
 				if step > 0 {
 					min = init
 					max = limit
 					if inclusive {
 						flags |= indVarMaxInc
 					}
 				} else {
 					min = limit
 					max = init
 					flags |= indVarMaxInc
 					if !inclusive {
 						flags |= indVarMinExc
 					}
 					step = -step
 				}
 				if f.pass.debug >= 1 {
 					printIndVar(b, ind, min, max, step, flags)
 				}

 				iv = append(iv, indVar{
 					ind: ind,
 					nxt: nxt,
 					min: min,
 					max: max,
 					// This is startBody.b, where startBody is the edge from the comparison for the
 					// induction variable, not necessarily the in-loop edge from the loop header.
 					// Induction variable bounds are not valid in the loop before this edge.
 					entry: startBody.b,
 					step:  step,
 					flags: flags,
 				})
 				b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
 			}
 		}
 	}

 	return iv
 }

 // subWillUnderflow checks if x - y underflows the min value.
 // y must be positive.
 func subWillUnderflow(x, y int64, min int64) bool {
 	if y < 0 {
 		base.Fatalf("expecting positive value")
 	}
 	return x < min+y
 }

 // addWillOverflow checks if x + y overflows the max value.
 // y must be positive.
 func addWillOverflow(x, y int64, max int64) bool {
 	if y < 0 {
 		base.Fatalf("expecting positive value")
 	}
 	return x > max-y
 }

 // diff returns x-y as a uint64. Requires x>=y.
 func diff(x, y int64) uint64 {
 	if x < y {
 		base.Fatalf("diff %d - %d underflowed", x, y)
 	}
 	return uint64(x - y)
 }

 // addU returns x+y. Requires that x+y does not overflow an int64.
 func addU(x int64, y uint64) int64 {
 	if y >= 1<<63 {
 		if x >= 0 {
 			base.Fatalf("addU overflowed %d + %d", x, y)
 		}
 		x += 1<<63 - 1
 		x += 1
 		y -= 1 << 63
 	}
 	// TODO(1.27): investigate passing a smaller-magnitude overflow limit in here.
 	if addWillOverflow(x, int64(y), maxSignedValue(types.Types[types.TINT64])) {
 		base.Fatalf("addU overflowed %d + %d", x, y)
 	}
 	return x + int64(y)
 }

 // subU returns x-y. Requires that x-y does not underflow an int64.
 func subU(x int64, y uint64) int64 {
 	if y >= 1<<63 {
 		if x < 0 {
 			base.Fatalf("subU underflowed %d - %d", x, y)
 		}
 		x -= 1<<63 - 1
 		x -= 1
 		y -= 1 << 63
 	}
 	// TODO(1.27): investigate passing a smaller-magnitude underflow limit in here.
 	if subWillUnderflow(x, int64(y), minSignedValue(types.Types[types.TINT64])) {
 		base.Fatalf("subU underflowed %d - %d", x, y)
 	}
 	return x - int64(y)
 }

 // if v is known to be x - c, where x is known to be nonnegative and c is a
 // constant, return x, c. Otherwise return nil, 0.
 func findKNN(v *Value) (*Value, int64) {
 	var x, y *Value
 	x = v
 	switch v.Op {
 	case OpSub64, OpSub32, OpSub16, OpSub8:
 		x = v.Args[0]
 		y = v.Args[1]

 	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
 		x = v.Args[0]
 		y = v.Args[1]
 		if x.isGenericIntConst() {
 			x, y = y, x
 		}
 	}
 	switch x.Op {
 	case OpSliceLen, OpStringLen, OpSliceCap:
 	default:
 		return nil, 0
 	}
 	if y == nil {
 		return x, 0
 	}
 	if !y.isGenericIntConst() {
 		return nil, 0
 	}
 	if v.Op == OpAdd64 || v.Op == OpAdd32 || v.Op == OpAdd16 || v.Op == OpAdd8 {
 		return x, -y.AuxInt
 	}
 	return x, y.AuxInt
 }

 func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
 	mb1, mb2 := "[", "]"
 	if flags&indVarMinExc != 0 {
 		mb1 = "("
 	}
 	if flags&indVarMaxInc == 0 {
 		mb2 = ")"
 	}

 	mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
 	if !min.isGenericIntConst() {
 		if b.Func.pass.debug >= 2 {
 			mlim1 = fmt.Sprint(min)
 		} else {
 			mlim1 = "?"
 		}
 	}
 	if !max.isGenericIntConst() {
 		if b.Func.pass.debug >= 2 {
 			mlim2 = fmt.Sprint(max)
 		} else {
 			mlim2 = "?"
 		}
 	}
 	extra := ""
 	if b.Func.pass.debug >= 2 {
 		extra = fmt.Sprintf(" (%s)", i)
 	}
 	b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
 }

 func minSignedValue(t *types.Type) int64 {
 	return -1 << (t.Size()*8 - 1)
 }

 func maxSignedValue(t *types.Type) int64 {
 	return 1<<((t.Size()*8)-1) - 1
 }
	// Copyright 2018 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	package ssa

	import (
	"cmd/compile/internal/base"
	"cmd/compile/internal/types"
	"fmt"
	)

	type indVarFlags uint8

	const (
	indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive)
	indVarMaxInc // maximum value is inclusive (default: exclusive)
	)

	type indVar struct {
	ind *Value // induction variable
	nxt *Value // the incremented variable
	min *Value // minimum value, inclusive/exclusive depends on flags
	max *Value // maximum value, inclusive/exclusive depends on flags
	entry *Block // the block where the edge from the succeeded comparison of the induction variable goes to, means when the bound check has passed.
	step int64 // it will always be positive.
	flags indVarFlags
	// Invariant: for all blocks dominated by entry:
	// min <= ind < max [if flags == 0]
	// min < ind < max [if flags == indVarMinExc]
	// min <= ind <= max [if flags == indVarMaxInc]
	// min < ind <= max [if flags == indVarMinExc\|indVarMaxInc]
	}

	// parseIndVar checks whether the SSA value passed as argument is a valid induction
	// variable, and, if so, extracts:
	// - the minimum bound
	// - the increment value
	// - the "next" value (SSA value that is Phi'd into the induction variable every loop)
	// - the header's edge returning from the body
	//
	// Currently, we detect induction variables that match (Phi min nxt),
	// with nxt being (Add inc ind).
	// If it can't parse the induction variable correctly, it returns (nil, nil, nil).
	func parseIndVar(ind Value) (min, inc, nxt Value, loopReturn Edge) {
	if ind.Op != OpPhi {
	return
	}

	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) {
	min, nxt, loopReturn = ind.Args[1], n, ind.Block.Preds[0]
	} 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) {
	min, nxt, loopReturn = ind.Args[0], n, ind.Block.Preds[1]
	} else {
	// Not a recognized induction variable.
	return
	}

	if nxt.Args[0] == ind { // nxt = ind + inc
	inc = nxt.Args[1]
	} else if nxt.Args[1] == ind { // nxt = inc + ind
	inc = nxt.Args[0]
	} else {
	panic("unreachable") // one of the cases must be true from the above.
	}

	return
	}

	// findIndVar finds induction variables in a function.
	//
	// Look for variables and blocks that satisfy the following
	//
	// loop:
	// ind = (Phi min nxt),
	// if ind < max
	// then goto enter_loop
	// else goto exit_loop
	//
	// enter_loop:
	// do something
	// nxt = inc + ind
	// goto loop
	//
	// exit_loop:
	//
	// We may have more than one induction variables, the loop in the go
	// source code may looks like this:
	//
	// for i >= 0 && j >= 0 {
	// // use i and j
	// i--
	// j--
	// }
	//
	// So, also look for variables and blocks that satisfy the following
	//
	// loop:
	// i = (Phi maxi nxti)
	// j = (Phi maxj nxtj)
	// if i >= mini
	// then goto check_j
	// else goto exit_loop
	//
	// check_j:
	// if j >= minj
	// then goto enter_loop
	// else goto exit_loop
	//
	// enter_loop:
	// do something
	// nxti = i - di
	// nxtj = j - dj
	// goto loop
	//
	// exit_loop:
	func findIndVar(f *Func) []indVar {
	var iv []indVar
	sdom := f.Sdom()

	nextblock:
	for _, b := range f.Blocks {
	if b.Kind != BlockIf {
	continue
	}
	c := b.Controls[0]
	for idx := range 2 {
	// Check that the control if it either ind </<= limit or limit </<= ind.
	// TODO: Handle unsigned comparisons?
	inclusive := false
	switch c.Op {
	case OpLeq64, OpLeq32, OpLeq16, OpLeq8:
	inclusive = true
	case OpLess64, OpLess32, OpLess16, OpLess8:
	default:
	continue nextblock
	}

	less := idx == 0
	// induction variable, ending value
	ind, limit := c.Args[idx], c.Args[1-idx]
	// starting value, increment value, next value, loop return edge
	init, inc, nxt, loopReturn := parseIndVar(ind)
	if init == nil {
	continue // this is not an induction variable
	}

	// This is ind.Block.Preds, not b.Preds. That's a restriction on the loop header,
	// not the comparison block.
	if len(ind.Block.Preds) != 2 {
	continue
	}

	// Expect the increment to be a nonzero constant.
	if !inc.isGenericIntConst() {
	continue
	}
	step := inc.AuxInt
	if step == 0 {
	continue
	}
	// step == minInt64 cannot be safely negated below, because -step
	// overflows back to minInt64. The later underflow checks need a
	// positive magnitude, so reject this case here.
	if step == minSignedValue(ind.Type) {
	continue
	}

	// startBody is the edge that eventually returns to the loop header.
	var startBody Edge
	switch {
	case sdom.IsAncestorEq(b.Succs[0].b, loopReturn.b):
	startBody = b.Succs[0]
	case sdom.IsAncestorEq(b.Succs[1].b, loopReturn.b):
	// if x { goto exit } else { goto entry } is identical to if !x { goto entry } else { goto exit }
	startBody = b.Succs[1]
	less = !less
	inclusive = !inclusive
	default:
	continue
	}

	// Increment sign must match comparison direction.
	// When incrementing, the termination comparison must be ind </<= limit.
	// When decrementing, the termination comparison must be ind >/>= limit.
	// See issue 26116.
	if step > 0 && !less {
	continue
	}
	if step < 0 && less {
	continue
	}

	// Up to now we extracted the induction variable (ind),
	// the increment delta (inc), the temporary sum (nxt),
	// the initial value (init) and the limiting value (limit).
	//
	// We also know that ind has the form (Phi init nxt) where
	// nxt is (Add inc nxt) which means: 1) inc dominates nxt
	// and 2) there is a loop starting at inc and containing nxt.
	//
	// We need to prove that the induction variable is incremented
	// only when it's smaller than the limiting value.
	// Two conditions must happen listed below to accept ind
	// as an induction variable.

	// First condition: the entry block has a single predecessor.
	// The entry now means the in-loop edge where the induction variable
	// comparison succeeded. Its predecessor is not necessarily the header
	// block. This implies that b.Succs[0] is reached iff ind < limit.
	if len(startBody.b.Preds) != 1 {
	// the other successor must exit the loop.
	continue
	}

	// Second condition: startBody.b dominates nxt so that
	// nxt is computed when inc < limit.
	if !sdom.IsAncestorEq(startBody.b, nxt.Block) {
	// inc+ind can only be reached through the branch that confirmed the
	// induction variable is in bounds.
	continue
	}

	// Check for overflow/underflow. We need to make sure that inc never causes
	// the induction variable to wrap around.
	// We use a function wrapper here for easy return true / return false / keep going logic.
	// This function returns true if the increment will never overflow/underflow.
	ok := func() bool {
	if step > 0 {
	if limit.isGenericIntConst() {
	// Figure out the actual largest value.
	v := limit.AuxInt
	if !inclusive {
	if v == minSignedValue(limit.Type) {
	return false // < minint is never satisfiable.
	}
	v--
	}
	if init.isGenericIntConst() {
	// Use stride to compute a better lower limit.
	if init.AuxInt > v {
	return false
	}
	// TODO(1.27): investigate passing a smaller-magnitude overflow limit to addU
	// for addWillOverflow.
	v = addU(init.AuxInt, diff(v, init.AuxInt)/uint64(step)*uint64(step))
	}
	if addWillOverflow(v, step, maxSignedValue(ind.Type)) {
	return false
	}
	if inclusive && v != limit.AuxInt \|\| !inclusive && v+1 != limit.AuxInt {
	// We know a better limit than the programmer did. Use our limit instead.
	limit = f.constVal(limit.Op, limit.Type, v, true)
	inclusive = true
	}
	return true
	}
	if step == 1 && !inclusive {
	// Can't overflow because maxint is never a possible value.
	return true
	}
	// If the limit is not a constant, check to see if it is a
	// negative offset from a known non-negative value.
	knn, k := findKNN(limit)
	if knn == nil \|\| k < 0 {
	return false
	}
	// limit == (something nonnegative) - k. That subtraction can't underflow, so
	// we can trust it.
	if inclusive {
	// ind <= knn - k cannot overflow if step is at most k
	return step <= k
	}
	// ind < knn - k cannot overflow if step is at most k+1
	return step <= k+1 && k != maxSignedValue(limit.Type)

	// TODO: other unrolling idioms
	// for i := 0; i < KNN - KNN % k ; i += k
	// for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2
	// for i := 0; i < KNN&(-k) ; i += k // k a power of 2
	} else { // step < 0
	if limit.isGenericIntConst() {
	// Figure out the actual smallest value.
	v := limit.AuxInt
	if !inclusive {
	if v == maxSignedValue(limit.Type) {
	return false // > maxint is never satisfiable.
	}
	v++
	}
	if init.isGenericIntConst() {
	// Use stride to compute a better lower limit.
	if init.AuxInt < v {
	return false
	}
	// TODO(1.27): investigate passing a smaller-magnitude underflow limit to subU
	// for subWillUnderflow.
	v = subU(init.AuxInt, diff(init.AuxInt, v)/uint64(-step)*uint64(-step))
	}
	if subWillUnderflow(v, -step, minSignedValue(ind.Type)) {
	return false
	}
	if inclusive && v != limit.AuxInt \|\| !inclusive && v-1 != limit.AuxInt {
	// We know a better limit than the programmer did. Use our limit instead.
	limit = f.constVal(limit.Op, limit.Type, v, true)
	inclusive = true
	}
	return true
	}
	if step == -1 && !inclusive {
	// Can't underflow because minint is never a possible value.
	return true
	}
	}
	return false
	}

	if ok() {
	flags := indVarFlags(0)
	var min, max *Value
	if step > 0 {
	min = init
	max = limit
	if inclusive {
	flags \|= indVarMaxInc
	}
	} else {
	min = limit
	max = init
	flags \|= indVarMaxInc
	if !inclusive {
	flags \|= indVarMinExc
	}
	step = -step
	}
	if f.pass.debug >= 1 {
	printIndVar(b, ind, min, max, step, flags)
	}

	iv = append(iv, indVar{
	ind: ind,
	nxt: nxt,
	min: min,
	max: max,
	// This is startBody.b, where startBody is the edge from the comparison for the
	// induction variable, not necessarily the in-loop edge from the loop header.
	// Induction variable bounds are not valid in the loop before this edge.
	entry: startBody.b,
	step: step,
	flags: flags,
	})
	b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
	}
	}
	}

	return iv
	}

	// subWillUnderflow checks if x - y underflows the min value.
	// y must be positive.
	func subWillUnderflow(x, y int64, min int64) bool {
	if y < 0 {
	base.Fatalf("expecting positive value")
	}
	return x < min+y
	}

	// addWillOverflow checks if x + y overflows the max value.
	// y must be positive.
	func addWillOverflow(x, y int64, max int64) bool {
	if y < 0 {
	base.Fatalf("expecting positive value")
	}
	return x > max-y
	}

	// diff returns x-y as a uint64. Requires x>=y.
	func diff(x, y int64) uint64 {
	if x < y {
	base.Fatalf("diff %d - %d underflowed", x, y)
	}
	return uint64(x - y)
	}

	// addU returns x+y. Requires that x+y does not overflow an int64.
	func addU(x int64, y uint64) int64 {
	if y >= 1<<63 {
	if x >= 0 {
	base.Fatalf("addU overflowed %d + %d", x, y)
	}
	x += 1<<63 - 1
	x += 1
	y -= 1 << 63
	}
	// TODO(1.27): investigate passing a smaller-magnitude overflow limit in here.
	if addWillOverflow(x, int64(y), maxSignedValue(types.Types[types.TINT64])) {
	base.Fatalf("addU overflowed %d + %d", x, y)
	}
	return x + int64(y)
	}

	// subU returns x-y. Requires that x-y does not underflow an int64.
	func subU(x int64, y uint64) int64 {
	if y >= 1<<63 {
	if x < 0 {
	base.Fatalf("subU underflowed %d - %d", x, y)
	}
	x -= 1<<63 - 1
	x -= 1
	y -= 1 << 63
	}
	// TODO(1.27): investigate passing a smaller-magnitude underflow limit in here.
	if subWillUnderflow(x, int64(y), minSignedValue(types.Types[types.TINT64])) {
	base.Fatalf("subU underflowed %d - %d", x, y)
	}
	return x - int64(y)
	}

	// if v is known to be x - c, where x is known to be nonnegative and c is a
	// constant, return x, c. Otherwise return nil, 0.
	func findKNN(v Value) (Value, int64) {
	var x, y *Value
	x = v
	switch v.Op {
	case OpSub64, OpSub32, OpSub16, OpSub8:
	x = v.Args[0]
	y = v.Args[1]

	case OpAdd64, OpAdd32, OpAdd16, OpAdd8:
	x = v.Args[0]
	y = v.Args[1]
	if x.isGenericIntConst() {
	x, y = y, x
	}
	}
	switch x.Op {
	case OpSliceLen, OpStringLen, OpSliceCap:
	default:
	return nil, 0
	}
	if y == nil {
	return x, 0
	}
	if !y.isGenericIntConst() {
	return nil, 0
	}
	if v.Op == OpAdd64 \|\| v.Op == OpAdd32 \|\| v.Op == OpAdd16 \|\| v.Op == OpAdd8 {
	return x, -y.AuxInt
	}
	return x, y.AuxInt
	}

	func printIndVar(b Block, i, min, max Value, inc int64, flags indVarFlags) {
	mb1, mb2 := "[", "]"
	if flags&indVarMinExc != 0 {
	mb1 = "("
	}
	if flags&indVarMaxInc == 0 {
	mb2 = ")"
	}

	mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
	if !min.isGenericIntConst() {
	if b.Func.pass.debug >= 2 {
	mlim1 = fmt.Sprint(min)
	} else {
	mlim1 = "?"
	}
	}
	if !max.isGenericIntConst() {
	if b.Func.pass.debug >= 2 {
	mlim2 = fmt.Sprint(max)
	} else {
	mlim2 = "?"
	}
	}
	extra := ""
	if b.Func.pass.debug >= 2 {
	extra = fmt.Sprintf(" (%s)", i)
	}
	b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
	}

	func minSignedValue(t *types.Type) int64 {
	return -1 << (t.Size()*8 - 1)
	}

	func maxSignedValue(t *types.Type) int64 {
	return 1<<((t.Size()*8)-1) - 1
	}