Switch to Select optimisations

[kariddi]

Summary

Hello,
here are a bunch of optimisations to add to SimplifyCFG try to convert Switches, when possible and convenient, to selects.

Initially the optimization tries to determine if the switch instruction is just a value select operation. If it is it checks if the the value selection happens between only two values (if more than two values are selected then probably switch table is better).
If the check is successful it tries three approaches to convert Switches into selects.

The first is very simple and just checks if only two cases are present and converts the switch into a simple select.
If there are more than two cases it then tries to check if these cases are grouped in ranges of values that are not overlapped, like in:
switch(a) {

case 0...100:
  return 10;
case 101...200:
  return 20;

}
if this is the case it converts the switch into a comparison with a pivot + select.
As a third approach it tires to check if there is a bit pattern with which it is possible to distinguish between two possible groups of switch cases like in:
a &= 0x3
switch (a) {

case 0:
case 2:
  return 10;
case 1:
case 3:
  return 20;

}

where the mask 0x1 can distinguish between the two groups (if "a" masked with 0x1 is 1 then we are in the second case, otherwise the first).
If this succeeds it substitutes the switch with an "and" + compare with 0 + select.

Please help review :)

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

3445–3450

Can you run clang-format on this?

3456

LLVM convention is to have capitalized values. Pointers and references should lean to the right.

3458

for (SwitchInst::CaseIt I : SI->cases() is a little more concise.

3479–3480

I feel like this would be easier to follow if you used a lambda and captured Result.

3745

This would be more concise as if (SelectValue)

3754–3755

This looks wrong if the bitwidth of Bits exceeds an i64, consider using APInt::getAllOnesValue or APInt::getMaxValue.

[kariddi]

Updates to address David's suggestions

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3445–3450

Done.

3456

Removed because of using the Lambda syntax you suggested

3458

Done

3479–3480

Done.

3745

Done

3754–3755

Done, thanks for this :)

[kariddi]

Whoops , I forgot to add the files with git before creating the diff :P

This is the revision that addresses David's suggestions.

[hans]

lib/Transforms/Utils/SimplifyCFG.cpp

3464

Why is this check needed? Doesn't GetCaseResults already check that the case leads to the common destination unconditionally?

3473

If I understand correctly, UniqueResults is a mapping from result to vector of cases. Could we use a DenseMap instead and save some code here?

3485

I guess the appending happened above, so maybe just "find the PHI"?

3491

nit: a period at the end of comments is preferred.

3497

This doesn't seem to take into account that there could be other instructions in the default destination before the unreachable terminator.

3504

again, doesn't GetCaseResults already check that the case leads to CommonDest?

3544

i assume the icmp should be with 10 here

3557

i would add an assert about ResultVector.size()

3606

Could these comparisons be done with sgt instead? I'd find that easier to read for code that checks whether a is bigger than b.

3624

I haven't had time to look at this one yet.

Do you think the bit pattern variant could be broken out to a separate patch?

3705

I don't think the "or more" case is supported, though?

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3464

Yeah, you are right. Thanks for this , makes it much cleaner!

3473

The main problem of DenseMap is that it is unordered. We need to enforce the same order every run if we want repeatability of output. Using a vector here makes it easier and probably faster, because the typical size of the vector here is in that spot where actually linear scanning a vector is usually faster.

3485

Done

3491

Done

3497

Good spot! :) I added a check to also be sure the basic block contains only one instruction.

3504

Yep

3544

Done :)

3557

Done.

3606

I have no preference on the matter, so I guess its ok :)

3624

Mmm, this is a rather important optimization for the use case I'm trying to cover. Do you think it is really necessary to put it in a separate patch later on?

3705

Yeah, we support just one PHI node here :)

[kariddi]

I addressed all Hans comments with the exception of using a DenseMap instead of a SmallVector for the results and splitting the bit patterns in a separate patch for now.

[hans]

lib/Transforms/Utils/SimplifyCFG.cpp

3473

That's a good point. I wish the code was simpler here, though. It seems like what we want is really just

UniqueResults[Results[0]].push_back(CaseVal);

Maybe if we break out the code to a helper function, "addUniqueResult" or something?

3494

Instead of checking the size, I would probably just grab for the first instruction and check if that's an UnreachableInst:

UnreachableInst *UI = dyn_cast<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg());

Actually, maybe this can just be baked into the if below:

if (!DefaultResult && !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg())

3624

It's just that a bigger patch takes longer to review. I haven't looked at this part yet, but will try to do so as soon as I can.

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3473

Sound like a good idea!

3494

Done!

3624

Thank you very much for your help hans :)

[kariddi]

Implemented the latest Hans's suggestions

[hans]

I think I understand the "bit pattern switch" a little better now, but it's not easy to understand from the code. I've tried to make some suggestions to make it more clear.

lib/Transforms/Utils/SimplifyCFG.cpp

80

If we're going to expose these typedef's throughout the whole file, they need less generic names.

3442

I would just take the "Constant *Result" as a parameter.

It would be nice to have a comment explaining what the function does, and that would also be a good place to the mapping that UniqueResults is.

3454

I know I'm old-school, but with less fancy C++, I think the code would become more clear:

for (auto &I : UniqueResults) {
  if (I.first == Result) {
    I.second.push_back(CaseVal)
    return;
  }
}
UniqueResults.push_back(std::make_pair(Result, SmallVector<ConstantInt*, 4>(1, CaseVal)));

3505

It would be nice with a comment about what "known ones and zeroes" mean. Maybe here, or when they're computed further down in the function.

Actually, maybe the parameters need better names. I commented about this further down.

3598

I think I commented on these before. It's just that with a name such as "first is bigger", I'd find it natural if the code to say that too, i.e.

FirstIsBigger = MinCaseFirst->getValue().sgt(MaxCaseSecond->getValue());

3651

These are the same values that were computed in the if statements above. Rather than repurposing these variables, I'd hoist this to above the if statement and try to give them better name and comment (it's not obvious to me what "unambigous patterns" mean).

Maybe (but good names are hard):

APInt FirstRangeSelectBits = FirstRangeKnownOneBits & SecondRangeKnownZeroBits;
APInt SecondRangeSelectBits = SecondRangeKnownOneBits & FirstRangeKnownZeroBits;
if (!DefaultCanTrigger && (FirstRangeSelectBits || SecondRangeSelectBits) {
  ...
}

Actually, since we don't do anything interesting if DefaultCanTrigger is true, we could just bail out early for that case - near the top:

if (DefaultCanTrigger)
  return nullptr;

3723

Since this ins't a bitmask, but a width, I would call it BitWidth, or CondWidth or something.

3725

Just to make the code easier to follow, I'd spell out "Compute known bits of the Condition." in a comment.

3728

I'd use the terminaly "known" instead of fixed or stuck. I'd also prefix the variable with Num since it's a count, not mask - something like:

const unsigend NumKnownBits = (KnownCondZeroBits | KnownCondOneBits).countPopulation();

3730

I'd just declare this when it's first used below.

3745

I find these names a little bit cryptic. What do you think about something like FirstRangeKnownZeroBits. Though it's a bit longer, it makes the contents clearer.

Also, since these declarators are all on separate lines anyway, I'd just write them out as one declaration per line.

3749

it's not clear to me what a "hit" is

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3442

Done.

3454

I think you are right :) Old school seems cleaner here!

3505

Done.

3598

Done :)

3651

Fixed :)

3723

Done

3725

Done

3728

Done

3730

Done

3745

Done

3749

I changed the name to something that is a little bit more similar to what it actually is

[kariddi]

Updated to comply with Hans's latest comments.

Thanks for all the effort put in reviewing this!

[hans]

lib/Transforms/Utils/SimplifyCFG.cpp

79

Thanks! These names are better. A comment explaining what the components of the pair represent would also be great.

3441

How about: "add CaseVal to the list of cases that generate Result".

3479

nit: "be sure it to be" ?

3480

It does occur in LLVM code, but I think the more common style is to not do explicit comparisons against nullptr, but rather do

