[ARM] Place jump table as the first operand in additions

[chill]

Summary

When generating table jump code for switch statements, place the jump
table label as the first operand in the various addition instructions in
order to enable addressing mode selectors to better match index
computation and possibly fold them into the addressing mode of the table
entry load instruction.

[efriedma]

I understand what you're trying to do with the changes to ARMISelLowering.cpp make sense, but I'm surprised our address-matching code doesn't try to commute the operands. Do we really not have code to do that somwhere?

I'm not sure what the change to ARMAsmPrinter.cpp is supposed to do; is it buggy, and nobody noticed because it never triggers?

I guess the change to ARMConstantIslandPass.cpp is just to match the new pattern we generate in Thumb1 mode?

Would this code be less confusing if we address the FIXME in ARMInstrInfo.td about using "addrmode2" in BR_JTm?

[chill]

In D39752#918295, @efriedma wrote:

I understand what you're trying to do with the changes to ARMISelLowering.cpp make sense, but I'm surprised our address-matching code doesn't try to commute the operands. Do we really not have code to do that somwhere?

I prefer to have any kind of IR generated or transformed into some (more or less) canonicalised form, to reduce the number of cases that need to be matched. For such indexed loads
it's fairly typical and natural to shift/multiply the index, instead of the base address.

I'm not sure what the change to ARMAsmPrinter.cpp is supposed to do; is it buggy, and nobody noticed because it never triggers?

Yes, the LDRrs should have the destination reg, the base reg, the index reg, and the shift amount. I'll see about adding a testcase for this.

I guess the change to ARMConstantIslandPass.cpp is just to match the new pattern we generate in Thumb1 mode?

It matches the different order of operands generated in ARMISelLOwering.cpp, ARMTargetLowering::LowerBR_JT.

Would this code be less confusing if we address the FIXME in ARMInstrInfo.td about using "addrmode2" in BR_JTm?

I have a patch for that too, will sent it shortly. The two changes are don't conflict or make one another redundant, IIRC.

[chill]

In D39752#919006, @chill wrote:

In D39752#918295, @efriedma wrote:

I understand what you're trying to do with the changes to ARMISelLowering.cpp make sense, but I'm surprised our address-matching code doesn't try to commute the operands. Do we really not have code to do that somwhere?

I prefer to have any kind of IR generated or transformed into some (more or less) canonicalised form, to reduce the number of cases that need to be matched. For such indexed loads
it's fairly typical and natural to shift/multiply the index, instead of the base address.

I'm not sure what the change to ARMAsmPrinter.cpp is supposed to do; is it buggy, and nobody noticed because it never triggers?

Yes, the LDRrs should have the destination reg, the base reg, the index reg, and the shift amount. I'll see about adding a testcase for this.

