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 // findIndVar finds induction variables in a function. 33 // 34 // Look for variables and blocks that satisfy the following 35 // 36 // loop: 37 // ind = (Phi min nxt), 38 // if ind < max 39 // then goto enter_loop 40 // else goto exit_loop 41 // 42 // enter_loop: 43 // do something 44 // nxt = inc + ind 45 // goto loop 46 // 47 // exit_loop: 48 // 49 // 50 // TODO: handle 32 bit operations 51 func findIndVar(f *Func) []indVar { 52 var iv []indVar 53 sdom := f.sdom() 54 55 for _, b := range f.Blocks { 56 if b.Kind != BlockIf || len(b.Preds) != 2 { 57 continue 58 } 59 60 var flags indVarFlags 61 var ind, max *Value // induction, and maximum 62 63 // Check thet the control if it either ind </<= max or max >/>= ind. 64 // TODO: Handle 32-bit comparisons. 65 // TODO: Handle unsigned comparisons? 66 switch b.Control.Op { 67 case OpLeq64: 68 flags |= indVarMaxInc 69 fallthrough 70 case OpLess64: 71 ind, max = b.Control.Args[0], b.Control.Args[1] 72 case OpGeq64: 73 flags |= indVarMaxInc 74 fallthrough 75 case OpGreater64: 76 ind, max = b.Control.Args[1], b.Control.Args[0] 77 default: 78 continue 79 } 80 81 // See if the arguments are reversed (i < len() <=> len() > i) 82 less := true 83 if max.Op == OpPhi { 84 ind, max = max, ind 85 less = false 86 } 87 88 // Check that the induction variable is a phi that depends on itself. 89 if ind.Op != OpPhi { 90 continue 91 } 92 93 // Extract min and nxt knowing that nxt is an addition (e.g. Add64). 94 var min, nxt *Value // minimum, and next value 95 if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) { 96 min, nxt = ind.Args[1], n 97 } else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) { 98 min, nxt = ind.Args[0], n 99 } else { 100 // Not a recognized induction variable. 101 continue 102 } 103 104 var inc *Value 105 if nxt.Args[0] == ind { // nxt = ind + inc 106 inc = nxt.Args[1] 107 } else if nxt.Args[1] == ind { // nxt = inc + ind 108 inc = nxt.Args[0] 109 } else { 110 panic("unreachable") // one of the cases must be true from the above. 111 } 112 113 // Expect the increment to be a nonzero constant. 114 if inc.Op != OpConst64 { 115 continue 116 } 117 step := inc.AuxInt 118 if step == 0 { 119 continue 120 } 121 122 // Increment sign must match comparison direction. 123 // When incrementing, the termination comparison must be ind </<= max. 124 // When decrementing, the termination comparison must be ind >/>= max. 125 // See issue 26116. 126 if step > 0 && !less { 127 continue 128 } 129 if step < 0 && less { 130 continue 131 } 132 133 // If the increment is negative, swap min/max and their flags 134 if step < 0 { 135 min, max = max, min 136 oldf := flags 137 flags = indVarMaxInc 138 if oldf&indVarMaxInc == 0 { 139 flags |= indVarMinExc 140 } 141 step = -step 142 } 143 144 // Up to now we extracted the induction variable (ind), 145 // the increment delta (inc), the temporary sum (nxt), 146 // the mininum value (min) and the maximum value (max). 147 // 148 // We also know that ind has the form (Phi min nxt) where 149 // nxt is (Add inc nxt) which means: 1) inc dominates nxt 150 // and 2) there is a loop starting at inc and containing nxt. 151 // 152 // We need to prove that the induction variable is incremented 153 // only when it's smaller than the maximum value. 154 // Two conditions must happen listed below to accept ind 155 // as an induction variable. 156 157 // First condition: loop entry has a single predecessor, which 158 // is the header block. This implies that b.Succs[0] is 159 // reached iff ind < max. 160 if len(b.Succs[0].b.Preds) != 1 { 161 // b.Succs[1] must exit the loop. 162 continue 163 } 164 165 // Second condition: b.Succs[0] dominates nxt so that 166 // nxt is computed when inc < max, meaning nxt <= max. 167 if !sdom.isAncestorEq(b.Succs[0].b, nxt.Block) { 168 // inc+ind can only be reached through the branch that enters the loop. 169 continue 170 } 171 172 // We can only guarantee that the loop runs within limits of induction variable 173 // if (one of) 174 // (1) the increment is ±1 175 // (2) the limits are constants 176 // (3) loop is of the form k0 upto Known_not_negative-k inclusive, step <= k 177 // (4) loop is of the form k0 upto Known_not_negative-k exclusive, step <= k+1 178 // (5) loop is of the form Known_not_negative downto k0, minint+step < k0 179 if step > 1 { 180 ok := false 181 if min.Op == OpConst64 && max.Op == OpConst64 { 182 if max.AuxInt > min.AuxInt && max.AuxInt%step == min.AuxInt%step { // handle overflow 183 ok = true 184 } 185 } 186 // Handle induction variables of these forms. 187 // KNN is known-not-negative. 188 // SIGNED ARITHMETIC ONLY. (see switch on b.Control.Op above) 189 // Possibilitis for KNN are len and cap; perhaps we can infer others. 190 // for i := 0; i <= KNN-k ; i += k 191 // for i := 0; i < KNN-(k-1); i += k 192 // Also handle decreasing. 193 194 // "Proof" copied from https://go-review.googlesource.com/c/go/+/104041/10/src/cmd/compile/internal/ssa/loopbce.go#164 195 // 196 // In the case of 197 // // PC is Positive Constant 198 // L := len(A)-PC 199 // for i := 0; i < L; i = i+PC 200 // 201 // we know: 202 // 203 // 0 + PC does not over/underflow. 204 // len(A)-PC does not over/underflow 205 // maximum value for L is MaxInt-PC 206 // i < L <= MaxInt-PC means i + PC < MaxInt hence no overflow. 207 208 // To match in SSA: 209 // if (a) min.Op == OpConst64(k0) 210 // and (b) k0 >= MININT + step 211 // and (c) max.Op == OpSubtract(Op{StringLen,SliceLen,SliceCap}, k) 212 // or (c) max.Op == OpAdd(Op{StringLen,SliceLen,SliceCap}, -k) 213 // or (c) max.Op == Op{StringLen,SliceLen,SliceCap} 214 // and (d) if upto loop, require indVarMaxInc && step <= k or !indVarMaxInc && step-1 <= k 215 216 if min.Op == OpConst64 && min.AuxInt >= step+math.MinInt64 { 217 knn := max 218 k := int64(0) 219 var kArg *Value 220 221 switch max.Op { 222 case OpSub64: 223 knn = max.Args[0] 224 kArg = max.Args[1] 225 226 case OpAdd64: 227 knn = max.Args[0] 228 kArg = max.Args[1] 229 if knn.Op == OpConst64 { 230 knn, kArg = kArg, knn 231 } 232 } 233 switch knn.Op { 234 case OpSliceLen, OpStringLen, OpSliceCap: 235 default: 236 knn = nil 237 } 238 239 if kArg != nil && kArg.Op == OpConst64 { 240 k = kArg.AuxInt 241 if max.Op == OpAdd64 { 242 k = -k 243 } 244 } 245 if k >= 0 && knn != nil { 246 if inc.AuxInt > 0 { // increasing iteration 247 // The concern for the relation between step and k is to ensure that iv never exceeds knn 248 // i.e., iv < knn-(K-1) ==> iv + K <= knn; iv <= knn-K ==> iv +K < knn 249 if step <= k || flags&indVarMaxInc == 0 && step-1 == k { 250 ok = true 251 } 252 } else { // decreasing iteration 253 // Will be decrementing from max towards min; max is knn-k; will only attempt decrement if 254 // knn-k >[=] min; underflow is only a concern if min-step is not smaller than min. 255 // This all assumes signed integer arithmetic 256 // This is already assured by the test above: min.AuxInt >= step+math.MinInt64 257 ok = true 258 } 259 } 260 } 261 262 // TODO: other unrolling idioms 263 // for i := 0; i < KNN - KNN % k ; i += k 264 // for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2 265 // for i := 0; i < KNN&(-k) ; i += k // k a power of 2 266 267 if !ok { 268 continue 269 } 270 } 271 272 if f.pass.debug >= 1 { 273 printIndVar(b, ind, min, max, step, flags) 274 } 275 276 iv = append(iv, indVar{ 277 ind: ind, 278 min: min, 279 max: max, 280 entry: b.Succs[0].b, 281 flags: flags, 282 }) 283 b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max) 284 } 285 286 return iv 287 } 288 289 func dropAdd64(v *Value) (*Value, int64) { 290 if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 { 291 return v.Args[1], v.Args[0].AuxInt 292 } 293 if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 { 294 return v.Args[0], v.Args[1].AuxInt 295 } 296 return v, 0 297 } 298 299 func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) { 300 mb1, mb2 := "[", "]" 301 if flags&indVarMinExc != 0 { 302 mb1 = "(" 303 } 304 if flags&indVarMaxInc == 0 { 305 mb2 = ")" 306 } 307 308 mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt) 309 if !min.isGenericIntConst() { 310 if b.Func.pass.debug >= 2 { 311 mlim1 = fmt.Sprint(min) 312 } else { 313 mlim1 = "?" 314 } 315 } 316 if !max.isGenericIntConst() { 317 if b.Func.pass.debug >= 2 { 318 mlim2 = fmt.Sprint(max) 319 } else { 320 mlim2 = "?" 321 } 322 } 323 extra := "" 324 if b.Func.pass.debug >= 2 { 325 extra = fmt.Sprintf(" (%s)", i) 326 } 327 b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra) 328 } 329