[SimplifyCFG] ReduceSwitchRange: use the smallest result type possible.

[shawnl]

Summary

I am trying to move towards much more space-efficient switch statements, using popcnt, as described in PR39013. This is the patch 6 towards that goal, and a continuation of D60673.

[shawnl]

The backends seem to be able to handle "illegal types", even if they couldn't before for this.

[shawnl]

I am going to drop this as this optimization really belongs in visitGEP, same with the bitmask code in this file.

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, ConstantInt *Offset, Type *MinTy,
+      IRBuilder<> &Builder,
       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);
+  Value *BuildLookup(Value *Index, Type *MinTy, IRBuilder<> &Builder);
 
   /// Return true if a table with TableSize elements of
   /// type ElementType would fit in a target-legal register.
   static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize,
                                  Type *ElementType);
 
 private:
   // Depending on the contents of the table, it can be represented in
private:
 
   // 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, ConstantInt *Offset, Type *ValueType,
+    IRBuilder<> &Builder,
     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);
+  uint64_t MinBitWidth;
+  bool DoTruncate = true;
+  IntegerType *ITy = nullptr;
+  if (ValueType)
+    ITy = dyn_cast<IntegerType>(ValueType);
+  if (ITy)
+    MinBitWidth = ITy->getBitWidth();
+  else
+    DoTruncate = false;
   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();
+    ConstantInt *CaseResCst;
+    if (DoTruncate && (CaseResCst = dyn_cast<ConstantInt>(CaseRes)))
+      TableContents[Idx] =
+          ConstantInt::get(ValueType->getContext(),
+                           CaseResCst->getValue().zextOrTrunc(MinBitWidth));
+    else {
+      assert(CaseRes->getType() == ValueType);
       TableContents[Idx] = CaseRes;
+    }
 
     if (CaseRes != SingleValue)
       SingleValue = nullptr;
   }
 
   // Fill in any holes in the table with the default result.
   if (Values.size() < TableSize) {
     assert(DefaultValue &&
            "Need a default value to fill the lookup table holes.");
-    assert(DefaultValue->getType() == ValueType);
+    Constant *DefaultValueTrunc;
+    ConstantInt *DV;
+    if (DoTruncate && (DV = dyn_cast<ConstantInt>(DefaultValue)))
+      DefaultValueTrunc = ConstantInt::get(
+          ValueType->getContext(), DV->getValue().zextOrTrunc(MinBitWidth));
+    else {
+      assert(DefaultValue->getType() == Values[0].second->getType());
+      DefaultValueTrunc = DefaultValue;
+    }
     for (uint64_t I = 0; I < TableSize; ++I) {
       if (!TableContents[I])
-        TableContents[I] = DefaultValue;
+        TableContents[I] = DefaultValueTrunc;
     }
 
     if (DefaultValue != SingleValue)
       SingleValue = nullptr;
   }
 
   // If each element in the table contains the same value, we only need to store
   // that single value.
for (uint64_t I = 0; I < TableSize; ++I) {
         } else if (Dist != DistToPrev) {
           LinearMappingPossible = false;
           break;
         }
       }
       PrevVal = Val;
     }
     if (LinearMappingPossible) {
-      LinearOffset = cast<ConstantInt>(TableContents[0]);
-      LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev);
+      uint64_t OrigBitWidth =
+          Values.begin()->second->getType()->getIntegerBitWidth();
+      LinearOffset =
+          ConstantInt::get(M.getContext(), cast<ConstantInt>(TableContents[0])
+                                               ->getValue()
+                                               .zextOrSelf(OrigBitWidth));
+      LinearMultiplier =
+          ConstantInt::get(M.getContext(), DistToPrev.zextOrSelf(OrigBitWidth));
       Kind = LinearMapKind;
       ++NumLinearMaps;
       return;
     }
   }
 
   // If the type is integer and the table fits in a register, build a bitmap.
   if (WouldFitInRegister(DL, TableSize, ValueType)) {
Array = new GlobalVariable(M, ArrayTy, /*constant=*/true,
                              "switch.table." + FuncName);
   Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
   // Set the alignment to that of an array items. We will be only loading one
   // value out of it.
   Array->setAlignment(DL.getPrefTypeAlignment(ValueType));
   Kind = ArrayKind;
 }
 
-Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) {
+Value *SwitchLookupTable::BuildLookup(Value *Index, Type *OrigTy,
+                                      IRBuilder<> &Builder) {
   switch (Kind) {
   case SingleValueKind:
+    assert(SingleValue->getType() == OrigTy);
     return SingleValue;
   case LinearMapKind: {
+    assert(LinearMultiplier->getType() == OrigTy);
     // Derive the result value from the input value.
     Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(),
                                           false, "switch.idx.cast");
     if (!LinearMultiplier->isOne())
       Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult");
     if (!LinearOffset->isZero())
       Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset");
     return Result;
case BitMapKind: {
     ShiftAmt = Builder.CreateMul(
         ShiftAmt, ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()),
         "switch.shiftamt");
 
     // Shift down.
     Value *DownShifted =
         Builder.CreateLShr(BitMap, ShiftAmt, "switch.downshift");
     // Mask off.
-    return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked");
+    Value *WrongWidth =
+        Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked");
+    return Builder.CreateZExtOrBitCast(WrongWidth, OrigTy, "switch.zext");
   }
   case ArrayKind: {
     // Make sure the table index will not overflow when treated as signed.
     IntegerType *IT = cast<IntegerType>(Index->getType());
     uint64_t TableSize =
         Array->getInitializer()->getType()->getArrayNumElements();
     if (TableSize > (1ULL << (IT->getBitWidth() - 1)))
       Index = Builder.CreateZExt(
           Index, IntegerType::get(IT->getContext(), IT->getBitWidth() + 1),
           "switch.tableidx.zext");
 
     Value *GEPIndices[] = {Builder.getInt32(0), Index};
     Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array,
                                            GEPIndices, "switch.gep");
-    return Builder.CreateLoad(
+    Value *WrongWidth = Builder.CreateLoad(
         cast<ArrayType>(Array->getValueType())->getElementType(), GEP,
         "switch.load");
+    return Builder.CreateZExtOrBitCast(WrongWidth, OrigTy, "switch.zext");
   }
   }
   llvm_unreachable("Unknown lookup table kind!");
 }
 
 bool SwitchLookupTable::WouldFitInRegister(const DataLayout &DL,
                                            uint64_t TableSize,
                                            Type *ElementType) {
   auto *IT = dyn_cast<IntegerType>(ElementType);
   if (!IT)
     return false;
   // FIXME: If the type is wider than it needs to be, e.g. i8 but all values
   // are <= 15, we could try to narrow the type.
 
   // Avoid overflow, fitsInLegalInteger uses unsigned int for the width.
   if (TableSize >= UINT_MAX / IT->getBitWidth())
     return false;
   return DL.fitsInLegalInteger(TableSize * IT->getBitWidth());
 }
 
 /// Determine whether a lookup table should be built for this switch, based on
 /// the number of cases, size of the table, and the types of the results.
-static bool
-ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
-                       const TargetTransformInfo &TTI, const DataLayout &DL,
-                       const SmallDenseMap<PHINode *, Type *> &ResultTypes) {
+static bool ShouldBuildLookupTable(
+    SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI,
+    const DataLayout &DL,
+    const SmallDenseMap<PHINode *, std::pair<Type *, Type *>> &ResultTypes) {
   if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10)
     return false; // TableSize overflowed, or mul below might overflow.
 
   bool AllTablesFitInRegister = true;
-  bool HasIllegalType = false;
   for (const auto &I : ResultTypes) {
-    Type *Ty = I.second;
-
-    // Saturate this flag to true.
-    HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty);
-
+    Type *Ty = I.second.second;
     // Saturate this flag to false.
     AllTablesFitInRegister =
         AllTablesFitInRegister &&
         SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty);
 
     // If both flags saturate, we're done. NOTE: This *only* works with
     // saturating flags, and all flags have to saturate first due to the
     // non-deterministic behavior of iterating over a dense map.
