Emit a left-shift instead of a power-of-two multiply for jump-tables

[arichardson]

Summary

SelectionDAGLegalize::ExpandNode() inserts an ISD::MUL when lowering a
BR_JT opcode. While many backends optimize this multiply into a shift, e.g.
the MIPS backend currently always lowers this into a sequence of
load-immediate+multiply+mflo in MipsSETargetLowering::lowerMulDiv().

I initially changed the multiply to a shift in the MIPS backend but it
turns out that would not have handled the MIPSR6 case and was a lot more
code than doing it in LegalizeDAG.
I believe performing this simple optimization in LegalizeDAG instead of
each individual backend is the better solution since this also fixes other
backeds such as MSP430 which calls the multiply runtime function
__mspabi_mpyi without this patch.

[sdardis]

I think we need to modify LegalizeDAG .cpp here directly to eliminate the multiplication, as the legalizer has legalized the ISD::BR_JT into an address synthesis, load and multiplication. The legalizer then recursively legalizes the multiplication into a mult/mflo pair.

Another option would be to provide a MipsPat to match the case of multiplication by a constant followed by a mflo, and where the constant is a power of 2 replace it with a shift of the variable operand to multiplication. That approach would be private to the MIPS backend.

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3692–3694

If you look at DAGCombine.cpp:2667, you'll see the folding of

fold (mul x, (1 << c)) -> x << c

so, if the jump table entry size is a power of two, Index can become a left shift of the log2 of size of the jump table entry, otherwise the multiplication is ok.

lib/Target/Mips/MipsSEISelLowering.cpp

1230–1242

This isn't particularly great as it misses the case where we have a MIPSR6 target, as we don't use this function to perform lowering for that target.

test/CodeGen/Mips/jump-table-mul.ll

3

Spurious RUN: line. If you mean to test the output of -debug, this test also needs: "REQUIRES: asserts", and a FileCheck invocation with a unique prefix.

6

You can remove this.

7

local_unnamed_addr #0 is spurious.

72

this can be dropped.

[arichardson]

Perform the optimization in LegalizeDAG instead. Turns out this also fixes MSP430

[sdardis]

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3700–3707

You drop the braces for this if/else pair as they're each a single statement.

[arichardson]

Address review comment

[sdardis]

LGTM.

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

