[SimplifyCFG] Try to fold switch with single result value and power-of-2 cases to mask+select

[bcl5980]

Summary

When switch with 2^n cases go to one result, check if the 2^n cases can be covered by n bit masks.
If yes we can use "and condition, ~mask" to simplify the switch

case 0 2 4 6 -> and condition, -7
https://alive2.llvm.org/ce/z/jjH_0N

case 0 2 8 10 -> and condition, -11
https://alive2.llvm.org/ce/z/K7E-2V

case 2 4 8 12 -> and (sub condition, 2), -11
https://alive2.llvm.org/ce/z/CrxbYg

Fix one case of https://github.com/llvm/llvm-project/issues/39957

[bcl5980]

I have no too much confidence about this change, so this should be a scatch without detail comments and the magic number is also a rough value.
So can someone help to give me suggestion it is worth or not?

[bcl5980]

https://godbolt.org/z/zPhnrexca
This change should get result similar to MSVC except ztfos4

[bcl5980]

fix the bitmask init value wrong
remove the MaxCasesPerResult limitation

[bcl5980]

update the correct mask0 case

[RKSimon]

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

70

(style) please can you replace the mask# naming sequence with test names that are more descriptive?

[bcl5980]

update test name

[bcl5980]

Ping.
Any suggestions for the patch?

[bcl5980]

@RKSimon Any suggestions for the patch?

[bcl5980]

Ping.

[spatel]

I have not stepped through the logic in "ConvertTwoCaseSwitch" in detail, but this seems to be on the right track.
We need to update function names and code comments for the more general transform now, so we should clean this set of functions up as much as possible before this patch. See if this makes sense:
D123614

[bcl5980]

In D122485#3445834, @spatel wrote:

I have not stepped through the logic in "ConvertTwoCaseSwitch" in detail, but this seems to be on the right track.
We need to update function names and code comments for the more general transform now, so we should clean this set of functions up as much as possible before this patch. See if this makes sense:
D123614

OK, I will rebase after D123614 land.

[bcl5980]

rebase code

[bcl5980]

Update comments

[bcl5980]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5646

@spatel I'm a little worry about here. I remove the early out this version. It will cause compile time increase if we have some very large switch with many cases to the same result but not the pattern we can fold. But I have no detail data to show how much extra compile this change will be involved. Do we have some common compile time tests?
Another way to do is enlarge MaxCasesPerResult. The patch first version adjust MaxCasesPerResult to 16. But 16 is also a magic number. Maybe we can add a config for it.
How about your suggestions?

[spatel]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5646

@nikic has a system that is used to check for compile time changes with benchmarks from the test suite:
https://llvm-compile-time-tracker.com/index.php

So we can run an experiment there.

But I think it is fine to use "16" as a limit for this analysis. You can give it a name and make it a debug option like the many others at the top of this file. For example:

static cl::opt<unsigned> MaxSpeculationDepth(
    "max-speculation-depth", cl::Hidden, cl::init(10),
    cl::desc("Limit maximum recursion depth when calculating costs of "
             "speculatively executed instructions"));

[spatel]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5646

We can reduce this patch by doing that part independently:
D123625

[bcl5980]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5646

Thanks for the help. I will rebase after D123625

[bcl5980]

rebase main

[spatel]

Let's add the baseline tests as an NFC commit now, so it is easier to see the diffs.

The order of the transforms creates an interesting trade-off, so we need a test like this (and probably even more tests):

define i8 @same_value_two_case(i32 %i) {
entry:
  switch i32 %i, label %default [
  i32 -3, label %end
  i32 5, label %end
  ]

default:
  br label %end

end:
  %t0 = phi i8 [ 42, %default ], [ 3, %entry ], [ 3, %entry ]
  ret i8 %t0
}

This patch creates a difference that survives all the way through codegen - instcombine does not recognize the equivalence between the 2 patterns:
https://alive2.llvm.org/ce/z/mqo87Z

It's not clear to me if there is a universal better form (depends on target?) or even which one is better for IR. To avoid those questions, you can re-order the transforms, so we do not have to answer it in this patch (add a TODO comment though).

[bcl5980]

In D122485#3448240, @spatel wrote:

Let's add the baseline tests as an NFC commit now, so it is easier to see the diffs.

The order of the transforms creates an interesting trade-off, so we need a test like this (and probably even more tests):

