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         sdom := f.sdom()
  37
  38 nextb:
  39         for _, b := range f.Blocks {
  40                 if b.Kind != BlockIf || len(b.Preds) != 2 {
  41                         continue
  42                 }
  43
  44                 var ind, max *Value // induction, and maximum
  45                 entry := -1         // which successor of b enters the loop
  46
  47                 // Check thet the control if it either ind < max or max > ind.
  48                 // TODO: Handle Leq64, Geq64.
  49                 switch b.Control.Op {
  50                 case OpLess64:
  51                         entry = 0
  52                         ind, max = b.Control.Args[0], b.Control.Args[1]
  53                 case OpGreater64:
  54                         entry = 0
  55                         ind, max = b.Control.Args[1], b.Control.Args[0]
  56                 default:
  57                         continue nextb
  58                 }
  59
  60                 // Check that the induction variable is a phi that depends on itself.
  61                 if ind.Op != OpPhi {
  62                         continue
  63                 }
  64
  65                 // Extract min and nxt knowing that nxt is an addition (e.g. Add64).
  66                 var min, nxt *Value // minimum, and next value
  67                 if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
  68                         min, nxt = ind.Args[1], n
  69                 } else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
  70                         min, nxt = ind.Args[0], n
  71                 } else {
  72                         // Not a recognized induction variable.
  73                         continue
  74                 }
  75
  76                 var inc *Value
  77                 if nxt.Args[0] == ind { // nxt = ind + inc
  78                         inc = nxt.Args[1]
  79                 } else if nxt.Args[1] == ind { // nxt = inc + ind
  80                         inc = nxt.Args[0]
  81                 } else {
  82                         panic("unreachable") // one of the cases must be true from the above.
  83                 }
  84
  85                 // Expect the increment to be a positive constant.
  86                 // TODO: handle negative increment.
  87                 if inc.Op != OpConst64 || inc.AuxInt <= 0 {
  88                         continue
  89                 }
  90
  91                 // Up to now we extracted the induction variable (ind),
  92                 // the increment delta (inc), the temporary sum (nxt),
  93                 // the mininum value (min) and the maximum value (max).
  94                 //
  95                 // We also know that ind has the form (Phi min nxt) where
  96                 // nxt is (Add inc nxt) which means: 1) inc dominates nxt
  97                 // and 2) there is a loop starting at inc and containing nxt.
  98                 //
  99                 // We need to prove that the induction variable is incremented
 100                 // only when it's smaller than the maximum value.
 101                 // Two conditions must happen listed below to accept ind
 102                 // as an induction variable.
 103
 104                 // First condition: loop entry has a single predecessor, which
 105                 // is the header block.  This implies that b.Succs[entry] is
 106                 // reached iff ind < max.
 107                 if len(b.Succs[entry].b.Preds) != 1 {
 108                         // b.Succs[1-entry] must exit the loop.
 109                         continue
 110                 }
 111
 112                 // Second condition: b.Succs[entry] dominates nxt so that
 113                 // nxt is computed when inc < max, meaning nxt <= max.
 114                 if !sdom.isAncestorEq(b.Succs[entry].b, nxt.Block) {
 115                         // inc+ind can only be reached through the branch that enters the loop.
 116                         continue
 117                 }
 118
 119                 // If max is c + SliceLen with c <= 0 then we drop c.
 120                 // Makes sure c + SliceLen doesn't overflow when SliceLen == 0.
 121                 // TODO: save c as an offset from max.
 122                 if w, c := dropAdd64(max); (w.Op == OpStringLen || w.Op == OpSliceLen) && 0 >= c && -c >= 0 {
 123                         max = w
 124                 }
 125
 126                 // We can only guarantee that the loops runs within limits of induction variable
 127                 // if the increment is 1 or when the limits are constants.
 128                 if inc.AuxInt != 1 {
 129                         ok := false
 130                         if min.Op == OpConst64 && max.Op == OpConst64 {
 131                                 if max.AuxInt > min.AuxInt && max.AuxInt%inc.AuxInt == min.AuxInt%inc.AuxInt { // handle overflow
 132                                         ok = true
 133                                 }
 134                         }
 135                         if !ok {
 136                                 continue
 137                         }
 138                 }
 139
 140                 if f.pass.debug >= 1 {
 141                         if min.Op == OpConst64 {
 142                                 b.Func.Warnl(b.Pos, "Induction variable with minimum %d and increment %d", min.AuxInt, inc.AuxInt)
 143                         } else {
 144                                 b.Func.Warnl(b.Pos, "Induction variable with non-const minimum and increment %d", inc.AuxInt)
 145                         }
 146                 }
 147
 148                 iv = append(iv, indVar{
 149                         ind:   ind,
 150                         inc:   inc,
 151                         nxt:   nxt,
 152                         min:   min,
 153                         max:   max,
 154                         entry: b.Succs[entry].b,
 155                 })
 156                 b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
 157         }
 158
 159         return iv
 160 }
 161
 162 func dropAdd64(v *Value) (*Value, int64) {
 163         if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 {
 164                 return v.Args[1], v.Args[0].AuxInt
 165         }
 166         if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 {
 167                 return v.Args[0], v.Args[1].AuxInt
 168         }
 169         return v, 0
 170 }