src/cmd/compile/internal/ssa/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         "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 }