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 // 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                 switch b.Control.Op {
 100                 case OpLeq64:
 101                         flags |= indVarMaxInc
 102                         fallthrough
 103                 case OpLess64:
 104                         ind, max = b.Control.Args[0], b.Control.Args[1]
 105                 case OpGeq64:
 106                         flags |= indVarMaxInc
 107                         fallthrough
 108                 case OpGreater64:
 109                         ind, max = b.Control.Args[1], b.Control.Args[0]
 110                 default:
 111                         continue
 112                 }
 113
 114                 // See if this is really an induction variable
 115                 less := true
 116                 min, inc, nxt := parseIndVar(ind)
 117                 if min == nil {
 118                         // We failed to parse the induction variable. Before punting, we want to check
 119                         // whether the control op was written with arguments in non-idiomatic order,
 120                         // so that we believe being "max" (the upper bound) is actually the induction
 121                         // variable itself. This would happen for code like:
 122                         //     for i := 0; len(n) > i; i++
 123                         min, inc, nxt = parseIndVar(max)
 124                         if min == nil {
 125                                 // No recognied induction variable on either operand
 126                                 continue
 127                         }
 128
 129                         // Ok, the arguments were reversed. Swap them, and remember that we're
 130                         // looking at a ind >/>= loop (so the induction must be decrementing).
 131                         ind, max = max, ind
 132                         less = false
 133                 }
 134
 135                 // Expect the increment to be a nonzero constant.
 136                 if inc.Op != OpConst64 {
 137                         continue
 138                 }
 139                 step := inc.AuxInt
 140                 if step == 0 {
 141                         continue
 142                 }
 143
 144                 // Increment sign must match comparison direction.
 145                 // When incrementing, the termination comparison must be ind </<= max.
 146                 // When decrementing, the termination comparison must be ind >/>= max.
 147                 // See issue 26116.
 148                 if step > 0 && !less {
 149                         continue
 150                 }
 151                 if step < 0 && less {
 152                         continue
 153                 }
 154
 155                 // If the increment is negative, swap min/max and their flags
 156                 if step < 0 {
 157                         min, max = max, min
 158                         oldf := flags
 159                         flags = indVarMaxInc
 160                         if oldf&indVarMaxInc == 0 {
 161                                 flags |= indVarMinExc
 162                         }
 163                         step = -step
 164                 }
 165
 166                 // Up to now we extracted the induction variable (ind),
 167                 // the increment delta (inc), the temporary sum (nxt),
 168                 // the mininum value (min) and the maximum value (max).
 169                 //
 170                 // We also know that ind has the form (Phi min nxt) where
 171                 // nxt is (Add inc nxt) which means: 1) inc dominates nxt
 172                 // and 2) there is a loop starting at inc and containing nxt.
 173                 //
 174                 // We need to prove that the induction variable is incremented
 175                 // only when it's smaller than the maximum value.
 176                 // Two conditions must happen listed below to accept ind
 177                 // as an induction variable.
 178
 179                 // First condition: loop entry has a single predecessor, which
 180                 // is the header block.  This implies that b.Succs[0] is
 181                 // reached iff ind < max.
 182                 if len(b.Succs[0].b.Preds) != 1 {
 183                         // b.Succs[1] must exit the loop.
 184                         continue
 185                 }
 186
 187                 // Second condition: b.Succs[0] dominates nxt so that
 188                 // nxt is computed when inc < max, meaning nxt <= max.
 189                 if !sdom.isAncestorEq(b.Succs[0].b, nxt.Block) {
 190                         // inc+ind can only be reached through the branch that enters the loop.
 191                         continue
 192                 }
 193
 194                 // We can only guarantee that the loop runs within limits of induction variable
 195                 // if (one of)
 196                 // (1) the increment is ±1
 197                 // (2) the limits are constants
 198                 // (3) loop is of the form k0 upto Known_not_negative-k inclusive, step <= k
 199                 // (4) loop is of the form k0 upto Known_not_negative-k exclusive, step <= k+1
 200                 // (5) loop is of the form Known_not_negative downto k0, minint+step < k0
 201                 if step > 1 {
 202                         ok := false
 203                         if min.Op == OpConst64 && max.Op == OpConst64 {
 204                                 if max.AuxInt > min.AuxInt && max.AuxInt%step == min.AuxInt%step { // handle overflow
 205                                         ok = true
 206                                 }
 207                         }
 208                         // Handle induction variables of these forms.
 209                         // KNN is known-not-negative.
 210                         // SIGNED ARITHMETIC ONLY. (see switch on b.Control.Op above)
 211                         // Possibilities for KNN are len and cap; perhaps we can infer others.
 212                         // for i := 0; i <= KNN-k    ; i += k
 213                         // for i := 0; i <  KNN-(k-1); i += k
 214                         // Also handle decreasing.
 215
 216                         // "Proof" copied from https://go-review.googlesource.com/c/go/+/104041/10/src/cmd/compile/internal/ssa/loopbce.go#164
 217                         //
 218                         //      In the case of
 219                         //      // PC is Positive Constant
 220                         //      L := len(A)-PC
 221                         //      for i := 0; i < L; i = i+PC
 222                         //
 223                         //      we know:
 224                         //
 225                         //      0 + PC does not over/underflow.
 226                         //      len(A)-PC does not over/underflow
 227                         //      maximum value for L is MaxInt-PC
 228                         //      i < L <= MaxInt-PC means i + PC < MaxInt hence no overflow.
 229
 230                         // To match in SSA:
 231                         // if  (a) min.Op == OpConst64(k0)
 232                         // and (b) k0 >= MININT + step
 233                         // and (c) max.Op == OpSubtract(Op{StringLen,SliceLen,SliceCap}, k)
 234                         // or  (c) max.Op == OpAdd(Op{StringLen,SliceLen,SliceCap}, -k)
 235                         // or  (c) max.Op == Op{StringLen,SliceLen,SliceCap}
 236                         // and (d) if upto loop, require indVarMaxInc && step <= k or !indVarMaxInc && step-1 <= k
 237
 238                         if min.Op == OpConst64 && min.AuxInt >= step+math.MinInt64 {
 239                                 knn := max
 240                                 k := int64(0)
 241                                 var kArg *Value
 242
 243                                 switch max.Op {
 244                                 case OpSub64:
 245                                         knn = max.Args[0]
 246                                         kArg = max.Args[1]
 247
 248                                 case OpAdd64:
 249                                         knn = max.Args[0]
 250                                         kArg = max.Args[1]
 251                                         if knn.Op == OpConst64 {
 252                                                 knn, kArg = kArg, knn
 253                                         }
 254                                 }
 255                                 switch knn.Op {
 256                                 case OpSliceLen, OpStringLen, OpSliceCap:
 257                                 default:
 258                                         knn = nil
 259                                 }
 260
 261                                 if kArg != nil && kArg.Op == OpConst64 {
 262                                         k = kArg.AuxInt
 263                                         if max.Op == OpAdd64 {
 264                                                 k = -k
 265                                         }
 266                                 }
 267                                 if k >= 0 && knn != nil {
 268                                         if inc.AuxInt > 0 { // increasing iteration
 269                                                 // The concern for the relation between step and k is to ensure that iv never exceeds knn
 270                                                 // i.e., iv < knn-(K-1) ==> iv + K <= knn; iv <= knn-K ==> iv +K < knn
 271                                                 if step <= k || flags&indVarMaxInc == 0 && step-1 == k {
 272                                                         ok = true
 273                                                 }
 274                                         } else { // decreasing iteration
 275                                                 // Will be decrementing from max towards min; max is knn-k; will only attempt decrement if
 276                                                 // knn-k >[=] min; underflow is only a concern if min-step is not smaller than min.
 277                                                 // This all assumes signed integer arithmetic
 278                                                 // This is already assured by the test above: min.AuxInt >= step+math.MinInt64
 279                                                 ok = true
 280                                         }
 281                                 }
 282                         }
 283
 284                         // TODO: other unrolling idioms
 285                         // for i := 0; i < KNN - KNN % k ; i += k
 286                         // for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2
 287                         // for i := 0; i < KNN&(-k) ; i += k // k a power of 2
 288
 289                         if !ok {
 290                                 continue
 291                         }
 292                 }
 293
 294                 if f.pass.debug >= 1 {
 295                         printIndVar(b, ind, min, max, step, flags)
 296                 }
 297
 298                 iv = append(iv, indVar{
 299                         ind:   ind,
 300                         min:   min,
 301                         max:   max,
 302                         entry: b.Succs[0].b,
 303                         flags: flags,
 304                 })
 305                 b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
 306         }
 307
 308         return iv
 309 }
 310
 311 func dropAdd64(v *Value) (*Value, int64) {
 312         if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 {
 313                 return v.Args[1], v.Args[0].AuxInt
 314         }
 315         if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 {
 316                 return v.Args[0], v.Args[1].AuxInt
 317         }
 318         return v, 0
 319 }
 320
 321 func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
 322         mb1, mb2 := "[", "]"
 323         if flags&indVarMinExc != 0 {
 324                 mb1 = "("
 325         }
 326         if flags&indVarMaxInc == 0 {
 327                 mb2 = ")"
 328         }
 329
 330         mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
 331         if !min.isGenericIntConst() {
 332                 if b.Func.pass.debug >= 2 {
 333                         mlim1 = fmt.Sprint(min)
 334                 } else {
 335                         mlim1 = "?"
 336                 }
 337         }
 338         if !max.isGenericIntConst() {
 339                 if b.Func.pass.debug >= 2 {
 340                         mlim2 = fmt.Sprint(max)
 341                 } else {
 342                         mlim2 = "?"
 343                 }
 344         }
 345         extra := ""
 346         if b.Func.pass.debug >= 2 {
 347                 extra = fmt.Sprintf(" (%s)", i)
 348         }
 349         b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
 350 }