[X86] Combine vXi64 multiplies to MULDQ/MULUDQ during DAG combine instead of lowering.

[craig.topper]

Summary

Previously we used a custom lowering for this because of the AVX1 splitting requirement. But we can do the split during DAG combine if we check the types and subtarget.

I tried to use SplitBinaryOpsAndApply but the 512-bit path through that code assumes a destination VT with i16 or i8 elements since it checks BWI. But I don't need a BWI check here nor do I need any splitting for 512 bits. So I just made a AVX1 helper. I used SelectionDAG::SplitVector and SelectionDAG::SplitDestVT since those already know how to split in half. Since this is during DAG combine it doesn't need the BUILD_VECTOR check that the extractSubvector helper uses.

The test change is a regression, but its not strictly related to this change. There's a DAG combine in visitBUILD_VECTOR that only runs during the post type legalization DAG combine or the DAG combine after legalizing vector ops. But those DAG combines only run if the legal types or legal vector ops process changed the DAG. The DAG combine I've added here runs before type legalization, there are no illegal types, and no vector ops to legalize so the DAG combine in visitBUILD_VECTOR didn't get a chance to run. I've tried to fix the build_vector DAG combine to work before type legalization, but I've hit other issues that I'm trying to work through. Hopefully we can try to resolve that separately.

[craig.topper]

Remove the MULDQ code from LowerMUL. The DAG combine should cover it now.

[craig.topper]

Added a flag to SplitBinaryOpsAndApply to control checking useBWIRegs or useAVX512Regs. I wanted to do it based on VT, but PMADDWD uses a vXi32 result VT and a vXi16 input VT.

Also removed some more code from LowerMUL that checked for hasDQI.

[RKSimon]

So what do you think we should do about this regression? We /could/ fix it via getFauxShuffleMask but there are probably better ways.

lib/Target/X86/X86ISelLowering.cpp

33167

PMULUDQBuilder ?

[craig.topper]

Rebase since simplify demanded bits went in. Still need to figure out how to fix the regression. Everything I've tried so far as introduce other regressions.

[craig.topper]

Added a target independent DAG combine to create zero_extend from a build_vector of zexts from a contiguous range of an input vector. This more or less recovers the regression. I can split that change out of this patch if you want. I'll definitely split it for commit.

[craig.topper]

test/CodeGen/X86/mulvi32.ll

170

These shuffles are moving the high elements down so we can zero extend. The original code used a punpck with zero instead.

181–182

I think this is simplify demanded bits on pmuldq kicking in to remove the zeros going into elements 1 and 3. So they are effectively garbage.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15070 ↗

