Expand SimplifyCFG to convert certain simple switches to selects

[kariddi]

Summary

This proposed patch adds some code to SimplifySwitch in SimplifyCFG in order to convert some switch constructs to selects when that is possible.

The idea here is to avoid unnecessary control-flow when the switch is simple enough to be converted into a simple one or two-way select with only a comparison. In order for that to be feasible the switch must be a the kind of "producing a value" like for example

switch (a) {

case 5:
  return 10;
case 9:
  return 11;
default:
  return 12;

}

The method uses three methods to try and transform the switch into a select.

First it checks if the number of cases is just 2 and in that case it just generates a simple comparison to check if the value is the one from the first case or from the second.
If this approach fails it then tries to see if case label values are dividable in two ordered groups and tries to emit a select that checks on a pivot value to see from which group we should select the value from.
If this is not possible it tries a third approach which is trying to identify some bits that are always one in one of the groups to select from and that are always zero in the other and use a bit mask to determine in which category the value falls into.

Reducing control flow in this way for these cases should be profitable for all hardware.
Please, comment on what you think about this.

[echristo]

Drive by miscellaneous style comment...

lib/Transforms/Utils/SimplifyCFG.cpp

3762

... this function is very very long. Any way to break it up a bit?

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3762

Yeah, maybe it is possible to break up the various stages (case 1, case 2 and case 3) in helper functions to shorten it a little bit.

[kariddi]

Modified to move some work into helper functions to improve readability

[echristo]

Looks pretty awesome, thanks for splitting it up.

Any performance numbers?

[kariddi]

Updated to apply without hunks after recent commits

[kariddi]

I made some micro benchmarks and the results are promising if the backend does a good job with select vs lookup table or branches + phi nodes.

For example on ARM this function:

int foo3_without_def(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;
}

}

was translated as:

_foo3_without_def_norm:
movw r1, :lower16:(l_switch.table1-(LPC1_0+8))
and r0, r0, #6
movt r1, :upper16:(l_switch.table1-(LPC1_0+8))
LPC1_0:
add r1, pc, r1
ldr r0, [r1, r0, lsl #2]
bx lr

while after the optimization is:

_foo3_without_def:
ubfx r0, r0, #1, #1
add r0, r0, #1
bx lr

Which is much faster.

On X86 I got mixed results with the select version being basically the same performance. After looking at the resulting code I noticed some strange code from the X86 backend.
The same function above without the optimization is translated as:
_foo3_without_def_norm:
andl $6, %edi
leaq l_switch.table1(%rip), %rax
movl (%rax,%rdi,4), %eax
retq

with the optimization:

_foo3_without_def:
pushq %rbp
movq %rsp, %rbp
shrl %edi
andl $1, %edi
leal 1(%rdi), %eax
popq %rbp
retq

As you can see the backend emits some (I think) unnecessary pushing/moving and popping of RBP, which takes away the advantage of the select with respect to the lookup table.
I don't really know why the X86 backend emits those to be honest, but I'm pretty sure they aren't needed and that everything could be done with 3 instruction. In this way this code could be made as fast as the ARM version with respect to the lookup table code.

[kariddi]

Whoops, I didn't notice that on X86 I had frame-pointers enabled by default (default without -fomit-frame-pointer) and that is the cause of those pushing and popping.

After omitting frame pointers I get this output:

_foo3_without_def:
shrl %edi
andl $1, %edi
leal 1(%rdi), %eax
retq

with the one without optimization being:

_foo3_without_def:
andl $6, %edi
leaq l_switch.table1(%rip), %rax
movl (%rax,%rdi,4), %eax
retq

Which is short in instruction count, thanks to X86 assembly being quite expressive, but accesses memory.

In my micro benchmark this is the result of the optimized version:

marcellos-mbp:test_files Kariddi$ time ./test2

real 0m3.880s
user 0m3.878s
sys 0m0.002s

vs unoptimized:

marcellos-mbp:test_files Kariddi$ time ./test2_norm

real 0m4.675s
user 0m4.670s
sys 0m0.003s

for this switch:

int foo3_without_def(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;
}

}

[reames]

I really like the overall direction of this patch, but it could use a bit of cleanup for readability.

