[RISCV] Add support for lowering jumptables

[asb]

Summary

Previously, the generation of jumptables was disabled. This patch adds the necessary support, as reflected in the updated output in test/CodeGen/RISCV/jumptable.ll.

[apazos]

lib/Target/RISCV/RISCVISelLowering.cpp

153

Alex, I see lower performance when creating jump tables. We might need to set a minimum JT entries value to avoid the degradation.

[kito-cheng]

GCC using 5 as threshold to decide using jump table or not for RISC-V and LLVM using 4.

Reference:
GCC: https://github.com/gcc-mirror/gcc/blob/master/gcc/targhooks.c#L1628

• Note: targetm.have_casesi () return false for RISC-V.

LLVM: https://github.com/llvm-mirror/llvm/blob/master/lib/CodeGen/TargetLoweringBase.cpp#L72

[apazos]

Alex, we have not yet merged this patch. We should merge it and we can leave the default as GCC.
This makes our code size gap with GCC smaller.
In the past I did see degradation in some SiFive hardware (I think it was on HiFive1 board). Maybe some of the SiFive colleagues can look at it at some point.

[lenary]

lib/Target/RISCV/RISCVISelLowering.cpp

375

I'm not sure we should merge this without support for position independent code.

[apazos]

It looks like it needs more work indeed. Enabling it won't build compiler-rt.

lib/Target/RISCV/RISCVISelLowering.h

