[LowerSwitch][AMDGPU] Do not handle impossible values

[rtereshin]

Summary

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.

[arsenm]

I'm not sure I see why LowerSwitch needs to worry about this optimization. Why doesn't SimplifyCFG or DCE or one of some other control flow optimization pass handle this so LowerSwitch doesn't have to worry about it?

lib/Transforms/Utils/LowerSwitch.cpp

83 ↗

(On Diff #186392)

Does this need to use the default Function analysis usage?

test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll

6–9 ↗

(On Diff #186392)

The test checks are pretty thin. I think it would be better to explicitly check for what comparisons are done (if not just generate these)

[rtereshin]

In D58096#1394620, @arsenm wrote:

I'm not sure I see why LowerSwitch needs to worry about this optimization. Why doesn't SimplifyCFG or DCE or one of some other control flow optimization pass handle this so LowerSwitch doesn't have to worry about it?

Hi Matt,

Thank you for looking into this!

You're right, it is possible to achieve similar results with other passes, and I didn't investigate that beforehand much. Now I did and this is what I found:

1. The only passes that can help are exactly the ones that use LVI: JumpThreading and CorrelatedValuePropagation (if followed by SimplifyCFG to clean up)
2. We (a downstream GPU target) can't really do JumpThreading: it does too much and shapes CFG in ways that go against our performance targets
3. We are (re)considering doing CorrelatedValuePropagation at the moment, but:

3.1) It doesn't do much on top of eliminating dead BBs originated from lowering switches when tested on large suite of real-world shaders (there are some nice selects' eliminations here and there, but very rarely)
3.2) it consumes about 30 times more compile time than this patch using LVI within the LowerSwitch itself costs us on top of TOT LowerSwitch, which changes the extra cost from negligible to requiring consideration
3.3) In fact, it misses some of the cases and it does a poorer job eliminating dead BBs originated from LowerSwitch than this patch even in its current state (and I continue digging, looking at refining the value constraints analysis with computeKnownBits for instance, which can punch holes in the middle of the range with known trailing zeros)

Please let me know if you think this makes sense and if you'd like to see the LVI usage guarded by LowerSwitch's constructor variables & command line options, and if so, what's the acceptable default for it in your opinion.

I will address your other comments a bit later and update the patch, potentially making even more effort figuring out the constraints on the value.

[arsenm]

It seems weird to me that doing this somewhere else somehow ends up being more expensive, but this needs a comment somewhere explaining why it should be handled here

lib/Transforms/Utils/LowerSwitch.cpp

145 ↗