You might also be able to generalize some of the transform:

• single unique value + default
• default probably dead without transform

lib/Transforms/Utils/SimplifyCFG.cpp

3686

range loop?

3700

split the two early exit cases? might improve readability, particularly if the CaseSuccessor != CommonDest check is above BI.

3713

You might restructure this to put ResultFound closer to it's use and separate the two if/else clauses.

3725

It looks like you might end up with PHI unset if you had a switch with only a default case. Could such a switch reach here?

3766

It looks like this code is actually handling two cases + default. Update the comment?

Also, is it always profitable to replace one switch with two selects? I would guess not, but will defer to actual measurement.

3814

Could you add examples to your function comments? It would make them a bit more obvious.

3902

Since you're handling defaults, wouldn't it also make sense to handle one unique result and a default? i.e.
switch(i) {
case 4,5,6: return 5;
default: return 0;
}

3955

It seems like proving the switch default is dead is a useful optimization even if we can make no other changes. Should this be separated and generalized?

3964

The general convention used is an early return when a change is made, not a signal value (nullptr here) when a change isn't made. In this particular example, I believe using that pattern would make the code much easier to follow.

3974

Everything from here on could easily be a helper function.

[kariddi]

Hi Philip, thanks for the comments!

I have a couple of questions about some of them to being better able to address them.

What you mean exactly with : "default probably dead without transform" ?

The other question is inlined.

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3766

On X86 from the measurements I did with a very simple micro benchmark it seems profitable.

This is the code of the benchmark:

int foo1_with_def(int a) {

switch(a) {
  case 10:
    return 10;
  case 20:
    return 2;
}
return 4;

}

int main() {

int a = 0;
int ret = 0;
for (; a < 2000000000; ++a) {
  ret |= foo1_with_def(a);
}

return ret;

}

And the generated code for the functions containing the switch is (+ performance results):

LLVM without patch:
_foo1_with_def:
movl $10, %eax
cmpl $10, %edi
je LBB0_4
cmpl $20, %edi
jne LBB0_3
movl $2, %eax
retq
LBB0_3:
movl $4, %eax
LBB0_4:
retq

real 0m5.522s
user 0m5.519s
sys 0m0.002s

LLVM with patch:

_foo1_with_def:
cmpl $10, %edi
movl $4, %ecx
cmovel %edi, %ecx
cmpl $20, %edi
movl $2, %eax
cmovnel %ecx, %eax
retq

real 0m3.233s
user 0m3.230s
sys 0m0.002s

I don't have any real world application though to back this up (it looks like a good result though).

In addition to that X86 is quite a control flow "friendly" architecture with respect to many others and if the results are positive on X86 I would expect that on some more custom architectures where control flow is more expensive this optimization might actually be even more effective.

3955

Do you mean making it a generic independent static function in SimplifyCFG.cpp ?

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3686

I checked here. I don't think it is possible with SwitchInst to iterate over the cases of the switch with range loop, because there are no begin()/end() methods and range loops only work over classes that expose those.

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3700

The conditions for the exit cases here are &&ed and not ||ed . So the exit case here is actually one (when both the conditions are verified). What exactly do you mean here?

3814

Very good point, I'll do that definitely in the next revision

3902

This is a good idea. I need to check if that is profitable in performance though (needs two comparisons to check if the value falls in the range). If it seems profitable I'll add it.

3964

I see, I will make the change, thanks.

3974

This is quite needed in order to make the change you requested in the comment above

[kariddi]

Sorry for having added the comments in different moments, but the answers came out at different moments in times :P

lib/Transforms/Utils/SimplifyCFG.cpp

3725

I tried to catch a case here where that happens, but I couldn't reproduce this case by trying to compile something like this:

define i32 @foo(i32 %a) #0 {
entry:

switch i32 %a, label %sw.default [
]

sw.default: ; preds = %entry

ret i32 10

}

with opt -simplifycfg

Anyway, if that is the case the test:

if (UniqueResults.size() != 2)
  return false;

in SwitchToSelect() should fail, because a PHI must be set if at least one Result is found, which would prevent the assertion on the next line to trigger.

I think bailing out in a case like that would be ok, because I don't think this is the right place where to handle a case like this one.

[kariddi]

lib/Transforms/Utils/SimplifyCFG.cpp

3902

I actually checked and seems like this specific case is already handled by TurnSwitchRangeIntoICmp()

[kariddi]

New revision.

In this revision I addressed most of the comments from Philip that I could, in particular:

• I restructured ResultFound to be closer to it's use.
• Updated the comment about the two cases case.
• Added examples on the various cases helper functions
• Handled directly the case "single range + default" i.e. switch (a) { case 4,5,6: return 20; default: return 10; } before this case was handled by TurnSwitchRangeIntoICmp + SimplifyCondBranch. Now it is handled directly. I updated the patterns of some tests for this , because the name of the generated virtual registers was different, but the generated code is the same.
• Switched to an early return approach in the function
• Moved the Switch removal + PHI fixup into an helper function

In addition to that I:

• Changed the order of execution of TurnSwitchRangeIntoICmp to run after SwitchToSelect , so that this function can handle directly some cases handled by TurnSwitchRangeIntoICmp + SimplifyCondBranch. Changing this order shouldn't have any other side effect.
• Modified the function to make optimization that have only "one value + default value" (like the "single range + default" above) possible to implement, so in the future if someone has an idea to add here that matches this pattern it is possible to add.

[reames]

Answering inline questions. Will glance at the revised version in separate review.

lib/Transforms/Utils/SimplifyCFG.cpp

3686

Maybe something we should add. Not asking that of you now.

3700

I had misread the code when scanning quickly. Please ignore previous comment.

3725

Your answer makes sense. I worry a bit that we're developing a series of small optimization tests where a single more general one would be better, but that's a concern for later.

3766

Thanks for the data. I'm not entirely sure about how this will play out on other architectures (i.e. ones without a conditional move). I am not requesting you hold the patch on this mind you. Just be prepared in case someone objects based on non-x86 perf data. :)

3814

Thanks for doing this. It helped a lot.

3902

Thanks for following up. This fits in with my "series of small optimizations" comment above, but not something which needs to be addressed now.

3955

For this change, no action needed.

I was essentially wondering whether the optimization "prove default case is dead based AnalyzeSwitchCases" would apply to switches with more than two groups or for which we can't completely fold to selects. This might be worth looking at as a follow up change.

[reames]

I'm running out of useful comments. :) I don't have commit rights, so I can't give you an official LGTM, but what I see looks reasonable.

Side note: this patch is getting really long. To make review easier, a set of smaller changes would be a good idea. Particularly since you have several independent changes which build on each other here.

Also, since I'm not sure it was clear before, my wondering about other possible optimizations are _not_ things you need to fix before submission. They might be TODOs to add or suggestions for future work, but unless they lead you to what you consider as a bug, you do not need to purse them. I worry I may have led you slightly astray on that.

lib/Transforms/Utils/SimplifyCFG.cpp

184

This looks like an entirely new optimization rather than moving code around? If so, do you mind separating this as a separate patch? Most of the rest seems fairly solid, this needs a bit more work.

I had trouble tracing through the logic and assumptions here. Example? (Feel free to post a different review.)

236

To make your example clearer, you might vertically separate the two ands. I had missed the &= usage on the left in first read through.

[kariddi]

Hi, sorry for the late answer.

Thanks for all your precious feedback Philip.

I think you are right, the patch grew quite a bit and it became quite difficult to audit.

I think I'll split it up into smaller pieces and propose them independently.

lib/Transforms/Utils/SimplifyCFG.cpp

   return SI->getNumCases() * 10 >= TableSize * 4;
 }
 
