478 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py2; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s3 4; A collection of tests that show we can use facts about an exit test to5; infer tighter bounds on an IV, and thus refine an IV into an addrec. The6; basic tactic being used is proving NW from exit structure and then7; implying NUW/NSW. Once NSW/NUW is inferred, we can derive addrecs from8; the zext/sext cases that we couldn't at initial SCEV construction.9 10@G = external global i811 12define void @nw_implies_nuw(i16 %n) mustprogress {13; CHECK-LABEL: 'nw_implies_nuw'14; CHECK-NEXT: Determining loop execution counts for: @nw_implies_nuw15; CHECK-NEXT: Loop %for.body: backedge-taken count is %n16; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 -117; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is %n18; CHECK-NEXT: Loop %for.body: Trip multiple is 119;20entry:21 br label %for.body22 23for.body: ; preds = %entry, %for.body24 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]25 %iv.next = add i8 %iv, 126 %zext = zext i8 %iv to i1627 %cmp = icmp ult i16 %zext, %n28 br i1 %cmp, label %for.body, label %for.end29 30for.end: ; preds = %for.body, %entry31 ret void32}33 34define void @neg_nw_nuw(i16 %n) mustprogress {35; CHECK-LABEL: 'neg_nw_nuw'36; CHECK-NEXT: Determining loop execution counts for: @neg_nw_nuw37; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.38; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.39; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.40;41entry:42 br label %for.body43 44for.body: ; preds = %entry, %for.body45 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]46 %iv.next = add i8 %iv, -147 %zext = zext i8 %iv to i1648 %cmp = icmp ult i16 %zext, %n49 br i1 %cmp, label %for.body, label %for.end50 51for.end: ; preds = %for.body, %entry52 ret void53}54 55define void @nw_implies_nsw(i16 %n) mustprogress {56; CHECK-LABEL: 'nw_implies_nsw'57; CHECK-NEXT: Determining loop execution counts for: @nw_implies_nsw58; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.59; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.60; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.61; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (128 + (-128 smax %n))62; CHECK-NEXT: Predicates:63; CHECK-NEXT: {-128,+,1}<%for.body> Added Flags: <nssw>64; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 -3264165; CHECK-NEXT: Predicates:66; CHECK-NEXT: {-128,+,1}<%for.body> Added Flags: <nssw>67; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (128 + (-128 smax %n))68; CHECK-NEXT: Predicates:69; CHECK-NEXT: {-128,+,1}<%for.body> Added Flags: <nssw>70;71entry:72 br label %for.body73 74for.body: ; preds = %entry, %for.body75 %iv = phi i8 [ %iv.next, %for.body ], [ -128, %entry ]76 %iv.next = add i8 %iv, 177 %zext = sext i8 %iv to i1678 %cmp = icmp slt i16 %zext, %n79 br i1 %cmp, label %for.body, label %for.end80 81for.end: ; preds = %for.body, %entry82 ret void83}84 85define void @neg_nw_nsw(i16 %n) mustprogress {86; CHECK-LABEL: 'neg_nw_nsw'87; CHECK-NEXT: Determining loop execution counts for: @neg_nw_nsw88; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.89; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.90; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.91;92entry:93 br label %for.body94 95for.body: ; preds = %entry, %for.body96 %iv = phi i8 [ %iv.next, %for.body ], [ -128, %entry ]97 %iv.next = add i8 %iv, -198 %zext = sext i8 %iv to i1699 %cmp = icmp slt i16 %zext, %n100 br i1 %cmp, label %for.body, label %for.end101 102for.end: ; preds = %for.body, %entry103 ret void104}105 106 107define void @actually_infinite() {108; CHECK-LABEL: 'actually_infinite'109; CHECK-NEXT: Determining loop execution counts for: @actually_infinite110; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.111; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.112; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.113; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is i16 257114; CHECK-NEXT: Predicates:115; CHECK-NEXT: {0,+,1}<%for.body> Added Flags: <nusw>116; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 257117; CHECK-NEXT: Predicates:118; CHECK-NEXT: {0,+,1}<%for.body> Added Flags: <nusw>119; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is i16 257120; CHECK-NEXT: Predicates:121; CHECK-NEXT: {0,+,1}<%for.body> Added Flags: <nusw>122;123entry:124 br label %for.body125 126for.body: ; preds = %entry, %for.body127 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]128 store volatile i8 %iv, ptr @G129 %iv.next = add i8 %iv, 1130 %zext = zext i8 %iv to i16131 %cmp = icmp ult i16 %zext, 257132 br i1 %cmp, label %for.body, label %for.end133 134for.end: ; preds = %for.body, %entry135 ret void136}137 138define void @rhs_mustexit_1(i16 %n.raw) mustprogress {139; CHECK-LABEL: 'rhs_mustexit_1'140; CHECK-NEXT: Determining loop execution counts for: @rhs_mustexit_1141; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.142; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.143; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.144; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>))145; CHECK-NEXT: Predicates:146; CHECK-NEXT: {1,+,1}<nw><%for.body> Added Flags: <nusw>147; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 -2148; CHECK-NEXT: Predicates:149; CHECK-NEXT: {1,+,1}<nw><%for.body> Added Flags: <nusw>150; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>))151; CHECK-NEXT: Predicates:152; CHECK-NEXT: {1,+,1}<nw><%for.body> Added Flags: <nusw>153;154entry:155 %n.and = and i16 %n.raw, 255156 %n = add nsw i16 %n.and, -1157 br label %for.body158 159for.body: ; preds = %entry, %for.body160 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]161 %iv.next = add i8 %iv, 1162 store i8 %iv, ptr @G163 %zext = zext i8 %iv.next to i16164 %cmp = icmp ult i16 %zext, %n165 br i1 %cmp, label %for.body, label %for.end166 167for.end: ; preds = %for.body, %entry168 ret void169}170 171define void @rhs_mustexit_3(i16 %n.raw) mustprogress {172; CHECK-LABEL: 'rhs_mustexit_3'173; CHECK-NEXT: Determining loop execution counts for: @rhs_mustexit_3174; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.175; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.176; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.177;178entry:179 %n.and = and i16 %n.raw, 255180 %n = add nsw i16 %n.and, -3181 br label %for.body182 183for.body: ; preds = %entry, %for.body184 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]185 %iv.next = add i8 %iv, 3186 store i8 %iv, ptr @G187 %zext = zext i8 %iv.next to i16188 %cmp = icmp ult i16 %zext, %n189 br i1 %cmp, label %for.body, label %for.end190 191for.end: ; preds = %for.body, %entry192 ret void193}194 195; Unknown, but non-zero step196define void @rhs_mustexit_nonzero_step(i16 %n.raw, i8 %step.raw) mustprogress {197; CHECK-LABEL: 'rhs_mustexit_nonzero_step'198; CHECK-NEXT: Determining loop execution counts for: @rhs_mustexit_nonzero_step199; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.200; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.201; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.202;203entry:204 %n.and = and i16 %n.raw, 255205 %n = add nsw i16 %n.and, -3206 %step = add nuw i8 %step.raw, 1207 br label %for.body208 209for.body: ; preds = %entry, %for.body210 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]211 %iv.next = add i8 %iv, %step212 store i8 %iv, ptr @G213 %zext = zext i8 %iv.next to i16214 %cmp = icmp ult i16 %zext, %n215 br i1 %cmp, label %for.body, label %for.end216 217for.end: ; preds = %for.body, %entry218 ret void219}220 221define void @neg_maybe_zero_step(i16 %n.raw, i8 %step) mustprogress {222; CHECK-LABEL: 'neg_maybe_zero_step'223; CHECK-NEXT: Determining loop execution counts for: @neg_maybe_zero_step224; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.225; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.226; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.227;228entry:229 %n.and = and i16 %n.raw, 255230 %n = add nsw i16 %n.and, -3231 br label %for.body232 233for.body: ; preds = %entry, %for.body234 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]235 %iv.next = add i8 %iv, %step236 store i8 %iv, ptr @G237 %zext = zext i8 %iv.next to i16238 %cmp = icmp ult i16 %zext, %n239 br i1 %cmp, label %for.body, label %for.end240 241for.end: ; preds = %for.body, %entry242 ret void243}244 245define void @neg_rhs_wrong_range(i16 %n.raw) mustprogress {246; CHECK-LABEL: 'neg_rhs_wrong_range'247; CHECK-NEXT: Determining loop execution counts for: @neg_rhs_wrong_range248; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.249; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.250; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.251;252entry:253 %n.and = and i16 %n.raw, 255254 %n = add nsw i16 %n.and, -1255 br label %for.body256 257for.body: ; preds = %entry, %for.body258 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]259 %iv.next = add i8 %iv, 2260 store i8 %iv, ptr @G261 %zext = zext i8 %iv.next to i16262 %cmp = icmp ult i16 %zext, %n263 br i1 %cmp, label %for.body, label %for.end264 265for.end: ; preds = %for.body, %entry266 ret void267}268 269define void @neg_rhs_maybe_infinite(i16 %n.raw) {270; CHECK-LABEL: 'neg_rhs_maybe_infinite'271; CHECK-NEXT: Determining loop execution counts for: @neg_rhs_maybe_infinite272; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.273; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.274; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.275; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>))276; CHECK-NEXT: Predicates:277; CHECK-NEXT: {1,+,1}<%for.body> Added Flags: <nusw>278; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 -2279; CHECK-NEXT: Predicates:280; CHECK-NEXT: {1,+,1}<%for.body> Added Flags: <nusw>281; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>))282; CHECK-NEXT: Predicates:283; CHECK-NEXT: {1,+,1}<%for.body> Added Flags: <nusw>284;285entry:286 %n.and = and i16 %n.raw, 255287 %n = add nsw i16 %n.and, -1288 br label %for.body289 290for.body: ; preds = %entry, %for.body291 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]292 %iv.next = add i8 %iv, 1293 store i8 %iv, ptr @G294 %zext = zext i8 %iv.next to i16295 %cmp = icmp ult i16 %zext, %n296 br i1 %cmp, label %for.body, label %for.end297 298for.end: ; preds = %for.body, %entry299 ret void300}301 302; Because of the range on RHS including only values within i8, we don't need303; the must exit property304define void @rhs_narrow_range(i16 %n.raw) {305; CHECK-LABEL: 'rhs_narrow_range'306; CHECK-NEXT: Determining loop execution counts for: @rhs_narrow_range307; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (1 umax (2 * (zext i7 (trunc i16 (%n.raw /u 2) to i7) to i16))<nuw><nsw>))<nsw>308; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 253309; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (1 umax (2 * (zext i7 (trunc i16 (%n.raw /u 2) to i7) to i16))<nuw><nsw>))<nsw>310; CHECK-NEXT: Loop %for.body: Trip multiple is 1311;312entry:313 %n = and i16 %n.raw, 254314 br label %for.body315 316for.body: ; preds = %entry, %for.body317 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]318 %iv.next = add i8 %iv, 1319 store i8 %iv, ptr @G320 %zext = zext i8 %iv.next to i16321 %cmp = icmp ult i16 %zext, %n322 br i1 %cmp, label %for.body, label %for.end323 324for.end: ; preds = %for.body, %entry325 ret void326}327 328define void @ugt_constant_rhs(i16 %n.raw, i8 %start) mustprogress {329;330; CHECK-LABEL: 'ugt_constant_rhs'331; CHECK-NEXT: Determining loop execution counts for: @ugt_constant_rhs332; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.333; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.334; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.335;336entry:337 br label %for.body338 339for.body: ; preds = %entry, %for.body340 %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ]341 %iv.next = add i8 %iv, 1342 %zext = zext i8 %iv.next to i16343 %cmp = icmp ugt i16 %zext, 254344 br i1 %cmp, label %for.body, label %for.end345 346for.end: ; preds = %for.body, %entry347 ret void348}349 350define void @ult_constant_rhs(i16 %n.raw, i8 %start) {351;352; CHECK-LABEL: 'ult_constant_rhs'353; CHECK-NEXT: Determining loop execution counts for: @ult_constant_rhs354; CHECK-NEXT: Loop %for.body: backedge-taken count is (255 + (-1 * (zext i8 (1 + %start) to i16))<nsw>)<nsw>355; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 255356; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (255 + (-1 * (zext i8 (1 + %start) to i16))<nsw>)<nsw>357; CHECK-NEXT: Loop %for.body: Trip multiple is 1358;359entry:360 br label %for.body361 362for.body: ; preds = %entry, %for.body363 %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ]364 %iv.next = add i8 %iv, 1365 %zext = zext i8 %iv.next to i16366 %cmp = icmp ult i16 %zext, 255367 br i1 %cmp, label %for.body, label %for.end368 369for.end: ; preds = %for.body, %entry370 ret void371}372 373define void @ult_constant_rhs_stride2(i16 %n.raw, i8 %start) {374;375; CHECK-LABEL: 'ult_constant_rhs_stride2'376; CHECK-NEXT: Determining loop execution counts for: @ult_constant_rhs_stride2377; CHECK-NEXT: Loop %for.body: backedge-taken count is ((1 + (-1 * (zext i8 (2 + %start) to i16))<nsw> + (254 umax (zext i8 (2 + %start) to i16))) /u 2)378; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 127379; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((1 + (-1 * (zext i8 (2 + %start) to i16))<nsw> + (254 umax (zext i8 (2 + %start) to i16))) /u 2)380; CHECK-NEXT: Loop %for.body: Trip multiple is 1381;382entry:383 br label %for.body384 385for.body: ; preds = %entry, %for.body386 %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ]387 %iv.next = add i8 %iv, 2388 %zext = zext i8 %iv.next to i16389 %cmp = icmp ult i16 %zext, 254390 br i1 %cmp, label %for.body, label %for.end391 392for.end: ; preds = %for.body, %entry393 ret void394}395 396define void @ult_constant_rhs_stride2_neg(i16 %n.raw, i8 %start) {397;398; CHECK-LABEL: 'ult_constant_rhs_stride2_neg'399; CHECK-NEXT: Determining loop execution counts for: @ult_constant_rhs_stride2_neg400; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.401; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.402; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.403; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((256 + (-1 * (zext i8 (2 + %start) to i16))<nsw>)<nsw> /u 2)404; CHECK-NEXT: Predicates:405; CHECK-NEXT: {(2 + %start),+,2}<%for.body> Added Flags: <nusw>406; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 128407; CHECK-NEXT: Predicates:408; CHECK-NEXT: {(2 + %start),+,2}<%for.body> Added Flags: <nusw>409; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is ((256 + (-1 * (zext i8 (2 + %start) to i16))<nsw>)<nsw> /u 2)410; CHECK-NEXT: Predicates:411; CHECK-NEXT: {(2 + %start),+,2}<%for.body> Added Flags: <nusw>412;413entry:414 br label %for.body415 416for.body: ; preds = %entry, %for.body417 %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ]418 %iv.next = add i8 %iv, 2419 %zext = zext i8 %iv.next to i16420 %cmp = icmp ult i16 %zext, 255421 br i1 %cmp, label %for.body, label %for.end422 423for.end: ; preds = %for.body, %entry424 ret void425}426 427 428define void @ult_restricted_rhs(i16 %n.raw) {429; CHECK-LABEL: 'ult_restricted_rhs'430; CHECK-NEXT: Determining loop execution counts for: @ult_restricted_rhs431; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (1 umax (zext i8 (trunc i16 %n.raw to i8) to i16)))<nsw>432; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 254433; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (1 umax (zext i8 (trunc i16 %n.raw to i8) to i16)))<nsw>434; CHECK-NEXT: Loop %for.body: Trip multiple is 1435;436entry:437 %n = and i16 %n.raw, 255438 br label %for.body439 440for.body: ; preds = %entry, %for.body441 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]442 %iv.next = add i8 %iv, 1443 %zext = zext i8 %iv.next to i16444 %cmp = icmp ult i16 %zext, %n445 br i1 %cmp, label %for.body, label %for.end446 447for.end: ; preds = %for.body, %entry448 ret void449}450 451define void @ult_guarded_rhs(i16 %n) {;452; CHECK-LABEL: 'ult_guarded_rhs'453; CHECK-NEXT: Determining loop execution counts for: @ult_guarded_rhs454; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (1 umax %n))455; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 -2456; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (1 umax %n))457; CHECK-NEXT: Loop %for.body: Trip multiple is 1458;459entry:460 %in_range = icmp ult i16 %n, 256461 br i1 %in_range, label %for.body, label %for.end462 463for.body: ; preds = %entry, %for.body464 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]465 %iv.next = add i8 %iv, 1466 %zext = zext i8 %iv.next to i16467 %cmp = icmp ult i16 %zext, %n468 br i1 %cmp, label %for.body, label %for.end469 470for.end: ; preds = %for.body, %entry471 ret void472}473 474 475 476declare void @llvm.assume(i1)477 478