if (!PHI) {

This applies throughout the patch and I think will simplify some lines.

3495

Just check for nullptr with !DefaultResult, and drop the extra parentheses.

3507

Thanks! I think the expanded comment and new variable names helps the readability of this code a lot.

3516

I would break this comment up into three comments and move them down to where the respective computation occurs in the for loop, i.e.

// Compute number of cases matching the known bits of the condition.
(code)

// Update known bits of case values.
(code)

// Compute min and max case value.
(code)

3548

Make ResultVector const-ref.

3562

Actually, I'd just do

if (DefaultResult)

here.

3596

Make ResultVector const-ref.

3640

Make ResultVector const-ref.

3670

the outer if-statement has already checked that either FirstResultGroupSelectBits or Second...Bits are non-zero, so this could just be an else branch, possibly with an assert.

3701

Can you explain (ideally by adding a comment) why we're not removing this successor?

3716

I would not declare this until it's first used, which seems to be after the InitializeUniqueCases call below.

3724

Since this is only used in the if statement below, I'm not sure it's worth a separate variable. I'd just check UniqueResults.size() in the if statement directly.

3733

I'd s/Zero/Zeroes/ and s/One/Ones/ in the second variable name.

3752

No point declaring the variable until it's used.

test/Transforms/SimplifyCFG/UnreachableEliminate.ll

51

Doesn't this change the test to not check the problem in the original bug? If you change one of the results that the switch go to to not be constant, that should defeat the switch-to-select transform.

test/Transforms/SimplifyCFG/switch-to-select-bitpattern.ll

4

might as well spell out "def" as "default" here and below to simplify for the reader

19

i'd put this comment down by the llvm function it represents

35

I'd drop the #0. Also a comment saying what's being tested, i.e. that this switch can't be transformed to select because it has a default.

66

i'd drop the #0

68

i think we should check more explicitly what's in the select.

96

would be nice to have tests for both the default with unreachable instruction, and the clever case where we know enough bits to figure out the default case can never happen.

test/Transforms/SimplifyCFG/switch-to-select-range.ll

4

again i'd drop the #0 here and below

6

a comment about what the test is intended to test, i.e. why this can't become a select, would be good.

37

we should check the select explicitly

test/Transforms/SimplifyCFG/switch-to-select-two-case.ll

14

again, i'd put the comment by the llvm function definition

27

we should check exactly what's being selected and compared here

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

79

Added

3441

Done!

3479

Modified :P

3480

I see. Sorry, I'm very used to the other way or writing it (because I somehow like it more because is more explicit) so I always forget of this rule :P

Fixed.

3495

Done

3516

Done.
I also kept the common outside of the loop, so that it works like an overview and the inner comments specify where that happens.

3548

Done

3562

Hmm, I prefer here changing DefaultCanTrigger to :

DefaultCanTrigger = DefaultResult;

and then use DefaultCanTrigger in the if, because that is used everywhere else we need to check if the default can trigger, so seems a little bit more coherent in my opinion. (Makes more clear to the reader what we want to test for)
What do you think?

3596

Done

3640

Done.

3670

Good catch!

3701

I think this is actually a bug ... the check should be with Destination.
I also added a fix for the PHI node.

3716

I think ResultType is not used anymore now.
Removed!

3724

Done

3733

Done.

3752

Legacy declaration :|
Done.

test/Transforms/SimplifyCFG/UnreachableEliminate.ll

51

Fixed!

test/Transforms/SimplifyCFG/switch-to-select-bitpattern.ll

4

Ok.

19

Good idea.

35

Done

66

Done

68

Done

96

There is a problem actually with that.

If the default block is explicitly unreachable then the Unreachable case elimination (an optimization run earlier) substitutes the default with one of the cases.
This might move one of the case group results from the UniqueResult vector to the DefaultResult.
The UniqueResult vector reduces its size from 2 to 1 and the optimization bails out.

Actually there could be a way maybe to improve it to cover also this case ...
In the case we only have one result in UniqueResult then the SelectBitmask is just the KnownOnes for that group.
If we can determine that the cases in the result group are all and the only possible case values for the switch condition that have Ones in that position then we can use the KnownOnes as the bit mask.

So , in this example:
int foo3_explicit_without_default(int a) {

a &= 0x6;
switch (a) {
  case 0:
    return 1;
  case 2:
    return 2;
  case 4:
    return 1;
  case 6:
    return 2;
}
__builtin_unreachable();

}

We have two groups, one generating the value "2" and one generating the value "1". The default is unreachable.

after optimization becomes:

define i32 @foo3_explicit_without_default(i32 %a) nounwind readnone ssp uwtable {

%1 = and i32 %a, 6
switch i32 %1, label %4 [
  i32 6, label %3
  i32 2, label %2
]

; <label>:2 ; preds = %0

br label %4

; <label>:3 ; preds = %0

br label %4

; <label>:4 ; preds = %0, %3, %2

%.0 = phi i32 [ 2, %3 ], [ 2, %2 ], [ 1, %0 ]
ret i32 %.0

}

Which is not optimizable, because the group generating "1" has been moved to the default.
But , because:

• KnownOnes for the cases generating "2" is 0x4, and
• the possible bit patterns for the switch condition are only 0x0, 0x2, 0x4, 0x6 and
• The cases in the group generating "2" are all and the only valid cases that match the KnownOnes mask for "2".

Then that mask can be used to differentiate between the default and the group generating "2".

Should I modify the algorithm to match this case in this patch? Or is it better to do it separately? (It would involve changing everything to support UniqueResults.size() < 2).

test/Transforms/SimplifyCFG/switch-to-select-range.ll

4

Done

6

Done

37

Done

test/Transforms/SimplifyCFG/switch-to-select-two-case.ll

14

Done

27

Done

[kariddi]

Latest corrections applied

[hans]

lib/Transforms/Utils/SimplifyCFG.cpp

3523

Isn't it the number of cases covered by the "pattern", rather than the other way around?

3562

That's fine.

3709

It's not clear from just reading the function what Destination is. It might be clearer to just use PHI->gerParent().

test/Transforms/SimplifyCFG/switch-to-select-bitpattern.ll

96

Sounds like that should be done separately.

Can we just add a test for the case the default case is not explicitly unreachable, but we figure it out based on known bits of the condition and number of cases?

Actually, couldn't the unreachable case elimination have that logic instead of our transform?

[kariddi]

I'on travel right now , so I will have to wait until I land before being able to produce the patch to address the latest comments, but I wanted to answer in advance ;-)

lib/Transforms/Utils/SimplifyCFG.cpp

3523

Ouch, my brain got reversed while writing this comment :-D

3709

I'll do that

test/Transforms/SimplifyCFG/switch-to-select-bitpattern.ll

96

I'll do that. What do you mean with the unreachable optimization to have the logic though? Do you mean calling the ConvertToSelectBitpattern within it? If that is the case I immagine we'll have to duplicate some code from SwitchToSelect into it. Also, there might be some optimizations that run afterwards that might help even more in the success of the optimization, but I don't have the code in front of me right now, so, I'll wait to confirm it.

[kariddi]

test/Transforms/SimplifyCFG/switch-to-select-bitpattern.ll

96

Let me know if the test you mean is the one in the latest revision.
The only difference with the explicit default case is that the result in the switch for the default is undef.

[kariddi]

Addresses latest suggestions

[hans]

The code for the first optimization, ConvertTwoCaseSwitch() looks good to me. I suggest you break that out to a separate patch so we can get that landed and make the rest of the code easier to review.

test/Transforms/SimplifyCFG/switch-to-select-bitpattern.ll

96

I just mean that checking known bits of the condition comparing that against the cases and figuring out if the default case if unreachable, seems like a more general optimization. Instead of just doing it in this case, where the switch is selecting between values, we should do it for all switches.

This way, we optimize more switches, and the code for the switch-to-select- transformation becomes simpler.

[kariddi]

Seems like a good idea, to split out ConvertTwoCaseSwitch() out if that helps out committing all the initial infrastructure.

[kariddi]

I'll make another patch with that and add you as a reviewer :)

lib/Transforms/Utils/SimplifyCFG.cpp

 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
 
 namespace {
+  // The first field contains the value that the switch produces when a certain
+  // case group is selected, and the second field is a vector containing the cases
+  // composing the case group.
+  typedef SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2>
+    SwitchCaseResultVectorTy;
+  // The first field contains the phi node that generates a result of the switch
+  // and the second field contains the value generated for a certain case in the switch
+  // for that PHI.
+  typedef SmallVector<std::pair<PHINode *, Constant *>, 4> SwitchCaseResultsTy;
+
   /// ValueEqualityComparisonCase - Represents a case of a switch.
   struct ValueEqualityComparisonCase {
     ConstantInt *Value;

   return Res.size() > 0;
 }
 
+// MapCaseToResult - This is an helper function used to
+// add CaseVal to the list of cases that generate Result.
+static void MapCaseToResult(ConstantInt *CaseVal,
+    SwitchCaseResultVectorTy &UniqueResults,
+    Constant *Result) {
+  for (auto &I : UniqueResults) {
+    if (I.first == Result) {
+      I.second.push_back(CaseVal);
+      return;
+    }
+  }
+  UniqueResults.push_back(std::make_pair(Result,
+        SmallVector<ConstantInt*, 4>(1, CaseVal)));
+}
+
+// InitializeUniqueCases - Helper function that initializes a map containing
+// results for the PHI node of the common destination block for a switch
+// instruction. Returns false if multiple PHI nodes have been found or if
+// there is not a common destination block for the switch.
+static bool InitializeUniqueCases(
+    SwitchInst *SI, const DataLayout *DL, PHINode *&PHI,
+    BasicBlock *&CommonDest,
+    SwitchCaseResultVectorTy &UniqueResults,
+    Constant *&DefaultResult) {
+  for (auto &I : SI->cases()) {
+    ConstantInt *CaseVal = I.getCaseValue();
+
+    // Resulting value at phi nodes for this case value.
+    SwitchCaseResultsTy Results;
+    if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results,
+                        DL))
+      return false;
+
+    // Only one value per case is permitted
+    if (Results.size() > 1)
+      return false;
+    MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second);
+
+    // Check the PHI consistency.
+    if (!PHI)
+      PHI = Results[0].first;
+    else if (PHI != Results[0].first)
+      return false;
+  }
+  // Find the default result value.
+  SmallVector<std::pair<PHINode *, Constant *>, 1> DefaultResults;
+  BasicBlock *DefaultDest = SI->getDefaultDest();
+  GetCaseResults(SI, nullptr, SI->getDefaultDest(), &CommonDest, DefaultResults,
+                 DL);
+  // If the default value is not found abort unless the default destination
+  // is unreachable.
+  DefaultResult =
+      DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr;
+  if ((!DefaultResult &&
+        !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg())))
+    return false;
+
+  return true;
+}
+
+// AnalyzeSwitchCases - Helper function to compute information about switch
+// cases, like known ones and zeroes, the minimum and the maximum case and
+// the number of case patterns that match the bitmask of the switch value.
+// KnownBitsCond parameters are a bit vector containing respectively the bits
+// that are known to be one or zero of the condition of the switch.
+// KnownBitsCase are instead the bits known to be one or zero for all the case
+// values contained in the vector of cases passed as input.
+static void AnalyzeSwitchCases(const SmallVectorImpl<ConstantInt *> &Cases,
+                               const APInt &KnownZeroBitsCond,
+                               const APInt &KnownOneBitsCond,
+                               APInt &KnownZeroBitsCase,
+                               APInt &KnownOneBitsCase, ConstantInt *&MinCase,
+                               ConstantInt *&MaxCase, unsigned &ValidCases) {
+  MinCase = Cases[0];
+  MaxCase = Cases[0];
+  // Compute the number of patterns covered by the cases of each result,
+  // the minimum and maximum cases and the zeroes and ones for this case group.
+  for (auto &Case : Cases) {
+    bool CaseMatchesCondPattern =
+        ((~Case->getValue() & KnownZeroBitsCond) == KnownZeroBitsCond) &&
+        ((Case->getValue() & KnownOneBitsCond) == KnownOneBitsCond);
+
+    // Increment the number of cases covered by
+    // the condition pattern in the group.
+    if (CaseMatchesCondPattern)
+      ++ValidCases;
+
+    // Compute the known ones and zeros of this case group.
+    KnownZeroBitsCase &= ~(Case->getValue());
+    KnownOneBitsCase &= Case->getValue();
+    // Compute the minimum and maximum case.
+    if (MinCase->getValue().sgt(Case->getValue()))
+      MinCase = Case;
+    if (MaxCase->getValue().slt(Case->getValue()))
+      MaxCase = Case;
+  }
+}
+
+// ConvertTwoCaseSwitch - Helper function that checks if it is possible to
+// transform a switch with only two cases (or two cases + default)
+// that produces a result into a value select.
+// Example:
+// switch (a) {
+//   case 10:                %0 = icmp eq i32 %a, 10
+//     return 10;            %1 = select i1 %0, i32 10, i32 4
+//   case 20:        ---->   %2 = icmp eq i32 %a, 20
+//     return 2;             %3 = select i1 %2, i32 2, i32 %1
+//   default:
+//     return 4;
+// }
+static Value *
+ConvertTwoCaseSwitch(const SwitchCaseResultVectorTy &ResultVector,
+                     Constant *DefaultResult, Value *Condition,
+                     IRBuilder<> &Builder) {
+  assert(ResultVector.size() == 2 &&
+      "We should have exactly two unique results at this point");
+  // If we are selecting between only two cases transform into a simple
+  // select or a two-way select if default is possible.
+  if (ResultVector[0].second.size() == 1 &&
+      ResultVector[1].second.size() == 1) {
+    ConstantInt *const FirstCase = ResultVector[0].second[0];
+    ConstantInt *const SecondCase = ResultVector[1].second[0];
+
+    bool DefaultCanTrigger = DefaultResult;
+    Value *SelectValue = ResultVector[1].first;
+    if (DefaultCanTrigger) {
+      Value *const ValueCompare =
+          Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp");
+      SelectValue = Builder.CreateSelect(ValueCompare, ResultVector[1].first,
+                                         DefaultResult, "switch.select");
+    }
+    Value *const ValueCompare =
+        Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp");
+    return Builder.CreateSelect(ValueCompare, ResultVector[0].first, SelectValue,
+                                "switch.select");
+  }
+
+  return nullptr;
+}
+
+// ConvertRangeSwitch - Helper function that checks if it is possible to
+// transform a switch with cases arranged into two ordered not overlapping
+// groups into a value select.
+//
+// Example:
+// switch (a) {
+//   case 0: case 2:
+//   case 4: case 6:
+//   case 8: case 10:
+//   case 12: case 14:
+//     return 10;         ---->   %0 = icmp ult i32 %a, 15
+//                                %1 = select i1 %0, i32 10, i32 20
+//   case 16: case 18:
+//   case 20: case 22:
+//   case 24: case 26:
+//   case 28: case 30:
+//     return 20;
+// }
+static Value *
+ConvertRangeSwitch(const SwitchCaseResultVectorTy &ResultVector,
+                   Value *Condition,
+                   bool DefaultCanTrigger, ConstantInt *MinCaseFirst,
+                   ConstantInt *MinCaseSecond, ConstantInt *MaxCaseFirst,
+                   ConstantInt *MaxCaseSecond, IRBuilder<> &Builder) {
+  const bool FirstIsBigger =
+    MinCaseFirst->getValue().sgt(MaxCaseSecond->getValue());
+  const bool SecondIsBigger =
+      MinCaseSecond->getValue().sgt(MaxCaseFirst->getValue());
+  // If the case statements ranges do not overlap use a comparison to
+  // distinguish between the two groups.
+  if (!DefaultCanTrigger && (FirstIsBigger || SecondIsBigger)) {
+    ConstantInt *Pivot = SecondIsBigger ? MaxCaseFirst : MaxCaseSecond;
+    Value *const SelectLHS =
+        SecondIsBigger ? ResultVector[0].first : ResultVector[1].first;
+    Value *const SelectRHS =
+        SecondIsBigger ? ResultVector[1].first : ResultVector[0].first;
+    Value *const ValueCompare =
+        Builder.CreateICmpSGT(Condition, Pivot, "switch.rangesub");
+    return Builder.CreateSelect(ValueCompare, SelectRHS, SelectLHS,
+                                "switch.rangeselect");
+  }
+
+  return nullptr;
+}
+
+// ConvertBitPatternSwitch - Helper function that checks if it is possible to
+// transform a switch with cases that are groupable by some bit pattern into
+// a value select.
+//
+// Example:
+// a &= 0x6;
+// switch (a) {
+//   case 0:
+//     return 1;
+//   case 2:
+//     return 2;
+//   case 4:         ---->  %0 = and i32 %a, 6
+//     return 1;            %1 = and i32 %0, 2
+//   case 6:                %2 = icmp eq i32 %1, 0
+//     return 2;            %3 = select i1 %3, i32 1, i32 2
+//   default:
+//     return 10;
+// }
+static Value *ConvertBitPatternSwitch(const SwitchCaseResultVectorTy &ResultVector,
+    Value *Condition,
+    bool DefaultCanTrigger, const APInt &FirstResultGroupZeroBits,
+    const APInt &FirstResultGroupOneBits,
+    const APInt &SecondResultGroupZeroBits,
+    const APInt &SecondResultGroupOneBits, IRBuilder<> &Builder) {
+
+  if (DefaultCanTrigger)
+    return nullptr;
+  // FirstResultGroupSelectBits and SecondResultGroupSelectBits
+  // are bitvectors containing the bits that are always one
+  // in a group of case labels and always zero in the other
+  APInt FirstResultGroupSelectBits = FirstResultGroupOneBits &
+    SecondResultGroupZeroBits;
+  APInt SecondResultGroupSelectBits = SecondResultGroupOneBits &
+    FirstResultGroupZeroBits;
+  // If there is no default case and we have unambiguous
+  // patterns do it with one select and one compare.
+  if (FirstResultGroupSelectBits != 0 || SecondResultGroupSelectBits != 0) {
+    Value *ValueCompare = nullptr;
+    // The comparison checks for ones that are always present in
+    // one of the groups that are always zero in the other.
+    if (FirstResultGroupSelectBits != 0) {
+      ConstantInt *const MaskValue =
+          ConstantInt::get(Condition->getContext(), FirstResultGroupSelectBits);
+      ValueCompare =
+          Builder.CreateAnd(Condition, MaskValue, "switch.selectmask");
+      ValueCompare = Builder.CreateICmpNE(
+          ValueCompare, ConstantInt::get(Condition->getType(), 0),
+          "switch.selectcmp");
+    } else {
+      assert(SecondResultGroupSelectBits != 0 &&
+          "One of the two select bit patterns should be different from zero");
+      ConstantInt *const MaskValue =
+          ConstantInt::get(Condition->getContext(), SecondResultGroupSelectBits);
+      ValueCompare =
+          Builder.CreateAnd(Condition, MaskValue, "switch.selectmask");
+      ValueCompare = Builder.CreateICmpEQ(
+          ValueCompare, ConstantInt::get(Condition->getType(), 0),
+          "switch.selectcmp");
+    }
+    return Builder.CreateSelect(ValueCompare, ResultVector[0].first,
+                                ResultVector[1].first, "switch.select");
+  }
+
+  return nullptr;
+}
+
+// RemoveSwitchAfterSelectConversion - Helper function to cleanup a switch
+// instruction that has been converted into a select, fixing up PHI nodes and
+// basic blocks.
+static void RemoveSwitchAfterSelectConversion(SwitchInst *SI, PHINode *PHI,
+                                              Value *SelectValue,
+                                              IRBuilder<> &Builder) {
+  BasicBlock *SelectBB = SI->getParent();
+  if (PHI->getBasicBlockIndex(SelectBB) >= 0)
+    PHI->removeIncomingValue(SelectBB);
+  PHI->addIncoming(SelectValue, SelectBB);
+
+  Builder.CreateBr(PHI->getParent());
+
+  // Remove the switch.
+  for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
+    BasicBlock *Succ = SI->getSuccessor(i);
+
+    if (Succ == PHI->getParent())
+      continue;
+    Succ->removePredecessor(SelectBB);
+  }
+  SI->eraseFromParent();
+}
+
+/// SwitchToSelect - If the switch is only used to initialize one or more
+/// phi nodes in a common successor block with only two different
+/// constant values, replace the switch with select.
+static bool SwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder,
+                           const DataLayout *DL, AssumptionTracker *AT) {
+  Value *const Cond = SI->getCondition();
+  PHINode *PHI = nullptr;
+  BasicBlock *CommonDest = nullptr;
+  Constant *DefaultResult;
+  SwitchCaseResultVectorTy UniqueResults;
+  // Collect all the cases that will deliver the same value from the switch.
+  if (!InitializeUniqueCases(SI, DL, PHI, CommonDest, UniqueResults,
+                             DefaultResult))
+    return false;
+  // Selects choose between maximum two values.
+  if (UniqueResults.size() != 2)
+    return false;
+  assert(PHI != nullptr && "PHI for value select not found");
+
+  const unsigned BitWidth = Cond->getType()->getIntegerBitWidth();
+
+  APInt KnownZerosCond(BitWidth, 0), KnownOnesCond(BitWidth, 0);
+  // Compute known bits of the Condition of the Switch statement.
+  computeKnownBits(Cond, KnownZerosCond, KnownOnesCond, DL, 0, AT, SI);
+  // Number of bits that are fixed in the switch condition value.
+  const unsigned NumKnownCondBits =
+      (KnownZerosCond | KnownOnesCond).countPopulation();
+
+  Builder.SetInsertPoint(SI);
+  Value *SelectValue = ConvertTwoCaseSwitch(
+      UniqueResults,
+      DefaultResult, Cond, Builder);
+  if (SelectValue) {
+    RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder);
+    return true;
+  }
+
+  // The switch has more than only two cases. Check to see if we can
+  // still transform it into a select
+  APInt FirstResultGroupZeroBits = APInt::getAllOnesValue(BitWidth);
+  APInt FirstResultGroupOneBits = APInt::getAllOnesValue(BitWidth);
+  APInt SecondResultGroupZeroBits = APInt::getAllOnesValue(BitWidth);
+  APInt SecondResultGroupOneBits = APInt::getAllOnesValue(BitWidth);
+  unsigned FirstGroupValidCases = 0, SecondGroupValidCases = 0;
+  ConstantInt *MinCaseFirst = nullptr, *MinCaseSecond = nullptr,
+              *MaxCaseFirst = nullptr, *MaxCaseSecond = nullptr;
+  AnalyzeSwitchCases(UniqueResults[0].second, KnownZerosCond, KnownOnesCond,
+                     FirstResultGroupZeroBits, FirstResultGroupOneBits,
+                     MinCaseFirst, MaxCaseFirst, FirstGroupValidCases);
+  AnalyzeSwitchCases(UniqueResults[1].second, KnownZerosCond, KnownOnesCond,
+                     SecondResultGroupZeroBits, SecondResultGroupOneBits,
+                     MinCaseSecond, MaxCaseSecond, SecondGroupValidCases);
+  // The default case can trigger if a default value has been found and
+  // if there are some possible bit combination of the condition value
+  // that are not covered from the case labels
+  bool DefaultCanTrigger = (((1 << (BitWidth - NumKnownCondBits)) -
+                        (FirstGroupValidCases + SecondGroupValidCases)) != 0);
+  DefaultCanTrigger &= (bool)DefaultResult;
+
+  SelectValue = ConvertRangeSwitch(
+      UniqueResults, Cond, DefaultCanTrigger,
+      MinCaseFirst, MinCaseSecond,
+      MaxCaseFirst, MaxCaseSecond, Builder);
+
+  if (SelectValue) {
+    RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder);
+    return true;
+  }
+
+  // If we couldn't split the switch results into two ranges of values
+  // try finding a bit pattern that covers the cases and test on that
+  SelectValue = ConvertBitPatternSwitch(UniqueResults,
+      Cond, DefaultCanTrigger,
+      FirstResultGroupZeroBits, FirstResultGroupOneBits,
+      SecondResultGroupZeroBits, SecondResultGroupOneBits, Builder);
+
+  if (SelectValue) {
+    RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, Builder);
+    return true;
+  }
+
+  // The switch couldn't be converted into a select.
+  return false;
+}
+
 namespace {
   /// SwitchLookupTable - This class represents a lookup table that can be used
   /// to replace a switch.

   if (EliminateDeadSwitchCases(SI, DL, AT))
     return SimplifyCFG(BB, TTI, DL, AT) | true;
 
-  if (ForwardSwitchConditionToPHI(SI))
+  if (SwitchToSelect(SI, Builder, DL, AT))
     return SimplifyCFG(BB, TTI, DL, AT) | true;
 
+  if (ForwardSwitchConditionToPHI(SI))
+    return SimplifyCFG(BB, TTI, DL, AT) | true;
+ 
   if (SwitchToLookupTable(SI, Builder, TTI, DL))
     return SimplifyCFG(BB, TTI, DL, AT) | true;
 

test/Transforms/SimplifyCFG/UnreachableEliminate.ll

 }
 
 ; PR9450