define i8 @same_value_two_case(i32 %i) {
entry:
  switch i32 %i, label %default [
  i32 -3, label %end
  i32 5, label %end
  ]

default:
  br label %end

end:
  %t0 = phi i8 [ 42, %default ], [ 3, %entry ], [ 3, %entry ]
  ret i8 %t0
}

I'm sorry but what's the difference between this test with switch_to_and0 ? For the negative offset?

[spatel]

In D122485#3448273, @bcl5980 wrote:

In D122485#3448240, @spatel wrote:

Let's add the baseline tests as an NFC commit now, so it is easier to see the diffs.

The order of the transforms creates an interesting trade-off, so we need a test like this (and probably even more tests):

define i8 @same_value_two_case(i32 %i) {
entry:
  switch i32 %i, label %default [
  i32 -3, label %end
  i32 5, label %end
  ]

default:
  br label %end

end:
  %t0 = phi i8 [ 42, %default ], [ 3, %entry ], [ 3, %entry ]
  ret i8 %t0
}

I'm sorry but what's the difference between this test with switch_to_and0 ? For the negative offset?

Ah, you're correct - I did not see that test diff. But we might want to include a test with negative offset, so we have coverage for that too.

[bcl5980]

In D122485#3448283, @spatel wrote:

In D122485#3448273, @bcl5980 wrote:

In D122485#3448240, @spatel wrote:

Let's add the baseline tests as an NFC commit now, so it is easier to see the diffs.

The order of the transforms creates an interesting trade-off, so we need a test like this (and probably even more tests):

define i8 @same_value_two_case(i32 %i) {
entry:
  switch i32 %i, label %default [
  i32 -3, label %end
  i32 5, label %end
  ]

default:
  br label %end

end:
  %t0 = phi i8 [ 42, %default ], [ 3, %entry ], [ 3, %entry ]
  ret i8 %t0
}

I'm sorry but what's the difference between this test with switch_to_and0 ? For the negative offset?

Ah, you're correct - I did not see that test diff. But we might want to include a test with negative offset, so we have coverage for that too.

