Index: llvm/lib/Transforms/Utils/LowerSwitch.cpp =================================================================== --- llvm/lib/Transforms/Utils/LowerSwitch.cpp +++ llvm/lib/Transforms/Utils/LowerSwitch.cpp @@ -24,6 +24,7 @@ #include "llvm/IR/CFG.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instructions.h" @@ -344,16 +345,38 @@ /// insts in a balanced binary search. void ProcessSwitchInst(SwitchInst *SI, SmallPtrSetImpl &DeleteList, - AssumptionCache *AC, LazyValueInfo *LVI) { + AssumptionCache *AC, LazyValueInfo *LVI, + DominatorTree *DT) { BasicBlock *OrigBlock = SI->getParent(); Function *F = OrigBlock->getParent(); Value *Val = SI->getCondition(); // The value we are switching on... BasicBlock* Default = SI->getDefaultDest(); + // The basic blocks dominated by the original default block won't change. + // So we query the descendants of the default block in the dominator tree + // before processing the switch instruction. + SmallVector BBDominatedByOrigDefault; + DT->getDescendants(Default, BBDominatedByOrigDefault); + + // This helper function is supposed to be called when switch processing is + // done. + // 1. The SwitchInst SI will be erased. + // 2. DT will be rebuilt to check whether the original default block become + // unreachable from entry. If so, add the OrigDefault and its dominatees + // to the DeleteList. + auto EraseSwitchInstAndDeleteOrigDefaultIfUnreachable = [&]() { + BasicBlock *OrigDefault = SI->getDefaultDest(); + SI->eraseFromParent(); + DT->recalculate(*OrigBlock->getParent()); + if (!DT->isReachableFromEntry(OrigDefault)) + DeleteList.insert(BBDominatedByOrigDefault.begin(), + BBDominatedByOrigDefault.end()); + }; // Don't handle unreachable blocks. If there are successors with phis, this // would leave them behind with missing predecessors. - if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) || - OrigBlock->getSinglePredecessor() == OrigBlock) { + if (!DT->isReachableFromEntry(OrigBlock)) { + LLVM_DEBUG(dbgs() << "Unreachable block " << OrigBlock->getName() + << " contains a switch inst, removing\n"); DeleteList.insert(OrigBlock); return; } @@ -480,11 +503,11 @@ // If there are no cases left, just branch. if (Cases.empty()) { BranchInst::Create(Default, OrigBlock); - SI->eraseFromParent(); // As all the cases have been replaced with a single branch, only keep // one entry in the PHI nodes. for (unsigned I = 0 ; I < (MaxPop - 1) ; ++I) PopSucc->removePredecessor(OrigBlock); + EraseSwitchInstAndDeleteOrigDefaultIfUnreachable(); return; } @@ -512,15 +535,11 @@ BranchInst::Create(SwitchBlock, OrigBlock); // We are now done with the switch instruction, delete it. - BasicBlock *OldDefault = SI->getDefaultDest(); - OrigBlock->getInstList().erase(SI); - - // If the Default block has no more predecessors just add it to DeleteList. - if (pred_empty(OldDefault)) - DeleteList.insert(OldDefault); + EraseSwitchInstAndDeleteOrigDefaultIfUnreachable(); } -bool LowerSwitch(Function &F, LazyValueInfo *LVI, AssumptionCache *AC) { +bool LowerSwitch(Function &F, LazyValueInfo *LVI, AssumptionCache *AC, + DominatorTree *DT) { bool Changed = false; SmallPtrSet DeleteList; @@ -533,14 +552,15 @@ if (SwitchInst *SI = dyn_cast(Cur.getTerminator())) { Changed = true; - ProcessSwitchInst(SI, DeleteList, AC, LVI); + ProcessSwitchInst(SI, DeleteList, AC, LVI, DT); } } - for (BasicBlock *BB : DeleteList) { + // Keep LazyValueInfo up-to-date. + for (auto *BB : DeleteList) LVI->eraseBlock(BB); - DeleteDeadBlock(BB); - } + SmallVector BBVec(DeleteList.begin(), DeleteList.end()); + DeleteDeadBlocks(BBVec); return Changed; } @@ -558,7 +578,10 @@ bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); } }; @@ -572,6 +595,7 @@ INITIALIZE_PASS_BEGIN(LowerSwitchLegacyPass, "lowerswitch", "Lower SwitchInst's to branches", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) INITIALIZE_PASS_END(LowerSwitchLegacyPass, "lowerswitch", "Lower SwitchInst's to branches", false, false) @@ -585,13 +609,19 @@ LazyValueInfo *LVI = &getAnalysis().getLVI(); auto *ACT = getAnalysisIfAvailable(); AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr; - return LowerSwitch(F, LVI, AC); + DominatorTree *DT = &getAnalysis().getDomTree(); + return LowerSwitch(F, LVI, AC, DT); } PreservedAnalyses LowerSwitchPass::run(Function &F, FunctionAnalysisManager &AM) { LazyValueInfo *LVI = &AM.getResult(F); AssumptionCache *AC = AM.getCachedResult(F); - return LowerSwitch(F, LVI, AC) ? PreservedAnalyses::none() - : PreservedAnalyses::all(); + DominatorTree *DT = &AM.getResult(F); + if (!LowerSwitch(F, LVI, AC, DT)) + return PreservedAnalyses::all(); + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + return PA; } Index: llvm/test/Transforms/LowerSwitch/delete-all-new-dead-blocks.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LowerSwitch/delete-all-new-dead-blocks.ll @@ -0,0 +1,102 @@ +; RUN: opt -S -lowerswitch %s | FileCheck %s +; RUN: opt %s -passes=lowerswitch -S | FileCheck %s + +; Check that the new dead blocks introduced by LowerSwitch pass (they were alive before the pass), are deleted. + +; CHECK-LABEL: define i32 @f +; CHECK-NOT: out_of_switch_range +; CHECK-NOT: successor_of_unreachable + +define i32 @f(i32 %c) { +chk65: + %cmp = icmp sgt i32 %c, 65 + br i1 %cmp, label %return, label %chk0 + +chk0: ; preds = %chk65 + %cmp1 = icmp slt i32 %c, 0 + br i1 %cmp, label %return, label %bb_if + +bb_if: ; preds = %chk0 + %ashr.val = ashr exact i32 %c, 2 + %cmp2 = icmp sgt i32 %ashr.val, 14 + br i1 %cmp2, label %bb_switch, label %return + +bb_switch: ; preds = %bb_if +; %ashr.val must be 15 or 16 here (analyzed by LazyValueInfo) + switch i32 %ashr.val, label %out_of_switch_range [ + i32 15, label %return + i32 16, label %another_ret + ] + +; unreachable default case +out_of_switch_range: ; preds = %bb_switch + br label %successor_of_unreachable + +; unreachable successors +successor_of_unreachable: ; preds = %out_of_switch_range + br label %return + +another_ret: ; preds = %bb_switch + br label %return + +return: ; preds = %another_ret, %successor_of_unreachable, %bb_switch, %bb_if, %chk0, %chk65 + %retval = phi i32 [ -1, %chk0 ], [ -1, %chk65 ], [ -1, %bb_if ], [ 42, %bb_switch ], [ 42, %another_ret ], [ -42, %successor_of_unreachable ] + ret i32 %retval +} + +; CHECK-LABEL: define i32 @g +; CHECK: bb_switch: +; CHECK-NEXT: br label %return +; CHECK-NOT: out_of_switch_range +define i32 @g(i32 %c) { +bb_switch: + switch i32 %c, label %out_of_switch_range [ + i32 16, label %return + ] + +out_of_switch_range: ; preds = %bb_switch + unreachable + +return: ; preds = %bb_switch + ret i32 %c +} + +; CHECK-LABEL: define i32 @h +; CHECK-NOT: out_of_switch_range +; CHECK-NOT: successor_of_unreachable +define i32 @h(i32 %c) { +chk65: + %cmp = icmp sgt i32 %c, 65 + br i1 %cmp, label %return, label %chk0 + +chk0: ; preds = %chk65 + %cmp1 = icmp slt i32 %c, 0 + br i1 %cmp, label %return, label %bb_if + +bb_if: ; preds = %chk0 + %ashr.val = ashr exact i32 %c, 2 + %cmp2 = icmp sgt i32 %ashr.val, 14 + br i1 %cmp2, label %bb_switch, label %return + +bb_switch: ; preds = %bb_if +; %ashr.val must be 15 or 16 here (analyzed by LazyValueInfo) + switch i32 %ashr.val, label %out_of_switch_range [ + i32 15, label %return + i32 16, label %another_ret + ] + +; unreachable default case +out_of_switch_range: ; preds = %bb_switch, %successor_of_unreachable + br label %successor_of_unreachable + +; unreachable successors +successor_of_unreachable: ; preds = %out_of_switch_range + br label %out_of_switch_range + +another_ret: ; preds = %bb_switch + br label %return + +return: ; preds = %another_ret, %bb_switch, %bb_if, %chk0, %chk65 + %retval = phi i32 [ -1, %chk0 ], [ -1, %chk65 ], [ -1, %bb_if ], [ 42, %bb_switch ], [ 42, %another_ret ] + ret i32 %retval +} Index: llvm/test/Transforms/Util/lowerswitch.ll =================================================================== --- llvm/test/Transforms/Util/lowerswitch.ll +++ llvm/test/Transforms/Util/lowerswitch.ll @@ -264,7 +264,7 @@ ] cleanup17: -; CHECK: cleanup17: +; CHECK-NOT: cleanup17: ; CHECK-NOT: phi i16 [ undef, %entry ] ; CHECK: return: