Index: llvm/trunk/lib/Transforms/Utils/LowerSwitch.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LowerSwitch.cpp +++ llvm/trunk/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(); + } + struct CaseRange { ConstantInt* Low; ConstantInt* High; @@ -90,15 +99,18 @@ using CaseItr = std::vector::iterator; private: - void processSwitchInst(SwitchInst *SI, SmallPtrSetImpl &DeleteList); + void processSwitchInst(SwitchInst *SI, + SmallPtrSetImpl &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 &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().getLVI(); + auto *ACT = getAnalysisIfAvailable(); + 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 DeleteList; @@ -142,11 +169,12 @@ if (SwitchInst *SI = dyn_cast(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::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 &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 &DeleteList) { - BasicBlock *CurBlock = SI->getParent(); - BasicBlock *OrigBlock = CurBlock; - Function *F = CurBlock->getParent(); + SmallPtrSetImpl &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); + if ((OrigBlock != &F->getEntryBlock() && pred_empty(OrigBlock)) || + OrigBlock->getSinglePredecessor() == OrigBlock) { + DeleteList.insert(OrigBlock); return; } + // Prepare cases vector. + CaseVector Cases; + const unsigned NumSimpleCases = Clusterify(Cases, SI); + LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() + << ". Total non-default cases: " << NumSimpleCases + << "\nCase clusters: " << Cases << "\n"); + // If there is only the default destination, just branch. - if (!SI->getNumCases()) { - BranchInst::Create(Default, CurBlock); + 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; } - // Prepare cases vector. - CaseVector Cases; - unsigned numCmps = Clusterify(Cases, SI); - LLVM_DEBUG(dbgs() << "Clusterify finished. Total clusters: " << Cases.size() - << ". Total compares: " << numCmps << "\n"); - LLVM_DEBUG(dbgs() << "Cases: " << Cases << "\n"); - (void)numCmps; - ConstantInt *LowerBound = nullptr; ConstantInt *UpperBound = nullptr; - std::vector UnreachableRanges; + bool DefaultIsUnreachableFromSwitch = false; if (isa(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 UnreachableRanges; + + if (DefaultIsUnreachableFromSwitch) { DenseMap 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)) Index: llvm/trunk/test/CodeGen/AMDGPU/valu-i1.ll =================================================================== --- llvm/trunk/test/CodeGen/AMDGPU/valu-i1.ll +++ llvm/trunk/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 Index: llvm/trunk/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll =================================================================== --- llvm/trunk/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll +++ llvm/trunk/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} Index: llvm/trunk/test/Transforms/Util/lowerswitch.ll =================================================================== --- llvm/trunk/test/Transforms/Util/lowerswitch.ll +++ llvm/trunk/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 ]