[GlobalISel] Implement bit-test switch table optimization

[aemerson]

Summary

This is mostly a straight port from SelectionDAG. We re-use the actual bit-test analysis part from SwitchLoweringUtils, which was factored out earlier to support jump-tables.

[arsenm]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

729

Should just change the insert point for the existing one? This loses the CSEInfo

738

Don't need the {}

744

Why depend on "legal" types? The concept should mostly be going away

757

This loses the address space, and I'm not sure why you would ever be avoiding the pointer type. Also, in general you should never need to call getPointerTy, since you can just re-use the type of the thing you already have

776

Don't need getReg

790

Same as above

795

Don't need = 0

940

Missing newline

[paquette]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

784

Move Doxygen comment to IRTranslator.h?

Also this comment isn't super useful.

[aemerson]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

744

This was from SelectionDAG, I think for performance reasons. I'll remove it.

776

Actually I do for buildBrCond() since that is still expecting a Register. I'll change that though.

[aemerson]

Address feedback.

[aemerson]

Posted old patch before, address feedback for reals this time.

[arsenm]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

769

Still have the .getReg not that it really matters

[aemerson]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

769

I'll remove it before commit.

[aemerson]

ping

[arsenm]

llvm/test/CodeGen/AArch64/GlobalISel/irtranslator-switch-bittest.ll

133

