[Thumb-1] Synthesize TBB/TBH instructions to make use of compressed jump tables

[jmolloy]

Summary

The TBB and TBH instructions in Thumb-2 allow jump tables to be compressed into sequences of bytes or shorts respectively. These instructions do not exist in Thumb-1, however it is possible to synthesize them out of a sequence of other instructions.

It turns out this sequence is so short that it's almost never a lose for performance and is ALWAYS a significant win for code size.

TBB example:

Before: lsls r0, r0, #2    After: add  r0, pc
        adr  r1, .LJTI0_0         ldrb r0, [r0, #6]
        ldr  r0, [r0, r1]         lsls r0, r0, #1
        mov  pc, r0               add  pc, r0
  => No change in prologue code size or dynamic instruction count. Jump table shrunk by a factor of 4.

The only case that can increase dynamic instruction count is the TBH case:

Before: lsls r0, r4, #2    After: lsls r4, r4, #1
        adr  r1, .LJTI0_0         add  r4, pc
        ldr  r0, [r0, r1]         ldrh r4, [r4, #6]
        mov  pc, r0               lsls r4, r4, #1
                                  add  pc, r4
=> 1 more instruction in prologue. Jump table shrunk by a factor of 2.

So there is an argument that this should be disabled when optimizing for performance (and a TBH needs to be generated). I'm not so sure about that in practice, because on small cores with Thumb-1 performance is often tied to code size. But I'm willing to turn it off when optimizing for performance if people want (also note that TBHs are fairly rare in practice!)

[rengolin]

Hi James,

Interesting idea! Though, the change is smaller than I was expecting. :)

I haven't looked in great detail, but here are some nits and questions to get you busy while I look at the rest. :)

cheers,
--renato

lib/Target/ARM/ARMConstantIslandPass.cpp

1987

rename?

lib/Target/ARM/ARMInstrThumb.td

1318

Why t2Pseudo?

test/CodeGen/ARM/jump-table-tbh.ll

30

I'm worried about the label naming here... Could it change later on?

The only test you really need here is that the first item is the same as the last. Maybe.

[jmolloy]

Thanks Renato! Nice catch on the t2Pseudo - that was a copy-paste error.

Cheers,

James

[rengolin]

Hi James,

The code looks good to me, and I think the idea is a good one, including performance of Thumb1 cores.

LGTM. Thanks!

lib/Target/ARM/ARMAsmPrinter.cpp

1774

Changing the table format/alignment looks like a code-size optimisation, so can be done later.

[jmolloy]

Thanks Renato, committed in r284580!

lib/Target/ARM/ARMAsmPrinter.cpp

     EmitToStreamer(*OutStreamer, MCInstBuilder(Opc)
                                      .addReg(MI->getOperand(0).getReg())
                                      .addReg(MI->getOperand(1).getReg())
                                      // Add predicate operands.
                                      .addImm(ARMCC::AL)
                                      .addReg(0));
     return;
   }
