451 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py2; RUN: opt %s -passes='print<scalar-evolution>' -scalar-evolution-classify-expressions=0 -disable-output 2>&1 | FileCheck %s3 4target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"5target triple = "x86_64-unknown-linux-gnu"6 7; A collection of tests focused on exercising logic to prove no-unsigned wrap8; from mustprogress semantics of loops.9 10define void @test(i32 %N) mustprogress {11; CHECK-LABEL: 'test'12; CHECK-NEXT: Determining loop execution counts for: @test13; CHECK-NEXT: Loop %for.body: backedge-taken count is ((-2 + %N) /u 2)14; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 214748364715; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((-2 + %N) /u 2)16; CHECK-NEXT: Loop %for.body: Trip multiple is 117;18entry:19 br label %for.body20 21for.body:22 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]23 %iv.next = add i32 %iv, 224 %cmp = icmp ne i32 %iv.next, %N25 br i1 %cmp, label %for.body, label %for.cond.cleanup26 27for.cond.cleanup:28 ret void29}30 31define void @test_preinc(i32 %N) mustprogress {32; CHECK-LABEL: 'test_preinc'33; CHECK-NEXT: Determining loop execution counts for: @test_preinc34; CHECK-NEXT: Loop %for.body: backedge-taken count is (%N /u 2)35; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 214748364736; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (%N /u 2)37; CHECK-NEXT: Loop %for.body: Trip multiple is 138;39entry:40 br label %for.body41 42for.body:43 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]44 %iv.next = add i32 %iv, 245 %cmp = icmp ne i32 %iv, %N46 br i1 %cmp, label %for.body, label %for.cond.cleanup47 48for.cond.cleanup:49 ret void50 51}52 53@G = external global i3254 55define void @test_well_defined_infinite_st(i32 %N) mustprogress {56; CHECK-LABEL: 'test_well_defined_infinite_st'57; CHECK-NEXT: Determining loop execution counts for: @test_well_defined_infinite_st58; 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 ((-2 + %N) /u 2)62; CHECK-NEXT: Predicates:63; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 064; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i32 214748364765; CHECK-NEXT: Predicates:66; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 067; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is ((-2 + %N) /u 2)68; CHECK-NEXT: Predicates:69; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 070;71entry:72 br label %for.body73 74for.body:75 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]76 %iv.next = add i32 %iv, 277 store volatile i32 0, ptr @G78 %cmp = icmp ne i32 %iv.next, %N79 br i1 %cmp, label %for.body, label %for.cond.cleanup80 81for.cond.cleanup:82 ret void83}84 85define void @test_well_defined_infinite_ld(i32 %N) mustprogress {86; CHECK-LABEL: 'test_well_defined_infinite_ld'87; CHECK-NEXT: Determining loop execution counts for: @test_well_defined_infinite_ld88; 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; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-2 + %N) /u 2)92; CHECK-NEXT: Predicates:93; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 094; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i32 214748364795; CHECK-NEXT: Predicates:96; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 097; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is ((-2 + %N) /u 2)98; CHECK-NEXT: Predicates:99; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0100;101entry:102 br label %for.body103 104for.body:105 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]106 %iv.next = add i32 %iv, 2107 %val = load volatile i32, ptr @G108 %cmp = icmp ne i32 %iv.next, %N109 br i1 %cmp, label %for.body, label %for.cond.cleanup110 111for.cond.cleanup:112 ret void113}114 115define void @test_no_mustprogress(i32 %N) {116; CHECK-LABEL: 'test_no_mustprogress'117; CHECK-NEXT: Determining loop execution counts for: @test_no_mustprogress118; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.119; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.120; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.121; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-2 + %N) /u 2)122; CHECK-NEXT: Predicates:123; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0124; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i32 2147483647125; CHECK-NEXT: Predicates:126; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0127; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is ((-2 + %N) /u 2)128; CHECK-NEXT: Predicates:129; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0130;131entry:132 br label %for.body133 134for.body:135 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]136 %iv.next = add i32 %iv, 2137 %cmp = icmp ne i32 %iv.next, %N138 br i1 %cmp, label %for.body, label %for.cond.cleanup139 140for.cond.cleanup:141 ret void142 143}144 145 146define void @test_1024(i32 %N) mustprogress {147; CHECK-LABEL: 'test_1024'148; CHECK-NEXT: Determining loop execution counts for: @test_1024149; CHECK-NEXT: Loop %for.body: backedge-taken count is ((-1024 + %N) /u 1024)150; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 4194303151; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((-1024 + %N) /u 1024)152; CHECK-NEXT: Loop %for.body: Trip multiple is 1153;154entry:155 br label %for.body156 157for.body:158 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]159 %iv.next = add i32 %iv, 1024160 %cmp = icmp ne i32 %iv.next, %N161 br i1 %cmp, label %for.body, label %for.cond.cleanup162 163for.cond.cleanup:164 ret void165}166 167define void @test_uneven_divide(i32 %N) mustprogress {168; CHECK-LABEL: 'test_uneven_divide'169; CHECK-NEXT: Determining loop execution counts for: @test_uneven_divide170; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (-1431655765 * %N))171; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 -1172; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (-1431655765 * %N))173; CHECK-NEXT: Loop %for.body: Trip multiple is 1174;175entry:176 br label %for.body177 178for.body:179 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]180 %iv.next = add i32 %iv, 3181 %cmp = icmp ne i32 %iv.next, %N182 br i1 %cmp, label %for.body, label %for.cond.cleanup183 184for.cond.cleanup:185 ret void186}187 188define void @test_non_invariant_rhs() mustprogress {189; CHECK-LABEL: 'test_non_invariant_rhs'190; CHECK-NEXT: Determining loop execution counts for: @test_non_invariant_rhs191; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.192; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.193; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.194;195entry:196 br label %for.body197 198for.body:199 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]200 %iv.next = add i32 %iv, 2201 %N = load i32, ptr @G202 %cmp = icmp ne i32 %iv.next, %N203 br i1 %cmp, label %for.body, label %for.cond.cleanup204 205for.cond.cleanup:206 ret void207}208 209declare void @mayexit()210 211define void @test_abnormal_exit(i32 %N) mustprogress {212; CHECK-LABEL: 'test_abnormal_exit'213; CHECK-NEXT: Determining loop execution counts for: @test_abnormal_exit214; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.215; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.216; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.217; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-2 + %N) /u 2)218; CHECK-NEXT: Predicates:219; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0220; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i32 2147483647221; CHECK-NEXT: Predicates:222; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0223; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is ((-2 + %N) /u 2)224; CHECK-NEXT: Predicates:225; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0226;227entry:228 br label %for.body229 230for.body:231 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]232 %iv.next = add i32 %iv, 2233 call void @mayexit()234 %cmp = icmp ne i32 %iv.next, %N235 br i1 %cmp, label %for.body, label %for.cond.cleanup236 237for.cond.cleanup:238 ret void239}240 241 242define void @test_other_exit(i32 %N) mustprogress {243; CHECK-LABEL: 'test_other_exit'244; CHECK-NEXT: Determining loop execution counts for: @test_other_exit245; CHECK-NEXT: Loop %for.body: <multiple exits> Unpredictable backedge-taken count.246; CHECK-NEXT: exit count for for.body: i32 9247; CHECK-NEXT: exit count for for.latch: ***COULDNOTCOMPUTE***248; CHECK-NEXT: predicated exit count for for.latch: ((-2 + %N) /u 2)249; CHECK-NEXT: Predicates:250; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0251; CHECK-EMPTY:252; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 9253; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is i32 9254; CHECK-NEXT: symbolic max exit count for for.body: i32 9255; CHECK-NEXT: symbolic max exit count for for.latch: ***COULDNOTCOMPUTE***256; CHECK-NEXT: predicated symbolic max exit count for for.latch: ((-2 + %N) /u 2)257; CHECK-NEXT: Predicates:258; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0259; CHECK-EMPTY:260; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (9 umin ((-2 + %N) /u 2))261; CHECK-NEXT: Predicates:262; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0263; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (9 umin ((-2 + %N) /u 2))264; CHECK-NEXT: Predicates:265; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0266;267entry:268 br label %for.body269 270for.body:271 %iv = phi i32 [ %iv.next, %for.latch ], [ 0, %entry ]272 %iv.next = add i32 %iv, 2273 %cmp1 = icmp ne i32 %iv.next, 20274 br i1 %cmp1, label %for.latch, label %for.cond.cleanup275 276for.latch:277 %cmp2 = icmp ne i32 %iv.next, %N278 br i1 %cmp2, label %for.body, label %for.cond.cleanup279 280for.cond.cleanup:281 ret void282}283 284define void @test_zext(i64 %N) mustprogress {285; CHECK-LABEL: 'test_zext'286; CHECK-NEXT: Determining loop execution counts for: @test_zext287; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.288; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.289; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.290; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (%N /u 2)291; CHECK-NEXT: Predicates:292; CHECK-NEXT: {0,+,2}<nuw><%for.body> Added Flags: <nusw>293; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807294; CHECK-NEXT: Predicates:295; CHECK-NEXT: {0,+,2}<nuw><%for.body> Added Flags: <nusw>296; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (%N /u 2)297; CHECK-NEXT: Predicates:298; CHECK-NEXT: {0,+,2}<nuw><%for.body> Added Flags: <nusw>299;300entry:301 br label %for.body302 303for.body:304 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]305 %iv.next = add i32 %iv, 2306 %zext = zext i32 %iv to i64307 %cmp = icmp ne i64 %zext, %N308 br i1 %cmp, label %for.body, label %for.cond.cleanup309 310for.cond.cleanup:311 ret void312}313 314define void @test_sext(i64 %N) mustprogress {315; CHECK-LABEL: 'test_sext'316; CHECK-NEXT: Determining loop execution counts for: @test_sext317; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.318; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.319; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.320; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (%N /u 2)321; CHECK-NEXT: Predicates:322; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>323; CHECK-NEXT: Equal predicate: (zext i1 (trunc i64 %N to i1) to i64) == 0324; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807325; CHECK-NEXT: Predicates:326; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>327; CHECK-NEXT: Equal predicate: (zext i1 (trunc i64 %N to i1) to i64) == 0328; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (%N /u 2)329; CHECK-NEXT: Predicates:330; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>331; CHECK-NEXT: Equal predicate: (zext i1 (trunc i64 %N to i1) to i64) == 0332;333entry:334 br label %for.body335 336for.body:337 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]338 %iv.next = add i32 %iv, 2339 %sext = sext i32 %iv to i64340 %cmp = icmp ne i64 %sext, %N341 br i1 %cmp, label %for.body, label %for.cond.cleanup342 343for.cond.cleanup:344 ret void345}346 347define void @test_zext_of_sext(i64 %N) mustprogress {348; CHECK-LABEL: 'test_zext_of_sext'349; CHECK-NEXT: Determining loop execution counts for: @test_zext_of_sext350; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.351; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.352; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.353; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (%N /u 2)354; CHECK-NEXT: Predicates:355; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>356; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nusw>357; CHECK-NEXT: Equal predicate: (zext i1 (trunc i64 %N to i1) to i64) == 0358; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807359; CHECK-NEXT: Predicates:360; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>361; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nusw>362; CHECK-NEXT: Equal predicate: (zext i1 (trunc i64 %N to i1) to i64) == 0363; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (%N /u 2)364; CHECK-NEXT: Predicates:365; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>366; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nusw>367; CHECK-NEXT: Equal predicate: (zext i1 (trunc i64 %N to i1) to i64) == 0368;369entry:370 br label %for.body371 372for.body:373 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]374 %iv.next = add i32 %iv, 2375 %sext = sext i32 %iv to i48376 %zext = zext i48 %sext to i64377 %cmp = icmp ne i64 %zext, %N378 br i1 %cmp, label %for.body, label %for.cond.cleanup379 380for.cond.cleanup:381 ret void382}383 384define void @test_zext_offset(i64 %N) mustprogress {385; CHECK-LABEL: 'test_zext_offset'386; CHECK-NEXT: Determining loop execution counts for: @test_zext_offset387; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.388; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.389; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.390; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-21 + %N) /u 2)391; CHECK-NEXT: Predicates:392; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nusw>393; CHECK-NEXT: Equal predicate: (zext i1 (true + (trunc i64 %N to i1)) to i64) == 0394; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807395; CHECK-NEXT: Predicates:396; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nusw>397; CHECK-NEXT: Equal predicate: (zext i1 (true + (trunc i64 %N to i1)) to i64) == 0398; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is ((-21 + %N) /u 2)399; CHECK-NEXT: Predicates:400; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nusw>401; CHECK-NEXT: Equal predicate: (zext i1 (true + (trunc i64 %N to i1)) to i64) == 0402;403entry:404 br label %for.body405 406for.body:407 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]408 %iv.next = add i32 %iv, 2409 %zext = zext i32 %iv to i64410 %offset = add i64 %zext, 21411 %cmp = icmp ne i64 %offset, %N412 br i1 %cmp, label %for.body, label %for.cond.cleanup413 414for.cond.cleanup:415 ret void416}417 418define void @test_sext_offset(i64 %N) mustprogress {419; CHECK-LABEL: 'test_sext_offset'420; CHECK-NEXT: Determining loop execution counts for: @test_sext_offset421; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count.422; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count.423; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count.424; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-21 + %N) /u 2)425; CHECK-NEXT: Predicates:426; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>427; CHECK-NEXT: Equal predicate: (zext i1 (true + (trunc i64 %N to i1)) to i64) == 0428; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807429; CHECK-NEXT: Predicates:430; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>431; CHECK-NEXT: Equal predicate: (zext i1 (true + (trunc i64 %N to i1)) to i64) == 0432; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is ((-21 + %N) /u 2)433; CHECK-NEXT: Predicates:434; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>435; CHECK-NEXT: Equal predicate: (zext i1 (true + (trunc i64 %N to i1)) to i64) == 0436;437entry:438 br label %for.body439 440for.body:441 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]442 %iv.next = add i32 %iv, 2443 %sext = sext i32 %iv to i64444 %offset = add i64 %sext, 21445 %cmp = icmp ne i64 %offset, %N446 br i1 %cmp, label %for.body, label %for.cond.cleanup447 448for.cond.cleanup:449 ret void450}451