From 8b6effd9690024d8138de9c903d88a0c3f706487 Mon Sep 17 00:00:00 2001 From: Fedor Sergeev Date: Tue, 4 Sep 2018 20:19:41 +0000 Subject: [PATCH] [SimpleLoopUnswitch] remove a chain of dead blocks at once Recent change to deleteDeadBlocksFromLoop was not enough to fix all the problems related to dead blocks after nontrivial unswitching of switches. We need to delete all the dead blocks that were created during unswitching, otherwise we will keep having problems with phi's or dead blocks. This change removes all the dead blocks that are reachable from the loop, not trying to track whether these blocks are newly created by unswitching or not. While not completely correct, we are unlikely to get loose but reachable dead blocks that do not belong to our loop nest. It does fix all the failures currently known, in particular PR38778. Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D51519 llvm-svn: 341398 --- llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp | 38 +++++++-------- .../SimpleLoopUnswitch/delete-dead-blocks.ll | 56 ++++++++++++++++++++++ 2 files changed, 75 insertions(+), 19 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp index 3cc2c65..57799c8 100644 --- a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -1378,25 +1378,25 @@ static void deleteDeadBlocksFromLoop(Loop &L, SmallVectorImpl &ExitBlocks, DominatorTree &DT, LoopInfo &LI) { - // Find all the dead blocks, and remove them from their successors. - SmallVector DeadBlocks; - for (BasicBlock *BB : ExitBlocks) - if (!DT.isReachableFromEntry(BB)) { - for (BasicBlock *SuccBB : successors(BB)) + // Find all the dead blocks tied to this loop, and remove them from their + // successors. + SmallPtrSet DeadBlockSet; + + // Start with loop/exit blocks and get a transitive closure of reachable dead + // blocks. + SmallVector DeathCandidates(ExitBlocks.begin(), + ExitBlocks.end()); + DeathCandidates.append(L.blocks().begin(), L.blocks().end()); + while (!DeathCandidates.empty()) { + auto *BB = DeathCandidates.pop_back_val(); + if (!DeadBlockSet.count(BB) && !DT.isReachableFromEntry(BB)) { + for (BasicBlock *SuccBB : successors(BB)) { SuccBB->removePredecessor(BB); - DeadBlocks.push_back(BB); - } - - for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) - for (BasicBlock *BB : ParentL->blocks()) - if (!DT.isReachableFromEntry(BB)) { - for (BasicBlock *SuccBB : successors(BB)) - SuccBB->removePredecessor(BB); - DeadBlocks.push_back(BB); + DeathCandidates.push_back(SuccBB); } - - SmallPtrSet DeadBlockSet(DeadBlocks.begin(), - DeadBlocks.end()); + DeadBlockSet.insert(BB); + } + } // Filter out the dead blocks from the exit blocks list so that it can be // used in the caller. @@ -1405,7 +1405,7 @@ deleteDeadBlocksFromLoop(Loop &L, // Walk from this loop up through its parents removing all of the dead blocks. for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) { - for (auto *BB : DeadBlocks) + for (auto *BB : DeadBlockSet) ParentL->getBlocksSet().erase(BB); llvm::erase_if(ParentL->getBlocksVector(), [&](BasicBlock *BB) { return DeadBlockSet.count(BB); }); @@ -1430,7 +1430,7 @@ deleteDeadBlocksFromLoop(Loop &L, // Remove the loop mappings for the dead blocks and drop all the references // from these blocks to others to handle cyclic references as we start // deleting the blocks themselves. - for (auto *BB : DeadBlocks) { + for (auto *BB : DeadBlockSet) { // Check that the dominator tree has already been updated. assert(!DT.getNode(BB) && "Should already have cleared domtree!"); LI.changeLoopFor(BB, nullptr); diff --git a/llvm/test/Transforms/SimpleLoopUnswitch/delete-dead-blocks.ll b/llvm/test/Transforms/SimpleLoopUnswitch/delete-dead-blocks.ll index 0be1c85..aa10670 100644 --- a/llvm/test/Transforms/SimpleLoopUnswitch/delete-dead-blocks.ll +++ b/llvm/test/Transforms/SimpleLoopUnswitch/delete-dead-blocks.ll @@ -43,3 +43,59 @@ get_out: get_out2: unreachable } + +; +; This comes from PR38778 +; CHECK-LABEL: @Test2 +define void @Test2(i32) { +header: + br label %loop +loop: + switch i32 %0, label %continue [ + i32 -2147483648, label %check + i32 98, label %guarded1 + i32 99, label %guarded2 + ] +; CHECK-NOT: {{^}}guarded1: +guarded1: + br i1 undef, label %continue, label %leave +guarded2: + br label %continue +check: + %val = add i32 0, 1 + br i1 undef, label %continue, label %leave +continue: + br label %loop +leave: + %local = phi i32 [ 0, %guarded1 ], [ %val, %check ] + ret void +} + +; +; Yet another test from PR38778 +; +; CHECK-LABEL: @Test3 +define void @Test3(i32) { +header: + br label %outer +outer: + %bad_input.i = icmp eq i32 %0, -2147483648 + br label %inner +inner: + br i1 %bad_input.i, label %overflow, label %switchme +overflow: + br label %continue +switchme: + switch i32 %0, label %continue [ + i32 88, label %go_out + i32 99, label %case2 + ] +; CHECK-NOT: {{^}}case2: +case2: + br label %continue +continue: + %local_11_92 = phi i32 [ 0, %switchme ], [ 18, %case2 ], [ 0, %overflow ] + br i1 undef, label %outer, label %inner +go_out: + unreachable +} -- 2.7.4