-define i32 @test4(i32 %v) {
+define i32 @test4(i32 %v, i32 %w) {
 ; CHECK: entry:
 ; CHECK-NEXT:  switch i32 %v, label %T [
 ; CHECK-NEXT:    i32 3, label %V

 default:
         unreachable
 U:
-        ret i32 1
+        ret i32 %w
 T:
         ret i32 2
 }

test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

   %x = phi i32 [ 3, %sw.default ], [ 7, %sw.bb1 ], [ 9, %entry ]
   ret i32 %x
 ; CHECK-LABEL: @twocases(
-; CHECK: switch i32
+; CHECK-NOT: switch i32
 ; CHECK-NOT: @switch.table
+; CHECK: %switch.selectcmp
+; CHECK-NEXT: %switch.select
+; CHECK-NEXT: %switch.selectcmp1
+; CHECK-NEXT: %switch.select2
 }
 
 ; Don't build tables for switches with TLS variables.

test/Transforms/SimplifyCFG/switch-to-select-bitpattern.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+; int foo3_with_default(int a) {
+;   switch (a) {
+;     case 0:
+;       return 1;
+;     case 1:
+;       return 2;
+;     case 2:
+;       return 1;
+;     case 3:
+;       return 2;
+;     default:
+;       return 10;
+;   }
+; }
+;
+; This switch cannot be transformed , because the algorithm
+; doesn't handle cases with reachable default cases.
+
+define i32 @foo3_with_default(i32 %a) {
+; CHECK-LABEL: @foo3_with_default
+; CHECK: switch i32
+entry:
+  switch i32 %a, label %sw.default [
+    i32 0, label %sw.bb
+    i32 1, label %sw.bb1
+    i32 2, label %sw.bb2
+    i32 3, label %sw.bb3
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.bb2:
+  br label %return
+
+sw.bb3:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 10, %sw.default ], [ 2, %sw.bb3 ], [ 1, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %sw.bb ]
+  ret i32 %retval.0
+}
+
+; int foo3_without_default(int a) {
+;   a &= 0x6;
+;   switch (a) {
+;     case 0:
+;       return 1;
+;     case 2:
+;       return 2;
+;     case 4:
+;       return 1;
+;     case 6:
+;       return 2;
+;     default:
+;       return 10;
+;   }
+; }
+;
+; The default in this switch case is unreachable.
+; This is detected and the switch is then processed.
+
+define i32 @foo3_without_default(i32 %a) {
+; CHECK-LABEL: @foo3_without_default
+; CHECK: %switch.select = select i1 %switch.selectcmp, i32 1, i32 2
+entry:
+  %and = and i32 %a, 6
+  switch i32 %and, label %sw.default [
+    i32 0, label %sw.bb
+    i32 2, label %sw.bb1
+    i32 4, label %sw.bb2
+    i32 6, label %sw.bb3
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.bb2:
+  br label %return
+
+sw.bb3:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 10, %sw.default ], [ 2, %sw.bb3 ], [ 1, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %sw.bb ]
+  ret i32 %retval.0
+}
+
+; int foo3_explicit_without_default(int a) {
+;   a &= 0x6;
+;   switch (a) {
+;     case 0:
+;       return 1;
+;     case 2:
+;       return 2;
+;     case 6:
+;       return 2;
+;     case 4:
+;       return 1;
+;   }
+; }
+;
+; The default in this switch case is not present and the result is undef
+; This is detected and the switch is then processed
+
+define i32 @foo3_explicit_without_default(i32 %a) {
+  %1 = and i32 %a, 6
+  switch i32 %1, label %6 [
+    i32 0, label %2
+    i32 2, label %3
+    i32 6, label %4
+    i32 4, label %5
+  ]
+
+; <label>:2                                       ; preds = %0
+  br label %6
+
+; <label>:3                                       ; preds = %0
+  br label %6
+
+; <label>:4                                       ; preds = %0
+  br label %6
+
+; <label>:5                                       ; preds = %0
+  br label %6
+
+; <label>:6                                       ; preds = %5, %4, %3, %2, %0
+  %.0 = phi i32 [ undef, %0 ], [ 1, %5 ], [ 2, %4 ], [ 2, %3 ], [ 1, %2 ]
+  ret i32 %.0
+}

test/Transforms/SimplifyCFG/switch-to-select-range.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+; The default case here stops us to be able to optimize,
+; because the range has holes.
+define i32 @foo2_with_default(i32 %a) {
+; CHECK-LABEL: @foo2_with_default
+; CHECK-NOT: select
+entry:
+  switch i32 %a, label %sw.default [
+    i32 10, label %sw.bb
+    i32 11, label %sw.bb
+    i32 12, label %sw.bb
+    i32 13, label %sw.bb
+    i32 14, label %sw.bb
+    i32 15, label %sw.bb
+    i32 19, label %sw.bb1
+    i32 20, label %sw.bb1
+    i32 21, label %sw.bb1
+    i32 22, label %sw.bb1
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 30, %sw.default ], [ 20, %sw.bb1 ], [ 10, %sw.bb ]
+  ret i32 %retval.0
+}
+
+; The default case here is unreachable, we detect that and so we can
+; optimize to a select.
+define i32 @foo2_without_default(i32 %a) {
+; CHECK-LABEL: @foo2_without_default
+; CHECK: %switch.rangeselect = select i1 %switch.rangesub, i32 20, i32 10
+entry:
+  %shl = shl i32 %a, 1
+  %and = and i32 %shl, 30
+  switch i32 %and, label %sw.default [
+    i32 0, label %sw.bb
+    i32 2, label %sw.bb
+    i32 4, label %sw.bb
+    i32 6, label %sw.bb
+    i32 8, label %sw.bb
+    i32 10, label %sw.bb
+    i32 12, label %sw.bb
+    i32 14, label %sw.bb
+    i32 16, label %sw.bb1
+    i32 18, label %sw.bb1
+    i32 20, label %sw.bb1
+    i32 22, label %sw.bb1
+    i32 24, label %sw.bb1
+    i32 26, label %sw.bb1
+    i32 28, label %sw.bb1
+    i32 30, label %sw.bb1
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.default:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 30, %sw.default ], [ 20, %sw.bb1 ], [ 10, %sw.bb ]
+  ret i32 %retval.0
+}

test/Transforms/SimplifyCFG/switch-to-select-two-case.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+; int foo1_with_default(int a) {
+;   switch(a) {
+;     case 10:
+;       return 10;
+;     case 20:
+;       return 2;
+;   }
+;   return 4;
+; }
+
+define i32 @foo1_with_default(i32 %a) {
+; CHECK-LABEL: @foo1_with_default
+; CHECK: icmp eq i32
+; CHECK-NEXT: %switch.select = select i1 %switch.selectcmp, i32 2, i32 4
+; CHECK-NEXT: %switch.selectcmp1 = icmp eq i32 %a, 10
+; CHECK-NEXT: %switch.select2 = select i1 %switch.selectcmp1, i32 10, i32 %switch.select
+entry:
+  switch i32 %a, label %sw.epilog [
+    i32 10, label %sw.bb
+    i32 20, label %sw.bb1
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.epilog:
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ 4, %sw.epilog ], [ 2, %sw.bb1 ], [ 10, %sw.bb ]
+  ret i32 %retval.0
+}
+
+; int foo1_without_default(int a) {
+;   switch(a) {
+;     case 10:
+;       return 10;
+;     case 20:
+;       return 2;
+;   }
+;   __builtin_unreachable();
+; }
+
+define i32 @foo1_without_default(i32 %a) {
+; CHECK-LABEL: @foo1_without_default
+; CHECK: icmp eq i32
+; CHECK-NEXT: %switch.select = select i1 %switch.selectcmp, i32 10, i32 2
+; CHECK-NOT: %switch.selectcmp1
+entry:
+  switch i32 %a, label %sw.epilog [
+    i32 10, label %sw.bb
+    i32 20, label %sw.bb1
+  ]
+
+sw.bb:
+  br label %return
+
+sw.bb1:
+  br label %return
+
+sw.epilog:
+  unreachable
+
+return:
+  %retval.0 = phi i32 [ 2, %sw.bb1 ], [ 10, %sw.bb ]
+  ret i32 %retval.0
+}