(On Diff #186392)

This is strange looking. I'm not sure what it really means to disable the dominator tree

448–450 ↗

(On Diff #186392)

These can be merged into one LLVM_DEBUG (and single quotes around \n)

[rtereshin]

In D58096#1398829, @arsenm wrote:

It seems weird to me that doing this somewhere else somehow ends up being more expensive, but this needs a comment somewhere explaining why it should be handled here

1. CorrelatedValuePropagation processes many kinds of instructions, LowerSwitch processes switches only.
2. Even if limited to icmp instructions only, CorrelatedValuePropagation when ran after LowerSwitch 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.

[rtereshin]

lib/Transforms/Utils/LowerSwitch.cpp

145 ↗

(On Diff #186392)

According to http://llvm.org/doxygen/classllvm_1_1LazyValueInfo.html#a5b29ad30fb31c6df2a3cbcefef8ae613 it "Disables use of the DominatorTree within LVI." As far as I can tell, the idea is that if LVI is allowed to use DT, DT needs to be valid at every point. As the LowerSwitch pass creates and deletes BBs as it goes, it will mean updating DT along the way using a DomTreeUpdater. Please see

commit 55da8a3a3e0af5afaa51f64c1385b2626c643317
Author: Brian M. Rzycki <[e-mail]>
Date:   Fri Feb 16 16:35:17 2018 +0000

    [JumpThreading] PR36133 enable/disable DominatorTree for LVI analysis

    Summary:
    The LazyValueInfo pass caches a copy of the DominatorTree when available.
    Whenever there are pending DominatorTree updates within JumpThreading's
    DeferredDominance object we cannot use the cached DT for LVI analysis.
    This commit adds the new methods enableDT() and disableDT() to LVI.
    JumpThreading also sets the appropriate usage model before calling LVI
    analysis methods.

    Fixes https://bugs.llvm.org/show_bug.cgi?id=36133

    Reviewers: sebpop, dberlin, kuhar

    Reviewed by: sebpop, kuhar

    Subscribers: uabelho, llvm-commits, aprantl, hiraditya, a.elovikov

    Differential Revision: https://reviews.llvm.org/D42717

for details.

I did't have time to investigate much neither how profitable it is to have the LVI using DT vs not using DT, nor what the compile time cost of using the updater, but from a quick glance it appeared that LVI only uses DT to do isValidAssumeForContext for assumptions from the AssumptionCache, which is kinda useless at least for us as we rarely if ever have any llvm.assume intrinsic calls on icmp's in the IR. Not to mention, isValidAssumeForContext can handle some of the cases even w/o a DT.

[rtereshin]

lib/Transforms/Utils/LowerSwitch.cpp

448–450 ↗

(On Diff #186392)

These can be merged into one LLVM_DEBUG

Sure, will do.

and single quotes around \n

Why?

grep -Eroh "<<\s*['\"]\\\?.['\"]" ./ --include='*.cpp' --include='*.h' --exclude-dir=build | grep -o "['\"]" | sort | uniq -c | sort -n

returns

6492 '
12003 "

(the example output of the first regex:

<< '"'
<< '['
<< '\n'
<< '\t'
<< '\n'
<< '\n'
<< "\n"
<< ":"
<< ":"
<< "\n"
<< "\n"
<< "\n"
<< "\n"
<< "\n"
<< "\n"
<< "\n"
<< " "

the current folder includes TOT llvm w/o clang or other projects)

[rtereshin]

lib/Transforms/Utils/LowerSwitch.cpp

83 ↗

(On Diff #186392)

I'm not sure what should be declared preserved here.

I tried removing LowerSwitch from the following pipelines:

-mtriple=amdgcn-amd-amdhsa -mcpu=gfx900
-O0 -mtriple=amdgcn-mesa-mesa3d -mcpu=bonaire
-mtriple=amdgcn-mesa-mesa3d -mcpu=bonaire
-march=r600 -mcpu=redwood

In no case it saved a re-computation of any of the analyses.

Do you have any suggestions?

[rtereshin]

1. Addressed comments
2. Refined the switch's operand constraints with known bits and added corresponding tests (all based on real-world cases)

[rtereshin]

Ping!

Is this good to go in?

Thanks,
Roman

[arsenm]

LGTM

lib/Transforms/Utils/LowerSwitch.cpp

83 ↗

(On Diff #186392)

I know if you don't call the base class analysis usage it causes problems with MachineFunctions, but not sure about IR passes

448–450 ↗

(On Diff #186392)

I don't remember where I saw this guideline, but apparently the character << is much cheaper for raw_ostream. I also just find using a string for a single character uglier.

494 ↗

(On Diff #186985)

Typo add's

[rtereshin]

Thank you!

lib/Transforms/Utils/LowerSwitch.cpp

83 ↗

(On Diff #186392)

Ah, true, I completely misunderstood you. AFAIK, for function passes the base class usage is empty and doesn't do anything.

448–450 ↗

(On Diff #186392)

I guess it depends on the tooling used to build it and operating system, And maybe on the version of LLVM as well.

I checked on macOS (llvm built by clang) as soon as you mentioned this, just printing a million new lines both ways. The time is exactly the same.

As for personal preferences, I guess they are just that. I find it a few keystrokes easier to change between "\n", ".\n", ":\n", " " and whatnot when they are all strings.

494 ↗

(On Diff #186985)

Not sure what do you mean. By add's I meant add instructions. I will replace it with that to avoid confusion, thanks!

[arsenm]

lib/Transforms/Utils/LowerSwitch.cpp

494 ↗

(On Diff #186985)

It's a plural, not a possessive so it should be adds

llvm/trunk/lib/Transforms/Utils/LowerSwitch.cpp

 // switch instruction until it is convenient.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #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"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #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"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <iterator>
 #include <limits>
public:
     static char ID;
 
     LowerSwitch() : FunctionPass(ID) {
       initializeLowerSwitchPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addRequired<LazyValueInfoWrapperPass>();
+    }
+
     struct CaseRange {
       ConstantInt* Low;
       ConstantInt* High;
       BasicBlock* BB;
 
       CaseRange(ConstantInt *low, ConstantInt *high, BasicBlock *bb)
           : Low(low), High(high), BB(bb) {}
     };
 
     using CaseVector = std::vector<CaseRange>;
     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);
   };
 
   /// The comparison function for sorting the switch case values in the vector.
   /// WARNING: Case ranges should be disjoint!
   struct CaseCmp {
     bool operator()(const LowerSwitch::CaseRange& C1,
                     const LowerSwitch::CaseRange& C2) {
       const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
       const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
       return CI1->getValue().slt(CI2->getValue());
     }
   };
 
 } // end anonymous namespace
 
 char LowerSwitch::ID = 0;
 
 // Publicly exposed interface to pass...
 char &llvm::LowerSwitchID = LowerSwitch::ID;
 
-INITIALIZE_PASS(LowerSwitch, "lowerswitch",
+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() {
   return new LowerSwitch();
 }
 
 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;
 
   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
     BasicBlock *Cur = &*I++; // Advance over block so we don't traverse new blocks
 
     // If the block is a dead Default block that will be deleted later, don't
     // waste time processing it.
     if (DeleteList.count(Cur))
       continue;
 
     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);
   }
 
   return Changed;
 }
 
 /// Used for debugging purposes.
 LLVM_ATTRIBUTE_USED
 static raw_ostream &operator<<(raw_ostream &O,
                                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 << "]";
 }
 
 /// Update the first occurrence of the "switch statement" BB in the PHI
 /// node with the "new" BB. The other occurrences will:
 ///
 /// 1) Be updated by subsequent calls to this function.  Switch statements may
 /// have more than one outcoming edge into the same BB if they all have the same
 /// value. When the switch statement is converted these incoming edges are now
 /// coming from multiple BBs.
 /// 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) {
     PHINode *PN = cast<PHINode>(I);
 
     // Only update the first occurrence.
     unsigned Idx = 0, E = PN->getNumIncomingValues();
     unsigned LocalNumMergedCases = NumMergedCases;

 /// a block emitted by one of the previous calls to switchConvert in the call
 /// stack.
 BasicBlock *
 LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
                            ConstantInt *UpperBound, Value *Val,
                            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) {
     // Check if the Case Range is perfectly squeezed in between
     // already checked Upper and Lower bounds. If it is then we can avoid
     // emitting the code that checks if the value actually falls in the range
     // 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;
   std::vector<CaseRange> LHS(Begin, Begin + Mid);
   LLVM_DEBUG(dbgs() << "LHS: " << LHS << "\n");
   std::vector<CaseRange> RHS(Begin + Mid, End);
   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
   // the smallest, so there is always a case range that has at least
   // a smaller value.
   ConstantInt *NewLowerBound = Pivot.Low;
 
   // Because NewLowerBound is never the smallest representable integer
   // it is safe here to subtract one.
   ConstantInt *NewUpperBound = ConstantInt::get(NewLowerBound->getContext(),
                                                 NewLowerBound->getValue() - 1);
 
   if (!UnreachableRanges.empty()) {
     // Check if the gap between LHS's highest and NewLowerBound is unreachable.
     int64_t GapLow = LHS.back().High->getSExtValue() + 1;
     int64_t GapHigh = NewLowerBound->getSExtValue() - 1;
     IntRange Gap = { GapLow, GapHigh };
     if (GapHigh >= GapLow && IsInRanges(Gap, UnreachableRanges))
       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.
   Function* F = OrigBlock->getParent();
   BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
 
   ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT,
                                 Val, Pivot.Low, "Pivot");
LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
   BranchInst::Create(LBranch, RBranch, Comp, NewNode);
   return NewNode;
 }
 
 /// Create a new leaf block for the binary lookup tree. It checks if the
 /// 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);
 
   // Emit comparison
   ICmpInst* Comp = nullptr;
   if (Leaf.Low == Leaf.High) {
     // Make the seteq instruction...
     Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_EQ, Val,
                         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,
                           "SwitchLeaf");
     } else {
       // Emit V-Lo <=u Hi-Lo
       Constant* NegLo = ConstantExpr::getNeg(Leaf.Low);
       Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo,
for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
     int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
     assert(BlockIdx != -1 && "Switch didn't go to this successor??");
     PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
   }
 
   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());
 
   // Merge case into clusters
   if (Cases.size() >= 2) {
     CaseItr I = Cases.begin();
     for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
       int64_t nextValue = J->Low->getSExtValue();
for (CaseItr J = std::next(I), E = Cases.end(); J != E; ++J) {
         // FIXME: Combine branch weights.
       } else if (++I != J) {
         *I = *J;
       }
     }
     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);
+  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<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;
 
     IntRange R = {std::numeric_limits<int64_t>::min(),
                   std::numeric_limits<int64_t>::max()};
     UnreachableRanges.push_back(R);
     for (const auto &I : Cases) {
for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();
       auto Next = I + 1;
       if (Next != E) {
         assert(Next->Low > I->High);
       }
     }
 #endif
 
     // As the default block in the switch is unreachable, update the PHI nodes
-    // (remove the entry to the default block) to reflect this.
+    // (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.
     assert(MaxPop > 0 && PopSucc);
     Default = PopSucc;
     Cases.erase(
         llvm::remove_if(
             Cases, [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }),
         Cases.end());
 
     // 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.
       for (unsigned I = 0 ; I < (MaxPop - 1) ; ++I)
         PopSucc->removePredecessor(OrigBlock);
       return;
     }
   }
 
-  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");
   F->getBasicBlockList().insert(Default->getIterator(), NewDefault);
   BranchInst::Create(Default, NewDefault);
 
   BasicBlock *SwitchBlock =
       switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
                     OrigBlock, OrigBlock, NewDefault, UnreachableRanges);
 
   // 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))
     DeleteList.insert(OldDefault);
 }

llvm/trunk/test/CodeGen/AMDGPU/valu-i1.ll

 ; RUN: llc -march=amdgcn -verify-machineinstrs -enable-misched -asm-verbose < %s | FileCheck -check-prefix=SI %s
 
 declare i32 @llvm.amdgcn.workitem.id.x() nounwind readnone
 
 ; SI-LABEL: {{^}}test_if:
 ; Make sure the i1 values created by the cfg structurizer pass are
 ; moved using VALU instructions
 
 
 ; 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
 ; SI-NEXT: s_xor_b64 [[SAVE2:s\[[0-9]+:[0-9]+\]]], exec, [[SAVE1]]
 ; SI-NEXT: ; mask branch [[FLOW_BB:BB[0-9]+_[0-9]+]]
 ; SI-NEXT: s_cbranch_execz [[FLOW_BB]]
 
 ; SI-NEXT: BB{{[0-9]+}}_1: ; %LeafBlock3
 ; SI:      s_mov_b64 s[{{[0-9]:[0-9]}}], -1
 ; SI:      s_and_saveexec_b64
 ; SI-NEXT: ; mask branch
 
 ; v_mov should be after exec modification
 ; SI: [[FLOW_BB]]:
 ; SI-NEXT: s_or_saveexec_b64 [[SAVE3:s\[[0-9]+:[0-9]+\]]], [[SAVE2]]
 ; SI-NEXT: s_xor_b64 exec, exec, [[SAVE3]]
 ; SI-NEXT: ; mask branch
 ;
 define amdgpu_kernel void @test_if(i32 %b, i32 addrspace(1)* %src, i32 addrspace(1)* %dst) #1 {
 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
 
 default:
   %cmp8 = icmp eq i32 %tid, 2
   %arrayidx10 = getelementptr i32, i32 addrspace(1)* %dst, i32 %b
   br i1 %cmp8, label %if, label %else

