[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

84–85

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

118–119

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

118–119

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;
 }
 
+/// A cheap transform: investigate using ctlz and/or cttz as a key to the switch
+/// FIXME: this transform would benifit from proper range analysis in SwitchToLookupTable
+static bool ReduceSwitchRangeWithCtlzOrCttz(SwitchInst &SI,
+                              SmallVectorImpl<uint64_t> &Values,
+                              bool &UseCtlz, bool &UseCttz, bool &UseInvert) {
+  unsigned BitWidth = SI.getCondition()->getType()->getIntegerBitWidth();
+
+  // Avoid applying this transform twice.
+  if (Values.back() == BitWidth)
+    return false;
+
+  // This case is not worth it, as it (usually) requires an additional branch
+  // to check if popcount is 1, and the number of cases is limited to 64, so
+  // it is already fast.
+  uint64_t MaxTableSize = BitWidth > 63 ? UINT64_MAX : 1ULL << BitWidth;
+  const bool DefaultIsReachable =
+      !isa<UnreachableInst>(SI.getDefaultDest()->getFirstNonPHIOrDbg());
+  const bool GeneratingCoveredLookupTable = (MaxTableSize == SI.getNumCases());
+  if (!DefaultIsReachable && !GeneratingCoveredLookupTable)
+    return false;
+
+  bool Invert = false;
+  bool Cttz = false;
+  while (true) {
+    bool GotCollision = false;
+    uint64_t Got = 0;
+    APInt Prev;
+    for (auto &V : Values) {
+      APInt Int = APInt(BitWidth, Invert ? ~V : V);
+      // No need to correct for the bit-width here, as we are just checking for
+      // collisions.
+      unsigned Ctz = (Cttz ?
+          Int.countTrailingZeros() :
+          Int.countLeadingZeros());
+      std::array<SwitchInst::CaseHandle*, 64> Prev;
+      if (Got & (1ULL << Ctz)) {
+        if (&*SI.findCaseValue(ConstantInt::get(SI.getContext(), Invert ? ~Int : Int)) ==
+          Prev[Ctz])
+          continue;
+        GotCollision = true;
+        break;
+      }
+      Got |= (1ULL << Ctz);
+      Prev[Ctz] = &*SI.findCaseValue(ConstantInt::get(SI.getContext(), Invert ? ~Int : Int));
+    }
+    if (!GotCollision) {
+      for (auto &V : Values)
+        V = Cttz ?
+          APInt(BitWidth, Invert ? ~V : V).countTrailingZeros() :
+          APInt(BitWidth, Invert ? ~V : V).countLeadingZeros();
+      if (Cttz)
+        UseCttz = true;
+      else
+        UseCtlz = true;
+      UseInvert = Invert;
+      llvm::sort(Values);
+      return true;
+    }
+    // We do this loop up to 4 times, trying differn't parameters
+    if (!Cttz) {
+      Cttz = true;
+    } else if (!Invert) {
+      Cttz = false;
+      Invert = true;
+    } else
+      break;
+  };
+  return false;
+}
+
 /// 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.

   // 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;
 
   // We organize the range to start from 0, if it is not already close.
-  SmallVector<uint64_t,4> Values;
+  SmallVector<uint64_t, 4> Values;
   for (auto &C : SI->cases())
     Values.push_back(C.getCaseValue()->getValue().getLimitedValue());
   llvm::sort(Values);
 
   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.
+
+  bool UseCtlz = false, UseCttz = false, UseInvert = false;
+  if (ReduceSwitchRangeWithCtlzOrCttz(*SI, Values, UseCtlz, UseCttz, UseInvert))
+    MadeChanges = true;
+
   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 (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.
 
   // Cttz often has an edge condition on 0 which means that the bit-width
   // is important, however here there is no such edge condition because if
   // 0 is the only value then a shift does nothing, and LLVM requires
   // well-formed IR to not have duplicate cases (so the minimum will not
   // be BitWidth)
   unsigned Shift = 64;
   for (auto &V : Values)
     Shift = std::min(Shift, countTrailingZeros((uint64_t)V));
   if (Shift > 0) {
     MadeChanges = true;
     for (auto &V : Values)
       V >>= Shift;
   }
 
   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 *ZeroNotUndef = Builder.getInt1(false);
   Value *Key = SI->getCondition();
-  if (Base > 0) {
+  if (UseInvert) {
+    auto *AllOnes = ConstantInt::getAllOnesValue(Ty);
+    Key = Builder.CreateXor(Key, AllOnes);
+  }
+  if (UseCtlz) {
+    Function *Ctlz = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::ctlz, Ty);
+    Key = Builder.CreateCall(Ctlz, {Key, ZeroNotUndef}, "switch.rangereduce");
+  } else if (UseCttz) {
+    Function *Cttz = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::cttz, Ty);
+    Key = Builder.CreateCall(Cttz, {Key, ZeroNotUndef}, "switch.rangereduce");
+  }
+  if (Base > 0)
     Key = Builder.CreateSub(Key, ConstantInt::get(Ty, Base), "switch.rangereduce");
-  }
   if (Shift > 0) {
     auto *ShiftC = ConstantInt::get(Ty, Shift);
     Function *Fshr = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::fshr, Ty);
     Key = Builder.CreateCall(Fshr, {Key, Key, ShiftC}, "switch.rangereduce");
   }
   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 if (UseCttz)
