[LowerSwitch][AMDGPU] Do not handle impossible values
This patch adds LazyValueInfo to LowerSwitch to compute the range of the
value being switched over and reduce the size of the tree LowerSwitch
builds to lower a switch.
Reviewed By: arsenm
Differential Revision: https://reviews.llvm.org/D58096
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@354670 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp
index fec13c8..08db63e 100644
--- a/lib/Transforms/Utils/LowerSwitch.cpp
+++ b/lib/Transforms/Utils/LowerSwitch.cpp
@@ -16,8 +16,12 @@
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/LazyValueInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
+#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
@@ -27,6 +31,7 @@
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
@@ -77,6 +82,10 @@
bool runOnFunction(Function &F) override;
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.addRequired<LazyValueInfoWrapperPass>();
+ }
+
struct CaseRange {
ConstantInt* Low;
ConstantInt* High;
@@ -90,15 +99,18 @@
using CaseItr = std::vector<CaseRange>::iterator;
private:
- void processSwitchInst(SwitchInst *SI, SmallPtrSetImpl<BasicBlock*> &DeleteList);
+ void processSwitchInst(SwitchInst *SI,
+ SmallPtrSetImpl<BasicBlock *> &DeleteList,
+ AssumptionCache *AC, LazyValueInfo *LVI);
BasicBlock *switchConvert(CaseItr Begin, CaseItr End,
ConstantInt *LowerBound, ConstantInt *UpperBound,
Value *Val, BasicBlock *Predecessor,
BasicBlock *OrigBlock, BasicBlock *Default,
const std::vector<IntRange> &UnreachableRanges);
- BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock,
- BasicBlock *Default);
+ BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val,
+ ConstantInt *LowerBound, ConstantInt *UpperBound,
+ BasicBlock *OrigBlock, BasicBlock *Default);
unsigned Clusterify(CaseVector &Cases, SwitchInst *SI);
};
@@ -120,8 +132,12 @@
// Publicly exposed interface to pass...
char &llvm::LowerSwitchID = LowerSwitch::ID;
-INITIALIZE_PASS(LowerSwitch, "lowerswitch",
- "Lower SwitchInst's to branches", false, false)
+INITIALIZE_PASS_BEGIN(LowerSwitch, "lowerswitch",
+ "Lower SwitchInst's to branches", false, false)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
+INITIALIZE_PASS_END(LowerSwitch, "lowerswitch",
+ "Lower SwitchInst's to branches", false, false)
// createLowerSwitchPass - Interface to this file...
FunctionPass *llvm::createLowerSwitchPass() {
@@ -129,6 +145,17 @@
}
bool LowerSwitch::runOnFunction(Function &F) {
+ LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
+ auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>();
+ AssumptionCache *AC = ACT ? &ACT->getAssumptionCache(F) : nullptr;
+ // Prevent LazyValueInfo from using the DominatorTree as LowerSwitch does not
+ // preserve it and it becomes stale (when available) pretty much immediately.
+ // Currently the DominatorTree is only used by LowerSwitch indirectly via LVI
+ // and computeKnownBits to refine isValidAssumeForContext's results. Given
+ // that the latter can handle some of the simple cases w/o a DominatorTree,
+ // it's easier to refrain from using the tree than to keep it up to date.
+ LVI->disableDT();
+
bool Changed = false;
SmallPtrSet<BasicBlock*, 8> DeleteList;
@@ -142,11 +169,12 @@
if (SwitchInst *SI = dyn_cast<SwitchInst>(Cur->getTerminator())) {
Changed = true;
- processSwitchInst(SI, DeleteList);
+ processSwitchInst(SI, DeleteList, AC, LVI);
}
}
for (BasicBlock* BB: DeleteList) {
+ LVI->eraseBlock(BB);
DeleteDeadBlock(BB);
}
@@ -159,10 +187,11 @@
const LowerSwitch::CaseVector &C) {
O << "[";
- for (LowerSwitch::CaseVector::const_iterator B = C.begin(),
- E = C.end(); B != E; ) {
- O << *B->Low << " -" << *B->High;
- if (++B != E) O << ", ";
+ for (LowerSwitch::CaseVector::const_iterator B = C.begin(), E = C.end();
+ B != E;) {
+ O << "[" << B->Low->getValue() << ", " << B->High->getValue() << "]";
+ if (++B != E)
+ O << ", ";
}
return O << "]";
@@ -178,8 +207,9 @@
/// 2) Removed if subsequent incoming values now share the same case, i.e.,
/// multiple outcome edges are condensed into one. This is necessary to keep the
/// number of phi values equal to the number of branches to SuccBB.
-static void fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
- unsigned NumMergedCases) {
+static void
+fixPhis(BasicBlock *SuccBB, BasicBlock *OrigBB, BasicBlock *NewBB,
+ const unsigned NumMergedCases = std::numeric_limits<unsigned>::max()) {
for (BasicBlock::iterator I = SuccBB->begin(),
IE = SuccBB->getFirstNonPHI()->getIterator();
I != IE; ++I) {
@@ -221,6 +251,7 @@
BasicBlock *Predecessor, BasicBlock *OrigBlock,
BasicBlock *Default,
const std::vector<IntRange> &UnreachableRanges) {
+ assert(LowerBound && UpperBound && "Bounds must be initialized");
unsigned Size = End - Begin;
if (Size == 1) {
@@ -230,13 +261,12 @@
// because the bounds already tell us so.
if (Begin->Low == LowerBound && Begin->High == UpperBound) {
unsigned NumMergedCases = 0;
- if (LowerBound && UpperBound)
- NumMergedCases =
- UpperBound->getSExtValue() - LowerBound->getSExtValue();
+ NumMergedCases = UpperBound->getSExtValue() - LowerBound->getSExtValue();
fixPhis(Begin->BB, OrigBlock, Predecessor, NumMergedCases);
return Begin->BB;
}
- return newLeafBlock(*Begin, Val, OrigBlock, Default);
+ return newLeafBlock(*Begin, Val, LowerBound, UpperBound, OrigBlock,
+ Default);
}
unsigned Mid = Size / 2;
@@ -246,8 +276,8 @@
LLVM_DEBUG(dbgs() << "RHS: " << RHS << "\n");
CaseRange &Pivot = *(Begin + Mid);
- LLVM_DEBUG(dbgs() << "Pivot ==> " << Pivot.Low->getValue() << " -"
- << Pivot.High->getValue() << "\n");
+ LLVM_DEBUG(dbgs() << "Pivot ==> [" << Pivot.Low->getValue() << ", "
+ << Pivot.High->getValue() << "]\n");
// NewLowerBound here should never be the integer minimal value.
// This is because it is computed from a case range that is never
@@ -269,14 +299,10 @@
NewUpperBound = LHS.back().High;
}
- LLVM_DEBUG(dbgs() << "LHS Bounds ==> "; if (LowerBound) {
- dbgs() << LowerBound->getSExtValue();
- } else { dbgs() << "NONE"; } dbgs() << " - "
- << NewUpperBound->getSExtValue() << "\n";
- dbgs() << "RHS Bounds ==> ";
- dbgs() << NewLowerBound->getSExtValue() << " - "; if (UpperBound) {
- dbgs() << UpperBound->getSExtValue() << "\n";
- } else { dbgs() << "NONE\n"; });
+ LLVM_DEBUG(dbgs() << "LHS Bounds ==> [" << LowerBound->getSExtValue() << ", "
+ << NewUpperBound->getSExtValue() << "]\n"
+ << "RHS Bounds ==> [" << NewLowerBound->getSExtValue()
+ << ", " << UpperBound->getSExtValue() << "]\n");
// Create a new node that checks if the value is < pivot. Go to the
// left branch if it is and right branch if not.
@@ -304,9 +330,11 @@
/// switch's value == the case's value. If not, then it jumps to the default
/// branch. At this point in the tree, the value can't be another valid case
/// value, so the jump to the "default" branch is warranted.
-BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val,
- BasicBlock* OrigBlock,
- BasicBlock* Default) {
+BasicBlock *LowerSwitch::newLeafBlock(CaseRange &Leaf, Value *Val,
+ ConstantInt *LowerBound,
+ ConstantInt *UpperBound,
+ BasicBlock *OrigBlock,
+ BasicBlock *Default) {
Function* F = OrigBlock->getParent();
BasicBlock* NewLeaf = BasicBlock::Create(Val->getContext(), "LeafBlock");
F->getBasicBlockList().insert(++OrigBlock->getIterator(), NewLeaf);
@@ -319,10 +347,14 @@
Leaf.Low, "SwitchLeaf");
} else {
// Make range comparison
- if (Leaf.Low->isMinValue(true /*isSigned*/)) {
+ if (Leaf.Low == LowerBound) {
// Val >= Min && Val <= Hi --> Val <= Hi
Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,
"SwitchLeaf");
+ } else if (Leaf.High == UpperBound) {
+ // Val <= Max && Val >= Lo --> Val >= Lo
+ Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SGE, Val, Leaf.Low,
+ "SwitchLeaf");
} else if (Leaf.Low->isZero()) {
// Val >= 0 && Val <= Hi --> Val <=u Hi
Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,
@@ -362,14 +394,20 @@
return NewLeaf;
}
-/// Transform simple list of Cases into list of CaseRange's.
+/// Transform simple list of \p SI's cases into list of CaseRange's \p Cases.
+/// \post \p Cases wouldn't contain references to \p SI's default BB.
+/// \returns Number of \p SI's cases that do not reference \p SI's default BB.
unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
- unsigned numCmps = 0;
+ unsigned NumSimpleCases = 0;
// Start with "simple" cases
- for (auto Case : SI->cases())
+ for (auto Case : SI->cases()) {
+ if (Case.getCaseSuccessor() == SI->getDefaultDest())
+ continue;
Cases.push_back(CaseRange(Case.getCaseValue(), Case.getCaseValue(),
Case.getCaseSuccessor()));
+ ++NumSimpleCases;
+ }
llvm::sort(Cases, CaseCmp());
@@ -395,60 +433,94 @@
Cases.erase(std::next(I), Cases.end());
}
- for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
- if (I->Low != I->High)
- // A range counts double, since it requires two compares.
- ++numCmps;
- }
+ return NumSimpleCases;
+}
- return numCmps;
+static ConstantRange getConstantRangeFromKnownBits(const KnownBits &Known) {
+ APInt Lower = Known.One;
+ APInt Upper = ~Known.Zero + 1;
+ if (Upper == Lower)
+ return ConstantRange(Known.getBitWidth(), /*isFullSet=*/true);
+ return ConstantRange(Lower, Upper);
}
/// Replace the specified switch instruction with a sequence of chained if-then
/// insts in a balanced binary search.
void LowerSwitch::processSwitchInst(SwitchInst *SI,
- SmallPtrSetImpl<BasicBlock*> &DeleteList) {
- BasicBlock *CurBlock = SI->getParent();
- BasicBlock *OrigBlock = CurBlock;
- Function *F = CurBlock->getParent();
+ SmallPtrSetImpl<BasicBlock *> &DeleteList,
+ AssumptionCache *AC, LazyValueInfo *LVI) {
+ BasicBlock *OrigBlock = SI->getParent();
+ Function *F = OrigBlock->getParent();
Value *Val = SI->getCondition(); // The value we are switching on...
BasicBlock* Default = SI->getDefaultDest();
// Don't handle unreachable blocks. If there are successors with phis, this
// would leave them behind with missing predecessors.
- if ((CurBlock != &F->getEntryBlock() && pred_empty(CurBlock)) ||
- CurBlock->getSinglePredecessor() == CurBlock) {
- DeleteList.insert(CurBlock);
- return;
- }
-
- // If there is only the default destination, just branch.
- if (!SI->getNumCases()) {
- BranchInst::Create(Default, CurBlock);
- SI->eraseFromParent();
+ if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) ||
+ OrigBlock->getSinglePredecessor() == OrigBlock) {
+ DeleteList.insert(OrigBlock);
return;
}
// Prepare cases vector.
CaseVector Cases;
- unsigned numCmps = Clusterify(Cases, SI);
+ const unsigned NumSimpleCases = Clusterify(Cases, SI);
LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size()
- << ". Total compares: " << numCmps << "\n");
- LLVM_DEBUG(dbgs() << "Cases: " << Cases << "\n");
- (void)numCmps;
+ << ". Total non-default cases: " << NumSimpleCases
+ << "\nCase clusters: " << Cases << "\n");
+
+ // If there is only the default destination, just branch.
+ if (Cases.empty()) {
+ BranchInst::Create(Default, OrigBlock);
+ // Remove all the references from Default's PHIs to OrigBlock, but one.
+ fixPhis(Default, OrigBlock, OrigBlock);
+ SI->eraseFromParent();
+ return;
+ }
ConstantInt *LowerBound = nullptr;
ConstantInt *UpperBound = nullptr;
- std::vector<IntRange> UnreachableRanges;
+ bool DefaultIsUnreachableFromSwitch = false;
if (isa<UnreachableInst>(Default->getFirstNonPHIOrDbg())) {
// Make the bounds tightly fitted around the case value range, because we
// know that the value passed to the switch must be exactly one of the case
// values.
- assert(!Cases.empty());
LowerBound = Cases.front().Low;
UpperBound = Cases.back().High;
+ DefaultIsUnreachableFromSwitch = true;
+ } else {
+ // Constraining the range of the value being switched over helps eliminating
+ // unreachable BBs and minimizing the number of `add` instructions
+ // newLeafBlock ends up emitting. Running CorrelatedValuePropagation after
+ // LowerSwitch isn't as good, and also much more expensive in terms of
+ // compile time for the following reasons:
+ // 1. it processes many kinds of instructions, not just switches;
+ // 2. even if limited to icmp instructions only, it will have to process
+ // roughly C icmp's per switch, where C is the number of cases in the
+ // switch, while LowerSwitch only needs to call LVI once per switch.
+ const DataLayout &DL = F->getParent()->getDataLayout();
+ KnownBits Known = computeKnownBits(Val, DL, /*Depth=*/0, AC, SI);
+ ConstantRange KnownBitsRange = getConstantRangeFromKnownBits(Known);
+ const ConstantRange LVIRange = LVI->getConstantRange(Val, OrigBlock, SI);
+ ConstantRange ValRange = KnownBitsRange.intersectWith(LVIRange);
+ // We delegate removal of unreachable non-default cases to other passes. In
+ // the unlikely event that some of them survived, we just conservatively
+ // maintain the invariant that all the cases lie between the bounds. This
+ // may, however, still render the default case effectively unreachable.
+ APInt Low = Cases.front().Low->getValue();
+ APInt High = Cases.back().High->getValue();
+ APInt Min = APIntOps::smin(ValRange.getSignedMin(), Low);
+ APInt Max = APIntOps::smax(ValRange.getSignedMax(), High);
+ LowerBound = ConstantInt::get(SI->getContext(), Min);
+ UpperBound = ConstantInt::get(SI->getContext(), Max);
+ DefaultIsUnreachableFromSwitch = (Min + (NumSimpleCases - 1) == Max);
+ }
+
+ std::vector<IntRange> UnreachableRanges;
+
+ if (DefaultIsUnreachableFromSwitch) {
DenseMap<BasicBlock *, unsigned> Popularity;
unsigned MaxPop = 0;
BasicBlock *PopSucc = nullptr;
@@ -495,8 +567,10 @@
#endif
// As the default block in the switch is unreachable, update the PHI nodes
- // (remove the entry to the default block) to reflect this.
- Default->removePredecessor(OrigBlock);
+ // (remove all of the references to the default block) to reflect this.
+ const unsigned NumDefaultEdges = SI->getNumCases() + 1 - NumSimpleCases;
+ for (unsigned I = 0; I < NumDefaultEdges; ++I)
+ Default->removePredecessor(OrigBlock);
// Use the most popular block as the new default, reducing the number of
// cases.
@@ -509,7 +583,7 @@
// If there are no cases left, just branch.
if (Cases.empty()) {
- BranchInst::Create(Default, CurBlock);
+ 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.
@@ -519,11 +593,6 @@
}
}
- unsigned NrOfDefaults = (SI->getDefaultDest() == Default) ? 1 : 0;
- for (const auto &Case : SI->cases())
- if (Case.getCaseSuccessor() == Default)
- NrOfDefaults++;
-
// Create a new, empty default block so that the new hierarchy of
// if-then statements go to this and the PHI nodes are happy.
BasicBlock *NewDefault = BasicBlock::Create(SI->getContext(), "NewDefault");
@@ -536,14 +605,14 @@
// If there are entries in any PHI nodes for the default edge, make sure
// to update them as well.
- fixPhis(Default, OrigBlock, NewDefault, NrOfDefaults);
+ fixPhis(Default, OrigBlock, NewDefault);
// Branch to our shiny new if-then stuff...
BranchInst::Create(SwitchBlock, OrigBlock);
// We are now done with the switch instruction, delete it.
BasicBlock *OldDefault = SI->getDefaultDest();
- CurBlock->getInstList().erase(SI);
+ OrigBlock->getInstList().erase(SI);
// If the Default block has no more predecessors just add it to DeleteList.
if (pred_begin(OldDefault) == pred_end(OldDefault))
diff --git a/test/CodeGen/AMDGPU/valu-i1.ll b/test/CodeGen/AMDGPU/valu-i1.ll
index ca85f0b..c64d4fc 100644
--- a/test/CodeGen/AMDGPU/valu-i1.ll
+++ b/test/CodeGen/AMDGPU/valu-i1.ll
@@ -8,7 +8,7 @@
; waitcnt should be inserted after exec modification
-; SI: v_cmp_lt_i32_e32 vcc, 0,
+; SI: v_cmp_lt_i32_e32 vcc, 1,
; SI-NEXT: s_mov_b64 {{s\[[0-9]+:[0-9]+\]}}, 0
; SI-NEXT: s_mov_b64 {{s\[[0-9]+:[0-9]+\]}}, 0
; SI-NEXT: s_and_saveexec_b64 [[SAVE1:s\[[0-9]+:[0-9]+\]]], vcc
@@ -31,16 +31,16 @@
entry:
%tid = call i32 @llvm.amdgcn.workitem.id.x() nounwind readnone
switch i32 %tid, label %default [
- i32 0, label %case0
i32 1, label %case1
+ i32 2, label %case2
]
-case0:
+case1:
%arrayidx1 = getelementptr i32, i32 addrspace(1)* %dst, i32 %b
store i32 13, i32 addrspace(1)* %arrayidx1, align 4
br label %end
-case1:
+case2:
%arrayidx5 = getelementptr i32, i32 addrspace(1)* %dst, i32 %b
store i32 17, i32 addrspace(1)* %arrayidx5, align 4
br label %end
diff --git a/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll b/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll
new file mode 100644
index 0000000..71c1ec7
--- /dev/null
+++ b/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll
@@ -0,0 +1,895 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -lowerswitch -S | FileCheck %s
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test1(i32 %val) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[TRUNC:%.*]] = trunc i32 [[VAL:%.*]] to i2
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i2 [[TRUNC]], 1
+; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i2 [[TRUNC]], -2
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_D:%.*]]
+; CHECK: case.D:
+; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %trunc = trunc i32 %val to i2
+ switch i2 %trunc, label %case.D [
+ i2 1, label %case.1 ; i2 1
+ i2 2, label %case.2 ; i2 -2
+ ]
+ ; It's known that %val can not be less than -2 or greater than 1
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = call i32 @caseD()
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test2() {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range !0
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 2
+; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_D:%.*]]
+; CHECK: case.D:
+; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %val = call i32 @getVal(), !range !0
+ switch i32 %val, label %case.D [
+ i32 1, label %case.1
+ i32 2, label %case.2
+ ]
+ ; It's known that %val can not be less than 1
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = call i32 @caseD()
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case is unreachable as non-default cases cover the range fully.
+define i32 @test3() {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range !1
+; CHECK-NEXT: br label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_1:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %val = call i32 @getVal(), !range !1
+ switch i32 %val, label %case.D [
+ i32 1, label %case.1
+ i32 2, label %case.2
+ i32 3, label %case.1
+ ]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = call i32 @caseD()
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case is still reachable as non-default cases do not cover the
+; range fully.
+define i32 @test4() {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range !2
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 2
+; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_D:%.*]]
+; CHECK: case.D:
+; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %val = call i32 @getVal(), !range !2
+ switch i32 %val, label %case.D [
+ i32 1, label %case.1
+ i32 2, label %case.2
+ ]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = call i32 @caseD()
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case appears to be unreachable as non-default cases cover the
+; range fully, but its basic block actually is reachable from the switch via
+; one of the non-default cases.
+define i32 @test5(i1 %cond) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK: switch:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range !1
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 3
+; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_1]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_D]]
+; CHECK: case.D:
+; CHECK-NEXT: [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[NEWDEFAULT]] ]
+; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ br i1 %cond, label %switch, label %case.D
+
+switch:
+ %val = call i32 @getVal(), !range !1
+ switch i32 %val, label %case.D [
+ i32 1, label %case.1
+ i32 2, label %case.D
+ i32 3, label %case.1
+ ]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.D:
+ %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
+ %resD.tmp = call i32 @caseD()
+ %resD = add i32 %resD.tmp, %delta
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case appears to be unreachable as non-default cases cover the
+; range fully, but its basic block actually is reachable, though, from a
+; different basic block, not the switch itself.
+define i32 @test6(i1 %cond) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK: switch:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range !1
+; CHECK-NEXT: br label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_1:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: case.D:
+; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], 0
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ br i1 %cond, label %switch, label %case.D
+
+switch:
+ %val = call i32 @getVal(), !range !1
+ switch i32 %val, label %case.D [
+ i32 1, label %case.1
+ i32 2, label %case.2
+ i32 3, label %case.1
+ ]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %delta = phi i32 [ 0, %entry ], [ 20, %switch ]
+ %resD.tmp = call i32 @caseD()
+ %resD = add i32 %resD.tmp, %delta
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Corner case:
+; 1) switch appears to have a non-empty set of non-default cases, but all of
+; them reference the default case basic block.
+define i32 @test7(i1 %cond) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK: switch:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range !1
+; CHECK-NEXT: br label [[CASE_D]]
+; CHECK: case.D:
+; CHECK-NEXT: [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[SWITCH]] ]
+; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: exit:
+; CHECK-NEXT: ret i32 [[RESD]]
+;
+entry:
+ br i1 %cond, label %switch, label %case.D
+
+switch:
+ %val = call i32 @getVal(), !range !1
+ switch i32 %val, label %case.D [
+ i32 2, label %case.D
+ ]
+
+case.D:
+ %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
+ %resD.tmp = call i32 @caseD()
+ %resD = add i32 %resD.tmp, %delta
+ br label %exit
+
+exit:
+ ret i32 %resD
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case appears to be unreachable as non-default cases cover the
+; range fully, but its basic block actually is reachable from the switch via
+; one of the non-default cases,
+; 3) such cases lie at the boundary of the range of values covered by
+; non-default cases, and if removed, do not change the fact that the rest of
+; the cases fully covers the value range.
+define i32 @test8(i1 %cond) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK: switch:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range !3
+; CHECK-NEXT: br label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_1:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: case.D:
+; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], 0
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ br i1 %cond, label %switch, label %case.D
+
+switch:
+ %val = call i32 @getVal(), !range !3
+ switch i32 %val, label %case.D [
+ i32 1, label %case.1
+ i32 2, label %case.2
+ i32 3, label %case.D
+ ]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
+ %resD.tmp = call i32 @caseD()
+ %resD = add i32 %resD.tmp, %delta
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Corner case:
+; 1) the default case appears to be unreachable as non-default cases cover the
+; range fully, but its basic block actually is reachable from the switch via
+; more than one non-default case.
+define i32 @test9(i1 %cond, i2 %val) {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK: switch:
+; CHECK-NEXT: br label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp sge i2 [[VAL:%.*]], 0
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_1:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_D]]
+; CHECK: case.D:
+; CHECK-NEXT: [[DELTA:%.*]] = phi i32 [ 20, [[NEWDEFAULT]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ br i1 %cond, label %switch, label %case.D
+
+switch:
+ switch i2 %val, label %case.D [
+ i2 0, label %case.1
+ i2 1, label %case.1
+ i2 2, label %case.D
+ i2 3, label %case.D
+ ]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.D:
+ %delta = phi i32 [20, %switch ], [ 20, %switch ], [ 20, %switch ], [ 0, %entry ]
+ %resD.tmp = call i32 @caseD()
+ %resD = add i32 %resD.tmp, %delta
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test10() {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal()
+; CHECK-NEXT: [[COND_LEFT:%.*]] = icmp sge i32 [[VAL]], 1
+; CHECK-NEXT: [[COND_RIGHT:%.*]] = icmp sle i32 [[VAL]], 6
+; CHECK-NEXT: [[COND:%.*]] = and i1 [[COND_LEFT]], [[COND_RIGHT]]
+; CHECK-NEXT: br i1 [[COND]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK: switch:
+; CHECK-NEXT: br label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[VAL_OFF:%.*]] = add i32 [[VAL]], -3
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp ule i32 [[VAL_OFF]], 1
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_1:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: case.D:
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ 0, [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %val = call i32 @getVal()
+ %cond.left = icmp sge i32 %val, 1
+ %cond.right = icmp sle i32 %val, 6
+ %cond = and i1 %cond.left, %cond.right
+ br i1 %cond, label %switch, label %case.D
+
+switch:
+ switch i32 %val, label %case.D [
+ i32 1, label %case.1
+ i32 2, label %case.1
+ i32 3, label %case.2
+ i32 4, label %case.2
+ i32 5, label %case.1
+ i32 6, label %case.1
+ ]
+ ; It's known that %val <- [1, 6]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = phi i32 [ 20, %switch ], [ 0, %entry ]
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test11() {
+; CHECK-LABEL: @test11(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal()
+; CHECK-NEXT: [[VAL_ZEXT:%.*]] = zext i32 [[VAL]] to i64
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i64 [[VAL_ZEXT]], 1
+; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i64 [[VAL_ZEXT]], 1
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_D:%.*]]
+; CHECK: case.D:
+; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %val = call i32 @getVal()
+ %val.zext = zext i32 %val to i64
+ switch i64 %val.zext, label %case.D [
+ i64 0, label %case.1
+ i64 1, label %case.2
+ ]
+ ; It's known that %val can not be less than 0
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = call i32 @caseD()
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define void @test12() {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br label [[FOR_BODY:%.*]]
+; CHECK: for.body:
+; CHECK-NEXT: [[INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[INDVAR]], 1
+; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[INDVAR]], 1
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: br label [[LATCH]]
+; CHECK: case.2:
+; CHECK-NEXT: br label [[LATCH]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[LATCH]]
+; CHECK: latch:
+; CHECK-NEXT: [[INC]] = add nuw nsw i32 [[INDVAR]], 1
+; CHECK-NEXT: br i1 undef, label [[EXIT:%.*]], label [[FOR_BODY]]
+; CHECK: exit:
+; CHECK-NEXT: ret void
+;
+entry:
+ br label %for.body
+
+for.body:
+ %indvar = phi i32 [ 0, %entry ], [ %inc, %latch ]
+ switch i32 %indvar, label %latch [
+ i32 0, label %case.1
+ i32 1, label %case.2
+ ]
+ ; It's known that %indvar can not be less than 0
+
+case.1:
+ br label %latch
+
+case.2:
+ br label %latch
+
+latch:
+ %inc = add nuw nsw i32 %indvar, 1
+ br i1 undef, label %exit, label %for.body
+
+exit:
+ ret void
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define void @test13(i32 %val) {
+; CHECK-LABEL: @test13(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[TMP:%.*]] = and i32 [[VAL:%.*]], 7
+; CHECK-NEXT: br label [[BB33:%.*]]
+; CHECK: bb33:
+; CHECK-NEXT: br label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[TMP_OFF:%.*]] = add i32 [[TMP]], -2
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp ule i32 [[TMP_OFF]], 1
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[BB34:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: bb34:
+; CHECK-NEXT: br label [[BB38:%.*]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[BB35:%.*]]
+; CHECK: bb35:
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[TMP]], 6
+; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK2:%.*]], label [[BB37:%.*]]
+; CHECK: LeafBlock2:
+; CHECK-NEXT: [[SWITCHLEAF3:%.*]] = icmp sle i32 [[TMP]], 1
+; CHECK-NEXT: br i1 [[SWITCHLEAF3]], label [[BB37]], label [[NEWDEFAULT1:%.*]]
+; CHECK: bb37:
+; CHECK-NEXT: br label [[BB38]]
+; CHECK: NewDefault1:
+; CHECK-NEXT: br label [[BB38]]
+; CHECK: bb38:
+; CHECK-NEXT: br label [[BB33]]
+;
+entry:
+ %tmp = and i32 %val, 7
+ br label %bb33
+
+bb33:
+ switch i32 %tmp, label %bb35 [
+ i32 2, label %bb34
+ i32 3, label %bb34
+ ]
+
+bb34:
+ br label %bb38
+
+bb35:
+ switch i32 %tmp, label %bb38 [
+ i32 0, label %bb37
+ i32 1, label %bb37
+ i32 6, label %bb37
+ i32 7, label %bb37
+ ]
+ ; It's known that %tmp <- [0, 1] U [4, 7]
+
+bb37:
+ br label %bb38
+
+bb38:
+ br label %bb33
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test14() {
+; CHECK-LABEL: @test14(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[TMP:%.*]] = call i32 @getVal(), !range !4
+; CHECK-NEXT: [[VAL:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP]])
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1
+; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_D:%.*]]
+; CHECK: case.D:
+; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %tmp = call i32 @getVal(), !range !4
+ %val = call i32 @llvm.ctpop.i32(i32 %tmp)
+ switch i32 %val, label %case.D [
+ i32 0, label %case.1
+ i32 1, label %case.2
+ ]
+ ; It's known that %val <- [0, 2]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = call i32 @caseD()
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test15() {
+; CHECK-LABEL: @test15(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[TMP:%.*]] = call i32 @getVal()
+; CHECK-NEXT: [[VAL:%.*]] = urem i32 [[TMP]], 3
+; CHECK-NEXT: br label [[NODEBLOCK:%.*]]
+; CHECK: NodeBlock:
+; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1
+; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_D:%.*]]
+; CHECK: case.D:
+; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %tmp = call i32 @getVal()
+ %val = urem i32 %tmp, 3
+ switch i32 %val, label %case.D [
+ i32 0, label %case.1
+ i32 1, label %case.2
+ ]
+ ; It's known that %val <- [0, 2]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = call i32 @caseD()
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test16(float %f) {
+; CHECK-LABEL: @test16(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[I:%.*]] = fptosi float [[F:%.*]] to i64
+; CHECK-NEXT: [[COND_LEFT:%.*]] = icmp slt i64 [[I]], 0
+; CHECK-NEXT: [[CLAMP_LEFT:%.*]] = select i1 [[COND_LEFT]], i64 0, i64 [[I]]
+; CHECK-NEXT: [[COND_RIGHT:%.*]] = icmp sgt i64 [[I]], 3
+; CHECK-NEXT: [[CLAMP:%.*]] = select i1 [[COND_RIGHT]], i64 3, i64 [[CLAMP_LEFT]]
+; CHECK-NEXT: br label [[LEAFBLOCK:%.*]]
+; CHECK: LeafBlock:
+; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp sge i64 [[CLAMP]], 2
+; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK: NewDefault:
+; CHECK-NEXT: br label [[CASE_1:%.*]]
+; CHECK: case.1:
+; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT: br label [[EXIT:%.*]]
+; CHECK: case.2:
+; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ]
+; CHECK-NEXT: ret i32 [[RES]]
+;
+entry:
+ %i = fptosi float %f to i64
+ %cond.left = icmp slt i64 %i, 0
+ %clamp.left = select i1 %cond.left, i64 0, i64 %i
+ %cond.right = icmp sgt i64 %i, 3
+ %clamp = select i1 %cond.right, i64 3, i64 %clamp.left
+ switch i64 %clamp, label %case.D [
+ i64 0, label %case.1
+ i64 1, label %case.1
+ i64 2, label %case.2
+ i64 3, label %case.2
+ ]
+ ; It's known that %val <- [0, 3]
+
+case.1:
+ %res1 = call i32 @case1()
+ br label %exit
+
+case.2:
+ %res2 = call i32 @case2()
+ br label %exit
+
+case.D:
+ %resD = call i32 @caseD()
+ br label %exit
+
+exit:
+ %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+ ret i32 %res
+}
+
+declare i32 @case1()
+declare i32 @case2()
+declare i32 @caseD()
+declare i32 @getVal()
+declare i32 @llvm.ctpop.i32(i32)
+
+!0 = !{i32 1, i32 257}
+!1 = !{i32 2, i32 3}
+!2 = !{i32 2, i32 257}
+!3 = !{i32 1, i32 3}
+!4 = !{i32 0, i32 4}
diff --git a/test/Transforms/Util/lowerswitch.ll b/test/Transforms/Util/lowerswitch.ll
index 5f5134e..6344f17 100644
--- a/test/Transforms/Util/lowerswitch.ll
+++ b/test/Transforms/Util/lowerswitch.ll
@@ -1,11 +1,21 @@
; RUN: opt -lowerswitch -S < %s | FileCheck %s
; Test that we don't crash and have a different basic block for each incoming edge.
-define void @test0() {
+define void @test0(i32 %mode) {
; CHECK-LABEL: @test0
-; CHECK: %merge = phi i64 [ 1, %BB3 ], [ 0, %NodeBlock5 ], [ 0, %LeafBlock1 ], [ 0, %NewDefault ]
+;
+; CHECK: icmp eq i32 %mode, 4
+; CHECK-NEXT: label %BB3, label %NewDefault
+;
+; CHECK: icmp eq i32 %mode, 2
+; CHECK-NEXT: label %BB3, label %NewDefault
+;
+; CHECK: icmp eq i32 %mode, 0
+; CHECK-NEXT: label %BB3, label %NewDefault
+;
+; CHECK: %merge = phi i64 [ 1, %BB3 ], [ 0, %NewDefault ]
BB1:
- switch i32 undef, label %BB2 [
+ switch i32 %mode, label %BB2 [
i32 3, label %BB2
i32 5, label %BB2
i32 0, label %BB3
@@ -24,13 +34,13 @@
; Test switch cases that are merged into a single case during lowerswitch
; (take 84 and 85 below) - check that the number of incoming phi values match
; the number of branches.
-define void @test1() {
+define void @test1(i32 %mode) {
; CHECK-LABEL: @test1
entry:
br label %bb1
bb1:
- switch i32 undef, label %bb1 [
+ switch i32 %mode, label %bb1 [
i32 84, label %bb3
i32 85, label %bb3
i32 86, label %bb2
@@ -190,7 +200,7 @@
; Test that the PHI node in for.cond should have one entry for each predecessor
; of its parent basic block after lowerswitch merged several cases into a new
; default block.
-define void @test3() {
+define void @test3(i32 %mode) {
; CHECK-LABEL: @test3
entry:
br label %lbl1
@@ -232,7 +242,7 @@
br label %cleanup
cleanup: ; preds = %for.body7, %if.then4, %if.then
- switch i32 undef, label %unreachable [
+ switch i32 %mode, label %unreachable [
i32 0, label %for.cond
i32 2, label %lbl1
i32 5, label %for.cond
@@ -245,10 +255,10 @@
; Test that the PHI node in cleanup17 is removed as the switch default block is
; not reachable.
-define void @test4() {
+define void @test4(i32 %mode) {
; CHECK-LABEL: @test4
entry:
- switch i32 undef, label %cleanup17 [
+ switch i32 %mode, label %cleanup17 [
i32 0, label %return
i32 9, label %return
]
@@ -267,7 +277,7 @@
; Test that the PHI node in for.inc is updated correctly as the switch is
; replaced with a single branch to for.inc
-define void @test5() {
+define void @test5(i32 %mode) {
; CHECK-LABEL: @test5
entry:
br i1 undef, label %cleanup10, label %cleanup10.thread
@@ -276,7 +286,7 @@
br label %for.inc
cleanup10:
- switch i32 undef, label %unreachable [
+ switch i32 %mode, label %unreachable [
i32 0, label %for.inc
i32 4, label %for.inc
]
