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