SDValue LowerCall(TargetLowering::CallLoweringInfo &CLI,
                     SmallVectorImpl<SDValue> &InVals) const override;
   bool shouldConvertConstantLoadToIntImm(const APInt &Imm,
                                          Type *Ty) const override {
     return true;
   }
   SDValue lowerGlobalAddress(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerBlockAddress(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerConstantPool(SDValue Op, SelectionDAG &DAG) const;
+  SDValue lowerJumpTable(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerExternalSymbol(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerSELECT(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerVASTART(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFRAMEADDR(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerRETURNADDR(SDValue Op, SelectionDAG &DAG) const;
 
   bool IsEligibleForTailCallOptimization(CCState &CCInfo,
     CallLoweringInfo &CLI, MachineFunction &MF,
     const SmallVector<CCValAssign, 16> &ArgLocs) const;
 };
 }
 
 #endif

lib/Target/RISCV/RISCVISelLowering.cpp

if (Subtarget.hasStdExtD()) {
     setOperationAction(ISD::BR_CC, MVT::f64, Expand);
     setLoadExtAction(ISD::EXTLOAD, MVT::f64, MVT::f32, Expand);
     setTruncStoreAction(MVT::f64, MVT::f32, Expand);
   }
 
   setOperationAction(ISD::GlobalAddress, XLenVT, Custom);
   setOperationAction(ISD::BlockAddress, XLenVT, Custom);
   setOperationAction(ISD::ConstantPool, XLenVT, Custom);
+  setOperationAction(ISD::JumpTable, XLenVT, Custom);
 
   if (Subtarget.hasStdExtA())
     setMaxAtomicSizeInBitsSupported(Subtarget.getXLen());
   else
     setMaxAtomicSizeInBitsSupported(0);
 
   setBooleanContents(ZeroOrOneBooleanContent);
 
   // Function alignments (log2).
   unsigned FunctionAlignment = Subtarget.hasStdExtC() ? 1 : 2;
   setMinFunctionAlignment(FunctionAlignment);
   setPrefFunctionAlignment(FunctionAlignment);
-
-  // Effectively disable jump table generation.
-  setMinimumJumpTableEntries(INT_MAX);
 }
 
 EVT RISCVTargetLowering::getSetCCResultType(const DataLayout &DL, LLVMContext &,
                                             EVT VT) const {
   if (!VT.isVector())
     return getPointerTy(DL);
   return VT.changeVectorElementTypeToInteger();
 }
SDValue RISCVTargetLowering::LowerOperation(SDValue Op,
   default:
     report_fatal_error("unimplemented operand");
   case ISD::GlobalAddress:
     return lowerGlobalAddress(Op, DAG);
   case ISD::BlockAddress:
     return lowerBlockAddress(Op, DAG);
   case ISD::ConstantPool:
     return lowerConstantPool(Op, DAG);
+  case ISD::JumpTable:
+    return lowerJumpTable(Op, DAG);
   case ISD::SELECT:
     return lowerSELECT(Op, DAG);
   case ISD::VASTART:
     return lowerVASTART(Op, DAG);
   case ISD::FRAMEADDR:
     return LowerFRAMEADDR(Op, DAG);
   case ISD::RETURNADDR:
     return LowerRETURNADDR(Op, DAG);
if (!isPositionIndependent()) {
     SDValue MNLo =
         SDValue(DAG.getMachineNode(RISCV::ADDI, DL, Ty, MNHi, CPALo), 0);
     return MNLo;
   } else {
     report_fatal_error("Unable to lowerConstantPool");
   }
 }
 
+SDValue RISCVTargetLowering::lowerJumpTable(SDValue Op,
+                                            SelectionDAG &DAG) const {
+  SDLoc DL(Op);
+  EVT Ty = Op.getValueType();
+  JumpTableSDNode *N = cast<JumpTableSDNode>(Op);
+  int JTI = N->getIndex();
+
+  if (!isPositionIndependent()) {
+    SDValue JTHi = DAG.getTargetJumpTable(JTI, Ty, RISCVII::MO_HI);
+    SDValue JTLo = DAG.getTargetJumpTable(JTI, Ty, RISCVII::MO_LO);
+    SDValue MNHi = SDValue(DAG.getMachineNode(RISCV::LUI, DL, Ty, JTHi), 0);
+    SDValue MNLo =
+        SDValue(DAG.getMachineNode(RISCV::ADDI, DL, Ty, MNHi, JTLo), 0);
+    return MNLo;
+  } else {
+    report_fatal_error("Unable to lowerConstantPool");
+  }
+}
+
 SDValue RISCVTargetLowering::lowerExternalSymbol(SDValue Op,
                                                  SelectionDAG &DAG) const {
   SDLoc DL(Op);
   EVT Ty = Op.getValueType();
   ExternalSymbolSDNode *N = cast<ExternalSymbolSDNode>(Op);
   const char *Sym = N->getSymbol();
 
   // TODO: should also handle gp-relative loads.

lib/Target/RISCV/RISCVMCInstLower.cpp

case MachineOperand::MO_BlockAddress:
     break;
   case MachineOperand::MO_ExternalSymbol:
     MCOp = lowerSymbolOperand(
         MO, AP.GetExternalSymbolSymbol(MO.getSymbolName()), AP);
     break;
   case MachineOperand::MO_ConstantPoolIndex:
     MCOp = lowerSymbolOperand(MO, AP.GetCPISymbol(MO.getIndex()), AP);
     break;
+  case MachineOperand::MO_JumpTableIndex:
+    MCOp = lowerSymbolOperand(MO, AP.GetJTISymbol(MO.getIndex()), AP);
+    break;
   }
   return true;
 }
 
 void llvm::LowerRISCVMachineInstrToMCInst(const MachineInstr *MI, MCInst &OutMI,
                                           const AsmPrinter &AP) {
   OutMI.setOpcode(MI->getOpcode());
 
   for (const MachineOperand &MO : MI->operands()) {
     MCOperand MCOp;
     if (LowerRISCVMachineOperandToMCOperand(MO, MCOp, AP))
       OutMI.addOperand(MCOp);
   }
 }

test/CodeGen/RISCV/jumptable.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=riscv32 -verify-machineinstrs < %s \
 ; RUN:   | FileCheck %s -check-prefix=RV32I
 
 define void @jt(i32 %in, i32* %out) {
 ; RV32I-LABEL: jt:
 ; RV32I:       # %bb.0: # %entry
-; RV32I-NEXT:    addi a2, zero, 2
-; RV32I-NEXT:    blt a2, a0, .LBB0_4
-; RV32I-NEXT:  # %bb.1: # %entry
-; RV32I-NEXT:    addi a3, zero, 1
-; RV32I-NEXT:    beq a0, a3, .LBB0_7
-; RV32I-NEXT:  # %bb.2: # %entry
-; RV32I-NEXT:    bne a0, a2, .LBB0_9
-; RV32I-NEXT:  # %bb.3: # %bb2
+; RV32I-NEXT:    addi sp, sp, -16
+; RV32I-NEXT:    sw ra, 12(sp)
+; RV32I-NEXT:    addi a2, a0, -1
 ; RV32I-NEXT:    addi a0, zero, 3
-; RV32I-NEXT:    sw a0, 0(a1)
-; RV32I-NEXT:    ret
-; RV32I-NEXT:  .LBB0_4: # %entry
-; RV32I-NEXT:    addi a3, zero, 3
-; RV32I-NEXT:    beq a0, a3, .LBB0_8
-; RV32I-NEXT:  # %bb.5: # %entry
-; RV32I-NEXT:    addi a2, zero, 4
-; RV32I-NEXT:    bne a0, a2, .LBB0_9
-; RV32I-NEXT:  # %bb.6: # %bb4
-; RV32I-NEXT:    addi a0, zero, 1
-; RV32I-NEXT:    sw a0, 0(a1)
-; RV32I-NEXT:    ret
-; RV32I-NEXT:  .LBB0_7: # %bb1
+; RV32I-NEXT:    bltu a0, a2, .LBB0_6
+; RV32I-NEXT:  # %bb.1: # %entry
+; RV32I-NEXT:    lui a3, %hi(.LJTI0_0)
+; RV32I-NEXT:    addi a3, a3, %lo(.LJTI0_0)
+; RV32I-NEXT:    slli a2, a2, 2
+; RV32I-NEXT:    add a2, a2, a3
+; RV32I-NEXT:    lw a2, 0(a2)
+; RV32I-NEXT:    jr a2
+; RV32I-NEXT:  .LBB0_2: # %bb1
 ; RV32I-NEXT:    addi a0, zero, 4
+; RV32I-NEXT:    j .LBB0_5
+; RV32I-NEXT:  .LBB0_3: # %bb3
+; RV32I-NEXT:    addi a0, zero, 2
+; RV32I-NEXT:    j .LBB0_5
+; RV32I-NEXT:  .LBB0_4: # %bb4
+; RV32I-NEXT:    addi a0, zero, 1
+; RV32I-NEXT:  .LBB0_5: # %exit
 ; RV32I-NEXT:    sw a0, 0(a1)
-; RV32I-NEXT:    ret
-; RV32I-NEXT:  .LBB0_8: # %bb3
-; RV32I-NEXT:    sw a2, 0(a1)
-; RV32I-NEXT:  .LBB0_9: # %exit
+; RV32I-NEXT:  .LBB0_6: # %exit
+; RV32I-NEXT:    lw ra, 12(sp)
+; RV32I-NEXT:    addi sp, sp, 16
 ; RV32I-NEXT:    ret
 entry:
   switch i32 %in, label %exit [
     i32 1, label %bb1
     i32 2, label %bb2
     i32 3, label %bb3
     i32 4, label %bb4
   ]