Can you add a few degenerate cases with 1 and 2 switch cases (and 0 if that's even accepted).

I also don't think any of these hit the omit-branch-to-next block case

[aemerson]

llvm/test/CodeGen/AArch64/GlobalISel/irtranslator-switch-bittest.ll

133

I'll add a test to check for a single BT cluster, but 1 or 2 switch cases by themselves won't trigger this optimization, it'll just use a simple equality check.

[aemerson]

Add another test case for just a single BT cluster. This test also falls through instead of generating a G_BR.

llvm/include/llvm/CodeGen/GlobalISel/IRTranslator.h

private:
   bool emitJumpTableHeader(SwitchCG::JumpTable &JT,
                            SwitchCG::JumpTableHeader &JTH,
                            MachineBasicBlock *HeaderBB);
   void emitJumpTable(SwitchCG::JumpTable &JT, MachineBasicBlock *MBB);
 
   void emitSwitchCase(SwitchCG::CaseBlock &CB, MachineBasicBlock *SwitchBB,
                       MachineIRBuilder &MIB);
 
-  bool lowerJumpTableWorkItem(SwitchCG::SwitchWorkListItem W,
-                              MachineBasicBlock *SwitchMBB,
-                              MachineBasicBlock *CurMBB,
-                              MachineBasicBlock *DefaultMBB,
-                              MachineIRBuilder &MIB,
-                              MachineFunction::iterator BBI,
-                              BranchProbability UnhandledProbs,
-                              SwitchCG::CaseClusterIt I,
-                              MachineBasicBlock *Fallthrough,
-                              bool FallthroughUnreachable);
+  /// Generate for for the BitTest header block, which precedes each sequence of
+  /// BitTestCases.
+  void emitBitTestHeader(SwitchCG::BitTestBlock &BTB,
+                         MachineBasicBlock *SwitchMBB);
+  /// Generate code to produces one "bit test" for a given BitTestCase \p B.
+  void emitBitTestCase(SwitchCG::BitTestBlock &BB, MachineBasicBlock *NextMBB,
+                       BranchProbability BranchProbToNext, Register Reg,
+                       SwitchCG::BitTestCase &B, MachineBasicBlock *SwitchBB);
+
+  bool lowerJumpTableWorkItem(
+      SwitchCG::SwitchWorkListItem W, MachineBasicBlock *SwitchMBB,
+      MachineBasicBlock *CurMBB, MachineBasicBlock *DefaultMBB,
+      MachineIRBuilder &MIB, MachineFunction::iterator BBI,
+      BranchProbability UnhandledProbs, SwitchCG::CaseClusterIt I,
+      MachineBasicBlock *Fallthrough, bool FallthroughUnreachable);
 
-  bool lowerSwitchRangeWorkItem(SwitchCG::CaseClusterIt I,
-                                Value *Cond,
+  bool lowerSwitchRangeWorkItem(SwitchCG::CaseClusterIt I, Value *Cond,
                                 MachineBasicBlock *Fallthrough,
                                 bool FallthroughUnreachable,
                                 BranchProbability UnhandledProbs,
                                 MachineBasicBlock *CurMBB,
                                 MachineIRBuilder &MIB,
                                 MachineBasicBlock *SwitchMBB);
 
+  bool lowerBitTestWorkItem(
+      SwitchCG::SwitchWorkListItem W, MachineBasicBlock *SwitchMBB,
+      MachineBasicBlock *CurMBB, MachineBasicBlock *DefaultMBB,
+      MachineIRBuilder &MIB, MachineFunction::iterator BBI,
+      BranchProbability DefaultProb, BranchProbability UnhandledProbs,
+      SwitchCG::CaseClusterIt I, MachineBasicBlock *Fallthrough,
+      bool FallthroughUnreachable);
+
   bool lowerSwitchWorkItem(SwitchCG::SwitchWorkListItem W, Value *Cond,
                            MachineBasicBlock *SwitchMBB,
                            MachineBasicBlock *DefaultMBB,
                            MachineIRBuilder &MIB);
 
   bool translateSwitch(const User &U, MachineIRBuilder &MIRBuilder);
   // End switch lowering section.
 

llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

public:
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Tst must be a generic virtual register with scalar
   ///      type. At the beginning of legalization, this will be a single
   ///      bit (s1). Targets with interesting flags registers may change
   ///      this. For a wider type, whether the branch is taken must only
   ///      depend on bit 0 (for now).
   ///
   /// \return The newly created instruction.
-  MachineInstrBuilder buildBrCond(Register Tst, MachineBasicBlock &Dest);
+  MachineInstrBuilder buildBrCond(const SrcOp &Tst, MachineBasicBlock &Dest);
 
   /// Build and insert G_BRINDIRECT \p Tgt
   ///
   /// G_BRINDIRECT is an indirect branch to \p Tgt.
   ///
   /// \pre setBasicBlock or setMI must have been called.
   /// \pre \p Tgt must be a generic virtual register with pointer type.
   ///

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

bool IRTranslator::translateSwitch(const User &U, MachineIRBuilder &MIB) {
   if (Clusters.empty()) {
     SwitchMBB->addSuccessor(DefaultMBB);
     if (DefaultMBB != SwitchMBB->getNextNode())
       MIB.buildBr(*DefaultMBB);
     return true;
   }
 
   SL->findJumpTables(Clusters, &SI, DefaultMBB, nullptr, nullptr);
+  SL->findBitTestClusters(Clusters, &SI);
 
   LLVM_DEBUG({
     dbgs() << "Case clusters: ";
     for (const CaseCluster &C : Clusters) {
       if (C.Kind == CC_JumpTable)
         dbgs() << "JT:";
       if (C.Kind == CC_BitTests)
         dbgs() << "BT:";
bool IRTranslator::lowerSwitchRangeWorkItem(SwitchCG::CaseClusterIt I,
   // The false probability is the sum of all unhandled cases.
   CaseBlock CB(Pred, FallthroughUnreachable, LHS, RHS, MHS, I->MBB, Fallthrough,
                CurMBB, MIB.getDebugLoc(), I->Prob, UnhandledProbs);
 
   emitSwitchCase(CB, SwitchMBB, MIB);
   return true;
 }
 
+void IRTranslator::emitBitTestHeader(SwitchCG::BitTestBlock &B,
+                                     MachineBasicBlock *SwitchBB) {
+  MachineIRBuilder &MIB = *CurBuilder;
+  MIB.setMBB(*SwitchBB);
+
+  // Subtract the minimum value.
+  Register SwitchOpReg = getOrCreateVReg(*B.SValue);
+
+  LLT SwitchOpTy = MRI->getType(SwitchOpReg);
+  Register MinValReg = MIB.buildConstant(SwitchOpTy, B.First).getReg(0);
+  auto RangeSub = MIB.buildSub(SwitchOpTy, SwitchOpReg, MinValReg);
+
+  // Ensure that the type will fit the mask value.
+  LLT MaskTy = SwitchOpTy;
+  for (unsigned I = 0, E = B.Cases.size(); I != E; ++I) {
+    if (!isUIntN(SwitchOpTy.getSizeInBits(), B.Cases[I].Mask)) {
+      // Switch table case range are encoded into series of masks.
+      // Just use pointer type, it's guaranteed to fit.
+      MaskTy = LLT::scalar(64);
+      break;
+    }
+  }
+  Register SubReg = RangeSub.getReg(0);
+  if (SwitchOpTy != MaskTy)
+    SubReg = MIB.buildZExtOrTrunc(MaskTy, SubReg).getReg(0);
+
+  B.RegVT = getMVTForLLT(MaskTy);
+  B.Reg = SubReg;
+
+  MachineBasicBlock *MBB = B.Cases[0].ThisBB;
+
+  if (!B.OmitRangeCheck)
+    addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb);
+  addSuccessorWithProb(SwitchBB, MBB, B.Prob);
+
+  SwitchBB->normalizeSuccProbs();
+
+  if (!B.OmitRangeCheck) {
+    // Conditional branch to the default block.
+    auto RangeCst = MIB.buildConstant(SwitchOpTy, B.Range);
+    auto RangeCmp = MIB.buildICmp(CmpInst::Predicate::ICMP_UGT, LLT::scalar(1),
+                                  RangeSub, RangeCst);
+    MIB.buildBrCond(RangeCmp, *B.Default);
+  }
+
+  // Avoid emitting unnecessary branches to the next block.
+  if (MBB != SwitchBB->getNextNode())
+    MIB.buildBr(*MBB);
+}
+
+void IRTranslator::emitBitTestCase(SwitchCG::BitTestBlock &BB,
+                                   MachineBasicBlock *NextMBB,
+                                   BranchProbability BranchProbToNext,
+                                   Register Reg, SwitchCG::BitTestCase &B,
+                                   MachineBasicBlock *SwitchBB) {
+  MachineIRBuilder &MIB = *CurBuilder;
+  MIB.setMBB(*SwitchBB);
+
+  LLT SwitchTy = getLLTForMVT(BB.RegVT);
+  Register Cmp;
+  unsigned PopCount = countPopulation(B.Mask);
+  if (PopCount == 1) {
+    // Testing for a single bit; just compare the shift count with what it
+    // would need to be to shift a 1 bit in that position.
+    auto MaskTrailingZeros =
+        MIB.buildConstant(SwitchTy, countTrailingZeros(B.Mask));
+    Cmp =
+        MIB.buildICmp(ICmpInst::ICMP_EQ, LLT::scalar(1), Reg, MaskTrailingZeros)
+            .getReg(0);
+  } else if (PopCount == BB.Range) {
+    // There is only one zero bit in the range, test for it directly.
+    auto MaskTrailingOnes =
+        MIB.buildConstant(SwitchTy, countTrailingOnes(B.Mask));
+    Cmp = MIB.buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), Reg, MaskTrailingOnes)
+              .getReg(0);
+  } else {
+    // Make desired shift.
+    auto CstOne = MIB.buildConstant(SwitchTy, 1);
+    auto SwitchVal = MIB.buildShl(SwitchTy, CstOne, Reg);
+
+    // Emit bit tests and jumps.
+    auto CstMask = MIB.buildConstant(SwitchTy, B.Mask);
+    auto AndOp = MIB.buildAnd(SwitchTy, SwitchVal, CstMask);
+    auto CstZero = MIB.buildConstant(SwitchTy, 0);
+    Cmp = MIB.buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), AndOp, CstZero)
+              .getReg(0);
+  }
+
+  // The branch probability from SwitchBB to B.TargetBB is B.ExtraProb.
+  addSuccessorWithProb(SwitchBB, B.TargetBB, B.ExtraProb);
+  // The branch probability from SwitchBB to NextMBB is BranchProbToNext.
+  addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext);
+  // It is not guaranteed that the sum of B.ExtraProb and BranchProbToNext is
+  // one as they are relative probabilities (and thus work more like weights),
+  // and hence we need to normalize them to let the sum of them become one.
+  SwitchBB->normalizeSuccProbs();
+
+  // Record the fact that the IR edge from the header to the bit test target
+  // will go through our new block. Neeeded for PHIs to have nodes added.
+  addMachineCFGPred({BB.Parent->getBasicBlock(), B.TargetBB->getBasicBlock()},
+                    SwitchBB);
+
+  MIB.buildBrCond(Cmp, *B.TargetBB);
+
+  // Avoid emitting unnecessary branches to the next block.
+  if (NextMBB != SwitchBB->getNextNode())
+    MIB.buildBr(*NextMBB);
+}
+
+bool IRTranslator::lowerBitTestWorkItem(
+    SwitchCG::SwitchWorkListItem W, MachineBasicBlock *SwitchMBB,
+    MachineBasicBlock *CurMBB, MachineBasicBlock *DefaultMBB,
+    MachineIRBuilder &MIB, MachineFunction::iterator BBI,
+    BranchProbability DefaultProb, BranchProbability UnhandledProbs,
+    SwitchCG::CaseClusterIt I, MachineBasicBlock *Fallthrough,
+    bool FallthroughUnreachable) {
+  using namespace SwitchCG;
+  MachineFunction *CurMF = SwitchMBB->getParent();
+  // FIXME: Optimize away range check based on pivot comparisons.
+  BitTestBlock *BTB = &SL->BitTestCases[I->BTCasesIndex];
+  // The bit test blocks haven't been inserted yet; insert them here.
+  for (BitTestCase &BTC : BTB->Cases)
+    CurMF->insert(BBI, BTC.ThisBB);
+
+  // Fill in fields of the BitTestBlock.
+  BTB->Parent = CurMBB;
+  BTB->Default = Fallthrough;
+
+  BTB->DefaultProb = UnhandledProbs;
+  // If the cases in bit test don't form a contiguous range, we evenly
+  // distribute the probability on the edge to Fallthrough to two
+  // successors of CurMBB.
+  if (!BTB->ContiguousRange) {
+    BTB->Prob += DefaultProb / 2;
+    BTB->DefaultProb -= DefaultProb / 2;
+  }
+
+  if (FallthroughUnreachable) {
+    // Skip the range check if the fallthrough block is unreachable.
+    BTB->OmitRangeCheck = true;
+  }
+
+  // If we're in the right place, emit the bit test header right now.
+  if (CurMBB == SwitchMBB) {
+    emitBitTestHeader(*BTB, SwitchMBB);
+    BTB->Emitted = true;
+  }
+  return true;
+}
+
 bool IRTranslator::lowerSwitchWorkItem(SwitchCG::SwitchWorkListItem W,
                                        Value *Cond,
                                        MachineBasicBlock *SwitchMBB,
                                        MachineBasicBlock *DefaultMBB,
                                        MachineIRBuilder &MIB) {
   using namespace SwitchCG;
   MachineFunction *CurMF = FuncInfo.MF;
   MachineBasicBlock *NextMBB = nullptr;
for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) {
     } else {
       Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock());
       CurMF->insert(BBI, Fallthrough);
     }
     UnhandledProbs -= I->Prob;
 
     switch (I->Kind) {
     case CC_BitTests: {
-      LLVM_DEBUG(dbgs() << "Switch to bit test optimization unimplemented");
-      return false; // Bit tests currently unimplemented.
+      if (!lowerBitTestWorkItem(W, SwitchMBB, CurMBB, DefaultMBB, MIB, BBI,
+                                DefaultProb, UnhandledProbs, I, Fallthrough,
+                                FallthroughUnreachable)) {
+        LLVM_DEBUG(dbgs() << "Failed to lower bit test for switch");
+        return false;
       }
+      break;
+    }
+
     case CC_JumpTable: {
       if (!lowerJumpTableWorkItem(W, SwitchMBB, CurMBB, DefaultMBB, MIB, BBI,
                                   UnhandledProbs, I, Fallthrough,
                                   FallthroughUnreachable)) {
         LLVM_DEBUG(dbgs() << "Failed to lower jump table");
         return false;
       }
       break;
#include "llvm/IR/Instruction.def"
     EntryBuilder->buildBlockAddress(Reg, BA);
   } else
     return false;
 
   return true;
 }
 
 void IRTranslator::finalizeBasicBlock() {
+  for (auto &BTB : SL->BitTestCases) {
+    // Emit header first, if it wasn't already emitted.
+    if (!BTB.Emitted)
+      emitBitTestHeader(BTB, BTB.Parent);
+
+    BranchProbability UnhandledProb = BTB.Prob;
+    for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
+      UnhandledProb -= BTB.Cases[j].ExtraProb;
+      // Set the current basic block to the mbb we wish to insert the code into
+      MachineBasicBlock *MBB = BTB.Cases[j].ThisBB;
+      // If all cases cover a contiguous range, it is not necessary to jump to
+      // the default block after the last bit test fails. This is because the
+      // range check during bit test header creation has guaranteed that every
+      // case here doesn't go outside the range. In this case, there is no need
+      // to perform the last bit test, as it will always be true. Instead, make
+      // the second-to-last bit-test fall through to the target of the last bit
+      // test, and delete the last bit test.
+
+      MachineBasicBlock *NextMBB;
+      if (BTB.ContiguousRange && j + 2 == ej) {
+        // Second-to-last bit-test with contiguous range: fall through to the
+        // target of the final bit test.
+        NextMBB = BTB.Cases[j + 1].TargetBB;
+      } else if (j + 1 == ej) {
+        // For the last bit test, fall through to Default.
+        NextMBB = BTB.Default;
+      } else {
+        // Otherwise, fall through to the next bit test.
+        NextMBB = BTB.Cases[j + 1].ThisBB;
+      }
+
+      emitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j], MBB);
+
+      // FIXME delete this block below?
+      if (BTB.ContiguousRange && j + 2 == ej) {
+        // Since we're not going to use the final bit test, remove it.
+        BTB.Cases.pop_back();
+        break;
+      }
+    }
+    // This is "default" BB. We have two jumps to it. From "header" BB and from
+    // last "case" BB, unless the latter was skipped.
+    CFGEdge HeaderToDefaultEdge = {BTB.Parent->getBasicBlock(),
+                                   BTB.Default->getBasicBlock()};
+    addMachineCFGPred(HeaderToDefaultEdge, BTB.Parent);
+    if (!BTB.ContiguousRange) {
+      addMachineCFGPred(HeaderToDefaultEdge, BTB.Cases.back().ThisBB);
+    }
+  }
+  SL->BitTestCases.clear();
+
   for (auto &JTCase : SL->JTCases) {
     // Emit header first, if it wasn't already emitted.
     if (!JTCase.first.Emitted)
       emitJumpTableHeader(JTCase.second, JTCase.first, JTCase.first.HeaderBB);
 
     emitJumpTable(JTCase.second, JTCase.second.MBB);
   }
   SL->JTCases.clear();

