[SimplifyCFG] Implement the suggested ctlz transform

[shawnl]

Summary

This is patch 5 is a series beginning with D61150

[nikic]

Can you please point to patch 5? I think it's missing. (Best directly add it as a parent revision.)

[jmolloy]

Thanks for implementing this! It's really cool.

lib/Transforms/Utils/SimplifyCFG.cpp

5492

s/Another/A. "Another" requires the user to know some context which has now gone.

5493

TODO -> FIXME

5494

No underscores in function names. ReduceSwitchRangeWithCtlz?

5495

It looks to me like this isn't clang-formatted. Can you git-clang-format all your diffs?

5496

You don't need DL or TTI here, please remove them.

5497

I'd use a reference here. It's what most of the rest of LLVM uses.

5498

s/reagarding/regarding.

"when given input 0, they return the bitwidth" would be a more natural phrasing.

5500

I would avoid talking about the solution you didn't implement. Checking for zero input (which your popcount does) is a totally reasonable and understandable thing (and much more understandable than trying to grok the xor/rotate explanation to then find it isn't used :D )

5503

getIntegerBitWidth() is defined on Type. You can avoid the cast.

unsigned BitWidth = SI->getCondition()->getType()->getIntegerBitWidth()

5515

This would be a pattern for instcombine to pick up. We shouldn't have to worry about this here.

5519

Isn't the order exactly reversed?

llvm::reverse(Values);

5520

And if you do need to sort, please use

llvm::sort(*Values)

5553

Please keep using SmallVector.

5556

Please keep using llvm::sort.

5620

Please remove the extra scope. There's no RAII objects here, so they aren't required.

5624

IntegerType::get(Ty->getContext(), 1)

Change to

Builder.getInt1(false);

And please change "Zero" to a more descriptive name for the second parameter to ctlz.

5632

See comments on diffbase about fshr. I don't think you need it, the rotate sequence is good enough. Is there a good reason why you think fshr is better?

5645

Why are you converting from APInt to uint64_t to APInt again? Just remove .getLimitedValue() and keep Sub.lshr() in the next line?

test/Transforms/SimplifyCFG/rangereduce.ll

85

Uh, something's fishy here - why was this fshr here in the first place? This switch just needs a subtract.

121

Your previous patch is clearly bogus; this is a shift by zero.

[shawnl]

lib/Transforms/Utils/SimplifyCFG.cpp

5500

which your popcount does

It does not. It only checks if the MAXIMUM is 1.

5515

Yes we do, because InstCombine does not know how to rearrange case statements.

5519

Nope, the first becomes the last. I guess I could use swap() and move().

5553

I was having problems when I tried to modify the reference to SmallVectorImpl that I did not know how to fix.

test/Transforms/SimplifyCFG/rangereduce.ll

121

shifts by zero are well defined, and get cleaned up by the optimizer, but I agree it didn't need to be inserted.

[lebedev.ri]

lib/Transforms/Utils/SimplifyCFG.cpp

5515

Sounds like a missed optimization on instcombine side then?
Trying to handle every single unrelated micro-transform in every optimization is a path to failure.

[jmolloy]

lib/Transforms/Utils/SimplifyCFG.cpp

5519

I'm not sure I agree with that, or at least I'm missing something.

Given a sorted array A of integers with popcount 1 (single bit set), I believe:

order(A) == order(cttz(A))  //  cttz does not change the order.
order(A) == reverse(order(ctlz(A))) // Conversely ctlz reverses the order.

If you need to handle the zero value too, then I would have thought cttz would barrel-shift as you describe and ctlz would barrel-shift the reversed order.

My comment above was based on the assumption that you're not allowing zero to be passed to ctlz/cttz. Given you are, just keep on using llvm::sort.

5553

We can fix that. Please keep using SmallVector and we can work through the difficulties.

[shawnl]

lib/Transforms/Utils/SimplifyCFG.cpp

5515

Yeah I am working on some patches.

5519

Oh yes, I was think about cttz, but now I am only using ctlz, so I can use llvm::reverse()

[shawnl]

This transform is deeply flawed, and needs much work. If the default is not reachable, there is no need to limit to countPopulation == 1, only assure that there are no duplicates. If the default _is_ reachable, then countPopulation <= 1 continues to be important, but also ctlz and cttz must be run, except in very specific circumstances (such as utf-8 first character parsing)

[jmolloy]

lib/Transforms/Utils/SimplifyCFG.cpp

5520

This loop is scary and hard to read. It's really asking for a helper function. I would do something like this:

// Given a set of equivalence classes, return true if, for every pair A, B in
// Values:
//   Fn(A) == Fn(B) if and only if EC(A) == EC(B).
template <typename Function>
bool IsBijectiveOverEquivalenceClasses(const EquivalenceClasses<APInt> &Values,
                                       const Function &Fn) {
  DenseMap<unsigned, APInt> Leaders;
  for (auto &V : Values) {
    auto TransformedValue = Fn(V.getData());
    auto LeaderIt = Leaders.find(TransformedValue);
    if (LeadersIt == Leaders.end()) {
      Leaders[TransformedValue] = V.getLeader()->getData();
      continue;
    }
    if (LeaderIt->getData() != V.getData())
      // This transformed value has already been seen and did not belong to the
      // same equivalence class. This is not a bijective relation.
      return false;
  }
  return true;
}

static bool CanReduceSwitchRangeWithCtlzOrCttz(SwitchInst &SI, bool &UseCtlz,
                                               bool &UseCttz, bool &UseInvert) {
  // Preconstruct equivalence classes of values based on successor block.
  DenseMap<BasicBlock *, APInt> Last;
  EquivalenceClasses<APInt> ECs;
  for (auto CI : SI.cases()) {
    auto I = Last.try_emplace(CI.getCaseSuccessor(), CI.getCaseValue()).first;
    ECs.unionSets(I.second, V);
  }
  UseInvert = false;

  UseCtlz = true;
  if (IsBijectiveOverEquivalenceClasses(
          ECs, [&](const APInt &V) { return V.countLeadingZeros(); }))
    return true;

  UseCtlz = false;
  if (IsBijectiveOverEquivalenceClasses(
          ECs, [&](const APInt &V) { return V.countTrailingZeros(); }))
    return true;

  UseInvert = true;
  UseCtlz = true;
  if (IsBijectiveOverEquivalenceClasses(
          ECs, [&](const APInt &V) { return (~V).countLeadingZeros(); }))
    return true;

  UseCtlz = false;
  if (IsBijectiveOverEquivalenceClasses(
          ECs, [&](const APInt &V) { return (~V).countTrailingZeros(); }))
    return true;

  return false;
}

static bool ReduceSwitchRangeWithCtlzOrCttz(SwitchInst &SI,
                                            SmallVectorImpl<uint64_t> &Values,
                                            bool &UseCtlz, bool &UseCttz,
                                            bool &UseInvert) {
  // Note we don't pass Values into this function. This predicate uses the
  // switch's current case values *and* their associated successor block, so a
  // rearranged Values array cannot be analyzed (because we wouldn't know which
  // successsor belonged to which value).
  if (!CanReduceSwitchRangeWithCtlzOrCttz(SI, UseCtlz, UseCttz, UseInvert))
    return false;

  for (auto CI : SI.cases()) {
    APInt I = CI.getCaseValue();
    if (UseCtlz)
      Values.push_back((Invert ? ~V : V).countTrailingZeros());
    else
      Values.push_back((Invert ? ~V : V).countLeadingZeros());
  }
  llvm::sort(Values);
  return true;
}

5532

This is a fallacy (will always be false) because:

1. SwitchInst::CaseHandle is unique based on switched value. There is one CaseHandle for every value in Values.
2. Prev is zero-initialized just above this line, in the loop.

[shawnl]

This optimization is not really worth it, for the amount of effort needed to implement it.

lib/Transforms/Utils/SimplifyCFG.cpp

   SI->eraseFromParent();
 
   ++NumLookupTables;
   if (NeedMask)
     ++NumLookupTablesHoles;
   return true;
 }
 
+/// Another cheap transform: investigate using ctlz as a key to the switch
+/// TODO: this transform would benifit from proper range analysis in SwitchToLookupTable
+static bool ReduceSwitchRange_ctlz(SwitchInst *SI,
+                              const DataLayout &DL,
+                              const TargetTransformInfo &TTI,
+                              std::vector<uint64_t> *Values) {
+  // There is a big gotcha reagarding ctlz/cttz: when input 0, they
+  // emit bit width. If not handled this can result in the transform
+  // being applied multiple times. We can either rotate bit width back to zero,
+  // by doing an xor or the most significant bit, followed by a rotate-left 1,
+  // which is expensive, or we can just avoid situation, by checking the range.
+  unsigned BitWidth = cast<IntegerType>(SI->getCondition()->getType())->getIntegerBitWidth();
+  if (Values->back() <= BitWidth)
+    return false;
+
+  unsigned MaxPopCount = 0;
+  for (auto &V : *Values) {
+    MaxPopCount = countPopulation(V);
+    if (MaxPopCount > 1)
+      break;
+  }
+  if (MaxPopCount != 1)
+    return false;
+  // TODO a single instruction can be saved on x86 by using cttz over ctlz
+  // when only ctlz results in a subtraction instruction being added
+  for (auto &V : *Values)
+    V = APInt(BitWidth, V).countLeadingZeros();
+  // 0 will suddenly become the largest (BitWidth), so we need to sort again.
+  // Sorting is OK because we either make a transform on all numbers, or do
+  // not make a transform at all.
+  std::sort(Values->begin(), Values->end());
+  return true;
+}
+
 /// 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());
   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
   // no few cases.
   if (SI->getNumCases() < 4)
     return false;
 
   // We organize the range to start from 0, if it is not already close.
-  SmallVector<uint64_t,4> Values;
+  std::vector<uint64_t> Values;
   for (auto &C : SI->cases())
     Values.push_back(C.getCaseValue()->getValue().getLimitedValue());
-  llvm::sort(Values);
+  std::sort(Values.begin(), Values.end());
 
   bool MadeChanges = false;
+
+  bool UseCtlz = ReduceSwitchRange_ctlz(SI, DL, TTI, &Values);
+  if (UseCtlz)
+    MadeChanges = true;
+
   // 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(V);
     if (TZ < Shift) {

   // 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 *Sub = Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base));
-  Value *Key;
-  if (Shift) {
-    auto *ShiftC = ConstantInt::get(Ty, Shift);
-    Function *Fshr = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::fshr, Ty);
-    Key = Builder.CreateCall(Fshr, {Sub, Sub, ShiftC});
-  } else
-    Key = Sub;
-  SI->replaceUsesOfWith(SI->getCondition(), Key);
+  {
+    Builder.SetInsertPoint(SI);
+    Value *Key = SI->getCondition();
+    if (UseCtlz) {
+      auto *Zero = ConstantInt::get(IntegerType::get(Ty->getContext(), 1), 0);
+      Function *Ctlz = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::ctlz, Ty);
+      Key = Builder.CreateCall(Ctlz, {Key, Zero});
+    }
+    if (Base)
+      Key = Builder.CreateSub(Key, ConstantInt::get(Ty, Base));
+    if (Shift) {
+      auto *ShiftC = ConstantInt::get(Ty, Shift);
+      Function *Fshr = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::fshr, Ty);
+      Key = Builder.CreateCall(Fshr, {Key, Key, ShiftC});
+    }
+    SI->replaceUsesOfWith(SI->getCondition(), Key);
+  }
 
   for (auto Case : SI->cases()) {
     auto *Orig = Case.getCaseValue();
-    auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base);
+    uint64_t Zeros;
+    if (UseCtlz)
+      Zeros = Orig->getValue().countLeadingZeros();
+    else
+      Zeros = Orig->getValue().getLimitedValue();
+    auto Sub = (APInt(BitWidth, Zeros) - Base).getLimitedValue();
     Case.setValue(
-        cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
+        cast<ConstantInt>(ConstantInt::get(Ty, APInt(BitWidth, Sub >> Shift))));
   }
   return true;
 }
 
 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();
 
   if (isValueEqualityComparison(SI)) {

test/Transforms/SimplifyCFG/rangereduce.ll

two:
   ret i128 1143
 three:
   ret i128 99783
 }
 
 define i32 @test3(i32 %a) {
 ; CHECK-LABEL: @test3(
 ; 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:    switch i32 [[TMP1]], 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:
two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i32 @test4(i32 %a) {
 ; CHECK-LABEL: @test4(
 ; 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:    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]]
two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i32 @test5(i32 %a) {
 ; CHECK-LABEL: @test5(
 ; 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:    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]]

 two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i32 @test9(i32 %a) {
 ; CHECK-LABEL: @test9(
-; 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:    [[TMP1:%.*]] = call i32 @llvm.fshr.i32(i32 [[A:%.*]], i32 [[A]], i32 1)
+; CHECK-NEXT:    switch i32 [[TMP1]], 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]]

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

SwitchProng3:                                     ; preds = %Entry
   ret i64 2
 SwitchProng4:                                     ; preds = %Entry
   ret i64 1
 }
 
 define i64 @switch_clz1(i16 %a) optsize #0  {
 ; CHECK-LABEL: @switch_clz1(
 ; CHECK-NEXT:  Entry:
-; CHECK-NEXT:    switch i16 [[A:%.*]], label [[SWITCHELSE:%.*]] [
-; CHECK-NEXT:    i16 2, label [[SWITCHPRONG:%.*]]
-; CHECK-NEXT:    i16 4, label [[SWITCHPRONG1:%.*]]
-; CHECK-NEXT:    i16 8, label [[SWITCHPRONG2:%.*]]
-; CHECK-NEXT:    i16 1, label [[SWITCHPRONG3:%.*]]
-; CHECK-NEXT:    i16 64, label [[SWITCHPRONG6:%.*]]
-; CHECK-NEXT:    i16 128, label [[SWITCHPRONG7:%.*]]
-; CHECK-NEXT:    i16 16, label [[SWITCHPRONG5:%.*]]
-; CHECK-NEXT:    i16 32, label [[SWITCHPRONG4:%.*]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP0:%.*]] = call i16 @llvm.ctlz.i16(i16 [[A:%.*]], i1 false)
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i16 [[TMP0]], 8
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i16 [[TMP1]], 8
+; CHECK-NEXT:    br i1 [[TMP2]], label [[SWITCH_LOOKUP:%.*]], label [[SWITCHELSE:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i64], [8 x i64]* @switch.table.switch_clz1, i32 0, i16 [[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]] ], [ 35, [[SWITCHPRONG2]] ], [ 31, [[SWITCHPRONG3]] ], [ 53, [[SWITCHPRONG4]] ], [ 51, [[SWITCHPRONG5]] ], [ 41, [[SWITCHPRONG6]] ], [ 34, [[SWITCHPRONG7]] ]
-; 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:       SwitchProng5:
-; CHECK-NEXT:    br label [[SWITCHELSE]]
-; CHECK:       SwitchProng6:
-; CHECK-NEXT:    br label [[SWITCHELSE]]
-; CHECK:       SwitchProng7:
-; CHECK-NEXT:    br label [[SWITCHELSE]]
+; CHECK-NEXT:    ret i64 10
 ;
 Entry:
   switch i16 %a, label %SwitchElse [
   i16 2, label %SwitchProng
   i16 4, label %SwitchProng1
   i16 8, label %SwitchProng2
   i16 1, label %SwitchProng3
   i16 64, label %SwitchProng6
SwitchProng6:                                     ; preds = %Entry
   ret i64 41
 SwitchProng7:                                     ; preds = %Entry
   ret i64 34
 }
 
 define i64 @switch_clz2(i8 %a) optsize #0  {
 ; CHECK-LABEL: @switch_clz2(
 ; CHECK-NEXT:  Entry:
-; CHECK-NEXT:    switch i8 [[A:%.*]], label [[SWITCHELSE:%.*]] [
-; CHECK-NEXT:    i8 -128, label [[SWITCHPRONG2:%.*]]
-; CHECK-NEXT:    i8 64, label [[SWITCHPRONG3:%.*]]
-; CHECK-NEXT:    i8 32, label [[SWITCHPRONG6:%.*]]
-; CHECK-NEXT:    i8 1, label [[SWITCHPRONG7:%.*]]
-; CHECK-NEXT:    i8 0, label [[SWITCHPRONG5:%.*]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP0:%.*]] = call i8 @llvm.ctlz.i8(i8 [[A:%.*]], i1 false)
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[TMP0]], 9
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[SWITCHPRONG2:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i64], [9 x i64]* @switch.table.switch_clz2, i32 0, i8 [[TMP0]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, i64* [[SWITCH_GEP]]
+; CHECK-NEXT:    ret i64 [[SWITCH_LOAD]]
 ; CHECK:       SwitchProng2:
-; CHECK-NEXT:    [[MERGE:%.*]] = phi i64 [ 35, [[ENTRY:%.*]] ], [ 31, [[SWITCHPRONG3]] ], [ 41, [[SWITCHPRONG6]] ], [ 40, [[SWITCHPRONG5]] ], [ 43, [[SWITCHPRONG7]] ], [ 12, [[SWITCHELSE]] ]
-; CHECK-NEXT:    ret i64 [[MERGE]]
-; CHECK:       SwitchProng3:
-; CHECK-NEXT:    br label [[SWITCHPRONG2]]
-; CHECK:       SwitchProng6:
-; CHECK-NEXT:    br label [[SWITCHPRONG2]]
-; CHECK:       SwitchProng5:
-; CHECK-NEXT:    br label [[SWITCHPRONG2]]
-; CHECK:       SwitchProng7:
-; CHECK-NEXT:    br label [[SWITCHPRONG2]]
-; CHECK:       SwitchElse:
-; CHECK-NEXT:    br label [[SWITCHPRONG2]]
+; CHECK-NEXT:    ret i64 12
 ;
 Entry:
   switch i8 %a, label %SwitchElse [
   i8 128, label %SwitchProng2
   i8 64, label %SwitchProng3
   i8 32, label %SwitchProng6
   i8 1, label %SwitchProng7
   i8 0, label %SwitchProng5