[SimplifyCFG] use fshr instead of shl/lshr/or

[shawnl]

Summary

This is patch 3 is a series beginning with D61150

We already try (but fail due to lack of sub op)
to convert this to fshr in AggressiveInstCombine.cpp:92.

Rotate instructions can be a single instructions sometimes,
comparedto three. See
https://bugs.llvm.org/show_bug.cgi?id=37461

[nikic]

As far as I know we don't have any known issues in funnel shift optimization or codegen. We should check with @spatel though.

[lebedev.ri]

The description on the patch is really unhelpful.
It should explain why the change is needed/should happen, not how great the new intrinsic is, how bad it is not to support it...
Also, as usual, please upload all patches with full context.

We already try (but fail due to lack of sub op)
to convert this to fshr in AggressiveInstCombine.cpp:92.

There wouldn't be any sub op here, because these are constants,
and we don't seem to canonicalize this rotate pattern with constants to fshl in instcombine/aggressiveinstcombine.
That is a separate issue, i'm not sure if it's a bug or not, so please file a bug.

[jmolloy]

Hi,

Yes, I also have the same concerns as Roman. If we don't canonicalize to fshr in instcombine, then we shouldn't canonicalize to fshr in simplifycfg. They're both canonicalization passes.

Given the testing burden, if you really want to go down this route I would recommend changing instcombine *first*, from which you can observe the fallout with a large testing base. Then change this code, which triggers in many fewer cases.

[spatel]

In D61158#1480108, @jmolloy wrote:

Hi,

Yes, I also have the same concerns as Roman. If we don't canonicalize to fshr in instcombine, then we shouldn't canonicalize to fshr in simplifycfg. They're both canonicalization passes.

Given the testing burden, if you really want to go down this route I would recommend changing instcombine *first*, from which you can observe the fallout with a large testing base. Then change this code, which triggers in many fewer cases.

I agree - the canonicalization should happen in instcombine (and that might make doing it in simplifycfg an academic exercise since we can always count on instcombine to do it).

In D61158, @nikic wrote:

As far as I know we don't have any known issues in funnel shift optimization or codegen.

That is my understanding too. Targets that support some kind of rotate/funnel instruction should produce those from the intrinsic. Targets that don't have that should translate exactly to the sh/sh/or sequence when building SDAG. We already canonicalize to the funnel shift intrinsics for a variable shift amount in several cases, but nobody bothered to add the constant shift amount pattern because it wasn't causing problems like the variable shift case. But using the intrinsics will still theoretically improve passes like inlining and vectorization (assuming they have their cost models straight).

Final note: please don't look at AggressiveInstCombine as your first source for canonicalization truth; use InstCombine for that and propose changes there. "AIC" is a home for expensive/unusual patterns and (at least currently) doesn't run without -O3.

[jmolloy]

lib/Transforms/Utils/SimplifyCFG.cpp

5587

I still don't agree with using fshr here; I've given you my rationale before.

[shawnl]

there are no problems, as we can just lower fshr down to what I replaced

http://llvm.org/doxygen/TargetLowering_8cpp_source.html#l04428

[jmolloy]

I don't agree; if you're going to add this canonicalization, please do it in InstCombine first.

lib/Transforms/Utils/SimplifyCFG.cpp

 
   // Cttz often has an edge condition on 0 which means that the bit-width
   // is important, however here there is no such edge condition because if
   // 0 is the only value then a shift does nothing, and LLVM requires
   // well-formed IR to not have duplicate cases (so the minimum will not
   // be BitWidth)
   unsigned Shift = 64;
   for (auto &V : Values)