llvm/trunk/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll

+; 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}

llvm/trunk/test/Transforms/Util/lowerswitch.ll

 ; 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
     i32 2, label %BB3
     i32 4, label %BB3
   ]
 
 BB2:
   %merge = phi i64 [ 1, %BB3 ], [ 0, %BB1 ], [ 0, %BB1 ], [ 0, %BB1 ]
   ret void
 
 BB3:
   br label %BB2
 }
 
 ; 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
     i32 78, label %exit
     i32 99, label %bb3
   ]
 
 bb2:

 
 ._crit_edge:                                      ; preds = %34, %0
   ret void
 }
 
 ; 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
 
 lbl1:                                             ; preds = %cleanup, %entry
   br label %lbl2
 
 lbl2:                                             ; preds = %cleanup, %lbl1

 
 if.then4:                                         ; preds = %for.end
   br label %cleanup
 
 for.body7:                                        ; preds = %for.end
   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
     i32 3, label %lbl2
   ]
 
 unreachable:                                      ; preds = %cleanup
   unreachable
 }
 
 ; 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
   ]
 
 cleanup17:
 ; CHECK: cleanup17:
 ; CHECK-NOT: phi i16 [ undef, %entry ]
 ; CHECK: return:
 
   %retval.4 = phi i16 [ undef, %entry ]
   unreachable
 
 return:
   ret void
 }
 
 ; 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
 
 cleanup10.thread:
   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
   ]
 
 for.inc:
 ; CHECK: for.inc:
 ; CHECK-NEXT: phi i16 [ 0, %cleanup10.thread ], [ undef, %cleanup10 ]
 %0 = phi i16 [ undef, %cleanup10 ], [ 0, %cleanup10.thread ], [ undef, %cleanup10 ]
   unreachable
 
 unreachable:
   unreachable
 }