Now that I looked closer, yes, this case didn't trigger, because we haven't had a shift amount there until this patch. Without this change
the compiler emits, e.g. ldr pc, [r1, r0] instead of ldr pc, [r1, r0, lsl #2]. The test test/CodeGen/ARM/arm-position-independence-jump-table.ll
tests this code, so no additional test needed.

[efriedma]

I prefer to have any kind of IR generated or transformed into some (more or less) canonicalised form, to reduce the number of cases that need to be matched. For such indexed loads it's fairly typical and natural to shift/multiply the index, instead of the base address.

Sure... but we definitely have code in ARMDAGToDAGISel::SelectAddrMode2Worker which tries to commute the base and offset. I'd like to understand why it isn't triggering. It's not a big deal to explicitly commute the operands here, but the same issue could affect other cases where the addition comes out of user code.

Just took a quick look with a debugger; it looks like the code never triggers because of the hasOneUse() check?

[chill]

In D39752#919736, @efriedma wrote:

I prefer to have any kind of IR generated or transformed into some (more or less) canonicalised form, to reduce the number of cases that need to be matched. For such indexed loads it's fairly typical and natural to shift/multiply the index, instead of the base address.

Sure... but we definitely have code in ARMDAGToDAGISel::SelectAddrMode2Worker which tries to commute the base and offset. I'd like to understand why it isn't triggering. It's not a big deal to explicitly commute the operands here, but the same issue could affect other cases where the addition comes out of user code.

Just took a quick look with a debugger; it looks like the code never triggers because of the hasOneUse() check?

Yes, that's right. That check was added by the following commit

https://github.com/llvm-mirror/llvm/commit/f40deed62f4f0126459ed7bfd1799f4e09b1aaa7#diff-c3cb15ba0731744ba5fbdc0ba6551c2eL498

I can't quite understand the logic there - certainly it would make more sense to fold the shift into the addressing
mode when shift node *has* one use ?

[efriedma]

LGTM.

I can't quite understand the logic there - certainly it would make more sense to fold the shift into the addressing mode when shift node *has* one use ?

I think that was the intent... but it got mixed up, and nobody caught it because it's not something which would trigger often anyway (since GEPs are lowered with the pointer base on the LHS). It is possible to show the general missed optimization with C code like the following: "int a(int x, int y) { return *((char*)(x*4)+y); }". But I'm fine leaving that for a separate patch.

lib/Target/ARM/ARMAsmPrinter.cpp

if (MI->getOperand(1).getReg() == 0) {
       TmpInst.addOperand(MCOperand::createReg(ARM::PC));
       TmpInst.addOperand(MCOperand::createReg(MI->getOperand(0).getReg()));
       TmpInst.addOperand(MCOperand::createImm(MI->getOperand(2).getImm()));
     } else {
       TmpInst.setOpcode(ARM::LDRrs);
       TmpInst.addOperand(MCOperand::createReg(ARM::PC));
       TmpInst.addOperand(MCOperand::createReg(MI->getOperand(0).getReg()));
       TmpInst.addOperand(MCOperand::createReg(MI->getOperand(1).getReg()));
-      TmpInst.addOperand(MCOperand::createImm(0));
+      TmpInst.addOperand(MCOperand::createImm(MI->getOperand(2).getImm()));
     }
     // Add predicate operands.
     TmpInst.addOperand(MCOperand::createImm(ARMCC::AL));
     TmpInst.addOperand(MCOperand::createReg(0));
     EmitToStreamer(*OutStreamer, TmpInst);
     return;
   }
   case ARM::BR_JTadd: {

lib/Target/ARM/ARMConstantIslandPass.cpp

if (isThumb2) {
       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
+      //   %t = tLDRr %base, %idx
       unsigned BaseReg = User.MI->getOperand(0).getReg();
 
       if (User.MI->getIterator() == User.MI->getParent()->begin())
         continue;
       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();
 
       // It's important that IdxReg is live until the actual TBB/TBH. Most of
       // the range is checked later, but the LEA might still clobber it and not
       // actually get removed.
       if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI))
         continue;
 
       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())
+      if (Load->getOperand(1).getReg() != BaseReg ||
+          Load->getOperand(2).getReg() != ShiftedIdxReg ||
+          !Load->getOperand(2).isKill())
         continue;
 
       // If we're in PIC mode, there should be another ADD following.
       auto *TRI = STI->getRegisterInfo();
 
       // %base cannot be redefined after the load as it will appear before
       // TBB/TBH like:
       //      %base =
       //      %base =
       //      tBB %base, %idx
       if (registerDefinedBetween(BaseReg, Load->getNextNode(), MBB->end(), TRI))
         continue;
 
       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())
+            Add->getOperand(2).getReg() != BaseReg ||
+            Add->getOperand(3).getReg() != Load->getOperand(0).getReg() ||
+            !Add->getOperand(3).isKill())
           continue;
         if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())
           continue;
         if (registerDefinedBetween(IdxReg, Add->getNextNode(), MI, TRI))
           // IdxReg gets redefined in the middle of the sequence.
           continue;
         Add->eraseFromParent();
         DeadSize += 2;

lib/Target/ARM/ARMISelLowering.cpp

