[ARM] Generate out-of-line jump tables for XO without 32-bit branch

[john.brawn]

Summary

When we only have a 16-bit pc-relative branch instruction we generate a table of address for a jump table. Currently this is placed inline, but this won't work with execute-only memory. In this case generate the jump table out-of-line.

[efriedma]

I'd prefer if the Thumb1 and Thumb2 codepaths work as close to the same way as possible; this looks significantly different. (Thumb2 execute-only has basically the same issues as Thumb1 execute-only, as far as I can tell; we only get away with "loading" from the text segment if we can form tbb/tbh.)

(Do we care about execute-only PIC?)

llvm/lib/Target/ARM/ARMISelLowering.cpp

3498

What relevant instructions does v8m.base have?

[john.brawn]

In D153774#4449785, @efriedma wrote:

I'd prefer if the Thumb1 and Thumb2 codepaths work as close to the same way as possible; this looks significantly different. (Thumb2 execute-only has basically the same issues as Thumb1 execute-only, as far as I can tell; we only get away with "loading" from the text segment if we can form tbb/tbh.)

The thumb1 and thumb2 handling of jump tables is already different, and the only difference of execute-only thumb1 from non-execute-only is the location of the jump table (inline vs out-of-line).

(Do we care about execute-only PIC?)

No.

llvm/lib/Target/ARM/ARMISelLowering.cpp

3498

t2B, the 32-bit direct branch instruction.

[efriedma]

Oh, I didn't remember JUMPTABLE_INSTS was a thing. This is making more sense now; Thumb2/armv8m.base defaults to jumping to a table of jumps, which works fine with execute-only, but Thumb1 (and apparently ARM-mode) loads offsets from a table instead, which doesn't work with execute-only. So to make Thumb1 work, you force the table to be emitted out-of-line.

That makes sense, but depending how much we care, there are probably better sequences. We can use "bl" as a 32-bit branch on Thumb1, like we do in other places. And we can then compress those 32-bit branches to 16-bit branches if the offsets aren't too big.

If you just care about getting it working, this is okay as-is. LGTM

llvm/lib/Target/ARM/ARMConstantIslandPass.cpp

 /// jumps to begin with. In almost all cases they'll never be moved from that
 /// position.
 void ARMConstantIslands::doInitialJumpTablePlacement(
     std::vector<MachineInstr *> &CPEMIs) {
   unsigned i = CPEntries.size();
   auto MJTI = MF->getJumpTableInfo();
   const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
 
+  // Only inline jump tables are placed in the function.
+  if (MJTI->getEntryKind() != MachineJumpTableInfo::EK_Inline)
+    return;
+
   MachineBasicBlock *LastCorrectlyNumberedBB = nullptr;
   for (MachineBasicBlock &MBB : *MF) {
     auto MI = MBB.getLastNonDebugInstr();
     // Look past potential SpeculationBarriers at end of BB.
     while (MI != MBB.end() &&
            (isSpeculationBarrierEndBBOpcode(MI->getOpcode()) ||
             MI->isDebugInstr()))
       --MI;
initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
   BBInfoVector &BBInfo = BBUtils->getBBInfo();
   // The known bits of the entry block offset are determined by the function
   // alignment.
   BBInfo.front().KnownBits = Log2(MF->getAlignment());
 
   // Compute block offsets and known bits.
   BBUtils->adjustBBOffsetsAfter(&MF->front());
 
+  // We only care about jump table instructions when jump tables are inline.
+  MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
+  bool InlineJumpTables =
+      MJTI && MJTI->getEntryKind() == MachineJumpTableInfo::EK_Inline;
+
   // Now go back through the instructions and build up our data structures.
   for (MachineBasicBlock &MBB : *MF) {
     // If this block doesn't fall through into the next MBB, then this is
     // 'water' that a constant pool island could be placed.
     if (!BBHasFallthrough(&MBB))
       WaterList.push_back(&MBB);
 
     for (MachineInstr &I : MBB) {
       if (I.isDebugInstr())
         continue;
 
       unsigned Opc = I.getOpcode();
       if (I.isBranch()) {
         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:
+          if (InlineJumpTables)
             T2JumpTables.push_back(&I);
           continue;   // Does not get an entry in ImmBranches
         case ARM::Bcc:
           isCond = true;
           UOpc = ARM::B;
           [[fallthrough]];
         case ARM::B:
           Bits = 24;
           Scale = 4;
for (MachineInstr &I : MBB) {
 
       if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS ||
           Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB ||
           Opc == ARM::JUMPTABLE_TBH)
         continue;
 
       // Scan the instructions for constant pool operands.
       for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op)
-        if (I.getOperand(op).isCPI() || I.getOperand(op).isJTI()) {
+        if (I.getOperand(op).isCPI() ||
+            (I.getOperand(op).isJTI() && InlineJumpTables)) {
           // We found one.  The addressing mode tells us the max displacement
           // from the PC that this instruction permits.
 
           // Basic size info comes from the TSFlags field.
           unsigned Bits = 0;
           unsigned Scale = 1;
           bool NegOk = false;
           bool IsSoImm = false;

llvm/lib/Target/ARM/ARMExpandPseudoInsts.cpp

 #include "ARMBaseRegisterInfo.h"
 #include "ARMConstantPoolValue.h"
 #include "ARMMachineFunctionInfo.h"
 #include "ARMSubtarget.h"
 #include "MCTargetDesc/ARMAddressingModes.h"
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "arm-pseudo"
 
 static cl::opt<bool>
case MachineOperand::MO_ExternalSymbol: {
     const char *ES = MO.getSymbolName();
     unsigned TF = MO.getTargetFlags();
     Upper8_15 = Upper8_15.addExternalSymbol(ES, TF | ARMII::MO_HI_8_15);
     Upper0_7 = Upper0_7.addExternalSymbol(ES, TF | ARMII::MO_HI_0_7);
     Lower8_15 = Lower8_15.addExternalSymbol(ES, TF | ARMII::MO_LO_8_15);
     Lower0_7 = Lower0_7.addExternalSymbol(ES, TF | ARMII::MO_LO_0_7);
     break;
   }
+  case MachineOperand::MO_JumpTableIndex: {
+    unsigned Idx = MO.getIndex();
+    unsigned TF = MO.getTargetFlags();
+    Upper8_15 = Upper8_15.addJumpTableIndex(Idx, TF | ARMII::MO_HI_8_15);
+    Upper0_7 = Upper0_7.addJumpTableIndex(Idx, TF | ARMII::MO_HI_0_7);
+    Lower8_15 = Lower8_15.addJumpTableIndex(Idx, TF | ARMII::MO_LO_8_15);
+    Lower0_7 = Lower0_7.addJumpTableIndex(Idx, TF | ARMII::MO_LO_0_7);
+    break;
+  }
   default: {
     const GlobalValue *GV = MO.getGlobal();
     unsigned TF = MO.getTargetFlags();
     Upper8_15 =
         Upper8_15.addGlobalAddress(GV, MO.getOffset(), TF | ARMII::MO_HI_8_15);
     Upper0_7 =
         Upper0_7.addGlobalAddress(GV, MO.getOffset(), TF | ARMII::MO_HI_0_7);
     Lower8_15 =
switch (Opcode) {
     case ARM::t2MOVCCi32imm:
       ExpandMOV32BitImm(MBB, MBBI);
       return true;
 
     case ARM::tMOVi32imm:
       ExpandTMOV32BitImm(MBB, MBBI);
       return true;
 
+    case ARM::tLEApcrelJT:
+      // Inline jump tables are handled in ARMAsmPrinter.
+      if (MI.getMF()->getJumpTableInfo()->getEntryKind() ==
+          MachineJumpTableInfo::EK_Inline)
+        return false;
+
+      // Use a 32-bit immediate move to generate the address of the jump table.
+      assert(STI->isThumb() && "Non-inline jump tables expected only in thumb");
+      ExpandTMOV32BitImm(MBB, MBBI);
+      return true;
+
     case ARM::SUBS_PC_LR: {
       MachineInstrBuilder MIB =
           BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(ARM::SUBri), ARM::PC)
               .addReg(ARM::LR)
               .add(MI.getOperand(0))
               .add(MI.getOperand(1))
               .add(MI.getOperand(2))
               .addReg(ARM::CPSR, RegState::Undef);

llvm/lib/Target/ARM/ARMISelLowering.cpp

if (CP->isMachineConstantPoolEntry())
     Res =
         DAG.getTargetConstantPool(CP->getMachineCPVal(), PtrVT, CPAlign);
   else
     Res = DAG.getTargetConstantPool(CP->getConstVal(), PtrVT, CPAlign);
   return DAG.getNode(ARMISD::Wrapper, dl, MVT::i32, Res);
 }
 
 unsigned ARMTargetLowering::getJumpTableEncoding() const {
+  // If we don't have a 32-bit pc-relative branch instruction then the jump
+  // table consists of block addresses. Usually this is inline, but for
+  // execute-only it must be placed out-of-line.
+  if (Subtarget->genExecuteOnly() && !Subtarget->hasV8MBaselineOps())
+    return MachineJumpTableInfo::EK_BlockAddress;
   return MachineJumpTableInfo::EK_Inline;
 }
 
 SDValue ARMTargetLowering::LowerBlockAddress(SDValue Op,
                                              SelectionDAG &DAG) const {
   MachineFunction &MF = DAG.getMachineFunction();
   ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
   unsigned ARMPCLabelIndex = 0;
   SDLoc DL(Op);
   EVT PtrVT = getPointerTy(DAG.getDataLayout());
   const BlockAddress *BA = cast<BlockAddressSDNode>(Op)->getBlockAddress();
   SDValue CPAddr;
   bool IsPositionIndependent = isPositionIndependent() || Subtarget->isROPI();
   if (!IsPositionIndependent) {
     CPAddr = DAG.getTargetConstantPool(BA, PtrVT, Align(4));

llvm/test/CodeGen/ARM/execute-only.ll

 ; CHECK-LABEL: .LJTI1_0:
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w
 
+; CHECK-T1-LABEL: jump_table:
+; CHECK-T1:      lsls [[REG_OFFSET:r[0-9]+]], {{r[0-9]+}}, #2
+; CHECK-T1-NEXT: movs [[REG_JT:r[0-9]+]], :upper8_15:.LJTI1_0
+; CHECK-T1-NEXT: lsls [[REG_JT]], [[REG_JT]], #8
+; CHECK-T1-NEXT: adds [[REG_JT]], :upper0_7:.LJTI1_0
+; CHECK-T1-NEXT: lsls [[REG_JT]], [[REG_JT]], #8
+; CHECK-T1-NEXT: adds [[REG_JT]], :lower8_15:.LJTI1_0
+; CHECK-T1-NEXT: lsls [[REG_JT]], [[REG_JT]], #8
+; CHECK-T1-NEXT: adds [[REG_JT]], :lower0_7:.LJTI1_0
+; CHECK-T1-NEXT: ldr  [[REG_ENTRY:r[0-9]+]], [[[REG_JT]], [[REG_OFFSET]]]
+; CHECK-T1-NEXT: mov  pc, [[REG_ENTRY]]
+; CHECK-T1:      .section .rodata,"a",%progbits
+; CHECK-T1-NEXT: .p2align 2, 0x0
+; CHECK-T1-NEXT: .LJTI1_0:
+; CHECK-T1-NEXT: .long
+; CHECK-T1-NEXT: .long
+; CHECK-T1-NEXT: .long
+; CHECK-T1-NEXT: .long
+; CHECK-T1-NEXT: .long
+; CHECK-T1-NEXT: .long
+
 entry:
   switch i32 %c, label %return [
     i32 1, label %sw.bb
     i32 2, label %sw.bb1
     i32 3, label %sw.bb3
     i32 4, label %sw.bb4
     i32 5, label %sw.bb6
     i32 6, label %sw.bb8