+  case ARM::tTBB_JT:
+  case ARM::tTBH_JT: {
+
+    bool Is8Bit = MI->getOpcode() == ARM::tTBB_JT;
+    unsigned Base = MI->getOperand(0).getReg();
+    unsigned Idx = MI->getOperand(1).getReg();
+    assert(MI->getOperand(1).isKill() && "We need the index register as scratch!");
+
+    // Multiply up idx if necessary.
+    if (!Is8Bit)
+      EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::tLSLri)
+                                       .addReg(Idx)
+                                       .addReg(ARM::CPSR)
+                                       .addReg(Idx)
+                                       .addImm(1)
+                                       // Add predicate operands.
+                                       .addImm(ARMCC::AL)
+                                       .addReg(0));
+
+    if (Base == ARM::PC) {
+      // TBB [base, idx] =
+      //    ADDS base, idx, base
+      //    LDRB idx, [idx, #4] ; or LDRH if TBH
+      //    LSLS idx, #1
+      //    ADDS pc, pc, idx
+
+      EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::tADDhirr)
+                                       .addReg(Idx)
+                                       .addReg(Idx)
+                                       .addReg(Base)
+                                       // Add predicate operands.
+                                       .addImm(ARMCC::AL)
+                                       .addReg(0));
+
+      unsigned Opc = Is8Bit ? ARM::tLDRBi : ARM::tLDRHi;
+      EmitToStreamer(*OutStreamer, MCInstBuilder(Opc)
+                                       .addReg(Idx)
+                                       .addReg(Idx)
+                                       .addImm(Is8Bit ? 6 : 3)
+                                       // Add predicate operands.
+                                       .addImm(ARMCC::AL)
+                                       .addReg(0));
+    } else {
+      // TBB [base, idx] =
+      //    LDRB idx, [base, idx] ; or LDRH if TBH
+      //    LSLS idx, #1
+      //    ADDS pc, pc, idx
+
+      unsigned Opc = Is8Bit ? ARM::tLDRBr : ARM::tLDRHr;
+      EmitToStreamer(*OutStreamer, MCInstBuilder(Opc)
+                                       .addReg(Idx)
+                                       .addReg(Base)
+                                       .addReg(Idx)
+                                       // Add predicate operands.
+                                       .addImm(ARMCC::AL)
+                                       .addReg(0));
+    }
+
+    // Lower and emit the PC label here. We reuse the table format from TBB/TBH
+    // which requires a 4-byte PC adjustment due to the size of t2TBB. We *could*
+    // make a new table format that only requires a 2-byte adjustment, or we
+    // could more simply just emit the label 2 bytes earlier. We take the easy
+    // option.
+    OutStreamer->EmitLabel(GetCPISymbol(MI->getOperand(3).getImm()));
+    
+    EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::tLSLri)
+                                     .addReg(Idx)
+                                     .addReg(ARM::CPSR)
+                                     .addReg(Idx)
+                                     .addImm(1)
+                                     // Add predicate operands.
+                                     .addImm(ARMCC::AL)
+                                     .addReg(0));
+
+    EmitToStreamer(*OutStreamer, MCInstBuilder(ARM::tADDhirr)
+                                     .addReg(ARM::PC)
+                                     .addReg(ARM::PC)
+                                     .addReg(Idx)
+                                     // Add predicate operands.
+                                     .addImm(ARMCC::AL)
+                                     .addReg(0));
+    return;
+  }
   case ARM::tBR_JTr:
   case ARM::BR_JTr: {
     // Lower and emit the instruction itself, then the jump table following it.
     // mov pc, target
     MCInst TmpInst;
     unsigned Opc = MI->getOpcode() == ARM::BR_JTr ?
       ARM::MOVr : ARM::tMOVr;
     TmpInst.setOpcode(Opc);

lib/Target/ARM/ARMConstantIslandPass.cpp

 static cl::opt<bool>
 AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true),
           cl::desc("Adjust basic block layout to better use TB[BH]"));
 
 static cl::opt<unsigned>
 CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30),
           cl::desc("The max number of iteration for converge"));
 
+static cl::opt<bool> SynthesizeThumb1TBB(
+    "arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true),
+    cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an "
+             "equivalent to the TBB/TBH instructions"));
+
 namespace {
   /// ARMConstantIslands - Due to limited PC-relative displacements, ARM
   /// requires constant pool entries to be scattered among the instructions
   /// inside a function.  To do this, it completely ignores the normal LLVM
   /// constant pool; instead, it places constants wherever it feels like with
   /// special instructions.
   ///
   /// The terminology used in this pass includes:
class ARMConstantIslands : public MachineFunctionPass {
     MachineFunction *MF;
     MachineConstantPool *MCP;
     const ARMBaseInstrInfo *TII;
     const ARMSubtarget *STI;
     ARMFunctionInfo *AFI;
     bool isThumb;
     bool isThumb1;
     bool isThumb2;
+    bool isPositionIndependentOrROPI;
   public:
     static char ID;
     ARMConstantIslands() : MachineFunctionPass(ID) {}
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     MachineFunctionProperties getRequiredProperties() const override {
       return MachineFunctionProperties().set(
bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {
   MCP = mf.getConstantPool();
 
   DEBUG(dbgs() << "***** ARMConstantIslands: "
                << MCP->getConstants().size() << " CP entries, aligned to "
                << MCP->getConstantPoolAlignment() << " bytes *****\n");
 
   STI = &static_cast<const ARMSubtarget &>(MF->getSubtarget());
   TII = STI->getInstrInfo();
+  isPositionIndependentOrROPI =
+      STI->getTargetLowering()->isPositionIndependent() || STI->isROPI();
   AFI = MF->getInfo<ARMFunctionInfo>();
 
   isThumb = AFI->isThumbFunction();
   isThumb1 = AFI->isThumb1OnlyFunction();
   isThumb2 = AFI->isThumb2Function();
 
   HasFarJump = false;
+  bool GenerateTBB = isThumb2 || (isThumb1 && SynthesizeThumb1TBB);
 
   // This pass invalidates liveness information when it splits basic blocks.
   MF->getRegInfo().invalidateLiveness();
 
   // Renumber all of the machine basic blocks in the function, guaranteeing that
   // the numbers agree with the position of the block in the function.
   MF->RenumberBlocks();
 
   // Try to reorder and otherwise adjust the block layout to make good use
   // of the TB[BH] instructions.
   bool MadeChange = false;
-  if (isThumb2 && AdjustJumpTableBlocks) {
+  if (GenerateTBB && AdjustJumpTableBlocks) {
     scanFunctionJumpTables();
     MadeChange |= reorderThumb2JumpTables();
     // Data is out of date, so clear it. It'll be re-computed later.
     T2JumpTables.clear();
     // Blocks may have shifted around. Keep the numbering up to date.
     MF->RenumberBlocks();
   }
 
bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {
   if (isThumb2 && !STI->prefers32BitThumb())
     MadeChange |= optimizeThumb2Instructions();
 
   // Shrink 32-bit branch instructions.
   if (isThumb && STI->hasV8MBaselineOps())
     MadeChange |= optimizeThumb2Branches();
 
   // Optimize jump tables using TBB / TBH.
-  if (isThumb2)
+  if (GenerateTBB)
     MadeChange |= optimizeThumb2JumpTables();
 
   // After a while, this might be made debug-only, but it is not expensive.
   verify();
 
   // If LR has been forced spilled and no far jump (i.e. BL) has been issued,
   // undo the spill / restore of LR if possible.
   if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump())
for (MachineBasicBlock &MBB : *MF) {
     case ARM::BR_JTr:
     case ARM::tBR_JTr:
     case ARM::BR_JTm:
       JTOpcode = ARM::JUMPTABLE_ADDRS;
       break;
     case ARM::t2BR_JT:
       JTOpcode = ARM::JUMPTABLE_INSTS;
       break;
+    case ARM::tTBB_JT:
     case ARM::t2TBB_JT:
       JTOpcode = ARM::JUMPTABLE_TBB;
       break;
+    case ARM::tTBH_JT:
     case ARM::t2TBH_JT:
       JTOpcode = ARM::JUMPTABLE_TBH;
       break;
     }
 
     unsigned NumOps = MI->getDesc().getNumOperands();
     MachineOperand JTOp =
       MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1));

 }
 
 /// scanFunctionJumpTables - Do a scan of the function, building up
 /// information about the sizes of each block and the locations of all
 /// the jump tables.
 void ARMConstantIslands::scanFunctionJumpTables() {
   for (MachineBasicBlock &MBB : *MF) {
     for (MachineInstr &I : MBB)
-      if (I.isBranch() && I.getOpcode() == ARM::t2BR_JT)
+      if (I.isBranch() &&
+          (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr))
         T2JumpTables.push_back(&I);
   }
 }
 
 /// initializeFunctionInfo - Do the initial scan of the function, building up
 /// information about the sizes of each block, the location of all the water,
 /// and finding all of the constant pool users.
 void ARMConstantIslands::
for (MachineInstr &I : MBB) {
         bool isCond = false;
         unsigned Bits = 0;
         unsigned Scale = 1;
         int UOpc = Opc;
         switch (Opc) {
         default:
           continue;  // Ignore other JT branches
         case ARM::t2BR_JT:
+        case ARM::tBR_JTr:
           T2JumpTables.push_back(&I);
           continue;   // Does not get an entry in ImmBranches
         case ARM::Bcc:
           isCond = true;
           UOpc = ARM::B;
           LLVM_FALLTHROUGH;
         case ARM::B:
           Bits = 24;
for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) {
         return false;
       if (MO.isUse() && MO.getReg() == EntryReg)
         RemovableAdd = nullptr;
     }
   }
 
   if (RemovableAdd) {
     RemovableAdd->eraseFromParent();
-    DeadSize += 4;
+    DeadSize += isThumb2 ? 4 : 2;
   } else if (BaseReg == EntryReg) {
     // The add wasn't removable, but clobbered the base for the TBB. So we can't
     // preserve it.
     return false;
   }
 
   // We reached the end of the block without seeing another definition of
   // BaseReg (except, possibly the t2ADDrs, which was removed). BaseReg can be
static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI) {
   ++MBB;
 
   return MBB != MF->end() && MBB->begin() != MBB->end() &&
          &*MBB->begin() == CPEMI;
 }
 
 /// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller
 /// jumptables when it's possible.
 bool ARMConstantIslands::optimizeThumb2JumpTables() {
   bool MadeChange = false;
 
   // FIXME: After the tables are shrunk, can we get rid some of the
   // constantpool tables?
   MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
   if (!MJTI) return false;
 
   const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) {
         HalfWordOk = false;
       if (!ByteOk && !HalfWordOk)
         break;
     }
 
     if (!ByteOk && !HalfWordOk)
       continue;
 
+    CPUser &User = CPUsers[JumpTableUserIndices[JTI]];
     MachineBasicBlock *MBB = MI->getParent();
     if (!MI->getOperand(0).isKill()) // FIXME: needed now?
       continue;
-    unsigned IdxReg = MI->getOperand(1).getReg();
-    bool IdxRegKill = MI->getOperand(1).isKill();
 
-    CPUser &User = CPUsers[JumpTableUserIndices[JTI]];
     unsigned DeadSize = 0;
     bool CanDeleteLEA = false;
     bool BaseRegKill = false;
+    
+    unsigned IdxReg = ~0U;
+    bool IdxRegKill = true;
+    if (isThumb2) {
+      IdxReg = MI->getOperand(1).getReg();
+      IdxRegKill = MI->getOperand(1).isKill();
+
       bool PreservedBaseReg =
         preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);
-
       if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg)
         continue;
+    } else {
+      // We're in thumb-1 mode, so we must have something like:
+      //   %idx = tLSLri %idx, 2
+      //   %base = tLEApcrelJT
+      //   %t = tLDRr %idx, %base
+      unsigned BaseReg = User.MI->getOperand(0).getReg();
+      
+      MachineInstr *Shift = User.MI->getPrevNode();
+      if (Shift->getOpcode() != ARM::tLSLri ||
+          Shift->getOperand(3).getImm() != 2 ||
+          !Shift->getOperand(2).isKill())
+        continue;
+      IdxReg = Shift->getOperand(2).getReg();
+      unsigned ShiftedIdxReg = Shift->getOperand(0).getReg();
+
+      MachineInstr *Load = User.MI->getNextNode();
+      if (Load->getOpcode() != ARM::tLDRr)
+        continue;
+      if (Load->getOperand(1).getReg() != ShiftedIdxReg ||
+          Load->getOperand(2).getReg() != BaseReg ||
+          !Load->getOperand(1).isKill())
+        continue;
+
+      // If we're in PIC mode, there should be another ADD following.
+      if (isPositionIndependentOrROPI) {
+        MachineInstr *Add = Load->getNextNode();
+        if (Add->getOpcode() != ARM::tADDrr ||
+            Add->getOperand(2).getReg() != Load->getOperand(0).getReg() ||
+            Add->getOperand(3).getReg() != BaseReg ||
+            !Add->getOperand(2).isKill())
+          continue;
+        if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())
+          continue;
+
+        Add->eraseFromParent();
+        DeadSize += 2;
+      } else {
+        if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg())
+          continue;
+      }
+      
+      
+      // Now safe to delete the load and lsl. The LEA will be removed later.
+      CanDeleteLEA = true;
+      Shift->eraseFromParent();
+      Load->eraseFromParent();
+      DeadSize += 4;
+    }
     
     DEBUG(dbgs() << "Shrink JT: " << *MI);
     MachineInstr *CPEMI = User.CPEMI;
     unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;
