1 ; RUN: opt -analyze -scalar-evolution -S < %s | FileCheck %s 2 3 ; Every combination of 4 ; - starting at 0, 1, or %x 5 ; - steping by 1 or 2 6 ; - stopping at %n or %n*2 7 ; - using nsw, or not 8 9 ; Some of these represent missed opportunities. 10 11 ; CHECK: Determining loop execution counts for: @foo 12 ; CHECK: Loop %loop: backedge-taken count is (-1 + %n) 13 ; CHECK: Loop %loop: max backedge-taken count is 6 14 define void @foo(i4 %n) { 15 entry: 16 %s = icmp sgt i4 %n, 0 17 br i1 %s, label %loop, label %exit 18 loop: 19 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 20 %i.next = add i4 %i, 1 21 %t = icmp slt i4 %i.next, %n 22 br i1 %t, label %loop, label %exit 23 exit: 24 ret void 25 } 26 27 ; CHECK: Determining loop execution counts for: @step2 28 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 29 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 30 define void @step2(i4 %n) { 31 entry: 32 %s = icmp sgt i4 %n, 0 33 br i1 %s, label %loop, label %exit 34 loop: 35 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 36 %i.next = add i4 %i, 2 37 %t = icmp slt i4 %i.next, %n 38 br i1 %t, label %loop, label %exit 39 exit: 40 ret void 41 } 42 43 ; CHECK: Determining loop execution counts for: @start1 44 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n)) 45 ; CHECK: Loop %loop: max backedge-taken count is 5 46 define void @start1(i4 %n) { 47 entry: 48 %s = icmp sgt i4 %n, 0 49 br i1 %s, label %loop, label %exit 50 loop: 51 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 52 %i.next = add i4 %i, 1 53 %t = icmp slt i4 %i.next, %n 54 br i1 %t, label %loop, label %exit 55 exit: 56 ret void 57 } 58 59 ; CHECK: Determining loop execution counts for: @start1_step2 60 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 61 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 62 define void @start1_step2(i4 %n) { 63 entry: 64 %s = icmp sgt i4 %n, 0 65 br i1 %s, label %loop, label %exit 66 loop: 67 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 68 %i.next = add i4 %i, 2 69 %t = icmp slt i4 %i.next, %n 70 br i1 %t, label %loop, label %exit 71 exit: 72 ret void 73 } 74 75 ; CHECK: Determining loop execution counts for: @startx 76 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) 77 ; CHECK: Loop %loop: max backedge-taken count is -1 78 define void @startx(i4 %n, i4 %x) { 79 entry: 80 %s = icmp sgt i4 %n, 0 81 br i1 %s, label %loop, label %exit 82 loop: 83 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 84 %i.next = add i4 %i, 1 85 %t = icmp slt i4 %i.next, %n 86 br i1 %t, label %loop, label %exit 87 exit: 88 ret void 89 } 90 91 ; CHECK: Determining loop execution counts for: @startx_step2 92 ; CHECK: Loop %loop: Unpredictable backedge-taken count. 93 ; CHECK: Loop %loop: Unpredictable max backedge-taken count. 94 define void @startx_step2(i4 %n, i4 %x) { 95 entry: 96 %s = icmp sgt i4 %n, 0 97 br i1 %s, label %loop, label %exit 98 loop: 99 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 100 %i.next = add i4 %i, 2 101 %t = icmp slt i4 %i.next, %n 102 br i1 %t, label %loop, label %exit 103 exit: 104 ret void 105 } 106 107 ; CHECK: Determining loop execution counts for: @nsw 108 ; CHECK: Loop %loop: backedge-taken count is (-1 + %n) 109 ; CHECK: Loop %loop: max backedge-taken count is 6 110 define void @nsw(i4 %n) { 111 entry: 112 %s = icmp sgt i4 %n, 0 113 br i1 %s, label %loop, label %exit 114 loop: 115 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 116 %i.next = add nsw i4 %i, 1 117 %t = icmp slt i4 %i.next, %n 118 br i1 %t, label %loop, label %exit 119 exit: 120 ret void 121 } 122 123 ; If %n is INT4_MAX, %i.next will wrap. The nsw bit says that the 124 ; result is undefined. Therefore, after the loop's second iteration, 125 ; we are free to assume that the loop exits. This is valid because: 126 ; (a) %i.next is a poison value after the second iteration, which can 127 ; also be considered an undef value. 128 ; (b) the return instruction enacts a side effect that is control 129 ; dependent on the poison value. 130 ; 131 ; CHECK-LABEL: nsw_step2 132 ; CHECK: Determining loop execution counts for: @nsw_step2 133 ; CHECK: Loop %loop: backedge-taken count is ((-1 + %n) /u 2) 134 ; CHECK: Loop %loop: max backedge-taken count is 2 135 define void @nsw_step2(i4 %n) { 136 entry: 137 %s = icmp sgt i4 %n, 0 138 br i1 %s, label %loop, label %exit 139 loop: 140 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 141 %i.next = add nsw i4 %i, 2 142 %t = icmp slt i4 %i.next, %n 143 br i1 %t, label %loop, label %exit 144 exit: 145 ret void 146 } 147 148 ; CHECK-LABEL: nsw_start1 149 ; CHECK: Determining loop execution counts for: @nsw_start1 150 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n)) 151 ; CHECK: Loop %loop: max backedge-taken count is 5 152 define void @nsw_start1(i4 %n) { 153 entry: 154 %s = icmp sgt i4 %n, 0 155 br i1 %s, label %loop, label %exit 156 loop: 157 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 158 %i.next = add nsw i4 %i, 1 159 %t = icmp slt i4 %i.next, %n 160 br i1 %t, label %loop, label %exit 161 exit: 162 ret void 163 } 164 165 ; CHECK: Determining loop execution counts for: @nsw_start1_step2 166 ; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax %n)) /u 2) 167 ; CHECK: Loop %loop: max backedge-taken count is 2 168 define void @nsw_start1_step2(i4 %n) { 169 entry: 170 %s = icmp sgt i4 %n, 0 171 br i1 %s, label %loop, label %exit 172 loop: 173 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 174 %i.next = add nsw i4 %i, 2 175 %t = icmp slt i4 %i.next, %n 176 br i1 %t, label %loop, label %exit 177 exit: 178 ret void 179 } 180 181 ; CHECK: Determining loop execution counts for: @nsw_startx 182 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) 183 ; CHECK: Loop %loop: max backedge-taken count is -1 184 define void @nsw_startx(i4 %n, i4 %x) { 185 entry: 186 %s = icmp sgt i4 %n, 0 187 br i1 %s, label %loop, label %exit 188 loop: 189 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 190 %i.next = add nsw i4 %i, 1 191 %t = icmp slt i4 %i.next, %n 192 br i1 %t, label %loop, label %exit 193 exit: 194 ret void 195 } 196 197 ; CHECK: Determining loop execution counts for: @nsw_startx_step2 198 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2) 199 ; CHECK: Loop %loop: max backedge-taken count is 7 200 define void @nsw_startx_step2(i4 %n, i4 %x) { 201 entry: 202 %s = icmp sgt i4 %n, 0 203 br i1 %s, label %loop, label %exit 204 loop: 205 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 206 %i.next = add nsw i4 %i, 2 207 %t = icmp slt i4 %i.next, %n 208 br i1 %t, label %loop, label %exit 209 exit: 210 ret void 211 } 212 213 ; CHECK: Determining loop execution counts for: @even 214 ; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n)) 215 ; CHECK: Loop %loop: max backedge-taken count is 5 216 define void @even(i4 %n) { 217 entry: 218 %m = shl i4 %n, 1 219 %s = icmp sgt i4 %m, 0 220 br i1 %s, label %loop, label %exit 221 loop: 222 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 223 %i.next = add i4 %i, 1 224 %t = icmp slt i4 %i.next, %m 225 br i1 %t, label %loop, label %exit 226 exit: 227 ret void 228 } 229 230 ; CHECK: Determining loop execution counts for: @even_step2 231 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2) 232 ; CHECK: Loop %loop: max backedge-taken count is 2 233 define void @even_step2(i4 %n) { 234 entry: 235 %m = shl i4 %n, 1 236 %s = icmp sgt i4 %m, 0 237 br i1 %s, label %loop, label %exit 238 loop: 239 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 240 %i.next = add i4 %i, 2 241 %t = icmp slt i4 %i.next, %m 242 br i1 %t, label %loop, label %exit 243 exit: 244 ret void 245 } 246 247 ; CHECK: Determining loop execution counts for: @even_start1 248 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n))) 249 ; CHECK: Loop %loop: max backedge-taken count is 4 250 define void @even_start1(i4 %n) { 251 entry: 252 %m = shl i4 %n, 1 253 %s = icmp sgt i4 %m, 0 254 br i1 %s, label %loop, label %exit 255 loop: 256 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 257 %i.next = add i4 %i, 1 258 %t = icmp slt i4 %i.next, %m 259 br i1 %t, label %loop, label %exit 260 exit: 261 ret void 262 } 263 264 ; CHECK: Determining loop execution counts for: @even_start1_step2 265 ; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2) 266 ; CHECK: Loop %loop: max backedge-taken count is 2 267 define void @even_start1_step2(i4 %n) { 268 entry: 269 %m = shl i4 %n, 1 270 %s = icmp sgt i4 %m, 0 271 br i1 %s, label %loop, label %exit 272 loop: 273 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 274 %i.next = add i4 %i, 2 275 %t = icmp slt i4 %i.next, %m 276 br i1 %t, label %loop, label %exit 277 exit: 278 ret void 279 } 280 281 ; CHECK: Determining loop execution counts for: @even_startx 282 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) 283 ; CHECK: Loop %loop: max backedge-taken count is -2 284 define void @even_startx(i4 %n, i4 %x) { 285 entry: 286 %m = shl i4 %n, 1 287 %s = icmp sgt i4 %m, 0 288 br i1 %s, label %loop, label %exit 289 loop: 290 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 291 %i.next = add i4 %i, 1 292 %t = icmp slt i4 %i.next, %m 293 br i1 %t, label %loop, label %exit 294 exit: 295 ret void 296 } 297 298 ; CHECK: Determining loop execution counts for: @even_startx_step2 299 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) 300 ; CHECK: Loop %loop: max backedge-taken count is 7 301 define void @even_startx_step2(i4 %n, i4 %x) { 302 entry: 303 %m = shl i4 %n, 1 304 %s = icmp sgt i4 %m, 0 305 br i1 %s, label %loop, label %exit 306 loop: 307 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 308 %i.next = add i4 %i, 2 309 %t = icmp slt i4 %i.next, %m 310 br i1 %t, label %loop, label %exit 311 exit: 312 ret void 313 } 314 315 ; CHECK: Determining loop execution counts for: @even_nsw 316 ; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n)) 317 ; CHECK: Loop %loop: max backedge-taken count is 5 318 define void @even_nsw(i4 %n) { 319 entry: 320 %m = shl i4 %n, 1 321 %s = icmp sgt i4 %m, 0 322 br i1 %s, label %loop, label %exit 323 loop: 324 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 325 %i.next = add nsw i4 %i, 1 326 %t = icmp slt i4 %i.next, %m 327 br i1 %t, label %loop, label %exit 328 exit: 329 ret void 330 } 331 332 ; CHECK: Determining loop execution counts for: @even_nsw_step2 333 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2) 334 ; CHECK: Loop %loop: max backedge-taken count is 2 335 define void @even_nsw_step2(i4 %n) { 336 entry: 337 %m = shl i4 %n, 1 338 %s = icmp sgt i4 %m, 0 339 br i1 %s, label %loop, label %exit 340 loop: 341 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 342 %i.next = add nsw i4 %i, 2 343 %t = icmp slt i4 %i.next, %m 344 br i1 %t, label %loop, label %exit 345 exit: 346 ret void 347 } 348 349 ; CHECK: Determining loop execution counts for: @even_nsw_start1 350 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n))) 351 ; CHECK: Loop %loop: max backedge-taken count is 4 352 define void @even_nsw_start1(i4 %n) { 353 entry: 354 %m = shl i4 %n, 1 355 %s = icmp sgt i4 %m, 0 356 br i1 %s, label %loop, label %exit 357 loop: 358 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 359 %i.next = add nsw i4 %i, 1 360 %t = icmp slt i4 %i.next, %m 361 br i1 %t, label %loop, label %exit 362 exit: 363 ret void 364 } 365 366 ; CHECK: Determining loop execution counts for: @even_nsw_start1_step2 367 ; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2) 368 ; CHECK: Loop %loop: max backedge-taken count is 2 369 define void @even_nsw_start1_step2(i4 %n) { 370 entry: 371 %m = shl i4 %n, 1 372 %s = icmp sgt i4 %m, 0 373 br i1 %s, label %loop, label %exit 374 loop: 375 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 376 %i.next = add nsw i4 %i, 2 377 %t = icmp slt i4 %i.next, %m 378 br i1 %t, label %loop, label %exit 379 exit: 380 ret void 381 } 382 383 ; CHECK: Determining loop execution counts for: @even_nsw_startx 384 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) 385 ; CHECK: Loop %loop: max backedge-taken count is -2 386 define void @even_nsw_startx(i4 %n, i4 %x) { 387 entry: 388 %m = shl i4 %n, 1 389 %s = icmp sgt i4 %m, 0 390 br i1 %s, label %loop, label %exit 391 loop: 392 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 393 %i.next = add nsw i4 %i, 1 394 %t = icmp slt i4 %i.next, %m 395 br i1 %t, label %loop, label %exit 396 exit: 397 ret void 398 } 399 400 ; CHECK: Determining loop execution counts for: @even_nsw_startx_step2 401 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) 402 ; CHECK: Loop %loop: max backedge-taken count is 7 403 define void @even_nsw_startx_step2(i4 %n, i4 %x) { 404 entry: 405 %m = shl i4 %n, 1 406 %s = icmp sgt i4 %m, 0 407 br i1 %s, label %loop, label %exit 408 loop: 409 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 410 %i.next = add nsw i4 %i, 2 411 %t = icmp slt i4 %i.next, %m 412 br i1 %t, label %loop, label %exit 413 exit: 414 ret void 415 } 416
