[RISCV] Add custom type legalization to form MULHSU when possible.

[craig.topper]

Summary

There's no target independent ISD opcode for MULHSU, so custom
legalize 2*XLen multiplies ourselves. We have to be a little
careful to prefer MULHU or MULHSU.

I thought about doing this in isel by pattern matching the
(add (mul X, (srai Y, XLen-1)), (mulhu X, Y)) pattern. I decided
against this because the add might become part of a chain of adds.
I don't trust DAG combine not to reassociate with other adds making
it difficult to find both pieces again.

[asb]

LGTM.

I think it's OK to land without this, but: Running this patch quickly across the GCC torture suite, the only codegen changes are to 20120817-1.c and pr51581-{1,2}.c on RV32 where a mulhsu is now selected rather than a solitary mulh. I believe this is still correct, but it made me wonder if we are missing some test coverage and should have a codegen test that would demonstrate that change.

[craig.topper]

In D99479#2663549, @asb wrote:

LGTM.

I think it's OK to land without this, but: Running this patch quickly across the GCC torture suite, the only codegen changes are to 20120817-1.c and pr51581-{1,2}.c on RV32 where a mulhsu is now selected rather than a solitary mulh. I believe this is still correct, but it made me wonder if we are missing some test coverage and should have a codegen test that would demonstrate that change.

I didn't intend that to happen. I was hoping to only affect cases that couldn't be handled by MULH and MULHU. I'll see about making my checks stricter.

llvm/lib/Target/RISCV/RISCVISelLowering.h

