...
Run Format

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 "fmt"
     8  
     9  type indVarFlags uint8
    10  
    11  const (
    12  	indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive)
    13  	indVarMaxInc                         // maximum value is inclusive (default: exclusive)
    14  )
    15  
    16  type indVar struct {
    17  	ind   *Value // induction variable
    18  	min   *Value // minimum value, inclusive/exclusive depends on flags
    19  	max   *Value // maximum value, inclusive/exclusive depends on flags
    20  	entry *Block // entry block in the loop.
    21  	flags indVarFlags
    22  	// Invariant: for all blocks strictly dominated by entry:
    23  	//	min <= ind <  max    [if flags == 0]
    24  	//	min <  ind <  max    [if flags == indVarMinExc]
    25  	//	min <= ind <= max    [if flags == indVarMaxInc]
    26  	//	min <  ind <= max    [if flags == indVarMinExc|indVarMaxInc]
    27  }
    28  
    29  // findIndVar finds induction variables in a function.
    30  //
    31  // Look for variables and blocks that satisfy the following
    32  //
    33  // loop:
    34  //   ind = (Phi min nxt),
    35  //   if ind < max
    36  //     then goto enter_loop
    37  //     else goto exit_loop
    38  //
    39  //   enter_loop:
    40  //	do something
    41  //      nxt = inc + ind
    42  //	goto loop
    43  //
    44  // exit_loop:
    45  //
    46  //
    47  // TODO: handle 32 bit operations
    48  func findIndVar(f *Func) []indVar {
    49  	var iv []indVar
    50  	sdom := f.sdom()
    51  
    52  	for _, b := range f.Blocks {
    53  		if b.Kind != BlockIf || len(b.Preds) != 2 {
    54  			continue
    55  		}
    56  
    57  		var flags indVarFlags
    58  		var ind, max *Value // induction, and maximum
    59  
    60  		// Check thet the control if it either ind </<= max or max >/>= ind.
    61  		// TODO: Handle 32-bit comparisons.
    62  		switch b.Control.Op {
    63  		case OpLeq64:
    64  			flags |= indVarMaxInc
    65  			fallthrough
    66  		case OpLess64:
    67  			ind, max = b.Control.Args[0], b.Control.Args[1]
    68  		case OpGeq64:
    69  			flags |= indVarMaxInc
    70  			fallthrough
    71  		case OpGreater64:
    72  			ind, max = b.Control.Args[1], b.Control.Args[0]
    73  		default:
    74  			continue
    75  		}
    76  
    77  		// See if the arguments are reversed (i < len() <=> len() > i)
    78  		less := true
    79  		if max.Op == OpPhi {
    80  			ind, max = max, ind
    81  			less = false
    82  		}
    83  
    84  		// Check that the induction variable is a phi that depends on itself.
    85  		if ind.Op != OpPhi {
    86  			continue
    87  		}
    88  
    89  		// Extract min and nxt knowing that nxt is an addition (e.g. Add64).
    90  		var min, nxt *Value // minimum, and next value
    91  		if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
    92  			min, nxt = ind.Args[1], n
    93  		} else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
    94  			min, nxt = ind.Args[0], n
    95  		} else {
    96  			// Not a recognized induction variable.
    97  			continue
    98  		}
    99  
   100  		var inc *Value
   101  		if nxt.Args[0] == ind { // nxt = ind + inc
   102  			inc = nxt.Args[1]
   103  		} else if nxt.Args[1] == ind { // nxt = inc + ind
   104  			inc = nxt.Args[0]
   105  		} else {
   106  			panic("unreachable") // one of the cases must be true from the above.
   107  		}
   108  
   109  		// Expect the increment to be a nonzero constant.
   110  		if inc.Op != OpConst64 {
   111  			continue
   112  		}
   113  		step := inc.AuxInt
   114  		if step == 0 {
   115  			continue
   116  		}
   117  
   118  		// Increment sign must match comparison direction.
   119  		// When incrementing, the termination comparison must be ind </<= max.
   120  		// When decrementing, the termination comparison must be ind >/>= max.
   121  		// See issue 26116.
   122  		if step > 0 && !less {
   123  			continue
   124  		}
   125  		if step < 0 && less {
   126  			continue
   127  		}
   128  
   129  		// If the increment is negative, swap min/max and their flags
   130  		if step < 0 {
   131  			min, max = max, min
   132  			oldf := flags
   133  			flags = indVarMaxInc
   134  			if oldf&indVarMaxInc == 0 {
   135  				flags |= indVarMinExc
   136  			}
   137  			step = -step
   138  		}
   139  
   140  		// Up to now we extracted the induction variable (ind),
   141  		// the increment delta (inc), the temporary sum (nxt),
   142  		// the mininum value (min) and the maximum value (max).
   143  		//
   144  		// We also know that ind has the form (Phi min nxt) where
   145  		// nxt is (Add inc nxt) which means: 1) inc dominates nxt
   146  		// and 2) there is a loop starting at inc and containing nxt.
   147  		//
   148  		// We need to prove that the induction variable is incremented
   149  		// only when it's smaller than the maximum value.
   150  		// Two conditions must happen listed below to accept ind
   151  		// as an induction variable.
   152  
   153  		// First condition: loop entry has a single predecessor, which
   154  		// is the header block.  This implies that b.Succs[0] is
   155  		// reached iff ind < max.
   156  		if len(b.Succs[0].b.Preds) != 1 {
   157  			// b.Succs[1] must exit the loop.
   158  			continue
   159  		}
   160  
   161  		// Second condition: b.Succs[0] dominates nxt so that
   162  		// nxt is computed when inc < max, meaning nxt <= max.
   163  		if !sdom.isAncestorEq(b.Succs[0].b, nxt.Block) {
   164  			// inc+ind can only be reached through the branch that enters the loop.
   165  			continue
   166  		}
   167  
   168  		// We can only guarantee that the loops runs within limits of induction variable
   169  		// if the increment is ±1 or when the limits are constants.
   170  		if step != 1 {
   171  			ok := false
   172  			if min.Op == OpConst64 && max.Op == OpConst64 {
   173  				if max.AuxInt > min.AuxInt && max.AuxInt%step == min.AuxInt%step { // handle overflow
   174  					ok = true
   175  				}
   176  			}
   177  			if !ok {
   178  				continue
   179  			}
   180  		}
   181  
   182  		if f.pass.debug >= 1 {
   183  			printIndVar(b, ind, min, max, step, flags)
   184  		}
   185  
   186  		iv = append(iv, indVar{
   187  			ind:   ind,
   188  			min:   min,
   189  			max:   max,
   190  			entry: b.Succs[0].b,
   191  			flags: flags,
   192  		})
   193  		b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
   194  	}
   195  
   196  	return iv
   197  }
   198  
   199  func dropAdd64(v *Value) (*Value, int64) {
   200  	if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 {
   201  		return v.Args[1], v.Args[0].AuxInt
   202  	}
   203  	if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 {
   204  		return v.Args[0], v.Args[1].AuxInt
   205  	}
   206  	return v, 0
   207  }
   208  
   209  func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
   210  	mb1, mb2 := "[", "]"
   211  	if flags&indVarMinExc != 0 {
   212  		mb1 = "("
   213  	}
   214  	if flags&indVarMaxInc == 0 {
   215  		mb2 = ")"
   216  	}
   217  
   218  	mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
   219  	if !min.isGenericIntConst() {
   220  		if b.Func.pass.debug >= 2 {
   221  			mlim1 = fmt.Sprint(min)
   222  		} else {
   223  			mlim1 = "?"
   224  		}
   225  	}
   226  	if !max.isGenericIntConst() {
   227  		if b.Func.pass.debug >= 2 {
   228  			mlim2 = fmt.Sprint(max)
   229  		} else {
   230  			mlim2 = "?"
   231  		}
   232  	}
   233  	extra := ""
   234  	if b.Func.pass.debug >= 2 {
   235  		extra = fmt.Sprintf(" (%s)", i)
   236  	}
   237  	b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
   238  }
   239  

View as plain text