-    Shift = std::min(Shift, countTrailingZeros((uint64_t)V);
+    Shift = std::min(Shift, countTrailingZeros((uint64_t)V));
   if (Shift > 0)
     for (auto &V : Values)
       V = (int64_t)((uint64_t)V >> Shift);
 
   if (!isSwitchDense(Values))
     // Transform didn't create a dense switch.
     return false;
 
   // The obvious transform is to shift the switch condition right and emit a
   // check that the condition actually cleanly divided by GCD, i.e.
   //   C & (1 << Shift - 1) == 0
   // inserting a new CFG edge to handle the case where it didn't divide cleanly.
   //
   // A cheaper way of doing this is a simple ROTR(C, Shift). This performs the
   // shift and puts the shifted-off bits in the uppermost bits. If any of these
   // are nonzero then the switch condition will be very large and will hit the
   // default case.
 
   auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
   Builder.SetInsertPoint(SI);
-  auto *ShiftC = ConstantInt::get(Ty, Shift);
-  auto *Sub = Builder.CreateSub(SI->getCondition(), ConstantInt::get(Ty, Base));
-  auto *LShr = Builder.CreateLShr(Sub, ShiftC);
-  auto *Shl = Builder.CreateShl(Sub, Ty->getBitWidth() - Shift);
-  auto *Rot = Builder.CreateOr(LShr, Shl);
-  SI->replaceUsesOfWith(SI->getCondition(), Rot);
+  Value *Key = SI->getCondition();
+  if (Base > 0) {
+    Key = Builder.CreateSub(Key, ConstantInt::get(Ty, Base), "switch.rangereduce");
+  }
+  if (Shift > 0) {
+    auto *ShiftC = ConstantInt::get(Ty, Shift);
+    Function *Fshr = Intrinsic::getDeclaration(SI->getModule(), Intrinsic::fshr, Ty);
+    Key = Builder.CreateCall(Fshr, {Key, Key, ShiftC}, "switch.rangereduce");
+  }
+  SI->replaceUsesOfWith(SI->getCondition(), Key);
 
   for (auto Case : SI->cases()) {
     auto *Orig = Case.getCaseValue();
     auto Sub = Orig->getValue() - APInt(Ty->getBitWidth(), Base);
     Case.setValue(
-        cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(ShiftC->getValue()))));
+        cast<ConstantInt>(ConstantInt::get(Ty, Sub.lshr(Shift))));
   }
   return true;
 }
 
 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();
 
   if (isValueEqualityComparison(SI)) {

test/Transforms/SimplifyCFG/rangereduce.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -switch-to-lookup -S | FileCheck %s
 ; RUN: opt < %s -passes='simplify-cfg<switch-to-lookup>' -S | FileCheck %s
 
 target datalayout = "e-n32"
 
 define i32 @test1(i32 %a) {
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE:%.*]] = sub i32 [[A:%.*]], 97
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE1:%.*]] = call i32 @llvm.fshr.i32(i32 [[SWITCH_RANGEREDUCE]], i32 [[SWITCH_RANGEREDUCE]], i32 2)
+; CHECK-NEXT:    switch i32 [[SWITCH_RANGEREDUCE1]], label [[DEF:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
 ; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
 ; CHECK-NEXT:    i32 2, label [[THREE:%.*]]
 ; CHECK-NEXT:    i32 3, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]

 two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i32 @test6(i32 %a) optsize {
 ; CHECK-LABEL: @test6(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], -109
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE:%.*]] = call i32 @llvm.fshr.i32(i32 [[A:%.*]], i32 [[A]], i32 2)
+; CHECK-NEXT:    switch i32 [[SWITCH_RANGEREDUCE]], label [[DEF:%.*]] [
 ; CHECK-NEXT:    i32 3, label [[ONE:%.*]]
 ; CHECK-NEXT:    i32 2, label [[TWO:%.*]]
 ; CHECK-NEXT:    i32 1, label [[THREE:%.*]]
 ; CHECK-NEXT:    i32 0, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]

 two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i8 @test7(i8 %a) optsize {
 ; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i8 [[A:%.*]], -36
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i8 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i8 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP4:%.*]] = or i8 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i8 [[TMP4]], 4
-; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]]
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE:%.*]] = call i8 @llvm.fshr.i8(i8 [[A:%.*]], i8 [[A]], i8 2)
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[SWITCH_RANGEREDUCE]], 4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[TMP4]] to i32
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[SWITCH_RANGEREDUCE]] to i32
 ; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i32 [[SWITCH_CAST]], 8
 ; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 -943228976, [[SWITCH_SHIFTAMT]]
 ; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
 ; CHECK-NEXT:    ret i8 [[SWITCH_MASKED]]
 ; CHECK:       def:
 ; CHECK-NEXT:    ret i8 -93
 ;
   switch i8 %a, label %def [

 two:
   ret i8 1143
 three:
   ret i8 99783
 }
 
 define i32 @test8(i32 %a) optsize {
 ; CHECK-LABEL: @test8(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE:%.*]] = sub i32 [[A:%.*]], 97
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE1:%.*]] = call i32 @llvm.fshr.i32(i32 [[SWITCH_RANGEREDUCE]], i32 [[SWITCH_RANGEREDUCE]], i32 2)
+; CHECK-NEXT:    switch i32 [[SWITCH_RANGEREDUCE1]], label [[DEF:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
 ; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
 ; CHECK-NEXT:    i32 2, label [[THREE:%.*]]
 ; CHECK-NEXT:    i32 4, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]

 two:
   ret i32 1143
 three:
   ret i32 99783
 }
 
 define i32 @test9(i32 %a) {
 ; CHECK-LABEL: @test9(
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 6
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 1
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 31
-; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[DEF:%.*]] [
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE:%.*]] = sub i32 [[A:%.*]], 6
+; CHECK-NEXT:    [[SWITCH_RANGEREDUCE1:%.*]] = call i32 @llvm.fshr.i32(i32 [[SWITCH_RANGEREDUCE]], i32 [[SWITCH_RANGEREDUCE]], i32 1)
+; CHECK-NEXT:    switch i32 [[SWITCH_RANGEREDUCE1]], label [[DEF:%.*]] [
 ; CHECK-NEXT:    i32 6, label [[ONE:%.*]]
 ; CHECK-NEXT:    i32 7, label [[TWO:%.*]]
 ; CHECK-NEXT:    i32 0, label [[THREE:%.*]]
 ; CHECK-NEXT:    i32 2, label [[THREE]]
 ; CHECK-NEXT:    ]
 ; CHECK:       def:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ]
 ; CHECK-NEXT:    ret i32 [[MERGE]]