+      Zeros = Orig->getValue().countTrailingZeros();
+    else
+      Zeros = Orig->getValue().getLimitedValue();
+    auto Sub = (APInt(BitWidth, Zeros) - Base);
     Case.setValue(
         cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
   }
   return true;
 }
 
 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();

test/Transforms/SimplifyCFG/rangereduce.ll

 one:
   ret i128 11984
 two:
   ret i128 1143
 three:
   ret i128 99783
 }
 
-; Optimization shouldn't trigger; too few cases
+; 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:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]
 ; CHECK:       one:

 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_RANGEREDUCE:%.*]] = sub i32 [[A:%.*]], 97
 ; CHECK-NEXT:    switch i32 [[SWITCH_RANGEREDUCE]], 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]] ]

 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_RANGEREDUCE:%.*]] = sub i32 [[A:%.*]], 97
 ; CHECK-NEXT:    switch i32 [[SWITCH_RANGEREDUCE]], 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]]

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:    [[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-NEXT:    [[SWITCH_RANGEREDUCE:%.*]] = sub i8 [[A:%.*]], 123
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE1:%.*]] = call i8 @llvm.fshr.i8(i8 [[SWITCH_RANGEREDUCE]], i8 [[SWITCH_RANGEREDUCE]], i8 1)
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[SWITCH_RANGEREDUCE1]], 5
+; CHECK-NEXT:    br i1 [[TMP0]], 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_GEP:%.*]] = getelementptr inbounds [5 x i64], [5 x i64]* @switch.table.switch_common_right_bits, i32 0, i8 [[SWITCH_RANGEREDUCE1]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, i64* [[SWITCH_GEP]]
 ; CHECK-NEXT:    ret i64 [[SWITCH_LOAD]]
 ; CHECK:       SwitchElse:
 ; CHECK-NEXT:    ret i64 10
 ;
 Entry:
   switch i8 %a, label %SwitchElse [
   i8 123, label %SwitchProng
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:    [[SWITCH_RANGEREDUCE:%.*]] = call i16 @llvm.ctlz.i16(i16 [[A:%.*]], i1 false)
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE1:%.*]] = sub i16 [[SWITCH_RANGEREDUCE]], 8
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i16 [[SWITCH_RANGEREDUCE1]], 8
+; CHECK-NEXT:    br i1 [[TMP0]], 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 [[SWITCH_RANGEREDUCE1]]
+; 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 undef
 ;
 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
   i16 128, label %SwitchProng7
   i16 16, label %SwitchProng5
   i16 32, label %SwitchProng4
   ]
 SwitchElse:                                       ; preds = %Entry
-  ret i64 10
+  ret i64 undef
 SwitchProng:                                      ; preds = %Entry
   ret i64 6
 SwitchProng1:                                     ; preds = %Entry
   ret i64 3
 SwitchProng2:                                     ; preds = %Entry
   ret i64 35
 SwitchProng3:                                     ; preds = %Entry
   ret i64 31
 SwitchProng4:                                     ; preds = %Entry
   ret i64 53
 SwitchProng5:                                     ; preds = %Entry
   ret i64 51
 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:    [[SWITCH_RANGEREDUCE:%.*]] = call i8 @llvm.ctlz.i8(i8 [[A:%.*]], i1 false)
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[SWITCH_RANGEREDUCE]], 9
+; CHECK-NEXT:    br i1 [[TMP0]], 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 [[SWITCH_RANGEREDUCE]]
+; 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 undef
+;
+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
+  ]
+SwitchProng2:                                     ; preds = %Entry
+  ret i64 35
+SwitchProng3:                                     ; preds = %Entry
+  ret i64 31
+SwitchProng6:                                     ; preds = %Entry
+  ret i64 41
+SwitchProng5:                                     ; preds = %Entry
+  ret i64 40
+SwitchProng7:                                     ; preds = %Entry
+  ret i64 43
+SwitchElse:                                     ; preds = %Entry
+  ret i64 undef
+}
+
+;can't be optimized as has a default case
+define i64 @switch_clz3(i8 %a) optsize #0  {
+; CHECK-LABEL: @switch_clz3(
+; CHECK-NEXT:  Entry:
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE:%.*]] = call i8 @llvm.ctlz.i8(i8 [[A:%.*]], i1 false)
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[SWITCH_RANGEREDUCE]], 9
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SWITCHPRONG2:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i64], [9 x i64]* @switch.table.switch_clz3, i32 0, i8 [[SWITCH_RANGEREDUCE]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, i64* [[SWITCH_GEP]]
+; CHECK-NEXT:    ret i64 [[SWITCH_LOAD]]
+; CHECK:       SwitchProng2:
+; CHECK-NEXT:    ret i64 undef
 ;
 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
   ]
 SwitchProng2:                                     ; preds = %Entry
   ret i64 35
 SwitchProng3:                                     ; preds = %Entry
   ret i64 31
 SwitchProng6:                                     ; preds = %Entry
   ret i64 41
 SwitchProng5:                                     ; preds = %Entry
   ret i64 40
 SwitchProng7:                                     ; preds = %Entry
   ret i64 43
 SwitchElse:                                     ; preds = %Entry
-  ret i64 12
+  ret i64 undef
 }
 
 ;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:    [[TMP0:%.*]] = icmp ult i8 [[A:%.*]], 6