-    if (HasIllegalType && !AllTablesFitInRegister)
+    if (!AllTablesFitInRegister)
       break;
   }
 
   // If each table would fit in a register, we should build it anyway.
   if (AllTablesFitInRegister)
     return true;
 
-  // Don't build a table that doesn't fit in-register if it has illegal types.
-  if (HasIllegalType)
-    return false;
-
   // The table density should be at least 40%. This is the same criterion as for
   // jump tables, see SelectionDAGBuilder::handleJTSwitchCase.
   // FIXME: Find the best cut-off.
   return SI->getNumCases() * 10 >= TableSize * 4;
 }
 
 /// Try to reuse the switch table index compare. Following pattern:
 /// \code
static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
   ConstantInt *MaxCaseVal = CI->getCaseValue();
 
   BasicBlock *CommonDest = nullptr;
 
   using ResultListTy = SmallVector<std::pair<ConstantInt *, Constant *>, 4>;
   SmallDenseMap<PHINode *, ResultListTy> ResultLists;
 
   SmallDenseMap<PHINode *, Constant *> DefaultResults;
-  SmallDenseMap<PHINode *, Type *> ResultTypes;
+  // Extend-to type (original type), type in table
+  SmallDenseMap<PHINode *, std::pair<Type *, Type *>> ResultTypes;
   SmallVector<PHINode *, 4> PHIs;
 
   for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) {
     ConstantInt *CaseVal = CI->getCaseValue();
     if (CaseVal->getValue().ult(MinCaseVal->getValue()))
       MinCaseVal = CaseVal;
     if (CaseVal->getValue().ugt(MaxCaseVal->getValue()))
       MaxCaseVal = CaseVal;
for (const auto &I : Results) {
       PHINode *PHI = I.first;
       Constant *Value = I.second;
       if (!ResultLists.count(PHI))
         PHIs.push_back(PHI);
       ResultLists[PHI].push_back(std::make_pair(CaseVal, Value));
     }
   }
 
-  // Keep track of the result types.
+  // Keep track of the result types, and calculate the smallest type we can use.
   for (PHINode *PHI : PHIs) {
-    ResultTypes[PHI] = ResultLists[PHI][0].second->getType();
+    ResultTypes[PHI].first = ResultLists[PHI][0].second->getType();
+
+    uint64_t MaxVal = 0;
+    for (auto &Res : ResultLists[PHI]) {
+      ConstantInt *CstI = dyn_cast<ConstantInt>(Res.second);
+      if (!CstI)
+        continue; // This is an undef
+      MaxVal = std::max(MaxVal, CstI->getValue().getLimitedValue());
+    }
+    if (MaxVal == UINT64_MAX || MaxVal == 0) {
+      // Compiler Explorer show that if the PHI is always 0 (or undef), it is
+      // pruned, so let's not worry about it.
+      ResultTypes[PHI].second = ResultTypes[PHI].first;
+      continue;
+    }
+    unsigned NewBitWidth = 64 - countLeadingZeros(MaxVal);
+    IntegerType *NewType = IntegerType::get(SI->getContext(), NewBitWidth);
+    ResultTypes[PHI].second = NewType;
+    if (ResultTypes[PHI].first->getIntegerBitWidth() <= NewBitWidth) {
+      // Can't truncate this type
+      assert(ResultTypes[PHI].first->getIntegerBitWidth() == NewBitWidth);
+      continue;
+    }
   }
 
   uint64_t NumResults = ResultLists[PHIs[0]].size();
   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.
