[SimplifyCFG] Run ReduceSwitchRange unconditionally, generalize

[shawnl]

Summary

This is patch 4 is a series beginning with D61150

Rather than gating on "isSwitchDense" (resulting in necessesarily
sparse lookup tables even when they were generated), always run
this quite cheap transform.

This transform is useful not just for generating tables.
LowerSwitch also wants this: read LowerSwitch.cpp:257.

Be careful to not generate worse code, by introducing a
SubThreshold heuristic.

Instead of just sorting by signed, generalize the finding of the
best base.

And now that it is run unconditionally, do not replicate its
functionality in SwitchToLookupTable (which could use a Sub
when having a hole is smaller, hence the SubThreshold
heuristic located in a single place).
This simplifies SwitchToLookupTable, and fixes
some ugly corner cases due to the use of signed numbers,
such as a table containing i16 32768 and 32769, of which
32769 would be interpreted as -32768, and now the code thinks
the table is size 65536.

(We still use unconditional subtraction when building a single-register mask,
but I think this whole block should go when the more general sparse
map is added, which doesn't leave empty holes in the table.)

And the reason test4 and test5 did not trigger was documented wrong:
it was because they were not considered sufficiently "dense".

[jmolloy]

Thanks! Much easier to review this time.

lib/Transforms/Utils/SimplifyCFG.cpp

5514

no -> so

5525

Can you mention why we're doing this? A naive reader may wonder why this might possibly return any value other than Values.back() - Values.front() + 1 (of course, a counterexample is the signed zero-crossing case mentioned in the diffbase).

5529

Please use capitals for induction variables, calculate the end value once, and use preincrement as per style guide:

for (unsigned I = 1, E = Values.size(); I != E; ++I) {

5537

Is this heuristic correct? From my understanding, SubThreshold is the number of table entries elided. BestDistance is the wrap distance.

But the number of table entries elided isn't the wrap distance, it's the Base that you calculate below (because by default we start counting from zero).

Am I wrong? I think this should be if (Base > SubThreshold ...)

5538

And if I'm right above, this whole clause goes away and the entire if becomes:

if (Values[BestIndex] >= SubThreshold)

test/Transforms/SimplifyCFG/X86/disable-lookup-table.ll

55–57

Can you please name the CreateSub() you added so it's not just a temporary? like "switch.reducerange" or something?

test/Transforms/SimplifyCFG/X86/switch-table-bug.ll

12–13

I particularly like this simplification :)

[jmolloy]

Thanks for the changes, just two comments!

lib/Transforms/Utils/SimplifyCFG.cpp

5445

This line is too complex. Please don't nest conditionals into function calls; use an extra line to set up the constant.

5530

Space after both ;'s.

The best way to do this is use git-clang-format, which I've recommended before.

[shawnl]

the old shifting code could create a invalid shl 32/64

[jmolloy]

LGTM, thanks for making the changes!

[lebedev.ri]

lib/Transforms/Utils/SimplifyCFG.cpp

5529

This wasn't done

[shawnl]

lib/Transforms/Utils/SimplifyCFG.cpp

5529

Oh I switched to using E in most places and I will use it here. I also ran git-clang-format.

[shawnl]

NFC

[shawnl]

applied 361727

lib/Transforms/Utils/SimplifyCFG.cpp

   SmallDenseMap<PHINode *, ResultListTy> ResultLists;
 
   SmallDenseMap<PHINode *, Constant *> DefaultResults;
   SmallDenseMap<PHINode *, Type *> ResultTypes;
   SmallVector<PHINode *, 4> PHIs;
 
   for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) {
     ConstantInt *CaseVal = CI->getCaseValue();
-    if (CaseVal->getValue().slt(MinCaseVal->getValue()))
+    if (CaseVal->getValue().ult(MinCaseVal->getValue()))
       MinCaseVal = CaseVal;
-    if (CaseVal->getValue().sgt(MaxCaseVal->getValue()))
+    if (CaseVal->getValue().ugt(MaxCaseVal->getValue()))
       MaxCaseVal = CaseVal;
 
     // Resulting value at phi nodes for this case value.
     using ResultsTy = SmallVector<std::pair<PHINode *, Constant *>, 4>;
     ResultsTy Results;
     if (!GetCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
                         Results, DL, TTI))
       return false;

   }
 
   // Keep track of the result types.
   for (PHINode *PHI : PHIs) {
     ResultTypes[PHI] = ResultLists[PHI][0].second->getType();
   }
 
   uint64_t NumResults = ResultLists[PHIs[0]].size();
-  APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue();
-  uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
+  uint64_t TableSize = MaxCaseVal->getValue().getLimitedValue() + 1;
   bool TableHasHoles = (NumResults < TableSize);
 
   // If the table has holes, we need a constant result for the default case
   // or a bitmask that fits in a register.
   SmallVector<std::pair<PHINode *, Constant *>, 4> DefaultResultsList;
   bool HasDefaultResults =
       GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest,
                      DefaultResultsList, DL, TTI);

 
   // Create the BB that does the lookups.
   Module &Mod = *CommonDest->getParent()->getParent();
   BasicBlock *LookupBB = BasicBlock::Create(
       Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest);
 
   // Compute the table index value.
   Builder.SetInsertPoint(SI);
-  Value *TableIndex;
-  if (MinCaseVal->isNullValue())
-    TableIndex = SI->getCondition();
-  else
-    TableIndex =
-        Builder.CreateSub(SI->getCondition(), MinCaseVal, "switch.tableidx");
+  Value *TableIndex = SI->getCondition();
 
   // Compute the maximum table size representable by the integer type we are
   // switching upon.
   unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits();
   uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize;
   assert(MaxTableSize >= TableSize &&
          "It is impossible for a switch to have more entries than the max "
          "representable value of its input integer type's size.");

   if (NeedMask) {
     // Before doing the lookup, we do the hole check. The LookupBB is therefore
     // re-purposed to do the hole check, and we create a new LookupBB.
     BasicBlock *MaskBB = LookupBB;
     MaskBB->setName("switch.hole_check");
     LookupBB = BasicBlock::Create(Mod.getContext(), "switch.lookup",
                                   CommonDest->getParent(), CommonDest);
 
+    // When doing the register-sized hole-check, unconditionally use a
+    // subtraction.
+    TableIndex = Builder.CreateSub(TableIndex, MinCaseVal);
+
     // Make the mask's bitwidth at least 8-bit and a power-of-2 to avoid
     // unnecessary illegal types.
     uint64_t TableSizePowOf2 = NextPowerOf2(std::max(7ULL, TableSize - 1ULL));
     APInt MaskInt(TableSizePowOf2, 0);
     APInt One(TableSizePowOf2, 1);
     // Build bitmask; fill in a 1 bit for every case.
     const ResultListTy &ResultList = ResultLists[PHIs[0]];
     for (size_t I = 0, E = ResultList.size(); I != E; ++I) {

   }
 
   bool ReturnedEarly = false;
   for (PHINode *PHI : PHIs) {
     const ResultListTy &ResultList = ResultLists[PHI];
 
     // If using a bitmask, use any value to fill the lookup table holes.
     Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI];
     StringRef FuncName = Fn->getName();
-    SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL,
-                            FuncName);
+    // Base is 0 unless using a hole check
+    ConstantInt *Base =
+        NeedMask ? MinCaseVal
+                 : ConstantInt::get(Mod.getContext(), APInt(CaseSize, 0));
+    SwitchLookupTable Table(Mod, TableSize, Base, ResultList, DV, DL, FuncName);
 
     Value *Result = Table.BuildLookup(TableIndex, Builder);
 
     // If the result is used to return immediately from the function, we want to
     // do that right here.
     if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->user_begin()) &&
         PHI->user_back() == CommonDest->getFirstNonPHIOrDbg()) {
       Builder.CreateRet(Result);

   SI->eraseFromParent();
 
   ++NumLookupTables;
   if (NeedMask)
     ++NumLookupTablesHoles;
   return true;
 }
 
