[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

33117

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

33117

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);
       }

 // Useful for operations that are available on SSE2 in 128-bit, on AVX2 in
 // 256-bit and on AVX512BW in 512-bit. The argument VT is the type used for
 // deciding if/how to split Ops. Ops elements do *not* have to be of type VT.
 // The argument Builder is a function that will be applied on each split part:
 // SDValue Builder(SelectionDAG&G, SDLoc, ArrayRef<SDValue>)
 template <typename F>
 SDValue SplitOpsAndApply(SelectionDAG &DAG, const X86Subtarget &Subtarget,
                          const SDLoc &DL, EVT VT, ArrayRef<SDValue> Ops,
-                         F Builder) {
+                         F Builder, bool CheckBWI = true) {
   assert(Subtarget.hasSSE2() && "Target assumed to support at least SSE2");
   unsigned NumSubs = 1;
-  if (Subtarget.useBWIRegs()) {
+  if ((CheckBWI && Subtarget.useBWIRegs()) ||
+      (!CheckBWI && Subtarget.useAVX512Regs())) {
     if (VT.getSizeInBits() > 512) {
       NumSubs = VT.getSizeInBits() / 512;
       assert((VT.getSizeInBits() % 512) == 0 && "Illegal vector size");
     }
   } else if (Subtarget.hasAVX2()) {
     if (VT.getSizeInBits() > 256) {
       NumSubs = VT.getSizeInBits() / 256;
       assert((VT.getSizeInBits() % 256) == 0 && "Illegal vector size");
SDValue SplitOpsAndApply(SelectionDAG &DAG, const X86Subtarget &Subtarget,
   return DAG.getNode(ISD::CONCAT_VECTORS, DL, VT, Subs);
 }
 
 // Helper for splitting operands of a binary operation to legal target size and
 // apply a function on each part.
 template <typename F>
 SDValue SplitBinaryOpsAndApply(SelectionDAG &DAG, const X86Subtarget &Subtarget,
                                const SDLoc &DL, EVT VT, SDValue Op0,
-                               SDValue Op1, F Builder) {
+                               SDValue Op1, F Builder, bool CheckBWI = true) {
   SDValue Ops[] = {Op0, Op1};
-  return SplitOpsAndApply(DAG, Subtarget, DL, VT, makeArrayRef(Ops), Builder);
+  return SplitOpsAndApply(DAG, Subtarget, DL, VT, makeArrayRef(Ops), Builder,
+                          CheckBWI);
 }
 
 // Return true if the instruction zeroes the unused upper part of the
 // destination and accepts mask.
 static bool isMaskedZeroUpperBitsvXi1(unsigned int Opcode) {
   switch (Opcode) {
   default:
     return false;
if (VT == MVT::v4i32) {
     // Merge the two vectors back together with a shuffle. This expands into 2
     // 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);
-  }
+  assert(!Subtarget.hasDQI() && "DQI should use MULLQ");
 
   //  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 AloBlo + Hi;
   APInt LowerBitsMask = APInt::getLowBitsSet(64, 32);
   bool ALoIsZero = DAG.MaskedValueIsZero(A, LowerBitsMask);
   bool BLoIsZero = DAG.MaskedValueIsZero(B, LowerBitsMask);
 
   APInt UpperBitsMask = APInt::getHighBitsSet(64, 32);
   bool AHiIsZero = DAG.MaskedValueIsZero(A, UpperBitsMask);
   bool BHiIsZero = DAG.MaskedValueIsZero(B, UpperBitsMask);
 
-  // If DQI is supported we can use MULLQ, but MULUDQ is still better if the
-  // the high bits are known to be zero.
-  if (Subtarget.hasDQI() && (!AHiIsZero || !BHiIsZero))
-    return Op;
-
   SDValue Zero = getZeroVector(VT, Subtarget, DAG, dl);
 
   // Only multiply lo/hi halves that aren't known to be zero.
   SDValue AloBlo = Zero;
   if (!ALoIsZero && !BLoIsZero)
     AloBlo = DAG.getNode(X86ISD::PMULUDQ, dl, VT, A, B);
 
   SDValue AloBhi = Zero;
auto PMADDWDBuilder = [](SelectionDAG &DAG, const SDLoc &DL,
     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);
 }
 
+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) {
+    auto PMULDQBuilder = [](SelectionDAG &DAG, const SDLoc &DL,
+                            ArrayRef<SDValue> Ops) {
+      return DAG.getNode(X86ISD::PMULDQ, DL, Ops[0].getValueType(), Ops);
+    };
+    return SplitBinaryOpsAndApply(DAG, Subtarget, SDLoc(N), VT,
+                                  N0, N1, PMULDQBuilder, /*CheckBWI*/false);
+  }
+
+  // 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)) {
+    auto PMULDQBuilder = [](SelectionDAG &DAG, const SDLoc &DL,
+                            ArrayRef<SDValue> Ops) {
+      return DAG.getNode(X86ISD::PMULUDQ, DL, Ops[0].getValueType(), Ops);
+    };
+    return SplitBinaryOpsAndApply(DAG, Subtarget, SDLoc(N), VT,
+                                  N0, N1, PMULDQBuilder, /*CheckBWI*/false);
+  }
+
+  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 (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