660 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 42; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s3 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: @foo10; CHECK-NEXT: Loop %bb: backedge-taken count is (-1 + %n)11; CHECK-NEXT: Loop %bb: constant max backedge-taken count is i32 214748364612; CHECK-NEXT: Loop %bb: symbolic max backedge-taken count is (-1 + %n)13; CHECK-NEXT: Loop %bb: Trip multiple is 114;15entry:16 %0 = icmp sgt i32 %n, 0 ; <i1> [#uses=1]17 br i1 %0, label %bb.nph, label %return18 19bb.nph: ; preds = %entry20 br label %bb21 22bb: ; preds = %bb1, %bb.nph23 %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 429 %4 = add i8 %p.01, 1 ; <i8> [#uses=1]30 %5 = add i32 %i.02, 1 ; <i32> [#uses=2]31 br label %bb132 33bb1: ; preds = %bb34 %6 = icmp slt i32 %5, %n ; <i1> [#uses=1]35 br i1 %6, label %bb, label %bb1.return_crit_edge36 37bb1.return_crit_edge: ; preds = %bb138 br label %return39 40return: ; preds = %bb1.return_crit_edge, %entry41 ret void42}43 44; ScalarEvolution should be able to find the maximum tripcount45; of this multiple-exit loop, and if it doesn't know the exact46; count, it should say so.47 48; PR784549 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: @main55; CHECK-NEXT: Loop %for.cond: <multiple exits> Unpredictable backedge-taken count.56; CHECK-NEXT: exit count for for.cond: i32 557; CHECK-NEXT: exit count for for.body: ***COULDNOTCOMPUTE***58; CHECK-NEXT: Loop %for.cond: constant max backedge-taken count is i32 559; CHECK-NEXT: Loop %for.cond: symbolic max backedge-taken count is i32 560; CHECK-NEXT: symbolic max exit count for for.cond: i32 561; CHECK-NEXT: symbolic max exit count for for.body: ***COULDNOTCOMPUTE***62;63entry:64 br label %for.cond65 66for.cond: ; preds = %for.inc, %entry67 %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.end70 71for.body: ; preds = %for.cond72 %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.inc77 78for.inc: ; preds = %for.body79 %add = add nsw i32 %g_4.0, 1 ; <i32> [#uses=1]80 br label %for.cond81 82for.end: ; preds = %for.body, %for.cond83 %call = call i32 (ptr, ...) @printf(ptr @.str, i32 %g_4.0) nounwind ; <i32> [#uses=0]84 ret i32 085}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: @test92; 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 214748364694; 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 196;97entry:98 %cmp1 = icmp sgt i32 %n, 099 br i1 %cmp1, label %for.body.lr.ph, label %for.end100 101for.body.lr.ph: ; preds = %entry102 %tmp = zext i32 %n to i64103 br label %for.body104 105for.body: ; preds = %for.body, %for.body.lr.ph106 %indvar = phi i64 [ %indvar.next, %for.body ], [ 0, %for.body.lr.ph ]107 %arrayidx = getelementptr i8, ptr %a, i64 %indvar108 store i8 0, ptr %arrayidx, align 1109 %indvar.next = add i64 %indvar, 1110 %exitcond = icmp ne i64 %indvar.next, %tmp111 br i1 %exitcond, label %for.body, label %for.cond.for.end_crit_edge112 113for.cond.for.end_crit_edge: ; preds = %for.body114 br label %for.end115 116for.end: ; preds = %for.cond.for.end_crit_edge, %entry117 ret void118}119 120 121; PR19799: Indvars miscompile due to an incorrect max backedge taken count from SCEV.122@a = common global i32 0, align 4123 124define i32 @pr19799() {125; CHECK-LABEL: 'pr19799'126; CHECK-NEXT: Determining loop execution counts for: @pr19799127; 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 1130; CHECK-NEXT: Loop %for.body.i: constant max backedge-taken count is i32 1131; CHECK-NEXT: Loop %for.body.i: symbolic max backedge-taken count is i32 1132; CHECK-NEXT: symbolic max exit count for for.body.i: ***COULDNOTCOMPUTE***133; CHECK-NEXT: symbolic max exit count for for.cond.i: i32 1134;135entry:136 store i32 -1, ptr @a, align 4137 br label %for.body.i138 139for.body.i: ; preds = %for.cond.i, %entry140 %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ]141 %tobool.i = icmp eq i32 %storemerge1.i, 0142 %add.i.i = add nsw i32 %storemerge1.i, 2143 br i1 %tobool.i, label %bar.exit, label %for.cond.i144 145for.cond.i: ; preds = %for.body.i146 store i32 %add.i.i, ptr @a, align 4147 %cmp.i = icmp slt i32 %storemerge1.i, 0148 br i1 %cmp.i, label %for.body.i, label %bar.exit149 150bar.exit: ; preds = %for.cond.i, %for.body.i151 ret i32 0152}153 154; PR18886: Indvars miscompile due to an incorrect max backedge taken count from SCEV.155@aa = global i64 0, align 8156 157define i32 @pr18886() {158; CHECK-LABEL: 'pr18886'159; CHECK-NEXT: Determining loop execution counts for: @pr18886160; 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 3163; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i64 3164; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is i64 3165; CHECK-NEXT: symbolic max exit count for for.body: ***COULDNOTCOMPUTE***166; CHECK-NEXT: symbolic max exit count for for.cond: i64 3167;168entry:169 store i64 -21, ptr @aa, align 8170 br label %for.body171 172for.body:173 %storemerge1 = phi i64 [ -21, %entry ], [ %add, %for.cond ]174 %tobool = icmp eq i64 %storemerge1, 0175 %add = add nsw i64 %storemerge1, 8176 br i1 %tobool, label %return, label %for.cond177 178for.cond:179 store i64 %add, ptr @aa, align 8180 %cmp = icmp slt i64 %add, 9181 br i1 %cmp, label %for.body, label %return182 183return:184 %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ]185 ret i32 %retval.0186}187 188; Here we have a must-exit loop latch that is not computable and a189; may-exit early exit that can only have one non-exiting iteration190; before the check is forever skipped.191;192@b = common global i32 0, align 4193 194define i32 @cannot_compute_mustexit() {195; CHECK-LABEL: 'cannot_compute_mustexit'196; CHECK-NEXT: Determining loop execution counts for: @cannot_compute_mustexit197; 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 4207 br label %for.body.i208 209for.body.i: ; preds = %for.cond.i, %entry210 %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ]211 %tobool.i = icmp eq i32 %storemerge1.i, 0212 %add.i.i = add nsw i32 %storemerge1.i, 2213 br i1 %tobool.i, label %bar.exit, label %for.cond.i214 215for.cond.i: ; preds = %for.body.i216 store i32 %add.i.i, ptr @a, align 4217 %ld = load volatile i32, ptr @b218 %cmp.i = icmp ne i32 %ld, 0219 br i1 %cmp.i, label %for.body.i, label %bar.exit220 221bar.exit: ; preds = %for.cond.i, %for.body.i222 ret i32 0223}224 225; This loop has two must-exits, both of which dominate the latch. The226; 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_mustexit231; CHECK-NEXT: Loop %for.body.i: <multiple exits> backedge-taken count is i32 1232; CHECK-NEXT: exit count for for.body.i: i32 1233; CHECK-NEXT: exit count for for.cond.i: i32 2234; CHECK-NEXT: Loop %for.body.i: constant max backedge-taken count is i32 1235; CHECK-NEXT: Loop %for.body.i: symbolic max backedge-taken count is i32 1236; CHECK-NEXT: symbolic max exit count for for.body.i: i32 1237; CHECK-NEXT: symbolic max exit count for for.cond.i: i32 2238; CHECK-NEXT: Loop %for.body.i: Trip multiple is 1239;240entry:241 store i32 -1, ptr @a, align 4242 br label %for.body.i243 244for.body.i: ; preds = %for.cond.i, %entry245 %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ]246 %tobool.i = icmp sgt i32 %storemerge1.i, 0247 %add.i.i = add nsw i32 %storemerge1.i, 2248 br i1 %tobool.i, label %bar.exit, label %for.cond.i249 250for.cond.i: ; preds = %for.body.i251 store i32 %add.i.i, ptr @a, align 4252 %cmp.i = icmp slt i32 %storemerge1.i, 3253 br i1 %cmp.i, label %for.body.i, label %bar.exit254 255bar.exit: ; preds = %for.cond.i, %for.body.i256 ret i32 0257}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_1262; 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 7264; 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 1266;267entry:268 %masked = and i32 %n, 7269 br label %for.body270 271for.body:272 %i = phi i32 [ 0, %entry ], [ %add, %for.body ]273 %add = add nsw i32 %i, 1274 %cmp = icmp ne i32 %i, %masked275 br i1 %cmp, label %for.body, label %bar.exit276 277bar.exit:278 ret i32 0279}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_2284; 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 -1286; 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 1288;289entry:290 %masked = and i32 %n, 7291 br label %for.body292 293for.body:294 %i = phi i32 [ 0, %entry ], [ %add, %for.body ]295 %add = add nsw i32 %i, 1296 %cmp = icmp ne i32 %add, %masked297 br i1 %cmp, label %for.body, label %bar.exit298 299bar.exit:300 ret i32 0301}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_3306; 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 6308; 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 1310;311entry:312 %masked = and i32 %n, 7313 %guard = icmp eq i32 %masked, 0314 br i1 %guard, label %exit, label %for.preheader315 316for.preheader:317 br label %for.body318 319for.body:320 %i = phi i32 [ 0, %for.preheader ], [ %add, %for.body ]321 %add = add nsw i32 %i, 1322 %cmp = icmp ne i32 %add, %masked323 br i1 %cmp, label %for.body, label %loop.exit324 325loop.exit:326 br label %exit327 328exit:329 ret i32 0330}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_4335; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + %n)336; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 -2337; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + %n)338; CHECK-NEXT: Loop %for.body: Trip multiple is 1339;340entry:341 %guard = icmp eq i32 %n, 0342 br i1 %guard, label %exit, label %for.preheader343 344for.preheader:345 br label %for.body346 347for.body:348 %i = phi i32 [ 0, %for.preheader ], [ %add, %for.body ]349 %add = add nsw i32 %i, 1350 %cmp = icmp ne i32 %add, %n351 br i1 %cmp, label %for.body, label %loop.exit352 353loop.exit:354 br label %exit355 356exit:357 ret i32 0358}359 360; The end bound of the loop can change between iterations, so the exact trip361; 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_bound365; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count.366; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 2147483646367; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i32 2147483646368;369entry:370 br label %loop371 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 4376 fence acquire377 %acc.next = add i32 %acc, %val378 %iv.next = add nsw i32 %iv, 1379 %n = load atomic i32, ptr %n_addr unordered, align 4380 %cmp = icmp slt i32 %iv.next, %n381 br i1 %cmp, label %loop, label %loop.exit382 383loop.exit:384 ret void385}386 387; Similar test as above, but unknown start value.388; Also, there's no nsw on the iv.next, but SCEV knows389; 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_bound2393; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count.394; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 -1395; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i32 -1396;397entry:398 br label %loop399 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 4404 fence acquire405 %acc.next = add i32 %acc, %val406 %iv.next = add i32 %iv, 1407 %n = load atomic i32, ptr %n_addr unordered, align 4408 %cmp = icmp slt i32 %iv.next, %n409 br i1 %cmp, label %loop, label %loop.exit410 411loop.exit:412 ret void413}414 415; changing end bound and greater than one stride416define 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_bound3419; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count.420; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 1073741823421; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i32 1073741823422;423entry:424 br label %loop425 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 4430 fence acquire431 %acc.next = add i32 %acc, %val432 %iv.next = add nsw i32 %iv, 4433 %n = load atomic i32, ptr %n_addr unordered, align 4434 %cmp = icmp slt i32 %iv.next, %n435 br i1 %cmp, label %loop, label %loop.exit436 437loop.exit:438 ret void439}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_bound4446; 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 %loop452 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 4457 fence acquire458 %acc.next = add i32 %acc, %val459 %iv.next = add i32 %iv, 4460 %n = load atomic i32, ptr %n_addr unordered, align 4461 %cmp = icmp slt i32 %iv.next, %n462 br i1 %cmp, label %loop, label %loop.exit463 464loop.exit:465 ret void466}467 468; unknown stride. Since it's not knownPositive, we do not estimate the max469; 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_bound5473; 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 %loop479 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 4484 fence acquire485 %acc.next = add i32 %acc, %val486 %iv.next = add nsw i32 %iv, %stride487 %n = load atomic i32, ptr %n_addr unordered, align 4488 %cmp = icmp slt i32 %iv.next, %n489 br i1 %cmp, label %loop, label %loop.exit490 491loop.exit:492 ret void493}494 495; negative stride value496define 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_bound6499; 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 %loop505 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 4510 fence acquire511 %acc.next = add i32 %acc, %val512 %iv.next = add nsw i32 %iv, -1513 %n = load atomic i32, ptr %n_addr unordered, align 4514 %cmp = icmp slt i32 %iv.next, %n515 br i1 %cmp, label %loop, label %loop.exit516 517loop.exit:518 ret void519}520 521; sgt with negative stride522define 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_bound7525; 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 %loop531 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 4536 fence acquire537 %acc.next = add i32 %acc, %val538 %iv.next = add i32 %iv, -1539 %n = load atomic i32, ptr %n_addr unordered, align 4540 %cmp = icmp sgt i32 %iv.next, %n541 br i1 %cmp, label %loop, label %loop.exit542 543loop.exit:544 ret void545}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_se550; CHECK-NEXT: Loop %loop: backedge-taken count is i8 0551; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i8 0552; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i8 0553; CHECK-NEXT: Loop %loop: Trip multiple is 1554;555entry:556 br label %loop557 558loop:559 %i = phi i8 [ 63, %entry ], [ %i.next, %loop ]560 %i.next = add nsw i8 %i, 63561 %t = icmp slt i8 %i.next, %n562 br i1 %t, label %loop, label %exit563 564exit:565 ret void566}567 568; Show that we correctly realize that %i can overflow here as long as569; 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_me573; CHECK-NEXT: Loop %loop: <multiple exits> Unpredictable backedge-taken count.574; CHECK-NEXT: exit count for loop: i8 1575; CHECK-NEXT: exit count for latch: ***COULDNOTCOMPUTE***576; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i8 1577; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i8 1578; CHECK-NEXT: symbolic max exit count for loop: i8 1579; CHECK-NEXT: symbolic max exit count for latch: ***COULDNOTCOMPUTE***580;581entry:582 br label %loop583 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, 1588 br i1 %early.exit, label %latch, label %exit589latch:590 %i.next = add nsw i8 %i, 63591 %j.next = add nsw nuw i8 %j, 1592 %t = icmp slt i8 %i.next, %n593 br i1 %t, label %loop, label %exit594 595exit:596 ret void597}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_stride604; CHECK-NEXT: Loop %loop: backedge-taken count is i1 false605; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i1 false606; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i1 false607; CHECK-NEXT: Loop %loop: Trip multiple is 1608;609entry:610 br label %loop611 612loop:613 %i = phi i1 [ -1, %entry ], [ %i.next, %loop ]614 %i.next = add nsw i1 %i, %s615 %t = icmp slt i1 %i.next, %n616 br i1 %t, label %loop, label %exit617 618exit:619 ret void620}621 622; This is a case where our max-backedge taken count logic happens to be623; able to prove a zero btc, but our symbolic logic doesn't due to a lack624; 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_btc628; CHECK-NEXT: Loop %for.body: backedge-taken count is i64 0629; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i64 0630; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is i64 0631; CHECK-NEXT: Loop %for.body: Trip multiple is 1632;633entry:634 %cmp = icmp slt i32 %a, 1635 %spec.select = select i1 %cmp, i32 %a, i32 1636 %cmp8 = icmp sgt i32 %a, 0637 br i1 %cmp8, label %for.body.preheader, label %loopexit638 639for.body.preheader: ; preds = %if.then4.i.i640 %umax = call i32 @llvm.umax.i32(i32 %spec.select, i32 1)641 %umax.i.i = zext i32 %umax to i64642 br label %for.body643 644for.body: ; preds = %for.inc, %for.body.preheader645 %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.inc ]646 call void @unknown()647 br label %for.inc648 649for.inc: ; preds = %for.body650 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1651 %exitcond.i.not.i534 = icmp ne i64 %indvars.iv.next, %umax.i.i652 br i1 %exitcond.i.not.i534, label %for.body, label %loopexit653 654loopexit:655 ret void656}657 658declare void @unknown()659declare i32 @llvm.umax.i32(i32, i32)660