+    if (!isThumb2)
+      Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;
+
     MachineBasicBlock::iterator MI_JT = MI;
     MachineInstr *NewJTMI =
         BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc))
             .addReg(User.MI->getOperand(0).getReg(),
                     getKillRegState(BaseRegKill))
             .addReg(IdxReg, getKillRegState(IdxRegKill))
             .addJumpTableIndex(JTI, JTOP.getTargetFlags())
             .addImm(CPEMI->getOperand(0).getImm());
     DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": " << *NewJTMI);
 
     unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;
     CPEMI->setDesc(TII->get(JTOpc));
 
     if (jumpTableFollowsTB(MI, User.CPEMI)) {
       NewJTMI->getOperand(0).setReg(ARM::PC);
       NewJTMI->getOperand(0).setIsKill(false);
 
       if (CanDeleteLEA)  {
         User.MI->eraseFromParent();
-        DeadSize += 4;
+        DeadSize += isThumb2 ? 4 : 2;
 
         // The LEA was eliminated, the TBB instruction becomes the only new user
         // of the jump table.
         User.MI = NewJTMI;
         User.MaxDisp = 4;
         User.NegOk = false;
         User.IsSoImm = false;
         User.KnownAlignment = false;
adjustJTTargetBlockForward(MachineBasicBlock *BB, MachineBasicBlock *JTBB) {
   MachineBasicBlock *NewBB =
     MF->CreateMachineBasicBlock(JTBB->getBasicBlock());
   MachineFunction::iterator MBBI = ++JTBB->getIterator();
   MF->insert(MBBI, NewBB);
 
   // Add an unconditional branch from NewBB to BB.
   // There doesn't seem to be meaningful DebugInfo available; this doesn't
   // correspond directly to anything in the source.
-  assert (isThumb2 && "Adjusting for TB[BH] but not in Thumb2?");
-  BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B)).addMBB(BB)
-          .addImm(ARMCC::AL).addReg(0);
+  if (isThumb2)
+    BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B))
+        .addMBB(BB)
+        .addImm(ARMCC::AL)
+        .addReg(0);
+  else
+    BuildMI(NewBB, DebugLoc(), TII->get(ARM::tB))
+        .addMBB(BB)
+        .addImm(ARMCC::AL)
+        .addReg(0);
 
   // Update internal data structures to account for the newly inserted MBB.
   MF->RenumberBlocks(NewBB);
 
   // Update the CFG.
   NewBB->addSuccessor(BB);
   JTBB->replaceSuccessor(BB, NewBB);
 
   ++NumJTInserted;
   return NewBB;
 }

