diff --git a/llvm/include/llvm/Transforms/Utils/Local.h b/llvm/include/llvm/Transforms/Utils/Local.h --- a/llvm/include/llvm/Transforms/Utils/Local.h +++ b/llvm/include/llvm/Transforms/Utils/Local.h @@ -55,6 +55,7 @@ class MemorySSAUpdater; class PHINode; class StoreInst; +class SwitchInst; class TargetLibraryInfo; class TargetTransformInfo; @@ -236,6 +237,10 @@ /// This function converts the specified invoek into a normall call. void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr); +/// This function removes the default destination from the specified switch. +void createUnreachableSwitchDefault(SwitchInst *Switch, + DomTreeUpdater *DTU = nullptr); + ///===---------------------------------------------------------------------===// /// Dbg Intrinsic utilities /// diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp --- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -341,7 +341,13 @@ // ConstantFoldTerminator() as the underlying SwitchInst can be changed. SwitchInstProfUpdateWrapper SI(*I); - for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) { + APInt Low = + APInt::getSignedMaxValue(Cond->getType()->getScalarSizeInBits()); + APInt High = + APInt::getSignedMinValue(Cond->getType()->getScalarSizeInBits()); + + SwitchInst::CaseIt CI = SI->case_begin(); + for (auto CE = SI->case_end(); CI != CE;) { ConstantInt *Case = CI->getCaseValue(); LazyValueInfo::Tristate State = LVI->getPredicateAt(CmpInst::ICMP_EQ, Cond, Case, I, @@ -374,9 +380,27 @@ break; } + // Get Lower/Upper bound from switch cases. + Low = APIntOps::smin(Case->getValue(), Low); + High = APIntOps::smax(Case->getValue(), High); + // Increment the case iterator since we didn't delete it. ++CI; } + + // Try to simplify default case as unreachable + if (CI == SI->case_end() && SI->getNumCases() != 0 && + !isa(SI->getDefaultDest()->getFirstNonPHIOrDbg())) { + const ConstantRange SIRange = + LVI->getConstantRange(SI->getCondition(), SI); + + Low = APIntOps::smin(SIRange.getSignedMin(), Low); + High = APIntOps::smax(SIRange.getSignedMax(), High); + if (Low + (SI->getNumCases() - 1) == High) { + createUnreachableSwitchDefault(SI, &DTU); + Changed = true; + } + } } if (Changed) diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -2194,6 +2194,30 @@ DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}}); } +void llvm::createUnreachableSwitchDefault(SwitchInst *Switch, + DomTreeUpdater *DTU) { + LLVM_DEBUG(dbgs() << "Switch default is dead.\n"); + auto *BB = Switch->getParent(); + BasicBlock *NewDefaultBlock = SplitBlockPredecessors( + Switch->getDefaultDest(), Switch->getParent(), "", DTU); + auto *OrigDefaultBlock = Switch->getDefaultDest(); + Switch->setDefaultDest(&*NewDefaultBlock); + if (DTU) + DTU->applyUpdates({{DominatorTree::Insert, BB, &*NewDefaultBlock}, + {DominatorTree::Delete, BB, OrigDefaultBlock}}); + + SplitBlock(&*NewDefaultBlock, &NewDefaultBlock->front(), DTU); + SmallVector Updates; + if (DTU) + for (auto *Successor : successors(NewDefaultBlock)) + Updates.push_back({DominatorTree::Delete, NewDefaultBlock, Successor}); + auto *NewTerminator = NewDefaultBlock->getTerminator(); + new UnreachableInst(Switch->getContext(), NewTerminator); + NewTerminator->eraseFromParent(); + if (DTU) + DTU->applyUpdates(Updates); +} + BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, BasicBlock *UnwindEdge, DomTreeUpdater *DTU) { diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -4729,29 +4729,6 @@ return true; } -static void createUnreachableSwitchDefault(SwitchInst *Switch, - DomTreeUpdater *DTU) { - LLVM_DEBUG(dbgs() << "SimplifyCFG: switch default is dead.\n"); - auto *BB = Switch->getParent(); - BasicBlock *NewDefaultBlock = SplitBlockPredecessors( - Switch->getDefaultDest(), Switch->getParent(), "", DTU); - auto *OrigDefaultBlock = Switch->getDefaultDest(); - Switch->setDefaultDest(&*NewDefaultBlock); - if (DTU) - DTU->applyUpdates({{DominatorTree::Insert, BB, &*NewDefaultBlock}, - {DominatorTree::Delete, BB, OrigDefaultBlock}}); - SplitBlock(&*NewDefaultBlock, &NewDefaultBlock->front(), DTU); - SmallVector Updates; - if (DTU) - for (auto *Successor : successors(NewDefaultBlock)) - Updates.push_back({DominatorTree::Delete, NewDefaultBlock, Successor}); - auto *NewTerminator = NewDefaultBlock->getTerminator(); - new UnreachableInst(Switch->getContext(), NewTerminator); - EraseTerminatorAndDCECond(NewTerminator); - if (DTU) - DTU->applyUpdates(Updates); -} - /// Turn a switch with two reachable destinations into an integer range /// comparison and branch. bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(SwitchInst *SI, diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll --- a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll @@ -377,6 +377,35 @@ ret void } +define i32 @switch_range(i32 %cond) { +; CHECK-LABEL: @switch_range( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[S:%.*]] = urem i32 [[COND:%.*]], 2 +; CHECK-NEXT: [[S1:%.*]] = add nuw nsw i32 [[S]], 1 +; CHECK-NEXT: br label [[EXIT1:%.*]] +; CHECK: exit1: +; CHECK-NEXT: ret i32 1 +; CHECK: unreachable1: +; CHECK-NEXT: unreachable +; CHECK: unreachable1.split: +; CHECK-NEXT: br label [[UNREACHABLE:%.*]] +; CHECK: unreachable: +; CHECK-NEXT: ret i32 0 +; +entry: + %s = urem i32 %cond, 2 + %s1 = add i32 %s, 1 + switch i32 %s1, label %unreachable [ + i32 1, label %exit1 + i32 2, label %exit1 + ] + +exit1: + ret i32 1 +unreachable: + ret i32 0 +} + define i1 @arg_attribute(i8* nonnull %a) { ; CHECK-LABEL: @arg_attribute( ; CHECK-NEXT: ret i1 false