PATCH] [SimplifyCFG] Run ReduceSwitchRange unconditionally, generalize

[shawnl]

Summary

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".

[shawnl]

needs another test

lib/Transforms/Utils/SimplifyCFG.cpp

 namespace {
 
 /// This class represents a lookup table that can be used to replace a switch.
 class SwitchLookupTable {
 public:
   /// Create a lookup table to use as a switch replacement with the contents
   /// of Values, using DefaultValue to fill any holes in the table.
   SwitchLookupTable(
-      Module &M, uint64_t TableSize, ConstantInt *Offset,
+      Module &M, uint64_t TableSize,
       const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
       Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName);
 
   /// Build instructions with Builder to retrieve the value at
   /// the position given by Index in the lookup table.
   Value *BuildLookup(Value *Index, IRBuilder<> &Builder);
 
   /// Return true if a table with TableSize elements of

 
   // For ArrayKind, this is the array.
   GlobalVariable *Array = nullptr;
 };
 
 } // end anonymous namespace
 
 SwitchLookupTable::SwitchLookupTable(
-    Module &M, uint64_t TableSize, ConstantInt *Offset,
+    Module &M, uint64_t TableSize,
     const SmallVectorImpl<std::pair<ConstantInt *, Constant *>> &Values,
     Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName) {
   assert(Values.size() && "Can't build lookup table without values!");
   assert(TableSize >= Values.size() && "Can't fit values in table!");
 
   // If all values in the table are equal, this is that value.
   SingleValue = Values.begin()->second;
 
   Type *ValueType = Values.begin()->second->getType();
 
   // Build up the table contents.
   SmallVector<Constant *, 64> TableContents(TableSize);
   for (size_t I = 0, E = Values.size(); I != E; ++I) {
     ConstantInt *CaseVal = Values[I].first;
     Constant *CaseRes = Values[I].second;
     assert(CaseRes->getType() == ValueType);
 
-    uint64_t Idx = (CaseVal->getValue() - Offset->getValue()).getLimitedValue();
+    uint64_t Idx = CaseVal->getValue().getLimitedValue();
     TableContents[Idx] = CaseRes;
 
     if (CaseRes != SingleValue)
       SingleValue = nullptr;
   }
 
   // Fill in any holes in the table with the default result.
   if (Values.size() < TableSize) {

   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,
+    SwitchLookupTable Table(Mod, TableSize, 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()) {

   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.
-  if (SI->getNumCases() < 4)
+
+  // Ignore switches with less than three cases. These will always be lowered
+  // into a simple comparison.
+  if (SI->getNumCases() < 3)
     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.
+  uint64_t BestDistance = APInt::getMaxValue(CondTy->getIntegerBitWidth()).getLimitedValue() -
+    Values.back() + Values.front() + 1;
+  unsigned BestIndex = 0;
+  for (unsigned i = 1;i != Values.size();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 ((BestDistance > SubThreshold) &&
+    (BestIndex != 0 || (Values[0] >= SubThreshold))) {
+    Base = Values[BestIndex];
+    MadeChanges = true;
+    for (auto &V : Values)
+      V = (APInt(BitWidth, V) - Base).getLimitedValue();
+  }
 
   // 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.
 
   unsigned Shift = 64;
   for (auto &V : Values) {
     // There is no edge condition when the BitWidth is less than 64, because if
     // 0 is the only value then a shift does nothing, and LLVM requires
     // well-formed IR to not have duplicate cases.
-    unsigned TZ = countTrailingZeros((uint64_t)V);
+    unsigned TZ = countTrailingZeros(V);
     if (TZ < Shift) {
       Shift = TZ;
       if (Shift == 0)
         break;
     }
   }
   if (Shift) {
+    MadeChanges = true;
     for (auto &V : Values)
       V = 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

     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/rangereduce.ll

 one:
   ret i128 11984
 two:
   ret i128 1143
 three:
   ret i128 99783
 }
 
-; Optimization shouldn't trigger; no holes present
 define i32 @test3(i32 %a) {
 ; CHECK-LABEL: @test3(
-; CHECK-NEXT:    switch i32 [[A:%.*]], label [[DEF:%.*]] [
-; CHECK-NEXT:    i32 97, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 98, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 99, label [[THREE:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshr.i32(i32 [[TMP1]], i32 [[TMP1]], i32 0)
+; CHECK-NEXT:    switch i32 [[TMP2]], label [[DEF:%.*]] [
+; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
+; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
+; CHECK-NEXT:    i32 2, 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]]

 one:
   ret i32 11984
 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:    [[TMP2:%.*]] = call i32 @llvm.fshr.i32(i32 [[TMP1]], i32 [[TMP1]], i32 0)
+; CHECK-NEXT:    switch i32 [[TMP2]], 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]]

 one:
   ret i32 11984
 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:    [[TMP2:%.*]] = call i32 @llvm.fshr.i32(i32 [[TMP1]], i32 [[TMP1]], i32 0)
+; CHECK-NEXT:    switch i32 [[TMP2]], 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:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshr.i32(i32 [[TMP1]], i32 [[TMP1]], i32 1)
 ; CHECK-NEXT:    switch i32 [[TMP2]], 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:    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-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