for (PHINode *PHI : PHIs) {
 
     // 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();
     // 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);
+    SwitchLookupTable Table(Mod, TableSize, Base, ResultTypes[PHI].second,
+                            Builder, ResultList, DV, DL, FuncName);
 
-    Value *Result = Table.BuildLookup(TableIndex, Builder);
+    Value *Result =
+        Table.BuildLookup(TableIndex, ResultTypes[PHI].first, 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);
       ReturnedEarly = true;
       break;

test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll

 target triple = "armv7a--none-eabi"
 
 define i32 @test1(i32 %n) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* @switch.table.test1, i32 0, i32 [[N]]
-; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
-; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i14], [3 x i14]* @switch.table.test1, i32 0, i32 [[N]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i14, i14* [[SWITCH_GEP]]
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i14 [[SWITCH_LOAD]] to i32
+; CHECK-NEXT:    ret i32 [[SWITCH_ZEXT]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 15498
 ;
 entry:
   switch i32 %n, label %sw.default [
   i32 0, label %sw.bb
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2

 
 @c1 = external constant i32, align 4
 @c2 = external constant i32, align 4
 @c3 = external constant i32, align 4
 @c4 = external constant i32, align 4
 
 
 define i32* @test2(i32 %n) {
-; ENABLE-LABEL: @test2(
-; ENABLE-NEXT:  entry:
-; ENABLE-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3
-; ENABLE-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
-; ENABLE:       switch.lookup:
-; ENABLE-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32*], [3 x i32*]* @switch.table.test2, i32 0, i32 [[N]]
-; ENABLE-NEXT:    [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]]
-; ENABLE-NEXT:    ret i32* [[SWITCH_LOAD]]
-; ENABLE:       return:
-; ENABLE-NEXT:    ret i32* @c4
-;
-; DISABLE-LABEL: @test2(
-; DISABLE-NEXT:  entry:
-; DISABLE-NEXT:    switch i32 [[N:%.*]], label [[SW_DEFAULT:%.*]] [
-; DISABLE-NEXT:    i32 0, label [[RETURN:%.*]]
-; DISABLE-NEXT:    i32 1, label [[SW_BB1:%.*]]
-; DISABLE-NEXT:    i32 2, label [[SW_BB2:%.*]]
-; DISABLE-NEXT:    ]
-; DISABLE:       sw.bb1:
-; DISABLE-NEXT:    br label [[RETURN]]
-; DISABLE:       sw.bb2:
-; DISABLE-NEXT:    br label [[RETURN]]
-; DISABLE:       sw.default:
-; DISABLE-NEXT:    br label [[RETURN]]
-; DISABLE:       return:
-; DISABLE-NEXT:    [[RETVAL_0:%.*]] = phi i32* [ @c4, [[SW_DEFAULT]] ], [ @c3, [[SW_BB2]] ], [ @c2, [[SW_BB1]] ], [ @c1, [[ENTRY:%.*]] ]
-; DISABLE-NEXT:    ret i32* [[RETVAL_0]]
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32*], [3 x i32*]* @switch.table.test2, i32 0, i32 [[N]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]]
+; CHECK-NEXT:    ret i32* [[SWITCH_LOAD]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32* @c4
 ;
 entry:
   switch i32 %n, label %sw.default [
   i32 0, label %sw.bb
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2
   ]
 

 }
 
 @g1 = external global i32, align 4
 @g2 = external global i32, align 4
 @g3 = external global i32, align 4
 @g4 = external global i32, align 4
 
 define i32* @test3(i32 %n) {
-; ENABLE-LABEL: @test3(
-; ENABLE-NEXT:  entry:
-; ENABLE-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3
-; ENABLE-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
-; ENABLE:       switch.lookup:
-; ENABLE-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32*], [3 x i32*]* @switch.table.test3, i32 0, i32 [[N]]
-; ENABLE-NEXT:    [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]]
-; ENABLE-NEXT:    ret i32* [[SWITCH_LOAD]]
-; ENABLE:       return:
-; ENABLE-NEXT:    ret i32* @g4
-;
-; DISABLE-LABEL: @test3(
-; DISABLE-NEXT:  entry:
-; DISABLE-NEXT:    switch i32 [[N:%.*]], label [[SW_DEFAULT:%.*]] [
-; DISABLE-NEXT:    i32 0, label [[RETURN:%.*]]
-; DISABLE-NEXT:    i32 1, label [[SW_BB1:%.*]]
-; DISABLE-NEXT:    i32 2, label [[SW_BB2:%.*]]
-; DISABLE-NEXT:    ]
-; DISABLE:       sw.bb1:
-; DISABLE-NEXT:    br label [[RETURN]]
-; DISABLE:       sw.bb2:
-; DISABLE-NEXT:    br label [[RETURN]]
-; DISABLE:       sw.default:
-; DISABLE-NEXT:    br label [[RETURN]]
-; DISABLE:       return:
-; DISABLE-NEXT:    [[RETVAL_0:%.*]] = phi i32* [ @g4, [[SW_DEFAULT]] ], [ @g3, [[SW_BB2]] ], [ @g2, [[SW_BB1]] ], [ @g1, [[ENTRY:%.*]] ]
-; DISABLE-NEXT:    ret i32* [[RETVAL_0]]
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32*], [3 x i32*]* @switch.table.test3, i32 0, i32 [[N]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]]
+; CHECK-NEXT:    ret i32* [[SWITCH_LOAD]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32* @g4
 ;
 entry:
   switch i32 %n, label %sw.default [
   i32 0, label %sw.bb
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2
   ]
 

 
 declare i32 @f1(i32, i32)
 declare i32 @f2(i32, i32)
 declare i32 @f3(i32, i32)
 declare i32 @f4(i32, i32)
 declare i32 @f5(i32, i32)
 
 define i32 @test4(i32 %a, i32 %b, i32 %c) {
-; ENABLE-LABEL: @test4(
-; ENABLE-NEXT:  entry:
-; ENABLE-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[A:%.*]], 1
-; ENABLE-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 3
-; ENABLE-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[COND_FALSE6:%.*]]
-; ENABLE:       cond.false6:
-; ENABLE-NEXT:    [[CMP7:%.*]] = icmp eq i32 [[A]], 4
-; ENABLE-NEXT:    [[COND:%.*]] = select i1 [[CMP7]], i32 (i32, i32)* @f4, i32 (i32, i32)* @f5
-; ENABLE-NEXT:    br label [[COND_END11:%.*]]
-; ENABLE:       switch.lookup:
-; ENABLE-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32 (i32, i32)*], [3 x i32 (i32, i32)*]* @switch.table.test4, i32 0, i32 [[SWITCH_TABLEIDX]]
-; ENABLE-NEXT:    [[SWITCH_LOAD:%.*]] = load i32 (i32, i32)*, i32 (i32, i32)** [[SWITCH_GEP]]
-; ENABLE-NEXT:    br label [[COND_END11]]
-; ENABLE:       cond.end11:
-; ENABLE-NEXT:    [[COND12:%.*]] = phi i32 (i32, i32)* [ [[COND]], [[COND_FALSE6]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
-; ENABLE-NEXT:    [[CALL:%.*]] = call i32 [[COND12]](i32 [[B:%.*]], i32 [[C:%.*]])
-; ENABLE-NEXT:    ret i32 [[CALL]]
-;
-; DISABLE-LABEL: @test4(
-; DISABLE-NEXT:  entry:
-; DISABLE-NEXT:    switch i32 [[A:%.*]], label [[COND_FALSE6:%.*]] [
-; DISABLE-NEXT:    i32 1, label [[COND_END11:%.*]]
-; DISABLE-NEXT:    i32 2, label [[COND_END11_FOLD_SPLIT:%.*]]
-; DISABLE-NEXT:    i32 3, label [[COND_END11_FOLD_SPLIT1:%.*]]
-; DISABLE-NEXT:    ]
-; DISABLE:       cond.false6:
-; DISABLE-NEXT:    [[CMP7:%.*]] = icmp eq i32 [[A]], 4
-; DISABLE-NEXT:    [[COND:%.*]] = select i1 [[CMP7]], i32 (i32, i32)* @f4, i32 (i32, i32)* @f5
-; DISABLE-NEXT:    br label [[COND_END11]]
-; DISABLE:       cond.end11.fold.split:
-; DISABLE-NEXT:    br label [[COND_END11]]
-; DISABLE:       cond.end11.fold.split1:
-; DISABLE-NEXT:    br label [[COND_END11]]
-; DISABLE:       cond.end11:
-; DISABLE-NEXT:    [[COND12:%.*]] = phi i32 (i32, i32)* [ @f1, [[ENTRY:%.*]] ], [ [[COND]], [[COND_FALSE6]] ], [ @f2, [[COND_END11_FOLD_SPLIT]] ], [ @f3, [[COND_END11_FOLD_SPLIT1]] ]
-; DISABLE-NEXT:    [[CALL:%.*]] = call i32 [[COND12]](i32 [[B:%.*]], i32 [[C:%.*]])
-; DISABLE-NEXT:    ret i32 [[CALL]]
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[A:%.*]], label [[COND_FALSE6:%.*]] [
+; CHECK-NEXT:    i32 1, label [[COND_END11:%.*]]
+; CHECK-NEXT:    i32 2, label [[COND_END11_FOLD_SPLIT:%.*]]
+; CHECK-NEXT:    i32 3, label [[COND_END11_FOLD_SPLIT1:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       cond.false6:
+; CHECK-NEXT:    [[CMP7:%.*]] = icmp eq i32 [[A]], 4
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP7]], i32 (i32, i32)* @f4, i32 (i32, i32)* @f5
+; CHECK-NEXT:    br label [[COND_END11]]
+; CHECK:       cond.end11.fold.split:
+; CHECK-NEXT:    br label [[COND_END11]]
+; CHECK:       cond.end11.fold.split1:
+; CHECK-NEXT:    br label [[COND_END11]]
+; CHECK:       cond.end11:
+; CHECK-NEXT:    [[COND12:%.*]] = phi i32 (i32, i32)* [ @f1, [[ENTRY:%.*]] ], [ [[COND]], [[COND_FALSE6]] ], [ @f2, [[COND_END11_FOLD_SPLIT]] ], [ @f3, [[COND_END11_FOLD_SPLIT1]] ]
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 [[COND12]](i32 [[B:%.*]], i32 [[C:%.*]])
+; CHECK-NEXT:    ret i32 [[CALL]]
 ;
 entry:
   %cmp = icmp eq i32 %a, 1
   br i1 %cmp, label %cond.end11, label %cond.false
 
 cond.false:
   %cmp1 = icmp eq i32 %a, 2
   br i1 %cmp1, label %cond.end11, label %cond.false3

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:    [[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:    [[SWITCH_CAST:%.*]] = zext i3 [[ARG]] to i28
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i28 [[SWITCH_CAST]], 4
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i28 129423864, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i28 [[SWITCH_DOWNSHIFT]] to i4
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i4 [[SWITCH_MASKED]] to i64
 ; CHECK-NEXT:    br label [[DEFAULT]]
 ; CHECK:       Default:
-; CHECK-NEXT:    [[V1:%.*]] = phi i64 [ 8, [[ENTRY:%.*]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
+; CHECK-NEXT:    [[V1:%.*]] = phi i64 [ 8, [[ENTRY:%.*]] ], [ [[SWITCH_ZEXT]], [[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

test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

 
 declare void @dummy(i8 signext, float)
 define void @h(i32 %x) {
 ; CHECK-LABEL: @h(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_EPILOG:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i32 [[X]], 8
-; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 89655594, [[SWITCH_SHIFTAMT]]
-; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = trunc i32 [[X]] to i28
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i28 [[SWITCH_CAST]], 7
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i28 11928746, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i28 [[SWITCH_DOWNSHIFT]] to i7
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i7 [[SWITCH_MASKED]] to i8
 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x float], [4 x float]* @switch.table.h, i32 0, i32 [[X]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load float, float* [[SWITCH_GEP]]
 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 ; CHECK:       sw.epilog:
-; CHECK-NEXT:    [[A_0:%.*]] = phi i8 [ [[SWITCH_MASKED]], [[SWITCH_LOOKUP]] ], [ 7, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[A_0:%.*]] = phi i8 [ [[SWITCH_ZEXT]], [[SWITCH_LOOKUP]] ], [ 7, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[B_0:%.*]] = phi float [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 0x4023FAE140000000, [[ENTRY]] ]
 ; CHECK-NEXT:    call void @dummy(i8 signext [[A_0]], float [[B_0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   switch i32 %x, label %sw.default [
   i32 0, label %sw.epilog
   i32 1, label %sw.bb1

 ; value is not used. This used to make the transformation generate illegal code.
 
 define i32 @earlyreturncrash(i32 %x)  {
 ; CHECK-LABEL: @earlyreturncrash(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_EPILOG:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.earlyreturncrash, i32 0, i32 [[X]]
-; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
-; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = trunc i32 [[X]] to i28
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i28 [[SWITCH_CAST]], 7
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i28 11928746, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i28 [[SWITCH_DOWNSHIFT]] to i7
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i7 [[SWITCH_MASKED]] to i32
+; CHECK-NEXT:    ret i32 [[SWITCH_ZEXT]]
 ; CHECK:       sw.epilog:
 ; CHECK-NEXT:    ret i32 7
 ;
 entry:
   switch i32 %x, label %sw.default [
   i32 0, label %sw.epilog
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2

 ; 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:    [[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 [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-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [200 x i16], [200 x i16]* @switch.table.large, i32 0, i32 [[SPEC_SELECT]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i16, i16* [[SWITCH_GEP]]
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i16 [[SWITCH_LOAD]] to i32
+; CHECK-NEXT:    ret i32 [[SWITCH_ZEXT]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %cmp = icmp slt i32 %x, 0
   br i1 %cmp, label %if.then, label %if.end
 
 if.then:
return:
   %retval.0 = phi i32 [ 1, %sw.bb3 ], [ -1, %sw.bb2 ], [ 0, %sw.bb ], [ 2, %sw.default ]
   ret i32 %retval.0
 
 }
 
 define i32 @unreachable_default(i32 %x)  {
 ; CHECK-LABEL: @unreachable_default(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.unreachable_default, i32 0, i32 [[X:%.*]]
-; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
-; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = trunc i32 [[X:%.*]] to i24
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i24 [[SWITCH_CAST]], 6
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i24 531754, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i24 [[SWITCH_DOWNSHIFT]] to i6
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i6 [[SWITCH_MASKED]] to i32
+; CHECK-NEXT:    ret i32 [[SWITCH_ZEXT]]
 ;
 entry:
   switch i32 %x, label %default [
   i32 0, label %bb0
   i32 1, label %bb1
   i32 2, label %bb2
   i32 3, label %bb3
   ]

 
 }
 
 ; Don't create a table with illegal type
 define i96 @illegaltype(i32 %c) {
 ; CHECK-LABEL: @illegaltype(
 ; CHECK-NEXT:  entry:
 ; 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-NEXT:    br label [[RETURN]]
-; CHECK:       sw.default:
-; CHECK-NEXT:    br label [[RETURN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 5
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i96], [5 x i96]* @switch.table.illegaltype, i32 0, i32 [[TMP0]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i96, i96* [[SWITCH_GEP]]
+; CHECK-NEXT:    ret i96 [[SWITCH_LOAD]]
 ; CHECK:       return:
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i96 [ 15, [[SW_DEFAULT]] ], [ 27, [[SW_BB4]] ], [ -1, [[SW_BB3]] ], [ 0, [[SW_BB2]] ], [ 123, [[SW_BB1]] ], [ 55, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i96 [[RETVAL_0]]
+; CHECK-NEXT:    ret i96 15
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 42, label %return
   i32 43, label %sw.bb1
   i32 44, label %sw.bb2
   i32 45, label %sw.bb3
   i32 46, label %sw.bb4

 
 ; We build lookup tables for switches with three or more cases.
 define i32 @threecases(i32 %c) {
 ; CHECK-LABEL: @threecases(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[C:%.*]], 3
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* @switch.table.threecases, i32 0, i32 [[C]]
-; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]]
-; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = trunc i32 [[C]] to i12
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i12 [[SWITCH_CAST]], 4
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i12 1402, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i12 [[SWITCH_DOWNSHIFT]] to i4
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i4 [[SWITCH_MASKED]] to i32
+; CHECK-NEXT:    ret i32 [[SWITCH_ZEXT]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 3
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 0, label %return
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2

 define i8 @linearmap1(i32 %c) {
 ; CHECK-LABEL: @linearmap1(
 ; CHECK-NEXT:  entry:
 ; 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 [[TMP0]] to i8
-; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul i8 [[SWITCH_IDX_CAST]], -5
+; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul i8 [[SWITCH_IDX_CAST]], 27
 ; 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 [
   i32 10, label %return

 ; 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:       switch.lookup:
-; 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:    [[SWITCH_CAST:%.*]] = zext i3 [[TMP2]] to i12
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i12 [[SWITCH_CAST]], 2
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i12 -1371, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i12 [[SWITCH_DOWNSHIFT]] to i2
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i2 [[SWITCH_MASKED]] to i32
 ; CHECK-NEXT:    br label [[L6]]
 ; CHECK:       l6:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[SWITCH_HOLE_CHECK]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[SWITCH_HOLE_CHECK]] ], [ [[SWITCH_ZEXT]], [[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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -switch-to-lookup -S | FileCheck %s
 ; RUN: opt < %s -passes='simplify-cfg<switch-to-lookup>' -S | FileCheck %s
 
 target datalayout = "e-n32"
 
 define i32 @test1(i32 %a) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
-; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 2, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 3, label [[THREE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i17], [4 x i17]* @switch.table.test1, i32 0, i32 [[TMP4]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i17, i17* [[SWITCH_GEP]]
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i17 [[SWITCH_LOAD]] to i32
+; CHECK-NEXT:    ret i32 [[SWITCH_ZEXT]]
 ; 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]]
-; CHECK:       three:
-; CHECK-NEXT:    br label [[DEF]]
+; CHECK-NEXT:    ret i32 8867
 ;
   switch i32 %a, label %def [
   i32 97, label %one
   i32 101, label %two
   i32 105, label %three
   i32 109, label %three
   ]
 

 }
 
 define i32 @test6(i32 %a) optsize {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], -109
 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
-; CHECK-NEXT:    i32 3, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 2, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 1, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 0, label [[THREE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i17], [4 x i17]* @switch.table.test6, i32 0, i32 [[TMP4]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i17, i17* [[SWITCH_GEP]]
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i17 [[SWITCH_LOAD]] to i32
+; CHECK-NEXT:    ret i32 [[SWITCH_ZEXT]]
 ; 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]]
-; CHECK:       three:
-; CHECK-NEXT:    br label [[DEF]]
+; CHECK-NEXT:    ret i32 8867
 ;
   switch i32 %a, label %def [
   i32 -97, label %one
   i32 -101, label %two
   i32 -105, label %three
   i32 -109, label %three
   ]
 

 }
 
 define i32 @test8(i32 %a) optsize {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
-; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 2, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 4, label [[THREE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 5
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i17], [5 x i17]* @switch.table.test8, i32 0, i32 [[TMP4]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i17, i17* [[SWITCH_GEP]]
+; CHECK-NEXT:    [[SWITCH_ZEXT:%.*]] = zext i17 [[SWITCH_LOAD]] to i32
+; CHECK-NEXT:    ret i32 [[SWITCH_ZEXT]]
 ; 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]]
-; CHECK:       three:
-; CHECK-NEXT:    br label [[DEF]]
+; CHECK-NEXT:    ret i32 8867
 ;
   switch i32 %a, label %def [
   i32 97, label %one
   i32 101, label %two
   i32 105, label %three
   i32 113, label %three
   ]