Black Lives Matter. Support the Equal Justice Initiative.

Source file src/cmd/compile/internal/ssa/loopbce.go

Documentation: cmd/compile/internal/ssa

     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  	"fmt"
     9  	"math"
    10  )
    11  
    12  type indVarFlags uint8
    13  
    14  const (
    15  	indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive)
    16  	indVarMaxInc                         // maximum value is inclusive (default: exclusive)
    17  )
    18  
    19  type indVar struct {
    20  	ind   *Value // induction variable
    21  	min   *Value // minimum value, inclusive/exclusive depends on flags
    22  	max   *Value // maximum value, inclusive/exclusive depends on flags
    23  	entry *Block // entry block in the loop.
    24  	flags indVarFlags
    25  	// Invariant: for all blocks strictly dominated by entry:
    26  	//	min <= ind <  max    [if flags == 0]
    27  	//	min <  ind <  max    [if flags == indVarMinExc]
    28  	//	min <= ind <= max    [if flags == indVarMaxInc]
    29  	//	min <  ind <= max    [if flags == indVarMinExc|indVarMaxInc]
    30  }
    31  
    32  // parseIndVar checks whether the SSA value passed as argument is a valid induction
    33  // variable, and, if so, extracts:
    34  //   * the minimum bound
    35  //   * the increment value
    36  //   * the "next" value (SSA value that is Phi'd into the induction variable every loop)
    37  // Currently, we detect induction variables that match (Phi min nxt),
    38  // with nxt being (Add inc ind).
    39  // If it can't parse the induction variable correctly, it returns (nil, nil, nil).
    40  func parseIndVar(ind *Value) (min, inc, nxt *Value) {
    41  	if ind.Op != OpPhi {
    42  		return
    43  	}
    44  
    45  	if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
    46  		min, nxt = ind.Args[1], n
    47  	} else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
    48  		min, nxt = ind.Args[0], n
    49  	} else {
    50  		// Not a recognized induction variable.
    51  		return
    52  	}
    53  
    54  	if nxt.Args[0] == ind { // nxt = ind + inc
    55  		inc = nxt.Args[1]
    56  	} else if nxt.Args[1] == ind { // nxt = inc + ind
    57  		inc = nxt.Args[0]
    58  	} else {
    59  		panic("unreachable") // one of the cases must be true from the above.
    60  	}
    61  
    62  	return
    63  }
    64  
    65  // findIndVar finds induction variables in a function.
    66  //
    67  // Look for variables and blocks that satisfy the following
    68  //
    69  // loop:
    70  //   ind = (Phi min nxt),
    71  //   if ind < max
    72  //     then goto enter_loop
    73  //     else goto exit_loop
    74  //
    75  //   enter_loop:
    76  //	do something
    77  //      nxt = inc + ind
    78  //	goto loop
    79  //
    80  // exit_loop:
    81  //
    82  //
    83  // TODO: handle 32 bit operations
    84  func findIndVar(f *Func) []indVar {
    85  	var iv []indVar
    86  	sdom := f.Sdom()
    87  
    88  	for _, b := range f.Blocks {
    89  		if b.Kind != BlockIf || len(b.Preds) != 2 {
    90  			continue
    91  		}
    92  
    93  		var flags indVarFlags
    94  		var ind, max *Value // induction, and maximum
    95  
    96  		// Check thet the control if it either ind </<= max or max >/>= ind.
    97  		// TODO: Handle 32-bit comparisons.
    98  		// TODO: Handle unsigned comparisons?
    99  		c := b.Controls[0]
   100  		switch c.Op {
   101  		case OpLeq64:
   102  			flags |= indVarMaxInc
   103  			fallthrough
   104  		case OpLess64:
   105  			ind, max = c.Args[0], c.Args[1]
   106  		default:
   107  			continue
   108  		}
   109  
   110  		// See if this is really an induction variable
   111  		less := true
   112  		min, inc, nxt := parseIndVar(ind)
   113  		if min == nil {
   114  			// We failed to parse the induction variable. Before punting, we want to check
   115  			// whether the control op was written with arguments in non-idiomatic order,
   116  			// so that we believe being "max" (the upper bound) is actually the induction
   117  			// variable itself. This would happen for code like:
   118  			//     for i := 0; len(n) > i; i++
   119  			min, inc, nxt = parseIndVar(max)
   120  			if min == nil {
   121  				// No recognied induction variable on either operand
   122  				continue
   123  			}
   124  
   125  			// Ok, the arguments were reversed. Swap them, and remember that we're
   126  			// looking at a ind >/>= loop (so the induction must be decrementing).
   127  			ind, max = max, ind
   128  			less = false
   129  		}
   130  
   131  		// Expect the increment to be a nonzero constant.
   132  		if inc.Op != OpConst64 {
   133  			continue
   134  		}
   135  		step := inc.AuxInt
   136  		if step == 0 {
   137  			continue
   138  		}
   139  
   140  		// Increment sign must match comparison direction.
   141  		// When incrementing, the termination comparison must be ind </<= max.
   142  		// When decrementing, the termination comparison must be ind >/>= max.
   143  		// See issue 26116.
   144  		if step > 0 && !less {
   145  			continue
   146  		}
   147  		if step < 0 && less {
   148  			continue
   149  		}
   150  
   151  		// If the increment is negative, swap min/max and their flags
   152  		if step < 0 {
   153  			min, max = max, min
   154  			oldf := flags
   155  			flags = indVarMaxInc
   156  			if oldf&indVarMaxInc == 0 {
   157  				flags |= indVarMinExc
   158  			}
   159  			step = -step
   160  		}
   161  
   162  		// Up to now we extracted the induction variable (ind),
   163  		// the increment delta (inc), the temporary sum (nxt),
   164  		// the mininum value (min) and the maximum value (max).
   165  		//
   166  		// We also know that ind has the form (Phi min nxt) where
   167  		// nxt is (Add inc nxt) which means: 1) inc dominates nxt
   168  		// and 2) there is a loop starting at inc and containing nxt.
   169  		//
   170  		// We need to prove that the induction variable is incremented
   171  		// only when it's smaller than the maximum value.
   172  		// Two conditions must happen listed below to accept ind
   173  		// as an induction variable.
   174  
   175  		// First condition: loop entry has a single predecessor, which
   176  		// is the header block.  This implies that b.Succs[0] is
   177  		// reached iff ind < max.
   178  		if len(b.Succs[0].b.Preds) != 1 {
   179  			// b.Succs[1] must exit the loop.
   180  			continue
   181  		}
   182  
   183  		// Second condition: b.Succs[0] dominates nxt so that
   184  		// nxt is computed when inc < max, meaning nxt <= max.
   185  		if !sdom.IsAncestorEq(b.Succs[0].b, nxt.Block) {
   186  			// inc+ind can only be reached through the branch that enters the loop.
   187  			continue
   188  		}
   189  
   190  		// We can only guarantee that the loop runs within limits of induction variable
   191  		// if (one of)
   192  		// (1) the increment is ±1
   193  		// (2) the limits are constants
   194  		// (3) loop is of the form k0 upto Known_not_negative-k inclusive, step <= k
   195  		// (4) loop is of the form k0 upto Known_not_negative-k exclusive, step <= k+1
   196  		// (5) loop is of the form Known_not_negative downto k0, minint+step < k0
   197  		if step > 1 {
   198  			ok := false
   199  			if min.Op == OpConst64 && max.Op == OpConst64 {
   200  				if max.AuxInt > min.AuxInt && max.AuxInt%step == min.AuxInt%step { // handle overflow
   201  					ok = true
   202  				}
   203  			}
   204  			// Handle induction variables of these forms.
   205  			// KNN is known-not-negative.
   206  			// SIGNED ARITHMETIC ONLY. (see switch on c above)
   207  			// Possibilities for KNN are len and cap; perhaps we can infer others.
   208  			// for i := 0; i <= KNN-k    ; i += k
   209  			// for i := 0; i <  KNN-(k-1); i += k
   210  			// Also handle decreasing.
   211  
   212  			// "Proof" copied from https://go-review.googlesource.com/c/go/+/104041/10/src/cmd/compile/internal/ssa/loopbce.go#164
   213  			//
   214  			//	In the case of
   215  			//	// PC is Positive Constant
   216  			//	L := len(A)-PC
   217  			//	for i := 0; i < L; i = i+PC
   218  			//
   219  			//	we know:
   220  			//
   221  			//	0 + PC does not over/underflow.
   222  			//	len(A)-PC does not over/underflow
   223  			//	maximum value for L is MaxInt-PC
   224  			//	i < L <= MaxInt-PC means i + PC < MaxInt hence no overflow.
   225  
   226  			// To match in SSA:
   227  			// if  (a) min.Op == OpConst64(k0)
   228  			// and (b) k0 >= MININT + step
   229  			// and (c) max.Op == OpSubtract(Op{StringLen,SliceLen,SliceCap}, k)
   230  			// or  (c) max.Op == OpAdd(Op{StringLen,SliceLen,SliceCap}, -k)
   231  			// or  (c) max.Op == Op{StringLen,SliceLen,SliceCap}
   232  			// and (d) if upto loop, require indVarMaxInc && step <= k or !indVarMaxInc && step-1 <= k
   233  
   234  			if min.Op == OpConst64 && min.AuxInt >= step+math.MinInt64 {
   235  				knn := max
   236  				k := int64(0)
   237  				var kArg *Value
   238  
   239  				switch max.Op {
   240  				case OpSub64:
   241  					knn = max.Args[0]
   242  					kArg = max.Args[1]
   243  
   244  				case OpAdd64:
   245  					knn = max.Args[0]
   246  					kArg = max.Args[1]
   247  					if knn.Op == OpConst64 {
   248  						knn, kArg = kArg, knn
   249  					}
   250  				}
   251  				switch knn.Op {
   252  				case OpSliceLen, OpStringLen, OpSliceCap:
   253  				default:
   254  					knn = nil
   255  				}
   256  
   257  				if kArg != nil && kArg.Op == OpConst64 {
   258  					k = kArg.AuxInt
   259  					if max.Op == OpAdd64 {
   260  						k = -k
   261  					}
   262  				}
   263  				if k >= 0 && knn != nil {
   264  					if inc.AuxInt > 0 { // increasing iteration
   265  						// The concern for the relation between step and k is to ensure that iv never exceeds knn
   266  						// i.e., iv < knn-(K-1) ==> iv + K <= knn; iv <= knn-K ==> iv +K < knn
   267  						if step <= k || flags&indVarMaxInc == 0 && step-1 == k {
   268  							ok = true
   269  						}
   270  					} else { // decreasing iteration
   271  						// Will be decrementing from max towards min; max is knn-k; will only attempt decrement if
   272  						// knn-k >[=] min; underflow is only a concern if min-step is not smaller than min.
   273  						// This all assumes signed integer arithmetic
   274  						// This is already assured by the test above: min.AuxInt >= step+math.MinInt64
   275  						ok = true
   276  					}
   277  				}
   278  			}
   279  
   280  			// TODO: other unrolling idioms
   281  			// for i := 0; i < KNN - KNN % k ; i += k
   282  			// for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2
   283  			// for i := 0; i < KNN&(-k) ; i += k // k a power of 2
   284  
   285  			if !ok {
   286  				continue
   287  			}
   288  		}
   289  
   290  		if f.pass.debug >= 1 {
   291  			printIndVar(b, ind, min, max, step, flags)
   292  		}
   293  
   294  		iv = append(iv, indVar{
   295  			ind:   ind,
   296  			min:   min,
   297  			max:   max,
   298  			entry: b.Succs[0].b,
   299  			flags: flags,
   300  		})
   301  		b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
   302  	}
   303  
   304  	return iv
   305  }
   306  
   307  func dropAdd64(v *Value) (*Value, int64) {
   308  	if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 {
   309  		return v.Args[1], v.Args[0].AuxInt
   310  	}
   311  	if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 {
   312  		return v.Args[0], v.Args[1].AuxInt
   313  	}
   314  	return v, 0
   315  }
   316  
   317  func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
   318  	mb1, mb2 := "[", "]"
   319  	if flags&indVarMinExc != 0 {
   320  		mb1 = "("
   321  	}
   322  	if flags&indVarMaxInc == 0 {
   323  		mb2 = ")"
   324  	}
   325  
   326  	mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
   327  	if !min.isGenericIntConst() {
   328  		if b.Func.pass.debug >= 2 {
   329  			mlim1 = fmt.Sprint(min)
   330  		} else {
   331  			mlim1 = "?"
   332  		}
   333  	}
   334  	if !max.isGenericIntConst() {
   335  		if b.Func.pass.debug >= 2 {
   336  			mlim2 = fmt.Sprint(max)
   337  		} else {
   338  			mlim2 = "?"
   339  		}
   340  	}
   341  	extra := ""
   342  	if b.Func.pass.debug >= 2 {
   343  		extra = fmt.Sprintf(" (%s)", i)
   344  	}
   345  	b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
   346  }
   347  

View as plain text