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 14define void @foo(i4 %n) { 15entry: 16 %s = icmp sgt i4 %n, 0 17 br i1 %s, label %loop, label %exit 18loop: 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 23exit: 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. 30define void @step2(i4 %n) { 31entry: 32 %s = icmp sgt i4 %n, 0 33 br i1 %s, label %loop, label %exit 34loop: 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 39exit: 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 46define void @start1(i4 %n) { 47entry: 48 %s = icmp sgt i4 %n, 0 49 br i1 %s, label %loop, label %exit 50loop: 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 55exit: 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. 62define void @start1_step2(i4 %n) { 63entry: 64 %s = icmp sgt i4 %n, 0 65 br i1 %s, label %loop, label %exit 66loop: 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 71exit: 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 78define void @startx(i4 %n, i4 %x) { 79entry: 80 %s = icmp sgt i4 %n, 0 81 br i1 %s, label %loop, label %exit 82loop: 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 87exit: 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. 94define void @startx_step2(i4 %n, i4 %x) { 95entry: 96 %s = icmp sgt i4 %n, 0 97 br i1 %s, label %loop, label %exit 98loop: 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 103exit: 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 110define void @nsw(i4 %n) { 111entry: 112 %s = icmp sgt i4 %n, 0 113 br i1 %s, label %loop, label %exit 114loop: 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 119exit: 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 135define void @nsw_step2(i4 %n) { 136entry: 137 %s = icmp sgt i4 %n, 0 138 br i1 %s, label %loop, label %exit 139loop: 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 144exit: 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 152define void @nsw_start1(i4 %n) { 153entry: 154 %s = icmp sgt i4 %n, 0 155 br i1 %s, label %loop, label %exit 156loop: 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 161exit: 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 168define void @nsw_start1_step2(i4 %n) { 169entry: 170 %s = icmp sgt i4 %n, 0 171 br i1 %s, label %loop, label %exit 172loop: 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 177exit: 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 184define void @nsw_startx(i4 %n, i4 %x) { 185entry: 186 %s = icmp sgt i4 %n, 0 187 br i1 %s, label %loop, label %exit 188loop: 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 193exit: 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 200define void @nsw_startx_step2(i4 %n, i4 %x) { 201entry: 202 %s = icmp sgt i4 %n, 0 203 br i1 %s, label %loop, label %exit 204loop: 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 209exit: 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 216define void @even(i4 %n) { 217entry: 218 %m = shl i4 %n, 1 219 %s = icmp sgt i4 %m, 0 220 br i1 %s, label %loop, label %exit 221loop: 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 226exit: 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 233define void @even_step2(i4 %n) { 234entry: 235 %m = shl i4 %n, 1 236 %s = icmp sgt i4 %m, 0 237 br i1 %s, label %loop, label %exit 238loop: 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 243exit: 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 250define void @even_start1(i4 %n) { 251entry: 252 %m = shl i4 %n, 1 253 %s = icmp sgt i4 %m, 0 254 br i1 %s, label %loop, label %exit 255loop: 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 260exit: 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 267define void @even_start1_step2(i4 %n) { 268entry: 269 %m = shl i4 %n, 1 270 %s = icmp sgt i4 %m, 0 271 br i1 %s, label %loop, label %exit 272loop: 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 277exit: 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 284define void @even_startx(i4 %n, i4 %x) { 285entry: 286 %m = shl i4 %n, 1 287 %s = icmp sgt i4 %m, 0 288 br i1 %s, label %loop, label %exit 289loop: 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 294exit: 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 301define void @even_startx_step2(i4 %n, i4 %x) { 302entry: 303 %m = shl i4 %n, 1 304 %s = icmp sgt i4 %m, 0 305 br i1 %s, label %loop, label %exit 306loop: 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 311exit: 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 318define void @even_nsw(i4 %n) { 319entry: 320 %m = shl i4 %n, 1 321 %s = icmp sgt i4 %m, 0 322 br i1 %s, label %loop, label %exit 323loop: 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 328exit: 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 335define void @even_nsw_step2(i4 %n) { 336entry: 337 %m = shl i4 %n, 1 338 %s = icmp sgt i4 %m, 0 339 br i1 %s, label %loop, label %exit 340loop: 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 345exit: 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 352define void @even_nsw_start1(i4 %n) { 353entry: 354 %m = shl i4 %n, 1 355 %s = icmp sgt i4 %m, 0 356 br i1 %s, label %loop, label %exit 357loop: 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 362exit: 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 369define void @even_nsw_start1_step2(i4 %n) { 370entry: 371 %m = shl i4 %n, 1 372 %s = icmp sgt i4 %m, 0 373 br i1 %s, label %loop, label %exit 374loop: 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 379exit: 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 386define void @even_nsw_startx(i4 %n, i4 %x) { 387entry: 388 %m = shl i4 %n, 1 389 %s = icmp sgt i4 %m, 0 390 br i1 %s, label %loop, label %exit 391loop: 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 396exit: 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 403define void @even_nsw_startx_step2(i4 %n, i4 %x) { 404entry: 405 %m = shl i4 %n, 1 406 %s = icmp sgt i4 %m, 0 407 br i1 %s, label %loop, label %exit 408loop: 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 413exit: 414 ret void 415} 416