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

View as plain text