Index: lib/Transforms/Scalar/LoopSimplifyCFG.cpp =================================================================== --- lib/Transforms/Scalar/LoopSimplifyCFG.cpp +++ lib/Transforms/Scalar/LoopSimplifyCFG.cpp @@ -45,6 +45,8 @@ "Number of terminators folded to unconditional branches"); STATISTIC(NumLoopBlocksDeleted, "Number of loop blocks deleted"); +STATISTIC(NumLoopExitsDeleted, + "Number of loop exiting edges deleted"); /// If \p BB is a switch or a conditional branch, but only one of its successors /// can be reached from this block in runtime, return this successor. Otherwise, @@ -227,6 +229,113 @@ "Header not in loop?"); } + /// We need to preserve static reachibility of all loop exit blocks (this is) + /// required by loop pass manager. In order to do it, we make the following + /// trick: + /// + /// preheader: + /// + /// br label %loop_header + /// + /// loop_header: + /// ... + /// br i1 false, label %dead_exit, label %loop_block + /// ... + /// + /// We cannot simply remove edge from the loop to dead exit because in this + /// case dead_exit (and its successors) may become unreachable. To avoid that, + /// we insert the following fictive preheader: + /// + /// preheader: + /// switch i32 0, label %new_preheader, + /// [i32 1, label %dead_exit_1], + /// [i32 2, label %dead_exit_2], + /// ... + /// [i32 N, label %dead_exit_N], + /// + /// preheader-split: + /// + /// br label %loop_header + /// + /// loop_header: + /// ... + /// br i1 false, label %dead_exit, label %loop_block + /// ... + /// + /// Doing so, we preserve static reachibility of all dead exits and can later + /// remove edges from the loop to these blocks. + void handleDeadExits() { + // If no dead exits, nothing to do. + if (DeadExitBlocks.empty()) + return; + + // Split preheader like this: + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); + BasicBlock *Preheader = L.getLoopPreheader(); + BasicBlock *NewPreheader = Preheader->splitBasicBlock( + Preheader->getTerminator(), + Twine(Preheader->getName()).concat("-split")); + DTU.deleteEdge(Preheader, L.getHeader()); + DTU.insertEdge(NewPreheader, L.getHeader()); + DTU.insertEdge(Preheader, NewPreheader); + IRBuilder<> Builder(Preheader->getTerminator()); + SwitchInst *DummySwitch = + Builder.CreateSwitch(Builder.getInt32(0), NewPreheader); + Preheader->getTerminator()->eraseFromParent(); + + unsigned DummyIdx = 1; + for (BasicBlock *BB : DeadExitBlocks) { + SmallVector DeadPhis; + for (auto &PN : BB->phis()) + DeadPhis.push_back(&PN); + + // Eliminate all Phis from dead exits. + for (Instruction *PN : DeadPhis) { + PN->replaceAllUsesWith(UndefValue::get(PN->getType())); + PN->eraseFromParent(); + } + assert(DummyIdx != 0 && "Too many dead exits!"); + DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB); + DTU.insertEdge(Preheader, BB); + ++NumLoopExitsDeleted; + } + + assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?"); + if (Loop *OuterLoop = LI.getLoopFor(Preheader)) { + OuterLoop->addBasicBlockToLoop(NewPreheader, LI); + + // When we break dead edges, the outer loop may become unreachable from + // the current loop. We need to fix loop info accordingly. For this, we + // find the most nested loop that still contains L and remove L from all + // loops that are inside of it. + Loop *StillReachable = nullptr; + for (BasicBlock *BB : LiveExitBlocks) { + Loop *BBL = LI.getLoopFor(BB); + if (BBL && BBL->contains(L.getHeader())) + if (!StillReachable || + BBL->getLoopDepth() > StillReachable->getLoopDepth()) + StillReachable = BBL; + } + + // Okay, our loop is no longer in the outer loop (and maybe not in some of + // its parents as well). Make the fixup. + if (StillReachable != OuterLoop) { + LI.changeLoopFor(NewPreheader, StillReachable); + for (Loop *NotContaining = OuterLoop; NotContaining != StillReachable; + NotContaining = NotContaining->getParentLoop()) { + NotContaining->removeBlockFromLoop(NewPreheader); + for (auto *BB : L.blocks()) + NotContaining->removeBlockFromLoop(BB); + } + OuterLoop->removeChildLoop(&L); + if (StillReachable) + StillReachable->addChildLoop(&L); + else + LI.addTopLevelLoop(&L); + } + } + } + /// Delete loop blocks that have become unreachable after folding. Make all /// relevant updates to DT and LI. void deleteDeadLoopBlocks() { @@ -308,14 +417,6 @@ return false; } - // TODO: Support dead loop exits. - if (!DeadExitBlocks.empty()) { - LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop " - << L.getHeader()->getName() - << ": we don't currently support dead loop exits.\n"); - return false; - } - // TODO: Support blocks that are not dead, but also not in loop after the // folding. if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() != @@ -337,6 +438,7 @@ << "\n"); // Make the actual transforms. + handleDeadExits(); foldTerminators(); if (!DeadLoopBlocks.empty()) { Index: test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll =================================================================== --- test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll +++ test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll @@ -16,8 +16,10 @@ ; CHECK: Deleting 2 dead blocks in loop header ; CHECK-LABEL: In function dead_block_propogate_test_switch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header
,%dead,%dummy,%backedge ; CHECK: Deleting 2 dead blocks in loop header -; CHECK-LABEL: In function dead_exit_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support dead loop exits. -; CHECK-LABEL: In function dead_exit_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support dead loop exits. +; CHECK-LABEL: In function dead_exit_test_branch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header
,%backedge +; CHECK: Replacing terminator of header with an unconditional branch to the block backedge +; CHECK-LABEL: In function dead_exit_test_switch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header
,%backedge +; CHECK: Replacing terminator of header with an unconditional branch to the block backedge ; CHECK-LABEL: In function dead_loop_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop. ; CHECK-LABEL: In function dead_loop_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop. ; CHECK-LABEL: In function dead_sub_loop_test_branch_loop: No constant terminator folding candidates found in loop dead_loop @@ -28,8 +30,10 @@ ; CHECK-LABEL: In function dead_sub_loop_test_switch_loop: No constant terminator folding candidates found in loop dead_loop ; CHECK-LABEL: In function dead_sub_loop_test_switch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header
,%live_preheader,%live_loop,%exit.a,%dead_preheader,%dead_loop,%exit.b,%backedge ; CHECK: Deleting 3 dead blocks in loop header -; CHECK-LABEL: In function inf_loop_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support dead loop exits. -; CHECK-LABEL: In function inf_loop_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support dead loop exits. +; CHECK-LABEL: In function inf_loop_test_branch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header
,%dead,%dummy,%backedge +; CHECK: Constant-folding 2 terminators in loop header +; CHECK-LABEL: In function inf_loop_test_switch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header
,%dead,%dummy,%backedge +; CHECK: Constant-folding 2 terminators in loop header ; CHECK-LABEL: In function live_block_test_branch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header
,%check,%live,%backedge ; CHECK: Replacing terminator of check with an unconditional branch to the block backedge ; CHECK-LABEL: In function live_block_test_branch_loop_phis: Constant terminator folding for loop Loop at depth 1 containing: %header
,%check,%live,%backedge @@ -52,14 +56,20 @@ ; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_1: No constant terminator folding candidates found in loop outer_header ; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_1: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop. ; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_1: No constant terminator folding candidates found in loop outer_header -; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_2: Give up constant terminator folding in loop header: we don't currently support dead loop exits. -; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_2: No constant terminator folding candidates found in loop outer_header -; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_2: Give up constant terminator folding in loop header: we don't currently support dead loop exits. -; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_2: No constant terminator folding candidates found in loop outer_header -; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_3: Give up constant terminator folding in loop header: we don't currently support dead loop exits. -; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_3: No constant terminator folding candidates found in loop outer_header -; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_3: Give up constant terminator folding in loop header: we don't currently support dead loop exits. -; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_3: No constant terminator folding candidates found in loop outer_header +; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_2: Constant terminator folding for loop Loop at depth 2 containing: %header
,%live_part,%dead,%backedge +; CHECK: Constant-folding 2 terminators in loop header +; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_2: Give up constant terminator folding in loop outer_header: we don't currently support deletion of the current loop. +; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_2: Constant terminator folding for loop Loop at depth 2 containing: %header
,%live_part,%dead,%backedge +; CHECK: Constant-folding 2 terminators in loop header +; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_2: Give up constant terminator folding in loop outer_header: we don't currently support deletion of the current loop. +; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_3: Constant terminator folding for loop Loop at depth 2 containing: %header
,%live_part,%dead,%backedge +; CHECK: Constant-folding 2 terminators in loop header +; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_3: Give up constant terminator folding in loop outer_header: we don't currently support deletion of the current loop. +; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_3: Constant terminator folding for loop Loop at depth 2 containing: %header
,%live_part,%dead,%backedge +; CHECK: Constant-folding 2 terminators in loop header +; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_3: Give up constant terminator folding in loop outer_header: we don't currently support deletion of the current loop. +; CHECK-LABEL: In function exit_branch_from_inner_to_grandparent: Constant terminator folding for loop Loop at depth 3 containing: %loop_3
,%loop_3_backedge +; CHECK-LABEL: In function exit_switch_from_inner_to_grandparent: Constant terminator folding for loop Loop at depth 3 containing: %loop_3
,%loop_3_backedge ; Make sure that we can eliminate a provably dead backedge. define i32 @dead_backedge_test_branch_loop(i32 %end) { @@ -291,24 +301,25 @@ define i32 @dead_exit_test_branch_loop(i32 %end) { ; CHECK-LABEL: @dead_exit_test_branch_loop( ; CHECK-NEXT: preheader: +; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[DEAD:%.*]] +; CHECK-NEXT: ] +; CHECK: preheader-split: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] -; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]] +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] +; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[HEADER]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK: dead: -; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[HEADER]] ] ; CHECK-NEXT: br label [[DUMMY:%.*]] ; CHECK: dummy: ; CHECK-NEXT: br label [[EXIT:%.*]] -; CHECK: backedge: -; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 -; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]] -; CHECK-NEXT: br i1 [[CMP]], label [[HEADER]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK: exit.loopexit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ] ; CHECK-NEXT: br label [[EXIT]] ; CHECK: exit: -; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I_LCSSA]], [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ] +; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ undef, [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ] ; CHECK-NEXT: ret i32 [[I_1]] ; preheader: @@ -339,28 +350,25 @@ define i32 @dead_exit_test_switch_loop(i32 %end) { ; CHECK-LABEL: @dead_exit_test_switch_loop( ; CHECK-NEXT: preheader: +; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[DEAD:%.*]] +; CHECK-NEXT: ] +; CHECK: preheader-split: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] -; CHECK-NEXT: switch i32 1, label [[DEAD:%.*]] [ -; CHECK-NEXT: i32 0, label [[DEAD]] -; CHECK-NEXT: i32 1, label [[BACKEDGE]] -; CHECK-NEXT: i32 2, label [[DEAD]] -; CHECK-NEXT: ] +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] +; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[HEADER]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK: dead: -; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I]], [[HEADER]] ], [ [[I]], [[HEADER]] ] ; CHECK-NEXT: br label [[DUMMY:%.*]] ; CHECK: dummy: ; CHECK-NEXT: br label [[EXIT:%.*]] -; CHECK: backedge: -; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 -; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]] -; CHECK-NEXT: br i1 [[CMP]], label [[HEADER]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK: exit.loopexit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ] ; CHECK-NEXT: br label [[EXIT]] ; CHECK: exit: -; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I_LCSSA]], [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ] +; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ undef, [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ] ; CHECK-NEXT: ret i32 [[I_1]] ; preheader: @@ -608,21 +616,18 @@ define i32 @inf_loop_test_branch_loop(i32 %end) { ; CHECK-LABEL: @inf_loop_test_branch_loop( ; CHECK-NEXT: preheader: +; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[EXIT:%.*]] +; CHECK-NEXT: ] +; CHECK: preheader-split: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] -; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]] -; CHECK: dead: -; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1 -; CHECK-NEXT: br label [[BACKEDGE]] -; CHECK: backedge: -; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1 +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] +; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]] -; CHECK-NEXT: br i1 true, label [[HEADER]], label [[EXIT:%.*]] +; CHECK-NEXT: br label [[HEADER]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] -; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] +; CHECK-NEXT: ret i32 undef ; preheader: br label %header @@ -651,25 +656,18 @@ define i32 @inf_loop_test_switch_loop(i32 %end) { ; CHECK-LABEL: @inf_loop_test_switch_loop( ; CHECK-NEXT: preheader: +; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[EXIT:%.*]] +; CHECK-NEXT: ] +; CHECK: preheader-split: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] -; CHECK-NEXT: switch i32 1, label [[DEAD:%.*]] [ -; CHECK-NEXT: i32 0, label [[DEAD]] -; CHECK-NEXT: i32 1, label [[BACKEDGE]] -; CHECK-NEXT: i32 2, label [[DEAD]] -; CHECK-NEXT: ] -; CHECK: dead: -; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1 -; CHECK-NEXT: br label [[BACKEDGE]] -; CHECK: backedge: -; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1 +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] +; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]] -; CHECK-NEXT: br i1 true, label [[HEADER]], label [[EXIT:%.*]] +; CHECK-NEXT: br label [[HEADER]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] -; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] +; CHECK-NEXT: ret i32 undef ; preheader: br label %header @@ -1261,25 +1259,23 @@ ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK: outer_header: ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] +; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[OUTER_BACKEDGE]] +; CHECK-NEXT: ] +; CHECK: preheader-split: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]] -; CHECK-NEXT: br i1 false, label [[BACKEDGE]], label [[DEAD:%.*]] -; CHECK: dead: ; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1 -; CHECK-NEXT: br label [[BACKEDGE]] -; CHECK: backedge: -; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1 -; CHECK-NEXT: br i1 true, label [[HEADER]], label [[OUTER_BACKEDGE]] +; CHECK-NEXT: [[I_INC]] = add i32 [[I_2]], 1 +; CHECK-NEXT: br label [[HEADER]] ; CHECK: outer_backedge: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1 ; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]] ; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]] ; entry: @@ -1324,29 +1320,23 @@ ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK: outer_header: ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] +; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[OUTER_BACKEDGE]] +; CHECK-NEXT: ] +; CHECK: preheader-split: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]] -; CHECK-NEXT: switch i32 1, label [[DEAD:%.*]] [ -; CHECK-NEXT: i32 0, label [[BACKEDGE]] -; CHECK-NEXT: ] -; CHECK: dead: ; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1 -; CHECK-NEXT: br label [[BACKEDGE]] -; CHECK: backedge: -; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1 -; CHECK-NEXT: switch i32 1, label [[HEADER]] [ -; CHECK-NEXT: i32 0, label [[OUTER_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: [[I_INC]] = add i32 [[I_2]], 1 +; CHECK-NEXT: br label [[HEADER]] ; CHECK: outer_backedge: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1 ; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]] ; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]] ; entry: @@ -1392,25 +1382,22 @@ ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK: outer_header: ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] +; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[OUTER_BACKEDGE]] +; CHECK-NEXT: ] +; CHECK: preheader-split: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]] -; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]] -; CHECK: dead: -; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1 -; CHECK-NEXT: br label [[BACKEDGE]] -; CHECK: backedge: -; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1 -; CHECK-NEXT: br i1 true, label [[HEADER]], label [[OUTER_BACKEDGE]] +; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; CHECK-NEXT: br label [[HEADER]] ; CHECK: outer_backedge: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1 ; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]] ; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]] ; entry: @@ -1455,29 +1442,22 @@ ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK: outer_header: ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] +; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[OUTER_BACKEDGE]] +; CHECK-NEXT: ] +; CHECK: preheader-split: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]] -; CHECK-NEXT: switch i32 1, label [[BACKEDGE]] [ -; CHECK-NEXT: i32 0, label [[DEAD:%.*]] -; CHECK-NEXT: ] -; CHECK: dead: -; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1 -; CHECK-NEXT: br label [[BACKEDGE]] -; CHECK: backedge: -; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1 -; CHECK-NEXT: switch i32 1, label [[HEADER]] [ -; CHECK-NEXT: i32 0, label [[OUTER_BACKEDGE]] -; CHECK-NEXT: ] +; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; CHECK-NEXT: br label [[HEADER]] ; CHECK: outer_backedge: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1 ; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]] ; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]] ; entry: @@ -1515,3 +1495,141 @@ exit: ret i32 %i.inc } + +define i32 @exit_branch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) { +; CHECK-LABEL: @exit_branch_from_inner_to_grandparent( +; CHECK-NEXT: preheader: +; CHECK-NEXT: br label [[LOOP_1:%.*]] +; CHECK: loop_1: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ] +; CHECK-NEXT: br label [[LOOP_2:%.*]] +; CHECK: loop_2: +; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ] +; CHECK-NEXT: switch i32 0, label [[LOOP_2_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[LOOP_2_BACKEDGE]] +; CHECK-NEXT: ] +; CHECK: loop_2-split: +; CHECK-NEXT: br label [[LOOP_3:%.*]] +; CHECK: loop_3: +; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_2_SPLIT]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ] +; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] +; CHECK: loop_3_backedge: +; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 +; CHECK-NEXT: br label [[LOOP_3]] +; CHECK: loop_2_backedge: +; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1 +; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]] +; CHECK: loop_1_backedge.loopexit: +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] +; CHECK: loop_1_backedge.loopexit1: +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] +; CHECK: loop_1_backedge: +; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1 +; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]] +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ] +; CHECK-NEXT: ret i32 [[I_LCSSA]] +; +preheader: + br label %loop_1 + +loop_1: + %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ] + br label %loop_2 + +loop_2: + %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ] + br label %loop_3 + +loop_3: + %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ] + br i1 %cond1, label %loop_3_backedge, label %loop_1_backedge + +loop_3_backedge: + %k.next = add i32 %k, 1 + br i1 true, label %loop_3, label %loop_2_backedge + +loop_2_backedge: + %j.next = add i32 %j, 1 + %c_2 = icmp slt i32 %j.next, %N + br i1 %c_2, label %loop_2, label %loop_1_backedge + +loop_1_backedge: + %i.next = add i32 %i, 1 + %c_1 = icmp slt i32 %i.next, %N + br i1 %c_1, label %loop_1, label %exit + +exit: + ret i32 %i +} + +define i32 @exit_switch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) { +; CHECK-LABEL: @exit_switch_from_inner_to_grandparent( +; CHECK-NEXT: preheader: +; CHECK-NEXT: br label [[LOOP_1:%.*]] +; CHECK: loop_1: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ] +; CHECK-NEXT: br label [[LOOP_2:%.*]] +; CHECK: loop_2: +; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ] +; CHECK-NEXT: switch i32 0, label [[LOOP_2_SPLIT:%.*]] [ +; CHECK-NEXT: i32 1, label [[LOOP_2_BACKEDGE]] +; CHECK-NEXT: ] +; CHECK: loop_2-split: +; CHECK-NEXT: br label [[LOOP_3:%.*]] +; CHECK: loop_3: +; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_2_SPLIT]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ] +; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] +; CHECK: loop_3_backedge: +; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 +; CHECK-NEXT: br label [[LOOP_3]] +; CHECK: loop_2_backedge: +; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1 +; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]] +; CHECK: loop_1_backedge.loopexit: +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] +; CHECK: loop_1_backedge.loopexit1: +; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]] +; CHECK: loop_1_backedge: +; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1 +; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]] +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ] +; CHECK-NEXT: ret i32 [[I_LCSSA]] +; +preheader: + br label %loop_1 + +loop_1: + %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ] + br label %loop_2 + +loop_2: + %j = phi i32 [ 0, %loop_1 ], [ %j.next, %loop_2_backedge ] + br label %loop_3 + +loop_3: + %k = phi i32 [ 0, %loop_2 ], [ %k.next, %loop_3_backedge ] + br i1 %cond1, label %loop_3_backedge, label %loop_1_backedge + +loop_3_backedge: + %k.next = add i32 %k, 1 + switch i32 1, label %loop_3 [i32 0, label %loop_2_backedge] + +loop_2_backedge: + %j.next = add i32 %j, 1 + %c_2 = icmp slt i32 %j.next, %N + br i1 %c_2, label %loop_2, label %loop_1_backedge + +loop_1_backedge: + %i.next = add i32 %i, 1 + %c_1 = icmp slt i32 %i.next, %N + br i1 %c_1, label %loop_1, label %exit + +exit: + ret i32 %i +}