-static bool isSwitchDense(ArrayRef<int64_t> Values) {
-  // See also SelectionDAGBuilder::isDense(), which this function was based on.
-  uint64_t Diff = (uint64_t)Values.back() - (uint64_t)Values.front();
-  uint64_t Range = Diff + 1;
-  uint64_t NumCases = Values.size();
-  // 40% is the default density for building a jump table in optsize/minsize
-  // mode.
-  uint64_t MinDensity = 40;
-
-  return NumCases * 100 >= Range * MinDensity;
-}
-
 /// Try to transform a switch that has "holes" in it to a contiguous sequence
 /// of cases.
 ///
 /// A switch such as: switch(i) {case 5: case 9: case 13: case 17:} can be
 /// range-reduced to: switch ((i-5) / 4) {case 0: case 1: case 2: case 3:}.
 ///
 /// This converts a sparse switch into a dense switch which allows better
 /// lowering and could also allow transforming into a lookup table.
 static bool ReduceSwitchRange(SwitchInst *SI, IRBuilder<> &Builder,
                               const DataLayout &DL,
                               const TargetTransformInfo &TTI) {
+  // The number of cases that need to be removed by a subtraction operation
+  // to make it worth using.
+  const unsigned SubThreshold = (SI->getFunction()->hasOptSize() ? 2 : 8);
   auto *CondTy = cast<IntegerType>(SI->getCondition()->getType());
-  if (CondTy->getIntegerBitWidth() > 64 ||
-      !DL.fitsInLegalInteger(CondTy->getIntegerBitWidth()))
+  unsigned BitWidth = CondTy->getIntegerBitWidth();
+  if (BitWidth > 64 || !DL.fitsInLegalInteger(BitWidth))
     return false;
   // Only bother with this optimization if there are more than 3 switch cases;
   // SDAG will only bother creating jump tables for 4 or more cases.
+  // This is also useful when using the LowerSwitch transform, but not with
+  // so few cases.
   if (SI->getNumCases() < 4)
     return false;
 
-  // This transform is agnostic to the signedness of the input or case values.
-  // We can treat the case values as signed or unsigned. We can optimize more
-  // common cases such as a sequence crossing zero {-4,0,4,8} if we interpret
-  // case values as signed.
-  SmallVector<int64_t, 4> Values;
+  // We organize the range to start from 0, if it is not already close.
+  SmallVector<uint64_t, 4> Values;
   for (auto &C : SI->cases())
-    Values.push_back(C.getCaseValue()->getValue().getSExtValue());
+    Values.push_back(C.getCaseValue()->getValue().getLimitedValue());
   llvm::sort(Values);
 
-  // If the switch is already dense, there's nothing useful to do here.
-  if (isSwitchDense(Values))
-    return false;
-
-  // First, transform the values such that they start at zero and ascend.
-  int64_t Base = Values[0];
-  for (auto &V : Values)
-    V -= (uint64_t)(Base);
+  bool MadeChanges = false;
+  // We must first look find the best start point, for example if we have a
+  // series that crosses zero: -2, -1, 0, 1, 2.
+  uint64_t BestDistance =
+      APInt::getMaxValue(CondTy->getIntegerBitWidth()).getLimitedValue() -
+      Values.back() + Values.front() + 1;
+  unsigned BestIndex = 0;
+  for (unsigned I = 1, E = Values.size(); I != E; I++) {
+    if (Values[I] - Values[I - 1] > BestDistance) {
+      BestIndex = I;
+      BestDistance = Values[I] - Values[I - 1];
+    }
+  }
+  uint64_t Base = 0;
+  // Now transform the values such that they start at zero and ascend.
+  if (Values[BestIndex] >= SubThreshold) {
+    Base = Values[BestIndex];
+    MadeChanges = true;
+    for (auto &V : Values)
+      V = (APInt(BitWidth, V) - Base).getLimitedValue();
+  }
 
   // Now we have signed numbers that have been shifted so that, given enough
   // precision, there are no negative values. Since the rest of the transform
   // is bitwise only, we switch now to an unsigned representation.
 
   // This transform can be done speculatively because it is so cheap - it
   // results in a single rotate operation being inserted.
   // FIXME: It's possible that optimizing a switch on powers of two might also
   // be beneficial - flag values are often powers of two and we could use a CLZ
   // as the key function.
 
   // countTrailingZeros(0) returns 64. As Values is guaranteed to have more than
   // one element and LLVM disallows duplicate cases, Shift is guaranteed to be
   // less than 64.
   unsigned Shift = 64;
   for (auto &V : Values)
-    Shift = std::min(Shift, countTrailingZeros((uint64_t)V);
+    Shift = std::min(Shift, countTrailingZeros(V));
   assert(Shift < 64);
-  if (Shift > 0)
+  if (Shift > 0) {
+    MadeChanges = true;
     for (auto &V : Values)
-      V = (int64_t)((uint64_t)V >> Shift);
+      V >>= Shift;
+  }
 
-  if (!isSwitchDense(Values))
-    // Transform didn't create a dense switch.
+  if (!MadeChanges)
+    // We didn't do anything.
     return false;
 
   // The obvious transform is to shift the switch condition right and emit a
   // check that the condition actually cleanly divided by GCD, i.e.
   //   C & (1 << Shift - 1) == 0
   // inserting a new CFG edge to handle the case where it didn't divide cleanly.
   //
   // A cheaper way of doing this is a simple ROTR(C, Shift). This performs the
   // shift and puts the shifted-off bits in the uppermost bits. If any of these
   // are nonzero then the switch condition will be very large and will hit the
   // default case.
 
   auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
   Builder.SetInsertPoint(SI);
-  auto *ShiftC = ConstantInt::get(Ty, Shift);
-  auto *Sub = Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base));
-  auto *LShr = Builder.CreateLShr(Sub, ShiftC);
-  auto *Shl = Builder.CreateShl(Sub, Ty->getBitWidth() - Shift);
-  auto *Rot = Builder.CreateOr(LShr, Shl);
-  SI->replaceUsesOfWith(SI->getCondition(), Rot);
+  Value *Key = SI->getCondition();
+  if (Base > 0)
+    Key = Builder.CreateSub(Key, ConstantInt::get(Ty, Base));
+  if (Shift > 0) {
+    // FIXME replace with fshr?
+    auto *ShiftC = ConstantInt::get(Ty, Shift);
+    auto *LShr = Builder.CreateLShr(Key, ShiftC);
+    auto *Shl = Builder.CreateShl(Key, Ty->getBitWidth() - Shift);
+    Key = Builder.CreateOr(LShr, Shl);
+  }
+  SI->replaceUsesOfWith(SI->getCondition(), Key);
 
   for (auto Case : SI->cases()) {
     auto *Orig = Case.getCaseValue();
     auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base);
