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,28 @@ 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); + + // If the numbered switch cases cover the entire range of the condition, + // then the default case is not reachable. + if (SIRange.getSignedMin() == Low && SIRange.getSignedMax() == High && + SI->getNumCases() == High - Low + 1) { + 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 @@ -25,6 +25,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AssumeBundleQueries.h" +#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/EHPersonalities.h" @@ -2182,6 +2183,42 @@ 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(); + auto *OrigDefaultBlock = Switch->getDefaultDest(); + + unsigned SuccIdx = (*Switch->case_default()).getSuccessorIndex(); + auto *NewSplitBlock = SplitCriticalEdge(Switch, SuccIdx); + if (NewSplitBlock && DTU) { + DTU->applyUpdates( + {{DominatorTree::Insert, BB, &*NewSplitBlock}, + {DominatorTree::Insert, NewSplitBlock, &*OrigDefaultBlock}}); + if (!llvm::is_contained(predecessors(OrigDefaultBlock), BB)) + DTU->applyUpdates({{DominatorTree::Delete, BB, &*OrigDefaultBlock}}); + } + + BasicBlock *NewDefaultBlock = SplitBlockPredecessors( + Switch->getDefaultDest(), Switch->getParent(), "", DTU); + 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 @@ -4743,29 +4743,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 @@ -382,7 +382,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[S:%.*]] = urem i32 [[COND:%.*]], 3 ; CHECK-NEXT: [[S1:%.*]] = add nuw nsw i32 [[S]], 1 -; CHECK-NEXT: switch i32 [[S1]], label [[UNREACHABLE:%.*]] [ +; CHECK-NEXT: switch i32 [[S1]], label [[UNREACHABLE1:%.*]] [ ; CHECK-NEXT: i32 1, label [[EXIT1:%.*]] ; CHECK-NEXT: i32 2, label [[EXIT2:%.*]] ; CHECK-NEXT: i32 3, label [[EXIT1]] @@ -391,6 +391,10 @@ ; CHECK-NEXT: ret i32 1 ; CHECK: exit2: ; CHECK-NEXT: ret i32 2 +; CHECK: unreachable1: +; CHECK-NEXT: unreachable +; CHECK: unreachable1.split: +; CHECK-NEXT: br label [[UNREACHABLE:%.*]] ; CHECK: unreachable: ; CHECK-NEXT: ret i32 0 ; @@ -411,6 +415,71 @@ ret i32 0 } +define i32 @switch_range_not_full(i32 %cond) { +; CHECK-LABEL: @switch_range_not_full( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[S:%.*]] = urem i32 [[COND:%.*]], 3 +; CHECK-NEXT: [[S1:%.*]] = add nuw nsw i32 [[S]], 1 +; CHECK-NEXT: switch i32 [[S1]], label [[UNREACHABLE:%.*]] [ +; CHECK-NEXT: i32 1, label [[EXIT1:%.*]] +; CHECK-NEXT: i32 3, label [[EXIT2:%.*]] +; CHECK-NEXT: ] +; CHECK: exit1: +; CHECK-NEXT: ret i32 1 +; CHECK: exit2: +; CHECK-NEXT: ret i32 2 +; CHECK: unreachable: +; CHECK-NEXT: ret i32 0 +; +entry: + %s = urem i32 %cond, 3 + %s1 = add i32 %s, 1 + switch i32 %s1, label %unreachable [ + i32 1, label %exit1 + i32 3, label %exit2 + ] + +exit1: + ret i32 1 +exit2: + ret i32 2 +unreachable: + ret i32 0 +} + +define i8 @switch_defaultdest_multipleuse(i8 %t0) { +; CHECK-LABEL: @switch_defaultdest_multipleuse( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[O:%.*]] = or i8 [[T0:%.*]], 1 +; CHECK-NEXT: [[S:%.*]] = sext i8 [[O]] to i16 +; CHECK-NEXT: [[R_RHS_TRUNC:%.*]] = trunc i16 [[S]] to i8 +; CHECK-NEXT: [[R1:%.*]] = srem i8 1, [[R_RHS_TRUNC]] +; CHECK-NEXT: [[R_SEXT:%.*]] = sext i8 [[R1]] to i16 +; CHECK-NEXT: [[T:%.*]] = trunc i16 [[R_SEXT]] to i8 +; CHECK-NEXT: br label [[EXIT:%.*]] +; CHECK: entry.exit_crit_edge2: +; CHECK-NEXT: unreachable +; CHECK: entry.exit_crit_edge2.split: +; CHECK-NEXT: br label [[ENTRY_EXIT_CRIT_EDGE:%.*]] +; CHECK: entry.exit_crit_edge: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i8 0 +; +entry: + %o = or i8 %t0, 1 + %s = sext i8 %o to i16 + %r = srem i16 1, %s + %t = trunc i16 %r to i8 + switch i8 %t, label %exit [ + i8 0, label %exit + i8 1, label %exit + ] + +exit: +ret i8 0 +} + define i1 @arg_attribute(i8* nonnull %a) { ; CHECK-LABEL: @arg_attribute( ; CHECK-NEXT: ret i1 false