src/cmd/compile/internal/ssa/loopbce.go

   1 package ssa
   2
   3 type indVar struct {
   4         ind   *Value // induction variable
   5         inc   *Value // increment, a constant
   6         nxt   *Value // ind+inc variable
   7         min   *Value // minimum value. inclusive,
   8         max   *Value // maximum value. exclusive.
   9         entry *Block // entry block in the loop.
  10         // Invariants: for all blocks dominated by entry:
  11         //      min <= ind < max
  12         //      min <= nxt <= max
  13 }
  14
  15 // findIndVar finds induction variables in a function.
  16 //
  17 // Look for variables and blocks that satisfy the following
  18 //
  19 // loop:
  20 //   ind = (Phi min nxt),
  21 //   if ind < max
  22 //     then goto enter_loop
  23 //     else goto exit_loop
  24 //
  25 //   enter_loop:
  26 //      do something
  27 //      nxt = inc + ind
  28 //      goto loop
  29 //
  30 // exit_loop:
  31 //
  32 //
  33 // TODO: handle 32 bit operations
  34 func findIndVar(f *Func) []indVar {
  35         var iv []indVar
  36
  37 nextb:
  38         for _, b := range f.Blocks {
  39                 if b.Kind != BlockIf || len(b.Preds) != 2 {
  40                         continue
  41                 }
  42
  43                 var ind, max *Value // induction, and maximum
  44                 entry := -1         // which successor of b enters the loop
  45
  46                 // Check thet the control if it either ind < max or max > ind.
  47                 // TODO: Handle Leq64, Geq64.
  48                 switch b.Control.Op {
  49                 case OpLess64:
  50                         entry = 0
  51                         ind, max = b.Control.Args[0], b.Control.Args[1]
  52                 case OpGreater64:
  53                         entry = 0
  54                         ind, max = b.Control.Args[1], b.Control.Args[0]
  55                 default:
  56                         continue nextb
  57                 }
  58
  59                 // Check that the induction variable is a phi that depends on itself.
  60                 if ind.Op != OpPhi {
  61                         continue
  62                 }
  63
  64                 // Extract min and nxt knowing that nxt is an addition (e.g. Add64).
  65                 var min, nxt *Value // minimum, and next value
  66                 if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
  67                         min, nxt = ind.Args[1], n
  68                 } else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
  69                         min, nxt = ind.Args[0], n
  70                 } else {
  71                         // Not a recognized induction variable.
  72                         continue
  73                 }
  74
  75                 var inc *Value
  76                 if nxt.Args[0] == ind { // nxt = ind + inc
  77                         inc = nxt.Args[1]
  78                 } else if nxt.Args[1] == ind { // nxt = inc + ind
  79                         inc = nxt.Args[0]
  80                 } else {
  81                         panic("unreachable") // one of the cases must be true from the above.
  82                 }
  83
  84                 // Expect the increment to be a positive constant.
  85                 // TODO: handle negative increment.
  86                 if inc.Op != OpConst64 || inc.AuxInt <= 0 {
  87                         continue
  88                 }
  89
  90                 // Up to now we extracted the induction variable (ind),
  91                 // the increment delta (inc), the temporary sum (nxt),
  92                 // the mininum value (min) and the maximum value (max).
  93                 //
  94                 // We also know that ind has the form (Phi min nxt) where
  95                 // nxt is (Add inc nxt) which means: 1) inc dominates nxt
  96                 // and 2) there is a loop starting at inc and containing nxt.
  97                 //
  98                 // We need to prove that the induction variable is incremented
  99                 // only when it's smaller than the maximum value.
 100                 // Two conditions must happen listed below to accept ind
 101                 // as an induction variable.
 102
 103                 // First condition: loop entry has a single predecessor, which
 104                 // is the header block.  This implies that b.Succs[entry] is
 105                 // reached iff ind < max.
 106                 if len(b.Succs[entry].b.Preds) != 1 {
 107                         // b.Succs[1-entry] must exit the loop.
 108                         continue
 109                 }
 110
 111                 // Second condition: b.Succs[entry] dominates nxt so that
 112                 // nxt is computed when inc < max, meaning nxt <= max.
 113                 if !f.sdom.isAncestorEq(b.Succs[entry].b, nxt.Block) {
 114                         // inc+ind can only be reached through the branch that enters the loop.
 115                         continue
 116                 }
 117
 118                 // If max is c + SliceLen with c <= 0 then we drop c.
 119                 // Makes sure c + SliceLen doesn't overflow when SliceLen == 0.
 120                 // TODO: save c as an offset from max.
 121                 if w, c := dropAdd64(max); (w.Op == OpStringLen || w.Op == OpSliceLen) && 0 >= c && -c >= 0 {
 122                         max = w
 123                 }
 124
 125                 // We can only guarantee that the loops runs within limits of induction variable
 126                 // if the increment is 1 or when the limits are constants.
 127                 if inc.AuxInt != 1 {
 128                         ok := false
 129                         if min.Op == OpConst64 && max.Op == OpConst64 {
 130                                 if max.AuxInt > min.AuxInt && max.AuxInt%inc.AuxInt == min.AuxInt%inc.AuxInt { // handle overflow
 131                                         ok = true
 132                                 }
 133                         }
 134                         if !ok {
 135                                 continue
 136                         }
 137                 }
 138
 139                 if f.pass.debug > 1 {
 140                         if min.Op == OpConst64 {
 141                                 b.Func.Config.Warnl(b.Line, "Induction variable with minimum %d and increment %d", min.AuxInt, inc.AuxInt)
 142                         } else {
 143                                 b.Func.Config.Warnl(b.Line, "Induction variable with non-const minimum and increment %d", inc.AuxInt)
 144                         }
 145                 }
 146
 147                 iv = append(iv, indVar{
 148                         ind:   ind,
 149                         inc:   inc,
 150                         nxt:   nxt,
 151                         min:   min,
 152                         max:   max,
 153                         entry: b.Succs[entry].b,
 154                 })
 155                 b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
 156         }
 157
 158         return iv
 159 }
 160
 161 // loopbce performs loop based bounds check elimination.
 162 func loopbce(f *Func) {
 163         ivList := findIndVar(f)
 164
 165         m := make(map[*Value]indVar)
 166         for _, iv := range ivList {
 167                 m[iv.ind] = iv
 168         }
 169
 170         removeBoundsChecks(f, m)
 171 }
 172
 173 // removesBoundsChecks remove IsInBounds and IsSliceInBounds based on the induction variables.
 174 func removeBoundsChecks(f *Func, m map[*Value]indVar) {
 175         for _, b := range f.Blocks {
 176                 if b.Kind != BlockIf {
 177                         continue
 178                 }
 179
 180                 v := b.Control
 181
 182                 // Simplify:
 183                 // (IsInBounds ind max) where 0 <= const == min <= ind < max.
 184                 // (IsSliceInBounds ind max) where 0 <= const == min <= ind < max.
 185                 // Found in:
 186                 //      for i := range a {
 187                 //              use a[i]
 188                 //              use a[i:]
 189                 //              use a[:i]
 190                 //      }
 191                 if v.Op == OpIsInBounds || v.Op == OpIsSliceInBounds {
 192                         ind, add := dropAdd64(v.Args[0])
 193                         if ind.Op != OpPhi {
 194                                 goto skip1
 195                         }
 196                         if v.Op == OpIsInBounds && add != 0 {
 197                                 goto skip1
 198                         }
 199                         if v.Op == OpIsSliceInBounds && (0 > add || add > 1) {
 200                                 goto skip1
 201                         }
 202
 203                         if iv, has := m[ind]; has && f.sdom.isAncestorEq(iv.entry, b) && isNonNegative(iv.min) {
 204                                 if v.Args[1] == iv.max {
 205                                         if f.pass.debug > 0 {
 206                                                 f.Config.Warnl(b.Line, "Found redundant %s", v.Op)
 207                                         }
 208                                         goto simplify
 209                                 }
 210                         }
 211                 }
 212         skip1:
 213
 214                 // Simplify:
 215                 // (IsSliceInBounds ind (SliceCap a)) where 0 <= min <= ind < max == (SliceLen a)
 216                 // Found in:
 217                 //      for i := range a {
 218                 //              use a[:i]
 219                 //              use a[:i+1]
 220                 //      }
 221                 if v.Op == OpIsSliceInBounds {
 222                         ind, add := dropAdd64(v.Args[0])
 223                         if ind.Op != OpPhi {
 224                                 goto skip2
 225                         }
 226                         if 0 > add || add > 1 {
 227                                 goto skip2
 228                         }
 229
 230                         if iv, has := m[ind]; has && f.sdom.isAncestorEq(iv.entry, b) && isNonNegative(iv.min) {
 231                                 if v.Args[1].Op == OpSliceCap && iv.max.Op == OpSliceLen && v.Args[1].Args[0] == iv.max.Args[0] {
 232                                         if f.pass.debug > 0 {
 233                                                 f.Config.Warnl(b.Line, "Found redundant %s (len promoted to cap)", v.Op)
 234                                         }
 235                                         goto simplify
 236                                 }
 237                         }
 238                 }
 239         skip2:
 240
 241                 // Simplify
 242                 // (IsInBounds (Add64 ind) (Const64 [c])) where 0 <= min <= ind < max <= (Const64 [c])
 243                 // (IsSliceInBounds ind (Const64 [c])) where 0 <= min <= ind < max <= (Const64 [c])
 244                 if v.Op == OpIsInBounds || v.Op == OpIsSliceInBounds {
 245                         ind, add := dropAdd64(v.Args[0])
 246                         if ind.Op != OpPhi {
 247                                 goto skip3
 248                         }
 249
 250                         // ind + add >= 0 <-> min + add >= 0 <-> min >= -add
 251                         if iv, has := m[ind]; has && f.sdom.isAncestorEq(iv.entry, b) && isGreaterOrEqualThan(iv.min, -add) {
 252                                 if !v.Args[1].isGenericIntConst() || !iv.max.isGenericIntConst() {
 253                                         goto skip3
 254                                 }
 255
 256                                 limit := v.Args[1].AuxInt
 257                                 if v.Op == OpIsSliceInBounds {
 258                                         // If limit++ overflows signed integer then 0 <= max && max <= limit will be false.
 259                                         limit++
 260                                 }
 261
 262                                 if max := iv.max.AuxInt + add; 0 <= max && max <= limit { // handle overflow
 263                                         if f.pass.debug > 0 {
 264                                                 f.Config.Warnl(b.Line, "Found redundant (%s ind %d), ind < %d", v.Op, v.Args[1].AuxInt, iv.max.AuxInt+add)
 265                                         }
 266                                         goto simplify
 267                                 }
 268                         }
 269                 }
 270         skip3:
 271
 272                 continue
 273
 274         simplify:
 275                 f.Logf("removing bounds check %v at %v in %s\n", b.Control, b, f.Name)
 276                 b.Kind = BlockFirst
 277                 b.SetControl(nil)
 278         }
 279 }
 280
 281 func dropAdd64(v *Value) (*Value, int64) {
 282         if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 {
 283                 return v.Args[1], v.Args[0].AuxInt
 284         }
 285         if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 {
 286                 return v.Args[0], v.Args[1].AuxInt
 287         }
 288         return v, 0
 289 }
 290
 291 func isGreaterOrEqualThan(v *Value, c int64) bool {
 292         if c == 0 {
 293                 return isNonNegative(v)
 294         }
 295         if v.isGenericIntConst() && v.AuxInt >= c {
 296                 return true
 297         }
 298         return false
 299 }