-    Case.setValue(
-        cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(ShiftC->getValue()))));
+    Case.setValue(cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
   }
   return true;
 }
 
 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();
 
   if (isValueEqualityComparison(SI)) {

     return requestResimplify();
 
   if (switchToSelect(SI, Builder, DL, TTI))
     return requestResimplify();
 
   if (Options.ForwardSwitchCondToPhi && ForwardSwitchConditionToPHI(SI))
     return requestResimplify();
 
+  if (ReduceSwitchRange(SI, Builder, DL, TTI))
+    return requestResimplify();
+
   // The conversion from switch to lookup tables results in difficult-to-analyze
   // code and makes pruning branches much harder. This is a problem if the
   // switch expression itself can still be restricted as a result of inlining or
   // CVP. Therefore, only apply this transformation during late stages of the
   // optimisation pipeline.
   if (Options.ConvertSwitchToLookupTable &&
       SwitchToLookupTable(SI, Builder, DL, TTI))
     return requestResimplify();
 
-  if (ReduceSwitchRange(SI, Builder, DL, TTI))
-    return requestResimplify();
-
   return false;
 }
 
 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();
   bool Changed = false;
 
   // Eliminate redundant destinations.

test/Transforms/SimplifyCFG/X86/disable-lookup-table.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -switch-to-lookup -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
 ; RUN: opt < %s -passes='simplify-cfg<switch-to-lookup>' -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
 
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 ; In the presence of "-no-jump-tables"="true", simplifycfg should not convert switches to lookup tables.
 
 ; CHECK: @switch.table.bar = private unnamed_addr constant [4 x i32] [i32 55, i32 123, i32 0, i32 -1]
 ; CHECK-LABEL: foo
 ; CHECK-NOT: @switch.table.foo = private unnamed_addr constant [4 x i32] [i32 55, i32 123, i32 0, i32 -1]
 
 define i32 @foo(i32 %c) "no-jump-tables"="true" {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 42, label [[RETURN:%.*]]
-; CHECK-NEXT:    i32 43, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i32 44, label [[SW_BB2:%.*]]
-; CHECK-NEXT:    i32 45, label [[SW_BB3:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[C:%.*]], 42
+; CHECK-NEXT:    switch i32 [[TMP0]], label [[SW_DEFAULT:%.*]] [
+; CHECK-NEXT:    i32 0, label [[RETURN:%.*]]
+; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
+; CHECK-NEXT:    i32 2, label [[SW_BB2:%.*]]
+; CHECK-NEXT:    i32 3, label [[SW_BB3:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       sw.bb1:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       sw.bb2:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       sw.bb3:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       sw.default:
return:
   %retval.0 = phi i32 [ 15, %sw.default ],  [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
   ret i32 %retval.0
 }
 
 
 define i32 @bar(i32 %c) {
 ; CHECK-LABEL: @bar(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 42
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 4
-; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[C:%.*]], 42
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.bar, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.bar, i32 0, i32 [[TMP0]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 15
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 42, label %return

test/Transforms/SimplifyCFG/X86/switch-covered-bug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -simplifycfg -switch-to-lookup < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
 ; RUN: opt -S -passes='simplify-cfg<switch-to-lookup>' < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
 
 ; rdar://17887153
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin12.0.0"
 
 define i64 @test(i3 %arg) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[ARG:%.*]], -4
-; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i4
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i64], [8 x i64]* @switch.table.test, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i3 [[ARG:%.*]], -1
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[DEFAULT:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[ARG]] to i4
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i64], [7 x i64]* @switch.table.test, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, i64* [[SWITCH_GEP]]
-; CHECK-NEXT:    [[V3:%.*]] = add i64 [[SWITCH_LOAD]], 0
+; CHECK-NEXT:    br label [[DEFAULT]]
+; CHECK:       Default:
+; CHECK-NEXT:    [[V1:%.*]] = phi i64 [ 8, [[ENTRY:%.*]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
+; CHECK-NEXT:    [[V3:%.*]] = add i64 [[V1]], 0
 ; CHECK-NEXT:    ret i64 [[V3]]
 ;
 entry:
   switch i3 %arg, label %Default [
   i3 -2, label %Label6
   i3 1, label %Label1
   i3 2, label %Label2
   i3 3, label %Label3

test/Transforms/SimplifyCFG/X86/switch-table-bug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -simplifycfg -switch-to-lookup < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
 ; RUN: opt -S -passes='simplify-cfg<switch-to-lookup>' < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
 
 ; rdar://17735071
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin12.0.0"
 
 define i64 @_TFO6reduce1E5toRawfS0_FT_Si(i2) {
 ; CHECK-LABEL: @_TFO6reduce1E5toRawfS0_FT_Si(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i2 [[TMP0:%.*]], -2
-; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i2 [[SWITCH_TABLEIDX]] to i3
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i64], [4 x i64]* @switch.table._TFO6reduce1E5toRawfS0_FT_Si, i32 0, i3 [[SWITCH_TABLEIDX_ZEXT]]
-; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, i64* [[SWITCH_GEP]]
-; CHECK-NEXT:    ret i64 [[SWITCH_LOAD]]
+; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = zext i2 [[TMP0:%.*]] to i64
+; CHECK-NEXT:    ret i64 [[SWITCH_IDX_CAST]]
 ;
 entry:
   switch i2 %0, label %1 [
   i2 0, label %2
   i2 1, label %3
   i2 -2, label %4
   i2 -1, label %5
   ]

test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

 ; A simple int-to-int selection switch.
 ; It is dense enough to be replaced by table lookup.
 ; The result is directly by a ret from an otherwise empty bb,
 ; so we return early, directly from the lookup bb.
 
 define i32 @f(i32 %c) {
 ; CHECK-LABEL: @f(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 42
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 7
-; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[C:%.*]], 42
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 7
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i32], [7 x i32]* @switch.table.f, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i32], [7 x i32]* @switch.table.f, i32 0, i32 [[TMP0]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 15
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 42, label %return

 
 }
 
 ; Same thing, but with i8's
 
 define i8 @char(i32 %c) {
 ; CHECK-LABEL: @char(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 42
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 9
-; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[C:%.*]], 42
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 9
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i8], [9 x i8]* @switch.table.char, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i8], [9 x i8]* @switch.table.char, i32 0, i32 [[TMP0]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i8, i8* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i8 [[SWITCH_LOAD]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i8 15
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 42, label %return

 ; can be packed into a bitmap.
 
 define i32 @crud(i8 zeroext %c)  {
 ; CHECK-LABEL: @crud(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[C:%.*]], 33
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOR_END:%.*]], label [[SWITCH_EARLY_TEST:%.*]]
 ; CHECK:       switch.early.test:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i8 [[C]], 34
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[SWITCH_TABLEIDX]], 59
-; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[LOR_END]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[C]], 34
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[TMP0]], 59
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[LOR_END]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[SWITCH_TABLEIDX]] to i59
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[TMP0]] to i59
 ; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i59 [[SWITCH_CAST]], 1
 ; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i59 -288230375765830623, [[SWITCH_SHIFTAMT]]
 ; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i59 [[SWITCH_DOWNSHIFT]] to i1
 ; CHECK-NEXT:    br label [[LOR_END]]
 ; CHECK:       lor.end:
-; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[SWITCH_MASKED]], [[SWITCH_LOOKUP]] ], [ false, [[SWITCH_EARLY_TEST]] ]
-; CHECK-NEXT:    [[LOR_EXT:%.*]] = zext i1 [[TMP1]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[SWITCH_MASKED]], [[SWITCH_LOOKUP]] ], [ false, [[SWITCH_EARLY_TEST]] ]
+; CHECK-NEXT:    [[LOR_EXT:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[LOR_EXT]]
 ;
 entry:
   %cmp = icmp ult i8 %c, 33
   br i1 %cmp, label %lor.end, label %switch.early.test
 
 switch.early.test:
   switch i8 %c, label %lor.rhs [
lor.end:
   ret i32 %lor.ext
 
 }
 
 ; PR13946
 define i32 @overflow(i32 %type) {
 ; CHECK-LABEL: @overflow(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 [[TYPE:%.*]], label [[IF_END:%.*]] [
-; CHECK-NEXT:    i32 3, label [[SW_BB3:%.*]]
-; CHECK-NEXT:    i32 -2147483645, label [[SW_BB3]]
-; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i32 2, label [[SW_BB2:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[TYPE:%.*]], -2147483645
+; CHECK-NEXT:    switch i32 [[TMP0]], label [[IF_END:%.*]] [
+; CHECK-NEXT:    i32 -2147483648, label [[SW_BB3:%.*]]
+; CHECK-NEXT:    i32 0, label [[SW_BB3]]
+; CHECK-NEXT:    i32 2147483646, label [[SW_BB1:%.*]]
+; CHECK-NEXT:    i32 2147483647, label [[SW_BB2:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       sw.bb1:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       sw.bb2:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       sw.bb3:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:

 ; CHECK: large
 ; CHECK-NOT: switch i32
 define i32 @large(i32 %x) {
 ; CHECK-LABEL: @large(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X]], -10
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[CMP]], i32 [[MUL]], i32 [[X]]
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[SPEC_SELECT]], 1
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 199
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SPEC_SELECT]], 200
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [199 x i32], [199 x i32]* @switch.table.large, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [200 x i32], [200 x i32]* @switch.table.large, i32 0, i32 [[SPEC_SELECT]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %cmp = icmp slt i32 %x, 0
   br i1 %cmp, label %if.then, label %if.end

 return:
   %retval.0 = phi i32 [ 39204, %sw.bb202 ], [ 38809, %sw.bb201 ], [ 38416, %sw.bb200 ], [ 38025, %sw.bb199 ], [ 37636, %sw.bb198 ], [ 37249, %sw.bb197 ], [ 36864, %sw.bb196 ], [ 36481, %sw.bb195 ], [ 36100, %sw.bb194 ], [ 35721, %sw.bb193 ], [ 35344, %sw.bb192 ], [ 34969, %sw.bb191 ], [ 34596, %sw.bb190 ], [ 34225, %sw.bb189 ], [ 33856, %sw.bb188 ], [ 33489, %sw.bb187 ], [ 33124, %sw.bb186 ], [ 32761, %sw.bb185 ], [ 32400, %sw.bb184 ], [ 32041, %sw.bb183 ], [ 31684, %sw.bb182 ], [ 31329, %sw.bb181 ], [ 30976, %sw.bb180 ], [ 30625, %sw.bb179 ], [ 30276, %sw.bb178 ], [ 29929, %sw.bb177 ], [ 29584, %sw.bb176 ], [ 29241, %sw.bb175 ], [ 28900, %sw.bb174 ], [ 28561, %sw.bb173 ], [ 28224, %sw.bb172 ], [ 27889, %sw.bb171 ], [ 27556, %sw.bb170 ], [ 27225, %sw.bb169 ], [ 26896, %sw.bb168 ], [ 26569, %sw.bb167 ], [ 26244, %sw.bb166 ], [ 25921, %sw.bb165 ], [ 25600, %sw.bb164 ], [ 25281, %sw.bb163 ], [ 24964, %sw.bb162 ], [ 24649, %sw.bb161 ], [ 24336, %sw.bb160 ], [ 24025, %sw.bb159 ], [ 23716, %sw.bb158 ], [ 23409, %sw.bb157 ], [ 23104, %sw.bb156 ], [ 22801, %sw.bb155 ], [ 22500, %sw.bb154 ], [ 22201, %sw.bb153 ], [ 21904, %sw.bb152 ], [ 21609, %sw.bb151 ], [ 21316, %sw.bb150 ], [ 21025, %sw.bb149 ], [ 20736, %sw.bb148 ], [ 20449, %sw.bb147 ], [ 20164, %sw.bb146 ], [ 19881, %sw.bb145 ], [ 19600, %sw.bb144 ], [ 19321, %sw.bb143 ], [ 19044, %sw.bb142 ], [ 18769, %sw.bb141 ], [ 18496, %sw.bb140 ], [ 18225, %sw.bb139 ], [ 17956, %sw.bb138 ], [ 17689, %sw.bb137 ], [ 17424, %sw.bb136 ], [ 17161, %sw.bb135 ], [ 16900, %sw.bb134 ], [ 16641, %sw.bb133 ], [ 16384, %sw.bb132 ], [ 16129, %sw.bb131 ], [ 15876, %sw.bb130 ], [ 15625, %sw.bb129 ], [ 15376, %sw.bb128 ], [ 15129, %sw.bb127 ], [ 14884, %sw.bb126 ], [ 14641, %sw.bb125 ], [ 14400, %sw.bb124 ], [ 14161, %sw.bb123 ], [ 13924, %sw.bb122 ], [ 13689, %sw.bb121 ], [ 13456, %sw.bb120 ], [ 13225, %sw.bb119 ], [ 12996, %sw.bb118 ], [ 12769, %sw.bb117 ], [ 12544, %sw.bb116 ], [ 12321, %sw.bb115 ], [ 12100, %sw.bb114 ], [ 11881, %sw.bb113 ], [ 11664, %sw.bb112 ], [ 11449, %sw.bb111 ], [ 11236, %sw.bb110 ], [ 11025, %sw.bb109 ], [ 10816, %sw.bb108 ], [ 10609, %sw.bb107 ], [ 10404, %sw.bb106 ], [ 10201, %sw.bb105 ], [ 10000, %sw.bb104 ], [ 9801, %sw.bb103 ], [ 9604, %sw.bb102 ], [ 9409, %sw.bb101 ], [ 9216, %sw.bb100 ], [ 9025, %sw.bb99 ], [ 8836, %sw.bb98 ], [ 8649, %sw.bb97 ], [ 8464, %sw.bb96 ], [ 8281, %sw.bb95 ], [ 8100, %sw.bb94 ], [ 7921, %sw.bb93 ], [ 7744, %sw.bb92 ], [ 7569, %sw.bb91 ], [ 7396, %sw.bb90 ], [ 7225, %sw.bb89 ], [ 7056, %sw.bb88 ], [ 6889, %sw.bb87 ], [ 6724, %sw.bb86 ], [ 6561, %sw.bb85 ], [ 6400, %sw.bb84 ], [ 6241, %sw.bb83 ], [ 6084, %sw.bb82 ], [ 5929, %sw.bb81 ], [ 5776, %sw.bb80 ], [ 5625, %sw.bb79 ], [ 5476, %sw.bb78 ], [ 5329, %sw.bb77 ], [ 5184, %sw.bb76 ], [ 5112, %sw.bb74 ], [ 4900, %sw.bb73 ], [ 4761, %sw.bb72 ], [ 4624, %sw.bb71 ], [ 4489, %sw.bb70 ], [ 4356, %sw.bb69 ], [ 4225, %sw.bb68 ], [ 4096, %sw.bb67 ], [ 3969, %sw.bb66 ], [ 3844, %sw.bb65 ], [ 3721, %sw.bb64 ], [ 3600, %sw.bb63 ], [ 3481, %sw.bb62 ], [ 3364, %sw.bb61 ], [ 3249, %sw.bb60 ], [ 3136, %sw.bb59 ], [ 3025, %sw.bb58 ], [ 2970, %sw.bb56 ], [ 2809, %sw.bb55 ], [ 2704, %sw.bb54 ], [ 2601, %sw.bb53 ], [ 2500, %sw.bb52 ], [ 2401, %sw.bb51 ], [ 2304, %sw.bb50 ], [ 2209, %sw.bb49 ], [ 2116, %sw.bb48 ], [ 2025, %sw.bb47 ], [ 1980, %sw.bb45 ], [ 1849, %sw.bb44 ], [ 1764, %sw.bb43 ], [ 1681, %sw.bb42 ], [ 1600, %sw.bb41 ], [ 1521, %sw.bb40 ], [ 1444, %sw.bb39 ], [ 1369, %sw.bb38 ], [ 1296, %sw.bb37 ], [ 1260, %sw.bb35 ], [ 1156, %sw.bb34 ], [ 1089, %sw.bb33 ], [ 1024, %sw.bb32 ], [ 961, %sw.bb31 ], [ 900, %sw.bb30 ], [ 841, %sw.bb29 ], [ 784, %sw.bb28 ], [ 729, %sw.bb27 ], [ 676, %sw.bb26 ], [ 625, %sw.bb25 ], [ 576, %sw.bb24 ], [ 529, %sw.bb23 ], [ 484, %sw.bb22 ], [ 441, %sw.bb21 ], [ 400, %sw.bb20 ], [ 361, %sw.bb19 ], [ 342, %sw.bb18 ], [ 289, %sw.bb17 ], [ 256, %sw.bb16 ], [ 225, %sw.bb15 ], [ 196, %sw.bb14 ], [ 169, %sw.bb13 ], [ 144, %sw.bb12 ], [ 121, %sw.bb11 ], [ 100, %sw.bb10 ], [ 81, %sw.bb9 ], [ 64, %sw.bb8 ], [ 49, %sw.bb7 ], [ 36, %sw.bb6 ], [ 25, %sw.bb5 ], [ 16, %sw.bb4 ], [ 9, %sw.bb3 ], [ 4, %sw.bb2 ], [ 1, %sw.bb1 ], [ 39601, %sw.bb203 ], [ 0, %if.end ]
   ret i32 %retval.0
 }
 
 define i32 @cprop(i32 %x, i32 %y) {
 ; CHECK-LABEL: @cprop(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 7
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 8
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i32], [7 x i32]* @switch.table.cprop, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], [8 x i32]* @switch.table.cprop, i32 0, i32 [[X]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 123
 ;
 entry:
   switch i32 %x, label %sw.default [
   i32 1, label %return
return:
   ret i32 %retval
 
 }
 
 ; Don't create a table with illegal type
 define i96 @illegaltype(i32 %c) {
 ; CHECK-LABEL: @illegaltype(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 42, label [[RETURN:%.*]]
-; CHECK-NEXT:    i32 43, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i32 44, label [[SW_BB2:%.*]]
-; CHECK-NEXT:    i32 45, label [[SW_BB3:%.*]]
-; CHECK-NEXT:    i32 46, label [[SW_BB4:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[C:%.*]], 42
+; CHECK-NEXT:    switch i32 [[TMP0]], label [[SW_DEFAULT:%.*]] [
+; CHECK-NEXT:    i32 0, label [[RETURN:%.*]]
+; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
+; CHECK-NEXT:    i32 2, label [[SW_BB2:%.*]]
+; CHECK-NEXT:    i32 3, label [[SW_BB3:%.*]]
+; CHECK-NEXT:    i32 4, label [[SW_BB4:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       sw.bb1:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       sw.bb2:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       sw.bb3:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       sw.bb4:

 ; CHECK-LABEL: @nodefaultwithholes(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[C:%.*]], 6
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_HOLE_CHECK:%.*]], label [[SW_DEFAULT:%.*]]
 ; CHECK:       sw.default:
 ; CHECK-NEXT:    call void @exit(i32 1)
 ; CHECK-NEXT:    unreachable
 ; CHECK:       switch.hole_check:
-; CHECK-NEXT:    [[SWITCH_MASKINDEX:%.*]] = trunc i32 [[C]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[C]], 0
+; CHECK-NEXT:    [[SWITCH_MASKINDEX:%.*]] = trunc i32 [[TMP1]] to i8
 ; CHECK-NEXT:    [[SWITCH_SHIFTED:%.*]] = lshr i8 47, [[SWITCH_MASKINDEX]]
 ; CHECK-NEXT:    [[SWITCH_LOBIT:%.*]] = trunc i8 [[SWITCH_SHIFTED]] to i1
 ; CHECK-NEXT:    br i1 [[SWITCH_LOBIT]], label [[SWITCH_LOOKUP:%.*]], label [[SW_DEFAULT]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i32], [6 x i32]* @switch.table.nodefaultwithholes, i32 0, i32 [[C]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i32], [6 x i32]* @switch.table.nodefaultwithholes, i32 0, i32 [[TMP1]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 0, label %return
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2
return:
   [ getelementptr inbounds ([3 x i32], [3 x i32]* @dllimport_a, i32 0, i32 0), %entry ]
   ret i32* %retval.0
 }
 
 ; We can use linear mapping.
 define i8 @linearmap1(i32 %c) {
 ; CHECK-LABEL: @linearmap1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 10
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 4
-; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[C:%.*]], 10
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[SWITCH_TABLEIDX]] to i8
+; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[TMP0]] to i8
 ; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul i8 [[SWITCH_IDX_CAST]], -5
 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i8 [[SWITCH_IDX_MULT]], 18
 ; CHECK-NEXT:    ret i8 [[SWITCH_OFFSET]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i8 3
 ;
 entry:
   switch i32 %c, label %sw.default [
return:
   %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 8, %sw.bb2 ], [ 13, %sw.bb1 ], [ 18, %entry ]
   ret i8 %x
 }
 
 ; Linear mapping in a different configuration.
 define i32 @linearmap2(i8 %c) {
 ; CHECK-LABEL: @linearmap2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i8 [[C:%.*]], -13
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[SWITCH_TABLEIDX]], 4
-; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[C:%.*]], -13
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[TMP0]], 4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = zext i8 [[SWITCH_TABLEIDX]] to i32
+; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = zext i8 [[TMP0]] to i32
 ; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add i32 [[SWITCH_IDX_CAST]], 18
 ; CHECK-NEXT:    ret i32 [[SWITCH_OFFSET]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 3
 ;
 entry:
   switch i8 %c, label %sw.default [
   i8 -10, label %return
return:
   %x = phi i32 [ 3, %sw.default ], [ 18, %sw.bb3 ], [ 19, %sw.bb2 ], [ 20, %sw.bb1 ], [ 21, %entry ]
   ret i32 %x
 }
 
 ; Linear mapping with overflows.
 define i8 @linearmap3(i32 %c) {
 ; CHECK-LABEL: @linearmap3(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 10
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 4
-; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[C:%.*]], 10
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[SWITCH_TABLEIDX]] to i8
+; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[TMP0]] to i8
 ; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul i8 [[SWITCH_IDX_CAST]], 100
 ; CHECK-NEXT:    ret i8 [[SWITCH_IDX_MULT]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i8 3
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 10, label %return
return:
   %x = phi i8 [ 3, %sw.default ], [ 44, %sw.bb3 ], [ -56, %sw.bb2 ], [ 100, %sw.bb1 ], [ 0, %entry ]
   ret i8 %x
 }
 
 ; Linear mapping with with multiplier 1 and offset 0.
 define i8 @linearmap4(i32 %c) {
 ; CHECK-LABEL: @linearmap4(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], -2
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 4
-; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[C:%.*]], -2
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[SWITCH_TABLEIDX]] to i8
+; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[TMP0]] to i8
 ; CHECK-NEXT:    ret i8 [[SWITCH_IDX_CAST]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i8 3
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 -2, label %return
   i32 -1, label %sw.bb1

 
 ; Make sure we do not crash due to trying to generate an unguarded
 ; lookup (since i3 can only hold values in the range of explicit
 ; values) and simultaneously trying to generate a branch to deal with
 ; the fact that we have holes in the range.
 define i32 @covered_switch_with_bit_tests(i3) {
 ; CHECK-LABEL: @covered_switch_with_bit_tests(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[TMP0:%.*]], -4
-; CHECK-NEXT:    [[SWITCH_MASKINDEX:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i8
-; CHECK-NEXT:    [[SWITCH_SHIFTED:%.*]] = lshr i8 -61, [[SWITCH_MASKINDEX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i3 [[TMP0:%.*]], -2
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_HOLE_CHECK:%.*]], label [[L6:%.*]]
+; CHECK:       switch.hole_check:
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i3 [[TMP0]], 2
+; CHECK-NEXT:    [[SWITCH_MASKINDEX:%.*]] = zext i3 [[TMP2]] to i8
+; CHECK-NEXT:    [[SWITCH_SHIFTED:%.*]] = lshr i8 15, [[SWITCH_MASKINDEX]]
 ; CHECK-NEXT:    [[SWITCH_LOBIT:%.*]] = trunc i8 [[SWITCH_SHIFTED]] to i1
-; CHECK-NEXT:    br i1 [[SWITCH_LOBIT]], label [[SWITCH_LOOKUP:%.*]], label [[L6:%.*]]
+; CHECK-NEXT:    br i1 [[SWITCH_LOBIT]], label [[SWITCH_LOOKUP:%.*]], label [[L6]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i4
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], [8 x i32]* @switch.table.covered_switch_with_bit_tests, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
+; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[TMP2]] to i4
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i32], [6 x i32]* @switch.table.covered_switch_with_bit_tests, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
 ; CHECK-NEXT:    br label [[L6]]
 ; CHECK:       l6:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[SWITCH_HOLE_CHECK]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   switch i3 %0, label %l6 [
   i3 -3, label %l5
   i3 -4, label %l5
   i3 3, label %l1
   i3 2, label %l1

test/Transforms/SimplifyCFG/rangereduce.ll

two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 ; Optimization shouldn't trigger; not an arithmetic progression
 define i32 @test4(i32 %a) {
 ; CHECK-LABEL: @test4(
-; CHECK-NEXT:    switch i32 [[A:%.*]], label [[DEF:%.*]] [
-; CHECK-NEXT:    i32 97, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 102, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 105, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 109, label [[THREE]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
+; CHECK-NEXT:    switch i32 [[TMP1]], label [[DEF:%.*]] [
+; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
+; CHECK-NEXT:    i32 5, label [[TWO:%.*]]
+; CHECK-NEXT:    i32 8, label [[THREE:%.*]]
+; CHECK-NEXT:    i32 12, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]
 ; CHECK:       one:
 ; CHECK-NEXT:    br label [[DEF]]
 ; CHECK:       two:
 ; CHECK-NEXT:    br label [[DEF]]
two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 ; Optimization shouldn't trigger; not a power of two
 define i32 @test5(i32 %a) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    switch i32 [[A:%.*]], label [[DEF:%.*]] [
-; CHECK-NEXT:    i32 97, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 102, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 107, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 112, label [[THREE]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
+; CHECK-NEXT:    switch i32 [[TMP1]], label [[DEF:%.*]] [
+; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
+; CHECK-NEXT:    i32 5, label [[TWO:%.*]]
+; CHECK-NEXT:    i32 10, label [[THREE:%.*]]
+; CHECK-NEXT:    i32 15, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]
 ; CHECK:       one:
 ; CHECK-NEXT:    br label [[DEF]]
 ; CHECK:       two:
 ; CHECK-NEXT:    br label [[DEF]]

 two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i32 @test9(i32 %a) {
 ; CHECK-LABEL: @test9(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 6
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 1
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 31
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
-; CHECK-NEXT:    i32 6, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 7, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 0, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 2, label [[THREE]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[A:%.*]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 [[A]], 31
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    switch i32 [[TMP3]], label [[DEF:%.*]] [
+; CHECK-NEXT:    i32 9, label [[ONE:%.*]]
+; CHECK-NEXT:    i32 10, label [[TWO:%.*]]
+; CHECK-NEXT:    i32 3, label [[THREE:%.*]]
+; CHECK-NEXT:    i32 5, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]
 ; CHECK:       one:
 ; CHECK-NEXT:    br label [[DEF]]
 ; CHECK:       two:
 ; CHECK-NEXT:    br label [[DEF]]

test/Transforms/SimplifyCFG/switch-dead-default.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -S -passes='simplify-cfg<switch-to-lookup>' | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 declare void @foo(i32)
 
 define void @test(i1 %a) {
 ; CHECK-LABEL: @test(
-; CHECK-NEXT:    br i1 [[A:%.*]], label [[TRUE:%.*]], label [[FALSE:%.*]]
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i1 [[A:%.*]], true
+; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i1 [[A_OFF]], true
+; CHECK-NEXT:    br i1 [[SWITCH]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ;
   switch i1 %a, label %default [i1 1, label %true
   i1 0, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 }
 
 define void @test2(i2 %a) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    switch i2 [[A:%.*]], label [[DEFAULT1:%.*]] [
 ; CHECK-NEXT:    i2 0, label [[CASE0:%.*]]
 ; CHECK-NEXT:    i2 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    i2 -2, label [[CASE2:%.*]]
 ; CHECK-NEXT:    i2 -1, label [[CASE3:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       case0:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case1:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case2:
-; CHECK-NEXT:    tail call void @foo(i32 2)
+; CHECK-NEXT:    call void @foo(i32 2)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case3:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ; CHECK:       default1:
 ; CHECK-NEXT:    unreachable
 ;
   switch i2 %a, label %default [i2 0, label %case0
   i2 1, label %case1
   i2 2, label %case2
   i2 3, label %case3]

 define void @test3(i2 %a) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    switch i2 [[A:%.*]], label [[DEFAULT:%.*]] [
 ; CHECK-NEXT:    i2 0, label [[CASE0:%.*]]
 ; CHECK-NEXT:    i2 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    i2 -2, label [[CASE2:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       case0:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case1:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case2:
-; CHECK-NEXT:    tail call void @foo(i32 2)
+; CHECK-NEXT:    call void @foo(i32 2)
 ; CHECK-NEXT:    ret void
 ; CHECK:       default:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ;
   switch i2 %a, label %default [i2 0, label %case0
   i2 1, label %case1
   i2 2, label %case2]
 
 case0:
   call void @foo(i32 0)

 ; number of possible cases.
 define void @test4(i128 %a) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    switch i128 [[A:%.*]], label [[DEFAULT:%.*]] [
 ; CHECK-NEXT:    i128 0, label [[CASE0:%.*]]
 ; CHECK-NEXT:    i128 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       case0:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case1:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       default:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ;
   switch i128 %a, label %default [i128 0, label %case0
   i128 1, label %case1]
 
 case0:
   call void @foo(i32 0)
   ret void
 case1:
   call void @foo(i32 1)
   ret void
 default:
   call void @foo(i32 0)
   ret void
 }
 
 ; All but one bit known zero
 define void @test5(i8 %a) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[A:%.*]], 2
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[SWITCH:%.*]] = icmp eq i8 [[A]], 1
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i8 [[A]], -1
+; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i8 [[A_OFF]], 1
 ; CHECK-NEXT:    br i1 [[SWITCH]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ;
   %cmp = icmp ult i8 %a, 2
   call void @llvm.assume(i1 %cmp)
   switch i8 %a, label %default [i8 1, label %true
   i8 0, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 }
 
 ;; All but one bit known one
 define void @test6(i8 %a) {
 ; CHECK-LABEL: @test6(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[A:%.*]], -3
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[SWITCH:%.*]] = icmp eq i8 [[A]], -1
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], -2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], -2
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i8 [[A]], 1
+; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i8 [[A_OFF]], 1
 ; CHECK-NEXT:    br i1 [[SWITCH]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ;
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, 254
   call void @llvm.assume(i1 %cmp)
   switch i8 %a, label %default [i8 255, label %true
   i8 254, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 }
 
 ; Check that we can eliminate both dead cases and dead defaults
 ; within a single run of simplify-cfg
 define void @test7(i8 %a) {
 ; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[A:%.*]], -3
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[SWITCH:%.*]] = icmp eq i8 [[A]], -1
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], -2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], -2
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i8 [[A]], 1
+; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i8 [[A_OFF]], 1
 ; CHECK-NEXT:    br i1 [[SWITCH]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ;
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, 254
   call void @llvm.assume(i1 %cmp)
   switch i8 %a, label %default [i8 255, label %true
   i8 254, label %false
   i8 0, label %also_dead]

 
 ;; All but one bit known undef
 ;; Note: This is currently testing an optimization which doesn't trigger. The
 ;; case this is protecting against is that a bit could be assumed both zero
 ;; *or* one given we know it's undef.  ValueTracking doesn't do this today,
 ;; but it doesn't hurt to confirm.
 define void @test8(i8 %a) {
 ; CHECK-LABEL: @test8(
-; CHECK-NEXT:    unreachable
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], -2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], undef
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    switch i8 [[A]], label [[DEFAULT:%.*]] [
+; CHECK-NEXT:    i8 -1, label [[TRUE:%.*]]
+; CHECK-NEXT:    i8 -2, label [[FALSE:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       true:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    ret void
+; CHECK:       false:
+; CHECK-NEXT:    call void @foo(i32 3)
+; CHECK-NEXT:    ret void
+; CHECK:       default:
+; CHECK-NEXT:    call void @foo(i32 2)
+; CHECK-NEXT:    ret void
 ;
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, undef
   call void @llvm.assume(i1 %cmp)
   switch i8 %a, label %default [i8 255, label %true
   i8 254, label %false]
 true:
   call void @foo(i32 1)

test/Transforms/SimplifyCFG/switch-genfori8.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes='simplify-cfg<switch-to-lookup>' < %s | FileCheck %s
 ; Using a Zig driver https://gist.github.com/shawnl/8137f62f7dbcfd539f6cf1925387cd38
 ;after-patch, covered lookup table: 509.8MiB/sec
 ;lookup table, not covered, only valid digits to prime the branch predictor: 437.8MiB/sec
 ;lookup table, not covered, random bytes: 242.0MiB/sec
 ;before-patch, no lookup table: 205.4MiB/sec
 
 ; ModuleID = 'chartodigit.c'
 source_filename = "chartodigit.c"
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-pc-linux-gnu"
 
 ; Function Attrs: norecurse nounwind readnone uwtable
 define dso_local zeroext i8 @char_to_digit(i8 zeroext) local_unnamed_addr #0 {
 ; CHECK-LABEL: @char_to_digit(
-; CHECK-NEXT:    switch i8 [[TMP0:%.*]], label [[TMP17:%.*]] [
-; CHECK-NEXT:    i8 48, label [[TMP18:%.*]]
-; CHECK-NEXT:    i8 49, label [[TMP2:%.*]]
-; CHECK-NEXT:    i8 50, label [[TMP3:%.*]]
-; CHECK-NEXT:    i8 51, label [[TMP4:%.*]]
-; CHECK-NEXT:    i8 52, label [[TMP5:%.*]]
-; CHECK-NEXT:    i8 53, label [[TMP6:%.*]]
-; CHECK-NEXT:    i8 54, label [[TMP7:%.*]]
-; CHECK-NEXT:    i8 55, label [[TMP8:%.*]]
-; CHECK-NEXT:    i8 56, label [[TMP9:%.*]]
-; CHECK-NEXT:    i8 57, label [[TMP10:%.*]]
-; CHECK-NEXT:    i8 97, label [[TMP11:%.*]]
-; CHECK-NEXT:    i8 98, label [[TMP12:%.*]]
-; CHECK-NEXT:    i8 99, label [[TMP13:%.*]]
-; CHECK-NEXT:    i8 100, label [[TMP14:%.*]]
-; CHECK-NEXT:    i8 101, label [[TMP15:%.*]]
-; CHECK-NEXT:    i8 102, label [[TMP16:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 [[TMP0:%.*]], 48
+; CHECK-NEXT:    switch i8 [[TMP2]], label [[TMP18:%.*]] [
+; CHECK-NEXT:    i8 0, label [[TMP19:%.*]]
+; CHECK-NEXT:    i8 1, label [[TMP3:%.*]]
+; CHECK-NEXT:    i8 2, label [[TMP4:%.*]]
+; CHECK-NEXT:    i8 3, label [[TMP5:%.*]]
+; CHECK-NEXT:    i8 4, label [[TMP6:%.*]]
+; CHECK-NEXT:    i8 5, label [[TMP7:%.*]]
+; CHECK-NEXT:    i8 6, label [[TMP8:%.*]]
+; CHECK-NEXT:    i8 7, label [[TMP9:%.*]]
+; CHECK-NEXT:    i8 8, label [[TMP10:%.*]]
+; CHECK-NEXT:    i8 9, label [[TMP11:%.*]]
+; CHECK-NEXT:    i8 49, label [[TMP12:%.*]]
+; CHECK-NEXT:    i8 50, label [[TMP13:%.*]]
+; CHECK-NEXT:    i8 51, label [[TMP14:%.*]]
+; CHECK-NEXT:    i8 52, label [[TMP15:%.*]]
+; CHECK-NEXT:    i8 53, label [[TMP16:%.*]]
+; CHECK-NEXT:    i8 54, label [[TMP17:%.*]]
 ; CHECK-NEXT:    ]
-; CHECK:       2:
-; CHECK-NEXT:    br label [[TMP18]]
 ; CHECK:       3:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       4:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       5:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       6:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       7:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       8:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       9:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       10:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       11:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       12:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       13:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       14:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       15:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       16:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       17:
-; CHECK-NEXT:    br label [[TMP18]]
+; CHECK-NEXT:    br label [[TMP19]]
 ; CHECK:       18:
-; CHECK-NEXT:    [[TMP19:%.*]] = phi i8 [ -1, [[TMP17]] ], [ 15, [[TMP16]] ], [ 14, [[TMP15]] ], [ 13, [[TMP14]] ], [ 12, [[TMP13]] ], [ 11, [[TMP12]] ], [ 10, [[TMP11]] ], [ 9, [[TMP10]] ], [ 8, [[TMP9]] ], [ 7, [[TMP8]] ], [ 6, [[TMP7]] ], [ 5, [[TMP6]] ], [ 4, [[TMP5]] ], [ 3, [[TMP4]] ], [ 2, [[TMP3]] ], [ 1, [[TMP2]] ], [ 0, [[TMP1:%.*]] ]
-; CHECK-NEXT:    ret i8 [[TMP19]]
+; CHECK-NEXT:    br label [[TMP19]]
+; CHECK:       19:
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i8 [ -1, [[TMP18]] ], [ 15, [[TMP17]] ], [ 14, [[TMP16]] ], [ 13, [[TMP15]] ], [ 12, [[TMP14]] ], [ 11, [[TMP13]] ], [ 10, [[TMP12]] ], [ 9, [[TMP11]] ], [ 8, [[TMP10]] ], [ 7, [[TMP9]] ], [ 6, [[TMP8]] ], [ 5, [[TMP7]] ], [ 4, [[TMP6]] ], [ 3, [[TMP5]] ], [ 2, [[TMP4]] ], [ 1, [[TMP3]] ], [ 0, [[TMP1:%.*]] ]
+; CHECK-NEXT:    ret i8 [[TMP20]]
 ;
   switch i8 %0, label %17 [
   i8 48, label %18
   i8 49, label %2
   i8 50, label %3
   i8 51, label %4
   i8 52, label %5
   i8 53, label %6

test/Transforms/SimplifyCFG/switch-simplify-range.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes='simplify-cfg<switch-to-lookup>' < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-pc-linux-gnu"
 
 attributes #0 = { "no-jump-tables"="false" }
 
 define i64 @switch_common_right_bits(i8 %a) #0  {
 ; CHECK-LABEL: @switch_common_right_bits(
 ; CHECK-NEXT:  Entry:
-; CHECK-NEXT:    switch i8 [[A:%.*]], label [[SWITCHELSE:%.*]] [
-; CHECK-NEXT:    i8 123, label [[SWITCHPRONG:%.*]]
-; CHECK-NEXT:    i8 125, label [[SWITCHPRONG1:%.*]]
-; CHECK-NEXT:    i8 127, label [[SWITCHPRONG2:%.*]]
-; CHECK-NEXT:    i8 -127, label [[SWITCHPRONG3:%.*]]
-; CHECK-NEXT:    i8 -125, label [[SWITCHPRONG4:%.*]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[A:%.*]], 123
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.fshr.i8(i8 [[TMP0]], i8 [[TMP0]], i8 1)
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 5
+; CHECK-NEXT:    br i1 [[TMP2]], label [[SWITCH_LOOKUP:%.*]], label [[SWITCHELSE:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i64], [5 x i64]* @switch.table.switch_common_right_bits, i32 0, i8 [[TMP1]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, i64* [[SWITCH_GEP]]
+; CHECK-NEXT:    ret i64 [[SWITCH_LOAD]]
 ; CHECK:       SwitchElse:
-; CHECK-NEXT:    [[MERGE:%.*]] = phi i64 [ 10, [[ENTRY:%.*]] ], [ 6, [[SWITCHPRONG]] ], [ 3, [[SWITCHPRONG1]] ], [ 4, [[SWITCHPRONG2]] ], [ 2, [[SWITCHPRONG3]] ], [ 1, [[SWITCHPRONG4]] ]
-; CHECK-NEXT:    ret i64 [[MERGE]]
-; CHECK:       SwitchProng:
-; CHECK-NEXT:    br label [[SWITCHELSE]]
-; CHECK:       SwitchProng1:
-; CHECK-NEXT:    br label [[SWITCHELSE]]
-; CHECK:       SwitchProng2:
-; CHECK-NEXT:    br label [[SWITCHELSE]]
-; CHECK:       SwitchProng3:
-; CHECK-NEXT:    br label [[SWITCHELSE]]
-; CHECK:       SwitchProng4:
-; CHECK-NEXT:    br label [[SWITCHELSE]]
+; CHECK-NEXT:    ret i64 10
 ;
 Entry:
   switch i8 %a, label %SwitchElse [
   i8 123, label %SwitchProng
   i8 125, label %SwitchProng1
   i8 127, label %SwitchProng2
   i8 129, label %SwitchProng3
   i8 131, label %SwitchProng4
SwitchElse:                                     ; preds = %Entry
   ret i64 12
 }
 
 ;Must check that the default was filled in at index 0 as happened here:
 ;@switch.table.switch_not_normalized_to_start_at_zero = private unnamed_addr constant [6 x i16] [i16 10, i16 7, i16 3, i16 1, i16 6, i16 8], align 2
 define i16 @switch_not_normalized_to_start_at_zero(i8 %a) #0  {
 ; CHECK-LABEL: @switch_not_normalized_to_start_at_zero(
 ; CHECK-NEXT:  Entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i8 [[A:%.*]], 1
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[SWITCH_TABLEIDX]], 5
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[A:%.*]], 6
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SWITCHELSE:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i16], [5 x i16]* @switch.table.switch_not_normalized_to_start_at_zero, i32 0, i8 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i16], [6 x i16]* @switch.table.switch_not_normalized_to_start_at_zero, i32 0, i8 [[A]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i16, i16* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i16 [[SWITCH_LOAD]]
 ; CHECK:       SwitchElse:
 ; CHECK-NEXT:    ret i16 10
 ;
 Entry:
   switch i8 %a, label %SwitchElse [
   i8 4, label %SwitchProng