enum NodeType : unsigned {
   /// condition code in op #2, a XLenVT constant from the ISD::CondCode enum.
   /// The lhs and rhs are XLenVT integers. The true and false values can be
   /// integer or floating point.
   SELECT_CC,
   BR_CC,
   BuildPairF64,
   SplitF64,
   TAIL,
+  // Multiply high for signedxunsigned.
+  MULHSU,
   // RV64I shifts, directly matching the semantics of the named RISC-V
   // instructions.
   SLLW,
   SRAW,
   SRLW,
   // 32-bit operations from RV64M that can't be simply matched with a pattern
   // at instruction selection time. These have undefined behavior for division
   // by 0 or overflow (divw) like their target independent counterparts.

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

RISCVTargetLowering::RISCVTargetLowering(const TargetMachine &TM,
   if (!Subtarget.hasStdExtM()) {
     setOperationAction(ISD::MUL, XLenVT, Expand);
     setOperationAction(ISD::MULHS, XLenVT, Expand);
     setOperationAction(ISD::MULHU, XLenVT, Expand);
     setOperationAction(ISD::SDIV, XLenVT, Expand);
     setOperationAction(ISD::UDIV, XLenVT, Expand);
     setOperationAction(ISD::SREM, XLenVT, Expand);
     setOperationAction(ISD::UREM, XLenVT, Expand);
-  }
-
-  if (Subtarget.is64Bit() && Subtarget.hasStdExtM()) {
+  } else {
+    if (Subtarget.is64Bit()) {
       setOperationAction(ISD::MUL, MVT::i32, Custom);
+      setOperationAction(ISD::MUL, MVT::i128, Custom);
 
       setOperationAction(ISD::SDIV, MVT::i8, Custom);
       setOperationAction(ISD::UDIV, MVT::i8, Custom);
       setOperationAction(ISD::UREM, MVT::i8, Custom);
       setOperationAction(ISD::SDIV, MVT::i16, Custom);
       setOperationAction(ISD::UDIV, MVT::i16, Custom);
       setOperationAction(ISD::UREM, MVT::i16, Custom);
       setOperationAction(ISD::SDIV, MVT::i32, Custom);
       setOperationAction(ISD::UDIV, MVT::i32, Custom);
       setOperationAction(ISD::UREM, MVT::i32, Custom);
+    } else {
+      setOperationAction(ISD::MUL, MVT::i64, Custom);
+    }
   }
 
   setOperationAction(ISD::SDIVREM, XLenVT, Expand);
   setOperationAction(ISD::UDIVREM, XLenVT, Expand);
   setOperationAction(ISD::SMUL_LOHI, XLenVT, Expand);
   setOperationAction(ISD::UMUL_LOHI, XLenVT, Expand);
 
   setOperationAction(ISD::SHL_PARTS, XLenVT, Custom);
case ISD::READCYCLECOUNTER: {
     SDValue RCW =
         DAG.getNode(RISCVISD::READ_CYCLE_WIDE, DL, VTs, N->getOperand(0));
 
     Results.push_back(
         DAG.getNode(ISD::BUILD_PAIR, DL, MVT::i64, RCW, RCW.getValue(1)));
     Results.push_back(RCW.getValue(2));
     break;
   }
+  case ISD::MUL: {
+    unsigned Size = N->getSimpleValueType(0).getSizeInBits();
+    unsigned XLen = Subtarget.getXLen();
+    // This multiply needs to be expanded, try to use MULHSU+MUL if possible.
+    if (Size > XLen) {
+      assert(Size == (XLen * 2) && "Unexpected custom legalisation");
+      SDValue LHS = N->getOperand(0);
+      SDValue RHS = N->getOperand(1);
+      APInt HighMask = APInt::getHighBitsSet(Size, XLen);
+
+      bool LHSIsU = DAG.MaskedValueIsZero(LHS, HighMask);
+      bool RHSIsU = DAG.MaskedValueIsZero(RHS, HighMask);
+      // We need exactly one side to be unsigned.
+      if (LHSIsU == RHSIsU)
+        return;
+
+      auto MakeMULPair = [&](SDValue S, SDValue U) {
+        MVT XLenVT = Subtarget.getXLenVT();
+        S = DAG.getNode(ISD::TRUNCATE, DL, XLenVT, S);
+        U = DAG.getNode(ISD::TRUNCATE, DL, XLenVT, U);
+        SDValue Lo = DAG.getNode(ISD::MUL, DL, XLenVT, S, U);
+        SDValue Hi = DAG.getNode(RISCVISD::MULHSU, DL, XLenVT, S, U);
+        return DAG.getNode(ISD::BUILD_PAIR, DL, N->getValueType(0), Lo, Hi);
+      };
+
+      bool LHSIsS = DAG.ComputeNumSignBits(LHS) > XLen;
+      bool RHSIsS = DAG.ComputeNumSignBits(RHS) > XLen;
+
+      // The other operand should be signed, but still prefer MULH when
+      // possible.
+      if (RHSIsU && LHSIsS && !RHSIsS)
+        Results.push_back(MakeMULPair(LHS, RHS));
+      else if (LHSIsU && RHSIsS && !LHSIsS)
+        Results.push_back(MakeMULPair(RHS, LHS));
+
+      return;
+    }
+    LLVM_FALLTHROUGH;
+  }
   case ISD::ADD:
   case ISD::SUB:
-  case ISD::MUL:
     assert(N->getValueType(0) == MVT::i32 && Subtarget.is64Bit() &&
            "Unexpected custom legalisation");
     if (N->getOperand(1).getOpcode() == ISD::Constant)
       return;
     Results.push_back(customLegalizeToWOpWithSExt(N, DAG));
     break;
   case ISD::SHL:
   case ISD::SRA:
#define NODE_NAME_CASE(NODE)                                                   \
   NODE_NAME_CASE(SRET_FLAG)
   NODE_NAME_CASE(MRET_FLAG)
   NODE_NAME_CASE(CALL)
   NODE_NAME_CASE(SELECT_CC)
   NODE_NAME_CASE(BR_CC)
   NODE_NAME_CASE(BuildPairF64)
   NODE_NAME_CASE(SplitF64)
   NODE_NAME_CASE(TAIL)
+  NODE_NAME_CASE(MULHSU)
   NODE_NAME_CASE(SLLW)
   NODE_NAME_CASE(SRAW)
   NODE_NAME_CASE(SRLW)
   NODE_NAME_CASE(DIVW)
   NODE_NAME_CASE(DIVUW)
   NODE_NAME_CASE(REMUW)
   NODE_NAME_CASE(ROLW)
   NODE_NAME_CASE(RORW)

llvm/lib/Target/RISCV/RISCVInstrInfoM.td

 // Multiplication and Division instruction set extension.
 //
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // RISC-V specific DAG Nodes.
 //===----------------------------------------------------------------------===//
 
+def riscv_mulhsu : SDNode<"RISCVISD::MULHSU", SDTIntBinOp>;
 def riscv_divw  : SDNode<"RISCVISD::DIVW",  SDT_RISCVIntBinOpW>;
 def riscv_divuw : SDNode<"RISCVISD::DIVUW", SDT_RISCVIntBinOpW>;
 def riscv_remuw : SDNode<"RISCVISD::REMUW", SDT_RISCVIntBinOpW>;
 
 //===----------------------------------------------------------------------===//
 // Instructions
 //===----------------------------------------------------------------------===//
 

 //===----------------------------------------------------------------------===//
 // Pseudo-instructions and codegen patterns
 //===----------------------------------------------------------------------===//
 
 let Predicates = [HasStdExtM] in {
 def : PatGprGpr<mul, MUL>;
 def : PatGprGpr<mulhs, MULH>;
 def : PatGprGpr<mulhu, MULHU>;
-// No ISDOpcode for mulhsu
+def : PatGprGpr<riscv_mulhsu, MULHSU>;
 def : PatGprGpr<sdiv, DIV>;
 def : PatGprGpr<udiv, DIVU>;
 def : PatGprGpr<srem, REM>;
 def : PatGprGpr<urem, REMU>;
 } // Predicates = [HasStdExtM]
 
 let Predicates = [HasStdExtM, IsRV64] in {
 def : Pat<(sext_inreg (mul GPR:$rs1, GPR:$rs2), i32),

llvm/test/CodeGen/RISCV/mul.ll

 ; RV32I-NEXT:    call __muldi3@plt
 ; RV32I-NEXT:    mv a0, a1
 ; RV32I-NEXT:    lw ra, 12(sp) # 4-byte Folded Reload
 ; RV32I-NEXT:    addi sp, sp, 16
 ; RV32I-NEXT:    ret
 ;
 ; RV32IM-LABEL: mulhsu:
 ; RV32IM:       # %bb.0:
-; RV32IM-NEXT:    srai a2, a1, 31
-; RV32IM-NEXT:    mulhu a1, a0, a1
-; RV32IM-NEXT:    mul a0, a0, a2
-; RV32IM-NEXT:    add a0, a1, a0
+; RV32IM-NEXT:    mulhsu a0, a1, a0
 ; RV32IM-NEXT:    ret
 ;
 ; RV64I-LABEL: mulhsu:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    addi sp, sp, -16
 ; RV64I-NEXT:    sd ra, 8(sp) # 8-byte Folded Spill
 ; RV64I-NEXT:    slli a0, a0, 32
 ; RV64I-NEXT:    srli a0, a0, 32

 ; RV64I-NEXT:    call __multi3@plt
 ; RV64I-NEXT:    mv a0, a1
 ; RV64I-NEXT:    ld ra, 8(sp) # 8-byte Folded Reload
 ; RV64I-NEXT:    addi sp, sp, 16
 ; RV64I-NEXT:    ret
 ;
 ; RV64IM-LABEL: mulhsu_i64:
 ; RV64IM:       # %bb.0:
-; RV64IM-NEXT:    srai a2, a1, 63
-; RV64IM-NEXT:    mulhu a1, a0, a1
-; RV64IM-NEXT:    mul a0, a0, a2
-; RV64IM-NEXT:    add a0, a1, a0
+; RV64IM-NEXT:    mulhsu a0, a1, a0
 ; RV64IM-NEXT:    ret
   %1 = zext i64 %a to i128
   %2 = sext i64 %b to i128
   %3 = mul i128 %1, %2
   %4 = lshr i128 %3, 64
   %5 = trunc i128 %4 to i64
   ret i64 %5
 }