1; REQUIRES: asserts 2; RUN: opt -S -basic-aa -licm -ipt-expensive-asserts=true < %s | FileCheck %s 3; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -ipt-expensive-asserts=true -S %s | FileCheck %s 4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 5target triple = "x86_64-unknown-linux-gnu" 6 7declare void @f() nounwind 8declare void @llvm.experimental.guard(i1,...) 9 10; constant fold on first ieration 11define i32 @test1(i32* noalias nocapture readonly %a) nounwind uwtable { 12; CHECK-LABEL: @test1( 13entry: 14; CHECK: %i1 = load i32, i32* %a, align 4 15; CHECK-NEXT: br label %for.body 16 br label %for.body 17 18for.body: 19 %iv = phi i32 [ 0, %entry ], [ %inc, %continue ] 20 %acc = phi i32 [ 0, %entry ], [ %add, %continue ] 21 %r.chk = icmp ult i32 %iv, 2000 22 br i1 %r.chk, label %continue, label %fail 23continue: 24 %i1 = load i32, i32* %a, align 4 25 %add = add nsw i32 %i1, %acc 26 %inc = add nuw nsw i32 %iv, 1 27 %exitcond = icmp eq i32 %inc, 1000 28 br i1 %exitcond, label %for.cond.cleanup, label %for.body 29 30for.cond.cleanup: 31 ret i32 %add 32 33fail: 34 call void @f() 35 ret i32 -1 36} 37 38; Same as test1, but with a floating point IR and fcmp 39define i32 @test_fcmp(i32* noalias nocapture readonly %a) nounwind uwtable { 40; CHECK-LABEL: @test_fcmp( 41entry: 42; CHECK: %i1 = load i32, i32* %a, align 4 43; CHECK-NEXT: br label %for.body 44 br label %for.body 45 46for.body: 47 %iv = phi float [ 0.0, %entry ], [ %inc, %continue ] 48 %acc = phi i32 [ 0, %entry ], [ %add, %continue ] 49 %r.chk = fcmp olt float %iv, 2000.0 50 br i1 %r.chk, label %continue, label %fail 51continue: 52 %i1 = load i32, i32* %a, align 4 53 %add = add nsw i32 %i1, %acc 54 %inc = fadd float %iv, 1.0 55 %exitcond = fcmp ogt float %inc, 1000.0 56 br i1 %exitcond, label %for.cond.cleanup, label %for.body 57 58for.cond.cleanup: 59 ret i32 %add 60 61fail: 62 call void @f() 63 ret i32 -1 64} 65 66; Count down from a.length w/entry guard 67; TODO: currently unable to prove the following: 68; ule i32 (add nsw i32 %len, -1), %len where len is [0, 512] 69define i32 @test2(i32* noalias nocapture readonly %a) nounwind uwtable { 70; CHECK-LABEL: @test2( 71entry: 72 %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512} 73 %is.non.pos = icmp eq i32 %len, 0 74 br i1 %is.non.pos, label %fail, label %preheader 75preheader: 76 %lenminusone = add nsw i32 %len, -1 77 br label %for.body 78for.body: 79 %iv = phi i32 [ %lenminusone, %preheader ], [ %dec, %continue ] 80 %acc = phi i32 [ 0, %preheader ], [ %add, %continue ] 81 %r.chk = icmp ule i32 %iv, %len 82 br i1 %r.chk, label %continue, label %fail 83continue: 84; CHECK-LABEL: continue 85; CHECK: %i1 = load i32, i32* %a, align 4 86 %i1 = load i32, i32* %a, align 4 87 %add = add nsw i32 %i1, %acc 88 %dec = add nsw i32 %iv, -1 89 %exitcond = icmp eq i32 %dec, 0 90 br i1 %exitcond, label %for.cond.cleanup, label %for.body 91 92for.cond.cleanup: 93 ret i32 %add 94 95fail: 96 call void @f() 97 ret i32 -1 98} 99 100; trivially true for zero 101define i32 @test3(i32* noalias nocapture readonly %a) nounwind uwtable { 102; CHECK-LABEL: @test3( 103entry: 104 %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512} 105 %is.zero = icmp eq i32 %len, 0 106 br i1 %is.zero, label %fail, label %preheader 107preheader: 108; CHECK: %i1 = load i32, i32* %a, align 4 109; CHECK-NEXT: br label %for.body 110 br label %for.body 111for.body: 112 %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ] 113 %acc = phi i32 [ 0, %preheader ], [ %add, %continue ] 114 %r.chk = icmp ule i32 %iv, %len 115 br i1 %r.chk, label %continue, label %fail 116continue: 117 %i1 = load i32, i32* %a, align 4 118 %add = add nsw i32 %i1, %acc 119 %inc = add nuw nsw i32 %iv, 1 120 %exitcond = icmp eq i32 %inc, 1000 121 br i1 %exitcond, label %for.cond.cleanup, label %for.body 122 123for.cond.cleanup: 124 ret i32 %add 125 126fail: 127 call void @f() 128 ret i32 -1 129} 130 131; requires fact length is non-zero 132define i32 @test4(i32* noalias nocapture readonly %a) nounwind uwtable { 133; CHECK-LABEL: @test4( 134; CHECK-NEXT: entry: 135; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[A:%.*]], align 4, !range !0 136; CHECK-NEXT: [[IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0 137; CHECK-NEXT: br i1 [[IS_ZERO]], label [[FAIL:%.*]], label [[PREHEADER:%.*]] 138; CHECK: preheader: 139; CHECK-NEXT: [[I1:%.*]] = load i32, i32* [[A]], align 4 140; CHECK-NEXT: br label [[FOR_BODY:%.*]] 141; CHECK: for.body: 142; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[INC:%.*]], [[CONTINUE:%.*]] ] 143; CHECK-NEXT: [[ACC:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[ADD:%.*]], [[CONTINUE]] ] 144; CHECK-NEXT: [[R_CHK:%.*]] = icmp ult i32 [[IV]], [[LEN]] 145; CHECK-NEXT: br i1 [[R_CHK]], label [[CONTINUE]], label [[FAIL_LOOPEXIT:%.*]] 146; CHECK: continue: 147; CHECK-NEXT: [[ADD]] = add nsw i32 [[I1]], [[ACC]] 148; CHECK-NEXT: [[INC]] = add nuw nsw i32 [[IV]], 1 149; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000 150; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]] 151; CHECK: for.cond.cleanup: 152; CHECK-NEXT: [[ADD_LCSSA:%.*]] = phi i32 [ [[ADD]], [[CONTINUE]] ] 153; CHECK-NEXT: ret i32 [[ADD_LCSSA]] 154; CHECK: fail.loopexit: 155; CHECK-NEXT: br label [[FAIL]] 156; CHECK: fail: 157; CHECK-NEXT: call void @f() 158; CHECK-NEXT: ret i32 -1 159; 160entry: 161 %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512} 162 %is.zero = icmp eq i32 %len, 0 163 br i1 %is.zero, label %fail, label %preheader 164preheader: 165 br label %for.body 166for.body: 167 %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ] 168 %acc = phi i32 [ 0, %preheader ], [ %add, %continue ] 169 %r.chk = icmp ult i32 %iv, %len 170 br i1 %r.chk, label %continue, label %fail 171continue: 172 %i1 = load i32, i32* %a, align 4 173 %add = add nsw i32 %i1, %acc 174 %inc = add nuw nsw i32 %iv, 1 175 %exitcond = icmp eq i32 %inc, 1000 176 br i1 %exitcond, label %for.cond.cleanup, label %for.body 177 178for.cond.cleanup: 179 ret i32 %add 180 181fail: 182 call void @f() 183 ret i32 -1 184} 185 186; variation on test1 with branch swapped 187define i32 @test-brswap(i32* noalias nocapture readonly %a) nounwind uwtable { 188; CHECK-LABEL: @test-brswap( 189entry: 190; CHECK: %i1 = load i32, i32* %a, align 4 191; CHECK-NEXT: br label %for.body 192 br label %for.body 193 194for.body: 195 %iv = phi i32 [ 0, %entry ], [ %inc, %continue ] 196 %acc = phi i32 [ 0, %entry ], [ %add, %continue ] 197 %r.chk = icmp ugt i32 %iv, 2000 198 br i1 %r.chk, label %fail, label %continue 199continue: 200 %i1 = load i32, i32* %a, align 4 201 %add = add nsw i32 %i1, %acc 202 %inc = add nuw nsw i32 %iv, 1 203 %exitcond = icmp eq i32 %inc, 1000 204 br i1 %exitcond, label %for.cond.cleanup, label %for.body 205 206for.cond.cleanup: 207 ret i32 %add 208 209fail: 210 call void @f() 211 ret i32 -1 212} 213 214define i32 @test-nonphi(i32* noalias nocapture readonly %a) nounwind uwtable { 215; CHECK-LABEL: @test-nonphi( 216entry: 217 br label %for.body 218 219for.body: 220; CHECK-LABEL: continue 221; CHECK: %i1 = load i32, i32* %a, align 4 222 %iv = phi i32 [ 0, %entry ], [ %inc, %continue ] 223 %acc = phi i32 [ 0, %entry ], [ %add, %continue ] 224 %xor = xor i32 %iv, 72 225 %r.chk = icmp ugt i32 %xor, 2000 226 br i1 %r.chk, label %fail, label %continue 227continue: 228 %i1 = load i32, i32* %a, align 4 229 %add = add nsw i32 %i1, %acc 230 %inc = add nuw nsw i32 %iv, 1 231 %exitcond = icmp eq i32 %inc, 1000 232 br i1 %exitcond, label %for.cond.cleanup, label %for.body 233 234for.cond.cleanup: 235 ret i32 %add 236 237fail: 238 call void @f() 239 ret i32 -1 240} 241 242define i32 @test-wrongphi(i32* noalias nocapture readonly %a) nounwind uwtable { 243; CHECK-LABEL: @test-wrongphi( 244entry: 245 br label %for.body 246 247for.body: 248 %iv = phi i32 [ 0, %entry ], [ %inc, %continue ] 249 %acc = phi i32 [ 0, %entry ], [ %add, %continue ] 250 %cond = icmp ult i32 %iv, 500 251 br i1 %cond, label %dummy_block1, label %dummy_block2 252 253dummy_block1: 254 br label %dummy_block2 255 256dummy_block2: 257 %wrongphi = phi i32 [11, %for.body], [12, %dummy_block1] 258 %r.chk = icmp ugt i32 %wrongphi, 2000 259 br i1 %r.chk, label %fail, label %continue 260continue: 261; CHECK-LABEL: continue 262; CHECK: %i1 = load i32, i32* %a, align 4 263 %i1 = load i32, i32* %a, align 4 264 %add = add nsw i32 %i1, %acc 265 %inc = add nuw nsw i32 %iv, 1 266 %exitcond = icmp eq i32 %inc, 1000 267 br i1 %exitcond, label %for.cond.cleanup, label %for.body 268 269for.cond.cleanup: 270 ret i32 %add 271 272fail: 273 call void @f() 274 ret i32 -1 275} 276 277; This works because loop-simplify is run implicitly, but test for it anyways 278define i32 @test-multiple-latch(i32* noalias nocapture readonly %a) nounwind uwtable { 279; CHECK-LABEL: @test-multiple-latch( 280entry: 281; CHECK: %i1 = load i32, i32* %a, align 4 282; CHECK-NEXT: br label %for.body 283 br label %for.body 284 285for.body: 286 %iv = phi i32 [ 0, %entry ], [ %inc, %continue1 ], [ %inc, %continue2 ] 287 %acc = phi i32 [ 0, %entry ], [ %add, %continue1 ], [ %add, %continue2 ] 288 %r.chk = icmp ult i32 %iv, 2000 289 br i1 %r.chk, label %continue1, label %fail 290continue1: 291 %i1 = load i32, i32* %a, align 4 292 %add = add nsw i32 %i1, %acc 293 %inc = add nuw nsw i32 %iv, 1 294 %cmp = icmp eq i32 %add, 0 295 br i1 %cmp, label %continue2, label %for.body 296continue2: 297 %exitcond = icmp eq i32 %inc, 1000 298 br i1 %exitcond, label %for.cond.cleanup, label %for.body 299 300for.cond.cleanup: 301 ret i32 %add 302 303fail: 304 call void @f() 305 ret i32 -1 306} 307 308define void @test-hoisting-in-presence-of-guards(i1 %c, i32* %p) { 309 310; CHECK-LABEL: @test-hoisting-in-presence-of-guards 311; CHECK: entry: 312; CHECK: %a = load i32, i32* %p 313; CHECK: %invariant_cond = icmp ne i32 %a, 100 314; CHECK: loop: 315 316entry: 317 br label %loop 318 319loop: 320 %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] 321 %iv.next = add i32 %iv, 1 322 %a = load i32, i32* %p 323 %invariant_cond = icmp ne i32 %a, 100 324 call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond) [ "deopt"() ] 325 %loop_cond = icmp slt i32 %iv.next, 1000 326 br i1 %loop_cond, label %loop, label %exit 327 328exit: 329 ret void 330} 331 332 333declare void @may_throw() inaccessiblememonly 334 335; Test that we can sink a mustexecute load from loop header even in presence of 336; throwing instructions after it. 337define void @test_hoist_from_header_01(i32* %p, i32 %n) { 338 339; CHECK-LABEL: @test_hoist_from_header_01( 340; CHECK: entry: 341; CHECK-NEXT: %load = load i32, i32* %p 342; CHECK-NOT: load i32 343 344entry: 345 br label %loop 346 347loop: 348 %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] 349 %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] 350 %load = load i32, i32* %p 351 call void @may_throw() 352 %cond = icmp slt i32 %iv, %n 353 br i1 %cond, label %if.true, label %if.false 354 355if.true: 356 %a = add i32 %iv, %iv 357 br label %backedge 358 359if.false: 360 %b = mul i32 %iv, %iv 361 br label %backedge 362 363backedge: 364 %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] 365 %iv.next = add i32 %iv, %merge 366 %loop.cond = icmp ult i32 %iv.next, %load 367 br i1 %loop.cond, label %loop, label %exit 368 369exit: 370 ret void 371} 372 373define void @test_hoist_from_header_02(i32* %p, i32 %n) { 374 375; CHECK-LABEL: @test_hoist_from_header_02( 376; CHECK: entry: 377; CHECK-NEXT: %load = load i32, i32* %p 378; CHECK-NOT: load i32 379 380entry: 381 br label %loop 382 383loop: 384 %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] 385 %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] 386 %load = load i32, i32* %p 387 %cond = icmp slt i32 %iv, %n 388 br i1 %cond, label %if.true, label %if.false 389 390if.true: 391 call void @may_throw() 392 %a = add i32 %iv, %iv 393 br label %backedge 394 395if.false: 396 %b = mul i32 %iv, %iv 397 br label %backedge 398 399backedge: 400 %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] 401 %iv.next = add i32 %iv, %merge 402 %loop.cond = icmp ult i32 %iv.next, %load 403 br i1 %loop.cond, label %loop, label %exit 404 405exit: 406 ret void 407} 408 409define void @test_hoist_from_header_03(i32* %p, i32 %n) { 410 411; CHECK-LABEL: @test_hoist_from_header_03( 412; CHECK: entry: 413; CHECK-NEXT: %load = load i32, i32* %p 414; CHECK-NOT: load i32 415 416entry: 417 br label %loop 418 419loop: 420 %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] 421 %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] 422 %load = load i32, i32* %p 423 %cond = icmp slt i32 %iv, %n 424 br i1 %cond, label %if.true, label %if.false 425 426if.true: 427 %a = add i32 %iv, %iv 428 br label %backedge 429 430if.false: 431 %b = mul i32 %iv, %iv 432 br label %backedge 433 434backedge: 435 %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] 436 call void @may_throw() 437 %iv.next = add i32 %iv, %merge 438 %loop.cond = icmp ult i32 %iv.next, %load 439 br i1 %loop.cond, label %loop, label %exit 440 441exit: 442 ret void 443} 444 445; Check that a throwing instruction prohibits hoisting across it. 446define void @test_hoist_from_header_04(i32* %p, i32 %n) { 447 448; CHECK-LABEL: @test_hoist_from_header_04( 449; CHECK: entry: 450; CHECK: loop: 451; CHECK: %load = load i32, i32* %p 452 453entry: 454 br label %loop 455 456loop: 457 %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] 458 %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] 459 call void @may_throw() 460 %load = load i32, i32* %p 461 %cond = icmp slt i32 %iv, %n 462 br i1 %cond, label %if.true, label %if.false 463 464if.true: 465 %a = add i32 %iv, %iv 466 br label %backedge 467 468if.false: 469 %b = mul i32 %iv, %iv 470 br label %backedge 471 472backedge: 473 %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] 474 %iv.next = add i32 %iv, %merge 475 %loop.cond = icmp ult i32 %iv.next, %load 476 br i1 %loop.cond, label %loop, label %exit 477 478exit: 479 ret void 480} 481 482; Check that we can hoist a mustexecute load from backedge even if something 483; throws after it. 484define void @test_hoist_from_backedge_01(i32* %p, i32 %n) { 485 486; CHECK-LABEL: @test_hoist_from_backedge_01( 487; CHECK: entry: 488; CHECK-NEXT: %load = load i32, i32* %p 489; CHECK-NOT: load i32 490 491entry: 492 br label %loop 493 494loop: 495 %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] 496 %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] 497 %cond = icmp slt i32 %iv, %n 498 br i1 %cond, label %if.true, label %if.false 499 500if.true: 501 %a = add i32 %iv, %iv 502 br label %backedge 503 504if.false: 505 %b = mul i32 %iv, %iv 506 br label %backedge 507 508backedge: 509 %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] 510 %iv.next = add i32 %iv, %merge 511 %load = load i32, i32* %p 512 call void @may_throw() 513 %loop.cond = icmp ult i32 %iv.next, %load 514 br i1 %loop.cond, label %loop, label %exit 515 516exit: 517 ret void 518} 519 520; Check that we don't hoist the load if something before it can throw. 521define void @test_hoist_from_backedge_02(i32* %p, i32 %n) { 522 523; CHECK-LABEL: @test_hoist_from_backedge_02( 524; CHECK: entry: 525; CHECK: loop: 526; CHECK: %load = load i32, i32* %p 527 528entry: 529 br label %loop 530 531loop: 532 %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] 533 %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] 534 %cond = icmp slt i32 %iv, %n 535 br i1 %cond, label %if.true, label %if.false 536 537if.true: 538 %a = add i32 %iv, %iv 539 br label %backedge 540 541if.false: 542 %b = mul i32 %iv, %iv 543 br label %backedge 544 545backedge: 546 %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] 547 %iv.next = add i32 %iv, %merge 548 call void @may_throw() 549 %load = load i32, i32* %p 550 %loop.cond = icmp ult i32 %iv.next, %load 551 br i1 %loop.cond, label %loop, label %exit 552 553exit: 554 ret void 555} 556 557define void @test_hoist_from_backedge_03(i32* %p, i32 %n) { 558 559; CHECK-LABEL: @test_hoist_from_backedge_03( 560; CHECK: entry: 561; CHECK: loop: 562; CHECK: %load = load i32, i32* %p 563 564entry: 565 br label %loop 566 567loop: 568 %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] 569 %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] 570 %cond = icmp slt i32 %iv, %n 571 br i1 %cond, label %if.true, label %if.false 572 573if.true: 574 %a = add i32 %iv, %iv 575 br label %backedge 576 577if.false: 578 %b = mul i32 %iv, %iv 579 call void @may_throw() 580 br label %backedge 581 582backedge: 583 %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] 584 %iv.next = add i32 %iv, %merge 585 %load = load i32, i32* %p 586 %loop.cond = icmp ult i32 %iv.next, %load 587 br i1 %loop.cond, label %loop, label %exit 588 589exit: 590 ret void 591} 592 593define void @test_hoist_from_backedge_04(i32* %p, i32 %n) { 594 595; CHECK-LABEL: @test_hoist_from_backedge_04( 596; CHECK: entry: 597; CHECK: loop: 598; CHECK: %load = load i32, i32* %p 599 600entry: 601 br label %loop 602 603loop: 604 %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] 605 %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ] 606 call void @may_throw() 607 %cond = icmp slt i32 %iv, %n 608 br i1 %cond, label %if.true, label %if.false 609 610if.true: 611 %a = add i32 %iv, %iv 612 br label %backedge 613 614if.false: 615 %b = mul i32 %iv, %iv 616 br label %backedge 617 618backedge: 619 %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ] 620 %iv.next = add i32 %iv, %merge 621 %load = load i32, i32* %p 622 %loop.cond = icmp ult i32 %iv.next, %load 623 br i1 %loop.cond, label %loop, label %exit 624 625exit: 626 ret void 627} 628