@spatel I feel so sorry that I check in the baseline test here rGe2d77a160c with a wrong issue number(show be #39957 but I write #54649).
Can I amend the commit message now?

[bcl5980]

rebase main

[spatel]

In D122485#3448422, @bcl5980 wrote:

@spatel I feel so sorry that I check in the baseline test here rGe2d77a160c with a wrong issue number(show be #39957 but I write #54649).
Can I amend the commit message now?

I do not know if you can amend a commit message after a push (but my git knowledge is not very good).

I don't think it is a big problem, but you could revert and recommit.

Alternatively, you can post a correction on the Phab review thread:
https://reviews.llvm.org/rGe2d77a160c5b8141eca3db1fca6dafd97e78288d
or on github directly?
https://github.com/llvm/llvm-project/commit/e2d77a160c5b8141eca3db1fca6dafd97e78288d

[bcl5980]

In D122485#3448240, @spatel wrote:

Let's add the baseline tests as an NFC commit now, so it is easier to see the diffs.

The order of the transforms creates an interesting trade-off, so we need a test like this (and probably even more tests):

define i8 @same_value_two_case(i32 %i) {
entry:
  switch i32 %i, label %default [
  i32 -3, label %end
  i32 5, label %end
  ]

default:
  br label %end

end:
  %t0 = phi i8 [ 42, %default ], [ 3, %entry ], [ 3, %entry ]
  ret i8 %t0
}

This patch creates a difference that survives all the way through codegen - instcombine does not recognize the equivalence between the 2 patterns:
https://alive2.llvm.org/ce/z/mqo87Z

It's not clear to me if there is a universal better form (depends on target?) or even which one is better for IR. To avoid those questions, you can re-order the transforms, so we do not have to answer it in this patch (add a TODO comment though).

Try two patterns on current backend, this patch's implementation generate better asm on x86 and aarch64: https://godbolt.org/z/nsoWa7Kqr

[spatel]

In D122485#3448597, @bcl5980 wrote:

Try two patterns on current backend, this patch's implementation generate better asm on x86 and aarch64: https://godbolt.org/z/nsoWa7Kqr

Thanks for checking that. I suspect that a target that has condition-logic instructions (like PowerPC) might be better off with the icmp pattern for some examples, but I agree that we can default to the 'and' pattern here. It is shorter IR for the case with no case minimum offset.
I added some more tests and tried to clean up the existing code a bit more. Please rebase and address minor issues. Then I think this patch will be good to go.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5683–5686

I think it would be better to put these examples closer to the code that does the transform.
I moved the existing example comment with:
0ef46dc0f9f3

5687

Remove the TODO - if we are going to use the new code on the 2-case pattern, then it is really a TODO for instcombine and/or codegen to alter it if needed.

5692

Don't move this comment.

5712

I added:

ArrayRef<ConstantInt *> CaseValues = ResultVector[0].second;

to make this more readable. You can use that in the new code.

5716

Use complete sentence/punctuation for code comments:

// Find minimal value.

5722

Add period at end of sentence.

5727–5728

Add period at end of sentence.

[spatel]

Also, I'm not sure what "mutil" means in the patch title. Could this be "Try to fold switch with single result value and power-of-2 cases to mask+select" ?

[bcl5980]

rebase and update comments

[spatel]

LGTM - I made a few more minor comments.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

5713–5715

The bit numbering is not clear to me. "0,4" clears bit 2?
It might help to show the mask as a bit value (for example -5 is "0b1..1011").
Maybe better to spell out the comparison too:
"Cond & 0b1..1011 == 0 ? result : default"

5718

Move this variable declaration/initialization to just above the loop where it is filled in.

5726–5728

Remove unnecessary braces around 1-line loop - { }.

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

68–223

It is independent of this patch, but we should put a TODO comment on this test or in the code because we do not produce the optimal code when there is no default:
https://alive2.llvm.org/ce/z/7qxumF

[bcl5980]

update comments

[bcl5980]

@spatel Thanks for the review. For me write comments and commit message is much harder than code because of my poor English. These comments are really helpful .

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

UniqueResults.push_back(
       std::make_pair(Result, SmallVector<ConstantInt *, 4>(1, CaseVal)));
   return 1;
 }
 
 // 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, PHINode *&PHI, BasicBlock *&CommonDest,
+static bool initializeUniqueCases(SwitchInst *SI, PHINode *&PHI,
+                                  BasicBlock *&CommonDest,
                                   SwitchCaseResultVectorTy &UniqueResults,
-                      Constant *&DefaultResult, const DataLayout &DL,
+                                  Constant *&DefaultResult,
+                                  const DataLayout &DL,
                                   const TargetTransformInfo &TTI,
-                      uintptr_t MaxUniqueResults, uintptr_t MaxCasesPerResult) {
+                                  uintptr_t MaxUniqueResults) {
   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, TTI))
       return false;
 
     // Only one value per case is permitted.
     if (Results.size() > 1)
       return false;
 
     // Add the case->result mapping to UniqueResults.
     const uintptr_t NumCasesForResult =
         mapCaseToResult(CaseVal, UniqueResults, Results.begin()->second);
 
-    // Early out if there are too many cases for this result.
-    if (NumCasesForResult > MaxCasesPerResult)
-      return false;
-
     // Early out if there are too many unique results.
     if (UniqueResults.size() > MaxUniqueResults)
       return false;
 
     // Check the PHI consistency.
     if (!PHI)
       PHI = Results[0].first;
     else if (PHI != Results[0].first)
DefaultResult =
       DefaultResults.size() == 1 ? DefaultResults.begin()->second : nullptr;
   if ((!DefaultResult &&
        !isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg())))
     return false;
 
   return true;
 }
 
-// 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 select.
-// Example:
+// Helper function that checks if it is possible to transform a switch with:
+// 1. two cases (or two cases + default) that produces a result into a select.
 // 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;
 // }
-// TODO: Handle switches with more than 2 cases that map to the same result.
+// 2. n bits group cases map to the same result into an and.
+//   case 0, 4        (bit 1 group)        ---> and -5
+//   case 0, 2, 4, 6  (bit 0, 1 group)     ---> and -7
+//   case 0, 2, 8, 10 (bit 0, bit 2 group) ---> and -11
 static Value *foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector,
                                  Constant *DefaultResult, Value *Condition,
                                  IRBuilder<> &Builder) {
-  // If we are selecting between only two cases transform into a simple
-  // select or a two-way select if default is possible.
   if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
       ResultVector[1].second.size() == 1) {
+    // If we are selecting between only two cases transform into a simple
+    // select or a two-way select if default is possible.
     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");
   }
 
