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, sdom sparseTree) []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].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 !sdom.isAncestorEq(b.Succs[entry], 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],
 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         idom := dominators(f)
 164         sdom := newSparseTree(f, idom)
 165         ivList := findIndVar(f, sdom)
 166
 167         m := make(map[*Value]indVar)
 168         for _, iv := range ivList {
 169                 m[iv.ind] = iv
 170         }
 171
 172         removeBoundsChecks(f, sdom, m)
 173 }
 174
 175 // removesBoundsChecks remove IsInBounds and IsSliceInBounds based on the induction variables.
 176 func removeBoundsChecks(f *Func, sdom sparseTree, m map[*Value]indVar) {
 177         for _, b := range f.Blocks {
 178                 if b.Kind != BlockIf {
 179                         continue
 180                 }
 181
 182                 v := b.Control
 183
 184                 // Simplify:
 185                 // (IsInBounds ind max) where 0 <= const == min <= ind < max.
 186                 // (IsSliceInBounds ind max) where 0 <= const == min <= ind < max.
 187                 // Found in:
 188                 //      for i := range a {
 189                 //              use a[i]
 190                 //              use a[i:]
 191                 //              use a[:i]
 192                 //      }
 193                 if v.Op == OpIsInBounds || v.Op == OpIsSliceInBounds {
 194                         ind, add := dropAdd64(v.Args[0])
 195                         if ind.Op != OpPhi {
 196                                 goto skip1
 197                         }
 198                         if v.Op == OpIsInBounds && add != 0 {
 199                                 goto skip1
 200                         }
 201                         if v.Op == OpIsSliceInBounds && (0 > add || add > 1) {
 202                                 goto skip1
 203                         }
 204
 205                         if iv, has := m[ind]; has && sdom.isAncestorEq(iv.entry, b) && isNonNegative(iv.min) {
 206                                 if v.Args[1] == iv.max {
 207                                         if f.pass.debug > 0 {
 208                                                 f.Config.Warnl(b.Line, "Found redundant %s", v.Op)
 209                                         }
 210                                         goto simplify
 211                                 }
 212                         }
 213                 }
 214         skip1:
 215
 216                 // Simplify:
 217                 // (IsSliceInBounds ind (SliceCap a)) where 0 <= min <= ind < max == (SliceLen a)
 218                 // Found in:
 219                 //      for i := range a {
 220                 //              use a[:i]
 221                 //              use a[:i+1]
 222                 //      }
 223                 if v.Op == OpIsSliceInBounds {
 224                         ind, add := dropAdd64(v.Args[0])
 225                         if ind.Op != OpPhi {
 226                                 goto skip2
 227                         }
 228                         if 0 > add || add > 1 {
 229                                 goto skip2
 230                         }
 231
 232                         if iv, has := m[ind]; has && sdom.isAncestorEq(iv.entry, b) && isNonNegative(iv.min) {
 233                                 if v.Args[1].Op == OpSliceCap && iv.max.Op == OpSliceLen && v.Args[1].Args[0] == iv.max.Args[0] {
 234                                         if f.pass.debug > 0 {
 235                                                 f.Config.Warnl(b.Line, "Found redundant %s (len promoted to cap)", v.Op)
 236                                         }
 237                                         goto simplify
 238                                 }
 239                         }
 240                 }
 241         skip2:
 242
 243                 continue
 244
 245         simplify:
 246                 f.Logf("removing bounds check %v at %v in %s\n", b.Control, b, f.Name)
 247                 b.Kind = BlockFirst
 248                 b.SetControl(nil)
 249         }
 250 }
 251
 252 func dropAdd64(v *Value) (*Value, int64) {
 253         if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 {
 254                 return v.Args[1], v.Args[0].AuxInt
 255         }
 256         if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 {
 257                 return v.Args[0], v.Args[1].AuxInt
 258         }
 259         return v, 0
 260 }