SDValue ARMTargetLowering::LowerBR_JT(SDValue Op, SelectionDAG &DAG) const {
   SDValue Index = Op.getOperand(2);
   SDLoc dl(Op);
 
   EVT PTy = getPointerTy(DAG.getDataLayout());
   JumpTableSDNode *JT = cast<JumpTableSDNode>(Table);
   SDValue JTI = DAG.getTargetJumpTable(JT->getIndex(), PTy);
   Table = DAG.getNode(ARMISD::WrapperJT, dl, MVT::i32, JTI);
   Index = DAG.getNode(ISD::MUL, dl, PTy, Index, DAG.getConstant(4, dl, PTy));
-  SDValue Addr = DAG.getNode(ISD::ADD, dl, PTy, Index, Table);
+  SDValue Addr = DAG.getNode(ISD::ADD, dl, PTy, Table, Index);
   if (Subtarget->isThumb2() || (Subtarget->hasV8MBaselineOps() && Subtarget->isThumb())) {
     // Thumb2 and ARMv8-M use a two-level jump. That is, it jumps into the jump table
     // which does another jump to the destination. This also makes it easier
     // to translate it to TBB / TBH later (Thumb2 only).
     // FIXME: This might not work if the function is extremely large.
     return DAG.getNode(ARMISD::BR2_JT, dl, MVT::Other, Chain,
                        Addr, Op.getOperand(2), JTI);
   }
   if (isPositionIndependent() || Subtarget->isROPI()) {
     Addr =
         DAG.getLoad((EVT)MVT::i32, dl, Chain, Addr,
                     MachinePointerInfo::getJumpTable(DAG.getMachineFunction()));
     Chain = Addr.getValue(1);
-    Addr = DAG.getNode(ISD::ADD, dl, PTy, Addr, Table);
+    Addr = DAG.getNode(ISD::ADD, dl, PTy, Table, Addr);
     return DAG.getNode(ARMISD::BR_JT, dl, MVT::Other, Chain, Addr, JTI);
   } else {
     Addr =
         DAG.getLoad(PTy, dl, Chain, Addr,
                     MachinePointerInfo::getJumpTable(DAG.getMachineFunction()));
     Chain = Addr.getValue(1);
     return DAG.getNode(ARMISD::BR_JT, dl, MVT::Other, Chain, Addr, JTI);
   }

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

 
 lab4:
   tail call void @exit4()
   ret void
 
 ; CHECK-LABEL: jump_table:
 
 ; ARM: adr     r[[R_TAB_BASE:[0-9]+]], [[LJTI:\.LJTI[0-9]+_[0-9]+]]
-; ARM: lsl     r[[R_TAB_IDX:[0-9]+]], r{{[0-9]+}}, #2
-; ARM_ABS: ldr     pc, [r[[R_TAB_IDX]], r[[R_TAB_BASE]]]
-; ARM_PC:  ldr     r[[R_OFFSET:[0-9]+]], [r[[R_TAB_IDX]], r[[R_TAB_BASE]]]
-; ARM_PC:  add     pc, r[[R_OFFSET]], r[[R_TAB_BASE]]
+; ARM_ABS: ldr     pc, [r[[R_TAB_BASE]], r{{[0-9]+}}, lsl #2]
+; ARM_PC:  ldr     r[[R_OFFSET:[0-9]+]], [r[[R_TAB_BASE]], r{{[0-9]+}}, lsl #2]
+; ARM_PC:  add     pc, r[[R_TAB_BASE]], r[[R_OFFSET]]
 ; ARM: [[LJTI]]
 ; ARM_ABS: .long [[LBB1:\.LBB[0-9]+_[0-9]+]]
 ; ARM_ABS: .long [[LBB2:\.LBB[0-9]+_[0-9]+]]
 ; ARM_ABS: .long [[LBB3:\.LBB[0-9]+_[0-9]+]]
 ; ARM_ABS: .long [[LBB4:\.LBB[0-9]+_[0-9]+]]
 ; ARM_PC:  .long [[LBB1:\.LBB[0-9]+_[0-9]+]]-[[LJTI]]
 ; ARM_PC:  .long [[LBB2:\.LBB[0-9]+_[0-9]+]]-[[LJTI]]
 ; ARM_PC:  .long [[LBB3:\.LBB[0-9]+_[0-9]+]]-[[LJTI]]

test/CodeGen/ARM/execute-only.ll

 define i32 @jump_table(i32 %c, i32 %a, i32 %b) #0 {
 ; CHECK-LABEL: jump_table:
 ; CHECK-T2: adr.w   [[REG_JT:r[0-9]+]], .LJTI1_0
 ; CHECK-T2: add.w   [[REG_ENTRY:r[0-9]+]], [[REG_JT]], {{r[0-9]+}}, lsl #2
 ; CHECK-T2: mov     pc, [[REG_ENTRY]]
 
 ; CHECK-T2BASE: lsls    [[REG_OFFSET:r[0-9]+]], {{r[0-9]+}}, #2
 ; CHECK-T2BASE: adr     [[REG_JT:r[0-9]+]], .LJTI1_0
-; CHECK-T2BASE: adds    [[REG_ENTRY:r[0-9]+]], [[REG_OFFSET]], [[REG_JT]]
+; CHECK-T2BASE: adds    [[REG_ENTRY:r[0-9]+]], [[REG_JT]], [[REG_OFFSET]]
 ; CHECK-T2BASE: mov     pc, [[REG_ENTRY]]
 
 ; CHECK-LABEL: .LJTI1_0:
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w
 ; CHECK-NEXT: b.w

test/CodeGen/ARM/v6-jumptable-clobber.mir

bb.0 (%ir-block.0):
     tBcc %bb.2.d1, 8, killed %cpsr
   
   bb.1 (%ir-block.0):
     successors: %bb.3.d2(0x07c549d2), %bb.9.d8(0x07c549d2), %bb.4.d3(0x07c549d2), %bb.5.d4(0x07c549d2), %bb.6.d5(0x07c549d2), %bb.7.d6(0x07c549d2), %bb.8.d7(0x07c549d2), %bb.10.d9(0x07c549d2), %bb.11.d10(0x07c549d2), %bb.2.d1(0x03ab62db), %bb.12.d11(0x07c549d2), %bb.13.d12(0x07c549d2), %bb.14.d13(0x07c549d2), %bb.15.d14(0x07c549d2), %bb.16.d15(0x07c549d2), %bb.17.d16(0x07c549d2), %bb.18.d17(0x07c549d2)
     liveins: %r1
   
     %r0, dead %cpsr = tLSLri killed %r1, 2, 14, _
     %r1 = tLEApcrelJT %jump-table.0, 14, _
-    %r0 = tLDRr killed %r0, killed %r1, 14, _ :: (load 4 from jump-table)
+    %r0 = tLDRr killed %r1, killed %r0, 14, _ :: (load 4 from jump-table)
     tBR_JTr killed %r0, %jump-table.0
   
   bb.3.d2:
   
   bb.9.d8:
   
   bb.4.d3:
   
bb.0 (%ir-block.0):
     tBcc %bb.2.d1, 8, killed %cpsr
   
   bb.1 (%ir-block.0):
     successors: %bb.3.d2(0x07c549d2), %bb.9.d8(0x07c549d2), %bb.4.d3(0x07c549d2), %bb.5.d4(0x07c549d2), %bb.6.d5(0x07c549d2), %bb.7.d6(0x07c549d2), %bb.8.d7(0x07c549d2), %bb.10.d9(0x07c549d2), %bb.11.d10(0x07c549d2), %bb.2.d1(0x03ab62db), %bb.12.d11(0x07c549d2), %bb.13.d12(0x07c549d2), %bb.14.d13(0x07c549d2), %bb.15.d14(0x07c549d2), %bb.16.d15(0x07c549d2), %bb.17.d16(0x07c549d2), %bb.18.d17(0x07c549d2)
     liveins: %r1
   
     %r0, dead %cpsr = tLSLri killed %r1, 2, 14, _
     %r1 = tLEApcrelJT %jump-table.0, 14, _
-    %r0 = tLDRr killed %r0, killed %r1, 14, _ :: (load 4 from jump-table)
+    %r0 = tLDRr killed %r1, killed %r0, 14, _ :: (load 4 from jump-table)
     tBR_JTr killed %r0, %jump-table.0
   
   bb.3.d2:
   
   bb.9.d8:
   
   bb.4.d3: