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

   1 package ssa
   2
   3 import "fmt"
   4
   5 type indVarFlags uint8
   6
   7 const (
   8         indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive)
   9         indVarMaxInc                         // maximum value is inclusive (default: exclusive)
  10 )
  11
  12 type indVar struct {
  13         ind   *Value // induction variable
  14         inc   *Value // increment, a constant
  15         nxt   *Value // ind+inc variable
  16         min   *Value // minimum value, inclusive/exclusive depends on flags
  17         max   *Value // maximum value, inclusive/exclusive depends on flags
  18         entry *Block // entry block in the loop.
  19         flags indVarFlags
  20         // Invariants: for all blocks dominated by entry:
  21         //      min <= ind < max
  22         //      min <= nxt <= max
  23 }
  24
  25 // findIndVar finds induction variables in a function.
  26 //
  27 // Look for variables and blocks that satisfy the following
  28 //
  29 // loop:
  30 //   ind = (Phi min nxt),
  31 //   if ind < max
  32 //     then goto enter_loop
  33 //     else goto exit_loop
  34 //
  35 //   enter_loop:
  36 //      do something
  37 //      nxt = inc + ind
  38 //      goto loop
  39 //
  40 // exit_loop:
  41 //
  42 //
  43 // TODO: handle 32 bit operations
  44 func findIndVar(f *Func) []indVar {
  45         var iv []indVar
  46         sdom := f.sdom()
  47
  48 nextb:
  49         for _, b := range f.Blocks {
  50                 if b.Kind != BlockIf || len(b.Preds) != 2 {
  51                         continue
  52                 }
  53
  54                 var flags indVarFlags
  55                 var ind, max *Value // induction, and maximum
  56                 entry := -1         // which successor of b enters the loop
  57
  58                 // Check thet the control if it either ind </<= max or max >/>= ind.
  59                 // TODO: Handle 32-bit comparisons.
  60                 switch b.Control.Op {
  61                 case OpLeq64:
  62                         flags |= indVarMaxInc
  63                         fallthrough
  64                 case OpLess64:
  65                         entry = 0
  66                         ind, max = b.Control.Args[0], b.Control.Args[1]
  67                 case OpGeq64:
  68                         flags |= indVarMaxInc
  69                         fallthrough
  70                 case OpGreater64:
  71                         entry = 0
  72                         ind, max = b.Control.Args[1], b.Control.Args[0]
  73                 default:
  74                         continue nextb
  75                 }
  76
  77                 // See if the arguments are reversed (i < len() <=> len() > i)
  78                 if max.Op == OpPhi {
  79                         ind, max = max, ind
  80                 }
  81
  82                 // Check that the induction variable is a phi that depends on itself.
  83                 if ind.Op != OpPhi {
  84                         continue
  85                 }
  86
  87                 // Extract min and nxt knowing that nxt is an addition (e.g. Add64).
  88                 var min, nxt *Value // minimum, and next value
  89                 if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
  90                         min, nxt = ind.Args[1], n
  91                 } else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
  92                         min, nxt = ind.Args[0], n
  93                 } else {
  94                         // Not a recognized induction variable.
  95                         continue
  96                 }
  97
  98                 var inc *Value
  99                 if nxt.Args[0] == ind { // nxt = ind + inc
 100                         inc = nxt.Args[1]
 101                 } else if nxt.Args[1] == ind { // nxt = inc + ind
 102                         inc = nxt.Args[0]
 103                 } else {
 104                         panic("unreachable") // one of the cases must be true from the above.
 105                 }
 106
 107                 // Expect the increment to be a constant.
 108                 if inc.Op != OpConst64 {
 109                         continue
 110                 }
 111
 112                 // If the increment is negative, swap min/max and their flags
 113                 if inc.AuxInt <= 0 {
 114                         min, max = max, min
 115                         oldf := flags
 116                         flags = 0
 117                         if oldf&indVarMaxInc == 0 {
 118                                 flags |= indVarMinExc
 119                         }
 120                         if oldf&indVarMinExc == 0 {
 121                                 flags |= indVarMaxInc
 122                         }
 123                 }
 124
 125                 // Up to now we extracted the induction variable (ind),
 126                 // the increment delta (inc), the temporary sum (nxt),
 127                 // the mininum value (min) and the maximum value (max).
 128                 //
 129                 // We also know that ind has the form (Phi min nxt) where
 130                 // nxt is (Add inc nxt) which means: 1) inc dominates nxt
 131                 // and 2) there is a loop starting at inc and containing nxt.
 132                 //
 133                 // We need to prove that the induction variable is incremented
 134                 // only when it's smaller than the maximum value.
 135                 // Two conditions must happen listed below to accept ind
 136                 // as an induction variable.
 137
 138                 // First condition: loop entry has a single predecessor, which
 139                 // is the header block.  This implies that b.Succs[entry] is
 140                 // reached iff ind < max.
 141                 if len(b.Succs[entry].b.Preds) != 1 {
 142                         // b.Succs[1-entry] must exit the loop.
 143                         continue
 144                 }
 145
 146                 // Second condition: b.Succs[entry] dominates nxt so that
 147                 // nxt is computed when inc < max, meaning nxt <= max.
 148                 if !sdom.isAncestorEq(b.Succs[entry].b, nxt.Block) {
 149                         // inc+ind can only be reached through the branch that enters the loop.
 150                         continue
 151                 }
 152
 153                 // We can only guarantee that the loops runs within limits of induction variable
 154                 // if the increment is ±1 or when the limits are constants.
 155                 if inc.AuxInt != 1 && inc.AuxInt != -1 {
 156                         ok := false
 157                         if min.Op == OpConst64 && max.Op == OpConst64 {
 158                                 if max.AuxInt > min.AuxInt && max.AuxInt%inc.AuxInt == min.AuxInt%inc.AuxInt { // handle overflow
 159                                         ok = true
 160                                 }
 161                         }
 162                         if !ok {
 163                                 continue
 164                         }
 165                 }
 166
 167                 if f.pass.debug >= 1 {
 168                         printIndVar(b, ind, min, max, inc.AuxInt, flags)
 169                 }
 170
 171                 iv = append(iv, indVar{
 172                         ind:   ind,
 173                         inc:   inc,
 174                         nxt:   nxt,
 175                         min:   min,
 176                         max:   max,
 177                         entry: b.Succs[entry].b,
 178                         flags: flags,
 179                 })
 180                 b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
 181         }
 182
 183         return iv
 184 }
 185
 186 func dropAdd64(v *Value) (*Value, int64) {
 187         if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 {
 188                 return v.Args[1], v.Args[0].AuxInt
 189         }
 190         if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 {
 191                 return v.Args[0], v.Args[1].AuxInt
 192         }
 193         return v, 0
 194 }
 195
 196 func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
 197         mb1, mb2 := "[", "]"
 198         if flags&indVarMinExc != 0 {
 199                 mb1 = "("
 200         }
 201         if flags&indVarMaxInc == 0 {
 202                 mb2 = ")"
 203         }
 204
 205         mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
 206         if !min.isGenericIntConst() {
 207                 if b.Func.pass.debug >= 2 {
 208                         mlim1 = fmt.Sprint(min)
 209                 } else {
 210                         mlim1 = "?"
 211                 }
 212         }
 213         if !max.isGenericIntConst() {
 214                 if b.Func.pass.debug >= 2 {
 215                         mlim2 = fmt.Sprint(max)
 216                 } else {
 217                         mlim2 = "?"
 218                 }
 219         }
 220         extra := ""
 221         if b.Func.pass.debug >= 2 {
 222                 extra = fmt.Sprintf(" (%s)", i)
 223         }
 224         b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
 225 }