1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py 2; RUN: opt %s -passes='print<scalar-evolution>' -scalar-evolution-classify-expressions=0 -disable-output 2>&1 | FileCheck %s 3 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 wrap 8; from mustprogress semantics of loops. 9 10define void @test(i32 %N) mustprogress { 11; CHECK-LABEL: 'test' 12; CHECK-NEXT: Determining loop execution counts for: @test 13; 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 2147483647 15; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((-2 + %N) /u 2) 16; CHECK-NEXT: Loop %for.body: Trip multiple is 1 17; 18entry: 19 br label %for.body 20 21for.body: 22 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 23 %iv.next = add i32 %iv, 2 24 %cmp = icmp ne i32 %iv.next, %N 25 br i1 %cmp, label %for.body, label %for.cond.cleanup 26 27for.cond.cleanup: 28 ret void 29} 30 31define void @test_preinc(i32 %N) mustprogress { 32; CHECK-LABEL: 'test_preinc' 33; CHECK-NEXT: Determining loop execution counts for: @test_preinc 34; 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 2147483647 36; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (%N /u 2) 37; CHECK-NEXT: Loop %for.body: Trip multiple is 1 38; 39entry: 40 br label %for.body 41 42for.body: 43 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 44 %iv.next = add i32 %iv, 2 45 %cmp = icmp ne i32 %iv, %N 46 br i1 %cmp, label %for.body, label %for.cond.cleanup 47 48for.cond.cleanup: 49 ret void 50 51} 52 53@G = external global i32 54 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_st 58; 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) == 0 64; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i32 2147483647 65; CHECK-NEXT: Predicates: 66; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0 67; 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) == 0 70; 71entry: 72 br label %for.body 73 74for.body: 75 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 76 %iv.next = add i32 %iv, 2 77 store volatile i32 0, ptr @G 78 %cmp = icmp ne i32 %iv.next, %N 79 br i1 %cmp, label %for.body, label %for.cond.cleanup 80 81for.cond.cleanup: 82 ret void 83} 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_ld 88; 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) == 0 94; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i32 2147483647 95; CHECK-NEXT: Predicates: 96; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0 97; 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) == 0 100; 101entry: 102 br label %for.body 103 104for.body: 105 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 106 %iv.next = add i32 %iv, 2 107 %val = load volatile i32, ptr @G 108 %cmp = icmp ne i32 %iv.next, %N 109 br i1 %cmp, label %for.body, label %for.cond.cleanup 110 111for.cond.cleanup: 112 ret void 113} 114 115define void @test_no_mustprogress(i32 %N) { 116; CHECK-LABEL: 'test_no_mustprogress' 117; CHECK-NEXT: Determining loop execution counts for: @test_no_mustprogress 118; 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) == 0 124; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i32 2147483647 125; CHECK-NEXT: Predicates: 126; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0 127; 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) == 0 130; 131entry: 132 br label %for.body 133 134for.body: 135 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 136 %iv.next = add i32 %iv, 2 137 %cmp = icmp ne i32 %iv.next, %N 138 br i1 %cmp, label %for.body, label %for.cond.cleanup 139 140for.cond.cleanup: 141 ret void 142 143} 144 145 146define void @test_1024(i32 %N) mustprogress { 147; CHECK-LABEL: 'test_1024' 148; CHECK-NEXT: Determining loop execution counts for: @test_1024 149; 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 4194303 151; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((-1024 + %N) /u 1024) 152; CHECK-NEXT: Loop %for.body: Trip multiple is 1 153; 154entry: 155 br label %for.body 156 157for.body: 158 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 159 %iv.next = add i32 %iv, 1024 160 %cmp = icmp ne i32 %iv.next, %N 161 br i1 %cmp, label %for.body, label %for.cond.cleanup 162 163for.cond.cleanup: 164 ret void 165} 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_divide 170; 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 -1 172; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (-1431655765 * %N)) 173; CHECK-NEXT: Loop %for.body: Trip multiple is 1 174; 175entry: 176 br label %for.body 177 178for.body: 179 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 180 %iv.next = add i32 %iv, 3 181 %cmp = icmp ne i32 %iv.next, %N 182 br i1 %cmp, label %for.body, label %for.cond.cleanup 183 184for.cond.cleanup: 185 ret void 186} 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_rhs 191; 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.body 197 198for.body: 199 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 200 %iv.next = add i32 %iv, 2 201 %N = load i32, ptr @G 202 %cmp = icmp ne i32 %iv.next, %N 203 br i1 %cmp, label %for.body, label %for.cond.cleanup 204 205for.cond.cleanup: 206 ret void 207} 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_exit 214; 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) == 0 220; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i32 2147483647 221; CHECK-NEXT: Predicates: 222; CHECK-NEXT: Equal predicate: (zext i1 (trunc i32 %N to i1) to i32) == 0 223; 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) == 0 226; 227entry: 228 br label %for.body 229 230for.body: 231 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 232 %iv.next = add i32 %iv, 2 233 call void @mayexit() 234 %cmp = icmp ne i32 %iv.next, %N 235 br i1 %cmp, label %for.body, label %for.cond.cleanup 236 237for.cond.cleanup: 238 ret void 239} 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_exit 245; CHECK-NEXT: Loop %for.body: <multiple exits> Unpredictable backedge-taken count. 246; CHECK-NEXT: exit count for for.body: i32 9 247; 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) == 0 251; CHECK-EMPTY: 252; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 9 253; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is i32 9 254; CHECK-NEXT: symbolic max exit count for for.body: i32 9 255; 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) == 0 259; 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) == 0 263; 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) == 0 266; 267entry: 268 br label %for.body 269 270for.body: 271 %iv = phi i32 [ %iv.next, %for.latch ], [ 0, %entry ] 272 %iv.next = add i32 %iv, 2 273 %cmp1 = icmp ne i32 %iv.next, 20 274 br i1 %cmp1, label %for.latch, label %for.cond.cleanup 275 276for.latch: 277 %cmp2 = icmp ne i32 %iv.next, %N 278 br i1 %cmp2, label %for.body, label %for.cond.cleanup 279 280for.cond.cleanup: 281 ret void 282} 283 284define void @test_zext(i64 %N) mustprogress { 285; CHECK-LABEL: 'test_zext' 286; CHECK-NEXT: Determining loop execution counts for: @test_zext 287; 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 9223372036854775807 294; 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.body 302 303for.body: 304 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 305 %iv.next = add i32 %iv, 2 306 %zext = zext i32 %iv to i64 307 %cmp = icmp ne i64 %zext, %N 308 br i1 %cmp, label %for.body, label %for.cond.cleanup 309 310for.cond.cleanup: 311 ret void 312} 313 314define void @test_sext(i64 %N) mustprogress { 315; CHECK-LABEL: 'test_sext' 316; CHECK-NEXT: Determining loop execution counts for: @test_sext 317; 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) == 0 324; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807 325; 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) == 0 328; 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) == 0 332; 333entry: 334 br label %for.body 335 336for.body: 337 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 338 %iv.next = add i32 %iv, 2 339 %sext = sext i32 %iv to i64 340 %cmp = icmp ne i64 %sext, %N 341 br i1 %cmp, label %for.body, label %for.cond.cleanup 342 343for.cond.cleanup: 344 ret void 345} 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_sext 350; 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) == 0 358; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807 359; 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) == 0 363; 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) == 0 368; 369entry: 370 br label %for.body 371 372for.body: 373 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 374 %iv.next = add i32 %iv, 2 375 %sext = sext i32 %iv to i48 376 %zext = zext i48 %sext to i64 377 %cmp = icmp ne i64 %zext, %N 378 br i1 %cmp, label %for.body, label %for.cond.cleanup 379 380for.cond.cleanup: 381 ret void 382} 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_offset 387; 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) == 0 394; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807 395; 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) == 0 398; 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) == 0 402; 403entry: 404 br label %for.body 405 406for.body: 407 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 408 %iv.next = add i32 %iv, 2 409 %zext = zext i32 %iv to i64 410 %offset = add i64 %zext, 21 411 %cmp = icmp ne i64 %offset, %N 412 br i1 %cmp, label %for.body, label %for.cond.cleanup 413 414for.cond.cleanup: 415 ret void 416} 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_offset 421; 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) == 0 428; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i64 9223372036854775807 429; 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) == 0 432; 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) == 0 436; 437entry: 438 br label %for.body 439 440for.body: 441 %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ] 442 %iv.next = add i32 %iv, 2 443 %sext = sext i32 %iv to i64 444 %offset = add i64 %sext, 21 445 %cmp = icmp ne i64 %offset, %N 446 br i1 %cmp, label %for.body, label %for.cond.cleanup 447 448for.cond.cleanup: 449 ret void 450} 451