Index: lib/Transforms/Scalar/LoopSimplifyCFG.cpp =================================================================== --- lib/Transforms/Scalar/LoopSimplifyCFG.cpp +++ lib/Transforms/Scalar/LoopSimplifyCFG.cpp @@ -43,6 +43,8 @@ STATISTIC(NumTerminatorsFolded, "Number of terminators folded to unconditional branches"); +STATISTIC(NumLoopBlocksDeleted, + "Number of loop blocks deleted"); /// If \p BB has multiple successors, but only one of them can be reached from /// this block in runtime, return this successor. Otherwise, return nullptr. @@ -218,6 +220,21 @@ } } + /// Delete loop blocks that have become unreachable after folding. Make all + /// relevant updates to DT and LI. + void deleteDeadLoopBlocks() { + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); + for (auto *BB : DeadLoopBlocks) { + LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName() + << "\n"); + if (LI.isLoopHeader(BB)) + LI.erase(LI.getLoopFor(BB)); + LI.removeBlock(BB); + DeleteDeadBlock(BB, &DTU); + ++NumLoopBlocksDeleted; + } + } + /// Constant-fold terminators of blocks acculumated in FoldCandidates into the /// unconditional branches. void foldTerminators() { @@ -259,10 +276,6 @@ bool run() { assert(L.getLoopLatch() && "Should be single latch!"); - // TODO: Support deletion of dead loop blocks. - if (!DeadLoopBlocks.empty()) - return false; - // TODO: Support dead loop exits. if (!DeadExitBlocks.empty()) return false; @@ -273,7 +286,8 @@ // TODO: Support blocks that are not dead, but also not in loop after the // folding. - if (BlocksInLoopAfterFolding.size() != L.getNumBlocks()) + if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() != + L.getNumBlocks()) return false; // Nothing to constant-fold. @@ -286,6 +300,8 @@ // Make the actual transforms. foldTerminators(); + deleteDeadLoopBlocks(); + return true; } }; Index: test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll =================================================================== --- test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll +++ test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll @@ -48,18 +48,12 @@ ; CHECK-NEXT: preheader: ; 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:%.*]] ], [ [[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:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -89,22 +83,12 @@ ; CHECK-NEXT: preheader: ; 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:%.*]] ], [ [[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:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -135,18 +119,12 @@ ; CHECK-NEXT: preheader: ; 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:%.*]] ], [ [[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:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -179,22 +157,12 @@ ; CHECK-NEXT: preheader: ; 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:%.*]] ], [ [[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:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -423,32 +391,19 @@ ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] -; CHECK-NEXT: br i1 true, label [[LIVE_PREHEADER:%.*]], label [[DEAD_PREHEADER:%.*]] -; CHECK: live_preheader: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[EXIT_A:%.*]] ] ; CHECK-NEXT: br label [[LIVE_LOOP:%.*]] ; CHECK: live_loop: -; CHECK-NEXT: [[A:%.*]] = phi i32 [ 0, [[LIVE_PREHEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ] +; CHECK-NEXT: [[A:%.*]] = phi i32 [ 0, [[HEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ] ; CHECK-NEXT: [[A_INC]] = add i32 [[A]], 1 ; CHECK-NEXT: [[CMP_A:%.*]] = icmp slt i32 [[A_INC]], [[END:%.*]] -; CHECK-NEXT: br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A:%.*]] +; CHECK-NEXT: br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A]] ; CHECK: exit.a: -; CHECK-NEXT: br label [[BACKEDGE]] -; CHECK: dead_preheader: -; CHECK-NEXT: br label [[DEAD_LOOP:%.*]] -; CHECK: dead_loop: -; CHECK-NEXT: [[B:%.*]] = phi i32 [ 0, [[DEAD_PREHEADER]] ], [ [[B_INC:%.*]], [[DEAD_LOOP]] ] -; CHECK-NEXT: [[B_INC]] = add i32 [[B]], 1 -; CHECK-NEXT: [[CMP_B:%.*]] = icmp slt i32 [[B_INC]], [[END]] -; CHECK-NEXT: br i1 [[CMP_B]], label [[DEAD_LOOP]], label [[EXIT_B:%.*]] -; CHECK: exit.b: -; CHECK-NEXT: br label [[BACKEDGE]] -; 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:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[EXIT_A]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -496,36 +451,19 @@ ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] -; CHECK-NEXT: switch i32 1, label [[DEAD_PREHEADER:%.*]] [ -; CHECK-NEXT: i32 0, label [[DEAD_PREHEADER]] -; CHECK-NEXT: i32 1, label [[LIVE_PREHEADER:%.*]] -; CHECK-NEXT: i32 2, label [[DEAD_PREHEADER]] -; CHECK-NEXT: ] -; CHECK: live_preheader: +; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[EXIT_A:%.*]] ] ; CHECK-NEXT: br label [[LIVE_LOOP:%.*]] ; CHECK: live_loop: -; CHECK-NEXT: [[A:%.*]] = phi i32 [ 0, [[LIVE_PREHEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ] +; CHECK-NEXT: [[A:%.*]] = phi i32 [ 0, [[HEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ] ; CHECK-NEXT: [[A_INC]] = add i32 [[A]], 1 ; CHECK-NEXT: [[CMP_A:%.*]] = icmp slt i32 [[A_INC]], [[END:%.*]] -; CHECK-NEXT: br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A:%.*]] +; CHECK-NEXT: br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A]] ; CHECK: exit.a: -; CHECK-NEXT: br label [[BACKEDGE]] -; CHECK: dead_preheader: -; CHECK-NEXT: br label [[DEAD_LOOP:%.*]] -; CHECK: dead_loop: -; CHECK-NEXT: [[B:%.*]] = phi i32 [ 0, [[DEAD_PREHEADER]] ], [ [[B_INC:%.*]], [[DEAD_LOOP]] ] -; CHECK-NEXT: [[B_INC]] = add i32 [[B]], 1 -; CHECK-NEXT: [[CMP_B:%.*]] = icmp slt i32 [[B_INC]], [[END]] -; CHECK-NEXT: br i1 [[CMP_B]], label [[DEAD_LOOP]], label [[EXIT_B:%.*]] -; CHECK: exit.b: -; CHECK-NEXT: br label [[BACKEDGE]] -; 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:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[EXIT_A]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -762,18 +700,12 @@ ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[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, [[OUTER_HEADER]] ], [ [[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 [[OUTER_BACKEDGE]] ; CHECK: outer_backedge: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ] ; 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:%.*]] @@ -822,22 +754,12 @@ ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[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, [[OUTER_HEADER]] ], [ [[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 [[OUTER_BACKEDGE]] ; CHECK: outer_backedge: -; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ] ; 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:%.*]]