llvm/lib/CodeGen/GlobalISel/MachineIRBuilder.cpp

 
 MachineInstrBuilder MachineIRBuilder::buildFConstant(const DstOp &Res,
                                                      const APFloat &Val) {
   auto &Ctx = getMF().getFunction().getContext();
   auto *CFP = ConstantFP::get(Ctx, Val);
   return buildFConstant(Res, *CFP);
 }
 
-MachineInstrBuilder MachineIRBuilder::buildBrCond(Register Tst,
+MachineInstrBuilder MachineIRBuilder::buildBrCond(const SrcOp &Tst,
                                                   MachineBasicBlock &Dest) {
-  assert(getMRI()->getType(Tst).isScalar() && "invalid operand type");
+  assert(Tst.getLLTTy(*getMRI()).isScalar() && "invalid operand type");
 
-  return buildInstr(TargetOpcode::G_BRCOND).addUse(Tst).addMBB(&Dest);
+  auto MIB = buildInstr(TargetOpcode::G_BRCOND);
+  Tst.addSrcToMIB(MIB);
+  MIB.addMBB(&Dest);
+  return MIB;
 }
 
 MachineInstrBuilder
 MachineIRBuilder::buildLoad(const DstOp &Dst, const SrcOp &Addr,
                             MachinePointerInfo PtrInfo, Align Alignment,
                             MachineMemOperand::Flags MMOFlags,
                             const AAMDNodes &AAInfo) {
   MMOFlags |= MachineMemOperand::MOLoad;

llvm/test/CodeGen/AArch64/GlobalISel/irtranslator-switch-bittest.ll

+; NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+; RUN: llc -mtriple aarch64 -aarch64-enable-atomic-cfg-tidy=0 -stop-after=irtranslator -global-isel -verify-machineinstrs %s -o - 2>&1 | FileCheck %s
+
+define i32 @test_bittest(i16 %p) {
+  ; CHECK-LABEL: name: test_bittest
+  ; CHECK: bb.1 (%ir-block.0):
+  ; CHECK:   successors: %bb.4(0x40000000), %bb.5(0x40000000)
+  ; CHECK:   liveins: $w0
+  ; CHECK:   [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+  ; CHECK:   [[TRUNC:%[0-9]+]]:_(s16) = G_TRUNC [[COPY]](s32)
+  ; CHECK:   [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 114
+  ; CHECK:   [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 42
+  ; CHECK:   [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  ; CHECK:   [[ZEXT:%[0-9]+]]:_(s32) = G_ZEXT [[TRUNC]](s16)
+  ; CHECK:   [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  ; CHECK:   [[SUB:%[0-9]+]]:_(s32) = G_SUB [[ZEXT]], [[C3]]
+  ; CHECK:   [[ZEXT1:%[0-9]+]]:_(s64) = G_ZEXT [[SUB]](s32)
+  ; CHECK:   [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 59
+  ; CHECK:   [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(ugt), [[SUB]](s32), [[C4]]
+  ; CHECK:   G_BRCOND [[ICMP]](s1), %bb.4
+  ; CHECK:   G_BR %bb.5
+  ; CHECK: bb.4 (%ir-block.0):
+  ; CHECK:   successors: %bb.3(0x40000000), %bb.2(0x40000000)
+  ; CHECK:   [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), [[ZEXT]](s32), [[C]]
+  ; CHECK:   G_BRCOND [[ICMP1]](s1), %bb.3
+  ; CHECK:   G_BR %bb.2
+  ; CHECK: bb.5 (%ir-block.0):
+  ; CHECK:   successors: %bb.3(0x40000000), %bb.4(0x40000000)
+  ; CHECK:   [[C5:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+  ; CHECK:   [[SHL:%[0-9]+]]:_(s64) = G_SHL [[C5]], [[ZEXT1]](s64)
+  ; CHECK:   [[C6:%[0-9]+]]:_(s64) = G_CONSTANT i64 866239240827043840
+  ; CHECK:   [[AND:%[0-9]+]]:_(s64) = G_AND [[SHL]], [[C6]]
+  ; CHECK:   [[C7:%[0-9]+]]:_(s64) = G_CONSTANT i64 0
+  ; CHECK:   [[ICMP2:%[0-9]+]]:_(s1) = G_ICMP intpred(ne), [[AND]](s64), [[C7]]
+  ; CHECK:   G_BRCOND [[ICMP2]](s1), %bb.3
+  ; CHECK:   G_BR %bb.4
+  ; CHECK: bb.2.sw.epilog:
+  ; CHECK:   $w0 = COPY [[C2]](s32)
+  ; CHECK:   RET_ReallyLR implicit $w0
+  ; CHECK: bb.3.cb1:
+  ; CHECK:   $w0 = COPY [[C1]](s32)
+  ; CHECK:   RET_ReallyLR implicit $w0
+  switch i16 %p, label %sw.epilog [
+    i16 58, label %cb1
+    i16 59, label %cb1
+    i16 47, label %cb1
+    i16 48, label %cb1
+    i16 50, label %cb1
+    i16 114, label %cb1
+  ]
+sw.epilog:
+  ret i32 0
+
+cb1:
+  ret i32 42
+}
+
+
+declare void @callee()
+
+define void @test_bittest_2_bt(i32 %p) {
+  ; CHECK-LABEL: name: test_bittest_2_bt
+  ; CHECK: bb.1.entry:
+  ; CHECK:   successors: %bb.5(0x40000000), %bb.6(0x40000000)
+  ; CHECK:   liveins: $w0
+  ; CHECK:   [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+  ; CHECK:   [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 176
+  ; CHECK:   [[SUB:%[0-9]+]]:_(s32) = G_SUB [[COPY]], [[C]]
+  ; CHECK:   [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 15
+  ; CHECK:   [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(ugt), [[SUB]](s32), [[C1]]
+  ; CHECK:   G_BRCOND [[ICMP]](s1), %bb.5
+  ; CHECK:   G_BR %bb.6
+  ; CHECK: bb.5.entry:
+  ; CHECK:   successors: %bb.4(0x40000000), %bb.7(0x40000000)
+  ; CHECK:   [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  ; CHECK:   [[SUB1:%[0-9]+]]:_(s32) = G_SUB [[COPY]], [[C2]]
+  ; CHECK:   [[ZEXT:%[0-9]+]]:_(s64) = G_ZEXT [[SUB1]](s32)
+  ; CHECK:   [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 38
+  ; CHECK:   [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(ugt), [[SUB1]](s32), [[C3]]
+  ; CHECK:   G_BRCOND [[ICMP1]](s1), %bb.4
+  ; CHECK:   G_BR %bb.7
+  ; CHECK: bb.6.entry:
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.5(0x40000000)
+  ; CHECK:   [[C4:%[0-9]+]]:_(s32) = G_CONSTANT i32 1
+  ; CHECK:   [[SHL:%[0-9]+]]:_(s32) = G_SHL [[C4]], [[SUB]](s32)
+  ; CHECK:   [[C5:%[0-9]+]]:_(s32) = G_CONSTANT i32 57351
+  ; CHECK:   [[AND:%[0-9]+]]:_(s32) = G_AND [[SHL]], [[C5]]
+  ; CHECK:   [[C6:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  ; CHECK:   [[ICMP2:%[0-9]+]]:_(s1) = G_ICMP intpred(ne), [[AND]](s32), [[C6]]
+  ; CHECK:   G_BRCOND [[ICMP2]](s1), %bb.2
+  ; CHECK:   G_BR %bb.5
+  ; CHECK: bb.7.entry:
+  ; CHECK:   successors: %bb.3(0x40000000), %bb.4(0x40000000)
+  ; CHECK:   [[C7:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+  ; CHECK:   [[SHL1:%[0-9]+]]:_(s64) = G_SHL [[C7]], [[ZEXT]](s64)
+  ; CHECK:   [[C8:%[0-9]+]]:_(s64) = G_CONSTANT i64 365072220160
+  ; CHECK:   [[AND1:%[0-9]+]]:_(s64) = G_AND [[SHL1]], [[C8]]
+  ; CHECK:   [[C9:%[0-9]+]]:_(s64) = G_CONSTANT i64 0
+  ; CHECK:   [[ICMP3:%[0-9]+]]:_(s1) = G_ICMP intpred(ne), [[AND1]](s64), [[C9]]
+  ; CHECK:   G_BRCOND [[ICMP3]](s1), %bb.3
+  ; CHECK:   G_BR %bb.4
+  ; CHECK: bb.2.sw.bb37:
+  ; CHECK:   TCRETURNdi @callee, 0, csr_aarch64_aapcs, implicit $sp
+  ; CHECK: bb.3.sw.bb55:
+  ; CHECK:   TCRETURNdi @callee, 0, csr_aarch64_aapcs, implicit $sp
+  ; CHECK: bb.4.sw.default:
+  ; CHECK:   RET_ReallyLR
+entry:
+  switch i32 %p, label %sw.default [
+    i32 32, label %sw.bb55
+    i32 34, label %sw.bb55
+    i32 36, label %sw.bb55
+    i32 191, label %sw.bb37
+    i32 190, label %sw.bb37
+    i32 189, label %sw.bb37
+    i32 178, label %sw.bb37
+    i32 177, label %sw.bb37
+    i32 176, label %sw.bb37
+    i32 38, label %sw.bb55
+  ]
+
+sw.bb37:                                          ; preds = %entry, %entry, %entry, %entry, %entry, %entry
+  tail call void @callee()
+  ret void
+
+sw.bb55:                                          ; preds = %entry, %entry, %entry, %entry
+  tail call void @callee()
+  ret void
+
+sw.default:                                       ; preds = %entry
+  ret void
+}
+
+define i32 @test_bittest_single_bt_only_with_fallthrough(i16 %p) {
+  ; CHECK-LABEL: name: test_bittest_single_bt_only_with_fallthrough
+  ; CHECK: bb.1 (%ir-block.0):
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.4(0x40000000)
+  ; CHECK:   liveins: $w0
+  ; CHECK:   [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+  ; CHECK:   [[TRUNC:%[0-9]+]]:_(s16) = G_TRUNC [[COPY]](s32)
+  ; CHECK:   [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 42
+  ; CHECK:   [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  ; CHECK:   [[ZEXT:%[0-9]+]]:_(s32) = G_ZEXT [[TRUNC]](s16)
+  ; CHECK:   [[C2:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  ; CHECK:   [[SUB:%[0-9]+]]:_(s32) = G_SUB [[ZEXT]], [[C2]]
+  ; CHECK:   [[ZEXT1:%[0-9]+]]:_(s64) = G_ZEXT [[SUB]](s32)
+  ; CHECK:   [[C3:%[0-9]+]]:_(s32) = G_CONSTANT i32 59
+  ; CHECK:   [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(ugt), [[SUB]](s32), [[C3]]
+  ; CHECK:   G_BRCOND [[ICMP]](s1), %bb.2
+  ; CHECK: bb.4 (%ir-block.0):
+  ; CHECK:   successors: %bb.3(0x40000000), %bb.2(0x40000000)
+  ; CHECK:   [[C4:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+  ; CHECK:   [[SHL:%[0-9]+]]:_(s64) = G_SHL [[C4]], [[ZEXT1]](s64)
+  ; CHECK:   [[C5:%[0-9]+]]:_(s64) = G_CONSTANT i64 866239240827043840
+  ; CHECK:   [[AND:%[0-9]+]]:_(s64) = G_AND [[SHL]], [[C5]]
+  ; CHECK:   [[C6:%[0-9]+]]:_(s64) = G_CONSTANT i64 0
+  ; CHECK:   [[ICMP1:%[0-9]+]]:_(s1) = G_ICMP intpred(ne), [[AND]](s64), [[C6]]
+  ; CHECK:   G_BRCOND [[ICMP1]](s1), %bb.3
+  ; CHECK: bb.2.sw.epilog:
+  ; CHECK:   $w0 = COPY [[C1]](s32)
+  ; CHECK:   RET_ReallyLR implicit $w0
+  ; CHECK: bb.3.cb1:
+  ; CHECK:   $w0 = COPY [[C]](s32)
+  ; CHECK:   RET_ReallyLR implicit $w0
+  switch i16 %p, label %sw.epilog [
+    i16 58, label %cb1
+    i16 59, label %cb1
+    i16 47, label %cb1
+    i16 48, label %cb1
+    i16 50, label %cb1
+  ]
+sw.epilog:
+  ret i32 0
+
+cb1:
+  ret i32 42
+}