lib/Target/ARM/ARMInstrThumb.td

 def tLEApcrel   : tPseudoInst<(outs tGPR:$Rd), (ins i32imm:$label, pred:$p),
                               2, IIC_iALUi, []>, Sched<[WriteALU]>;
 
 let hasSideEffects = 1 in
 def tLEApcrelJT : tPseudoInst<(outs tGPR:$Rd),
                               (ins i32imm:$label, pred:$p),
                               2, IIC_iALUi, []>, Sched<[WriteALU]>;
 
+// Thumb-1 doesn't have the TBB or TBH instructions, but we can synthesize them
+// and make use of the same compressed jump table format as Thumb-2.
+let Size = 2 in {
+def tTBB_JT : tPseudoInst<(outs),
+        (ins tGPR:$base, tGPR:$index, i32imm:$jt, i32imm:$pclbl), 0, IIC_Br, []>,
+        Sched<[WriteBr]>;
+
+def tTBH_JT : tPseudoInst<(outs),
+        (ins tGPR:$base, tGPR:$index, i32imm:$jt, i32imm:$pclbl), 0, IIC_Br, []>,
+        Sched<[WriteBr]>;
+}
+
 //===----------------------------------------------------------------------===//
 // TLS Instructions
 //
 
 // __aeabi_read_tp preserves the registers r1-r3.
 // This is a pseudo inst so that we can get the encoding right,
 // complete with fixup for the aeabi_read_tp function.
 let isCall = 1, Defs = [R0, R12, LR, CPSR], Uses = [SP] in

