1; RUN: opt -passes='loop(unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s 2; RUN: opt -passes='loop-mssa(unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s 3; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -S < %s | FileCheck %s 4; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s | FileCheck %s 5 6declare i32 @a() 7declare i32 @b() 8declare i32 @c() 9declare i32 @d() 10 11declare void @sink1(i32) 12declare void @sink2(i32) 13 14declare i1 @cond() 15declare i32 @cond.i32() 16 17; Negative test: we cannot unswitch convergent calls. 18define void @test_no_unswitch_convergent(i1* %ptr, i1 %cond) { 19; CHECK-LABEL: @test_no_unswitch_convergent( 20entry: 21 br label %loop_begin 22; CHECK-NEXT: entry: 23; CHECK-NEXT: br label %loop_begin 24; 25; We shouldn't have unswitched into any other block either. 26; CHECK-NOT: br i1 %cond 27 28loop_begin: 29 br i1 %cond, label %loop_a, label %loop_b 30; CHECK: loop_begin: 31; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b 32 33loop_a: 34 call i32 @a() convergent 35 br label %loop_latch 36 37loop_b: 38 call i32 @b() 39 br label %loop_latch 40 41loop_latch: 42 %v = load i1, i1* %ptr 43 br i1 %v, label %loop_begin, label %loop_exit 44 45loop_exit: 46 ret void 47} 48 49; Negative test: we cannot unswitch noduplicate calls. 50define void @test_no_unswitch_noduplicate(i1* %ptr, i1 %cond) { 51; CHECK-LABEL: @test_no_unswitch_noduplicate( 52entry: 53 br label %loop_begin 54; CHECK-NEXT: entry: 55; CHECK-NEXT: br label %loop_begin 56; 57; We shouldn't have unswitched into any other block either. 58; CHECK-NOT: br i1 %cond 59 60loop_begin: 61 br i1 %cond, label %loop_a, label %loop_b 62; CHECK: loop_begin: 63; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b 64 65loop_a: 66 call i32 @a() noduplicate 67 br label %loop_latch 68 69loop_b: 70 call i32 @b() 71 br label %loop_latch 72 73loop_latch: 74 %v = load i1, i1* %ptr 75 br i1 %v, label %loop_begin, label %loop_exit 76 77loop_exit: 78 ret void 79} 80 81declare i32 @__CxxFrameHandler3(...) 82 83; Negative test: we cannot unswitch when tokens are used across blocks as we 84; might introduce PHIs. 85define void @test_no_unswitch_cross_block_token(i1* %ptr, i1 %cond) nounwind personality i32 (...)* @__CxxFrameHandler3 { 86; CHECK-LABEL: @test_no_unswitch_cross_block_token( 87entry: 88 br label %loop_begin 89; CHECK-NEXT: entry: 90; CHECK-NEXT: br label %loop_begin 91; 92; We shouldn't have unswitched into any other block either. 93; CHECK-NOT: br i1 %cond 94 95loop_begin: 96 br i1 %cond, label %loop_a, label %loop_b 97; CHECK: loop_begin: 98; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b 99 100loop_a: 101 call i32 @a() 102 br label %loop_cont 103 104loop_b: 105 call i32 @b() 106 br label %loop_cont 107 108loop_cont: 109 invoke i32 @a() 110 to label %loop_latch unwind label %loop_catch 111 112loop_latch: 113 br label %loop_begin 114 115loop_catch: 116 %catch = catchswitch within none [label %loop_catch_latch, label %loop_exit] unwind to caller 117 118loop_catch_latch: 119 %catchpad_latch = catchpad within %catch [] 120 catchret from %catchpad_latch to label %loop_begin 121 122loop_exit: 123 %catchpad_exit = catchpad within %catch [] 124 catchret from %catchpad_exit to label %exit 125 126exit: 127 ret void 128} 129 130 131; Non-trivial loop unswitching where there are two distinct trivial conditions 132; to unswitch within the loop. 133define i32 @test1(i1* %ptr, i1 %cond1, i1 %cond2) { 134; CHECK-LABEL: @test1( 135entry: 136 br label %loop_begin 137; CHECK-NEXT: entry: 138; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 139 140loop_begin: 141 br i1 %cond1, label %loop_a, label %loop_b 142 143loop_a: 144 call i32 @a() 145 br label %latch 146; The 'loop_a' unswitched loop. 147; 148; CHECK: entry.split.us: 149; CHECK-NEXT: br label %loop_begin.us 150; 151; CHECK: loop_begin.us: 152; CHECK-NEXT: br label %loop_a.us 153; 154; CHECK: loop_a.us: 155; CHECK-NEXT: call i32 @a() 156; CHECK-NEXT: br label %latch.us 157; 158; CHECK: latch.us: 159; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 160; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us 161; 162; CHECK: loop_exit.split.us: 163; CHECK-NEXT: br label %loop_exit 164 165loop_b: 166 br i1 %cond2, label %loop_b_a, label %loop_b_b 167; The second unswitched condition. 168; 169; CHECK: entry.split: 170; CHECK-NEXT: br i1 %cond2, label %entry.split.split.us, label %entry.split.split 171 172loop_b_a: 173 call i32 @b() 174 br label %latch 175; The 'loop_b_a' unswitched loop. 176; 177; CHECK: entry.split.split.us: 178; CHECK-NEXT: br label %loop_begin.us1 179; 180; CHECK: loop_begin.us1: 181; CHECK-NEXT: br label %loop_b.us 182; 183; CHECK: loop_b.us: 184; CHECK-NEXT: br label %loop_b_a.us 185; 186; CHECK: loop_b_a.us: 187; CHECK-NEXT: call i32 @b() 188; CHECK-NEXT: br label %latch.us2 189; 190; CHECK: latch.us2: 191; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 192; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us1, label %loop_exit.split.split.us 193; 194; CHECK: loop_exit.split.split.us: 195; CHECK-NEXT: br label %loop_exit.split 196 197loop_b_b: 198 call i32 @c() 199 br label %latch 200; The 'loop_b_b' unswitched loop. 201; 202; CHECK: entry.split.split: 203; CHECK-NEXT: br label %loop_begin 204; 205; CHECK: loop_begin: 206; CHECK-NEXT: br label %loop_b 207; 208; CHECK: loop_b: 209; CHECK-NEXT: br label %loop_b_b 210; 211; CHECK: loop_b_b: 212; CHECK-NEXT: call i32 @c() 213; CHECK-NEXT: br label %latch 214; 215; CHECK: latch: 216; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 217; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split.split 218; 219; CHECK: loop_exit.split.split: 220; CHECK-NEXT: br label %loop_exit.split 221 222latch: 223 %v = load i1, i1* %ptr 224 br i1 %v, label %loop_begin, label %loop_exit 225 226loop_exit: 227 ret i32 0 228; CHECK: loop_exit.split: 229; CHECK-NEXT: br label %loop_exit 230; 231; CHECK: loop_exit: 232; CHECK-NEXT: ret 233} 234 235define i32 @test2(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr, i32* %c.ptr) { 236; CHECK-LABEL: @test2( 237entry: 238 br label %loop_begin 239; CHECK-NEXT: entry: 240; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 241 242loop_begin: 243 %v = load i1, i1* %ptr 244 br i1 %cond1, label %loop_a, label %loop_b 245 246loop_a: 247 %a = load i32, i32* %a.ptr 248 %ac = load i32, i32* %c.ptr 249 br i1 %v, label %loop_begin, label %loop_exit 250; The 'loop_a' unswitched loop. 251; 252; CHECK: entry.split.us: 253; CHECK-NEXT: br label %loop_begin.us 254; 255; CHECK: loop_begin.us: 256; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 257; CHECK-NEXT: br label %loop_a.us 258; 259; CHECK: loop_a.us: 260; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 261; CHECK-NEXT: %[[AC:.*]] = load i32, i32* %c.ptr 262; CHECK-NEXT: br i1 %[[V]], label %loop_begin.backedge.us, label %loop_exit.split.us 263; 264; CHECK: loop_exit.split.us: 265; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a.us ] 266; CHECK-NEXT: %[[AC_LCSSA:.*]] = phi i32 [ %[[AC]], %loop_a.us ] 267; CHECK-NEXT: br label %loop_exit 268 269loop_b: 270 %b = load i32, i32* %b.ptr 271 %bc = load i32, i32* %c.ptr 272 br i1 %v, label %loop_begin, label %loop_exit 273; The 'loop_b' unswitched loop. 274; 275; CHECK: entry.split: 276; CHECK-NEXT: br label %loop_begin 277; 278; CHECK: loop_begin: 279; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 280; CHECK-NEXT: br label %loop_b 281; 282; CHECK: loop_b: 283; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 284; CHECK-NEXT: %[[BC:.*]] = load i32, i32* %c.ptr 285; CHECK-NEXT: br i1 %[[V]], label %loop_begin.backedge, label %loop_exit.split 286; 287; CHECK: loop_exit.split: 288; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ] 289; CHECK-NEXT: %[[BC_LCSSA:.*]] = phi i32 [ %[[BC]], %loop_b ] 290; CHECK-NEXT: br label %loop_exit 291 292loop_exit: 293 %ab.phi = phi i32 [ %a, %loop_a ], [ %b, %loop_b ] 294 %c.phi = phi i32 [ %ac, %loop_a ], [ %bc, %loop_b ] 295 %result = add i32 %ab.phi, %c.phi 296 ret i32 %result 297; CHECK: loop_exit: 298; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ] 299; CHECK-NEXT: %[[C_PHI:.*]] = phi i32 [ %[[BC_LCSSA]], %loop_exit.split ], [ %[[AC_LCSSA]], %loop_exit.split.us ] 300; CHECK-NEXT: %[[RESULT:.*]] = add i32 %[[AB_PHI]], %[[C_PHI]] 301; CHECK-NEXT: ret i32 %[[RESULT]] 302} 303 304; Test a non-trivial unswitch of an exiting edge to an exit block with other 305; in-loop predecessors. 306define i32 @test3a(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { 307; CHECK-LABEL: @test3a( 308entry: 309 br label %loop_begin 310; CHECK-NEXT: entry: 311; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 312 313loop_begin: 314 %v = load i1, i1* %ptr 315 %a = load i32, i32* %a.ptr 316 br i1 %cond1, label %loop_exit, label %loop_b 317; The 'loop_exit' clone. 318; 319; CHECK: entry.split.us: 320; CHECK-NEXT: br label %loop_begin.us 321; 322; CHECK: loop_begin.us: 323; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 324; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 325; CHECK-NEXT: br label %loop_exit.split.us 326; 327; CHECK: loop_exit.split.us: 328; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ] 329; CHECK-NEXT: br label %loop_exit 330 331loop_b: 332 %b = load i32, i32* %b.ptr 333 br i1 %v, label %loop_begin, label %loop_exit 334; The 'loop_b' unswitched loop. 335; 336; CHECK: entry.split: 337; CHECK-NEXT: br label %loop_begin 338; 339; CHECK: loop_begin: 340; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 341; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 342; CHECK-NEXT: br label %loop_b 343; 344; CHECK: loop_b: 345; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 346; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split 347; 348; CHECK: loop_exit.split: 349; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ] 350; CHECK-NEXT: br label %loop_exit 351 352loop_exit: 353 %ab.phi = phi i32 [ %a, %loop_begin ], [ %b, %loop_b ] 354 ret i32 %ab.phi 355; CHECK: loop_exit: 356; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ] 357; CHECK-NEXT: ret i32 %[[AB_PHI]] 358} 359 360; Test a non-trivial unswitch of an exiting edge to an exit block with other 361; in-loop predecessors. This is the same as @test3a but with the reversed order 362; of successors so that the exiting edge is *not* the cloned edge. 363define i32 @test3b(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { 364; CHECK-LABEL: @test3b( 365entry: 366 br label %loop_begin 367; CHECK-NEXT: entry: 368; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 369 370loop_begin: 371 %v = load i1, i1* %ptr 372 %a = load i32, i32* %a.ptr 373 br i1 %cond1, label %loop_b, label %loop_exit 374; The 'loop_b' unswitched loop. 375; 376; CHECK: entry.split.us: 377; CHECK-NEXT: br label %loop_begin.us 378; 379; CHECK: loop_begin.us: 380; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 381; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 382; CHECK-NEXT: br label %loop_b.us 383; 384; CHECK: loop_b.us: 385; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 386; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us 387; 388; CHECK: loop_exit.split.us: 389; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b.us ] 390; CHECK-NEXT: br label %loop_exit 391 392loop_b: 393 %b = load i32, i32* %b.ptr 394 br i1 %v, label %loop_begin, label %loop_exit 395; The original loop, now non-looping due to unswitching.. 396; 397; CHECK: entry.split: 398; CHECK-NEXT: br label %loop_begin 399; 400; CHECK: loop_begin: 401; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 402; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 403; CHECK-NEXT: br label %loop_exit.split 404; 405; CHECK: loop_exit.split: 406; CHECK-NEXT: br label %loop_exit 407 408loop_exit: 409 %ab.phi = phi i32 [ %b, %loop_b ], [ %a, %loop_begin ] 410 ret i32 %ab.phi 411; CHECK: loop_exit: 412; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[A]], %loop_exit.split ], [ %[[B_LCSSA]], %loop_exit.split.us ] 413; CHECK-NEXT: ret i32 %[[AB_PHI]] 414} 415 416; Test a non-trivial unswitch of an exiting edge to an exit block with no other 417; in-loop predecessors. 418define void @test4a(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { 419; CHECK-LABEL: @test4a( 420entry: 421 br label %loop_begin 422; CHECK-NEXT: entry: 423; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 424 425loop_begin: 426 %v = load i1, i1* %ptr 427 %a = load i32, i32* %a.ptr 428 br i1 %cond1, label %loop_exit1, label %loop_b 429; The 'loop_exit' clone. 430; 431; CHECK: entry.split.us: 432; CHECK-NEXT: br label %loop_begin.us 433; 434; CHECK: loop_begin.us: 435; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 436; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 437; CHECK-NEXT: br label %loop_exit1.split.us 438; 439; CHECK: loop_exit1.split.us: 440; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ] 441; CHECK-NEXT: br label %loop_exit1 442 443loop_b: 444 %b = load i32, i32* %b.ptr 445 br i1 %v, label %loop_begin, label %loop_exit2 446; The 'loop_b' unswitched loop. 447; 448; CHECK: entry.split: 449; CHECK-NEXT: br label %loop_begin 450; 451; CHECK: loop_begin: 452; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 453; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 454; CHECK-NEXT: br label %loop_b 455; 456; CHECK: loop_b: 457; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 458; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit2 459 460loop_exit1: 461 %a.phi = phi i32 [ %a, %loop_begin ] 462 call void @sink1(i32 %a.phi) 463 ret void 464; CHECK: loop_exit1: 465; CHECK-NEXT: call void @sink1(i32 %[[A_LCSSA]]) 466; CHECK-NEXT: ret void 467 468loop_exit2: 469 %b.phi = phi i32 [ %b, %loop_b ] 470 call void @sink2(i32 %b.phi) 471 ret void 472; CHECK: loop_exit2: 473; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ] 474; CHECK-NEXT: call void @sink2(i32 %[[B_LCSSA]]) 475; CHECK-NEXT: ret void 476} 477 478; Test a non-trivial unswitch of an exiting edge to an exit block with no other 479; in-loop predecessors. This is the same as @test4a but with the edges reversed 480; so that the exiting edge is *not* the cloned edge. 481define void @test4b(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { 482; CHECK-LABEL: @test4b( 483entry: 484 br label %loop_begin 485; CHECK-NEXT: entry: 486; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 487 488loop_begin: 489 %v = load i1, i1* %ptr 490 %a = load i32, i32* %a.ptr 491 br i1 %cond1, label %loop_b, label %loop_exit1 492; The 'loop_b' clone. 493; 494; CHECK: entry.split.us: 495; CHECK-NEXT: br label %loop_begin.us 496; 497; CHECK: loop_begin.us: 498; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 499; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 500; CHECK-NEXT: br label %loop_b.us 501; 502; CHECK: loop_b.us: 503; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 504; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit2.split.us 505; 506; CHECK: loop_exit2.split.us: 507; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b.us ] 508; CHECK-NEXT: br label %loop_exit2 509 510loop_b: 511 %b = load i32, i32* %b.ptr 512 br i1 %v, label %loop_begin, label %loop_exit2 513; The 'loop_exit' unswitched path. 514; 515; CHECK: entry.split: 516; CHECK-NEXT: br label %loop_begin 517; 518; CHECK: loop_begin: 519; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 520; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 521; CHECK-NEXT: br label %loop_exit1 522 523loop_exit1: 524 %a.phi = phi i32 [ %a, %loop_begin ] 525 call void @sink1(i32 %a.phi) 526 ret void 527; CHECK: loop_exit1: 528; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ] 529; CHECK-NEXT: call void @sink1(i32 %[[A_PHI]]) 530; CHECK-NEXT: ret void 531 532loop_exit2: 533 %b.phi = phi i32 [ %b, %loop_b ] 534 call void @sink2(i32 %b.phi) 535 ret void 536; CHECK: loop_exit2: 537; CHECK-NEXT: call void @sink2(i32 %[[B_LCSSA]]) 538; CHECK-NEXT: ret void 539} 540 541; Test a non-trivial unswitch of an exiting edge to an exit block with no other 542; in-loop predecessors. This is the same as @test4a but with a common merge 543; block after the independent loop exits. This requires a different structural 544; update to the dominator tree. 545define void @test4c(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { 546; CHECK-LABEL: @test4c( 547entry: 548 br label %loop_begin 549; CHECK-NEXT: entry: 550; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 551 552loop_begin: 553 %v = load i1, i1* %ptr 554 %a = load i32, i32* %a.ptr 555 br i1 %cond1, label %loop_exit1, label %loop_b 556; The 'loop_exit' clone. 557; 558; CHECK: entry.split.us: 559; CHECK-NEXT: br label %loop_begin.us 560; 561; CHECK: loop_begin.us: 562; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 563; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 564; CHECK-NEXT: br label %loop_exit1.split.us 565; 566; CHECK: loop_exit1.split.us: 567; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ] 568; CHECK-NEXT: br label %loop_exit1 569 570loop_b: 571 %b = load i32, i32* %b.ptr 572 br i1 %v, label %loop_begin, label %loop_exit2 573; The 'loop_b' unswitched loop. 574; 575; CHECK: entry.split: 576; CHECK-NEXT: br label %loop_begin 577; 578; CHECK: loop_begin: 579; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 580; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 581; CHECK-NEXT: br label %loop_b 582; 583; CHECK: loop_b: 584; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 585; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit2 586 587loop_exit1: 588 %a.phi = phi i32 [ %a, %loop_begin ] 589 call void @sink1(i32 %a.phi) 590 br label %exit 591; CHECK: loop_exit1: 592; CHECK-NEXT: call void @sink1(i32 %[[A_LCSSA]]) 593; CHECK-NEXT: br label %exit 594 595loop_exit2: 596 %b.phi = phi i32 [ %b, %loop_b ] 597 call void @sink2(i32 %b.phi) 598 br label %exit 599; CHECK: loop_exit2: 600; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ] 601; CHECK-NEXT: call void @sink2(i32 %[[B_LCSSA]]) 602; CHECK-NEXT: br label %exit 603 604exit: 605 ret void 606; CHECK: exit: 607; CHECK-NEXT: ret void 608} 609 610; Test that we can unswitch a condition out of multiple layers of a loop nest. 611define i32 @test5(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { 612; CHECK-LABEL: @test5( 613entry: 614 br label %loop_begin 615; CHECK-NEXT: entry: 616; CHECK-NEXT: br i1 %cond1, label %loop_begin.split.us, label %entry.split 617; 618; CHECK: entry.split: 619; CHECK-NEXT: br label %loop_begin 620; 621; CHECK: loop_begin: 622; CHECK-NEXT: br label %loop_begin.split 623 624loop_begin: 625 br label %inner_loop_begin 626 627inner_loop_begin: 628 %v = load i1, i1* %ptr 629 %a = load i32, i32* %a.ptr 630 br i1 %cond1, label %loop_exit, label %inner_loop_b 631; The 'loop_exit' clone. 632; 633; CHECK: loop_begin.split.us: 634; CHECK-NEXT: br label %inner_loop_begin.us 635; 636; CHECK: inner_loop_begin.us: 637; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 638; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 639; CHECK-NEXT: br label %loop_exit.loopexit.split.us 640; 641; CHECK: loop_exit.loopexit.split.us: 642; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ] 643; CHECK-NEXT: br label %loop_exit 644 645inner_loop_b: 646 %b = load i32, i32* %b.ptr 647 br i1 %v, label %inner_loop_begin, label %loop_latch 648; The 'inner_loop_b' unswitched loop. 649; 650; CHECK: loop_begin.split: 651; CHECK-NEXT: br label %inner_loop_begin 652; 653; CHECK: inner_loop_begin: 654; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 655; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 656; CHECK-NEXT: br label %inner_loop_b 657; 658; CHECK: inner_loop_b: 659; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 660; CHECK-NEXT: br i1 %[[V]], label %inner_loop_begin, label %loop_latch 661 662loop_latch: 663 %b.phi = phi i32 [ %b, %inner_loop_b ] 664 %v2 = load i1, i1* %ptr 665 br i1 %v2, label %loop_begin, label %loop_exit 666; CHECK: loop_latch: 667; CHECK-NEXT: %[[B_INNER_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_b ] 668; CHECK-NEXT: %[[V2:.*]] = load i1, i1* %ptr 669; CHECK-NEXT: br i1 %[[V2]], label %loop_begin, label %loop_exit.loopexit1 670 671loop_exit: 672 %ab.phi = phi i32 [ %a, %inner_loop_begin ], [ %b.phi, %loop_latch ] 673 ret i32 %ab.phi 674; CHECK: loop_exit.loopexit: 675; CHECK-NEXT: br label %loop_exit 676; 677; CHECK: loop_exit.loopexit1: 678; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B_INNER_LCSSA]], %loop_latch ] 679; CHECK-NEXT: br label %loop_exit 680; 681; CHECK: loop_exit: 682; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.loopexit ], [ %[[B_LCSSA]], %loop_exit.loopexit1 ] 683; CHECK-NEXT: ret i32 %[[AB_PHI]] 684} 685 686; Test that we can unswitch a condition where we end up only cloning some of 687; the nested loops and needing to delete some of the nested loops. 688define i32 @test6(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { 689; CHECK-LABEL: @test6( 690entry: 691 br label %loop_begin 692; CHECK-NEXT: entry: 693; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 694 695loop_begin: 696 %v = load i1, i1* %ptr 697 br i1 %cond1, label %loop_a, label %loop_b 698 699loop_a: 700 br label %loop_a_inner 701 702loop_a_inner: 703 %va = load i1, i1* %ptr 704 %a = load i32, i32* %a.ptr 705 br i1 %va, label %loop_a_inner, label %loop_a_inner_exit 706 707loop_a_inner_exit: 708 %a.lcssa = phi i32 [ %a, %loop_a_inner ] 709 br label %latch 710; The 'loop_a' cloned loop. 711; 712; CHECK: entry.split.us: 713; CHECK-NEXT: br label %loop_begin.us 714; 715; CHECK: loop_begin.us: 716; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 717; CHECK-NEXT: br label %loop_a.us 718; 719; CHECK: loop_a.us: 720; CHECK-NEXT: br label %loop_a_inner.us 721; 722; CHECK: loop_a_inner.us 723; CHECK-NEXT: %[[VA:.*]] = load i1, i1* %ptr 724; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 725; CHECK-NEXT: br i1 %[[VA]], label %loop_a_inner.us, label %loop_a_inner_exit.us 726; 727; CHECK: loop_a_inner_exit.us: 728; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a_inner.us ] 729; CHECK-NEXT: br label %latch.us 730; 731; CHECK: latch.us: 732; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %loop_a_inner_exit.us ] 733; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us 734; 735; CHECK: loop_exit.split.us: 736; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_PHI]], %latch.us ] 737; CHECK-NEXT: br label %loop_exit 738 739loop_b: 740 br label %loop_b_inner 741 742loop_b_inner: 743 %vb = load i1, i1* %ptr 744 %b = load i32, i32* %b.ptr 745 br i1 %vb, label %loop_b_inner, label %loop_b_inner_exit 746 747loop_b_inner_exit: 748 %b.lcssa = phi i32 [ %b, %loop_b_inner ] 749 br label %latch 750 751latch: 752 %ab.phi = phi i32 [ %a.lcssa, %loop_a_inner_exit ], [ %b.lcssa, %loop_b_inner_exit ] 753 br i1 %v, label %loop_begin, label %loop_exit 754; The 'loop_b' unswitched loop. 755; 756; CHECK: entry.split: 757; CHECK-NEXT: br label %loop_begin 758; 759; CHECK: loop_begin: 760; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 761; CHECK-NEXT: br label %loop_b 762; 763; CHECK: loop_b: 764; CHECK-NEXT: br label %loop_b_inner 765; 766; CHECK: loop_b_inner 767; CHECK-NEXT: %[[VB:.*]] = load i1, i1* %ptr 768; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 769; CHECK-NEXT: br i1 %[[VB]], label %loop_b_inner, label %loop_b_inner_exit 770; 771; CHECK: loop_b_inner_exit: 772; CHECK-NEXT: %[[B_INNER_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b_inner ] 773; CHECK-NEXT: br label %latch 774; 775; CHECK: latch: 776; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split 777; 778; CHECK: loop_exit.split: 779; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B_INNER_LCSSA]], %latch ] 780; CHECK-NEXT: br label %loop_exit 781 782loop_exit: 783 %ab.lcssa = phi i32 [ %ab.phi, %latch ] 784 ret i32 %ab.lcssa 785; CHECK: loop_exit: 786; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ] 787; CHECK-NEXT: ret i32 %[[AB_PHI]] 788} 789 790; Test that when unswitching a deeply nested loop condition in a way that 791; produces a non-loop clone that can reach multiple exit blocks which are part 792; of different outer loops we correctly divide the cloned loop blocks between 793; the outer loops based on reachability. 794define i32 @test7a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 795; CHECK-LABEL: @test7a( 796entry: 797 br label %loop_begin 798; CHECK-NEXT: entry: 799; CHECK-NEXT: br label %loop_begin 800 801loop_begin: 802 %a = load i32, i32* %a.ptr 803 br label %inner_loop_begin 804; CHECK: loop_begin: 805; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 806; CHECK-NEXT: br label %inner_loop_begin 807 808inner_loop_begin: 809 %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ] 810 %cond = load i1, i1* %cond.ptr 811 %b = load i32, i32* %b.ptr 812 br label %inner_inner_loop_begin 813; CHECK: inner_loop_begin: 814; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ] 815; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 816; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 817; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split 818 819inner_inner_loop_begin: 820 %v1 = load i1, i1* %ptr 821 br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b 822 823inner_inner_loop_a: 824 %v2 = load i1, i1* %ptr 825 br i1 %v2, label %loop_exit, label %inner_inner_loop_c 826 827inner_inner_loop_b: 828 %v3 = load i1, i1* %ptr 829 br i1 %v3, label %inner_inner_loop_exit, label %inner_inner_loop_c 830 831inner_inner_loop_c: 832 %v4 = load i1, i1* %ptr 833 br i1 %v4, label %inner_loop_exit, label %inner_inner_loop_d 834 835inner_inner_loop_d: 836 br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_begin 837; The cloned copy that always exits with the adjustments required to fix up 838; loop exits. 839; 840; CHECK: inner_loop_begin.split.us: 841; CHECK-NEXT: br label %inner_inner_loop_begin.us 842; 843; CHECK: inner_inner_loop_begin.us: 844; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 845; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us 846; 847; CHECK: inner_inner_loop_b.us: 848; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 849; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_c.us.loopexit 850; 851; CHECK: inner_inner_loop_a.us: 852; CHECK-NEXT: %[[A_NEW_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_begin.us ] 853; CHECK-NEXT: %[[B_NEW_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_begin.us ] 854; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 855; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us, label %inner_inner_loop_c.us 856; 857; CHECK: inner_inner_loop_c.us.loopexit: 858; CHECK-NEXT: br label %inner_inner_loop_c.us 859; 860; CHECK: inner_inner_loop_c.us: 861; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 862; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit.split.us, label %inner_inner_loop_d.us 863; 864; CHECK: inner_inner_loop_d.us: 865; CHECK-NEXT: br label %inner_loop_exit.loopexit.split 866; 867; CHECK: inner_inner_loop_exit.split.us: 868; CHECK-NEXT: br label %inner_inner_loop_exit 869; 870; CHECK: loop_exit.split.us: 871; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_NEW_LCSSA]], %inner_inner_loop_a.us ] 872; CHECK-NEXT: %[[B_LCSSA_US:.*]] = phi i32 [ %[[B_NEW_LCSSA]], %inner_inner_loop_a.us ] 873; CHECK-NEXT: br label %loop_exit 874; 875; CHECK: inner_loop_exit.loopexit.split.us: 876; CHECK-NEXT: br label %inner_loop_exit.loopexit 877; 878; The original copy that continues to loop. 879; 880; CHECK: inner_loop_begin.split: 881; CHECK-NEXT: br label %inner_inner_loop_begin 882; 883; CHECK: inner_inner_loop_begin: 884; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 885; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b 886; 887; CHECK: inner_inner_loop_a: 888; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 889; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split, label %inner_inner_loop_c 890; 891; CHECK: inner_inner_loop_b: 892; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 893; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split, label %inner_inner_loop_c 894; 895; CHECK: inner_inner_loop_c: 896; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 897; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit.split, label %inner_inner_loop_d 898; 899; CHECK: inner_inner_loop_d: 900; CHECK-NEXT: br label %inner_inner_loop_begin 901; 902; CHECK: inner_inner_loop_exit.split: 903; CHECK-NEXT: br label %inner_inner_loop_exit 904 905inner_inner_loop_exit: 906 %a2 = load i32, i32* %a.ptr 907 %v5 = load i1, i1* %ptr 908 br i1 %v5, label %inner_loop_exit, label %inner_loop_begin 909; CHECK: inner_inner_loop_exit: 910; CHECK-NEXT: %[[A2]] = load i32, i32* %a.ptr 911; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 912; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin 913 914inner_loop_exit: 915 br label %loop_begin 916; CHECK: inner_loop_exit.loopexit.split: 917; CHECK-NEXT: br label %inner_loop_exit.loopexit 918; 919; CHECK: inner_loop_exit.loopexit: 920; CHECK-NEXT: br label %inner_loop_exit 921; 922; CHECK: inner_loop_exit.loopexit1: 923; CHECK-NEXT: br label %inner_loop_exit 924; 925; CHECK: inner_loop_exit: 926; CHECK-NEXT: br label %loop_begin 927 928loop_exit: 929 %a.lcssa = phi i32 [ %a.phi, %inner_inner_loop_a ] 930 %b.lcssa = phi i32 [ %b, %inner_inner_loop_a ] 931 %result = add i32 %a.lcssa, %b.lcssa 932 ret i32 %result 933; CHECK: loop_exit.split: 934; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a ] 935; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_a ] 936; CHECK-NEXT: br label %loop_exit 937; 938; CHECK: loop_exit: 939; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ] 940; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA_US]], %loop_exit.split.us ] 941; CHECK-NEXT: %[[RESULT:.*]] = add i32 %[[A_PHI]], %[[B_PHI]] 942; CHECK-NEXT: ret i32 %[[RESULT]] 943} 944 945; Same pattern as @test7a but here the original loop becomes a non-loop that 946; can reach multiple exit blocks which are part of different outer loops. 947define i32 @test7b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 948; CHECK-LABEL: @test7b( 949entry: 950 br label %loop_begin 951; CHECK-NEXT: entry: 952; CHECK-NEXT: br label %loop_begin 953 954loop_begin: 955 %a = load i32, i32* %a.ptr 956 br label %inner_loop_begin 957; CHECK: loop_begin: 958; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 959; CHECK-NEXT: br label %inner_loop_begin 960 961inner_loop_begin: 962 %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ] 963 %cond = load i1, i1* %cond.ptr 964 %b = load i32, i32* %b.ptr 965 br label %inner_inner_loop_begin 966; CHECK: inner_loop_begin: 967; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ] 968; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 969; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 970; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split 971 972inner_inner_loop_begin: 973 %v1 = load i1, i1* %ptr 974 br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b 975 976inner_inner_loop_a: 977 %v2 = load i1, i1* %ptr 978 br i1 %v2, label %loop_exit, label %inner_inner_loop_c 979 980inner_inner_loop_b: 981 %v3 = load i1, i1* %ptr 982 br i1 %v3, label %inner_inner_loop_exit, label %inner_inner_loop_c 983 984inner_inner_loop_c: 985 %v4 = load i1, i1* %ptr 986 br i1 %v4, label %inner_loop_exit, label %inner_inner_loop_d 987 988inner_inner_loop_d: 989 br i1 %cond, label %inner_inner_loop_begin, label %inner_loop_exit 990; The cloned copy that continues looping. 991; 992; CHECK: inner_loop_begin.split.us: 993; CHECK-NEXT: br label %inner_inner_loop_begin.us 994; 995; CHECK: inner_inner_loop_begin.us: 996; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 997; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us 998; 999; CHECK: inner_inner_loop_b.us: 1000; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1001; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_c.us 1002; 1003; CHECK: inner_inner_loop_a.us: 1004; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1005; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us, label %inner_inner_loop_c.us 1006; 1007; CHECK: inner_inner_loop_c.us: 1008; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1009; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit.split.us, label %inner_inner_loop_d.us 1010; 1011; CHECK: inner_inner_loop_d.us: 1012; CHECK-NEXT: br label %inner_inner_loop_begin.us 1013; 1014; CHECK: inner_inner_loop_exit.split.us: 1015; CHECK-NEXT: br label %inner_inner_loop_exit 1016; 1017; CHECK: loop_exit.split.us: 1018; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a.us ] 1019; CHECK-NEXT: %[[B_LCSSA_US:.*]] = phi i32 [ %[[B]], %inner_inner_loop_a.us ] 1020; CHECK-NEXT: br label %loop_exit 1021; 1022; CHECK: inner_loop_exit.loopexit.split.us: 1023; CHECK-NEXT: br label %inner_loop_exit.loopexit 1024; 1025; The original copy that now always exits and needs adjustments for exit 1026; blocks. 1027; 1028; CHECK: inner_loop_begin.split: 1029; CHECK-NEXT: br label %inner_inner_loop_begin 1030; 1031; CHECK: inner_inner_loop_begin: 1032; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1033; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b 1034; 1035; CHECK: inner_inner_loop_a: 1036; CHECK-NEXT: %[[A_NEW_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_begin ] 1037; CHECK-NEXT: %[[B_NEW_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_begin ] 1038; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1039; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split, label %inner_inner_loop_c 1040; 1041; CHECK: inner_inner_loop_b: 1042; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1043; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split, label %inner_inner_loop_c.loopexit 1044; 1045; CHECK: inner_inner_loop_c.loopexit: 1046; CHECK-NEXT: br label %inner_inner_loop_c 1047; 1048; CHECK: inner_inner_loop_c: 1049; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1050; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit.split, label %inner_inner_loop_d 1051; 1052; CHECK: inner_inner_loop_d: 1053; CHECK-NEXT: br label %inner_loop_exit.loopexit.split 1054; 1055; CHECK: inner_inner_loop_exit.split: 1056; CHECK-NEXT: br label %inner_inner_loop_exit 1057 1058inner_inner_loop_exit: 1059 %a2 = load i32, i32* %a.ptr 1060 %v5 = load i1, i1* %ptr 1061 br i1 %v5, label %inner_loop_exit, label %inner_loop_begin 1062; CHECK: inner_inner_loop_exit: 1063; CHECK-NEXT: %[[A2]] = load i32, i32* %a.ptr 1064; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1065; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin 1066 1067inner_loop_exit: 1068 br label %loop_begin 1069; CHECK: inner_loop_exit.loopexit.split: 1070; CHECK-NEXT: br label %inner_loop_exit.loopexit 1071; 1072; CHECK: inner_loop_exit.loopexit: 1073; CHECK-NEXT: br label %inner_loop_exit 1074; 1075; CHECK: inner_loop_exit.loopexit1: 1076; CHECK-NEXT: br label %inner_loop_exit 1077; 1078; CHECK: inner_loop_exit: 1079; CHECK-NEXT: br label %loop_begin 1080 1081loop_exit: 1082 %a.lcssa = phi i32 [ %a.phi, %inner_inner_loop_a ] 1083 %b.lcssa = phi i32 [ %b, %inner_inner_loop_a ] 1084 %result = add i32 %a.lcssa, %b.lcssa 1085 ret i32 %result 1086; CHECK: loop_exit.split: 1087; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_NEW_LCSSA]], %inner_inner_loop_a ] 1088; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B_NEW_LCSSA]], %inner_inner_loop_a ] 1089; CHECK-NEXT: br label %loop_exit 1090; 1091; CHECK: loop_exit: 1092; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ] 1093; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA_US]], %loop_exit.split.us ] 1094; CHECK-NEXT: %[[RESULT:.*]] = add i32 %[[A_PHI]], %[[B_PHI]] 1095; CHECK-NEXT: ret i32 %[[RESULT]] 1096} 1097 1098; Test that when the exit block set of an inner loop changes to start at a less 1099; high level of the loop nest we correctly hoist the loop up the nest. 1100define i32 @test8a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 1101; CHECK-LABEL: @test8a( 1102entry: 1103 br label %loop_begin 1104; CHECK-NEXT: entry: 1105; CHECK-NEXT: br label %loop_begin 1106 1107loop_begin: 1108 %a = load i32, i32* %a.ptr 1109 br label %inner_loop_begin 1110; CHECK: loop_begin: 1111; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1112; CHECK-NEXT: br label %inner_loop_begin 1113 1114inner_loop_begin: 1115 %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ] 1116 %cond = load i1, i1* %cond.ptr 1117 %b = load i32, i32* %b.ptr 1118 br label %inner_inner_loop_begin 1119; CHECK: inner_loop_begin: 1120; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ] 1121; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 1122; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 1123; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split 1124 1125inner_inner_loop_begin: 1126 %v1 = load i1, i1* %ptr 1127 br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b 1128 1129inner_inner_loop_a: 1130 %v2 = load i1, i1* %ptr 1131 br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit 1132 1133inner_inner_loop_b: 1134 br i1 %cond, label %inner_inner_loop_latch, label %inner_inner_loop_exit 1135 1136inner_inner_loop_latch: 1137 br label %inner_inner_loop_begin 1138; The cloned region is now an exit from the inner loop. 1139; 1140; CHECK: inner_loop_begin.split.us: 1141; CHECK-NEXT: %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_begin ] 1142; CHECK-NEXT: br label %inner_inner_loop_begin.us 1143; 1144; CHECK: inner_inner_loop_begin.us: 1145; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1146; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us 1147; 1148; CHECK: inner_inner_loop_b.us: 1149; CHECK-NEXT: br label %inner_inner_loop_latch.us 1150; 1151; CHECK: inner_inner_loop_a.us: 1152; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1153; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_latch.us, label %inner_loop_exit.loopexit.split.us 1154; 1155; CHECK: inner_inner_loop_latch.us: 1156; CHECK-NEXT: br label %inner_inner_loop_begin.us 1157; 1158; CHECK: inner_loop_exit.loopexit.split.us: 1159; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_a.us ] 1160; CHECK-NEXT: br label %inner_loop_exit.loopexit 1161; 1162; The original region exits the loop earlier. 1163; 1164; CHECK: inner_loop_begin.split: 1165; CHECK-NEXT: br label %inner_inner_loop_begin 1166; 1167; CHECK: inner_inner_loop_begin: 1168; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1169; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b 1170; 1171; CHECK: inner_inner_loop_a: 1172; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1173; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_latch, label %inner_loop_exit.loopexit.split 1174; 1175; CHECK: inner_inner_loop_b: 1176; CHECK-NEXT: br label %inner_inner_loop_exit 1177; 1178; CHECK: inner_inner_loop_latch: 1179; CHECK-NEXT: br label %inner_inner_loop_begin 1180 1181inner_inner_loop_exit: 1182 %a2 = load i32, i32* %a.ptr 1183 %v4 = load i1, i1* %ptr 1184 br i1 %v4, label %inner_loop_exit, label %inner_loop_begin 1185; CHECK: inner_inner_loop_exit: 1186; CHECK-NEXT: %[[A2]] = load i32, i32* %a.ptr 1187; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1188; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin 1189 1190inner_loop_exit: 1191 %v5 = load i1, i1* %ptr 1192 br i1 %v5, label %loop_exit, label %loop_begin 1193; CHECK: inner_loop_exit.loopexit.split: 1194; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a ] 1195; CHECK-NEXT: br label %inner_loop_exit.loopexit 1196; 1197; CHECK: inner_loop_exit.loopexit: 1198; CHECK-NEXT: %[[A_INNER_US_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit.split ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ] 1199; CHECK-NEXT: br label %inner_loop_exit 1200; 1201; CHECK: inner_loop_exit.loopexit1: 1202; CHECK-NEXT: %[[A_INNER_LCSSA2:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_exit ] 1203; CHECK-NEXT: br label %inner_loop_exit 1204; 1205; CHECK: inner_loop_exit: 1206; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA2]], %inner_loop_exit.loopexit1 ], [ %[[A_INNER_US_PHI]], %inner_loop_exit.loopexit ] 1207; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1208; CHECK-NEXT: br i1 %[[V]], label %loop_exit, label %loop_begin 1209 1210loop_exit: 1211 %a.lcssa = phi i32 [ %a.phi, %inner_loop_exit ] 1212 ret i32 %a.lcssa 1213; CHECK: loop_exit: 1214; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] 1215; CHECK-NEXT: ret i32 %[[A_LCSSA]] 1216} 1217 1218; Same pattern as @test8a but where the original loop looses an exit block and 1219; needs to be hoisted up the nest. 1220define i32 @test8b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 1221; CHECK-LABEL: @test8b( 1222entry: 1223 br label %loop_begin 1224; CHECK-NEXT: entry: 1225; CHECK-NEXT: br label %loop_begin 1226 1227loop_begin: 1228 %a = load i32, i32* %a.ptr 1229 br label %inner_loop_begin 1230; CHECK: loop_begin: 1231; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1232; CHECK-NEXT: br label %inner_loop_begin 1233 1234inner_loop_begin: 1235 %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ] 1236 %cond = load i1, i1* %cond.ptr 1237 %b = load i32, i32* %b.ptr 1238 br label %inner_inner_loop_begin 1239; CHECK: inner_loop_begin: 1240; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ] 1241; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 1242; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 1243; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split 1244 1245inner_inner_loop_begin: 1246 %v1 = load i1, i1* %ptr 1247 br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b 1248 1249inner_inner_loop_a: 1250 %v2 = load i1, i1* %ptr 1251 br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit 1252 1253inner_inner_loop_b: 1254 br i1 %cond, label %inner_inner_loop_exit, label %inner_inner_loop_latch 1255 1256inner_inner_loop_latch: 1257 br label %inner_inner_loop_begin 1258; The cloned region is similar to before but with one earlier exit. 1259; 1260; CHECK: inner_loop_begin.split.us: 1261; CHECK-NEXT: br label %inner_inner_loop_begin.us 1262; 1263; CHECK: inner_inner_loop_begin.us: 1264; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1265; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us 1266; 1267; CHECK: inner_inner_loop_b.us: 1268; CHECK-NEXT: br label %inner_inner_loop_exit.split.us 1269; 1270; CHECK: inner_inner_loop_a.us: 1271; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1272; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_latch.us, label %inner_loop_exit.loopexit.split.us 1273; 1274; CHECK: inner_inner_loop_latch.us: 1275; CHECK-NEXT: br label %inner_inner_loop_begin.us 1276; 1277; CHECK: inner_inner_loop_exit.split.us: 1278; CHECK-NEXT: br label %inner_inner_loop_exit 1279; 1280; CHECK: inner_loop_exit.loopexit.split.us: 1281; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a.us ] 1282; CHECK-NEXT: br label %inner_loop_exit.loopexit 1283; 1284; The original region is now an exit in the preheader. 1285; 1286; CHECK: inner_loop_begin.split: 1287; CHECK-NEXT: %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_begin ] 1288; CHECK-NEXT: br label %inner_inner_loop_begin 1289; 1290; CHECK: inner_inner_loop_begin: 1291; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1292; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b 1293; 1294; CHECK: inner_inner_loop_a: 1295; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1296; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_latch, label %inner_loop_exit.loopexit.split 1297; 1298; CHECK: inner_inner_loop_b: 1299; CHECK-NEXT: br label %inner_inner_loop_latch 1300; 1301; CHECK: inner_inner_loop_latch: 1302; CHECK-NEXT: br label %inner_inner_loop_begin 1303 1304inner_inner_loop_exit: 1305 %a2 = load i32, i32* %a.ptr 1306 %v4 = load i1, i1* %ptr 1307 br i1 %v4, label %inner_loop_exit, label %inner_loop_begin 1308; CHECK: inner_inner_loop_exit: 1309; CHECK-NEXT: %[[A2]] = load i32, i32* %a.ptr 1310; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1311; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin 1312 1313inner_loop_exit: 1314 %v5 = load i1, i1* %ptr 1315 br i1 %v5, label %loop_exit, label %loop_begin 1316; CHECK: inner_loop_exit.loopexit.split: 1317; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_a ] 1318; CHECK-NEXT: br label %inner_loop_exit.loopexit 1319; 1320; CHECK: inner_loop_exit.loopexit: 1321; CHECK-NEXT: %[[A_INNER_US_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit.split ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ] 1322; CHECK-NEXT: br label %inner_loop_exit 1323; 1324; CHECK: inner_loop_exit.loopexit1: 1325; CHECK-NEXT: %[[A_INNER_LCSSA2:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_exit ] 1326; CHECK-NEXT: br label %inner_loop_exit 1327; 1328; CHECK: inner_loop_exit: 1329; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA2]], %inner_loop_exit.loopexit1 ], [ %[[A_INNER_US_PHI]], %inner_loop_exit.loopexit ] 1330; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1331; CHECK-NEXT: br i1 %[[V]], label %loop_exit, label %loop_begin 1332 1333loop_exit: 1334 %a.lcssa = phi i32 [ %a.phi, %inner_loop_exit ] 1335 ret i32 %a.lcssa 1336; CHECK: loop_exit: 1337; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] 1338; CHECK-NEXT: ret i32 %[[A_LCSSA]] 1339} 1340 1341; Test for when unswitching produces a clone of an inner loop but 1342; the clone no longer has an exiting edge *at all* and loops infinitely. 1343; Because it doesn't ever exit to the outer loop it is no longer an inner loop 1344; but needs to be hoisted up the nest to be a top-level loop. 1345define i32 @test9a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 1346; CHECK-LABEL: @test9a( 1347entry: 1348 br label %loop_begin 1349; CHECK-NEXT: entry: 1350; CHECK-NEXT: br label %loop_begin 1351 1352loop_begin: 1353 %b = load i32, i32* %b.ptr 1354 %cond = load i1, i1* %cond.ptr 1355 br label %inner_loop_begin 1356; CHECK: loop_begin: 1357; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 1358; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 1359; CHECK-NEXT: br i1 %[[COND]], label %loop_begin.split.us, label %loop_begin.split 1360 1361inner_loop_begin: 1362 %a = load i32, i32* %a.ptr 1363 br i1 %cond, label %inner_loop_latch, label %inner_loop_exit 1364 1365inner_loop_latch: 1366 call void @sink1(i32 %b) 1367 br label %inner_loop_begin 1368; The cloned inner loop ends up as an infinite loop and thus being a top-level 1369; loop with the preheader as an exit block of the outer loop. 1370; 1371; CHECK: loop_begin.split.us 1372; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_begin ] 1373; CHECK-NEXT: br label %inner_loop_begin.us 1374; 1375; CHECK: inner_loop_begin.us: 1376; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1377; CHECK-NEXT: br label %inner_loop_latch.us 1378; 1379; CHECK: inner_loop_latch.us: 1380; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) 1381; CHECK-NEXT: br label %inner_loop_begin.us 1382; 1383; The original loop becomes boring non-loop code. 1384; 1385; CHECK: loop_begin.split 1386; CHECK-NEXT: br label %inner_loop_begin 1387; 1388; CHECK: inner_loop_begin: 1389; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1390; CHECK-NEXT: br label %inner_loop_exit 1391 1392inner_loop_exit: 1393 %a.inner_lcssa = phi i32 [ %a, %inner_loop_begin ] 1394 %v = load i1, i1* %ptr 1395 br i1 %v, label %loop_begin, label %loop_exit 1396; CHECK: inner_loop_exit: 1397; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin ] 1398; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1399; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit 1400 1401loop_exit: 1402 %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ] 1403 ret i32 %a.lcssa 1404; CHECK: loop_exit: 1405; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ] 1406; CHECK-NEXT: ret i32 %[[A_LCSSA]] 1407} 1408 1409; The same core pattern as @test9a, but instead of the cloned loop becoming an 1410; infinite loop, the original loop has its only exit unswitched and the 1411; original loop becomes infinite and must be hoisted out of the loop nest. 1412define i32 @test9b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 1413; CHECK-LABEL: @test9b( 1414entry: 1415 br label %loop_begin 1416; CHECK-NEXT: entry: 1417; CHECK-NEXT: br label %loop_begin 1418 1419loop_begin: 1420 %b = load i32, i32* %b.ptr 1421 %cond = load i1, i1* %cond.ptr 1422 br label %inner_loop_begin 1423; CHECK: loop_begin: 1424; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 1425; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 1426; CHECK-NEXT: br i1 %[[COND]], label %loop_begin.split.us, label %loop_begin.split 1427 1428inner_loop_begin: 1429 %a = load i32, i32* %a.ptr 1430 br i1 %cond, label %inner_loop_exit, label %inner_loop_latch 1431 1432inner_loop_latch: 1433 call void @sink1(i32 %b) 1434 br label %inner_loop_begin 1435; The cloned inner loop becomes a boring non-loop. 1436; 1437; CHECK: loop_begin.split.us 1438; CHECK-NEXT: br label %inner_loop_begin.us 1439; 1440; CHECK: inner_loop_begin.us: 1441; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1442; CHECK-NEXT: br label %inner_loop_exit.split.us 1443; 1444; CHECK: inner_loop_exit.split.us 1445; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ] 1446; CHECK-NEXT: br label %inner_loop_exit 1447; 1448; The original loop becomes an infinite loop and thus a top-level loop with the 1449; preheader as an exit block for the outer loop. 1450; 1451; CHECK: loop_begin.split 1452; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_begin ] 1453; CHECK-NEXT: br label %inner_loop_begin 1454; 1455; CHECK: inner_loop_begin: 1456; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1457; CHECK-NEXT: br label %inner_loop_latch 1458; 1459; CHECK: inner_loop_latch: 1460; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) 1461; CHECK-NEXT: br label %inner_loop_begin 1462 1463inner_loop_exit: 1464 %a.inner_lcssa = phi i32 [ %a, %inner_loop_begin ] 1465 %v = load i1, i1* %ptr 1466 br i1 %v, label %loop_begin, label %loop_exit 1467; CHECK: inner_loop_exit: 1468; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1469; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit 1470 1471loop_exit: 1472 %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ] 1473 ret i32 %a.lcssa 1474; CHECK: loop_exit: 1475; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit ] 1476; CHECK-NEXT: ret i32 %[[A_LCSSA]] 1477} 1478 1479; Test that requires re-forming dedicated exits for the cloned loop. 1480define i32 @test10a(i1* %ptr, i1 %cond, i32* %a.ptr) { 1481; CHECK-LABEL: @test10a( 1482entry: 1483 br label %loop_begin 1484; CHECK-NEXT: entry: 1485; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 1486 1487loop_begin: 1488 %a = load i32, i32* %a.ptr 1489 %v1 = load i1, i1* %ptr 1490 br i1 %v1, label %loop_a, label %loop_b 1491 1492loop_a: 1493 %v2 = load i1, i1* %ptr 1494 br i1 %v2, label %loop_exit, label %loop_begin 1495 1496loop_b: 1497 br i1 %cond, label %loop_exit, label %loop_begin 1498; The cloned loop with one edge as a direct exit. 1499; 1500; CHECK: entry.split.us: 1501; CHECK-NEXT: br label %loop_begin.us 1502; 1503; CHECK: loop_begin.us: 1504; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1505; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1506; CHECK-NEXT: br i1 %[[V]], label %loop_a.us, label %loop_b.us 1507; 1508; CHECK: loop_b.us: 1509; CHECK-NEXT: %[[A_LCSSA_B:.*]] = phi i32 [ %[[A]], %loop_begin.us ] 1510; CHECK-NEXT: br label %loop_exit.split.us 1511; 1512; CHECK: loop_a.us: 1513; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1514; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us.loopexit, label %loop_begin.backedge.us 1515; 1516; CHECK: loop_begin.backedge.us: 1517; CHECK-NEXT: br label %loop_begin.us 1518; 1519; CHECK: loop_exit.split.us.loopexit: 1520; CHECK-NEXT: %[[A_LCSSA_A:.*]] = phi i32 [ %[[A]], %loop_a.us ] 1521; CHECK-NEXT: br label %loop_exit 1522; 1523; CHECK: loop_exit.split.us: 1524; CHECK-NEXT: %[[A_PHI_US:.*]] = phi i32 [ %[[A_LCSSA_B]], %loop_b.us ], [ %[[A_LCSSA_A]], %loop_exit.split.us.loopexit ] 1525; CHECK-NEXT: br label %loop_exit 1526 1527; The original loop without one 'loop_exit' edge. 1528; 1529; CHECK: entry.split: 1530; CHECK-NEXT: br label %loop_begin 1531; 1532; CHECK: loop_begin: 1533; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1534; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1535; CHECK-NEXT: br i1 %[[V]], label %loop_a, label %loop_b 1536; 1537; CHECK: loop_a: 1538; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1539; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split, label %loop_begin.backedge 1540; 1541; CHECK: loop_begin.backedge: 1542; CHECK-NEXT: br label %loop_begin 1543; 1544; CHECK: loop_b: 1545; CHECK-NEXT: br label %loop_begin.backedge 1546; 1547; CHECK: loop_exit.split: 1548; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ] 1549; CHECK-NEXT: br label %loop_exit 1550 1551loop_exit: 1552 %a.lcssa = phi i32 [ %a, %loop_a ], [ %a, %loop_b ] 1553 ret i32 %a.lcssa 1554; CHECK: loop_exit: 1555; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_PHI_US]], %loop_exit.split.us ] 1556; CHECK-NEXT: ret i32 %[[A_PHI]] 1557} 1558 1559; Test that requires re-forming dedicated exits for the original loop. 1560define i32 @test10b(i1* %ptr, i1 %cond, i32* %a.ptr) { 1561; CHECK-LABEL: @test10b( 1562entry: 1563 br label %loop_begin 1564; CHECK-NEXT: entry: 1565; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 1566 1567loop_begin: 1568 %a = load i32, i32* %a.ptr 1569 %v1 = load i1, i1* %ptr 1570 br i1 %v1, label %loop_a, label %loop_b 1571 1572loop_a: 1573 %v2 = load i1, i1* %ptr 1574 br i1 %v2, label %loop_begin, label %loop_exit 1575 1576loop_b: 1577 br i1 %cond, label %loop_begin, label %loop_exit 1578; The cloned loop without one of the exits. 1579; 1580; CHECK: entry.split.us: 1581; CHECK-NEXT: br label %loop_begin.us 1582; 1583; CHECK: loop_begin.us: 1584; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1585; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1586; CHECK-NEXT: br i1 %[[V]], label %loop_a.us, label %loop_b.us 1587; 1588; CHECK: loop_b.us: 1589; CHECK-NEXT: br label %loop_begin.backedge.us 1590; 1591; CHECK: loop_a.us: 1592; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1593; CHECK-NEXT: br i1 %[[V]], label %loop_begin.backedge.us, label %loop_exit.split.us 1594; 1595; CHECK: loop_begin.backedge.us: 1596; CHECK-NEXT: br label %loop_begin.us 1597; 1598; CHECK: loop_exit.split.us: 1599; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ] 1600; CHECK-NEXT: br label %loop_exit 1601 1602; The original loop without one 'loop_exit' edge. 1603; 1604; CHECK: entry.split: 1605; CHECK-NEXT: br label %loop_begin 1606; 1607; CHECK: loop_begin: 1608; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1609; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1610; CHECK-NEXT: br i1 %[[V]], label %loop_a, label %loop_b 1611; 1612; CHECK: loop_a: 1613; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1614; CHECK-NEXT: br i1 %[[V]], label %loop_begin.backedge, label %loop_exit.split.loopexit 1615; 1616; CHECK: loop_begin.backedge: 1617; CHECK-NEXT: br label %loop_begin 1618; 1619; CHECK: loop_b: 1620; CHECK-NEXT: %[[A_LCSSA_B:.*]] = phi i32 [ %[[A]], %loop_begin ] 1621; CHECK-NEXT: br label %loop_exit.split 1622; 1623; CHECK: loop_exit.split.loopexit: 1624; CHECK-NEXT: %[[A_LCSSA_A:.*]] = phi i32 [ %[[A]], %loop_a ] 1625; CHECK-NEXT: br label %loop_exit.split 1626; 1627; CHECK: loop_exit.split: 1628; CHECK-NEXT: %[[A_PHI_SPLIT:.*]] = phi i32 [ %[[A_LCSSA_B]], %loop_b ], [ %[[A_LCSSA_A]], %loop_exit.split.loopexit ] 1629; CHECK-NEXT: br label %loop_exit 1630 1631loop_exit: 1632 %a.lcssa = phi i32 [ %a, %loop_a ], [ %a, %loop_b ] 1633 ret i32 %a.lcssa 1634; CHECK: loop_exit: 1635; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_PHI_SPLIT]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ] 1636; CHECK-NEXT: ret i32 %[[A_PHI]] 1637} 1638 1639; Check that if a cloned inner loop after unswitching doesn't loop and directly 1640; exits even an outer loop, we don't add the cloned preheader to the outer 1641; loop and do add the needed LCSSA phi nodes for the new exit block from the 1642; outer loop. 1643define i32 @test11a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 1644; CHECK-LABEL: @test11a( 1645entry: 1646 br label %loop_begin 1647; CHECK-NEXT: entry: 1648; CHECK-NEXT: br label %loop_begin 1649 1650loop_begin: 1651 %b = load i32, i32* %b.ptr 1652 %v1 = load i1, i1* %ptr 1653 br i1 %v1, label %loop_latch, label %inner_loop_ph 1654; CHECK: loop_begin: 1655; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 1656; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1657; CHECK-NEXT: br i1 %[[V]], label %loop_latch, label %inner_loop_ph 1658 1659inner_loop_ph: 1660 %cond = load i1, i1* %cond.ptr 1661 br label %inner_loop_begin 1662; CHECK: inner_loop_ph: 1663; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 1664; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_ph.split.us, label %inner_loop_ph.split 1665 1666inner_loop_begin: 1667 call void @sink1(i32 %b) 1668 %a = load i32, i32* %a.ptr 1669 br i1 %cond, label %loop_exit, label %inner_loop_a 1670 1671inner_loop_a: 1672 %v2 = load i1, i1* %ptr 1673 br i1 %v2, label %inner_loop_exit, label %inner_loop_begin 1674; The cloned path doesn't actually loop and is an exit from the outer loop as 1675; well. 1676; 1677; CHECK: inner_loop_ph.split.us: 1678; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_ph ] 1679; CHECK-NEXT: br label %inner_loop_begin.us 1680; 1681; CHECK: inner_loop_begin.us: 1682; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) 1683; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1684; CHECK-NEXT: br label %loop_exit.loopexit.split.us 1685; 1686; CHECK: loop_exit.loopexit.split.us: 1687; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ] 1688; CHECK-NEXT: br label %loop_exit.loopexit 1689; 1690; The original remains a loop losing the exit edge. 1691; 1692; CHECK: inner_loop_ph.split: 1693; CHECK-NEXT: br label %inner_loop_begin 1694; 1695; CHECK: inner_loop_begin: 1696; CHECK-NEXT: call void @sink1(i32 %[[B]]) 1697; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1698; CHECK-NEXT: br label %inner_loop_a 1699; 1700; CHECK: inner_loop_a: 1701; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1702; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit, label %inner_loop_begin 1703 1704inner_loop_exit: 1705 %a.inner_lcssa = phi i32 [ %a, %inner_loop_a ] 1706 %v3 = load i1, i1* %ptr 1707 br i1 %v3, label %loop_latch, label %loop_exit 1708; CHECK: inner_loop_exit: 1709; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_a ] 1710; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1711; CHECK-NEXT: br i1 %[[V]], label %loop_latch, label %loop_exit.loopexit1 1712 1713loop_latch: 1714 br label %loop_begin 1715; CHECK: loop_latch: 1716; CHECK-NEXT: br label %loop_begin 1717 1718loop_exit: 1719 %a.lcssa = phi i32 [ %a, %inner_loop_begin ], [ %a.inner_lcssa, %inner_loop_exit ] 1720 ret i32 %a.lcssa 1721; CHECK: loop_exit.loopexit: 1722; CHECK-NEXT: br label %loop_exit 1723; 1724; CHECK: loop_exit.loopexit1: 1725; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ] 1726; CHECK-NEXT: br label %loop_exit 1727; 1728; CHECK: loop_exit: 1729; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %loop_exit.loopexit ], [ %[[A_LCSSA]], %loop_exit.loopexit1 ] 1730; CHECK-NEXT: ret i32 %[[A_PHI]] 1731} 1732 1733; Check that if the original inner loop after unswitching doesn't loop and 1734; directly exits even an outer loop, we remove the original preheader from the 1735; outer loop and add needed LCSSA phi nodes for the new exit block from the 1736; outer loop. 1737define i32 @test11b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 1738; CHECK-LABEL: @test11b( 1739entry: 1740 br label %loop_begin 1741; CHECK-NEXT: entry: 1742; CHECK-NEXT: br label %loop_begin 1743 1744loop_begin: 1745 %b = load i32, i32* %b.ptr 1746 %v1 = load i1, i1* %ptr 1747 br i1 %v1, label %loop_latch, label %inner_loop_ph 1748; CHECK: loop_begin: 1749; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 1750; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1751; CHECK-NEXT: br i1 %[[V]], label %loop_latch, label %inner_loop_ph 1752 1753inner_loop_ph: 1754 %cond = load i1, i1* %cond.ptr 1755 br label %inner_loop_begin 1756; CHECK: inner_loop_ph: 1757; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 1758; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_ph.split.us, label %inner_loop_ph.split 1759 1760inner_loop_begin: 1761 call void @sink1(i32 %b) 1762 %a = load i32, i32* %a.ptr 1763 br i1 %cond, label %inner_loop_a, label %loop_exit 1764 1765inner_loop_a: 1766 %v2 = load i1, i1* %ptr 1767 br i1 %v2, label %inner_loop_exit, label %inner_loop_begin 1768; The cloned path continues to loop without the exit out of the entire nest. 1769; 1770; CHECK: inner_loop_ph.split.us: 1771; CHECK-NEXT: br label %inner_loop_begin.us 1772; 1773; CHECK: inner_loop_begin.us: 1774; CHECK-NEXT: call void @sink1(i32 %[[B]]) 1775; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1776; CHECK-NEXT: br label %inner_loop_a.us 1777; 1778; CHECK: inner_loop_a.us: 1779; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1780; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.split.us, label %inner_loop_begin.us 1781; 1782; CHECK: inner_loop_exit.split.us: 1783; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_a.us ] 1784; CHECK-NEXT: br label %inner_loop_exit 1785; 1786; The original remains a loop losing the exit edge. 1787; 1788; CHECK: inner_loop_ph.split: 1789; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_ph ] 1790; CHECK-NEXT: br label %inner_loop_begin 1791; 1792; CHECK: inner_loop_begin: 1793; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) 1794; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1795; CHECK-NEXT: br label %loop_exit.loopexit 1796 1797inner_loop_exit: 1798 %a.inner_lcssa = phi i32 [ %a, %inner_loop_a ] 1799 %v3 = load i1, i1* %ptr 1800 br i1 %v3, label %loop_latch, label %loop_exit 1801; CHECK: inner_loop_exit: 1802; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1803; CHECK-NEXT: br i1 %[[V]], label %loop_latch, label %loop_exit.loopexit1 1804 1805loop_latch: 1806 br label %loop_begin 1807; CHECK: loop_latch: 1808; CHECK-NEXT: br label %loop_begin 1809 1810loop_exit: 1811 %a.lcssa = phi i32 [ %a, %inner_loop_begin ], [ %a.inner_lcssa, %inner_loop_exit ] 1812 ret i32 %a.lcssa 1813; CHECK: loop_exit.loopexit: 1814; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin ] 1815; CHECK-NEXT: br label %loop_exit 1816; 1817; CHECK: loop_exit.loopexit1: 1818; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit ] 1819; CHECK-NEXT: br label %loop_exit 1820; 1821; CHECK: loop_exit: 1822; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.loopexit ], [ %[[A_LCSSA_US]], %loop_exit.loopexit1 ] 1823; CHECK-NEXT: ret i32 %[[A_PHI]] 1824} 1825 1826; Like test11a, but checking that when the whole thing is wrapped in yet 1827; another loop, we correctly attribute the cloned preheader to that outermost 1828; loop rather than only handling the case where the preheader is not in any loop 1829; at all. 1830define i32 @test12a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 1831; CHECK-LABEL: @test12a( 1832entry: 1833 br label %loop_begin 1834; CHECK-NEXT: entry: 1835; CHECK-NEXT: br label %loop_begin 1836 1837loop_begin: 1838 br label %inner_loop_begin 1839; CHECK: loop_begin: 1840; CHECK-NEXT: br label %inner_loop_begin 1841 1842inner_loop_begin: 1843 %b = load i32, i32* %b.ptr 1844 %v1 = load i1, i1* %ptr 1845 br i1 %v1, label %inner_loop_latch, label %inner_inner_loop_ph 1846; CHECK: inner_loop_begin: 1847; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 1848; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1849; CHECK-NEXT: br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph 1850 1851inner_inner_loop_ph: 1852 %cond = load i1, i1* %cond.ptr 1853 br label %inner_inner_loop_begin 1854; CHECK: inner_inner_loop_ph: 1855; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 1856; CHECK-NEXT: br i1 %[[COND]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split 1857 1858inner_inner_loop_begin: 1859 call void @sink1(i32 %b) 1860 %a = load i32, i32* %a.ptr 1861 br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_a 1862 1863inner_inner_loop_a: 1864 %v2 = load i1, i1* %ptr 1865 br i1 %v2, label %inner_inner_loop_exit, label %inner_inner_loop_begin 1866; The cloned path doesn't actually loop and is an exit from the outer loop as 1867; well. 1868; 1869; CHECK: inner_inner_loop_ph.split.us: 1870; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_ph ] 1871; CHECK-NEXT: br label %inner_inner_loop_begin.us 1872; 1873; CHECK: inner_inner_loop_begin.us: 1874; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) 1875; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1876; CHECK-NEXT: br label %inner_loop_exit.loopexit.split.us 1877; 1878; CHECK: inner_loop_exit.loopexit.split.us: 1879; CHECK-NEXT: %[[A_INNER_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_inner_loop_begin.us ] 1880; CHECK-NEXT: br label %inner_loop_exit.loopexit 1881; 1882; The original remains a loop losing the exit edge. 1883; 1884; CHECK: inner_inner_loop_ph.split: 1885; CHECK-NEXT: br label %inner_inner_loop_begin 1886; 1887; CHECK: inner_inner_loop_begin: 1888; CHECK-NEXT: call void @sink1(i32 %[[B]]) 1889; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1890; CHECK-NEXT: br label %inner_inner_loop_a 1891; 1892; CHECK: inner_inner_loop_a: 1893; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1894; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit, label %inner_inner_loop_begin 1895 1896inner_inner_loop_exit: 1897 %a.inner_inner_lcssa = phi i32 [ %a, %inner_inner_loop_a ] 1898 %v3 = load i1, i1* %ptr 1899 br i1 %v3, label %inner_loop_latch, label %inner_loop_exit 1900; CHECK: inner_inner_loop_exit: 1901; CHECK-NEXT: %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_inner_loop_a ] 1902; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1903; CHECK-NEXT: br i1 %[[V]], label %inner_loop_latch, label %inner_loop_exit.loopexit1 1904 1905inner_loop_latch: 1906 br label %inner_loop_begin 1907; CHECK: inner_loop_latch: 1908; CHECK-NEXT: br label %inner_loop_begin 1909 1910inner_loop_exit: 1911 %a.inner_lcssa = phi i32 [ %a, %inner_inner_loop_begin ], [ %a.inner_inner_lcssa, %inner_inner_loop_exit ] 1912 %v4 = load i1, i1* %ptr 1913 br i1 %v4, label %loop_begin, label %loop_exit 1914; CHECK: inner_loop_exit.loopexit: 1915; CHECK-NEXT: br label %inner_loop_exit 1916; 1917; CHECK: inner_loop_exit.loopexit1: 1918; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_exit ] 1919; CHECK-NEXT: br label %inner_loop_exit 1920; 1921; CHECK: inner_loop_exit: 1922; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA_US]], %inner_loop_exit.loopexit ], [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit1 ] 1923; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1924; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit 1925 1926loop_exit: 1927 %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ] 1928 ret i32 %a.lcssa 1929; CHECK: loop_exit: 1930; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] 1931; CHECK-NEXT: ret i32 %[[A_LCSSA]] 1932} 1933 1934; Like test11b, but checking that when the whole thing is wrapped in yet 1935; another loop, we correctly sink the preheader to the outermost loop rather 1936; than only handling the case where the preheader is completely removed from 1937; a loop. 1938define i32 @test12b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { 1939; CHECK-LABEL: @test12b( 1940entry: 1941 br label %loop_begin 1942; CHECK-NEXT: entry: 1943; CHECK-NEXT: br label %loop_begin 1944 1945loop_begin: 1946 br label %inner_loop_begin 1947; CHECK: loop_begin: 1948; CHECK-NEXT: br label %inner_loop_begin 1949 1950inner_loop_begin: 1951 %b = load i32, i32* %b.ptr 1952 %v1 = load i1, i1* %ptr 1953 br i1 %v1, label %inner_loop_latch, label %inner_inner_loop_ph 1954; CHECK: inner_loop_begin: 1955; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 1956; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1957; CHECK-NEXT: br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph 1958 1959inner_inner_loop_ph: 1960 %cond = load i1, i1* %cond.ptr 1961 br label %inner_inner_loop_begin 1962; CHECK: inner_inner_loop_ph: 1963; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr 1964; CHECK-NEXT: br i1 %[[COND]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split 1965 1966inner_inner_loop_begin: 1967 call void @sink1(i32 %b) 1968 %a = load i32, i32* %a.ptr 1969 br i1 %cond, label %inner_inner_loop_a, label %inner_loop_exit 1970 1971inner_inner_loop_a: 1972 %v2 = load i1, i1* %ptr 1973 br i1 %v2, label %inner_inner_loop_exit, label %inner_inner_loop_begin 1974; The cloned path continues to loop without the exit out of the entire nest. 1975; 1976; CHECK: inner_inner_loop_ph.split.us: 1977; CHECK-NEXT: br label %inner_inner_loop_begin.us 1978; 1979; CHECK: inner_inner_loop_begin.us: 1980; CHECK-NEXT: call void @sink1(i32 %[[B]]) 1981; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 1982; CHECK-NEXT: br label %inner_inner_loop_a.us 1983; 1984; CHECK: inner_inner_loop_a.us: 1985; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 1986; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_begin.us 1987; 1988; CHECK: inner_inner_loop_exit.split.us: 1989; CHECK-NEXT: %[[A_INNER_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_inner_loop_a.us ] 1990; CHECK-NEXT: br label %inner_inner_loop_exit 1991; 1992; The original remains a loop losing the exit edge. 1993; 1994; CHECK: inner_inner_loop_ph.split: 1995; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_ph ] 1996; CHECK-NEXT: br label %inner_inner_loop_begin 1997; 1998; CHECK: inner_inner_loop_begin: 1999; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) 2000; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 2001; CHECK-NEXT: br label %inner_loop_exit.loopexit 2002 2003inner_inner_loop_exit: 2004 %a.inner_inner_lcssa = phi i32 [ %a, %inner_inner_loop_a ] 2005 %v3 = load i1, i1* %ptr 2006 br i1 %v3, label %inner_loop_latch, label %inner_loop_exit 2007; CHECK: inner_inner_loop_exit: 2008; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2009; CHECK-NEXT: br i1 %[[V]], label %inner_loop_latch, label %inner_loop_exit.loopexit1 2010 2011inner_loop_latch: 2012 br label %inner_loop_begin 2013; CHECK: inner_loop_latch: 2014; CHECK-NEXT: br label %inner_loop_begin 2015 2016inner_loop_exit: 2017 %a.inner_lcssa = phi i32 [ %a, %inner_inner_loop_begin ], [ %a.inner_inner_lcssa, %inner_inner_loop_exit ] 2018 %v4 = load i1, i1* %ptr 2019 br i1 %v4, label %loop_begin, label %loop_exit 2020; CHECK: inner_loop_exit.loopexit: 2021; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_inner_loop_begin ] 2022; CHECK-NEXT: br label %inner_loop_exit 2023; 2024; CHECK: inner_loop_exit.loopexit1: 2025; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA_US]], %inner_inner_loop_exit ] 2026; CHECK-NEXT: br label %inner_loop_exit 2027; 2028; CHECK: inner_loop_exit: 2029; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit1 ] 2030; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2031; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit 2032 2033loop_exit: 2034 %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ] 2035 ret i32 %a.lcssa 2036; CHECK: loop_exit: 2037; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] 2038; CHECK-NEXT: ret i32 %[[A_LCSSA]] 2039} 2040 2041; Test where the cloned loop has an inner loop that has to be traversed to form 2042; the cloned loop, and where this inner loop has multiple blocks, and where the 2043; exiting block that connects the inner loop to the cloned loop is not the header 2044; block. This ensures that we correctly handle interesting corner cases of 2045; traversing back to the header when establishing the cloned loop. 2046define i32 @test13a(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) { 2047; CHECK-LABEL: @test13a( 2048entry: 2049 br label %loop_begin 2050; CHECK-NEXT: entry: 2051; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 2052 2053loop_begin: 2054 %a = load i32, i32* %a.ptr 2055 %v1 = load i1, i1* %ptr 2056 br i1 %v1, label %loop_a, label %loop_b 2057 2058loop_a: 2059 %v2 = load i1, i1* %ptr 2060 br i1 %v2, label %loop_exit, label %loop_latch 2061 2062loop_b: 2063 %b = load i32, i32* %b.ptr 2064 br i1 %cond, label %loop_b_inner_ph, label %loop_exit 2065 2066loop_b_inner_ph: 2067 br label %loop_b_inner_header 2068 2069loop_b_inner_header: 2070 %v3 = load i1, i1* %ptr 2071 br i1 %v3, label %loop_b_inner_latch, label %loop_b_inner_body 2072 2073loop_b_inner_body: 2074 %v4 = load i1, i1* %ptr 2075 br i1 %v4, label %loop_b_inner_latch, label %loop_b_inner_exit 2076 2077loop_b_inner_latch: 2078 br label %loop_b_inner_header 2079 2080loop_b_inner_exit: 2081 br label %loop_latch 2082 2083loop_latch: 2084 br label %loop_begin 2085; The cloned loop contains an inner loop within it. 2086; 2087; CHECK: entry.split.us: 2088; CHECK-NEXT: br label %loop_begin.us 2089; 2090; CHECK: loop_begin.us: 2091; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 2092; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2093; CHECK-NEXT: br i1 %[[V]], label %loop_a.us, label %loop_b.us 2094; 2095; CHECK: loop_b.us: 2096; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 2097; CHECK-NEXT: br label %loop_b_inner_ph.us 2098; 2099; CHECK: loop_b_inner_ph.us: 2100; CHECK-NEXT: br label %loop_b_inner_header.us 2101; 2102; CHECK: loop_b_inner_header.us: 2103; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2104; CHECK-NEXT: br i1 %[[V]], label %loop_b_inner_latch.us, label %loop_b_inner_body.us 2105; 2106; CHECK: loop_b_inner_body.us: 2107; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2108; CHECK-NEXT: br i1 %[[V]], label %loop_b_inner_latch.us, label %loop_b_inner_exit.us 2109; 2110; CHECK: loop_b_inner_exit.us: 2111; CHECK-NEXT: br label %loop_latch.us 2112; 2113; CHECK: loop_b_inner_latch.us: 2114; CHECK-NEXT: br label %loop_b_inner_header.us 2115; 2116; CHECK: loop_a.us: 2117; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2118; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us, label %loop_latch.us 2119; 2120; CHECK: loop_latch.us: 2121; CHECK-NEXT: br label %loop_begin.us 2122; 2123; CHECK: loop_exit.split.us: 2124; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ] 2125; CHECK-NEXT: br label %loop_exit 2126; 2127; And the original loop no longer contains an inner loop. 2128; 2129; CHECK: entry.split: 2130; CHECK-NEXT: br label %loop_begin 2131; 2132; CHECK: loop_begin: 2133; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 2134; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2135; CHECK-NEXT: br i1 %[[V]], label %loop_a, label %loop_b 2136; 2137; CHECK: loop_a: 2138; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2139; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.loopexit, label %loop_latch 2140; 2141; CHECK: loop_b: 2142; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 2143; CHECK-NEXT: br label %loop_exit.split 2144; 2145; CHECK: loop_latch: 2146; CHECK-NEXT: br label %loop_begin 2147 2148loop_exit: 2149 %lcssa = phi i32 [ %a, %loop_a ], [ %b, %loop_b ] 2150 ret i32 %lcssa 2151; CHECK: loop_exit.split.loopexit: 2152; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ] 2153; CHECK-NEXT: br label %loop_exit.split 2154; 2155; CHECK: loop_exit.split: 2156; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[B]], %loop_b ], [ %[[A_LCSSA]], %loop_exit.split.loopexit ] 2157; CHECK-NEXT: br label %loop_exit 2158; 2159; CHECK: loop_exit: 2160; CHECK-NEXT: %[[AB_PHI_US:.*]] = phi i32 [ %[[AB_PHI]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ] 2161; CHECK-NEXT: ret i32 %[[AB_PHI_US]] 2162} 2163 2164; Test where the original loop has an inner loop that has to be traversed to 2165; rebuild the loop, and where this inner loop has multiple blocks, and where 2166; the exiting block that connects the inner loop to the original loop is not 2167; the header block. This ensures that we correctly handle interesting corner 2168; cases of traversing back to the header when re-establishing the original loop 2169; still exists after unswitching. 2170define i32 @test13b(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) { 2171; CHECK-LABEL: @test13b( 2172entry: 2173 br label %loop_begin 2174; CHECK-NEXT: entry: 2175; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 2176 2177loop_begin: 2178 %a = load i32, i32* %a.ptr 2179 %v1 = load i1, i1* %ptr 2180 br i1 %v1, label %loop_a, label %loop_b 2181 2182loop_a: 2183 %v2 = load i1, i1* %ptr 2184 br i1 %v2, label %loop_exit, label %loop_latch 2185 2186loop_b: 2187 %b = load i32, i32* %b.ptr 2188 br i1 %cond, label %loop_exit, label %loop_b_inner_ph 2189 2190loop_b_inner_ph: 2191 br label %loop_b_inner_header 2192 2193loop_b_inner_header: 2194 %v3 = load i1, i1* %ptr 2195 br i1 %v3, label %loop_b_inner_latch, label %loop_b_inner_body 2196 2197loop_b_inner_body: 2198 %v4 = load i1, i1* %ptr 2199 br i1 %v4, label %loop_b_inner_latch, label %loop_b_inner_exit 2200 2201loop_b_inner_latch: 2202 br label %loop_b_inner_header 2203 2204loop_b_inner_exit: 2205 br label %loop_latch 2206 2207loop_latch: 2208 br label %loop_begin 2209; The cloned loop doesn't contain an inner loop. 2210; 2211; CHECK: entry.split.us: 2212; CHECK-NEXT: br label %loop_begin.us 2213; 2214; CHECK: loop_begin.us: 2215; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 2216; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2217; CHECK-NEXT: br i1 %[[V]], label %loop_a.us, label %loop_b.us 2218; 2219; CHECK: loop_b.us: 2220; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 2221; CHECK-NEXT: br label %loop_exit.split.us 2222; 2223; CHECK: loop_a.us: 2224; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2225; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us.loopexit, label %loop_latch.us 2226; 2227; CHECK: loop_latch.us: 2228; CHECK-NEXT: br label %loop_begin.us 2229; 2230; CHECK: loop_exit.split.us.loopexit: 2231; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ] 2232; CHECK-NEXT: br label %loop_exit.split.us 2233; 2234; CHECK: loop_exit.split.us: 2235; CHECK-NEXT: %[[AB_PHI_US:.*]] = phi i32 [ %[[B]], %loop_b.us ], [ %[[A_LCSSA_US]], %loop_exit.split.us.loopexit ] 2236; CHECK-NEXT: br label %loop_exit 2237; 2238; But the original loop contains an inner loop that must be traversed.; 2239; 2240; CHECK: entry.split: 2241; CHECK-NEXT: br label %loop_begin 2242; 2243; CHECK: loop_begin: 2244; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr 2245; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2246; CHECK-NEXT: br i1 %[[V]], label %loop_a, label %loop_b 2247; 2248; CHECK: loop_a: 2249; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2250; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split, label %loop_latch 2251; 2252; CHECK: loop_b: 2253; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr 2254; CHECK-NEXT: br label %loop_b_inner_ph 2255; 2256; CHECK: loop_b_inner_ph: 2257; CHECK-NEXT: br label %loop_b_inner_header 2258; 2259; CHECK: loop_b_inner_header: 2260; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2261; CHECK-NEXT: br i1 %[[V]], label %loop_b_inner_latch, label %loop_b_inner_body 2262; 2263; CHECK: loop_b_inner_body: 2264; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2265; CHECK-NEXT: br i1 %[[V]], label %loop_b_inner_latch, label %loop_b_inner_exit 2266; 2267; CHECK: loop_b_inner_latch: 2268; CHECK-NEXT: br label %loop_b_inner_header 2269; 2270; CHECK: loop_b_inner_exit: 2271; CHECK-NEXT: br label %loop_latch 2272; 2273; CHECK: loop_latch: 2274; CHECK-NEXT: br label %loop_begin 2275 2276loop_exit: 2277 %lcssa = phi i32 [ %a, %loop_a ], [ %b, %loop_b ] 2278 ret i32 %lcssa 2279; CHECK: loop_exit.split: 2280; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ] 2281; CHECK-NEXT: br label %loop_exit 2282; 2283; CHECK: loop_exit: 2284; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[AB_PHI_US]], %loop_exit.split.us ] 2285; CHECK-NEXT: ret i32 %[[AB_PHI]] 2286} 2287 2288define i32 @test20(i32* %var, i32 %cond1, i32 %cond2) { 2289; CHECK-LABEL: @test20( 2290entry: 2291 br label %loop_begin 2292; CHECK-NEXT: entry: 2293; CHECK-NEXT: switch i32 %cond2, label %[[ENTRY_SPLIT_EXIT:.*]] [ 2294; CHECK-NEXT: i32 0, label %[[ENTRY_SPLIT_A:.*]] 2295; CHECK-NEXT: i32 1, label %[[ENTRY_SPLIT_A]] 2296; CHECK-NEXT: i32 13, label %[[ENTRY_SPLIT_B:.*]] 2297; CHECK-NEXT: i32 2, label %[[ENTRY_SPLIT_A]] 2298; CHECK-NEXT: i32 42, label %[[ENTRY_SPLIT_C:.*]] 2299; CHECK-NEXT: ] 2300 2301loop_begin: 2302 %var_val = load i32, i32* %var 2303 switch i32 %cond2, label %loop_exit [ 2304 i32 0, label %loop_a 2305 i32 1, label %loop_a 2306 i32 13, label %loop_b 2307 i32 2, label %loop_a 2308 i32 42, label %loop_c 2309 ] 2310 2311loop_a: 2312 call i32 @a() 2313 br label %loop_latch 2314; Unswitched 'a' loop. 2315; 2316; CHECK: [[ENTRY_SPLIT_A]]: 2317; CHECK-NEXT: br label %[[LOOP_BEGIN_A:.*]] 2318; 2319; CHECK: [[LOOP_BEGIN_A]]: 2320; CHECK-NEXT: %{{.*}} = load i32, i32* %var 2321; CHECK-NEXT: br label %[[LOOP_A:.*]] 2322; 2323; CHECK: [[LOOP_A]]: 2324; CHECK-NEXT: call i32 @a() 2325; CHECK-NEXT: br label %[[LOOP_LATCH_A:.*]] 2326; 2327; CHECK: [[LOOP_LATCH_A]]: 2328; CHECK: br label %[[LOOP_BEGIN_A]] 2329 2330loop_b: 2331 call i32 @b() 2332 br label %loop_latch 2333; Unswitched 'b' loop. 2334; 2335; CHECK: [[ENTRY_SPLIT_B]]: 2336; CHECK-NEXT: br label %[[LOOP_BEGIN_B:.*]] 2337; 2338; CHECK: [[LOOP_BEGIN_B]]: 2339; CHECK-NEXT: %{{.*}} = load i32, i32* %var 2340; CHECK-NEXT: br label %[[LOOP_B:.*]] 2341; 2342; CHECK: [[LOOP_B]]: 2343; CHECK-NEXT: call i32 @b() 2344; CHECK-NEXT: br label %[[LOOP_LATCH_B:.*]] 2345; 2346; CHECK: [[LOOP_LATCH_B]]: 2347; CHECK: br label %[[LOOP_BEGIN_B]] 2348 2349loop_c: 2350 call i32 @c() noreturn nounwind 2351 br label %loop_latch 2352; Unswitched 'c' loop. 2353; 2354; CHECK: [[ENTRY_SPLIT_C]]: 2355; CHECK-NEXT: br label %[[LOOP_BEGIN_C:.*]] 2356; 2357; CHECK: [[LOOP_BEGIN_C]]: 2358; CHECK-NEXT: %{{.*}} = load i32, i32* %var 2359; CHECK-NEXT: br label %[[LOOP_C:.*]] 2360; 2361; CHECK: [[LOOP_C]]: 2362; CHECK-NEXT: call i32 @c() 2363; CHECK-NEXT: br label %[[LOOP_LATCH_C:.*]] 2364; 2365; CHECK: [[LOOP_LATCH_C]]: 2366; CHECK: br label %[[LOOP_BEGIN_C]] 2367 2368loop_latch: 2369 br label %loop_begin 2370 2371loop_exit: 2372 %lcssa = phi i32 [ %var_val, %loop_begin ] 2373 ret i32 %lcssa 2374; Unswitched exit edge (no longer a loop). 2375; 2376; CHECK: [[ENTRY_SPLIT_EXIT]]: 2377; CHECK-NEXT: br label %loop_begin 2378; 2379; CHECK: loop_begin: 2380; CHECK-NEXT: %[[V:.*]] = load i32, i32* %var 2381; CHECK-NEXT: br label %loop_exit 2382; 2383; CHECK: loop_exit: 2384; CHECK-NEXT: %[[LCSSA:.*]] = phi i32 [ %[[V]], %loop_begin ] 2385; CHECK-NEXT: ret i32 %[[LCSSA]] 2386} 2387 2388; Negative test: we do not switch when the loop contains unstructured control 2389; flows as it would significantly complicate the process as novel loops might 2390; be formed, etc. 2391define void @test_no_unswitch_unstructured_cfg(i1* %ptr, i1 %cond) { 2392; CHECK-LABEL: @test_no_unswitch_unstructured_cfg( 2393entry: 2394 br label %loop_begin 2395 2396loop_begin: 2397 br i1 %cond, label %loop_left, label %loop_right 2398 2399loop_left: 2400 %v1 = load i1, i1* %ptr 2401 br i1 %v1, label %loop_right, label %loop_merge 2402 2403loop_right: 2404 %v2 = load i1, i1* %ptr 2405 br i1 %v2, label %loop_left, label %loop_merge 2406 2407loop_merge: 2408 %v3 = load i1, i1* %ptr 2409 br i1 %v3, label %loop_latch, label %loop_exit 2410 2411loop_latch: 2412 br label %loop_begin 2413 2414loop_exit: 2415 ret void 2416} 2417 2418; A test reduced out of 403.gcc with interesting nested loops that trigger 2419; multiple unswitches. A key component of this test is that there are multiple 2420; paths to reach an inner loop after unswitching, and one of them is via the 2421; predecessors of the unswitched loop header. That can allow us to find the loop 2422; through multiple different paths. 2423define void @test21(i1 %a, i1 %b) { 2424; CHECK-LABEL: @test21( 2425bb: 2426 br label %bb3 2427; CHECK-NOT: br i1 %a 2428; 2429; CHECK: br i1 %a, label %[[BB_SPLIT_US:.*]], label %[[BB_SPLIT:.*]] 2430; 2431; CHECK-NOT: br i1 %a 2432; CHECK-NOT: br i1 %b 2433; 2434; CHECK: [[BB_SPLIT]]: 2435; CHECK: br i1 %b 2436; 2437; CHECK-NOT: br i1 %a 2438; CHECK-NOT: br i1 %b 2439 2440bb3: 2441 %tmp1.0 = phi i32 [ 0, %bb ], [ %tmp1.3, %bb23 ] 2442 br label %bb7 2443 2444bb7: 2445 %tmp.0 = phi i1 [ true, %bb3 ], [ false, %bb19 ] 2446 %tmp1.1 = phi i32 [ %tmp1.0, %bb3 ], [ %tmp1.2.lcssa, %bb19 ] 2447 br i1 %tmp.0, label %bb11.preheader, label %bb23 2448 2449bb11.preheader: 2450 br i1 %a, label %bb19, label %bb14.lr.ph 2451 2452bb14.lr.ph: 2453 br label %bb14 2454 2455bb14: 2456 %tmp2.02 = phi i32 [ 0, %bb14.lr.ph ], [ 1, %bb14 ] 2457 br i1 %b, label %bb11.bb19_crit_edge, label %bb14 2458 2459bb11.bb19_crit_edge: 2460 %split = phi i32 [ %tmp2.02, %bb14 ] 2461 br label %bb19 2462 2463bb19: 2464 %tmp1.2.lcssa = phi i32 [ %split, %bb11.bb19_crit_edge ], [ %tmp1.1, %bb11.preheader ] 2465 %tmp21 = icmp eq i32 %tmp1.2.lcssa, 0 2466 br i1 %tmp21, label %bb23, label %bb7 2467 2468bb23: 2469 %tmp1.3 = phi i32 [ %tmp1.2.lcssa, %bb19 ], [ %tmp1.1, %bb7 ] 2470 br label %bb3 2471} 2472 2473; A test reduced out of 400.perlbench that when unswitching the `%stop` 2474; condition clones a loop nest outside of a containing loop. This excercises a 2475; different cloning path from our other test cases and in turn verifying the 2476; resulting structure can catch any failures to correctly clone these nested 2477; loops. 2478declare void @f() 2479declare void @g() 2480declare i32 @h(i32 %arg) 2481define void @test22(i32 %arg) { 2482; CHECK-LABEL: define void @test22( 2483entry: 2484 br label %loop1.header 2485 2486loop1.header: 2487 %stop = phi i1 [ true, %loop1.latch ], [ false, %entry ] 2488 %i = phi i32 [ %i.lcssa, %loop1.latch ], [ %arg, %entry ] 2489; CHECK: %[[I:.*]] = phi i32 [ %{{.*}}, %loop1.latch ], [ %arg, %entry ] 2490 br i1 %stop, label %loop1.exit, label %loop1.body.loop2.ph 2491; CHECK: br i1 %stop, label %loop1.exit, label %loop1.body.loop2.ph 2492 2493loop1.body.loop2.ph: 2494 br label %loop2.header 2495; Just check that the we unswitched the key condition and that leads to the 2496; inner loop header. 2497; 2498; CHECK: loop1.body.loop2.ph: 2499; CHECK-NEXT: br i1 %stop, label %[[SPLIT_US:.*]], label %[[SPLIT:.*]] 2500; 2501; CHECK: [[SPLIT_US]]: 2502; CHECK-NEXT: br label %[[LOOP2_HEADER_US:.*]] 2503; 2504; CHECK: [[LOOP2_HEADER_US]]: 2505; CHECK-NEXT: %{{.*}} = phi i32 [ %[[I]], %[[SPLIT_US]] ] 2506; 2507; CHECK: [[SPLIT]]: 2508; CHECK-NEXT: br label %[[LOOP2_HEADER:.*]] 2509; 2510; CHECK: [[LOOP2_HEADER]]: 2511; CHECK-NEXT: %{{.*}} = phi i32 [ %[[I]], %[[SPLIT]] ] 2512 2513loop2.header: 2514 %i.inner = phi i32 [ %i, %loop1.body.loop2.ph ], [ %i.next, %loop2.latch ] 2515 br label %loop3.header 2516 2517loop3.header: 2518 %sw = call i32 @h(i32 %i.inner) 2519 switch i32 %sw, label %loop3.exit [ 2520 i32 32, label %loop3.header 2521 i32 59, label %loop2.latch 2522 i32 36, label %loop1.latch 2523 ] 2524 2525loop2.latch: 2526 %i.next = add i32 %i.inner, 1 2527 br i1 %stop, label %loop2.exit, label %loop2.header 2528 2529loop1.latch: 2530 %i.lcssa = phi i32 [ %i.inner, %loop3.header ] 2531 br label %loop1.header 2532 2533loop3.exit: 2534 call void @f() 2535 ret void 2536 2537loop2.exit: 2538 call void @g() 2539 ret void 2540 2541loop1.exit: 2542 call void @g() 2543 ret void 2544} 2545 2546; Test that when we are unswitching and need to rebuild the loop block set we 2547; correctly skip past inner loops. We want to use the inner loop to efficiently 2548; skip whole subregions of the outer loop blocks but just because the header of 2549; the outer loop is also the preheader of an inner loop shouldn't confuse this 2550; walk. 2551define void @test23(i1 %arg, i1* %ptr) { 2552; CHECK-LABEL: define void @test23( 2553entry: 2554 br label %outer.header 2555; CHECK: entry: 2556; CHECK-NEXT: br i1 %arg, 2557; 2558; Just verify that we unswitched the correct bits. We should call `@f` twice in 2559; one unswitch and `@f` and then `@g` in the other. 2560; CHECK: call void 2561; CHECK-SAME: @f 2562; CHECK: call void 2563; CHECK-SAME: @f 2564; 2565; CHECK: call void 2566; CHECK-SAME: @f 2567; CHECK: call void 2568; CHECK-SAME: @g 2569 2570outer.header: 2571 br label %inner.header 2572 2573inner.header: 2574 call void @f() 2575 br label %inner.latch 2576 2577inner.latch: 2578 %inner.cond = load i1, i1* %ptr 2579 br i1 %inner.cond, label %inner.header, label %outer.body 2580 2581outer.body: 2582 br i1 %arg, label %outer.body.left, label %outer.body.right 2583 2584outer.body.left: 2585 call void @f() 2586 br label %outer.latch 2587 2588outer.body.right: 2589 call void @g() 2590 br label %outer.latch 2591 2592outer.latch: 2593 %outer.cond = load i1, i1* %ptr 2594 br i1 %outer.cond, label %outer.header, label %exit 2595 2596exit: 2597 ret void 2598} 2599 2600; Non-trivial loop unswitching where there are two invariant conditions, but the 2601; second one is only in the cloned copy of the loop after unswitching. 2602define i32 @test24(i1* %ptr, i1 %cond1, i1 %cond2) { 2603; CHECK-LABEL: @test24( 2604entry: 2605 br label %loop_begin 2606; CHECK-NEXT: entry: 2607; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split 2608 2609loop_begin: 2610 br i1 %cond1, label %loop_a, label %loop_b 2611 2612loop_a: 2613 br i1 %cond2, label %loop_a_a, label %loop_a_c 2614; The second unswitched condition. 2615; 2616; CHECK: entry.split.us: 2617; CHECK-NEXT: br i1 %cond2, label %entry.split.us.split.us, label %entry.split.us.split 2618 2619loop_a_a: 2620 call i32 @a() 2621 br label %latch 2622; The 'loop_a_a' unswitched loop. 2623; 2624; CHECK: entry.split.us.split.us: 2625; CHECK-NEXT: br label %loop_begin.us.us 2626; 2627; CHECK: loop_begin.us.us: 2628; CHECK-NEXT: br label %loop_a.us.us 2629; 2630; CHECK: loop_a.us.us: 2631; CHECK-NEXT: br label %loop_a_a.us.us 2632; 2633; CHECK: loop_a_a.us.us: 2634; CHECK-NEXT: call i32 @a() 2635; CHECK-NEXT: br label %latch.us.us 2636; 2637; CHECK: latch.us.us: 2638; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2639; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us.us, label %loop_exit.split.us.split.us 2640; 2641; CHECK: loop_exit.split.us.split.us: 2642; CHECK-NEXT: br label %loop_exit.split 2643 2644loop_a_c: 2645 call i32 @c() 2646 br label %latch 2647; The 'loop_a_c' unswitched loop. 2648; 2649; CHECK: entry.split.us.split: 2650; CHECK-NEXT: br label %loop_begin.us 2651; 2652; CHECK: loop_begin.us: 2653; CHECK-NEXT: br label %loop_a.us 2654; 2655; CHECK: loop_a.us: 2656; CHECK-NEXT: br label %loop_a_c.us 2657; 2658; CHECK: loop_a_c.us: 2659; CHECK-NEXT: call i32 @c() 2660; CHECK-NEXT: br label %latch 2661; 2662; CHECK: latch.us: 2663; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2664; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us.split 2665; 2666; CHECK: loop_exit.split.us.split: 2667; CHECK-NEXT: br label %loop_exit.split 2668 2669loop_b: 2670 call i32 @b() 2671 br label %latch 2672; The 'loop_b' unswitched loop. 2673; 2674; CHECK: entry.split: 2675; CHECK-NEXT: br label %loop_begin 2676; 2677; CHECK: loop_begin: 2678; CHECK-NEXT: br label %loop_b 2679; 2680; CHECK: loop_b: 2681; CHECK-NEXT: call i32 @b() 2682; CHECK-NEXT: br label %latch 2683; 2684; CHECK: latch: 2685; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr 2686; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split 2687; 2688; CHECK: loop_exit.split: 2689; CHECK-NEXT: br label %loop_exit 2690 2691latch: 2692 %v = load i1, i1* %ptr 2693 br i1 %v, label %loop_begin, label %loop_exit 2694 2695loop_exit: 2696 ret i32 0 2697; CHECK: loop_exit: 2698; CHECK-NEXT: ret 2699} 2700 2701; Non-trivial partial loop unswitching of an invariant input to an 'or'. 2702define i32 @test25(i1* %ptr, i1 %cond) { 2703; CHECK-LABEL: @test25( 2704entry: 2705 br label %loop_begin 2706; CHECK-NEXT: entry: 2707; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split 2708 2709loop_begin: 2710 %v1 = load i1, i1* %ptr 2711 %cond_or = or i1 %v1, %cond 2712 br i1 %cond_or, label %loop_a, label %loop_b 2713 2714loop_a: 2715 call i32 @a() 2716 br label %latch 2717; The 'loop_a' unswitched loop. 2718; 2719; CHECK: entry.split.us: 2720; CHECK-NEXT: br label %loop_begin.us 2721; 2722; CHECK: loop_begin.us: 2723; CHECK-NEXT: br label %loop_a.us 2724; 2725; CHECK: loop_a.us: 2726; CHECK-NEXT: call i32 @a() 2727; CHECK-NEXT: br label %latch.us 2728; 2729; CHECK: latch.us: 2730; CHECK-NEXT: %[[V2_US:.*]] = load i1, i1* %ptr 2731; CHECK-NEXT: br i1 %[[V2_US]], label %loop_begin.us, label %loop_exit.split.us 2732; 2733; CHECK: loop_exit.split.us: 2734; CHECK-NEXT: br label %loop_exit 2735 2736loop_b: 2737 call i32 @b() 2738 br label %latch 2739; The original loop. 2740; 2741; CHECK: entry.split: 2742; CHECK-NEXT: br label %loop_begin 2743; 2744; CHECK: loop_begin: 2745; CHECK-NEXT: %[[V1:.*]] = load i1, i1* %ptr 2746; CHECK-NEXT: %[[OR:.*]] = or i1 %[[V1]], false 2747; CHECK-NEXT: br i1 %[[OR]], label %loop_a, label %loop_b 2748; 2749; CHECK: loop_a: 2750; CHECK-NEXT: call i32 @a() 2751; CHECK-NEXT: br label %latch 2752; 2753; CHECK: loop_b: 2754; CHECK-NEXT: call i32 @b() 2755; CHECK-NEXT: br label %latch 2756 2757latch: 2758 %v2 = load i1, i1* %ptr 2759 br i1 %v2, label %loop_begin, label %loop_exit 2760; CHECK: latch: 2761; CHECK-NEXT: %[[V2:.*]] = load i1, i1* %ptr 2762; CHECK-NEXT: br i1 %[[V2]], label %loop_begin, label %loop_exit.split 2763 2764loop_exit: 2765 ret i32 0 2766; CHECK: loop_exit.split: 2767; CHECK-NEXT: br label %loop_exit 2768; 2769; CHECK: loop_exit: 2770; CHECK-NEXT: ret 2771} 2772 2773; Non-trivial partial loop unswitching of multiple invariant inputs to an `and` 2774; chain. 2775define i32 @test26(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2, i1 %cond3) { 2776; CHECK-LABEL: @test26( 2777entry: 2778 br label %loop_begin 2779; CHECK-NEXT: entry: 2780; CHECK-NEXT: %[[INV_AND:.*]] = and i1 %cond3, %cond1 2781; CHECK-NEXT: br i1 %[[INV_AND]], label %entry.split, label %entry.split.us 2782 2783loop_begin: 2784 %v1 = load i1, i1* %ptr1 2785 %v2 = load i1, i1* %ptr2 2786 %cond_and1 = and i1 %v1, %cond1 2787 %cond_or1 = or i1 %v2, %cond2 2788 %cond_and2 = and i1 %cond_and1, %cond_or1 2789 %cond_and3 = and i1 %cond_and2, %cond3 2790 br i1 %cond_and3, label %loop_a, label %loop_b 2791; The 'loop_b' unswitched loop. 2792; 2793; CHECK: entry.split.us: 2794; CHECK-NEXT: br label %loop_begin.us 2795; 2796; CHECK: loop_begin.us: 2797; CHECK-NEXT: br label %loop_b.us 2798; 2799; CHECK: loop_b.us: 2800; CHECK-NEXT: call i32 @b() 2801; CHECK-NEXT: br label %latch.us 2802; 2803; CHECK: latch.us: 2804; CHECK-NEXT: %[[V3_US:.*]] = load i1, i1* %ptr3 2805; CHECK-NEXT: br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us 2806; 2807; CHECK: loop_exit.split.us: 2808; CHECK-NEXT: br label %loop_exit 2809 2810; The original loop. 2811; 2812; CHECK: entry.split: 2813; CHECK-NEXT: br label %loop_begin 2814; 2815; CHECK: loop_begin: 2816; CHECK-NEXT: %[[V1:.*]] = load i1, i1* %ptr1 2817; CHECK-NEXT: %[[V2:.*]] = load i1, i1* %ptr2 2818; CHECK-NEXT: %[[AND1:.*]] = and i1 %[[V1]], true 2819; CHECK-NEXT: %[[OR1:.*]] = or i1 %[[V2]], %cond2 2820; CHECK-NEXT: %[[AND2:.*]] = and i1 %[[AND1]], %[[OR1]] 2821; CHECK-NEXT: %[[AND3:.*]] = and i1 %[[AND2]], true 2822; CHECK-NEXT: br i1 %[[AND3]], label %loop_a, label %loop_b 2823 2824loop_a: 2825 call i32 @a() 2826 br label %latch 2827; CHECK: loop_a: 2828; CHECK-NEXT: call i32 @a() 2829; CHECK-NEXT: br label %latch 2830 2831loop_b: 2832 call i32 @b() 2833 br label %latch 2834; CHECK: loop_b: 2835; CHECK-NEXT: call i32 @b() 2836; CHECK-NEXT: br label %latch 2837 2838latch: 2839 %v3 = load i1, i1* %ptr3 2840 br i1 %v3, label %loop_begin, label %loop_exit 2841; CHECK: latch: 2842; CHECK-NEXT: %[[V3:.*]] = load i1, i1* %ptr3 2843; CHECK-NEXT: br i1 %[[V3]], label %loop_begin, label %loop_exit.split 2844 2845loop_exit: 2846 ret i32 0 2847; CHECK: loop_exit.split: 2848; CHECK-NEXT: br label %loop_exit 2849; 2850; CHECK: loop_exit: 2851; CHECK-NEXT: ret 2852} 2853 2854; Non-trivial partial loop unswitching of multiple invariant inputs to an `or` 2855; chain. Basically an inverted version of corresponding `and` test (test26). 2856define i32 @test27(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2, i1 %cond3) { 2857; CHECK-LABEL: @test27( 2858entry: 2859 br label %loop_begin 2860; CHECK-NEXT: entry: 2861; CHECK-NEXT: %[[INV_OR:.*]] = or i1 %cond3, %cond1 2862; CHECK-NEXT: br i1 %[[INV_OR]], label %entry.split.us, label %entry.split 2863 2864loop_begin: 2865 %v1 = load i1, i1* %ptr1 2866 %v2 = load i1, i1* %ptr2 2867 %cond_or1 = or i1 %v1, %cond1 2868 %cond_and1 = and i1 %v2, %cond2 2869 %cond_or2 = or i1 %cond_or1, %cond_and1 2870 %cond_or3 = or i1 %cond_or2, %cond3 2871 br i1 %cond_or3, label %loop_b, label %loop_a 2872; The 'loop_b' unswitched loop. 2873; 2874; CHECK: entry.split.us: 2875; CHECK-NEXT: br label %loop_begin.us 2876; 2877; CHECK: loop_begin.us: 2878; CHECK-NEXT: br label %loop_b.us 2879; 2880; CHECK: loop_b.us: 2881; CHECK-NEXT: call i32 @b() 2882; CHECK-NEXT: br label %latch.us 2883; 2884; CHECK: latch.us: 2885; CHECK-NEXT: %[[V3_US:.*]] = load i1, i1* %ptr3 2886; CHECK-NEXT: br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us 2887; 2888; CHECK: loop_exit.split.us: 2889; CHECK-NEXT: br label %loop_exit 2890 2891; The original loop. 2892; 2893; CHECK: entry.split: 2894; CHECK-NEXT: br label %loop_begin 2895; 2896; CHECK: loop_begin: 2897; CHECK-NEXT: %[[V1:.*]] = load i1, i1* %ptr1 2898; CHECK-NEXT: %[[V2:.*]] = load i1, i1* %ptr2 2899; CHECK-NEXT: %[[OR1:.*]] = or i1 %[[V1]], false 2900; CHECK-NEXT: %[[AND1:.*]] = and i1 %[[V2]], %cond2 2901; CHECK-NEXT: %[[OR2:.*]] = or i1 %[[OR1]], %[[AND1]] 2902; CHECK-NEXT: %[[OR3:.*]] = or i1 %[[OR2]], false 2903; CHECK-NEXT: br i1 %[[OR3]], label %loop_b, label %loop_a 2904 2905loop_a: 2906 call i32 @a() 2907 br label %latch 2908; CHECK: loop_a: 2909; CHECK-NEXT: call i32 @a() 2910; CHECK-NEXT: br label %latch 2911 2912loop_b: 2913 call i32 @b() 2914 br label %latch 2915; CHECK: loop_b: 2916; CHECK-NEXT: call i32 @b() 2917; CHECK-NEXT: br label %latch 2918 2919latch: 2920 %v3 = load i1, i1* %ptr3 2921 br i1 %v3, label %loop_begin, label %loop_exit 2922; CHECK: latch: 2923; CHECK-NEXT: %[[V3:.*]] = load i1, i1* %ptr3 2924; CHECK-NEXT: br i1 %[[V3]], label %loop_begin, label %loop_exit.split 2925 2926loop_exit: 2927 ret i32 0 2928; CHECK: loop_exit.split: 2929; CHECK-NEXT: br label %loop_exit 2930; 2931; CHECK: loop_exit: 2932; CHECK-NEXT: ret 2933} 2934 2935; Non-trivial unswitching of a switch. 2936define i32 @test28(i1* %ptr, i32 %cond) { 2937; CHECK-LABEL: @test28( 2938entry: 2939 br label %loop_begin 2940; CHECK-NEXT: entry: 2941; CHECK-NEXT: switch i32 %cond, label %[[ENTRY_SPLIT_LATCH:.*]] [ 2942; CHECK-NEXT: i32 0, label %[[ENTRY_SPLIT_A:.*]] 2943; CHECK-NEXT: i32 1, label %[[ENTRY_SPLIT_B:.*]] 2944; CHECK-NEXT: i32 2, label %[[ENTRY_SPLIT_C:.*]] 2945; CHECK-NEXT: ] 2946 2947loop_begin: 2948 switch i32 %cond, label %latch [ 2949 i32 0, label %loop_a 2950 i32 1, label %loop_b 2951 i32 2, label %loop_c 2952 ] 2953 2954loop_a: 2955 call i32 @a() 2956 br label %latch 2957; Unswitched 'a' loop. 2958; 2959; CHECK: [[ENTRY_SPLIT_A]]: 2960; CHECK-NEXT: br label %[[LOOP_BEGIN_A:.*]] 2961; 2962; CHECK: [[LOOP_BEGIN_A]]: 2963; CHECK-NEXT: br label %[[LOOP_A:.*]] 2964; 2965; CHECK: [[LOOP_A]]: 2966; CHECK-NEXT: call i32 @a() 2967; CHECK-NEXT: br label %[[LOOP_LATCH_A:.*]] 2968; 2969; CHECK: [[LOOP_LATCH_A]]: 2970; CHECK-NEXT: %[[V_A:.*]] = load i1, i1* %ptr 2971; CHECK: br i1 %[[V_A]], label %[[LOOP_BEGIN_A]], label %[[LOOP_EXIT_A:.*]] 2972; 2973; CHECK: [[LOOP_EXIT_A]]: 2974; CHECK-NEXT: br label %loop_exit 2975 2976loop_b: 2977 call i32 @b() 2978 br label %latch 2979; Unswitched 'b' loop. 2980; 2981; CHECK: [[ENTRY_SPLIT_B]]: 2982; CHECK-NEXT: br label %[[LOOP_BEGIN_B:.*]] 2983; 2984; CHECK: [[LOOP_BEGIN_B]]: 2985; CHECK-NEXT: br label %[[LOOP_B:.*]] 2986; 2987; CHECK: [[LOOP_B]]: 2988; CHECK-NEXT: call i32 @b() 2989; CHECK-NEXT: br label %[[LOOP_LATCH_B:.*]] 2990; 2991; CHECK: [[LOOP_LATCH_B]]: 2992; CHECK-NEXT: %[[V_B:.*]] = load i1, i1* %ptr 2993; CHECK: br i1 %[[V_B]], label %[[LOOP_BEGIN_B]], label %[[LOOP_EXIT_B:.*]] 2994; 2995; CHECK: [[LOOP_EXIT_B]]: 2996; CHECK-NEXT: br label %loop_exit 2997 2998loop_c: 2999 call i32 @c() 3000 br label %latch 3001; Unswitched 'c' loop. 3002; 3003; CHECK: [[ENTRY_SPLIT_C]]: 3004; CHECK-NEXT: br label %[[LOOP_BEGIN_C:.*]] 3005; 3006; CHECK: [[LOOP_BEGIN_C]]: 3007; CHECK-NEXT: br label %[[LOOP_C:.*]] 3008; 3009; CHECK: [[LOOP_C]]: 3010; CHECK-NEXT: call i32 @c() 3011; CHECK-NEXT: br label %[[LOOP_LATCH_C:.*]] 3012; 3013; CHECK: [[LOOP_LATCH_C]]: 3014; CHECK-NEXT: %[[V_C:.*]] = load i1, i1* %ptr 3015; CHECK: br i1 %[[V_C]], label %[[LOOP_BEGIN_C]], label %[[LOOP_EXIT_C:.*]] 3016; 3017; CHECK: [[LOOP_EXIT_C]]: 3018; CHECK-NEXT: br label %loop_exit 3019 3020latch: 3021 %v = load i1, i1* %ptr 3022 br i1 %v, label %loop_begin, label %loop_exit 3023; Unswitched the 'latch' only loop. 3024; 3025; CHECK: [[ENTRY_SPLIT_LATCH]]: 3026; CHECK-NEXT: br label %[[LOOP_BEGIN_LATCH:.*]] 3027; 3028; CHECK: [[LOOP_BEGIN_LATCH]]: 3029; CHECK-NEXT: br label %[[LOOP_LATCH_LATCH:.*]] 3030; 3031; CHECK: [[LOOP_LATCH_LATCH]]: 3032; CHECK-NEXT: %[[V_LATCH:.*]] = load i1, i1* %ptr 3033; CHECK: br i1 %[[V_LATCH]], label %[[LOOP_BEGIN_LATCH]], label %[[LOOP_EXIT_LATCH:.*]] 3034; 3035; CHECK: [[LOOP_EXIT_LATCH]]: 3036; CHECK-NEXT: br label %loop_exit 3037 3038loop_exit: 3039 ret i32 0 3040; CHECK: loop_exit: 3041; CHECK-NEXT: ret i32 0 3042} 3043 3044; A test case designed to exercise unusual properties of switches: they 3045; can introduce multiple edges to successors. These need lots of special case 3046; handling as they get collapsed in many cases (domtree, the unswitch itself) 3047; but not in all cases (the PHI node operands). 3048define i32 @test29(i32 %arg) { 3049; CHECK-LABEL: @test29( 3050entry: 3051 br label %header 3052; CHECK-NEXT: entry: 3053; CHECK-NEXT: switch i32 %arg, label %[[ENTRY_SPLIT_C:.*]] [ 3054; CHECK-NEXT: i32 0, label %[[ENTRY_SPLIT_A:.*]] 3055; CHECK-NEXT: i32 1, label %[[ENTRY_SPLIT_A]] 3056; CHECK-NEXT: i32 2, label %[[ENTRY_SPLIT_B:.*]] 3057; CHECK-NEXT: i32 3, label %[[ENTRY_SPLIT_C]] 3058; CHECK-NEXT: ] 3059 3060header: 3061 %tmp = call i32 @d() 3062 %cmp1 = icmp eq i32 %tmp, 0 3063 ; We set up a chain through all the successors of the switch that doesn't 3064 ; involve the switch so that we can have interesting PHI nodes in them. 3065 br i1 %cmp1, label %body.a, label %dispatch 3066 3067dispatch: 3068 ; Switch with multiple successors. We arrange the last successor to be the 3069 ; default to make the test case easier to read. This has a duplicate edge 3070 ; both to the default destination (which is completely superfluous but 3071 ; technically valid IR) and to a regular successor. 3072 switch i32 %arg, label %body.c [ 3073 i32 0, label %body.a 3074 i32 1, label %body.a 3075 i32 2, label %body.b 3076 i32 3, label %body.c 3077 ] 3078 3079body.a: 3080 %tmp.a.phi = phi i32 [ 0, %header ], [ %tmp, %dispatch ], [ %tmp, %dispatch ] 3081 %tmp.a = call i32 @a() 3082 %tmp.a.sum = add i32 %tmp.a.phi, %tmp.a 3083 br label %body.b 3084; Unswitched 'a' loop. 3085; 3086; CHECK: [[ENTRY_SPLIT_A]]: 3087; CHECK-NEXT: br label %[[HEADER_A:.*]] 3088; 3089; CHECK: [[HEADER_A]]: 3090; CHECK-NEXT: %[[TMP_A:.*]] = call i32 @d() 3091; CHECK-NEXT: %[[CMP1_A:.*]] = icmp eq i32 %[[TMP_A]], 0 3092; CHECK-NEXT: br i1 %[[CMP1_A]], label %[[BODY_A_A:.*]], label %[[DISPATCH_A:.*]] 3093; 3094; CHECK: [[DISPATCH_A]]: 3095; CHECK-NEXT: br label %[[BODY_A_A]] 3096; 3097; CHECK: [[BODY_A_A]]: 3098; CHECK-NEXT: %[[TMP_A_PHI_A:.*]] = phi i32 [ 0, %[[HEADER_A]] ], [ %[[TMP_A]], %[[DISPATCH_A]] ] 3099; CHECK-NEXT: %[[TMP_A_A:.*]] = call i32 @a() 3100; CHECK-NEXT: %[[TMP_A_SUM_A:.*]] = add i32 %[[TMP_A_PHI_A]], %[[TMP_A_A]] 3101; CHECK-NEXT: br label %[[BODY_B_A:.*]] 3102; 3103; CHECK: [[BODY_B_A]]: 3104; CHECK-NEXT: %[[TMP_B_PHI_A:.*]] = phi i32 [ %[[TMP_A_SUM_A]], %[[BODY_A_A]] ] 3105; CHECK-NEXT: %[[TMP_B_A:.*]] = call i32 @b() 3106; CHECK-NEXT: %[[TMP_B_SUM_A:.*]] = add i32 %[[TMP_B_PHI_A]], %[[TMP_B_A]] 3107; CHECK-NEXT: br label %[[BODY_C_A:.*]] 3108; 3109; CHECK: [[BODY_C_A]]: 3110; CHECK-NEXT: %[[TMP_C_PHI_A:.*]] = phi i32 [ %[[TMP_B_SUM_A]], %[[BODY_B_A]] ] 3111; CHECK-NEXT: %[[TMP_C_A:.*]] = call i32 @c() 3112; CHECK-NEXT: %[[TMP_C_SUM_A:.*]] = add i32 %[[TMP_C_PHI_A]], %[[TMP_C_A]] 3113; CHECK-NEXT: br label %[[LATCH_A:.*]] 3114; 3115; CHECK: [[LATCH_A]]: 3116; CHECK-NEXT: %[[CMP2_A:.*]] = icmp slt i32 %[[TMP_C_SUM_A]], 42 3117; CHECK: br i1 %[[CMP2_A]], label %[[HEADER_A]], label %[[LOOP_EXIT_A:.*]] 3118; 3119; CHECK: [[LOOP_EXIT_A]]: 3120; CHECK-NEXT: %[[LCSSA_A:.*]] = phi i32 [ %[[TMP_C_SUM_A]], %[[LATCH_A]] ] 3121; CHECK-NEXT: br label %exit 3122 3123body.b: 3124 %tmp.b.phi = phi i32 [ %tmp, %dispatch ], [ %tmp.a.sum, %body.a ] 3125 %tmp.b = call i32 @b() 3126 %tmp.b.sum = add i32 %tmp.b.phi, %tmp.b 3127 br label %body.c 3128; Unswitched 'b' loop. 3129; 3130; CHECK: [[ENTRY_SPLIT_B]]: 3131; CHECK-NEXT: br label %[[HEADER_B:.*]] 3132; 3133; CHECK: [[HEADER_B]]: 3134; CHECK-NEXT: %[[TMP_B:.*]] = call i32 @d() 3135; CHECK-NEXT: %[[CMP1_B:.*]] = icmp eq i32 %[[TMP_B]], 0 3136; CHECK-NEXT: br i1 %[[CMP1_B]], label %[[BODY_A_B:.*]], label %[[DISPATCH_B:.*]] 3137; 3138; CHECK: [[DISPATCH_B]]: 3139; CHECK-NEXT: br label %[[BODY_B_B:.*]] 3140; 3141; CHECK: [[BODY_A_B]]: 3142; CHECK-NEXT: %[[TMP_A_PHI_B:.*]] = phi i32 [ 0, %[[HEADER_B]] ] 3143; CHECK-NEXT: %[[TMP_A_B:.*]] = call i32 @a() 3144; CHECK-NEXT: %[[TMP_A_SUM_B:.*]] = add i32 %[[TMP_A_PHI_B]], %[[TMP_A_B]] 3145; CHECK-NEXT: br label %[[BODY_B_B:.*]] 3146; 3147; CHECK: [[BODY_B_B]]: 3148; CHECK-NEXT: %[[TMP_B_PHI_B:.*]] = phi i32 [ %[[TMP_B]], %[[DISPATCH_B]] ], [ %[[TMP_A_SUM_B]], %[[BODY_A_B]] ] 3149; CHECK-NEXT: %[[TMP_B_B:.*]] = call i32 @b() 3150; CHECK-NEXT: %[[TMP_B_SUM_B:.*]] = add i32 %[[TMP_B_PHI_B]], %[[TMP_B_B]] 3151; CHECK-NEXT: br label %[[BODY_C_B:.*]] 3152; 3153; CHECK: [[BODY_C_B]]: 3154; CHECK-NEXT: %[[TMP_C_PHI_B:.*]] = phi i32 [ %[[TMP_B_SUM_B]], %[[BODY_B_B]] ] 3155; CHECK-NEXT: %[[TMP_C_B:.*]] = call i32 @c() 3156; CHECK-NEXT: %[[TMP_C_SUM_B:.*]] = add i32 %[[TMP_C_PHI_B]], %[[TMP_C_B]] 3157; CHECK-NEXT: br label %[[LATCH_B:.*]] 3158; 3159; CHECK: [[LATCH_B]]: 3160; CHECK-NEXT: %[[CMP2_B:.*]] = icmp slt i32 %[[TMP_C_SUM_B]], 42 3161; CHECK: br i1 %[[CMP2_B]], label %[[HEADER_B]], label %[[LOOP_EXIT_B:.*]] 3162; 3163; CHECK: [[LOOP_EXIT_B]]: 3164; CHECK-NEXT: %[[LCSSA_B:.*]] = phi i32 [ %[[TMP_C_SUM_B]], %[[LATCH_B]] ] 3165; CHECK-NEXT: br label %[[EXIT_SPLIT:.*]] 3166 3167body.c: 3168 %tmp.c.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ], [ %tmp.b.sum, %body.b ] 3169 %tmp.c = call i32 @c() 3170 %tmp.c.sum = add i32 %tmp.c.phi, %tmp.c 3171 br label %latch 3172; Unswitched 'c' loop. 3173; 3174; CHECK: [[ENTRY_SPLIT_C]]: 3175; CHECK-NEXT: br label %[[HEADER_C:.*]] 3176; 3177; CHECK: [[HEADER_C]]: 3178; CHECK-NEXT: %[[TMP_C:.*]] = call i32 @d() 3179; CHECK-NEXT: %[[CMP1_C:.*]] = icmp eq i32 %[[TMP_C]], 0 3180; CHECK-NEXT: br i1 %[[CMP1_C]], label %[[BODY_A_C:.*]], label %[[DISPATCH_C:.*]] 3181; 3182; CHECK: [[DISPATCH_C]]: 3183; CHECK-NEXT: br label %[[BODY_C_C:.*]] 3184; 3185; CHECK: [[BODY_A_C]]: 3186; CHECK-NEXT: %[[TMP_A_PHI_C:.*]] = phi i32 [ 0, %[[HEADER_C]] ] 3187; CHECK-NEXT: %[[TMP_A_C:.*]] = call i32 @a() 3188; CHECK-NEXT: %[[TMP_A_SUM_C:.*]] = add i32 %[[TMP_A_PHI_C]], %[[TMP_A_C]] 3189; CHECK-NEXT: br label %[[BODY_B_C:.*]] 3190; 3191; CHECK: [[BODY_B_C]]: 3192; CHECK-NEXT: %[[TMP_B_PHI_C:.*]] = phi i32 [ %[[TMP_A_SUM_C]], %[[BODY_A_C]] ] 3193; CHECK-NEXT: %[[TMP_B_C:.*]] = call i32 @b() 3194; CHECK-NEXT: %[[TMP_B_SUM_C:.*]] = add i32 %[[TMP_B_PHI_C]], %[[TMP_B_C]] 3195; CHECK-NEXT: br label %[[BODY_C_C:.*]] 3196; 3197; CHECK: [[BODY_C_C]]: 3198; CHECK-NEXT: %[[TMP_C_PHI_C:.*]] = phi i32 [ %[[TMP_C]], %[[DISPATCH_C]] ], [ %[[TMP_B_SUM_C]], %[[BODY_B_C]] ] 3199; CHECK-NEXT: %[[TMP_C_C:.*]] = call i32 @c() 3200; CHECK-NEXT: %[[TMP_C_SUM_C:.*]] = add i32 %[[TMP_C_PHI_C]], %[[TMP_C_C]] 3201; CHECK-NEXT: br label %[[LATCH_C:.*]] 3202; 3203; CHECK: [[LATCH_C]]: 3204; CHECK-NEXT: %[[CMP2_C:.*]] = icmp slt i32 %[[TMP_C_SUM_C]], 42 3205; CHECK: br i1 %[[CMP2_C]], label %[[HEADER_C]], label %[[LOOP_EXIT_C:.*]] 3206; 3207; CHECK: [[LOOP_EXIT_C]]: 3208; CHECK-NEXT: %[[LCSSA_C:.*]] = phi i32 [ %[[TMP_C_SUM_C]], %[[LATCH_C]] ] 3209; CHECK-NEXT: br label %[[EXIT_SPLIT]] 3210 3211latch: 3212 %cmp2 = icmp slt i32 %tmp.c.sum, 42 3213 br i1 %cmp2, label %header, label %exit 3214 3215exit: 3216 %lcssa.phi = phi i32 [ %tmp.c.sum, %latch ] 3217 ret i32 %lcssa.phi 3218; CHECK: [[EXIT_SPLIT]]: 3219; CHECK-NEXT: %[[EXIT_PHI1:.*]] = phi i32 [ %[[LCSSA_C]], %[[LOOP_EXIT_C]] ], [ %[[LCSSA_B]], %[[LOOP_EXIT_B]] ] 3220; CHECK-NEXT: br label %exit 3221 3222; CHECK: exit: 3223; CHECK-NEXT: %[[EXIT_PHI2:.*]] = phi i32 [ %[[EXIT_PHI1]], %[[EXIT_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ] 3224; CHECK-NEXT: ret i32 %[[EXIT_PHI2]] 3225} 3226 3227; Similar to @test29 but designed to have one of the duplicate edges be 3228; a loop exit edge as those can in some cases be special. Among other things, 3229; this includes an LCSSA phi with multiple entries despite being a dedicated 3230; exit block. 3231define i32 @test30(i32 %arg) { 3232; CHECK-LABEL: define i32 @test30( 3233entry: 3234 br label %header 3235; CHECK-NEXT: entry: 3236; CHECK-NEXT: switch i32 %arg, label %[[ENTRY_SPLIT_EXIT:.*]] [ 3237; CHECK-NEXT: i32 -1, label %[[ENTRY_SPLIT_EXIT]] 3238; CHECK-NEXT: i32 0, label %[[ENTRY_SPLIT_A:.*]] 3239; CHECK-NEXT: i32 1, label %[[ENTRY_SPLIT_B:.*]] 3240; CHECK-NEXT: i32 2, label %[[ENTRY_SPLIT_B]] 3241; CHECK-NEXT: ] 3242 3243header: 3244 %tmp = call i32 @d() 3245 %cmp1 = icmp eq i32 %tmp, 0 3246 br i1 %cmp1, label %body.a, label %dispatch 3247 3248dispatch: 3249 switch i32 %arg, label %loop.exit1 [ 3250 i32 -1, label %loop.exit1 3251 i32 0, label %body.a 3252 i32 1, label %body.b 3253 i32 2, label %body.b 3254 ] 3255 3256body.a: 3257 %tmp.a.phi = phi i32 [ 0, %header ], [ %tmp, %dispatch ] 3258 %tmp.a = call i32 @a() 3259 %tmp.a.sum = add i32 %tmp.a.phi, %tmp.a 3260 br label %body.b 3261; Unswitched 'a' loop. 3262; 3263; CHECK: [[ENTRY_SPLIT_A]]: 3264; CHECK-NEXT: br label %[[HEADER_A:.*]] 3265; 3266; CHECK: [[HEADER_A]]: 3267; CHECK-NEXT: %[[TMP_A:.*]] = call i32 @d() 3268; CHECK-NEXT: %[[CMP1_A:.*]] = icmp eq i32 %[[TMP_A]], 0 3269; CHECK-NEXT: br i1 %[[CMP1_A]], label %[[BODY_A_A:.*]], label %[[DISPATCH_A:.*]] 3270; 3271; CHECK: [[DISPATCH_A]]: 3272; CHECK-NEXT: br label %[[BODY_A_A]] 3273; 3274; CHECK: [[BODY_A_A]]: 3275; CHECK-NEXT: %[[TMP_A_PHI_A:.*]] = phi i32 [ 0, %[[HEADER_A]] ], [ %[[TMP_A]], %[[DISPATCH_A]] ] 3276; CHECK-NEXT: %[[TMP_A_A:.*]] = call i32 @a() 3277; CHECK-NEXT: %[[TMP_A_SUM_A:.*]] = add i32 %[[TMP_A_PHI_A]], %[[TMP_A_A]] 3278; CHECK-NEXT: br label %[[BODY_B_A:.*]] 3279; 3280; CHECK: [[BODY_B_A]]: 3281; CHECK-NEXT: %[[TMP_B_PHI_A:.*]] = phi i32 [ %[[TMP_A_SUM_A]], %[[BODY_A_A]] ] 3282; CHECK-NEXT: %[[TMP_B_A:.*]] = call i32 @b() 3283; CHECK-NEXT: %[[TMP_B_SUM_A:.*]] = add i32 %[[TMP_B_PHI_A]], %[[TMP_B_A]] 3284; CHECK-NEXT: br label %[[LATCH_A:.*]] 3285; 3286; CHECK: [[LATCH_A]]: 3287; CHECK-NEXT: %[[CMP2_A:.*]] = icmp slt i32 %[[TMP_B_SUM_A]], 42 3288; CHECK: br i1 %[[CMP2_A]], label %[[HEADER_A]], label %[[LOOP_EXIT_A:.*]] 3289; 3290; CHECK: [[LOOP_EXIT_A]]: 3291; CHECK-NEXT: %[[LCSSA_A:.*]] = phi i32 [ %[[TMP_B_SUM_A]], %[[LATCH_A]] ] 3292; CHECK-NEXT: br label %loop.exit2 3293 3294body.b: 3295 %tmp.b.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ], [ %tmp.a.sum, %body.a ] 3296 %tmp.b = call i32 @b() 3297 %tmp.b.sum = add i32 %tmp.b.phi, %tmp.b 3298 br label %latch 3299; Unswitched 'b' loop. 3300; 3301; CHECK: [[ENTRY_SPLIT_B]]: 3302; CHECK-NEXT: br label %[[HEADER_B:.*]] 3303; 3304; CHECK: [[HEADER_B]]: 3305; CHECK-NEXT: %[[TMP_B:.*]] = call i32 @d() 3306; CHECK-NEXT: %[[CMP1_B:.*]] = icmp eq i32 %[[TMP_B]], 0 3307; CHECK-NEXT: br i1 %[[CMP1_B]], label %[[BODY_A_B:.*]], label %[[DISPATCH_B:.*]] 3308; 3309; CHECK: [[DISPATCH_B]]: 3310; CHECK-NEXT: br label %[[BODY_B_B]] 3311; 3312; CHECK: [[BODY_A_B]]: 3313; CHECK-NEXT: %[[TMP_A_PHI_B:.*]] = phi i32 [ 0, %[[HEADER_B]] ] 3314; CHECK-NEXT: %[[TMP_A_B:.*]] = call i32 @a() 3315; CHECK-NEXT: %[[TMP_A_SUM_B:.*]] = add i32 %[[TMP_A_PHI_B]], %[[TMP_A_B]] 3316; CHECK-NEXT: br label %[[BODY_B_B:.*]] 3317; 3318; CHECK: [[BODY_B_B]]: 3319; CHECK-NEXT: %[[TMP_B_PHI_B:.*]] = phi i32 [ %[[TMP_B]], %[[DISPATCH_B]] ], [ %[[TMP_A_SUM_B]], %[[BODY_A_B]] ] 3320; CHECK-NEXT: %[[TMP_B_B:.*]] = call i32 @b() 3321; CHECK-NEXT: %[[TMP_B_SUM_B:.*]] = add i32 %[[TMP_B_PHI_B]], %[[TMP_B_B]] 3322; CHECK-NEXT: br label %[[LATCH_B:.*]] 3323; 3324; CHECK: [[LATCH_B]]: 3325; CHECK-NEXT: %[[CMP2_B:.*]] = icmp slt i32 %[[TMP_B_SUM_B]], 42 3326; CHECK: br i1 %[[CMP2_B]], label %[[HEADER_B]], label %[[LOOP_EXIT_B:.*]] 3327; 3328; CHECK: [[LOOP_EXIT_B]]: 3329; CHECK-NEXT: %[[LCSSA_B:.*]] = phi i32 [ %[[TMP_B_SUM_B]], %[[LATCH_B]] ] 3330; CHECK-NEXT: br label %[[LOOP_EXIT2_SPLIT:.*]] 3331 3332latch: 3333 %cmp2 = icmp slt i32 %tmp.b.sum, 42 3334 br i1 %cmp2, label %header, label %loop.exit2 3335 3336loop.exit1: 3337 %l1.phi = phi i32 [ %tmp, %dispatch ], [ %tmp, %dispatch ] 3338 br label %exit 3339; Unswitched 'exit' loop. 3340; 3341; CHECK: [[ENTRY_SPLIT_EXIT]]: 3342; CHECK-NEXT: br label %[[HEADER_EXIT:.*]] 3343; 3344; CHECK: [[HEADER_EXIT]]: 3345; CHECK-NEXT: %[[TMP_EXIT:.*]] = call i32 @d() 3346; CHECK-NEXT: %[[CMP1_EXIT:.*]] = icmp eq i32 %[[TMP_EXIT]], 0 3347; CHECK-NEXT: br i1 %[[CMP1_EXIT]], label %[[BODY_A_EXIT:.*]], label %[[DISPATCH_EXIT:.*]] 3348; 3349; CHECK: [[DISPATCH_EXIT]]: 3350; CHECK-NEXT: %[[TMP_LCSSA:.*]] = phi i32 [ %[[TMP_EXIT]], %[[HEADER_EXIT]] ] 3351; CHECK-NEXT: br label %loop.exit1 3352; 3353; CHECK: [[BODY_A_EXIT]]: 3354; CHECK-NEXT: %[[TMP_A_PHI_EXIT:.*]] = phi i32 [ 0, %[[HEADER_EXIT]] ] 3355; CHECK-NEXT: %[[TMP_A_EXIT:.*]] = call i32 @a() 3356; CHECK-NEXT: %[[TMP_A_SUM_EXIT:.*]] = add i32 %[[TMP_A_PHI_EXIT]], %[[TMP_A_EXIT]] 3357; CHECK-NEXT: br label %[[BODY_B_EXIT:.*]] 3358; 3359; CHECK: [[BODY_B_EXIT]]: 3360; CHECK-NEXT: %[[TMP_B_PHI_EXIT:.*]] = phi i32 [ %[[TMP_A_SUM_EXIT]], %[[BODY_A_EXIT]] ] 3361; CHECK-NEXT: %[[TMP_B_EXIT:.*]] = call i32 @b() 3362; CHECK-NEXT: %[[TMP_B_SUM_EXIT:.*]] = add i32 %[[TMP_B_PHI_EXIT]], %[[TMP_B_EXIT]] 3363; CHECK-NEXT: br label %[[LATCH_EXIT:.*]] 3364; 3365; CHECK: [[LATCH_EXIT]]: 3366; CHECK-NEXT: %[[CMP2_EXIT:.*]] = icmp slt i32 %[[TMP_B_SUM_EXIT]], 42 3367; CHECK: br i1 %[[CMP2_EXIT]], label %[[HEADER_EXIT]], label %[[LOOP_EXIT_EXIT:.*]] 3368; 3369; CHECK: loop.exit1: 3370; CHECK-NEXT: %[[L1_PHI:.*]] = phi i32 [ %[[TMP_LCSSA]], %[[DISPATCH_EXIT]] ] 3371; CHECK-NEXT: br label %exit 3372; 3373; CHECK: [[LOOP_EXIT_EXIT]]: 3374; CHECK-NEXT: %[[L2_PHI:.*]] = phi i32 [ %[[TMP_B_SUM_EXIT]], %[[LATCH_EXIT]] ] 3375; CHECK-NEXT: br label %[[LOOP_EXIT2_SPLIT]] 3376 3377loop.exit2: 3378 %l2.phi = phi i32 [ %tmp.b.sum, %latch ] 3379 br label %exit 3380; CHECK: [[LOOP_EXIT2_SPLIT]]: 3381; CHECK-NEXT: %[[LOOP_EXIT_PHI1:.*]] = phi i32 [ %[[L2_PHI]], %[[LOOP_EXIT_EXIT]] ], [ %[[LCSSA_B]], %[[LOOP_EXIT_B]] ] 3382; CHECK-NEXT: br label %loop.exit2 3383; 3384; CHECK: loop.exit2: 3385; CHECK-NEXT: %[[LOOP_EXIT_PHI2:.*]] = phi i32 [ %[[LOOP_EXIT_PHI1]], %[[LOOP_EXIT2_SPLIT]] ], [ %[[LCSSA_A]], %[[LOOP_EXIT_A]] ] 3386; CHECK-NEXT: br label %exit 3387 3388exit: 3389 %l.phi = phi i32 [ %l1.phi, %loop.exit1 ], [ %l2.phi, %loop.exit2 ] 3390 ret i32 %l.phi 3391; CHECK: exit: 3392; CHECK-NEXT: %[[EXIT_PHI:.*]] = phi i32 [ %[[L1_PHI]], %loop.exit1 ], [ %[[LOOP_EXIT_PHI2]], %loop.exit2 ] 3393; CHECK-NEXT: ret i32 %[[EXIT_PHI]] 3394} 3395 3396; Unswitch will not actually change the loop nest from: 3397; A < B < C 3398define void @hoist_inner_loop0() { 3399; CHECK-LABEL: define void @hoist_inner_loop0( 3400entry: 3401 br label %a.header 3402; CHECK: entry: 3403; CHECK-NEXT: br label %a.header 3404 3405a.header: 3406 br label %b.header 3407; CHECK: a.header: 3408; CHECK-NEXT: br label %b.header 3409 3410b.header: 3411 %v1 = call i1 @cond() 3412 br label %c.header 3413; CHECK: b.header: 3414; CHECK-NEXT: %v1 = call i1 @cond() 3415; CHECK-NEXT: br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]] 3416; 3417; CHECK: [[B_HEADER_SPLIT_US]]: 3418; CHECK-NEXT: br label %[[C_HEADER_US:.*]] 3419; 3420; CHECK: [[C_HEADER_US]]: 3421; CHECK-NEXT: call i32 @c() 3422; CHECK-NEXT: br label %[[B_LATCH_SPLIT_US:.*]] 3423; 3424; CHECK: [[B_LATCH_SPLIT_US]]: 3425; CHECK-NEXT: br label %b.latch 3426; 3427; CHECK: [[B_HEADER_SPLIT]]: 3428; CHECK-NEXT: br label %c.header 3429 3430c.header: 3431 call i32 @c() 3432 br i1 %v1, label %b.latch, label %c.latch 3433; CHECK: c.header: 3434; CHECK-NEXT: call i32 @c() 3435; CHECK-NEXT: br label %c.latch 3436 3437c.latch: 3438 %v2 = call i1 @cond() 3439 br i1 %v2, label %c.header, label %b.latch 3440; CHECK: c.latch: 3441; CHECK-NEXT: %v2 = call i1 @cond() 3442; CHECK-NEXT: br i1 %v2, label %c.header, label %[[B_LATCH_SPLIT:.*]] 3443 3444b.latch: 3445 %v3 = call i1 @cond() 3446 br i1 %v3, label %b.header, label %a.latch 3447; CHECK: [[B_LATCH_SPLIT]]: 3448; CHECK-NEXT: br label %b.latch 3449; 3450; CHECK: b.latch: 3451; CHECK-NEXT: %v3 = call i1 @cond() 3452; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch 3453 3454a.latch: 3455 br label %a.header 3456; CHECK: a.latch: 3457; CHECK-NEXT: br label %a.header 3458 3459exit: 3460 ret void 3461; CHECK: exit: 3462; CHECK-NEXT: ret void 3463} 3464 3465; Unswitch will transform the loop nest from: 3466; A < B < C 3467; into 3468; A < (B, C) 3469define void @hoist_inner_loop1(i32* %ptr) { 3470; CHECK-LABEL: define void @hoist_inner_loop1( 3471entry: 3472 br label %a.header 3473; CHECK: entry: 3474; CHECK-NEXT: br label %a.header 3475 3476a.header: 3477 %x.a = load i32, i32* %ptr 3478 br label %b.header 3479; CHECK: a.header: 3480; CHECK-NEXT: %x.a = load i32, i32* %ptr 3481; CHECK-NEXT: br label %b.header 3482 3483b.header: 3484 %x.b = load i32, i32* %ptr 3485 %v1 = call i1 @cond() 3486 br label %c.header 3487; CHECK: b.header: 3488; CHECK-NEXT: %x.b = load i32, i32* %ptr 3489; CHECK-NEXT: %v1 = call i1 @cond() 3490; CHECK-NEXT: br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]] 3491; 3492; CHECK: [[B_HEADER_SPLIT_US]]: 3493; CHECK-NEXT: br label %[[C_HEADER_US:.*]] 3494; 3495; CHECK: [[C_HEADER_US]]: 3496; CHECK-NEXT: call i32 @c() 3497; CHECK-NEXT: br label %[[B_LATCH_US:.*]] 3498; 3499; CHECK: [[B_LATCH_US]]: 3500; CHECK-NEXT: br label %b.latch 3501; 3502; CHECK: [[B_HEADER_SPLIT]]: 3503; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] 3504; CHECK-NEXT: br label %c.header 3505 3506c.header: 3507 call i32 @c() 3508 br i1 %v1, label %b.latch, label %c.latch 3509; CHECK: c.header: 3510; CHECK-NEXT: call i32 @c() 3511; CHECK-NEXT: br label %c.latch 3512 3513c.latch: 3514 ; Use values from other loops to check LCSSA form. 3515 store i32 %x.a, i32* %ptr 3516 store i32 %x.b, i32* %ptr 3517 %v2 = call i1 @cond() 3518 br i1 %v2, label %c.header, label %a.exit.c 3519; CHECK: c.latch: 3520; CHECK-NEXT: store i32 %x.a, i32* %ptr 3521; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr 3522; CHECK-NEXT: %v2 = call i1 @cond() 3523; CHECK-NEXT: br i1 %v2, label %c.header, label %a.exit.c 3524 3525b.latch: 3526 %v3 = call i1 @cond() 3527 br i1 %v3, label %b.header, label %a.exit.b 3528; CHECK: b.latch: 3529; CHECK-NEXT: %v3 = call i1 @cond() 3530; CHECK-NEXT: br i1 %v3, label %b.header, label %a.exit.b 3531 3532a.exit.c: 3533 br label %a.latch 3534; CHECK: a.exit.c 3535; CHECK-NEXT: br label %a.latch 3536 3537a.exit.b: 3538 br label %a.latch 3539; CHECK: a.exit.b: 3540; CHECK-NEXT: br label %a.latch 3541 3542a.latch: 3543 br label %a.header 3544; CHECK: a.latch: 3545; CHECK-NEXT: br label %a.header 3546 3547exit: 3548 ret void 3549; CHECK: exit: 3550; CHECK-NEXT: ret void 3551} 3552 3553; Unswitch will transform the loop nest from: 3554; A < B < C 3555; into 3556; (A < B), C 3557define void @hoist_inner_loop2(i32* %ptr) { 3558; CHECK-LABEL: define void @hoist_inner_loop2( 3559entry: 3560 br label %a.header 3561; CHECK: entry: 3562; CHECK-NEXT: br label %a.header 3563 3564a.header: 3565 %x.a = load i32, i32* %ptr 3566 br label %b.header 3567; CHECK: a.header: 3568; CHECK-NEXT: %x.a = load i32, i32* %ptr 3569; CHECK-NEXT: br label %b.header 3570 3571b.header: 3572 %x.b = load i32, i32* %ptr 3573 %v1 = call i1 @cond() 3574 br label %c.header 3575; CHECK: b.header: 3576; CHECK-NEXT: %x.b = load i32, i32* %ptr 3577; CHECK-NEXT: %v1 = call i1 @cond() 3578; CHECK-NEXT: br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]] 3579; 3580; CHECK: [[B_HEADER_SPLIT_US]]: 3581; CHECK-NEXT: br label %[[C_HEADER_US:.*]] 3582; 3583; CHECK: [[C_HEADER_US]]: 3584; CHECK-NEXT: call i32 @c() 3585; CHECK-NEXT: br label %[[B_LATCH_US:.*]] 3586; 3587; CHECK: [[B_LATCH_US]]: 3588; CHECK-NEXT: br label %b.latch 3589; 3590; CHECK: [[B_HEADER_SPLIT]]: 3591; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] 3592; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] 3593; CHECK-NEXT: br label %c.header 3594 3595c.header: 3596 call i32 @c() 3597 br i1 %v1, label %b.latch, label %c.latch 3598; CHECK: c.header: 3599; CHECK-NEXT: call i32 @c() 3600; CHECK-NEXT: br label %c.latch 3601 3602c.latch: 3603 ; Use values from other loops to check LCSSA form. 3604 store i32 %x.a, i32* %ptr 3605 store i32 %x.b, i32* %ptr 3606 %v2 = call i1 @cond() 3607 br i1 %v2, label %c.header, label %exit 3608; CHECK: c.latch: 3609; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr 3610; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr 3611; CHECK-NEXT: %v2 = call i1 @cond() 3612; CHECK-NEXT: br i1 %v2, label %c.header, label %exit 3613 3614b.latch: 3615 %v3 = call i1 @cond() 3616 br i1 %v3, label %b.header, label %a.latch 3617; CHECK: b.latch: 3618; CHECK-NEXT: %v3 = call i1 @cond() 3619; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch 3620 3621a.latch: 3622 br label %a.header 3623; CHECK: a.latch: 3624; CHECK-NEXT: br label %a.header 3625 3626exit: 3627 ret void 3628; CHECK: exit: 3629; CHECK-NEXT: ret void 3630} 3631 3632; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop. 3633; Unswitch will transform the loop nest from: 3634; A < B < C < D 3635; into 3636; (A < B), (C < D) 3637define void @hoist_inner_loop3(i32* %ptr) { 3638; CHECK-LABEL: define void @hoist_inner_loop3( 3639entry: 3640 br label %a.header 3641; CHECK: entry: 3642; CHECK-NEXT: br label %a.header 3643 3644a.header: 3645 %x.a = load i32, i32* %ptr 3646 br label %b.header 3647; CHECK: a.header: 3648; CHECK-NEXT: %x.a = load i32, i32* %ptr 3649; CHECK-NEXT: br label %b.header 3650 3651b.header: 3652 %x.b = load i32, i32* %ptr 3653 %v1 = call i1 @cond() 3654 br label %c.header 3655; CHECK: b.header: 3656; CHECK-NEXT: %x.b = load i32, i32* %ptr 3657; CHECK-NEXT: %v1 = call i1 @cond() 3658; CHECK-NEXT: br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]] 3659; 3660; CHECK: [[B_HEADER_SPLIT_US]]: 3661; CHECK-NEXT: br label %[[C_HEADER_US:.*]] 3662; 3663; CHECK: [[C_HEADER_US]]: 3664; CHECK-NEXT: call i32 @c() 3665; CHECK-NEXT: br label %[[B_LATCH_US:.*]] 3666; 3667; CHECK: [[B_LATCH_US]]: 3668; CHECK-NEXT: br label %b.latch 3669; 3670; CHECK: [[B_HEADER_SPLIT]]: 3671; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] 3672; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] 3673; CHECK-NEXT: br label %c.header 3674 3675c.header: 3676 call i32 @c() 3677 br i1 %v1, label %b.latch, label %c.body 3678; CHECK: c.header: 3679; CHECK-NEXT: call i32 @c() 3680; CHECK-NEXT: br label %c.body 3681 3682c.body: 3683 %x.c = load i32, i32* %ptr 3684 br label %d.header 3685; CHECK: c.body: 3686; CHECK-NEXT: %x.c = load i32, i32* %ptr 3687; CHECK-NEXT: br label %d.header 3688 3689d.header: 3690 ; Use values from other loops to check LCSSA form. 3691 store i32 %x.a, i32* %ptr 3692 store i32 %x.b, i32* %ptr 3693 store i32 %x.c, i32* %ptr 3694 %v2 = call i1 @cond() 3695 br i1 %v2, label %d.header, label %c.latch 3696; CHECK: d.header: 3697; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr 3698; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr 3699; CHECK-NEXT: store i32 %x.c, i32* %ptr 3700; CHECK-NEXT: %v2 = call i1 @cond() 3701; CHECK-NEXT: br i1 %v2, label %d.header, label %c.latch 3702 3703c.latch: 3704 %v3 = call i1 @cond() 3705 br i1 %v3, label %c.header, label %exit 3706; CHECK: c.latch: 3707; CHECK-NEXT: %v3 = call i1 @cond() 3708; CHECK-NEXT: br i1 %v3, label %c.header, label %exit 3709 3710b.latch: 3711 %v4 = call i1 @cond() 3712 br i1 %v4, label %b.header, label %a.latch 3713; CHECK: b.latch: 3714; CHECK-NEXT: %v4 = call i1 @cond() 3715; CHECK-NEXT: br i1 %v4, label %b.header, label %a.latch 3716 3717a.latch: 3718 br label %a.header 3719; CHECK: a.latch: 3720; CHECK-NEXT: br label %a.header 3721 3722exit: 3723 ret void 3724; CHECK: exit: 3725; CHECK-NEXT: ret void 3726} 3727 3728; This test is designed to exercise checking multiple remaining exits from the 3729; loop being unswitched. 3730; Unswitch will transform the loop nest from: 3731; A < B < C < D 3732; into 3733; A < B < (C, D) 3734define void @hoist_inner_loop4() { 3735; CHECK-LABEL: define void @hoist_inner_loop4( 3736entry: 3737 br label %a.header 3738; CHECK: entry: 3739; CHECK-NEXT: br label %a.header 3740 3741a.header: 3742 br label %b.header 3743; CHECK: a.header: 3744; CHECK-NEXT: br label %b.header 3745 3746b.header: 3747 br label %c.header 3748; CHECK: b.header: 3749; CHECK-NEXT: br label %c.header 3750 3751c.header: 3752 %v1 = call i1 @cond() 3753 br label %d.header 3754; CHECK: c.header: 3755; CHECK-NEXT: %v1 = call i1 @cond() 3756; CHECK-NEXT: br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]] 3757; 3758; CHECK: [[C_HEADER_SPLIT_US]]: 3759; CHECK-NEXT: br label %[[D_HEADER_US:.*]] 3760; 3761; CHECK: [[D_HEADER_US]]: 3762; CHECK-NEXT: call i32 @d() 3763; CHECK-NEXT: br label %[[C_LATCH_US:.*]] 3764; 3765; CHECK: [[C_LATCH_US]]: 3766; CHECK-NEXT: br label %c.latch 3767; 3768; CHECK: [[C_HEADER_SPLIT]]: 3769; CHECK-NEXT: br label %d.header 3770 3771d.header: 3772 call i32 @d() 3773 br i1 %v1, label %c.latch, label %d.exiting1 3774; CHECK: d.header: 3775; CHECK-NEXT: call i32 @d() 3776; CHECK-NEXT: br label %d.exiting1 3777 3778d.exiting1: 3779 %v2 = call i1 @cond() 3780 br i1 %v2, label %d.exiting2, label %a.latch 3781; CHECK: d.exiting1: 3782; CHECK-NEXT: %v2 = call i1 @cond() 3783; CHECK-NEXT: br i1 %v2, label %d.exiting2, label %a.latch 3784 3785d.exiting2: 3786 %v3 = call i1 @cond() 3787 br i1 %v3, label %d.exiting3, label %loopexit.d 3788; CHECK: d.exiting2: 3789; CHECK-NEXT: %v3 = call i1 @cond() 3790; CHECK-NEXT: br i1 %v3, label %d.exiting3, label %loopexit.d 3791 3792d.exiting3: 3793 %v4 = call i1 @cond() 3794 br i1 %v4, label %d.latch, label %b.latch 3795; CHECK: d.exiting3: 3796; CHECK-NEXT: %v4 = call i1 @cond() 3797; CHECK-NEXT: br i1 %v4, label %d.latch, label %b.latch 3798 3799d.latch: 3800 br label %d.header 3801; CHECK: d.latch: 3802; CHECK-NEXT: br label %d.header 3803 3804c.latch: 3805 %v5 = call i1 @cond() 3806 br i1 %v5, label %c.header, label %loopexit.c 3807; CHECK: c.latch: 3808; CHECK-NEXT: %v5 = call i1 @cond() 3809; CHECK-NEXT: br i1 %v5, label %c.header, label %loopexit.c 3810 3811b.latch: 3812 br label %b.header 3813; CHECK: b.latch: 3814; CHECK-NEXT: br label %b.header 3815 3816a.latch: 3817 br label %a.header 3818; CHECK: a.latch: 3819; CHECK-NEXT: br label %a.header 3820 3821loopexit.d: 3822 br label %exit 3823; CHECK: loopexit.d: 3824; CHECK-NEXT: br label %exit 3825 3826loopexit.c: 3827 br label %exit 3828; CHECK: loopexit.c: 3829; CHECK-NEXT: br label %exit 3830 3831exit: 3832 ret void 3833; CHECK: exit: 3834; CHECK-NEXT: ret void 3835} 3836 3837; Unswitch will transform the loop nest from: 3838; A < B < C < D 3839; into 3840; A < ((B < C), D) 3841define void @hoist_inner_loop5(i32* %ptr) { 3842; CHECK-LABEL: define void @hoist_inner_loop5( 3843entry: 3844 br label %a.header 3845; CHECK: entry: 3846; CHECK-NEXT: br label %a.header 3847 3848a.header: 3849 %x.a = load i32, i32* %ptr 3850 br label %b.header 3851; CHECK: a.header: 3852; CHECK-NEXT: %x.a = load i32, i32* %ptr 3853; CHECK-NEXT: br label %b.header 3854 3855b.header: 3856 %x.b = load i32, i32* %ptr 3857 br label %c.header 3858; CHECK: b.header: 3859; CHECK-NEXT: %x.b = load i32, i32* %ptr 3860; CHECK-NEXT: br label %c.header 3861 3862c.header: 3863 %x.c = load i32, i32* %ptr 3864 %v1 = call i1 @cond() 3865 br label %d.header 3866; CHECK: c.header: 3867; CHECK-NEXT: %x.c = load i32, i32* %ptr 3868; CHECK-NEXT: %v1 = call i1 @cond() 3869; CHECK-NEXT: br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]] 3870; 3871; CHECK: [[C_HEADER_SPLIT_US]]: 3872; CHECK-NEXT: br label %[[D_HEADER_US:.*]] 3873; 3874; CHECK: [[D_HEADER_US]]: 3875; CHECK-NEXT: call i32 @d() 3876; CHECK-NEXT: br label %[[C_LATCH_US:.*]] 3877; 3878; CHECK: [[C_LATCH_US]]: 3879; CHECK-NEXT: br label %c.latch 3880; 3881; CHECK: [[C_HEADER_SPLIT]]: 3882; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ] 3883; CHECK-NEXT: %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ] 3884; CHECK-NEXT: br label %d.header 3885 3886d.header: 3887 call i32 @d() 3888 br i1 %v1, label %c.latch, label %d.latch 3889; CHECK: d.header: 3890; CHECK-NEXT: call i32 @d() 3891; CHECK-NEXT: br label %d.latch 3892 3893d.latch: 3894 ; Use values from other loops to check LCSSA form. 3895 store i32 %x.a, i32* %ptr 3896 store i32 %x.b, i32* %ptr 3897 store i32 %x.c, i32* %ptr 3898 %v2 = call i1 @cond() 3899 br i1 %v2, label %d.header, label %a.latch 3900; CHECK: d.latch: 3901; CHECK-NEXT: store i32 %x.a, i32* %ptr 3902; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr 3903; CHECK-NEXT: store i32 %[[X_C_LCSSA]], i32* %ptr 3904; CHECK-NEXT: %v2 = call i1 @cond() 3905; CHECK-NEXT: br i1 %v2, label %d.header, label %a.latch 3906 3907c.latch: 3908 %v3 = call i1 @cond() 3909 br i1 %v3, label %c.header, label %b.latch 3910; CHECK: c.latch: 3911; CHECK-NEXT: %v3 = call i1 @cond() 3912; CHECK-NEXT: br i1 %v3, label %c.header, label %b.latch 3913 3914b.latch: 3915 br label %b.header 3916; CHECK: b.latch: 3917; CHECK-NEXT: br label %b.header 3918 3919a.latch: 3920 br label %a.header 3921; CHECK: a.latch: 3922; CHECK-NEXT: br label %a.header 3923 3924exit: 3925 ret void 3926; CHECK: exit: 3927; CHECK-NEXT: ret void 3928} 3929 3930define void @hoist_inner_loop_switch(i32* %ptr) { 3931; CHECK-LABEL: define void @hoist_inner_loop_switch( 3932entry: 3933 br label %a.header 3934; CHECK: entry: 3935; CHECK-NEXT: br label %a.header 3936 3937a.header: 3938 %x.a = load i32, i32* %ptr 3939 br label %b.header 3940; CHECK: a.header: 3941; CHECK-NEXT: %x.a = load i32, i32* %ptr 3942; CHECK-NEXT: br label %b.header 3943 3944b.header: 3945 %x.b = load i32, i32* %ptr 3946 %v1 = call i32 @cond.i32() 3947 br label %c.header 3948; CHECK: b.header: 3949; CHECK-NEXT: %x.b = load i32, i32* %ptr 3950; CHECK-NEXT: %v1 = call i32 @cond.i32() 3951; CHECK-NEXT: switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [ 3952; CHECK-NEXT: i32 1, label %[[B_HEADER_SPLIT_US:.*]] 3953; CHECK-NEXT: i32 2, label %[[B_HEADER_SPLIT_US]] 3954; CHECK-NEXT: i32 3, label %[[B_HEADER_SPLIT_US]] 3955; CHECK-NEXT: ] 3956; 3957; CHECK: [[B_HEADER_SPLIT_US]]: 3958; CHECK-NEXT: br label %[[C_HEADER_US:.*]] 3959; 3960; CHECK: [[C_HEADER_US]]: 3961; CHECK-NEXT: call i32 @c() 3962; CHECK-NEXT: br label %[[B_LATCH_US:.*]] 3963; 3964; CHECK: [[B_LATCH_US]]: 3965; CHECK-NEXT: br label %b.latch 3966; 3967; CHECK: [[B_HEADER_SPLIT]]: 3968; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] 3969; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] 3970; CHECK-NEXT: br label %c.header 3971 3972c.header: 3973 call i32 @c() 3974 switch i32 %v1, label %c.latch [ 3975 i32 1, label %b.latch 3976 i32 2, label %b.latch 3977 i32 3, label %b.latch 3978 ] 3979; CHECK: c.header: 3980; CHECK-NEXT: call i32 @c() 3981; CHECK-NEXT: br label %c.latch 3982 3983c.latch: 3984 ; Use values from other loops to check LCSSA form. 3985 store i32 %x.a, i32* %ptr 3986 store i32 %x.b, i32* %ptr 3987 %v2 = call i1 @cond() 3988 br i1 %v2, label %c.header, label %exit 3989; CHECK: c.latch: 3990; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr 3991; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr 3992; CHECK-NEXT: %v2 = call i1 @cond() 3993; CHECK-NEXT: br i1 %v2, label %c.header, label %exit 3994 3995b.latch: 3996 %v3 = call i1 @cond() 3997 br i1 %v3, label %b.header, label %a.latch 3998; CHECK: b.latch: 3999; CHECK-NEXT: %v3 = call i1 @cond() 4000; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch 4001 4002a.latch: 4003 br label %a.header 4004; CHECK: a.latch: 4005; CHECK-NEXT: br label %a.header 4006 4007exit: 4008 ret void 4009; CHECK: exit: 4010; CHECK-NEXT: ret void 4011} 4012 4013; A devilish pattern. This is a crafty, crafty test case designed to risk 4014; creating indirect cycles with trivial and non-trivial unswitching. The inner 4015; loop has a switch with a trivial exit edge that can be unswitched, but the 4016; rest of the switch cannot be unswitched because its cost is too high. 4017; However, the unswitching of the trivial edge creates a new switch in the 4018; outer loop. *This* switch isn't trivial, but has a low cost to unswitch. When 4019; we unswitch this switch from the outer loop, we will remove it completely and 4020; create a clone of the inner loop on one side. This clone will then again be 4021; viable for unswitching the inner-most loop. This lets us check that the 4022; unswitching doesn't end up cycling infinitely even when the cycle is 4023; indirect and due to revisiting a loop after cloning. 4024define void @test31(i32 %arg) { 4025; CHECK-LABEL: define void @test31( 4026entry: 4027 br label %outer.header 4028; CHECK-NEXT: entry: 4029; CHECK-NEXT: switch i32 %arg, label %[[ENTRY_SPLIT:.*]] [ 4030; CHECK-NEXT: i32 1, label %[[ENTRY_SPLIT_US:.*]] 4031; CHECK-NEXT: i32 2, label %[[ENTRY_SPLIT_US]] 4032; CHECK-NEXT: ] 4033; 4034; CHECK: [[ENTRY_SPLIT_US]]: 4035; CHECK-NEXT: switch i32 %arg, label %[[ENTRY_SPLIT_US_SPLIT:.*]] [ 4036; CHECK-NEXT: i32 1, label %[[ENTRY_SPLIT_US_SPLIT_US:.*]] 4037; CHECK-NEXT: ] 4038 4039outer.header: 4040 br label %inner.header 4041 4042inner.header: 4043 switch i32 %arg, label %inner.loopexit1 [ 4044 i32 1, label %inner.body1 4045 i32 2, label %inner.body2 4046 ] 4047 4048inner.body1: 4049 %a = call i32 @a() 4050 br label %inner.latch 4051; The (super convoluted) fully unswitched loop around `@a`. 4052; 4053; CHECK: [[ENTRY_SPLIT_US_SPLIT_US]]: 4054; CHECK-NEXT: br label %[[OUTER_HEADER_US_US:.*]] 4055; 4056; CHECK: [[OUTER_HEADER_US_US]]: 4057; CHECK-NEXT: br label %[[OUTER_HEADER_SPLIT_US_US:.*]] 4058; 4059; CHECK: [[OUTER_LATCH_US_US:.*]]: 4060; CHECK-NEXT: %[[OUTER_COND_US_US:.*]] = call i1 @cond() 4061; CHECK-NEXT: br i1 %[[OUTER_COND_US_US]], label %[[OUTER_HEADER_US_US]], label %[[EXIT_SPLIT_US_SPLIT_US:.*]] 4062; 4063; CHECK: [[OUTER_HEADER_SPLIT_US_US]]: 4064; CHECK-NEXT: br label %[[OUTER_HEADER_SPLIT_SPLIT_US_US_US:.*]] 4065; 4066; CHECK: [[INNER_LOOPEXIT2_US_US:.*]]: 4067; CHECK-NEXT: br label %[[OUTER_LATCH_US_US]] 4068; 4069; CHECK: [[OUTER_HEADER_SPLIT_SPLIT_US_US_US]]: 4070; CHECK-NEXT: br label %[[INNER_HEADER_US_US_US:.*]] 4071; 4072; CHECK: [[INNER_HEADER_US_US_US]]: 4073; CHECK-NEXT: br label %[[INNER_BODY1_US_US_US:.*]] 4074; 4075; CHECK: [[INNER_BODY1_US_US_US]]: 4076; CHECK-NEXT: %[[A:.*]] = call i32 @a() 4077; CHECK-NEXT: br label %[[INNER_LATCH_US_US_US:.*]] 4078; 4079; CHECK: [[INNER_LATCH_US_US_US]]: 4080; CHECK-NEXT: %[[PHI_A:.*]] = phi i32 [ %[[A]], %[[INNER_BODY1_US_US_US]] ] 4081; CHECK-NEXT: call void @sink1(i32 0) 4082; CHECK-NEXT: call void @sink1(i32 0) 4083; CHECK-NEXT: call void @sink1(i32 0) 4084; CHECK-NEXT: call void @sink1(i32 0) 4085; CHECK-NEXT: call void @sink1(i32 0) 4086; CHECK-NEXT: call void @sink1(i32 0) 4087; CHECK-NEXT: call void @sink1(i32 0) 4088; CHECK-NEXT: call void @sink1(i32 0) 4089; CHECK-NEXT: call void @sink1(i32 0) 4090; CHECK-NEXT: call void @sink1(i32 0) 4091; CHECK-NEXT: call void @sink1(i32 %[[PHI_A]]) 4092; CHECK-NEXT: %[[INNER_COND_US_US_US:.*]] = call i1 @cond() 4093; CHECK-NEXT: br i1 %[[INNER_COND_US_US_US]], label %[[INNER_HEADER_US_US_US]], label %[[INNER_LOOPEXIT2_SPLIT_US_US_US:.*]] 4094; 4095; CHECK: [[INNER_LOOPEXIT2_SPLIT_US_US_US]]: 4096; CHECK-NEXT: br label %[[INNER_LOOPEXIT2_US_US]] 4097; 4098; CHECK: [[EXIT_SPLIT_US_SPLIT_US]]: 4099; CHECK-NEXT: br label %[[EXIT_SPLIT_US:.*]] 4100 4101 4102inner.body2: 4103 %b = call i32 @b() 4104 br label %inner.latch 4105; The fully unswitched loop around `@b`. 4106; 4107; CHECK: [[ENTRY_SPLIT_US_SPLIT]]: 4108; CHECK-NEXT: br label %[[OUTER_HEADER_US:.*]] 4109; 4110; CHECK: [[OUTER_HEADER_US]]: 4111; CHECK-NEXT: br label %[[OUTER_HEADER_SPLIT_US:.*]] 4112; 4113; CHECK: [[INNER_HEADER_US:.*]]: 4114; CHECK-NEXT: br label %[[INNER_BODY2_US:.*]] 4115; 4116; CHECK: [[INNER_BODY2_US]]: 4117; CHECK-NEXT: %[[B:.*]] = call i32 @b() 4118; CHECK-NEXT: br label %[[INNER_LATCH_US:.*]] 4119; 4120; CHECK: [[INNER_LATCH_US]]: 4121; CHECK-NEXT: call void @sink1(i32 0) 4122; CHECK-NEXT: call void @sink1(i32 0) 4123; CHECK-NEXT: call void @sink1(i32 0) 4124; CHECK-NEXT: call void @sink1(i32 0) 4125; CHECK-NEXT: call void @sink1(i32 0) 4126; CHECK-NEXT: call void @sink1(i32 0) 4127; CHECK-NEXT: call void @sink1(i32 0) 4128; CHECK-NEXT: call void @sink1(i32 0) 4129; CHECK-NEXT: call void @sink1(i32 0) 4130; CHECK-NEXT: call void @sink1(i32 0) 4131; CHECK-NEXT: call void @sink1(i32 %[[B]]) 4132; CHECK-NEXT: %[[INNER_COND_US:.*]] = call i1 @cond() 4133; CHECK-NEXT: br i1 %[[INNER_COND_US]], label %[[INNER_HEADER_US]], label %[[INNER_LOOPEXIT2_SPLIT_US:.*]] 4134; 4135; CHECK: [[INNER_LOOPEXIT2_SPLIT_US]]: 4136; CHECK-NEXT: br label %[[INNER_LOOPEXIT2_US:.*]] 4137; 4138; CHECK: [[OUTER_LATCH_US:.*]]: 4139; CHECK-NEXT: %[[OUTER_COND_US:.*]] = call i1 @cond() 4140; CHECK-NEXT: br i1 %[[OUTER_COND_US]], label %[[OUTER_HEADER_US]], label %[[EXIT_SPLIT_US_SPLIT:.*]] 4141; 4142; CHECK: [[OUTER_HEADER_SPLIT_US]]: 4143; CHECK-NEXT: br label %[[OUTER_HEADER_SPLIT_SPLIT_US:.*]] 4144; 4145; CHECK: [[OUTER_HEADER_SPLIT_SPLIT_US]]: 4146; CHECK-NEXT: br label %[[INNER_HEADER_US]] 4147; 4148; CHECK: [[INNER_LOOPEXIT2_US]]: 4149; CHECK-NEXT: br label %[[OUTER_LATCH_US]] 4150; 4151; CHECK: [[EXIT_SPLIT_US]]: 4152; CHECK-NEXT: br label %exit 4153 4154inner.latch: 4155 %phi = phi i32 [ %a, %inner.body1 ], [ %b, %inner.body2 ] 4156 ; Make 10 junk calls here to ensure we're over the "50" cost threshold of 4157 ; non-trivial unswitching for this inner switch. 4158 call void @sink1(i32 0) 4159 call void @sink1(i32 0) 4160 call void @sink1(i32 0) 4161 call void @sink1(i32 0) 4162 call void @sink1(i32 0) 4163 call void @sink1(i32 0) 4164 call void @sink1(i32 0) 4165 call void @sink1(i32 0) 4166 call void @sink1(i32 0) 4167 call void @sink1(i32 0) 4168 call void @sink1(i32 %phi) 4169 %inner.cond = call i1 @cond() 4170 br i1 %inner.cond, label %inner.header, label %inner.loopexit2 4171 4172inner.loopexit1: 4173 br label %outer.latch 4174; The unswitched `loopexit1` path. 4175; 4176; CHECK: [[ENTRY_SPLIT]]: 4177; CHECK-NEXT: br label %[[OUTER_HEADER:.*]] 4178; 4179; CHECK: outer.header: 4180; CHECK-NEXT: br label %inner.loopexit1 4181; 4182; CHECK: inner.loopexit1: 4183; CHECK-NEXT: br label %outer.latch 4184; 4185; CHECK: outer.latch: 4186; CHECK-NEXT: %outer.cond = call i1 @cond() 4187; CHECK-NEXT: br i1 %outer.cond, label %outer.header, label %[[EXIT_SPLIT:.*]] 4188; 4189; CHECK: [[EXIT_SPLIT]]: 4190; CHECK-NEXT: br label %exit 4191 4192inner.loopexit2: 4193 br label %outer.latch 4194 4195outer.latch: 4196 %outer.cond = call i1 @cond() 4197 br i1 %outer.cond, label %outer.header, label %exit 4198 4199exit: 4200 ret void 4201; CHECK: exit: 4202; CHECK-NEXT: ret void 4203} 4204 4205; Non-trivial partial loop unswitching of multiple invariant inputs to an `and` 4206; chain (select version). 4207define i32 @test32(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2) { 4208; CHECK-LABEL: @test32( 4209entry: 4210 br label %loop_begin 4211; CHECK-NEXT: entry: 4212; CHECK-NEXT: %[[INV_AND:.*]] = and i1 %cond2, %cond1 4213; CHECK-NEXT: br i1 %[[INV_AND]], label %entry.split, label %entry.split.us 4214 4215loop_begin: 4216 %v1 = load i1, i1* %ptr1 4217 %v2 = load i1, i1* %ptr2 4218 %cond_and1 = select i1 %v1, i1 %cond1, i1 false 4219 %cond_and2 = select i1 %cond_and1, i1 %cond2, i1 false 4220 br i1 %cond_and2, label %loop_a, label %loop_b 4221; The 'loop_b' unswitched loop. 4222; 4223; CHECK: entry.split.us: 4224; CHECK-NEXT: br label %loop_begin.us 4225; 4226; CHECK: loop_begin.us: 4227; CHECK-NEXT: %[[V2_US]] = load i1, i1* %ptr2, align 1 4228; CHECK-NEXT: br label %loop_b.us 4229; 4230; CHECK: loop_b.us: 4231; CHECK-NEXT: call i32 @b() 4232; CHECK-NEXT: br label %latch.us 4233; 4234; CHECK: latch.us: 4235; CHECK-NEXT: %[[V3_US:.*]] = load i1, i1* %ptr3, align 1 4236; CHECK-NEXT: br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us 4237; 4238; CHECK: loop_exit.split.us: 4239; CHECK-NEXT: br label %loop_exit 4240 4241; The original loop. 4242; 4243; CHECK: entry.split: 4244; CHECK-NEXT: br label %loop_begin 4245; 4246; CHECK: loop_begin: 4247; CHECK-NEXT: %[[V1:.*]] = load i1, i1* %ptr1 4248; CHECK-NEXT: %[[V2:.*]] = load i1, i1* %ptr2 4249; CHECK-NEXT: %[[AND1:.*]] = select i1 %[[V1]], i1 true, i1 false 4250; CHECK-NEXT: %[[AND2:.*]] = select i1 %[[AND1]], i1 true, i1 false 4251; CHECK-NEXT: br i1 %[[V1]], label %loop_a, label %loop_b 4252 4253loop_a: 4254 call i32 @a() 4255 br label %latch 4256; CHECK: loop_a: 4257; CHECK-NEXT: call i32 @a() 4258; CHECK-NEXT: br label %latch 4259 4260loop_b: 4261 call i32 @b() 4262 br label %latch 4263; CHECK: loop_b: 4264; CHECK-NEXT: call i32 @b() 4265; CHECK-NEXT: br label %latch 4266 4267latch: 4268 %v3 = load i1, i1* %ptr3 4269 br i1 %v3, label %loop_begin, label %loop_exit 4270; CHECK: latch: 4271; CHECK-NEXT: %[[V3:.*]] = load i1, i1* %ptr3, align 1 4272; CHECK-NEXT: br i1 %[[V3]], label %loop_begin, label %loop_exit.split 4273 4274loop_exit: 4275 ret i32 0 4276; CHECK: loop_exit.split: 4277; CHECK-NEXT: br label %loop_exit 4278; 4279; CHECK: loop_exit: 4280; CHECK-NEXT: ret 4281} 4282 4283; Non-trivial partial loop unswitching of multiple invariant inputs to an `or` 4284; chain (select version). 4285define i32 @test33(i1* %ptr1, i1* %ptr2, i1* %ptr3, i1 %cond1, i1 %cond2) { 4286; CHECK-LABEL: @test33( 4287entry: 4288 br label %loop_begin 4289; CHECK-NEXT: entry: 4290; CHECK-NEXT: %[[INV_OR:.*]] = or i1 %cond2, %cond1 4291; CHECK-NEXT: br i1 %[[INV_OR]], label %entry.split.us, label %entry.split 4292 4293loop_begin: 4294 %v1 = load i1, i1* %ptr1 4295 %v2 = load i1, i1* %ptr2 4296 %cond_and1 = select i1 %v1, i1 true, i1 %cond1 4297 %cond_and2 = select i1 %cond_and1, i1 true, i1 %cond2 4298 br i1 %cond_and2, label %loop_b, label %loop_a 4299; The 'loop_b' unswitched loop. 4300; 4301; CHECK: entry.split.us: 4302; CHECK-NEXT: br label %loop_begin.us 4303; 4304; CHECK: loop_begin.us: 4305; CHECK-NEXT: %[[V2_US]] = load i1, i1* %ptr2, align 1 4306; CHECK-NEXT: br label %loop_b.us 4307; 4308; CHECK: loop_b.us: 4309; CHECK-NEXT: call i32 @b() 4310; CHECK-NEXT: br label %latch.us 4311; 4312; CHECK: latch.us: 4313; CHECK-NEXT: %[[V3_US:.*]] = load i1, i1* %ptr3, align 1 4314; CHECK-NEXT: br i1 %[[V3_US]], label %loop_begin.us, label %loop_exit.split.us 4315; 4316; CHECK: loop_exit.split.us: 4317; CHECK-NEXT: br label %loop_exit 4318 4319; The original loop. 4320; 4321; CHECK: entry.split: 4322; CHECK-NEXT: br label %loop_begin 4323; 4324; CHECK: loop_begin: 4325; CHECK-NEXT: %[[V1:.*]] = load i1, i1* %ptr1 4326; CHECK-NEXT: %[[V2:.*]] = load i1, i1* %ptr2 4327; CHECK-NEXT: %[[AND1:.*]] = select i1 %[[V1]], i1 true, i1 false 4328; CHECK-NEXT: %[[AND2:.*]] = select i1 %[[AND1]], i1 true, i1 false 4329; CHECK-NEXT: br i1 %[[V1]], label %loop_b, label %loop_a 4330 4331loop_a: 4332 call i32 @a() 4333 br label %latch 4334; CHECK: loop_a: 4335; CHECK-NEXT: call i32 @a() 4336; CHECK-NEXT: br label %latch 4337 4338loop_b: 4339 call i32 @b() 4340 br label %latch 4341; CHECK: loop_b: 4342; CHECK-NEXT: call i32 @b() 4343; CHECK-NEXT: br label %latch 4344 4345latch: 4346 %v3 = load i1, i1* %ptr3 4347 br i1 %v3, label %loop_begin, label %loop_exit 4348; CHECK: latch: 4349; CHECK-NEXT: %[[V3:.*]] = load i1, i1* %ptr3, align 1 4350; CHECK-NEXT: br i1 %[[V3]], label %loop_begin, label %loop_exit.split 4351 4352loop_exit: 4353 ret i32 0 4354; CHECK: loop_exit.split: 4355; CHECK-NEXT: br label %loop_exit 4356; 4357; CHECK: loop_exit: 4358; CHECK-NEXT: ret 4359} 4360