case ISD::BR_JT: {
     SDValue Index = Node->getOperand(2);
 
     const DataLayout &TD = DAG.getDataLayout();
     EVT PTy = TLI.getPointerTy(TD);
 
     unsigned EntrySize =
       DAG.getMachineFunction().getJumpTableInfo()->getEntrySize(TD);
 
+    // TODO: Should we turn this into a shift if entry size is a power of 2
+    // This would stop MIPS from emitting a dmult+dmlfo for this but could
+    // it possibly break other targets?
     Index = DAG.getNode(ISD::MUL, dl, Index.getValueType(), Index,
                         DAG.getConstant(EntrySize, dl, Index.getValueType()));
     SDValue Addr = DAG.getNode(ISD::ADD, dl, Index.getValueType(),
                                Index, Table);
 
     EVT MemVT = EVT::getIntegerVT(*DAG.getContext(), EntrySize * 8);
     SDValue LD = DAG.getExtLoad(
         ISD::SEXTLOAD, dl, PTy, Chain, Addr,
         MachinePointerInfo::getJumpTable(DAG.getMachineFunction()), MemVT);
     Addr = LD;
     if (TLI.isJumpTableRelative()) {
       // For PIC, the sequence is:
       // BRIND(load(Jumptable + index) + RelocBase)
       // RelocBase can be JumpTable, GOT or some sort of global base.
       Addr = DAG.getNode(ISD::ADD, dl, PTy, Addr,
                           TLI.getPICJumpTableRelocBase(Table, DAG));
     }
 
     Tmp1 = TLI.expandIndirectJTBranch(dl, LD.getValue(1), Addr, DAG);
     Results.push_back(Tmp1);
     break;

lib/Target/Mips/MipsSEISelLowering.cpp

 SDValue MipsSETargetLowering::lowerMulDiv(SDValue Op, unsigned NewOpc,
                                           bool HasLo, bool HasHi,
                                           SelectionDAG &DAG) const {
   // MIPS32r6/MIPS64r6 removed accumulator based multiplies.
   assert(!Subtarget.hasMips32r6());
 
   EVT Ty = Op.getOperand(0).getValueType();
   SDLoc DL(Op);
+
+  // Turn constant power-of-two multiplications that only need lo into a shift:
+  // FIXME: this is probably the wrong place to do this transformation but it is
+  // needed to avoid emitting a li/dmult/dmflo instead of a single shift with an
+  // immediate operand during the lowering of jump tables
+  if ((NewOpc == MipsISD::Mult || NewOpc == MipsISD::Multu) && HasLo &&
+      !HasHi) {
+    if (ConstantSDNode *CImm = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
+      const APInt &Val = CImm->getAPIntValue();
+      if (Val.isStrictlyPositive() && Val.isPowerOf2())
+        return DAG.getNode(ISD::SHL, DL, Ty, Op->getOperand(0),
+                           DAG.getConstant(Val.logBase2(), DL, Ty));
+    }
+  }
+
   SDValue Mult = DAG.getNode(NewOpc, DL, MVT::Untyped,
                              Op.getOperand(0), Op.getOperand(1));
   SDValue Lo, Hi;
 
   if (HasLo)
     Lo = DAG.getNode(MipsISD::MFLO, DL, Ty, Mult);
   if (HasHi)
     Hi = DAG.getNode(MipsISD::MFHI, DL, Ty, Mult);

test/CodeGen/Mips/2010-07-20-Switch.ll

 
 ; PIC-O32: sll $[[R0:[0-9]+]], ${{[0-9]+}}, 2
 ; PIC-O32: lw $[[R1:[0-9]+]], %got($JTI0_0)
 ; PIC-O32: addu $[[R2:[0-9]+]], $[[R0]], $[[R1]]
 ; PIC-O32: lw $[[R4:[0-9]+]], %lo($JTI0_0)($[[R2]])
 ; PIC-O32: addu $[[R5:[0-9]+]], $[[R4:[0-9]+]]
 ; PIC-O32: jr  $[[R5]]
 
-; STATIC-N64: mflo $[[R0:[0-9]]]
+; STATIC-N64: dsrl $[[I32:[0-9]]], ${{[0-9]+}}, 32
+; STATIC-N64: dsll $[[R0:[0-9]]], $[[I32]], 3
 ; STATIC-N64: lui $[[R1:[0-9]]], %highest(.LJTI0_0)
 ; STATIC-N64: daddiu $[[R2:[0-9]]], $[[R1]], %higher(.LJTI0_0)
 ; STATIC-N64: dsll $[[R3:[0-9]]], $[[R2]], 16
 ; STATIC-N64: daddiu $[[R4:[0-9]]], $[[R3]], %hi(.LJTI0_0)
 ; STATIC-N64: dsll $[[R5:[0-9]]], $[[R4]], 16
 ; STATIC-N64: daddu $[[R6:[0-9]]], $[[R0]], $[[R4]]
 ; STATIC-N64: ld ${{[0-9]+}}, %lo(.LJTI0_0)($[[R6]])
 

test/CodeGen/Mips/indirect-jump-hazard/jumptables.ll

 ; MIPS64R2-NEXT:    daddiu $sp, $sp, -16
 ; MIPS64R2-NEXT:    .cfi_def_cfa_offset 16
 ; MIPS64R2-NEXT:    sw $4, 4($sp)
 ; MIPS64R2-NEXT:    lwu $2, 4($sp)
 ; MIPS64R2-NEXT:    sltiu $1, $2, 7
 ; MIPS64R2-NEXT:    beqz $1, .LBB0_3
 ; MIPS64R2-NEXT:    nop
 ; MIPS64R2-NEXT:  .LBB0_1: # %entry
-; MIPS64R2-NEXT:    daddiu $1, $zero, 8
-; MIPS64R2-NEXT:    dmult $2, $1
-; MIPS64R2-NEXT:    mflo $1
+; MIPS64R2-NEXT:    dsll $1, $2, 3
 ; MIPS64R2-NEXT:    lui $2, %highest(.LJTI0_0)
 ; MIPS64R2-NEXT:    daddiu $2, $2, %higher(.LJTI0_0)
 ; MIPS64R2-NEXT:    dsll $2, $2, 16
 ; MIPS64R2-NEXT:    daddiu $2, $2, %hi(.LJTI0_0)
 ; MIPS64R2-NEXT:    dsll $2, $2, 16
 ; MIPS64R2-NEXT:    daddu $1, $1, $2
 ; MIPS64R2-NEXT:    ld $1, %lo(.LJTI0_0)($1)
 ; MIPS64R2-NEXT:    jr.hb $1

 ; PIC-MIPS64R2-NEXT:    daddu $1, $1, $25
 ; PIC-MIPS64R2-NEXT:    daddiu $2, $1, %lo(%neg(%gp_rel(_Z3fooi)))
 ; PIC-MIPS64R2-NEXT:    sw $4, 4($sp)
 ; PIC-MIPS64R2-NEXT:    lwu $3, 4($sp)
 ; PIC-MIPS64R2-NEXT:    sltiu $1, $3, 7
 ; PIC-MIPS64R2-NEXT:    beqz $1, .LBB0_3
 ; PIC-MIPS64R2-NEXT:    nop
 ; PIC-MIPS64R2-NEXT:  .LBB0_1: # %entry
-; PIC-MIPS64R2-NEXT:    daddiu $1, $zero, 8
-; PIC-MIPS64R2-NEXT:    dmult $3, $1
-; PIC-MIPS64R2-NEXT:    mflo $1
+; PIC-MIPS64R2-NEXT:    dsll $1, $3, 3
 ; PIC-MIPS64R2-NEXT:    ld $3, %got_page(.LJTI0_0)($2)
 ; PIC-MIPS64R2-NEXT:    daddu $1, $1, $3
 ; PIC-MIPS64R2-NEXT:    ld $1, %got_ofst(.LJTI0_0)($1)
 ; PIC-MIPS64R2-NEXT:    daddu $1, $1, $2
 ; PIC-MIPS64R2-NEXT:    jr.hb $1
 ; PIC-MIPS64R2-NEXT:    nop
 ; PIC-MIPS64R2-NEXT:  .LBB0_2: # %sw.bb
 ; PIC-MIPS64R2-NEXT:    ld $1, %got_page(.L.str)($2)

test/CodeGen/Mips/jump-table-mul.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; We used to generate a mul+mflo sequence instead of shifting by 2/3 to get the jump table address
+; RUN: llc %s -O2 -mtriple=mips64-unknown-freebsd -target-abi n64 -relocation-model=pic -o /dev/null -debug
+; RUN: llc %s -O2 -mtriple=mips64-unknown-freebsd -target-abi n64 -relocation-model=pic -o - | FileCheck %s
+
+; Function Attrs: noreturn nounwind
+define i64 @test(i64 %arg) local_unnamed_addr #0 {
+; CHECK-LABEL: test:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    lui $1, %hi(%neg(%gp_rel(test)))
+; CHECK-NEXT:    daddu $2, $1, $25
+; CHECK-NEXT:    sltiu $1, $4, 11
+; CHECK-NEXT:    beqz $1, .LBB0_3
+; CHECK-NEXT:    nop
+; CHECK-NEXT:  .LBB0_1: # %entry
+; CHECK-NEXT:    daddiu $1, $2, %lo(%neg(%gp_rel(test)))
+; CHECK-NEXT:    dsll $2, $4, 3
+; Previously this dsll was the following sequence:
+; daddiu  $2, $zero, 8
+; dmult $4, $2
+; mflo  $2
+; CHECK-NEXT:    ld $3, %got_page(.LJTI0_0)($1)
+; CHECK-NEXT:    daddu $2, $2, $3
+; CHECK-NEXT:    ld $2, %got_ofst(.LJTI0_0)($2)
+; CHECK-NEXT:    daddu $1, $2, $1
+; CHECK-NEXT:    jr $1
+; CHECK-NEXT:    nop
+; CHECK-NEXT:  .LBB0_2: # %sw.bb
+; CHECK-NEXT:    jr $ra
+; CHECK-NEXT:    daddiu $2, $zero, 1
+; CHECK-NEXT:  .LBB0_3: # %default
+; CHECK-NEXT:    jr $ra
+; CHECK-NEXT:    daddiu $2, $zero, 1234
+; CHECK-NEXT:  .LBB0_4: # %sw.bb1
+; CHECK-NEXT:    jr $ra
+; CHECK-NEXT:    daddiu $2, $zero, 0
+entry:
+  switch i64 %arg, label %default [
+    i64 0, label %sw.bb
+    i64 3, label %sw.bb
+    i64 5, label %sw.bb
+    i64 10, label %sw.bb1
+  ]
+
+default:
+  ret i64 1234
+
+sw.bb:
+  ret i64 1
+
+sw.bb1:
+  ret i64 0
+}
+
+; CHECK-LABEL:  .section  .rodata,"a",@progbits
+; CHECK-NEXT:   .p2align  3
+; CHECK-LABEL: .LJTI0_0:
+; CHECK-NEXT:   .gpdword  .LBB0_2
+; CHECK-NEXT:   .gpdword  .LBB0_3
+; CHECK-NEXT:   .gpdword  .LBB0_3
+; CHECK-NEXT:   .gpdword  .LBB0_2
+; CHECK-NEXT:   .gpdword  .LBB0_3
+; CHECK-NEXT:   .gpdword  .LBB0_2
+; CHECK-NEXT:   .gpdword  .LBB0_3
+; CHECK-NEXT:   .gpdword  .LBB0_3
+; CHECK-NEXT:   .gpdword  .LBB0_3
+; CHECK-NEXT:   .gpdword  .LBB0_3
+; CHECK-NEXT:   .gpdword  .LBB0_4
+
+
+
+attributes #0 = { noreturn nounwind }