From cb5331eb932c1367e8396378eaa976f38d5f3688 Mon Sep 17 00:00:00 2001 From: Ilya Biryukov Date: Thu, 6 Dec 2018 13:21:01 +0000 Subject: [PATCH] Revert "[LoopSimplifyCFG] Delete dead in-loop blocks" This reverts commit r348457. The original commit causes clang to crash when doing an instrumented build with a new pass manager. Reverting to unbreak our integrate. llvm-svn: 348484 --- llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp | 42 ++----- .../LoopSimplifyCFG/constant-fold-branch.ll | 130 ++++++++++++++++----- 2 files changed, 114 insertions(+), 58 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp b/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp index 9d5b33e..3de701e 100644 --- a/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp +++ b/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp @@ -46,8 +46,6 @@ static cl::opt EnableTermFolding("enable-loop-simplifycfg-term-folding", STATISTIC(NumTerminatorsFolded, "Number of terminators folded to unconditional branches"); -STATISTIC(NumLoopBlocksDeleted, - "Number of loop blocks 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, @@ -236,27 +234,6 @@ private: "All blocks that stay in loop should be live!"); } - /// 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); - if (MSSAU) - MSSAU->removeBlocks(DeadLoopBlocks); - for (auto *BB : DeadLoopBlocks) { - assert(BB != L.getHeader() && - "Header of the current loop cannot be dead!"); - LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName() - << "\n"); - if (LI.isLoopHeader(BB)) { - assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!"); - 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() { @@ -341,6 +318,15 @@ public: return false; } + // TODO: Support deletion of dead loop blocks. + if (!DeadLoopBlocks.empty()) { + LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop " + << L.getHeader()->getName() + << ": we don't currently" + " support deletion of dead in-loop blocks.\n"); + return false; + } + // TODO: Support dead loop exits. if (!DeadExitBlocks.empty()) { LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop " @@ -351,8 +337,7 @@ public: // TODO: Support blocks that are not dead, but also not in loop after the // folding. - if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() != - L.getNumBlocks()) { + if (BlocksInLoopAfterFolding.size() != L.getNumBlocks()) { LLVM_DEBUG( dbgs() << "Give up constant terminator folding in loop " << L.getHeader()->getName() @@ -372,13 +357,6 @@ public: // Make the actual transforms. foldTerminators(); - if (!DeadLoopBlocks.empty()) { - LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size() - << " dead blocks in loop " << L.getHeader()->getName() - << "\n"); - deleteDeadLoopBlocks(); - } - #ifndef NDEBUG // Make sure that we have preserved all data structures after the transform. DT.verify(); diff --git a/llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll b/llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll index a06ada7..7998aa3 100644 --- a/llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll +++ b/llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll @@ -88,12 +88,18 @@ define i32 @dead_block_test_branch_loop(i32 %end) { ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; 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: [[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]], [[HEADER]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -123,12 +129,22 @@ define i32 @dead_block_test_switch_loop(i32 %end) { ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; 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: [[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]], [[HEADER]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -159,12 +175,18 @@ define i32 @dead_block_propogate_test_branch_loop(i32 %end) { ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; 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: [[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]], [[HEADER]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -197,12 +219,22 @@ define i32 @dead_block_propogate_test_switch_loop(i32 %end) { ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; 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: [[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]], [[HEADER]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -431,19 +463,32 @@ define i32 @dead_sub_loop_test_branch_loop(i32 %end) { ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[EXIT_A:%.*]] ] +; 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: br label [[LIVE_LOOP:%.*]] ; CHECK: live_loop: -; CHECK-NEXT: [[A:%.*]] = phi i32 [ 0, [[HEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ] +; CHECK-NEXT: [[A:%.*]] = phi i32 [ 0, [[LIVE_PREHEADER]] ], [ [[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]], [[EXIT_A]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -491,19 +536,36 @@ define i32 @dead_sub_loop_test_switch_loop(i32 %end) { ; CHECK-NEXT: preheader: ; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK: header: -; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[EXIT_A:%.*]] ] +; 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: br label [[LIVE_LOOP:%.*]] ; CHECK: live_loop: -; CHECK-NEXT: [[A:%.*]] = phi i32 [ 0, [[HEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ] +; CHECK-NEXT: [[A:%.*]] = phi i32 [ 0, [[LIVE_PREHEADER]] ], [ [[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]], [[EXIT_A]] ] +; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; preheader: @@ -836,12 +898,18 @@ define i32 @partial_sub_loop_test_branch_loop(i32 %end) { ; 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:%.*]], [[HEADER]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; 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: [[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]], [[HEADER]] ] +; 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:%.*]] @@ -890,12 +958,22 @@ define i32 @partial_sub_loop_test_switch_loop(i32 %end) { ; 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:%.*]], [[HEADER]] ] -; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 +; 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: [[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]], [[HEADER]] ] +; 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:%.*]] -- 2.7.4