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

3691–3693

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 ↗

(On Diff #142902)

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

4

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.

7

You can remove this.

8

local_unnamed_addr #0 is spurious.

73

this can be dropped.

[arichardson]

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

[sdardis]

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3695–3702

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);
 
+    // For power-of-two jumptable entry sizes convert multiplication to a shift.
+    // This transformation needs to be done here since otherwise the MIPS
+    // backend will end up emitting a three instruction multiply sequence
+    // instead of a single shift and MSP430 will call a runtime function.
+    if (llvm::isPowerOf2_32(EntrySize))
+      Index = DAG.getNode(
+          ISD::SHL, dl, Index.getValueType(), Index,
+          DAG.getConstant(llvm::Log2_32(EntrySize), dl, Index.getValueType()));
+    else
       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()) {

test/CodeGen/MSP430/jumptable.ll

 ; RUN: llc < %s | FileCheck %s
 
 target datalayout = "e-p:16:16:16-i8:8:8-i16:16:16-i32:16:32-n8:16"
 target triple = "msp430---elf"
 
 ; Function Attrs: nounwind
 define i16 @test(i16 %i) #0 {
 entry:
 ; CHECK-LABEL: test:
+; CHECK:      sub.w   #4, r1
+; CHECK-NEXT: mov.w   r12, 0(r1)
+; CHECK-NEXT: cmp.w   #4, r12
+; CHECK-NEXT: jhs     .LBB0_3
   %retval = alloca i16, align 2
   %i.addr = alloca i16, align 2
   store i16 %i, i16* %i.addr, align 2
   %0 = load i16, i16* %i.addr, align 2
-; CHECK: mov.w #2, r13
-; CHECK: call #__mspabi_mpyi
-; CHECK: br .LJTI0_0(r12)
+; CHECK:      rla.w r12
+; CHECK-NEXT: br .LJTI0_0(r12)
   switch i16 %0, label %sw.default [
     i16 0, label %sw.bb
     i16 1, label %sw.bb1
     i16 2, label %sw.bb2
     i16 3, label %sw.bb3
   ]
 
 sw.bb:                                            ; preds = %entry

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 - | FileCheck %s
+
+define i64 @test(i64 %arg) {
+; 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