+  if (ResultVector.size() == 1 && DefaultResult) {
+    unsigned CaseCount = ResultVector[0].second.size();
+    if (isPowerOf2_32(CaseCount)) {
+      ConstantInt *MinCaseVal = ResultVector[0].second[0];
+      APInt BitMask = APInt::getZero(MinCaseVal->getBitWidth());
+      // find mininal value
+      for (auto Case : ResultVector[0].second) {
+        if (Case->getValue().slt(MinCaseVal->getValue()))
+          MinCaseVal = Case;
+      }
+
+      // Mark the bits case number touched 
+      for (auto Case : ResultVector[0].second) {
+        BitMask |= (Case->getValue() - MinCaseVal->getValue());
+      }
+
+      // Check if cases with the same result can cover all number 
+      // in touched bits
+      if (BitMask.countPopulation() == Log2_32(CaseCount)) {
+        if (!MinCaseVal->isNullValue())
+          Condition = Builder.CreateSub(Condition, MinCaseVal);
+        Value *And = Builder.CreateAnd(Condition, ~BitMask, "switch.and");
+        Value *Cmp = Builder.CreateICmpEQ(
+            And, Constant::getNullValue(And->getType()), "switch.selectcmp");
+        return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
+      }
+    }
+
     // Handle the degenerate case where two cases have the same value.
-  if (ResultVector.size() == 1 && ResultVector[0].second.size() == 2 &&
-      DefaultResult) {
-    Value *Cmp1 = Builder.CreateICmpEQ(
-        Condition, ResultVector[0].second[0], "switch.selectcmp.case1");
-    Value *Cmp2 = Builder.CreateICmpEQ(
-        Condition, ResultVector[0].second[1], "switch.selectcmp.case2");
+    if (ResultVector[0].second.size() == 2) {
+      Value *Cmp1 = Builder.CreateICmpEQ(Condition, ResultVector[0].second[0],
+                                         "switch.selectcmp.case1");
+      Value *Cmp2 = Builder.CreateICmpEQ(Condition, ResultVector[0].second[1],
+                                         "switch.selectcmp.case2");
       Value *Cmp = Builder.CreateOr(Cmp1, Cmp2, "switch.selectcmp");
       return Builder.CreateSelect(Cmp, ResultVector[0].first, DefaultResult);
     }
+  }
 
   return nullptr;
 }
 
 // Helper function to cleanup a switch instruction that has been converted into
 // a select, fixing up PHI nodes and basic blocks.
 static void removeSwitchAfterSelectFold(SwitchInst *SI, PHINode *PHI,
                                         Value *SelectValue,
static bool trySwitchToSelect(SwitchInst *SI, IRBuilder<> &Builder,
                               const TargetTransformInfo &TTI) {
   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, PHI, CommonDest, UniqueResults, DefaultResult,
-                             DL, TTI, /*MaxUniqueResults*/ 2,
-                             /*MaxCasesPerResult*/ 2))
+                             DL, TTI, /*MaxUniqueResults*/ 2))
     return false;
 
   assert(PHI != nullptr && "PHI for value select not found");
   Builder.SetInsertPoint(SI);
   Value *SelectValue =
       foldSwitchToSelect(UniqueResults, DefaultResult, Cond, Builder);
   if (!SelectValue)
     return false;

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

sw.bb:
   br label %return
 
 sw.epilog:
   br label %return
 
 return:
   %retval.0 = phi i32 [ 4, %sw.epilog ], [ 10, %sw.bb ]
   ret i32 %retval.0
 }