test/Transforms/SimplifyCFG/switch-dead-default.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -S -passes='simplify-cfg<switch-to-lookup>' | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 declare void @foo(i32)
 
 define void @test(i1 %a) {
 ; CHECK-LABEL: @test(
-; CHECK-NEXT:    br i1 [[A:%.*]], label [[TRUE:%.*]], label [[FALSE:%.*]]
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i1 [[A:%.*]], true
+; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i1 [[A_OFF]], true
+; CHECK-NEXT:    br i1 [[SWITCH]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ;
   switch i1 %a, label %default [i1 1, label %true
   i1 0, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 }
 
 define void @test2(i2 %a) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    switch i2 [[A:%.*]], label [[DEFAULT1:%.*]] [
 ; CHECK-NEXT:    i2 0, label [[CASE0:%.*]]
 ; CHECK-NEXT:    i2 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    i2 -2, label [[CASE2:%.*]]
 ; CHECK-NEXT:    i2 -1, label [[CASE3:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       case0:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case1:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case2:
-; CHECK-NEXT:    tail call void @foo(i32 2)
+; CHECK-NEXT:    call void @foo(i32 2)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case3:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ; CHECK:       default1:
 ; CHECK-NEXT:    unreachable
 ;
   switch i2 %a, label %default [i2 0, label %case0
   i2 1, label %case1
   i2 2, label %case2
   i2 3, label %case3]

 define void @test3(i2 %a) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    switch i2 [[A:%.*]], label [[DEFAULT:%.*]] [
 ; CHECK-NEXT:    i2 0, label [[CASE0:%.*]]
 ; CHECK-NEXT:    i2 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    i2 -2, label [[CASE2:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       case0:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case1:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case2:
-; CHECK-NEXT:    tail call void @foo(i32 2)
+; CHECK-NEXT:    call void @foo(i32 2)
 ; CHECK-NEXT:    ret void
 ; CHECK:       default:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ;
   switch i2 %a, label %default [i2 0, label %case0
   i2 1, label %case1
   i2 2, label %case2]
 
 case0:
   call void @foo(i32 0)

 ; number of possible cases.
 define void @test4(i128 %a) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    switch i128 [[A:%.*]], label [[DEFAULT:%.*]] [
 ; CHECK-NEXT:    i128 0, label [[CASE0:%.*]]
 ; CHECK-NEXT:    i128 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       case0:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ; CHECK:       case1:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       default:
-; CHECK-NEXT:    tail call void @foo(i32 0)
+; CHECK-NEXT:    call void @foo(i32 0)
 ; CHECK-NEXT:    ret void
 ;
   switch i128 %a, label %default [i128 0, label %case0
   i128 1, label %case1]
 
 case0:
   call void @foo(i32 0)
   ret void
 case1:
   call void @foo(i32 1)
   ret void
 default:
   call void @foo(i32 0)
   ret void
 }
 
 ; All but one bit known zero
 define void @test5(i8 %a) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[A:%.*]], 2
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[SWITCH:%.*]] = icmp eq i8 [[A]], 1
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i8 [[A]], -1
+; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i8 [[A_OFF]], 1
 ; CHECK-NEXT:    br i1 [[SWITCH]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ;
   %cmp = icmp ult i8 %a, 2
   call void @llvm.assume(i1 %cmp)
   switch i8 %a, label %default [i8 1, label %true
   i8 0, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 }
 
 ;; All but one bit known one
 define void @test6(i8 %a) {
 ; CHECK-LABEL: @test6(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[A:%.*]], -3
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[SWITCH:%.*]] = icmp eq i8 [[A]], -1
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], -2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], -2
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i8 [[A]], 1
+; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i8 [[A_OFF]], 1
 ; CHECK-NEXT:    br i1 [[SWITCH]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ;
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, 254
   call void @llvm.assume(i1 %cmp)
   switch i8 %a, label %default [i8 255, label %true
   i8 254, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 }
 
 ; Check that we can eliminate both dead cases and dead defaults
 ; within a single run of simplify-cfg
 define void @test7(i8 %a) {
 ; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[A:%.*]], -3
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[SWITCH:%.*]] = icmp eq i8 [[A]], -1
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], -2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], -2
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i8 [[A]], 1
+; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i8 [[A_OFF]], 1
 ; CHECK-NEXT:    br i1 [[SWITCH]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    tail call void @foo(i32 1)
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    tail call void @foo(i32 3)
+; CHECK-NEXT:    call void @foo(i32 3)
 ; CHECK-NEXT:    ret void
 ;
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, 254
   call void @llvm.assume(i1 %cmp)
   switch i8 %a, label %default [i8 255, label %true
   i8 254, label %false
   i8 0, label %also_dead]

 
 ;; All but one bit known undef
 ;; Note: This is currently testing an optimization which doesn't trigger. The
 ;; case this is protecting against is that a bit could be assumed both zero
 ;; *or* one given we know it's undef.  ValueTracking doesn't do this today,
 ;; but it doesn't hurt to confirm.
 define void @test8(i8 %a) {
 ; CHECK-LABEL: @test8(
-; CHECK-NEXT:    unreachable
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], -2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], undef
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    switch i8 [[A]], label [[DEFAULT:%.*]] [
+; CHECK-NEXT:    i8 -1, label [[TRUE:%.*]]
+; CHECK-NEXT:    i8 -2, label [[FALSE:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       true:
+; CHECK-NEXT:    call void @foo(i32 1)
+; CHECK-NEXT:    ret void
+; CHECK:       false:
+; CHECK-NEXT:    call void @foo(i32 3)
+; CHECK-NEXT:    ret void
+; CHECK:       default:
+; CHECK-NEXT:    call void @foo(i32 2)
+; CHECK-NEXT:    ret void
 ;
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, undef
   call void @llvm.assume(i1 %cmp)
   switch i8 %a, label %default [i8 255, label %true
   i8 254, label %false]
 true:
   call void @foo(i32 1)