(On Diff #140027)

Its strange that we have reduceBuildVecExtToExtBuildVec for post-legalization and this for pre-legalization. Not exactly the same I know.

test/CodeGen/X86/combine-pmuldq.ll

8 ↗

(On Diff #140027)

This TODO can go

27 ↗

(On Diff #140027)

This TODO can go

[craig.topper]

Remove TODOs

[craig.topper]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15070 ↗

(On Diff #140027)

I tried to enable reduceBuildVecExtToExtBuildVec pre-legalization, but it was too aggressive and caused many other issues. The first DAG combine effectively runs on the DAG bottom up. So we could fold BUILD_VECTORS of zero_extends before the zero_extends are combined with loads or truncates before them. So we would need to try to detect those opportunities and prevent the combine or add more combines to do the same combines with the new build_vector.

[craig.topper]

Ping

[RKSimon]

LGTM - with a few minors

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14981 ↗

(On Diff #140093)

You're setting the return type as uint64_t but returning -1 ?

15001 ↗

(On Diff #140093)

(Offset + i) for clarity

lib/Target/X86/X86ISelLowering.cpp

33167

PMULUDQBuilder ?

[craig.topper]

Commited in r329510.

lib/Target/X86/X86ISelLowering.cpp

if (!Subtarget.useSoftFloat() && Subtarget.useAVX512Regs()) {
     setOperationPromotedToType(ISD::OR,  MVT::v16i32, MVT::v8i64);
     setOperationPromotedToType(ISD::XOR, MVT::v16i32, MVT::v8i64);
 
     if (Subtarget.hasDQI()) {
       setOperationAction(ISD::SINT_TO_FP, MVT::v8i64, Legal);
       setOperationAction(ISD::UINT_TO_FP, MVT::v8i64, Legal);
       setOperationAction(ISD::FP_TO_SINT, MVT::v8i64, Legal);
       setOperationAction(ISD::FP_TO_UINT, MVT::v8i64, Legal);
+
+      setOperationAction(ISD::MUL,        MVT::v8i64, Legal);
     }
 
     if (Subtarget.hasCDI()) {
       // NonVLX sub-targets extend 128/256 vectors to use the 512 version.
       for (auto VT : { MVT::v16i32, MVT::v8i64} ) {
         setOperationAction(ISD::CTLZ,            VT, Legal);
         setOperationAction(ISD::CTTZ_ZERO_UNDEF, VT, Custom);
       }
for (auto VT : { MVT::v4i32, MVT::v8i32, MVT::v2i64, MVT::v4i64,
       setOperationAction(ISD::MSCATTER, VT, Custom);
 
     if (Subtarget.hasDQI()) {
       for (auto VT : { MVT::v2i64, MVT::v4i64 }) {
         setOperationAction(ISD::SINT_TO_FP,     VT, Legal);
         setOperationAction(ISD::UINT_TO_FP,     VT, Legal);
         setOperationAction(ISD::FP_TO_SINT,     VT, Legal);
         setOperationAction(ISD::FP_TO_UINT,     VT, Legal);
+
+        setOperationAction(ISD::MUL,            VT, Legal);
       }
     }
 
     if (Subtarget.hasCDI()) {
       for (auto VT : { MVT::v4i32, MVT::v8i32, MVT::v2i64, MVT::v4i64 }) {
         setOperationAction(ISD::CTLZ,            VT, Legal);
         setOperationAction(ISD::CTTZ_ZERO_UNDEF, VT, Custom);
       }
if (VT == MVT::v4i32) {
     // shuffles.
     static const int ShufMask[] = { 0, 4, 2, 6 };
     return DAG.getVectorShuffle(VT, dl, Evens, Odds, ShufMask);
   }
 
   assert((VT == MVT::v2i64 || VT == MVT::v4i64 || VT == MVT::v8i64) &&
          "Only know how to lower V2I64/V4I64/V8I64 multiply");
 
-  // MULDQ returns the 64-bit result of the signed multiplication of the lower
-  // 32-bits. We can lower with this if the sign bits stretch that far.
-  if (Subtarget.hasSSE41() && DAG.ComputeNumSignBits(A) > 32 &&
-      DAG.ComputeNumSignBits(B) > 32) {
-    return DAG.getNode(X86ISD::PMULDQ, dl, VT, A, B);
-  }
-
   //  Ahi = psrlqi(a, 32);
   //  Bhi = psrlqi(b, 32);
   //
   //  AloBlo = pmuludq(a, b);
   //  AloBhi = pmuludq(a, Bhi);
   //  AhiBlo = pmuludq(Ahi, b);
   //
   //  Hi = psllqi(AloBhi + AhiBlo, 32);
return DAG.getNode(
                     DAG.getNode(ISD::SHL, DL, VT, N->getOperand(0),
                                 DAG.getConstant(5, DL, MVT::i8)),
                     N->getOperand(0)),
         N->getOperand(0));
   }
   return SDValue();
 }
 
+static SDValue getNodeAVXSplit(unsigned Opcode, const SDLoc &DL, EVT VT,
+                               ArrayRef<SDValue> Ops, SelectionDAG &DAG,
+                               const X86Subtarget &Subtarget) {
+  assert(DAG.getTargetLoweringInfo().isTypeLegal(VT) && "Expected legal type");
+  assert(VT.isVector() && VT.isInteger() && "Expected integer vector type");
+
+  if (VT.getSimpleVT().is256BitVector() && !Subtarget.hasAVX2()) {
+    SmallVector<SDValue, 2> OpsLo(Ops.size()), OpsHi(Ops.size());
+    for (unsigned i = 0; i != Ops.size(); ++i)
+      std::tie(OpsLo[i], OpsHi[i]) = DAG.SplitVector(Ops[i], DL);
+
+    EVT LoVT, HiVT;
+    std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(VT);
+    SDValue Lo = DAG.getNode(Opcode, DL, LoVT, OpsLo);
+    SDValue Hi = DAG.getNode(Opcode, DL, HiVT, OpsHi);
+    return DAG.getNode(ISD::CONCAT_VECTORS, DL, VT, Lo, Hi);
+  }
+
+  return DAG.getNode(Opcode, DL, VT, Ops);
+}
+
 // If the upper 17 bits of each element are zero then we can use PMADDWD,
 // which is always at least as quick as PMULLD, expect on KNL.
 static SDValue combineMulToPMADDWD(SDNode *N, SelectionDAG &DAG,
                                    const X86Subtarget &Subtarget) {
   if (!Subtarget.hasSSE2())
     return SDValue();
 
   if (Subtarget.getProcFamily() == X86Subtarget::IntelKNL)
static SDValue combineMulToPMADDWD(SDNode *N, SelectionDAG &DAG,
 
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   APInt Mask17 = APInt::getHighBitsSet(32, 17);
   if (!DAG.MaskedValueIsZero(N1, Mask17) ||
       !DAG.MaskedValueIsZero(N0, Mask17))
     return SDValue();
 
-  // Use SplitBinaryOpsAndApply to handle AVX splitting.
-  auto PMADDWDBuilder = [](SelectionDAG &DAG, const SDLoc &DL,
-                           ArrayRef<SDValue> Ops) {
-    MVT VT = MVT::getVectorVT(MVT::i32, Ops[0].getValueSizeInBits() / 32);
-    return DAG.getNode(X86ISD::VPMADDWD, DL, VT, Ops);
-  };
-  return SplitBinaryOpsAndApply(DAG, Subtarget, SDLoc(N), VT,
-                                DAG.getBitcast(WVT, N0),
-                                DAG.getBitcast(WVT, N1), PMADDWDBuilder);
+  return getNodeAVXSplit(X86ISD::VPMADDWD, SDLoc(N), VT,
+                         { DAG.getBitcast(WVT, N0), DAG.getBitcast(WVT, N1) },
+                         DAG, Subtarget);
+}
+
+static SDValue combineMulToPMULDQ(SDNode *N, SelectionDAG &DAG,
+                                  const X86Subtarget &Subtarget) {
+  if (!Subtarget.hasSSE2())
+    return SDValue();
+
+  EVT VT = N->getValueType(0);
+
+  // Only support vXi64 vectors.
+  if (!VT.isVector() || VT.getVectorElementType() != MVT::i64 ||
+      !DAG.getTargetLoweringInfo().isTypeLegal(VT))
+    return SDValue();
+
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+
+  // MULDQ returns the 64-bit result of the signed multiplication of the lower
+  // 32-bits. We can lower with this if the sign bits stretch that far.
+  if (Subtarget.hasSSE41() && DAG.ComputeNumSignBits(N0) > 32 &&
+      DAG.ComputeNumSignBits(N1) > 32) {
+    return getNodeAVXSplit(X86ISD::PMULDQ, SDLoc(N), VT, { N0, N1 },
+                           DAG, Subtarget);
+  }
+
+  // If the upper bits are zero we can use a single pmuludq.
+  APInt Mask = APInt::getHighBitsSet(64, 32);
+  if (DAG.MaskedValueIsZero(N0, Mask) && DAG.MaskedValueIsZero(N1, Mask)) {
+    return getNodeAVXSplit(X86ISD::PMULUDQ, SDLoc(N), VT, { N0, N1 },
+                           DAG, Subtarget);
+  }
+
+  return SDValue();
 }
 
 /// Optimize a single multiply with constant into two operations in order to
 /// implement it with two cheaper instructions, e.g. LEA + SHL, LEA + LEA.
 static SDValue combineMul(SDNode *N, SelectionDAG &DAG,
                           TargetLowering::DAGCombinerInfo &DCI,
                           const X86Subtarget &Subtarget) {
   EVT VT = N->getValueType(0);
 
   if (SDValue V = combineMulToPMADDWD(N, DAG, Subtarget))
     return V;
 
+  if (SDValue V = combineMulToPMULDQ(N, DAG, Subtarget))
+    return V;
+
   if (DCI.isBeforeLegalize() && VT.isVector())
     return reduceVMULWidth(N, DAG, Subtarget);
 
   if (!MulConstantOptimization)
     return SDValue();
   // An imul is usually smaller than the alternative sequence.
   if (DAG.getMachineFunction().getFunction().optForMinSize())
     return SDValue();
 
   if (DCI.isBeforeLegalize() || DCI.isCalledByLegalizer())
     return SDValue();
 
   if (VT != MVT::i64 && VT != MVT::i32)
     return SDValue();
 
   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
   if (!C)
     return SDValue();
   uint64_t MulAmt = C->getZExtValue();
   if (isPowerOf2_64(MulAmt) || MulAmt == 3 || MulAmt == 5 || MulAmt == 9)
     return SDValue();
 
   uint64_t MulAmt1 = 0;
   uint64_t MulAmt2 = 0;
   if ((MulAmt % 9) == 0) {
     MulAmt1 = 9;
if (TLI.isOperationLegalOrPromote(Opcode, VT) &&
       return TruncateArithmetic(Op0, Op1);
     break;
   }
 
   case ISD::MUL:
     // X86 is rubbish at scalar and vector i64 multiplies (until AVX512DQ) - its
     // better to truncate if we have the chance.
     if (SrcVT.getScalarType() == MVT::i64 && TLI.isOperationLegal(Opcode, VT) &&
-        !Subtarget.hasDQI())
+        !TLI.isOperationLegal(Opcode, SrcVT))
       return TruncateArithmetic(Src.getOperand(0), Src.getOperand(1));
     LLVM_FALLTHROUGH;
   case ISD::ADD: {
     // TODO: ISD::SUB should be here but interferes with combineSubToSubus.
     SDValue Op0 = Src.getOperand(0);
     SDValue Op1 = Src.getOperand(1);
     if (TLI.isOperationLegal(Opcode, VT) &&
         IsRepeatedOpOrFreeTruncation(Op0, Op1))

test/CodeGen/X86/mulvi32.ll

 ; SSE2-NEXT:    pmuludq %xmm4, %xmm2
 ; SSE2-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm3[0],xmm1[1],xmm3[1]
 ; SSE2-NEXT:    pmuludq %xmm1, %xmm0
 ; SSE2-NEXT:    movdqa %xmm2, %xmm1
 ; SSE2-NEXT:    retq
 ;
 ; SSE42-LABEL: _mul4xi32toi64a:
 ; SSE42:       # %bb.0:
 ; SSE42-NEXT:    pxor %xmm3, %xmm3
 ; SSE42-NEXT:    pmovzxdq {{.*#+}} xmm4 = xmm0[0],zero,xmm0[1],zero
 ; SSE42-NEXT:    punpckhdq {{.*#+}} xmm0 = xmm0[2],xmm3[2],xmm0[3],xmm3[3]
 ; SSE42-NEXT:    pmovzxdq {{.*#+}} xmm2 = xmm1[0],zero,xmm1[1],zero
 ; SSE42-NEXT:    punpckhdq {{.*#+}} xmm1 = xmm1[2],xmm3[2],xmm1[3],xmm3[3]
 ; SSE42-NEXT:    pmuludq %xmm0, %xmm1
 ; SSE42-NEXT:    pmuludq %xmm4, %xmm2
 ; SSE42-NEXT:    movdqa %xmm2, %xmm0
 ; SSE42-NEXT:    retq
 ;
 ; AVX1-LABEL: _mul4xi32toi64a:
 ; AVX1:       # %bb.0:
-; AVX1-NEXT:    vpxor %xmm2, %xmm2, %xmm2
-; AVX1-NEXT:    vpunpckhdq {{.*#+}} xmm3 = xmm1[2],xmm2[2],xmm1[3],xmm2[3]
-; AVX1-NEXT:    vpunpckhdq {{.*#+}} xmm2 = xmm0[2],xmm2[2],xmm0[3],xmm2[3]
-; AVX1-NEXT:    vpmuludq %xmm3, %xmm2, %xmm2
-; AVX1-NEXT:    vpmovzxdq {{.*#+}} xmm1 = xmm1[0],zero,xmm1[1],zero
-; AVX1-NEXT:    vpmovzxdq {{.*#+}} xmm0 = xmm0[0],zero,xmm0[1],zero
-; AVX1-NEXT:    vpmuludq %xmm1, %xmm0, %xmm0
-; AVX1-NEXT:    vinsertf128 $1, %xmm2, %ymm0, %ymm0
+; AVX1-NEXT:    vmovd %xmm0, %r8d
+; AVX1-NEXT:    vpextrd $1, %xmm0, %r9d
+; AVX1-NEXT:    vpextrd $2, %xmm0, %edx
+; AVX1-NEXT:    vpextrd $3, %xmm0, %esi
+; AVX1-NEXT:    vmovd %xmm1, %r10d
+; AVX1-NEXT:    vpextrd $1, %xmm1, %eax
+; AVX1-NEXT:    vpextrd $2, %xmm1, %ecx
+; AVX1-NEXT:    vpextrd $3, %xmm1, %edi
+; AVX1-NEXT:    vmovq %rdi, %xmm0
+; AVX1-NEXT:    vmovq %rcx, %xmm1
+; AVX1-NEXT:    vpunpcklqdq {{.*#+}} xmm0 = xmm1[0],xmm0[0]
+; AVX1-NEXT:    vmovq %rsi, %xmm1
+; AVX1-NEXT:    vmovq %rdx, %xmm2
+; AVX1-NEXT:    vpunpcklqdq {{.*#+}} xmm1 = xmm2[0],xmm1[0]
+; AVX1-NEXT:    vpmuludq %xmm0, %xmm1, %xmm0
+; AVX1-NEXT:    vmovq %rax, %xmm1
+; AVX1-NEXT:    vmovq %r10, %xmm2
+; AVX1-NEXT:    vpunpcklqdq {{.*#+}} xmm1 = xmm2[0],xmm1[0]
+; AVX1-NEXT:    vmovq %r9, %xmm2
+; AVX1-NEXT:    vmovq %r8, %xmm3
+; AVX1-NEXT:    vpunpcklqdq {{.*#+}} xmm2 = xmm3[0],xmm2[0]
+; AVX1-NEXT:    vpmuludq %xmm1, %xmm2, %xmm1
+; AVX1-NEXT:    vinsertf128 $1, %xmm0, %ymm1, %ymm0
 ; AVX1-NEXT:    retq
 ;
 ; AVX2-LABEL: _mul4xi32toi64a:
 ; AVX2:       # %bb.0:
-; AVX2-NEXT:    vpxor %xmm2, %xmm2, %xmm2
-; AVX2-NEXT:    vpunpckhdq {{.*#+}} xmm3 = xmm0[2],xmm2[2],xmm0[3],xmm2[3]
-; AVX2-NEXT:    vpmovzxdq {{.*#+}} xmm0 = xmm0[0],zero,xmm0[1],zero
-; AVX2-NEXT:    vinserti128 $1, %xmm3, %ymm0, %ymm0
-; AVX2-NEXT:    vpunpckhdq {{.*#+}} xmm2 = xmm1[2],xmm2[2],xmm1[3],xmm2[3]
-; AVX2-NEXT:    vpmovzxdq {{.*#+}} xmm1 = xmm1[0],zero,xmm1[1],zero
-; AVX2-NEXT:    vinserti128 $1, %xmm2, %ymm1, %ymm1
+; AVX2-NEXT:    vmovd %xmm0, %r10d
+; AVX2-NEXT:    vpextrd $1, %xmm0, %ecx
+; AVX2-NEXT:    vpextrd $2, %xmm0, %edx
+; AVX2-NEXT:    vpextrd $3, %xmm0, %esi
+; AVX2-NEXT:    vmovd %xmm1, %r8d
+; AVX2-NEXT:    vpextrd $1, %xmm1, %r9d
+; AVX2-NEXT:    vpextrd $2, %xmm1, %edi
+; AVX2-NEXT:    vpextrd $3, %xmm1, %eax
+; AVX2-NEXT:    vmovq %rsi, %xmm0
+; AVX2-NEXT:    vmovq %rdx, %xmm1
+; AVX2-NEXT:    vpunpcklqdq {{.*#+}} xmm0 = xmm1[0],xmm0[0]
+; AVX2-NEXT:    vmovq %rcx, %xmm1
+; AVX2-NEXT:    vmovq %r10, %xmm2
+; AVX2-NEXT:    vpunpcklqdq {{.*#+}} xmm1 = xmm2[0],xmm1[0]
+; AVX2-NEXT:    vinserti128 $1, %xmm0, %ymm1, %ymm0
+; AVX2-NEXT:    vmovq %rax, %xmm1
+; AVX2-NEXT:    vmovq %rdi, %xmm2
+; AVX2-NEXT:    vpunpcklqdq {{.*#+}} xmm1 = xmm2[0],xmm1[0]
+; AVX2-NEXT:    vmovq %r9, %xmm2
+; AVX2-NEXT:    vmovq %r8, %xmm3
+; AVX2-NEXT:    vpunpcklqdq {{.*#+}} xmm2 = xmm3[0],xmm2[0]
+; AVX2-NEXT:    vinserti128 $1, %xmm1, %ymm2, %ymm1
 ; AVX2-NEXT:    vpmuludq %ymm1, %ymm0, %ymm0
 ; AVX2-NEXT:    retq
   %f00 = extractelement <4 x i32> %0, i32 0
   %f01 = extractelement <4 x i32> %0, i32 1
   %f02 = extractelement <4 x i32> %0, i32 2
   %f03 = extractelement <4 x i32> %0, i32 3
   %f10 = extractelement <4 x i32> %1, i32 0
   %f11 = extractelement <4 x i32> %1, i32 1