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         "cmd/compile/internal/base"
   9         "fmt"
  10         "math"
  11 )
  12
  13 type indVarFlags uint8
  14
  15 const (
  16         indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive)
  17         indVarMaxInc                         // maximum value is inclusive (default: exclusive)
  18 )
  19
  20 type indVar struct {
  21         ind   *Value // induction variable
  22         min   *Value // minimum value, inclusive/exclusive depends on flags
  23         max   *Value // maximum value, inclusive/exclusive depends on flags
  24         entry *Block // entry block in the loop.
  25         flags indVarFlags
  26         // Invariant: for all blocks strictly dominated by entry:
  27         //      min <= ind <  max    [if flags == 0]
  28         //      min <  ind <  max    [if flags == indVarMinExc]
  29         //      min <= ind <= max    [if flags == indVarMaxInc]
  30         //      min <  ind <= max    [if flags == indVarMinExc|indVarMaxInc]
  31 }
  32
  33 // parseIndVar checks whether the SSA value passed as argument is a valid induction
  34 // variable, and, if so, extracts:
  35 //   - the minimum bound
  36 //   - the increment value
  37 //   - the "next" value (SSA value that is Phi'd into the induction variable every loop)
  38 //
  39 // Currently, we detect induction variables that match (Phi min nxt),
  40 // with nxt being (Add inc ind).
  41 // If it can't parse the induction variable correctly, it returns (nil, nil, nil).
  42 func parseIndVar(ind *Value) (min, inc, nxt *Value) {
  43         if ind.Op != OpPhi {
  44                 return
  45         }
  46
  47         if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
  48                 min, nxt = ind.Args[1], n
  49         } else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
  50                 min, nxt = ind.Args[0], n
  51         } else {
  52                 // Not a recognized induction variable.
  53                 return
  54         }
  55
  56         if nxt.Args[0] == ind { // nxt = ind + inc
  57                 inc = nxt.Args[1]
  58         } else if nxt.Args[1] == ind { // nxt = inc + ind
  59                 inc = nxt.Args[0]
  60         } else {
  61                 panic("unreachable") // one of the cases must be true from the above.
  62         }
  63
  64         return
  65 }
  66
  67 // findIndVar finds induction variables in a function.
  68 //
  69 // Look for variables and blocks that satisfy the following
  70 //
  71 //       loop:
  72 //         ind = (Phi min nxt),
  73 //         if ind < max
  74 //           then goto enter_loop
  75 //           else goto exit_loop
  76 //
  77 //         enter_loop:
  78 //              do something
  79 //            nxt = inc + ind
  80 //              goto loop
  81 //
  82 //       exit_loop:
  83 //
  84 // TODO: handle 32 bit operations
  85 func findIndVar(f *Func) []indVar {
  86         var iv []indVar
  87         sdom := f.Sdom()
  88
  89         for _, b := range f.Blocks {
  90                 if b.Kind != BlockIf || len(b.Preds) != 2 {
  91                         continue
  92                 }
  93
  94                 var ind *Value   // induction variable
  95                 var init *Value  // starting value
  96                 var limit *Value // ending value
  97
  98                 // Check thet the control if it either ind </<= limit or limit </<= ind.
  99                 // TODO: Handle 32-bit comparisons.
 100                 // TODO: Handle unsigned comparisons?
 101                 c := b.Controls[0]
 102                 inclusive := false
 103                 switch c.Op {
 104                 case OpLeq64:
 105                         inclusive = true
 106                         fallthrough
 107                 case OpLess64:
 108                         ind, limit = c.Args[0], c.Args[1]
 109                 default:
 110                         continue
 111                 }
 112
 113                 // See if this is really an induction variable
 114                 less := true
 115                 init, inc, nxt := parseIndVar(ind)
 116                 if init == nil {
 117                         // We failed to parse the induction variable. Before punting, we want to check
 118                         // whether the control op was written with the induction variable on the RHS
 119                         // instead of the LHS. This happens for the downwards case, like:
 120                         //     for i := len(n)-1; i >= 0; i--
 121                         init, inc, nxt = parseIndVar(limit)
 122                         if init == nil {
 123                                 // No recognied induction variable on either operand
 124                                 continue
 125                         }
 126
 127                         // Ok, the arguments were reversed. Swap them, and remember that we're
 128                         // looking at a ind >/>= loop (so the induction must be decrementing).
 129                         ind, limit = limit, ind
 130                         less = false
 131                 }
 132
 133                 // Expect the increment to be a nonzero constant.
 134                 if inc.Op != OpConst64 {
 135                         continue
 136                 }
 137                 step := inc.AuxInt
 138                 if step == 0 {
 139                         continue
 140                 }
 141
 142                 // Increment sign must match comparison direction.
 143                 // When incrementing, the termination comparison must be ind </<= limit.
 144                 // When decrementing, the termination comparison must be ind >/>= limit.
 145                 // See issue 26116.
 146                 if step > 0 && !less {
 147                         continue
 148                 }
 149                 if step < 0 && less {
 150                         continue
 151                 }
 152
 153                 // Up to now we extracted the induction variable (ind),
 154                 // the increment delta (inc), the temporary sum (nxt),
 155                 // the initial value (init) and the limiting value (limit).
 156                 //
 157                 // We also know that ind has the form (Phi init nxt) where
 158                 // nxt is (Add inc nxt) which means: 1) inc dominates nxt
 159                 // and 2) there is a loop starting at inc and containing nxt.
 160                 //
 161                 // We need to prove that the induction variable is incremented
 162                 // only when it's smaller than the limiting value.
 163                 // Two conditions must happen listed below to accept ind
 164                 // as an induction variable.
 165
 166                 // First condition: loop entry has a single predecessor, which
 167                 // is the header block.  This implies that b.Succs[0] is
 168                 // reached iff ind < limit.
 169                 if len(b.Succs[0].b.Preds) != 1 {
 170                         // b.Succs[1] must exit the loop.
 171                         continue
 172                 }
 173
 174                 // Second condition: b.Succs[0] dominates nxt so that
 175                 // nxt is computed when inc < limit.
 176                 if !sdom.IsAncestorEq(b.Succs[0].b, nxt.Block) {
 177                         // inc+ind can only be reached through the branch that enters the loop.
 178                         continue
 179                 }
 180
 181                 // Check for overflow/underflow. We need to make sure that inc never causes
 182                 // the induction variable to wrap around.
 183                 // We use a function wrapper here for easy return true / return false / keep going logic.
 184                 // This function returns true if the increment will never overflow/underflow.
 185                 ok := func() bool {
 186                         if step > 0 {
 187                                 if limit.Op == OpConst64 {
 188                                         // Figure out the actual largest value.
 189                                         v := limit.AuxInt
 190                                         if !inclusive {
 191                                                 if v == math.MinInt64 {
 192                                                         return false // < minint is never satisfiable.
 193                                                 }
 194                                                 v--
 195                                         }
 196                                         if init.Op == OpConst64 {
 197                                                 // Use stride to compute a better lower limit.
 198                                                 if init.AuxInt > v {
 199                                                         return false
 200                                                 }
 201                                                 v = addU(init.AuxInt, diff(v, init.AuxInt)/uint64(step)*uint64(step))
 202                                         }
 203                                         // It is ok if we can't overflow when incrementing from the largest value.
 204                                         return !addWillOverflow(v, step)
 205                                 }
 206                                 if step == 1 && !inclusive {
 207                                         // Can't overflow because maxint is never a possible value.
 208                                         return true
 209                                 }
 210                                 // If the limit is not a constant, check to see if it is a
 211                                 // negative offset from a known non-negative value.
 212                                 knn, k := findKNN(limit)
 213                                 if knn == nil || k < 0 {
 214                                         return false
 215                                 }
 216                                 // limit == (something nonnegative) - k. That subtraction can't underflow, so
 217                                 // we can trust it.
 218                                 if inclusive {
 219                                         // ind <= knn - k cannot overflow if step is at most k
 220                                         return step <= k
 221                                 }
 222                                 // ind < knn - k cannot overflow if step is at most k+1
 223                                 return step <= k+1 && k != math.MaxInt64
 224                         } else { // step < 0
 225                                 if limit.Op == OpConst64 {
 226                                         // Figure out the actual smallest value.
 227                                         v := limit.AuxInt
 228                                         if !inclusive {
 229                                                 if v == math.MaxInt64 {
 230                                                         return false // > maxint is never satisfiable.
 231                                                 }
 232                                                 v++
 233                                         }
 234                                         if init.Op == OpConst64 {
 235                                                 // Use stride to compute a better lower limit.
 236                                                 if init.AuxInt < v {
 237                                                         return false
 238                                                 }
 239                                                 v = subU(init.AuxInt, diff(init.AuxInt, v)/uint64(-step)*uint64(-step))
 240                                         }
 241                                         // It is ok if we can't underflow when decrementing from the smallest value.
 242                                         return !subWillUnderflow(v, -step)
 243                                 }
 244                                 if step == -1 && !inclusive {
 245                                         // Can't underflow because minint is never a possible value.
 246                                         return true
 247                                 }
 248                         }
 249                         return false
 250
 251                 }
 252
 253                 if ok() {
 254                         flags := indVarFlags(0)
 255                         var min, max *Value
 256                         if step > 0 {
 257                                 min = init
 258                                 max = limit
 259                                 if inclusive {
 260                                         flags |= indVarMaxInc
 261                                 }
 262                         } else {
 263                                 min = limit
 264                                 max = init
 265                                 flags |= indVarMaxInc
 266                                 if !inclusive {
 267                                         flags |= indVarMinExc
 268                                 }
 269                                 step = -step
 270                         }
 271                         if f.pass.debug >= 1 {
 272                                 printIndVar(b, ind, min, max, step, flags)
 273                         }
 274
 275                         iv = append(iv, indVar{
 276                                 ind:   ind,
 277                                 min:   min,
 278                                 max:   max,
 279                                 entry: b.Succs[0].b,
 280                                 flags: flags,
 281                         })
 282                         b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
 283                 }
 284
 285                 // TODO: other unrolling idioms
 286                 // for i := 0; i < KNN - KNN % k ; i += k
 287                 // for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2
 288                 // for i := 0; i < KNN&(-k) ; i += k // k a power of 2
 289         }
 290
 291         return iv
 292 }
 293
 294 // addWillOverflow reports whether x+y would result in a value more than maxint.
 295 func addWillOverflow(x, y int64) bool {
 296         return x+y < x
 297 }
 298
 299 // subWillUnderflow reports whether x-y would result in a value less than minint.
 300 func subWillUnderflow(x, y int64) bool {
 301         return x-y > x
 302 }
 303
 304 // diff returns x-y as a uint64. Requires x>=y.
 305 func diff(x, y int64) uint64 {
 306         if x < y {
 307                 base.Fatalf("diff %d - %d underflowed", x, y)
 308         }
 309         return uint64(x - y)
 310 }
 311
 312 // addU returns x+y. Requires that x+y does not overflow an int64.
 313 func addU(x int64, y uint64) int64 {
 314         if y >= 1<<63 {
 315                 if x >= 0 {
 316                         base.Fatalf("addU overflowed %d + %d", x, y)
 317                 }
 318                 x += 1<<63 - 1
 319                 x += 1
 320                 y -= 1 << 63
 321         }
 322         if addWillOverflow(x, int64(y)) {
 323                 base.Fatalf("addU overflowed %d + %d", x, y)
 324         }
 325         return x + int64(y)
 326 }
 327
 328 // subU returns x-y. Requires that x-y does not underflow an int64.
 329 func subU(x int64, y uint64) int64 {
 330         if y >= 1<<63 {
 331                 if x < 0 {
 332                         base.Fatalf("subU underflowed %d - %d", x, y)
 333                 }
 334                 x -= 1<<63 - 1
 335                 x -= 1
 336                 y -= 1 << 63
 337         }
 338         if subWillUnderflow(x, int64(y)) {
 339                 base.Fatalf("subU underflowed %d - %d", x, y)
 340         }
 341         return x - int64(y)
 342 }
 343
 344 // if v is known to be x - c, where x is known to be nonnegative and c is a
 345 // constant, return x, c. Otherwise return nil, 0.
 346 func findKNN(v *Value) (*Value, int64) {
 347         var x, y *Value
 348         x = v
 349         switch v.Op {
 350         case OpSub64:
 351                 x = v.Args[0]
 352                 y = v.Args[1]
 353
 354         case OpAdd64:
 355                 x = v.Args[0]
 356                 y = v.Args[1]
 357                 if x.Op == OpConst64 {
 358                         x, y = y, x
 359                 }
 360         }
 361         switch x.Op {
 362         case OpSliceLen, OpStringLen, OpSliceCap:
 363         default:
 364                 return nil, 0
 365         }
 366         if y == nil {
 367                 return x, 0
 368         }
 369         if y.Op != OpConst64 {
 370                 return nil, 0
 371         }
 372         if v.Op == OpAdd64 {
 373                 return x, -y.AuxInt
 374         }
 375         return x, y.AuxInt
 376 }
 377
 378 func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
 379         mb1, mb2 := "[", "]"
 380         if flags&indVarMinExc != 0 {
 381                 mb1 = "("
 382         }
 383         if flags&indVarMaxInc == 0 {
 384                 mb2 = ")"
 385         }
 386
 387         mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
 388         if !min.isGenericIntConst() {
 389                 if b.Func.pass.debug >= 2 {
 390                         mlim1 = fmt.Sprint(min)
 391                 } else {
 392                         mlim1 = "?"
 393                 }
 394         }
 395         if !max.isGenericIntConst() {
 396                 if b.Func.pass.debug >= 2 {
 397                         mlim2 = fmt.Sprint(max)
 398                 } else {
 399                         mlim2 = "?"
 400                 }
 401         }
 402         extra := ""
 403         if b.Func.pass.debug >= 2 {
 404                 extra = fmt.Sprintf(" (%s)", i)
 405         }
 406         b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
 407 }