+// 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,
+    SmallDenseMap<Constant *, SmallVector<ConstantInt *, 4>> &UniqueResults,
+    Constant *&DefaultResult) {
+  for (auto I = SI->case_begin(), E = SI->case_end(); I != E; ++I) {
+    ConstantInt *CaseVal = I.getCaseValue();
+    BasicBlock *CaseSuccessor = I.getCaseSuccessor();
+
+    // Resulting value at phi nodes for this case value.
+    typedef SmallVector<std::pair<PHINode *, Constant *>, 4> ResultsTy;
+    ResultsTy Results;
+    if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results,
+                        DL))
+      return false;
+
+    BranchInst *BI = dyn_cast<BranchInst>(CaseSuccessor->getTerminator());
+    // Support only the case where the switch branches directly or through an
+    // intermediate unconditional block to the common destination.
+    if (CaseSuccessor != CommonDest &&
+        !(BI && BI->isUnconditional() && BI->getSuccessor(0) == CommonDest))
+      return false;
+    // Only one value per case is permitted
+    if (Results.size() > 1)
+      return false;
+    auto &Result = *Results.begin();
+    auto ResultFound = UniqueResults.find(Result.second);
+    if (ResultFound == UniqueResults.end()) {
+      UniqueResults[Result.second].push_back(CaseVal);
+    } else {
+      // Avoid querying the map again if we already found the result.
+      ResultFound->second.push_back(CaseVal);
+    }
+
+    // Append the result from this case to the list and find the PHI
+    if (PHI == nullptr)
+      PHI = Result.first;
+    else if (PHI != Result.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);
+  // No default case makes us assume that default is not possible.
+  DefaultResult =
+      DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr;
+  BranchInst *BI = dyn_cast<BranchInst>(DefaultDest->getTerminator());
+  if (DefaultDest != CommonDest &&
+      !(BI && BI->isUnconditional() && BI->getSuccessor(0) == CommonDest))
+    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.
+static void AnalyzeSwitchCases(const SmallVectorImpl<ConstantInt *> *Cases,
+                               const APInt &KnownZeroesCond,
+                               const APInt &KnownOnesCond, APInt &KnownZeroes,
+                               APInt &KnownOnes, ConstantInt *&MinCase,
+                               ConstantInt *&MaxCase, unsigned &PossibleHits) {
+  if (Cases == nullptr)
+    return;
+  // 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() & KnownZeroesCond) == KnownZeroesCond) &&
+        ((Case->getValue() & KnownOnesCond) == KnownOnesCond);
+
+    if (CaseMatchesCondPattern)
+      ++PossibleHits;
+
+    KnownZeroes &= ~(Case->getValue());
+    KnownOnes &= Case->getValue();
+    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, 1
+//     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 SmallVectorImpl<ConstantInt *> *FirstGroupCasesPtr,
+                     const SmallVectorImpl<ConstantInt *> *SecondGroupCasesPtr,
+                     Constant *FirstGroupResult, Constant *SecondGroupResult,
+                     Constant *DefaultResult, Value *Condition,
+                     const APInt &KnownZeroCond, const APInt &KnownOneCond,
+                     unsigned Bits, IRBuilder<> &Builder) {
+  if (FirstGroupCasesPtr == nullptr || SecondGroupCasesPtr == nullptr)
+    return nullptr;
+  auto &FirstGroupCases = *FirstGroupCasesPtr;
+  auto &SecondGroupCases = *SecondGroupCasesPtr;
+  const unsigned CondStuckBits =
+      (KnownZeroCond | KnownOneCond).countPopulation();
+  // If we are selecting between only two cases transform into a simple
+  // select or a two-way select if default is possible.
+  if (FirstGroupCases.size() == 1 && SecondGroupCases.size() == 1) {
+    ConstantInt *const FirstCase = FirstGroupCases[0];
+    ConstantInt *const SecondCase = SecondGroupCases[0];
+    // In this case we have only one case per result. From the analysis of
+    // the condition value done above we can determine if the condition value
+    // can assume the value of the case or if the case is dead.
+    const unsigned FirstCanHit =
+        ((~FirstCase->getValue() & KnownZeroCond) == KnownZeroCond) &&
+        ((FirstCase->getValue() & KnownOneCond) == KnownOneCond);
+    const unsigned SecondCanHit =
+        ((~SecondCase->getValue() & KnownZeroCond) == KnownZeroCond) &&
+        ((SecondCase->getValue() & KnownOneCond) == KnownOneCond);
+
+    // 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 << (Bits - CondStuckBits)) - (FirstCanHit + SecondCanHit) != 0);
+    DefaultCanTrigger &= (DefaultResult != nullptr);
+    Value *SelectValue = SecondGroupResult;
+    if (DefaultCanTrigger) {
+      Value *const ValueCompare =
+          Builder.CreateICmpEQ(Condition, SecondCase, "switch.selectcmp");
+      SelectValue = Builder.CreateSelect(ValueCompare, SecondGroupResult,
+                                         DefaultResult, "switch.select");
+    }
+    Value *const ValueCompare =
+        Builder.CreateICmpEQ(Condition, FirstCase, "switch.selectcmp");
+    return Builder.CreateSelect(ValueCompare, FirstGroupResult, 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(Constant *FirstGroupResult, Constant *SecondGroupResult,
+                   Value *Condition, Constant *DefaultResult, unsigned NumCases,
+                   bool DefaultCanTrigger, ConstantInt *MinCaseFirst,
+                   ConstantInt *MinCaseSecond, ConstantInt *MaxCaseFirst,
+                   ConstantInt *MaxCaseSecond, IRBuilder<> &Builder) {
+  if (FirstGroupResult == nullptr)
+    return nullptr;
+
+  const bool RangeIsContinuous =
+      (MaxCaseFirst->getValue() - MinCaseFirst->getValue()) + 1 == NumCases;
+  if (RangeIsContinuous && SecondGroupResult == nullptr &&
+      DefaultResult != nullptr) {
+    Constant *Offset = ConstantExpr::getNeg(MinCaseFirst);
+    Constant *NCases = ConstantInt::get(Offset->getType(), NumCases);
+
+    Value *Sub = Condition;
+    if (!Offset->isNullValue())
+      Sub = Builder.CreateAdd(Sub, Offset, "switch.off");
+    Value *ValueCompare;
+    // If NumCases overflowed, then all possible values jump to the successor.
+    if (NCases->isNullValue() && NumCases != 0)
+      ValueCompare = ConstantInt::getTrue(FirstGroupResult->getContext());
+    else
+      ValueCompare = Builder.CreateICmpULT(Sub, NCases, "switch.cmp");
+    return Builder.CreateSelect(ValueCompare, FirstGroupResult, DefaultResult,
+                                "switch.rangeselect");
+  }
+
+  if (SecondGroupResult == nullptr)
+    return nullptr;
+  const bool FirstIsBigger =
+      MaxCaseSecond->getValue().slt(MinCaseFirst->getValue());
+  const bool SecondIsBigger =
+      MaxCaseFirst->getValue().slt(MinCaseSecond->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 ? FirstGroupResult : SecondGroupResult;
+    Value *const SelectRHS =
+        SecondIsBigger ? SecondGroupResult : FirstGroupResult;
+    Value *const ValueCompare =
+        Builder.CreateICmpSLE(Condition, Pivot, "switch.rangesub");
+    return Builder.CreateSelect(ValueCompare, SelectLHS, SelectRHS,
+                                "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(
+    Constant *FirstGroupResult, Constant *SecondGroupResult, Value *Condition,
+    bool DefaultCanTrigger, const APInt &KnownZeroFirst, APInt KnownOneFirst,
+    const APInt &KnownZeroSecond, APInt KnownOneSecond, IRBuilder<> &Builder) {
+
+  if (FirstGroupResult == nullptr || SecondGroupResult == nullptr)
+    return nullptr;
+  // If there is no default case and we have unambiguous
+  // patterns do it with one select and one compare.
+  if (!DefaultCanTrigger && ((KnownOneFirst & KnownZeroSecond) != 0 ||
+                             (KnownOneSecond & KnownZeroFirst) != 0)) {
+    Value *ValueCompare = nullptr;
+    // KnownOneFirst and KnownOneSecond after this assignment
+    // are bitvectors containing the bits that are always one
+    // in a group of case labels and always zero in the other
+    KnownOneFirst &= KnownZeroSecond;
+    KnownOneSecond &= KnownZeroFirst;
+    // The comparison checks for ones that are always present in
+    // one of the groups that are always zero in the other.
+    if (KnownOneFirst != 0) {
+      ConstantInt *const MaskValue =
+          ConstantInt::get(Condition->getContext(), KnownOneFirst);
+      ValueCompare =
+          Builder.CreateAnd(Condition, MaskValue, "switch.selectmask");
+      ValueCompare = Builder.CreateICmpNE(
+          ValueCompare, ConstantInt::get(Condition->getType(), 0),
+          "switch.selectcmp");
+    } else if (KnownOneSecond != 0) {
+      ConstantInt *const MaskValue =
+          ConstantInt::get(Condition->getContext(), KnownOneSecond);
+      ValueCompare =
+          Builder.CreateAnd(Condition, MaskValue, "switch.selectmask");
+      ValueCompare = Builder.CreateICmpEQ(
+          ValueCompare, ConstantInt::get(Condition->getType(), 0),
+          "switch.selectcmp");
+    }
+    return Builder.CreateSelect(ValueCompare, FirstGroupResult,
+                                SecondGroupResult, "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,
+                                              BasicBlock *Destination,
+                                              IRBuilder<> &Builder) {
+  PHI->addIncoming(SelectValue, SI->getParent());
+
+  Builder.CreateBr(Destination);
+
+  // Remove the switch.
+  for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) {
+    BasicBlock *Succ = SI->getSuccessor(i);
+
+    if (Succ == SI->getDefaultDest())
+      continue;
+    Succ->removePredecessor(SI->getParent());
+  }
+  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) {
+  Value *const Cond = SI->getCondition();
+  PHINode *PHI = nullptr;
+  BasicBlock *CommonDest = nullptr;
+  Type *ResultType;
+  Constant *DefaultResult;
+
+  SmallDenseMap<Constant *, SmallVector<ConstantInt *, 4>> UniqueResults;
+  // Collect all the cases that will deliver the same value from the switch.
+  if (!InitializeUniqueCases(SI, DL, PHI, CommonDest, UniqueResults,
+                             DefaultResult))
+    return false;
+  const unsigned NumOfResults = UniqueResults.size();
+  // Selects choose between maximum two values.
+  if (NumOfResults > 2)
+    return false;
+  assert(PHI != nullptr && "PHI for value select not found");
+  ResultType = PHI->getType();
+
+  const unsigned Bits = Cond->getType()->getIntegerBitWidth();
+
+  const SmallVectorImpl<ConstantInt *> *FirstGroupCases = nullptr;
+  const SmallVectorImpl<ConstantInt *> *SecondGroupCases = nullptr;
+  Constant *FirstGroupResult = nullptr;
+  Constant *SecondGroupResult = nullptr;
+  {
+    auto ResultIt = UniqueResults.begin();
+    if (NumOfResults >= 1) {
+      FirstGroupCases = &ResultIt->second;
+      FirstGroupResult = ResultIt->first;
+    }
+    if (NumOfResults == 2) {
+      ++ResultIt;
+      SecondGroupCases = &ResultIt->second;
+      SecondGroupResult = ResultIt->first;
+    }
+  }
+  // SmallDenseMap is unordered. Enforce a stable ordering here.
+  if (SecondGroupCases != nullptr &&
+      (isa<UndefValue>(SecondGroupResult) ||
+       (!isa<UndefValue>(FirstGroupResult) &&
+        FirstGroupResult->getUniqueInteger().sgt(
+            SecondGroupResult->getUniqueInteger())))) {
+    std::swap(FirstGroupCases, SecondGroupCases);
+    std::swap(FirstGroupResult, SecondGroupResult);
+  }
+
+  APInt KnownZeroCond(Bits, 0), KnownOneCond(Bits, 0);
+  computeKnownBits(Cond, KnownZeroCond, KnownOneCond);
+  // Number of bits that are fixed in the switch condition value.
+  const unsigned CondStuckBits =
+      (KnownZeroCond | KnownOneCond).countPopulation();
+  Value *SelectValue = nullptr;
+
+  Builder.SetInsertPoint(SI);
+  SelectValue = ConvertTwoCaseSwitch(
+      FirstGroupCases, SecondGroupCases, FirstGroupResult, SecondGroupResult,
+      DefaultResult, Cond, KnownZeroCond, KnownOneCond, Bits, Builder);
+  if (SelectValue != nullptr) {
+    RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, CommonDest,
+                                      Builder);
+    return true;
+  }
+
+  // The switch has more than only two cases. Check to see if we can
+  // still transform it into a select
+  bool DefaultCanTrigger;
+  APInt KnownZeroFirst(Bits, ~(0ULL)), KnownOneFirst(Bits, ~(0ULL)),
+      KnownZeroSecond(Bits, ~(0ULL)), KnownOneSecond(Bits, ~(0ULL));
+  unsigned FirstPossibleHits = 0, SecondPossibleHits = 0;
+  ConstantInt *MinCaseFirst = FirstGroupCases ? (*FirstGroupCases)[0] : nullptr,
+              *MinCaseSecond =
+                  SecondGroupCases ? (*SecondGroupCases)[0] : nullptr,
+              *MaxCaseFirst = MinCaseFirst, *MaxCaseSecond = MinCaseSecond;
+  AnalyzeSwitchCases(FirstGroupCases, KnownZeroCond, KnownOneCond,
+                     KnownZeroFirst, KnownOneFirst, MinCaseFirst, MaxCaseFirst,
+                     FirstPossibleHits);
+  AnalyzeSwitchCases(SecondGroupCases, KnownZeroCond, KnownOneCond,
+                     KnownZeroSecond, KnownOneSecond, MinCaseSecond,
+                     MaxCaseSecond, SecondPossibleHits);
+  // 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
+  DefaultCanTrigger = (((1 << (Bits - CondStuckBits)) -
+                        (FirstPossibleHits + SecondPossibleHits)) != 0);
+  DefaultCanTrigger &= DefaultResult != nullptr;
+
+  SelectValue = ConvertRangeSwitch(
+      FirstGroupResult, SecondGroupResult, Cond, DefaultResult,
+      SI->getNumCases(), DefaultCanTrigger, MinCaseFirst, MinCaseSecond,
+      MaxCaseFirst, MaxCaseSecond, Builder);
+
+  if (SelectValue != nullptr) {
+    RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, CommonDest,
+                                      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(
+      FirstGroupResult, SecondGroupResult, Cond, DefaultCanTrigger,
+      KnownZeroFirst, KnownOneFirst, KnownZeroSecond, KnownOneSecond, Builder);
+
+  if (SelectValue != nullptr) {
+    RemoveSwitchAfterSelectConversion(SI, PHI, SelectValue, CommonDest,
+                                      Builder);
+    return true;
+  }
+
+  // The switch couldn't be converted into a select.
+  return false;
+}
+
 /// SwitchToLookupTable - If the switch is only used to initialize one or more
 /// phi nodes in a common successor block with different constant values,
 /// replace the switch with lookup tables.

         return SimplifyCFG(BB, TTI, DL) | true;
   }
 
-  // Try to transform the switch into an icmp and a branch.
-  if (TurnSwitchRangeIntoICmp(SI, Builder))
-    return SimplifyCFG(BB, TTI, DL) | true;
-
   // Remove unreachable cases.
   if (EliminateDeadSwitchCases(SI))
     return SimplifyCFG(BB, TTI, DL) | true;

   if (ForwardSwitchConditionToPHI(SI))
     return SimplifyCFG(BB, TTI, DL) | true;
 
+  if (SwitchToSelect(SI, Builder, DL))
+    return SimplifyCFG(BB, TTI, DL) | true;
+
+  // Try to transform the switch into an icmp and a branch.
+  if (TurnSwitchRangeIntoICmp(SI, Builder))
+    return SimplifyCFG(BB, TTI, DL) | true;
+
   if (SwitchToLookupTable(SI, Builder, TTI, DL))
     return SimplifyCFG(BB, TTI, DL) | true;
 

test/Transforms/SimplifyCFG/2014-06-19-SwitchToSelectBitPattern.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+; int foo3_with_def(int a) {
+;   switch (a) {
+;     case 0:
+;       return 1;
+;     case 1:
+;       return 2;
+;     case 2:
+;       return 1;
+;     case 3:
+;       return 2;
+;     default:
+;       return 10;
+;   }
+; }
+;
+; int foo3_without_def(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;
+;   }
+; }
+
+define i32 @foo3_with_def(i32 %a) #0 {
+; CHECK-LABEL: @foo3_with_def
+; 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
+}
+
+define i32 @foo3_without_def(i32 %a) #0 {
+; CHECK-LABEL: @foo3_without_def
+; CHECK: select
+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
+}

test/Transforms/SimplifyCFG/2014-06-19-SwitchToSelectRange.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+define i32 @foo2_with_def(i32 %a) #0 {
+; CHECK-LABEL: @foo2_with_def
+; 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
+}
+
+define i32 @foo2_without_def(i32 %a) #0 {
+; CHECK-LABEL: @foo2_without_def
+; CHECK: select
+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/2014-06-19-SwitchToSelectTwoCase.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+; int foo1_with_def(int a) {
+;   switch(a) {
+;     case 10:
+;       return 10;
+;     case 20:
+;       return 2;
+;   }
+;   return 4;
+; }
+;
+; int foo1_without_def(int a) {
+;   switch(a) {
+;     case 10:
+;       return 10;
+;     case 20:
+;       return 2;
+;   }
+;   __builtin_unreachable();
+; }
+
+define i32 @foo1_with_def(i32 %a) #0 {
+; CHECK-LABEL: @foo1_with_def
+; CHECK: icmp eq i32
+; CHECK-NEXT: select i1
+; CHECK-NEXT: icmp eq i32
+; CHECK-NEXT: select i1
+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
+}
+
+define i32 @foo1_without_def(i32 %a) #0 {
+; CHECK-LABEL: @foo1_without_def
+; CHECK: icmp eq i32
+; CHECK-NEXT: select i1
+; 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
+}

test/Transforms/SimplifyCFG/UnreachableEliminate.ll

 
 ; PR9450
 define i32 @test4(i32 %v) {
+; CHECK-LABEL: @test4(
 ; CHECK: entry:
-; CHECK-NEXT:  switch i32 %v, label %T [
-; CHECK-NEXT:    i32 3, label %V
-; CHECK-NEXT:    i32 2, label %U
-; CHECK-NEXT:  ]
+; CHECK: %switch.selectcmp = icmp eq i32 %v, 3
+; CHECK-NEXT: %switch.select = select i1 %switch.selectcmp, i32 7, i32 2
+; CHECK-NEXT: %switch.selectcmp1 = icmp eq i32 %v, 2
+; CHECK-NEXT: %switch.select2 = select i1 %switch.selectcmp1, i32 1, i32 %switch.select
+; CHECK-NEXT: ret i32 %switch.select2
 
 entry:
         br label %SWITCH

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-icmp.ll

  ret i1 %0
 
 ; CHECK-LABEL: @test1(
-; CHECK: %x.off = add i32 %x, -1
-; CHECK: %switch = icmp ult i32 %x.off, 3
+; CHECK: %switch.off = add i32 %x, -1
+; CHECK: %switch.cmp = icmp ult i32 %switch.off, 3
 }
 
 define zeroext i1 @test2(i32 %x) nounwind readnone ssp noredzone {

  ret i1 %0
 
 ; CHECK-LABEL: @test2(
-; CHECK: %switch = icmp ult i32 %x, 2
+; CHECK: %switch.cmp = icmp ult i32 %x, 2
 }
 
 define i32 @test3(i1 %flag) {

test/Transforms/SimplifyCFG/switch_create.ll

         ret i1 %UnifiedRetVal
 
 ; CHECK-LABEL: @test6(
-; CHECK: %tmp.2.i.off = add i32 %tmp.2.i, -14
-; CHECK: %switch = icmp ult i32 %tmp.2.i.off, 6
+; CHECK: %switch.off = add i32 %tmp.2.i, -14
+; CHECK: %switch.cmp = icmp ult i32 %switch.off, 6
 }
 
 define void @test7(i8 zeroext %c, i32 %x) nounwind ssp noredzone {

 define zeroext i1 @test16(i32 %x) nounwind {
 entry:
 ; CHECK-LABEL: @test16(
-; CHECK: %x.off = add i32 %x, -1
-; CHECK: %switch = icmp ult i32 %x.off, 3
+; CHECK: %switch.off = add i32 %x, -1
+; CHECK: %switch.cmp = icmp ult i32 %switch.off, 3
   %cmp.i = icmp eq i32 %x, 1
   br i1 %cmp.i, label %lor.end, label %lor.lhs.false