1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 4 2; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s 3 4; ScalarEvolution should be able to understand the loop and eliminate the casts. 5 6 7define void @foo(ptr nocapture %d, i32 %n) nounwind { 8; CHECK-LABEL: 'foo' 9; CHECK-NEXT: Determining loop execution counts for: @foo 10; CHECK-NEXT: Loop %bb: backedge-taken count is (-1 + %n) 11; CHECK-NEXT: Loop %bb: constant max backedge-taken count is i32 2147483646 12; CHECK-NEXT: Loop %bb: symbolic max backedge-taken count is (-1 + %n) 13; CHECK-NEXT: Loop %bb: Trip multiple is 1 14; 15entry: 16 %0 = icmp sgt i32 %n, 0 ; <i1> [#uses=1] 17 br i1 %0, label %bb.nph, label %return 18 19bb.nph: ; preds = %entry 20 br label %bb 21 22bb: ; preds = %bb1, %bb.nph 23 %i.02 = phi i32 [ %5, %bb1 ], [ 0, %bb.nph ] ; <i32> [#uses=2] 24 %p.01 = phi i8 [ %4, %bb1 ], [ -1, %bb.nph ] ; <i8> [#uses=2] 25 %1 = sext i8 %p.01 to i32 ; <i32> [#uses=1] 26 %2 = sext i32 %i.02 to i64 ; <i64> [#uses=1] 27 %3 = getelementptr i32, ptr %d, i64 %2 ; <ptr> [#uses=1] 28 store i32 %1, ptr %3, align 4 29 %4 = add i8 %p.01, 1 ; <i8> [#uses=1] 30 %5 = add i32 %i.02, 1 ; <i32> [#uses=2] 31 br label %bb1 32 33bb1: ; preds = %bb 34 %6 = icmp slt i32 %5, %n ; <i1> [#uses=1] 35 br i1 %6, label %bb, label %bb1.return_crit_edge 36 37bb1.return_crit_edge: ; preds = %bb1 38 br label %return 39 40return: ; preds = %bb1.return_crit_edge, %entry 41 ret void 42} 43 44; ScalarEvolution should be able to find the maximum tripcount 45; of this multiple-exit loop, and if it doesn't know the exact 46; count, it should say so. 47 48; PR7845 49 50@.str = private constant [4 x i8] c"%d\0A\00" ; <ptr> [#uses=2] 51 52define i32 @main() nounwind { 53; CHECK-LABEL: 'main' 54; CHECK-NEXT: Determining loop execution counts for: @main 55; CHECK-NEXT: Loop %for.cond: <multiple exits> Unpredictable backedge-taken count. 56; CHECK-NEXT: exit count for for.cond: i32 5 57; CHECK-NEXT: exit count for for.body: ***COULDNOTCOMPUTE*** 58; CHECK-NEXT: Loop %for.cond: constant max backedge-taken count is i32 5 59; CHECK-NEXT: Loop %for.cond: symbolic max backedge-taken count is i32 5 60; CHECK-NEXT: symbolic max exit count for for.cond: i32 5 61; CHECK-NEXT: symbolic max exit count for for.body: ***COULDNOTCOMPUTE*** 62; 63entry: 64 br label %for.cond 65 66for.cond: ; preds = %for.inc, %entry 67 %g_4.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ] ; <i32> [#uses=5] 68 %cmp = icmp slt i32 %g_4.0, 5 ; <i1> [#uses=1] 69 br i1 %cmp, label %for.body, label %for.end 70 71for.body: ; preds = %for.cond 72 %conv = trunc i32 %g_4.0 to i16 ; <i16> [#uses=1] 73 %tobool.not = icmp eq i16 %conv, 0 ; <i1> [#uses=1] 74 %tobool3 = icmp ne i32 %g_4.0, 0 ; <i1> [#uses=1] 75 %or.cond = and i1 %tobool.not, %tobool3 ; <i1> [#uses=1] 76 br i1 %or.cond, label %for.end, label %for.inc 77 78for.inc: ; preds = %for.body 79 %add = add nsw i32 %g_4.0, 1 ; <i32> [#uses=1] 80 br label %for.cond 81 82for.end: ; preds = %for.body, %for.cond 83 %call = call i32 (ptr, ...) @printf(ptr @.str, i32 %g_4.0) nounwind ; <i32> [#uses=0] 84 ret i32 0 85} 86 87declare i32 @printf(ptr, ...) 88 89define void @test(ptr %a, i32 %n) nounwind { 90; CHECK-LABEL: 'test' 91; CHECK-NEXT: Determining loop execution counts for: @test 92; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (zext i32 %n to i64))<nsw> 93; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i64 2147483646 94; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (zext i32 %n to i64))<nsw> 95; CHECK-NEXT: Loop %for.body: Trip multiple is 1 96; 97entry: 98 %cmp1 = icmp sgt i32 %n, 0 99 br i1 %cmp1, label %for.body.lr.ph, label %for.end 100 101for.body.lr.ph: ; preds = %entry 102 %tmp = zext i32 %n to i64 103 br label %for.body 104 105for.body: ; preds = %for.body, %for.body.lr.ph 106 %indvar = phi i64 [ %indvar.next, %for.body ], [ 0, %for.body.lr.ph ] 107 %arrayidx = getelementptr i8, ptr %a, i64 %indvar 108 store i8 0, ptr %arrayidx, align 1 109 %indvar.next = add i64 %indvar, 1 110 %exitcond = icmp ne i64 %indvar.next, %tmp 111 br i1 %exitcond, label %for.body, label %for.cond.for.end_crit_edge 112 113for.cond.for.end_crit_edge: ; preds = %for.body 114 br label %for.end 115 116for.end: ; preds = %for.cond.for.end_crit_edge, %entry 117 ret void 118} 119 120 121; PR19799: Indvars miscompile due to an incorrect max backedge taken count from SCEV. 122@a = common global i32 0, align 4 123 124define i32 @pr19799() { 125; CHECK-LABEL: 'pr19799' 126; CHECK-NEXT: Determining loop execution counts for: @pr19799 127; CHECK-NEXT: Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count. 128; CHECK-NEXT: exit count for for.body.i: ***COULDNOTCOMPUTE*** 129; CHECK-NEXT: exit count for for.cond.i: i32 1 130; CHECK-NEXT: Loop %for.body.i: constant max backedge-taken count is i32 1 131; CHECK-NEXT: Loop %for.body.i: symbolic max backedge-taken count is i32 1 132; CHECK-NEXT: symbolic max exit count for for.body.i: ***COULDNOTCOMPUTE*** 133; CHECK-NEXT: symbolic max exit count for for.cond.i: i32 1 134; 135entry: 136 store i32 -1, ptr @a, align 4 137 br label %for.body.i 138 139for.body.i: ; preds = %for.cond.i, %entry 140 %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ] 141 %tobool.i = icmp eq i32 %storemerge1.i, 0 142 %add.i.i = add nsw i32 %storemerge1.i, 2 143 br i1 %tobool.i, label %bar.exit, label %for.cond.i 144 145for.cond.i: ; preds = %for.body.i 146 store i32 %add.i.i, ptr @a, align 4 147 %cmp.i = icmp slt i32 %storemerge1.i, 0 148 br i1 %cmp.i, label %for.body.i, label %bar.exit 149 150bar.exit: ; preds = %for.cond.i, %for.body.i 151 ret i32 0 152} 153 154; PR18886: Indvars miscompile due to an incorrect max backedge taken count from SCEV. 155@aa = global i64 0, align 8 156 157define i32 @pr18886() { 158; CHECK-LABEL: 'pr18886' 159; CHECK-NEXT: Determining loop execution counts for: @pr18886 160; CHECK-NEXT: Loop %for.body: <multiple exits> Unpredictable backedge-taken count. 161; CHECK-NEXT: exit count for for.body: ***COULDNOTCOMPUTE*** 162; CHECK-NEXT: exit count for for.cond: i64 3 163; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i64 3 164; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is i64 3 165; CHECK-NEXT: symbolic max exit count for for.body: ***COULDNOTCOMPUTE*** 166; CHECK-NEXT: symbolic max exit count for for.cond: i64 3 167; 168entry: 169 store i64 -21, ptr @aa, align 8 170 br label %for.body 171 172for.body: 173 %storemerge1 = phi i64 [ -21, %entry ], [ %add, %for.cond ] 174 %tobool = icmp eq i64 %storemerge1, 0 175 %add = add nsw i64 %storemerge1, 8 176 br i1 %tobool, label %return, label %for.cond 177 178for.cond: 179 store i64 %add, ptr @aa, align 8 180 %cmp = icmp slt i64 %add, 9 181 br i1 %cmp, label %for.body, label %return 182 183return: 184 %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ] 185 ret i32 %retval.0 186} 187 188; Here we have a must-exit loop latch that is not computable and a 189; may-exit early exit that can only have one non-exiting iteration 190; before the check is forever skipped. 191; 192@b = common global i32 0, align 4 193 194define i32 @cannot_compute_mustexit() { 195; CHECK-LABEL: 'cannot_compute_mustexit' 196; CHECK-NEXT: Determining loop execution counts for: @cannot_compute_mustexit 197; CHECK-NEXT: Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count. 198; CHECK-NEXT: exit count for for.body.i: ***COULDNOTCOMPUTE*** 199; CHECK-NEXT: exit count for for.cond.i: ***COULDNOTCOMPUTE*** 200; CHECK-NEXT: Loop %for.body.i: Unpredictable constant max backedge-taken count. 201; CHECK-NEXT: Loop %for.body.i: Unpredictable symbolic max backedge-taken count. 202; CHECK-NEXT: symbolic max exit count for for.body.i: ***COULDNOTCOMPUTE*** 203; CHECK-NEXT: symbolic max exit count for for.cond.i: ***COULDNOTCOMPUTE*** 204; 205entry: 206 store i32 -1, ptr @a, align 4 207 br label %for.body.i 208 209for.body.i: ; preds = %for.cond.i, %entry 210 %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ] 211 %tobool.i = icmp eq i32 %storemerge1.i, 0 212 %add.i.i = add nsw i32 %storemerge1.i, 2 213 br i1 %tobool.i, label %bar.exit, label %for.cond.i 214 215for.cond.i: ; preds = %for.body.i 216 store i32 %add.i.i, ptr @a, align 4 217 %ld = load volatile i32, ptr @b 218 %cmp.i = icmp ne i32 %ld, 0 219 br i1 %cmp.i, label %for.body.i, label %bar.exit 220 221bar.exit: ; preds = %for.cond.i, %for.body.i 222 ret i32 0 223} 224 225; This loop has two must-exits, both of which dominate the latch. The 226; MaxBECount should be the minimum of them. 227; 228define i32 @two_mustexit() { 229; CHECK-LABEL: 'two_mustexit' 230; CHECK-NEXT: Determining loop execution counts for: @two_mustexit 231; CHECK-NEXT: Loop %for.body.i: <multiple exits> backedge-taken count is i32 1 232; CHECK-NEXT: exit count for for.body.i: i32 1 233; CHECK-NEXT: exit count for for.cond.i: i32 2 234; CHECK-NEXT: Loop %for.body.i: constant max backedge-taken count is i32 1 235; CHECK-NEXT: Loop %for.body.i: symbolic max backedge-taken count is i32 1 236; CHECK-NEXT: symbolic max exit count for for.body.i: i32 1 237; CHECK-NEXT: symbolic max exit count for for.cond.i: i32 2 238; CHECK-NEXT: Loop %for.body.i: Trip multiple is 1 239; 240entry: 241 store i32 -1, ptr @a, align 4 242 br label %for.body.i 243 244for.body.i: ; preds = %for.cond.i, %entry 245 %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ] 246 %tobool.i = icmp sgt i32 %storemerge1.i, 0 247 %add.i.i = add nsw i32 %storemerge1.i, 2 248 br i1 %tobool.i, label %bar.exit, label %for.cond.i 249 250for.cond.i: ; preds = %for.body.i 251 store i32 %add.i.i, ptr @a, align 4 252 %cmp.i = icmp slt i32 %storemerge1.i, 3 253 br i1 %cmp.i, label %for.body.i, label %bar.exit 254 255bar.exit: ; preds = %for.cond.i, %for.body.i 256 ret i32 0 257} 258 259define i32 @ne_max_trip_count_1(i32 %n) { 260; CHECK-LABEL: 'ne_max_trip_count_1' 261; CHECK-NEXT: Determining loop execution counts for: @ne_max_trip_count_1 262; CHECK-NEXT: Loop %for.body: backedge-taken count is (zext i3 (trunc i32 %n to i3) to i32) 263; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 7 264; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (zext i3 (trunc i32 %n to i3) to i32) 265; CHECK-NEXT: Loop %for.body: Trip multiple is 1 266; 267entry: 268 %masked = and i32 %n, 7 269 br label %for.body 270 271for.body: 272 %i = phi i32 [ 0, %entry ], [ %add, %for.body ] 273 %add = add nsw i32 %i, 1 274 %cmp = icmp ne i32 %i, %masked 275 br i1 %cmp, label %for.body, label %bar.exit 276 277bar.exit: 278 ret i32 0 279} 280 281define i32 @ne_max_trip_count_2(i32 %n) { 282; CHECK-LABEL: 'ne_max_trip_count_2' 283; CHECK-NEXT: Determining loop execution counts for: @ne_max_trip_count_2 284; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (zext i3 (trunc i32 %n to i3) to i32))<nsw> 285; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 -1 286; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (zext i3 (trunc i32 %n to i3) to i32))<nsw> 287; CHECK-NEXT: Loop %for.body: Trip multiple is 1 288; 289entry: 290 %masked = and i32 %n, 7 291 br label %for.body 292 293for.body: 294 %i = phi i32 [ 0, %entry ], [ %add, %for.body ] 295 %add = add nsw i32 %i, 1 296 %cmp = icmp ne i32 %add, %masked 297 br i1 %cmp, label %for.body, label %bar.exit 298 299bar.exit: 300 ret i32 0 301} 302 303define i32 @ne_max_trip_count_3(i32 %n) { 304; CHECK-LABEL: 'ne_max_trip_count_3' 305; CHECK-NEXT: Determining loop execution counts for: @ne_max_trip_count_3 306; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (zext i3 (trunc i32 %n to i3) to i32))<nsw> 307; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 6 308; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (zext i3 (trunc i32 %n to i3) to i32))<nsw> 309; CHECK-NEXT: Loop %for.body: Trip multiple is 1 310; 311entry: 312 %masked = and i32 %n, 7 313 %guard = icmp eq i32 %masked, 0 314 br i1 %guard, label %exit, label %for.preheader 315 316for.preheader: 317 br label %for.body 318 319for.body: 320 %i = phi i32 [ 0, %for.preheader ], [ %add, %for.body ] 321 %add = add nsw i32 %i, 1 322 %cmp = icmp ne i32 %add, %masked 323 br i1 %cmp, label %for.body, label %loop.exit 324 325loop.exit: 326 br label %exit 327 328exit: 329 ret i32 0 330} 331 332define i32 @ne_max_trip_count_4(i32 %n) { 333; CHECK-LABEL: 'ne_max_trip_count_4' 334; CHECK-NEXT: Determining loop execution counts for: @ne_max_trip_count_4 335; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + %n) 336; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 -2 337; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + %n) 338; CHECK-NEXT: Loop %for.body: Trip multiple is 1 339; 340entry: 341 %guard = icmp eq i32 %n, 0 342 br i1 %guard, label %exit, label %for.preheader 343 344for.preheader: 345 br label %for.body 346 347for.body: 348 %i = phi i32 [ 0, %for.preheader ], [ %add, %for.body ] 349 %add = add nsw i32 %i, 1 350 %cmp = icmp ne i32 %add, %n 351 br i1 %cmp, label %for.body, label %loop.exit 352 353loop.exit: 354 br label %exit 355 356exit: 357 ret i32 0 358} 359 360; The end bound of the loop can change between iterations, so the exact trip 361; count is unknown, but SCEV can calculate the max trip count. 362define void @changing_end_bound(ptr %n_addr, ptr %addr) { 363; CHECK-LABEL: 'changing_end_bound' 364; CHECK-NEXT: Determining loop execution counts for: @changing_end_bound 365; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 366; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 2147483646 367; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i32 2147483646 368; 369entry: 370 br label %loop 371 372loop: 373 %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] 374 %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ] 375 %val = load atomic i32, ptr %addr unordered, align 4 376 fence acquire 377 %acc.next = add i32 %acc, %val 378 %iv.next = add nsw i32 %iv, 1 379 %n = load atomic i32, ptr %n_addr unordered, align 4 380 %cmp = icmp slt i32 %iv.next, %n 381 br i1 %cmp, label %loop, label %loop.exit 382 383loop.exit: 384 ret void 385} 386 387; Similar test as above, but unknown start value. 388; Also, there's no nsw on the iv.next, but SCEV knows 389; the termination condition is LT, so the IV cannot wrap. 390define void @changing_end_bound2(i32 %start, ptr %n_addr, ptr %addr) { 391; CHECK-LABEL: 'changing_end_bound2' 392; CHECK-NEXT: Determining loop execution counts for: @changing_end_bound2 393; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 394; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 -1 395; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i32 -1 396; 397entry: 398 br label %loop 399 400loop: 401 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 402 %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ] 403 %val = load atomic i32, ptr %addr unordered, align 4 404 fence acquire 405 %acc.next = add i32 %acc, %val 406 %iv.next = add i32 %iv, 1 407 %n = load atomic i32, ptr %n_addr unordered, align 4 408 %cmp = icmp slt i32 %iv.next, %n 409 br i1 %cmp, label %loop, label %loop.exit 410 411loop.exit: 412 ret void 413} 414 415; changing end bound and greater than one stride 416define void @changing_end_bound3(i32 %start, ptr %n_addr, ptr %addr) { 417; CHECK-LABEL: 'changing_end_bound3' 418; CHECK-NEXT: Determining loop execution counts for: @changing_end_bound3 419; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 420; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 1073741823 421; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i32 1073741823 422; 423entry: 424 br label %loop 425 426loop: 427 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 428 %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ] 429 %val = load atomic i32, ptr %addr unordered, align 4 430 fence acquire 431 %acc.next = add i32 %acc, %val 432 %iv.next = add nsw i32 %iv, 4 433 %n = load atomic i32, ptr %n_addr unordered, align 4 434 %cmp = icmp slt i32 %iv.next, %n 435 br i1 %cmp, label %loop, label %loop.exit 436 437loop.exit: 438 ret void 439} 440 441; same as above test, but the IV can wrap around. 442; so the max backedge taken count is unpredictable. 443define void @changing_end_bound4(i32 %start, ptr %n_addr, ptr %addr) { 444; CHECK-LABEL: 'changing_end_bound4' 445; CHECK-NEXT: Determining loop execution counts for: @changing_end_bound4 446; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 447; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count. 448; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count. 449; 450entry: 451 br label %loop 452 453loop: 454 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 455 %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ] 456 %val = load atomic i32, ptr %addr unordered, align 4 457 fence acquire 458 %acc.next = add i32 %acc, %val 459 %iv.next = add i32 %iv, 4 460 %n = load atomic i32, ptr %n_addr unordered, align 4 461 %cmp = icmp slt i32 %iv.next, %n 462 br i1 %cmp, label %loop, label %loop.exit 463 464loop.exit: 465 ret void 466} 467 468; unknown stride. Since it's not knownPositive, we do not estimate the max 469; backedge taken count. 470define void @changing_end_bound5(i32 %stride, i32 %start, ptr %n_addr, ptr %addr) { 471; CHECK-LABEL: 'changing_end_bound5' 472; CHECK-NEXT: Determining loop execution counts for: @changing_end_bound5 473; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 474; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count. 475; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count. 476; 477entry: 478 br label %loop 479 480loop: 481 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 482 %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ] 483 %val = load atomic i32, ptr %addr unordered, align 4 484 fence acquire 485 %acc.next = add i32 %acc, %val 486 %iv.next = add nsw i32 %iv, %stride 487 %n = load atomic i32, ptr %n_addr unordered, align 4 488 %cmp = icmp slt i32 %iv.next, %n 489 br i1 %cmp, label %loop, label %loop.exit 490 491loop.exit: 492 ret void 493} 494 495; negative stride value 496define void @changing_end_bound6(i32 %start, ptr %n_addr, ptr %addr) { 497; CHECK-LABEL: 'changing_end_bound6' 498; CHECK-NEXT: Determining loop execution counts for: @changing_end_bound6 499; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 500; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count. 501; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count. 502; 503entry: 504 br label %loop 505 506loop: 507 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 508 %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ] 509 %val = load atomic i32, ptr %addr unordered, align 4 510 fence acquire 511 %acc.next = add i32 %acc, %val 512 %iv.next = add nsw i32 %iv, -1 513 %n = load atomic i32, ptr %n_addr unordered, align 4 514 %cmp = icmp slt i32 %iv.next, %n 515 br i1 %cmp, label %loop, label %loop.exit 516 517loop.exit: 518 ret void 519} 520 521; sgt with negative stride 522define void @changing_end_bound7(i32 %start, ptr %n_addr, ptr %addr) { 523; CHECK-LABEL: 'changing_end_bound7' 524; CHECK-NEXT: Determining loop execution counts for: @changing_end_bound7 525; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 526; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count. 527; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count. 528; 529entry: 530 br label %loop 531 532loop: 533 %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ] 534 %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ] 535 %val = load atomic i32, ptr %addr unordered, align 4 536 fence acquire 537 %acc.next = add i32 %acc, %val 538 %iv.next = add i32 %iv, -1 539 %n = load atomic i32, ptr %n_addr unordered, align 4 540 %cmp = icmp sgt i32 %iv.next, %n 541 br i1 %cmp, label %loop, label %loop.exit 542 543loop.exit: 544 ret void 545} 546 547define void @max_overflow_se(i8 %n) mustprogress { 548; CHECK-LABEL: 'max_overflow_se' 549; CHECK-NEXT: Determining loop execution counts for: @max_overflow_se 550; CHECK-NEXT: Loop %loop: backedge-taken count is i8 0 551; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i8 0 552; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i8 0 553; CHECK-NEXT: Loop %loop: Trip multiple is 1 554; 555entry: 556 br label %loop 557 558loop: 559 %i = phi i8 [ 63, %entry ], [ %i.next, %loop ] 560 %i.next = add nsw i8 %i, 63 561 %t = icmp slt i8 %i.next, %n 562 br i1 %t, label %loop, label %exit 563 564exit: 565 ret void 566} 567 568; Show that we correctly realize that %i can overflow here as long as 569; the early exit is taken before we branch on poison. 570define void @max_overflow_me(i8 %n) mustprogress { 571; CHECK-LABEL: 'max_overflow_me' 572; CHECK-NEXT: Determining loop execution counts for: @max_overflow_me 573; CHECK-NEXT: Loop %loop: <multiple exits> Unpredictable backedge-taken count. 574; CHECK-NEXT: exit count for loop: i8 1 575; CHECK-NEXT: exit count for latch: ***COULDNOTCOMPUTE*** 576; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i8 1 577; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i8 1 578; CHECK-NEXT: symbolic max exit count for loop: i8 1 579; CHECK-NEXT: symbolic max exit count for latch: ***COULDNOTCOMPUTE*** 580; 581entry: 582 br label %loop 583 584loop: 585 %i = phi i8 [ 63, %entry ], [ %i.next, %latch ] 586 %j = phi i8 [ 0, %entry ], [ %j.next, %latch ] 587 %early.exit = icmp ne i8 %j, 1 588 br i1 %early.exit, label %latch, label %exit 589latch: 590 %i.next = add nsw i8 %i, 63 591 %j.next = add nsw nuw i8 %j, 1 592 %t = icmp slt i8 %i.next, %n 593 br i1 %t, label %loop, label %exit 594 595exit: 596 ret void 597} 598 599 600; Max backedge-taken count is zero. 601define void @bool_stride(i1 %s, i1 %n) mustprogress { 602; CHECK-LABEL: 'bool_stride' 603; CHECK-NEXT: Determining loop execution counts for: @bool_stride 604; CHECK-NEXT: Loop %loop: backedge-taken count is i1 false 605; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i1 false 606; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i1 false 607; CHECK-NEXT: Loop %loop: Trip multiple is 1 608; 609entry: 610 br label %loop 611 612loop: 613 %i = phi i1 [ -1, %entry ], [ %i.next, %loop ] 614 %i.next = add nsw i1 %i, %s 615 %t = icmp slt i1 %i.next, %n 616 br i1 %t, label %loop, label %exit 617 618exit: 619 ret void 620} 621 622; This is a case where our max-backedge taken count logic happens to be 623; able to prove a zero btc, but our symbolic logic doesn't due to a lack 624; of context sensativity. 625define void @ne_zero_max_btc(i32 %a) { 626; CHECK-LABEL: 'ne_zero_max_btc' 627; CHECK-NEXT: Determining loop execution counts for: @ne_zero_max_btc 628; CHECK-NEXT: Loop %for.body: backedge-taken count is i64 0 629; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i64 0 630; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is i64 0 631; CHECK-NEXT: Loop %for.body: Trip multiple is 1 632; 633entry: 634 %cmp = icmp slt i32 %a, 1 635 %spec.select = select i1 %cmp, i32 %a, i32 1 636 %cmp8 = icmp sgt i32 %a, 0 637 br i1 %cmp8, label %for.body.preheader, label %loopexit 638 639for.body.preheader: ; preds = %if.then4.i.i 640 %umax = call i32 @llvm.umax.i32(i32 %spec.select, i32 1) 641 %umax.i.i = zext i32 %umax to i64 642 br label %for.body 643 644for.body: ; preds = %for.inc, %for.body.preheader 645 %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.inc ] 646 call void @unknown() 647 br label %for.inc 648 649for.inc: ; preds = %for.body 650 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 651 %exitcond.i.not.i534 = icmp ne i64 %indvars.iv.next, %umax.i.i 652 br i1 %exitcond.i.not.i534, label %for.body, label %loopexit 653 654loopexit: 655 ret void 656} 657 658declare void @unknown() 659declare i32 @llvm.umax.i32(i32, i32) 660