1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py 2; RUN: opt -disable-output "-passes=print<scalar-evolution>" -S -scalar-evolution-classify-expressions=0 < %s 2>&1 | FileCheck %s 3 4; Every combination of 5; - starting at 0, 1, or %x 6; - steping by 1 or 2 7; - stopping at %n or ptr2 8; - using nsw, or not 9 10; Some of these represent missed opportunities. 11 12define void @foo(i4 %n) { 13; CHECK-LABEL: 'foo' 14; CHECK-NEXT: Determining loop execution counts for: @foo 15; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %n) 16; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 6 17; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + %n) 18; CHECK-NEXT: Loop %loop: Trip multiple is 1 19; 20entry: 21 %s = icmp sgt i4 %n, 0 22 br i1 %s, label %loop, label %exit 23loop: 24 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 25 %i.next = add i4 %i, 1 26 %t = icmp slt i4 %i.next, %n 27 br i1 %t, label %loop, label %exit 28exit: 29 ret void 30} 31 32define void @step2(i4 %n) { 33; CHECK-LABEL: 'step2' 34; CHECK-NEXT: Determining loop execution counts for: @step2 35; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 36; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count. 37; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count. 38; 39entry: 40 %s = icmp sgt i4 %n, 0 41 br i1 %s, label %loop, label %exit 42loop: 43 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 44 %i.next = add i4 %i, 2 45 %t = icmp slt i4 %i.next, %n 46 br i1 %t, label %loop, label %exit 47exit: 48 ret void 49} 50 51define void @start1(i4 %n) { 52; CHECK-LABEL: 'start1' 53; CHECK-NEXT: Determining loop execution counts for: @start1 54; CHECK-NEXT: Loop %loop: backedge-taken count is (-2 + (2 smax %n))<nsw> 55; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 5 56; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-2 + (2 smax %n))<nsw> 57; CHECK-NEXT: Loop %loop: Trip multiple is 1 58; 59entry: 60 %s = icmp sgt i4 %n, 0 61 br i1 %s, label %loop, label %exit 62loop: 63 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 64 %i.next = add i4 %i, 1 65 %t = icmp slt i4 %i.next, %n 66 br i1 %t, label %loop, label %exit 67exit: 68 ret void 69} 70 71define void @start1_step2(i4 %n) { 72; CHECK-LABEL: 'start1_step2' 73; CHECK-NEXT: Determining loop execution counts for: @start1_step2 74; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 75; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count. 76; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count. 77; 78entry: 79 %s = icmp sgt i4 %n, 0 80 br i1 %s, label %loop, label %exit 81loop: 82 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 83 %i.next = add i4 %i, 2 84 %t = icmp slt i4 %i.next, %n 85 br i1 %t, label %loop, label %exit 86exit: 87 ret void 88} 89 90define void @startx(i4 %n, i4 %x) { 91; CHECK-LABEL: 'startx' 92; CHECK-NEXT: Determining loop execution counts for: @startx 93; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) 94; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 -1 95; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) 96; CHECK-NEXT: Loop %loop: Trip multiple is 1 97; 98entry: 99 %s = icmp sgt i4 %n, 0 100 br i1 %s, label %loop, label %exit 101loop: 102 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 103 %i.next = add i4 %i, 1 104 %t = icmp slt i4 %i.next, %n 105 br i1 %t, label %loop, label %exit 106exit: 107 ret void 108} 109 110define void @startx_step2(i4 %n, i4 %x) { 111; CHECK-LABEL: 'startx_step2' 112; CHECK-NEXT: Determining loop execution counts for: @startx_step2 113; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 114; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count. 115; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count. 116; 117entry: 118 %s = icmp sgt i4 %n, 0 119 br i1 %s, label %loop, label %exit 120loop: 121 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 122 %i.next = add i4 %i, 2 123 %t = icmp slt i4 %i.next, %n 124 br i1 %t, label %loop, label %exit 125exit: 126 ret void 127} 128 129define void @nsw(i4 %n) { 130; CHECK-LABEL: 'nsw' 131; CHECK-NEXT: Determining loop execution counts for: @nsw 132; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %n) 133; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 6 134; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + %n) 135; CHECK-NEXT: Loop %loop: Trip multiple is 1 136; 137entry: 138 %s = icmp sgt i4 %n, 0 139 br i1 %s, label %loop, label %exit 140loop: 141 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 142 %i.next = add nsw i4 %i, 1 143 %t = icmp slt i4 %i.next, %n 144 br i1 %t, label %loop, label %exit 145exit: 146 ret void 147} 148 149; If %n is INT4_MAX, %i.next will wrap. The nsw bit says that the 150; result is undefined. Therefore, after the loop's second iteration, 151; we are free to assume that the loop exits. This is valid because: 152; (a) %i.next is a poison value after the second iteration, which can 153; also be considered an undef value. 154; (b) the return instruction enacts a side effect that is control 155; dependent on the poison value. 156; 157define void @nsw_step2(i4 %n) { 158; CHECK-LABEL: 'nsw_step2' 159; CHECK-NEXT: Determining loop execution counts for: @nsw_step2 160; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + %n) /u 2) 161; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2 162; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + %n) /u 2) 163; CHECK-NEXT: Loop %loop: Trip multiple is 1 164; 165entry: 166 %s = icmp sgt i4 %n, 0 167 br i1 %s, label %loop, label %exit 168loop: 169 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 170 %i.next = add nsw i4 %i, 2 171 %t = icmp slt i4 %i.next, %n 172 br i1 %t, label %loop, label %exit 173exit: 174 ret void 175} 176 177define void @nsw_start1(i4 %n) { 178; CHECK-LABEL: 'nsw_start1' 179; CHECK-NEXT: Determining loop execution counts for: @nsw_start1 180; CHECK-NEXT: Loop %loop: backedge-taken count is (-2 + (2 smax %n))<nsw> 181; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 5 182; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-2 + (2 smax %n))<nsw> 183; CHECK-NEXT: Loop %loop: Trip multiple is 1 184; 185entry: 186 %s = icmp sgt i4 %n, 0 187 br i1 %s, label %loop, label %exit 188loop: 189 %i = phi i4 [ 1, %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 197define void @nsw_start1_step2(i4 %n) { 198; CHECK-LABEL: 'nsw_start1_step2' 199; CHECK-NEXT: Determining loop execution counts for: @nsw_start1_step2 200; CHECK-NEXT: Loop %loop: backedge-taken count is ((-2 + (3 smax %n))<nsw> /u 2) 201; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2 202; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-2 + (3 smax %n))<nsw> /u 2) 203; CHECK-NEXT: Loop %loop: Trip multiple is 1 204; 205entry: 206 %s = icmp sgt i4 %n, 0 207 br i1 %s, label %loop, label %exit 208loop: 209 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 210 %i.next = add nsw i4 %i, 2 211 %t = icmp slt i4 %i.next, %n 212 br i1 %t, label %loop, label %exit 213exit: 214 ret void 215} 216 217define void @nsw_startx(i4 %n, i4 %x) { 218; CHECK-LABEL: 'nsw_startx' 219; CHECK-NEXT: Determining loop execution counts for: @nsw_startx 220; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) 221; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 -1 222; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) 223; CHECK-NEXT: Loop %loop: Trip multiple is 1 224; 225entry: 226 %s = icmp sgt i4 %n, 0 227 br i1 %s, label %loop, label %exit 228loop: 229 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 230 %i.next = add nsw i4 %i, 1 231 %t = icmp slt i4 %i.next, %n 232 br i1 %t, label %loop, label %exit 233exit: 234 ret void 235} 236 237define void @nsw_startx_step2(i4 %n, i4 %x) { 238; CHECK-LABEL: 'nsw_startx_step2' 239; CHECK-NEXT: Determining loop execution counts for: @nsw_startx_step2 240; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2) 241; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 7 242; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2) 243; CHECK-NEXT: Loop %loop: Trip multiple is 1 244; 245entry: 246 %s = icmp sgt i4 %n, 0 247 br i1 %s, label %loop, label %exit 248loop: 249 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 250 %i.next = add nsw i4 %i, 2 251 %t = icmp slt i4 %i.next, %n 252 br i1 %t, label %loop, label %exit 253exit: 254 ret void 255} 256 257define void @even(i4 %n) { 258; CHECK-LABEL: 'even' 259; CHECK-NEXT: Determining loop execution counts for: @even 260; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (2 * %n)) 261; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 5 262; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (2 * %n)) 263; CHECK-NEXT: Loop %loop: Trip multiple is 2 264; 265entry: 266 %m = shl i4 %n, 1 267 %s = icmp sgt i4 %m, 0 268 br i1 %s, label %loop, label %exit 269loop: 270 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 271 %i.next = add i4 %i, 1 272 %t = icmp slt i4 %i.next, %m 273 br i1 %t, label %loop, label %exit 274exit: 275 ret void 276} 277 278define void @even_step2(i4 %n) { 279; CHECK-LABEL: 'even_step2' 280; CHECK-NEXT: Determining loop execution counts for: @even_step2 281; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2) 282; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2 283; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (2 * %n)) /u 2) 284; CHECK-NEXT: Loop %loop: Trip multiple is 1 285; 286entry: 287 %m = shl i4 %n, 1 288 %s = icmp sgt i4 %m, 0 289 br i1 %s, label %loop, label %exit 290loop: 291 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 292 %i.next = add i4 %i, 2 293 %t = icmp slt i4 %i.next, %m 294 br i1 %t, label %loop, label %exit 295exit: 296 ret void 297} 298 299define void @even_start1(i4 %n) { 300; CHECK-LABEL: 'even_start1' 301; CHECK-NEXT: Determining loop execution counts for: @even_start1 302; CHECK-NEXT: Loop %loop: backedge-taken count is (-2 + (2 * %n)) 303; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 4 304; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-2 + (2 * %n)) 305; CHECK-NEXT: Loop %loop: Trip multiple is 1 306; 307entry: 308 %m = shl i4 %n, 1 309 %s = icmp sgt i4 %m, 0 310 br i1 %s, label %loop, label %exit 311loop: 312 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 313 %i.next = add i4 %i, 1 314 %t = icmp slt i4 %i.next, %m 315 br i1 %t, label %loop, label %exit 316exit: 317 ret void 318} 319 320define void @even_start1_step2(i4 %n) { 321; CHECK-LABEL: 'even_start1_step2' 322; CHECK-NEXT: Determining loop execution counts for: @even_start1_step2 323; CHECK-NEXT: Loop %loop: backedge-taken count is ((-2 + (2 * %n)) /u 2) 324; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2 325; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-2 + (2 * %n)) /u 2) 326; CHECK-NEXT: Loop %loop: Trip multiple is 1 327; 328entry: 329 %m = shl i4 %n, 1 330 %s = icmp sgt i4 %m, 0 331 br i1 %s, label %loop, label %exit 332loop: 333 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 334 %i.next = add i4 %i, 2 335 %t = icmp slt i4 %i.next, %m 336 br i1 %t, label %loop, label %exit 337exit: 338 ret void 339} 340 341define void @even_startx(i4 %n, i4 %x) { 342; CHECK-LABEL: 'even_startx' 343; CHECK-NEXT: Determining loop execution counts for: @even_startx 344; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) 345; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 -2 346; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) 347; CHECK-NEXT: Loop %loop: Trip multiple is 1 348; 349entry: 350 %m = shl i4 %n, 1 351 %s = icmp sgt i4 %m, 0 352 br i1 %s, label %loop, label %exit 353loop: 354 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 355 %i.next = add i4 %i, 1 356 %t = icmp slt i4 %i.next, %m 357 br i1 %t, label %loop, label %exit 358exit: 359 ret void 360} 361 362define void @even_startx_step2(i4 %n, i4 %x) { 363; CHECK-LABEL: 'even_startx_step2' 364; CHECK-NEXT: Determining loop execution counts for: @even_startx_step2 365; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) 366; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 7 367; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) 368; CHECK-NEXT: Loop %loop: Trip multiple is 1 369; 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 [ %x, %entry ], [ %i.next, %loop ] 376 %i.next = add 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 383define void @even_nsw(i4 %n) { 384; CHECK-LABEL: 'even_nsw' 385; CHECK-NEXT: Determining loop execution counts for: @even_nsw 386; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (2 * %n)) 387; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 5 388; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (2 * %n)) 389; CHECK-NEXT: Loop %loop: Trip multiple is 2 390; 391entry: 392 %m = shl i4 %n, 1 393 %s = icmp sgt i4 %m, 0 394 br i1 %s, label %loop, label %exit 395loop: 396 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 397 %i.next = add nsw i4 %i, 1 398 %t = icmp slt i4 %i.next, %m 399 br i1 %t, label %loop, label %exit 400exit: 401 ret void 402} 403 404define void @even_nsw_step2(i4 %n) { 405; CHECK-LABEL: 'even_nsw_step2' 406; CHECK-NEXT: Determining loop execution counts for: @even_nsw_step2 407; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2) 408; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2 409; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (2 * %n)) /u 2) 410; CHECK-NEXT: Loop %loop: Trip multiple is 1 411; 412entry: 413 %m = shl i4 %n, 1 414 %s = icmp sgt i4 %m, 0 415 br i1 %s, label %loop, label %exit 416loop: 417 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ] 418 %i.next = add nsw i4 %i, 2 419 %t = icmp slt i4 %i.next, %m 420 br i1 %t, label %loop, label %exit 421exit: 422 ret void 423} 424 425define void @even_nsw_start1(i4 %n) { 426; CHECK-LABEL: 'even_nsw_start1' 427; CHECK-NEXT: Determining loop execution counts for: @even_nsw_start1 428; CHECK-NEXT: Loop %loop: backedge-taken count is (-2 + (2 * %n)) 429; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 4 430; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-2 + (2 * %n)) 431; CHECK-NEXT: Loop %loop: Trip multiple is 1 432; 433entry: 434 %m = shl i4 %n, 1 435 %s = icmp sgt i4 %m, 0 436 br i1 %s, label %loop, label %exit 437loop: 438 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 439 %i.next = add nsw i4 %i, 1 440 %t = icmp slt i4 %i.next, %m 441 br i1 %t, label %loop, label %exit 442exit: 443 ret void 444} 445 446define void @even_nsw_start1_step2(i4 %n) { 447; CHECK-LABEL: 'even_nsw_start1_step2' 448; CHECK-NEXT: Determining loop execution counts for: @even_nsw_start1_step2 449; CHECK-NEXT: Loop %loop: backedge-taken count is ((-2 + (2 * %n)) /u 2) 450; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2 451; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-2 + (2 * %n)) /u 2) 452; CHECK-NEXT: Loop %loop: Trip multiple is 1 453; 454entry: 455 %m = shl i4 %n, 1 456 %s = icmp sgt i4 %m, 0 457 br i1 %s, label %loop, label %exit 458loop: 459 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ] 460 %i.next = add nsw i4 %i, 2 461 %t = icmp slt i4 %i.next, %m 462 br i1 %t, label %loop, label %exit 463exit: 464 ret void 465} 466 467define void @even_nsw_startx(i4 %n, i4 %x) { 468; CHECK-LABEL: 'even_nsw_startx' 469; CHECK-NEXT: Determining loop execution counts for: @even_nsw_startx 470; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) 471; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 -2 472; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) 473; CHECK-NEXT: Loop %loop: Trip multiple is 1 474; 475entry: 476 %m = shl i4 %n, 1 477 %s = icmp sgt i4 %m, 0 478 br i1 %s, label %loop, label %exit 479loop: 480 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 481 %i.next = add nsw i4 %i, 1 482 %t = icmp slt i4 %i.next, %m 483 br i1 %t, label %loop, label %exit 484exit: 485 ret void 486} 487 488define void @even_nsw_startx_step2(i4 %n, i4 %x) { 489; CHECK-LABEL: 'even_nsw_startx_step2' 490; CHECK-NEXT: Determining loop execution counts for: @even_nsw_startx_step2 491; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) 492; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 7 493; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) 494; CHECK-NEXT: Loop %loop: Trip multiple is 1 495; 496entry: 497 %m = shl i4 %n, 1 498 %s = icmp sgt i4 %m, 0 499 br i1 %s, label %loop, label %exit 500loop: 501 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ] 502 %i.next = add nsw i4 %i, 2 503 %t = icmp slt i4 %i.next, %m 504 br i1 %t, label %loop, label %exit 505exit: 506 ret void 507} 508