+
+define i1 @switch_to_and0(i8 %0) {
+; CHECK-LABEL: @switch_to_and0(
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 [[TMP0:%.*]], 43
+; CHECK-NEXT:    [[SWITCH_AND:%.*]] = and i8 [[TMP2]], -3
+; CHECK-NEXT:    [[SWITCH_SELECTCMP:%.*]] = icmp eq i8 [[SWITCH_AND]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false
+; CHECK-NEXT:    ret i1 [[TMP3]]
+;
+  switch i8 %0, label %2 [
+  i8 43, label %3
+  i8 45, label %3
+  ]
+
+2:
+  br label %3
+
+3:
+  %4 = phi i1 [ false, %2 ], [ true, %1 ], [ true, %1 ]
+  ret i1 %4
+}
+
+
+define i1 @switch_to_and1(i32 %i) {
+; CHECK-LABEL: @switch_to_and1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SWITCH_AND:%.*]] = and i32 [[I:%.*]], -7
+; CHECK-NEXT:    [[SWITCH_SELECTCMP:%.*]] = icmp eq i32 [[SWITCH_AND]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false
+; CHECK-NEXT:    ret i1 [[TMP0]]
+;
+entry:
+  switch i32 %i, label %lor.rhs [
+  i32 0, label %lor.end
+  i32 2, label %lor.end
+  i32 4, label %lor.end
+  i32 6, label %lor.end
+  ]
+
+lor.rhs:
+  br label %lor.end
+
+lor.end:
+  %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ], [ true, %entry ]
+  ret i1 %0
+}
+
+define i1 @switch_to_and2(i32 %i) {
+; CHECK-LABEL: @switch_to_and2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SWITCH_AND:%.*]] = and i32 [[I:%.*]], -11
+; CHECK-NEXT:    [[SWITCH_SELECTCMP:%.*]] = icmp eq i32 [[SWITCH_AND]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false
+; CHECK-NEXT:    ret i1 [[TMP0]]
+;
+entry:
+  switch i32 %i, label %lor.rhs [
+  i32 0, label %lor.end
+  i32 2, label %lor.end
+  i32 8, label %lor.end
+  i32 10, label %lor.end
+  ]
+
+lor.rhs:
+  br label %lor.end
+
+lor.end:
+  %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ], [ true, %entry ]
+  ret i1 %0
+}
+
+define i1 @switch_to_and3(i32 %i) {
+; CHECK-LABEL: @switch_to_and3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[I:%.*]], 2
+; CHECK-NEXT:    [[SWITCH_AND:%.*]] = and i32 [[TMP0]], -11
+; CHECK-NEXT:    [[SWITCH_SELECTCMP:%.*]] = icmp eq i32 [[SWITCH_AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[SWITCH_SELECTCMP]], i1 true, i1 false
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+entry:
+  switch i32 %i, label %lor.rhs [
+  i32 2, label %lor.end
+  i32 4, label %lor.end
+  i32 10, label %lor.end
+  i32 12, label %lor.end
+  ]
+
+lor.rhs:
+  br label %lor.end
+
+lor.end:
+  %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ], [ true, %entry ]
+  ret i1 %0
+}
+
+define i1 @negative_switch_to_and0(i32 %i) {
+; CHECK-LABEL: @negative_switch_to_and0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[I:%.*]], label [[LOR_RHS:%.*]] [
+; CHECK-NEXT:    i32 1, label [[LOR_END:%.*]]
+; CHECK-NEXT:    i32 4, label [[LOR_END]]
+; CHECK-NEXT:    i32 10, label [[LOR_END]]
+; CHECK-NEXT:    i32 12, label [[LOR_END]]
+; CHECK-NEXT:    ]
+; CHECK:       lor.rhs:
+; CHECK-NEXT:    br label [[LOR_END]]
+; CHECK:       lor.end:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ false, [[LOR_RHS]] ], [ true, [[ENTRY]] ], [ true, [[ENTRY]] ], [ true, [[ENTRY]] ]
+; CHECK-NEXT:    ret i1 [[TMP0]]
+;
+entry:
+  switch i32 %i, label %lor.rhs [
+  i32 1, label %lor.end
+  i32 4, label %lor.end
+  i32 10, label %lor.end
+  i32 12, label %lor.end
+  ]
+
+lor.rhs:
+  br label %lor.end
+
+lor.end:
+  %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ], [ true, %entry ]
+  ret i1 %0
+}
+
+define i1 @negative_switch_to_and1(i32 %i) {
+; CHECK-LABEL: @negative_switch_to_and1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[I:%.*]], label [[LOR_RHS:%.*]] [
+; CHECK-NEXT:    i32 0, label [[LOR_END:%.*]]
+; CHECK-NEXT:    i32 2, label [[LOR_END]]
+; CHECK-NEXT:    i32 4, label [[LOR_END]]
+; CHECK-NEXT:    ]
+; CHECK:       lor.rhs:
+; CHECK-NEXT:    br label [[LOR_END]]
+; CHECK:       lor.end:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ false, [[LOR_RHS]] ], [ true, [[ENTRY]] ], [ true, [[ENTRY]] ]
+; CHECK-NEXT:    ret i1 [[TMP0]]
+;
+entry:
+  switch i32 %i, label %lor.rhs [
+  i32 0, label %lor.end
+  i32 2, label %lor.end
+  i32 4, label %lor.end
+  ]
+
+lor.rhs:
+  br label %lor.end
+
+lor.end:
+  %0 = phi i1 [ true, %entry ], [ false, %lor.rhs ], [ true, %entry ], [ true, %entry ]
+  ret i1 %0
+}