test/CodeGen/ARM/arm-position-independence-jump-table.ll

 ; Test for generation of jump table for ropi/rwpi
 
 ; RUN: llc -relocation-model=static    -mtriple=armv7a--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ARM --check-prefix=ARM_ABS
 ; RUN: llc -relocation-model=ropi      -mtriple=armv7a--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ARM --check-prefix=ARM_PC
 ; RUN: llc -relocation-model=ropi-rwpi -mtriple=armv7a--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ARM --check-prefix=ARM_PC
 
 ; RUN: llc -relocation-model=static    -mtriple=thumbv7m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB2
 ; RUN: llc -relocation-model=ropi      -mtriple=thumbv7m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB2
 ; RUN: llc -relocation-model=ropi-rwpi -mtriple=thumbv7m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB2
 
-; RUN: llc -relocation-model=static    -mtriple=thumbv6m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB1 --check-prefix=THUMB1_ABS
-; RUN: llc -relocation-model=ropi      -mtriple=thumbv6m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB1 --check-prefix=THUMB1_PC
-; RUN: llc -relocation-model=ropi-rwpi -mtriple=thumbv6m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB1 --check-prefix=THUMB1_PC
+; RUN: llc -relocation-model=static    -mtriple=thumbv6m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB1
+; RUN: llc -relocation-model=ropi      -mtriple=thumbv6m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB1
+; RUN: llc -relocation-model=ropi-rwpi -mtriple=thumbv6m--none-eabi -disable-block-placement < %s | FileCheck %s --check-prefix=CHECK --check-prefix=THUMB1
 
 
 declare void @exit0()
 declare void @exit1()
 declare void @exit2()
 declare void @exit3()
 declare void @exit4()
 define void @jump_table(i32 %val) {

 ; THUMB2-NEXT: b exit1
 ; THUMB2: [[LBB2]]
 ; THUMB2-NEXT: b exit2
 ; THUMB2: [[LBB3]]
 ; THUMB2-NEXT: b exit3
 ; THUMB2: [[LBB4]]
 ; THUMB2-NEXT: b exit4
 
-; THUMB1: lsls    r[[R_TAB_INDEX:[0-9]+]], r{{[0-9]+}}, #2 
-; THUMB1: adr     r[[R_TAB_BASE:[0-9]+]], [[LJTI:\.LJTI[0-9]+_[0-9]+]]
-; THUMB1: ldr     r[[R_BB_ADDR:[0-9]+]], [r[[R_TAB_INDEX]], r[[R_TAB_BASE]]]
-; THUMB1_PC: adds    r[[R_BB_ADDR]], r[[R_BB_ADDR]], r[[R_TAB_BASE]]
-; THUMB1: mov     pc, r[[R_BB_ADDR]]
-; THUMB1: [[LJTI]]
-; THUMB1_ABS: .long [[LBB1:\.LBB[0-9]+_[0-9]+]]+1
-; THUMB1_ABS: .long [[LBB2:\.LBB[0-9]+_[0-9]+]]+1
-; THUMB1_ABS: .long [[LBB3:\.LBB[0-9]+_[0-9]+]]+1
-; THUMB1_ABS: .long [[LBB4:\.LBB[0-9]+_[0-9]+]]+1
-; THUMB1_PC:  .long [[LBB1:\.LBB[0-9]+_[0-9]+]]-[[LJTI]]
-; THUMB1_PC:  .long [[LBB2:\.LBB[0-9]+_[0-9]+]]-[[LJTI]]
-; THUMB1_PC:  .long [[LBB3:\.LBB[0-9]+_[0-9]+]]-[[LJTI]]
-; THUMB1_PC:  .long [[LBB4:\.LBB[0-9]+_[0-9]+]]-[[LJTI]]
+
+; THUMB1: add     r[[x:[0-9]+]], pc
+; THUMB1: ldrb    r[[x]], [r[[x]], #6] 
+; THUMB1: [[LCPI:\.LCPI[0-9]+_[0-9]+]]:
+; THUMB1: lsls    r[[x]], r[[x]], #1
+; THUMB1: add     pc, r[[x]]
+; THUMB1: .byte   ([[LBB1:\.LBB[0-9]+_[0-9]+]]-([[LCPI]]+4))/2
+; THUMB1: .byte   ([[LBB2:\.LBB[0-9]+_[0-9]+]]-([[LCPI]]+4))/2
+; THUMB1: .byte   ([[LBB3:\.LBB[0-9]+_[0-9]+]]-([[LCPI]]+4))/2
+; THUMB1: .byte   ([[LBB4:\.LBB[0-9]+_[0-9]+]]-([[LCPI]]+4))/2
 ; THUMB1: [[LBB1]]
 ; THUMB1-NEXT: bl exit1
-; THUMB1-NEXT: pop
 ; THUMB1: [[LBB2]]
 ; THUMB1-NEXT: bl exit2
-; THUMB1-NEXT: pop
 ; THUMB1: [[LBB3]]
 ; THUMB1-NEXT: bl exit3
-; THUMB1-NEXT: pop
 ; THUMB1: [[LBB4]]
 ; THUMB1-NEXT: bl exit4
-; THUMB1-NEXT: pop
 }

test/CodeGen/ARM/jump-table-tbh.ll

+; RUN: llc -mtriple=thumbv7m-linux-gnu -o - %s | FileCheck %s --check-prefix=T2
+; RUN: llc -mtriple=thumbv6m-linux-gnu -o - %s | FileCheck %s --check-prefix=T1
+
+declare void @foo(double)
+declare i32 @llvm.arm.space(i32, i32)
+
+define i32 @test_tbh(i1 %tst, i32 %sw, i32 %l) {
+  br label %complex
+
+; T2-LABEL: test_tbh:
+; T2: [[ANCHOR:.LCPI[0-9_]+]]:
+; T2: tbh [pc, r{{[0-9]+}}, lsl #1]
+; T2-NEXT: @ BB#1
+; T2-NEXT: LJTI
+; T2-NEXT: .short (.LBB0_[[x:[0-9]+]]-([[ANCHOR]]+4))/2
+; T2-NEXT: .short (.LBB0_{{[0-9]+}}-([[ANCHOR]]+4))/2
+; T2-NEXT: .short (.LBB0_{{[0-9]+}}-([[ANCHOR]]+4))/2
+; T2-NEXT: .short (.LBB0_[[x]]-([[ANCHOR]]+4))/2
+
+; T1-LABEL: test_tbh:
+; T1: lsls [[x:r[0-9]+]], r4, #1
+; T1: add [[x]], pc
+; T1: ldrh [[x]], {{\[}}[[x]], #6]
+; T1: [[ANCHOR:.LCPI[0-9_]+]]:
+; T1: lsls [[x]], [[x]], #1
+; T1: add pc, [[x]]
+; T1-NEXT: @ BB#2
+; T1-NEXT: LJTI
+; T1-NEXT: .short (.LBB0_[[x:[0-9]+]]-([[ANCHOR]]+4))/2
+; T1-NEXT: .short (.LBB0_{{[0-9]+}}-([[ANCHOR]]+4))/2
+; T1-NEXT: .short (.LBB0_{{[0-9]+}}-([[ANCHOR]]+4))/2
+; T1-NEXT: .short (.LBB0_[[x]]-([[ANCHOR]]+4))/2
+
+complex:
+  call void @foo(double 12345.0)
+  switch i32 %sw, label %second [ i32 0, label %other
+                                  i32 1, label %third
+                                  i32 2, label %end
+                                  i32 3, label %other ]
+
+second:
+  ret i32 43
+third:
+  call i32 @llvm.arm.space(i32 970, i32 undef)
+  ret i32 0
+
+other:
+  call void @bar()
+  unreachable
+
+end:
+  ret i32 42
+}
+
+declare void @bar()

test/CodeGen/Thumb2/thumb2-jtb.ll

 ; RUN: llc -mtriple=thumb-eabi -mcpu=arm1156t2-s -mattr=+thumb2 -arm-adjust-jump-tables=0 %s -o - | FileCheck %s
+; RUN: llc -mtriple=thumbv6-eabi -mcpu=cortex-m0 -arm-adjust-jump-tables=0 %s -o - | FileCheck %s
 
 ; Do not use tbb / tbh if any destination is before the jumptable.
 ; rdar://7102917
 
 define i16 @main__getopt_internal_2E_exit_2E_ce(i32, i1 %b) nounwind {
 ; CHECK: main__getopt_internal_2E_exit_2E_ce
 ; CHECK-NOT: tbb
 ; CHECK-NOT: tbh

test/CodeGen/Thumb2/thumb2-tbb.ll

 ; RUN: llc < %s -mtriple=thumbv7-apple-darwin | FileCheck %s
 ; RUN: llc < %s -mtriple=thumbv7-apple-darwin -relocation-model=pic | FileCheck %s
+; RUN: llc < %s -mtriple=thumbv6m-apple-darwin -relocation-model=static | FileCheck %s --check-prefix=THUMB1
+; RUN: llc < %s -mtriple=thumbv6m-apple-darwin -relocation-model=pic | FileCheck %s --check-prefix=THUMB1
 
 define void @bar(i32 %n.u) {
 entry:
 ; CHECK-LABEL: bar:
 ; CHECK: tbb
 ; CHECK: .data_region jt8
 ; CHECK: .end_data_region
 ; CHECK-NEXT: .p2align 1
 
+; THUMB1-LABEL: bar:
+; THUMB1: add pc, r0
+; THUMB1: .data_region jt8
+; THUMB1: .byte (LBB0_3-(LCPI0_0+4))/2
+; THUMB1: .end_data_region
+; THUMB1-NEXT: .p2align 1
+
     switch i32 %n.u, label %bb12 [i32 1, label %bb i32 2, label %bb6 i32 4, label %bb7 i32 5, label %bb8 i32 6, label %bb10 i32 7, label %bb1 i32 8, label %bb3 i32 9, label %bb4 i32 10, label %bb9 i32 11, label %bb2 i32 12, label %bb5 i32 13, label %bb11 ]
 bb:
     tail call void(...) @foo1()
     ret void
 bb1:
     tail call void(...) @foo2()
     ret void
 bb2:

test/CodeGen/Thumb2/thumb2-tbh.ll

-; RUN: llc < %s -mtriple=thumbv7-apple-darwin -relocation-model=pic | FileCheck %s
+; RUN: llc < %s -mtriple=thumbv7-apple-darwin -relocation-model=pic | FileCheck %s --check-prefix=CHECK --check-prefix=T2
+; RUN: llc < %s -mtriple=thumbv6m-apple-darwin -relocation-model=pic | FileCheck %s --check-prefix=CHECK --check-prefix=T1
+; RUN: llc < %s -mtriple=thumbv6m-apple-darwin -relocation-model=static | FileCheck %s --check-prefix=CHECK --check-prefix=T1
 
 ; Thumb2 target should reorder the bb's in order to use tbb / tbh.
 
   %struct.R_flstr = type { i32, i32, i8* }
   %struct._T_tstr = type { i32, %struct.R_flstr*, %struct._T_tstr* }
 @_C_nextcmd = external global i32   ; <i32*> [#uses=3]
 @.str31 = external constant [28 x i8], align 1    ; <[28 x i8]*> [#uses=1]
 @_T_gtol = external global %struct._T_tstr*   ; <%struct._T_tstr**> [#uses=2]
 
 declare i32 @strlen(i8* nocapture) nounwind readonly
 
 declare void @Z_fatal(i8*) noreturn nounwind
 
 declare noalias i8* @calloc(i32, i32) nounwind
 
 ; Jump tables are not anchored next to the TBB/TBH any more. Make sure the
 ; correct address is still calculated (i.e. via a PC-relative symbol *at* the
 ; TBB/TBH).
 define i32 @main(i32 %argc, i8** nocapture %argv) nounwind {
 ; CHECK-LABEL: main:
 ; CHECK-NOT: adr {{r[0-9]+}}, LJTI
 ; CHECK: [[PCREL_ANCHOR:LCPI[0-9]+_[0-9]+]]:
-; CHECK-NEXT:     tbb [pc, {{r[0-9]+}}]
+; T2-NEXT:     tbb [pc, {{r[0-9]+}}]
+; T1-NEXT:     lsls r[[x:[0-9]+]], {{r[0-9]+}}, #1
+; T1-NEXT:     add  pc, r[[x]]
 
 ; CHECK: LJTI0_0:
 ; CHECK-NEXT: .data_region jt8
 ; CHECK-NEXT: .byte (LBB{{[0-9]+_[0-9]+}}-([[PCREL_ANCHOR]]+4))/2
 
 entry:
   br label %bb42.i