[TargetLowering] Add support for non-uniform vectors to BuildExactSDIV

[RKSimon]

Summary

This patch refactors the existing BuildExactSDIV implementation to support non-uniform constant vector denominators.

I've ended up duplicating much of the scalar/vector code pattern that I did for TargetLowering::BuildUDIV (D49248) - calling a 'BuildSDIVPattern' helper - does anyone have any suggestions how I could reduce this further? I'm going to end up doing the same again for TargetLowering::BuildSDIV as well when I get around to it.

[greened]

Is it possible to break this into a NFC refactor and a separate patch to handle non-uniform denominators?

[RKSimon]

In D50392#1191041, @greened wrote:

Is it possible to break this into a NFC refactor and a separate patch to handle non-uniform denominators?

Sure, pulling out the BuildSDIVPattern helper and the codegen is doable as an NFC. That would leave the patch mainly as the if(isVector()) .. else .. block

[greened]

Sure, pulling out the BuildSDIVPattern helper and the codegen is doable as an NFC. That would leave the patch mainly as the if(isVector()) .. else .. block

The intent would be to have the largish code changes not result in test changes and then the smaller functional change would be reflected in the tests.

[RKSimon]

Rebased.

I've refactored the approach slightly to demonstrate ISD::matchUnaryPredicate being used to iterate over a scalar or the elements of a vector. - this could be used in TargetLowering::BuildUDIV as well to make the equivalent code easier to understand.

[RKSimon]

ping?

[craig.topper]

test/CodeGen/X86/sdiv-exact.ll

2

Why are the features flags between 32-bit and 64-bit mismatched? This results in making 64-bit look way better than 32-bit in the modified test cases. For example test5 where 64-bit is one instruction.

[RKSimon]

test/CodeGen/X86/sdiv-exact.ll

2

Laziness mainly - I didn't see much gain from SSE2/AVX2 codegen tests for both 32/64 - its easy enough to add if you think its useful?

[craig.topper]

LGTM

test/CodeGen/X86/sdiv-exact.ll

2

I agree there's probably not much value. I just had to go up here to figure out why 64-bit looked so much better.

lib/CodeGen/SelectionDAG/TargetLowering.cpp

 /// Given an exact SDIV by a constant, create a multiplication
 /// with the multiplicative inverse of the constant.
 static SDValue BuildExactSDIV(const TargetLowering &TLI, SDNode *N,
                               const SDLoc &dl, SelectionDAG &DAG,
                               SmallVectorImpl<SDNode *> &Created) {
   SDValue Op0 = N->getOperand(0);
   SDValue Op1 = N->getOperand(1);
   EVT VT = N->getValueType(0);
+  EVT SVT = VT.getScalarType();
   EVT ShVT = TLI.getShiftAmountTy(VT, DAG.getDataLayout());
+  EVT ShSVT = ShVT.getScalarType();
 
-  auto BuildSDIVPattern = [](APInt Divisor, unsigned &Shift, APInt &Factor) {
-    bool UseSRA = false;
-    Shift = Divisor.countTrailingZeros();
+  SmallVector<SDValue, 16> Shifts, Factors;
+
+  auto BuildSDIVPattern = [&](ConstantSDNode *C) {
+    if (C->isNullValue())
+      return false;
+    APInt Divisor = C->getAPIntValue();
+    unsigned Shift = Divisor.countTrailingZeros();
     if (Shift) {
       Divisor.ashrInPlace(Shift);
       UseSRA = true;
     }
     // Calculate the multiplicative inverse, using Newton's method.
     APInt t;
-    Factor = Divisor;
+    APInt Factor = Divisor;
     while ((t = Divisor * Factor) != 1)
       Factor *= APInt(Divisor.getBitWidth(), 2) - t;
-    return UseSRA;
+    Shifts.push_back(DAG.getConstant(Shift, dl, ShSVT));
+    Factors.push_back(DAG.getConstant(Factor, dl, SVT));
+    return true;
   };
 
-  ConstantSDNode *C = isConstOrConstSplat(Op1);
-  if (!C || C->isNullValue())
+  // Collect all magic values from the build vector.
+  if (!ISD::matchUnaryPredicate(Op1, BuildSDIVPattern))
     return SDValue();
 
-  APInt FactorVal;
-  unsigned ShiftVal;
-  bool UseSRA = BuildSDIVPattern(C->getAPIntValue(), ShiftVal, FactorVal);
-  SDValue Shift = DAG.getConstant(ShiftVal, dl, ShVT);
-  SDValue Factor = DAG.getConstant(FactorVal, dl, VT);
+  SDValue Shift, Factor;
+  if (VT.isVector()) {
+    Shift = DAG.getBuildVector(ShVT, dl, Shifts);
+    Factor = DAG.getBuildVector(VT, dl, Factors);
+  } else {
+    Shift = Shifts[0];
+    Factor = Factors[0];
+  }
 
   SDValue Res = Op0;
 
   // Shift the value upfront if it is even, so the LSB is one.
   if (UseSRA) {
     // TODO: For UDIV use SRL instead of SRA.
     SDNodeFlags Flags;
     Flags.setExact(true);

test/CodeGen/X86/sdiv-exact.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown -mattr=+sse2 | FileCheck %s --check-prefix=X86
 ; RUN: llc < %s -mtriple=x86_64-unknown -mattr=+avx2 | FileCheck %s --check-prefix=X64
 
 define i32 @test1(i32 %x) {
 ; X86-LABEL: test1:
 ; X86:       # %bb.0:
 ; X86-NEXT:    imull $-1030792151, {{[0-9]+}}(%esp), %eax # imm = 0xC28F5C29
 ; X86-NEXT:    retl
 ;

 ; X64-NEXT:    retq
   %div = sdiv exact <4 x i32> %x, <i32 25, i32 25, i32 25, i32 25>
   ret <4 x i32> %div
 }
 
 define <4 x i32> @test5(<4 x i32> %x) {
 ; X86-LABEL: test5:
 ; X86:       # %bb.0:
-; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm0[3,1,2,3]
-; X86-NEXT:    movd %xmm1, %eax
-; X86-NEXT:    imull $-1030792151, %eax, %eax # imm = 0xC28F5C29
-; X86-NEXT:    movd %eax, %xmm1
-; X86-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[2,3,0,1]
-; X86-NEXT:    movd %xmm2, %eax
-; X86-NEXT:    imull $-1030792151, %eax, %eax # imm = 0xC28F5C29
-; X86-NEXT:    movd %eax, %xmm2
-; X86-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
-; X86-NEXT:    movd %xmm0, %eax
-; X86-NEXT:    sarl $3, %eax
-; X86-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X86-NEXT:    movd %eax, %xmm1
-; X86-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[1,1,2,3]
-; X86-NEXT:    movd %xmm0, %eax
-; X86-NEXT:    sarl $3, %eax
-; X86-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X86-NEXT:    movd %eax, %xmm0
-; X86-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1]
-; X86-NEXT:    punpcklqdq {{.*#+}} xmm1 = xmm1[0],xmm2[0]
-; X86-NEXT:    movdqa %xmm1, %xmm0
+; X86-NEXT:    movdqa {{.*#+}} xmm1 = [2863311531,2863311531,3264175145,3264175145]
+; X86-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[1,1,3,3]
+; X86-NEXT:    pmuludq %xmm1, %xmm0
+; X86-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]
+; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; X86-NEXT:    pmuludq %xmm2, %xmm1
+; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; X86-NEXT:    punpckldq {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test5:
 ; X64:       # %bb.0:
-; X64-NEXT:    vpextrd $1, %xmm0, %eax
-; X64-NEXT:    sarl $3, %eax
-; X64-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X64-NEXT:    vmovd %xmm0, %ecx
-; X64-NEXT:    sarl $3, %ecx
-; X64-NEXT:    imull $-1431655765, %ecx, %ecx # imm = 0xAAAAAAAB
-; X64-NEXT:    vmovd %ecx, %xmm1
-; X64-NEXT:    vpinsrd $1, %eax, %xmm1, %xmm1
-; X64-NEXT:    vpextrd $2, %xmm0, %eax
-; X64-NEXT:    imull $-1030792151, %eax, %eax # imm = 0xC28F5C29
-; X64-NEXT:    vpinsrd $2, %eax, %xmm1, %xmm1
-; X64-NEXT:    vpextrd $3, %xmm0, %eax
-; X64-NEXT:    imull $-1030792151, %eax, %eax # imm = 0xC28F5C29
-; X64-NEXT:    vpinsrd $3, %eax, %xmm1, %xmm0
+; X64-NEXT:    vpmulld {{.*}}(%rip), %xmm0, %xmm0
 ; X64-NEXT:    retq
   %div = sdiv exact <4 x i32> %x, <i32 24, i32 24, i32 25, i32 25>
   ret <4 x i32> %div
 }
 
 define <4 x i32> @test6(<4 x i32> %x) {
 ; X86-LABEL: test6:
 ; X86:       # %bb.0:
-; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm0[3,1,2,3]
-; X86-NEXT:    movd %xmm1, %eax
-; X86-NEXT:    sarl %eax
-; X86-NEXT:    imull $-991146299, %eax, %eax # imm = 0xC4EC4EC5
-; X86-NEXT:    movd %eax, %xmm1
-; X86-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[2,3,0,1]
-; X86-NEXT:    movd %xmm2, %eax
-; X86-NEXT:    sarl %eax
-; X86-NEXT:    imull $-991146299, %eax, %eax # imm = 0xC4EC4EC5
-; X86-NEXT:    movd %eax, %xmm2
-; X86-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
-; X86-NEXT:    movd %xmm0, %eax
-; X86-NEXT:    sarl $3, %eax
-; X86-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X86-NEXT:    movd %eax, %xmm1
-; X86-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[1,1,2,3]
-; X86-NEXT:    movd %xmm0, %eax
-; X86-NEXT:    sarl $3, %eax
-; X86-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X86-NEXT:    movd %eax, %xmm0
+; X86-NEXT:    movdqa %xmm0, %xmm1
+; X86-NEXT:    psrad $3, %xmm1
+; X86-NEXT:    psrad $1, %xmm0
+; X86-NEXT:    movsd {{.*#+}} xmm0 = xmm1[0],xmm0[1]
+; X86-NEXT:    movdqa {{.*#+}} xmm2 = [2863311531,2863311531,3303820997,3303820997]
+; X86-NEXT:    movapd %xmm0, %xmm1
+; X86-NEXT:    pmuludq %xmm2, %xmm1
+; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; X86-NEXT:    shufps {{.*#+}} xmm0 = xmm0[1,1,3,3]
+; X86-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
+; X86-NEXT:    pmuludq %xmm0, %xmm2
+; X86-NEXT:    pshufd {{.*#+}} xmm0 = xmm2[0,2,2,3]
 ; X86-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1]
-; X86-NEXT:    punpcklqdq {{.*#+}} xmm1 = xmm1[0],xmm2[0]
 ; X86-NEXT:    movdqa %xmm1, %xmm0
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test6:
 ; X64:       # %bb.0:
-; X64-NEXT:    vpextrd $1, %xmm0, %eax
-; X64-NEXT:    sarl $3, %eax
-; X64-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X64-NEXT:    vmovd %xmm0, %ecx
-; X64-NEXT:    sarl $3, %ecx
-; X64-NEXT:    imull $-1431655765, %ecx, %ecx # imm = 0xAAAAAAAB
-; X64-NEXT:    vmovd %ecx, %xmm1
-; X64-NEXT:    vpinsrd $1, %eax, %xmm1, %xmm1
-; X64-NEXT:    vpextrd $2, %xmm0, %eax
-; X64-NEXT:    sarl %eax
-; X64-NEXT:    imull $-991146299, %eax, %eax # imm = 0xC4EC4EC5
-; X64-NEXT:    vpinsrd $2, %eax, %xmm1, %xmm1
-; X64-NEXT:    vpextrd $3, %xmm0, %eax
-; X64-NEXT:    sarl %eax
-; X64-NEXT:    imull $-991146299, %eax, %eax # imm = 0xC4EC4EC5
-; X64-NEXT:    vpinsrd $3, %eax, %xmm1, %xmm0
+; X64-NEXT:    vpsravd {{.*}}(%rip), %xmm0, %xmm0
+; X64-NEXT:    vpmulld {{.*}}(%rip), %xmm0, %xmm0
 ; X64-NEXT:    retq
   %div = sdiv exact <4 x i32> %x, <i32 24, i32 24, i32 26, i32 26>
   ret <4 x i32> %div
 }
 
 define <4 x i32> @test7(<4 x i32> %x) {
 ; X86-LABEL: test7:
 ; X86:       # %bb.0:
-; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm0[3,1,2,3]
-; X86-NEXT:    movd %xmm1, %eax
-; X86-NEXT:    imull $1749801491, %eax, %eax # imm = 0x684BDA13
-; X86-NEXT:    movd %eax, %xmm1
-; X86-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[2,3,0,1]
-; X86-NEXT:    movd %xmm2, %eax
-; X86-NEXT:    imull $1749801491, %eax, %eax # imm = 0x684BDA13
-; X86-NEXT:    movd %eax, %xmm2
-; X86-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
-; X86-NEXT:    movd %xmm0, %eax
-; X86-NEXT:    imull $-1030792151, %eax, %eax # imm = 0xC28F5C29
-; X86-NEXT:    movd %eax, %xmm1
-; X86-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[1,1,2,3]
-; X86-NEXT:    movd %xmm0, %eax
-; X86-NEXT:    imull $-1030792151, %eax, %eax # imm = 0xC28F5C29
-; X86-NEXT:    movd %eax, %xmm0
-; X86-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1]
-; X86-NEXT:    punpcklqdq {{.*#+}} xmm1 = xmm1[0],xmm2[0]
-; X86-NEXT:    movdqa %xmm1, %xmm0
+; X86-NEXT:    movdqa {{.*#+}} xmm1 = [3264175145,3264175145,1749801491,1749801491]
+; X86-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[1,1,3,3]
+; X86-NEXT:    pmuludq %xmm1, %xmm0
+; X86-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]
+; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; X86-NEXT:    pmuludq %xmm2, %xmm1
+; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; X86-NEXT:    punpckldq {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test7:
 ; X64:       # %bb.0:
-; X64-NEXT:    vpextrd $1, %xmm0, %eax
-; X64-NEXT:    imull $-1030792151, %eax, %eax # imm = 0xC28F5C29
-; X64-NEXT:    vmovd %xmm0, %ecx
-; X64-NEXT:    imull $-1030792151, %ecx, %ecx # imm = 0xC28F5C29
-; X64-NEXT:    vmovd %ecx, %xmm1
-; X64-NEXT:    vpinsrd $1, %eax, %xmm1, %xmm1
-; X64-NEXT:    vpextrd $2, %xmm0, %eax
-; X64-NEXT:    imull $1749801491, %eax, %eax # imm = 0x684BDA13
-; X64-NEXT:    vpinsrd $2, %eax, %xmm1, %xmm1
-; X64-NEXT:    vpextrd $3, %xmm0, %eax
-; X64-NEXT:    imull $1749801491, %eax, %eax # imm = 0x684BDA13
-; X64-NEXT:    vpinsrd $3, %eax, %xmm1, %xmm0
+; X64-NEXT:    vpmulld {{.*}}(%rip), %xmm0, %xmm0
 ; X64-NEXT:    retq
   %div = sdiv exact <4 x i32> %x, <i32 25, i32 25, i32 27, i32 27>
   ret <4 x i32> %div
 }
 
 define <4 x i32> @test8(<4 x i32> %x) {
 ; X86-LABEL: test8:
 ; X86:       # %bb.0:
-; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm0[2,3,0,1]
-; X86-NEXT:    movd %xmm1, %eax
-; X86-NEXT:    sarl $3, %eax
-; X86-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X86-NEXT:    movd %eax, %xmm1
-; X86-NEXT:    shufps {{.*#+}} xmm1 = xmm1[0,0],xmm0[3,0]
-; X86-NEXT:    movaps %xmm0, %xmm2
-; X86-NEXT:    shufps {{.*#+}} xmm2 = xmm2[0,1],xmm1[0,2]
-; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm0[3,1,2,3]
-; X86-NEXT:    movd %xmm1, %eax
-; X86-NEXT:    sarl $3, %eax
-; X86-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X86-NEXT:    movd %eax, %xmm1
-; X86-NEXT:    shufps {{.*#+}} xmm1 = xmm1[0,0],xmm2[2,0]
-; X86-NEXT:    shufps {{.*#+}} xmm0 = xmm0[0,1],xmm1[2,0]
+; X86-NEXT:    movdqa %xmm0, %xmm1
+; X86-NEXT:    psrad $3, %xmm1
+; X86-NEXT:    movsd {{.*#+}} xmm1 = xmm0[0],xmm1[1]
+; X86-NEXT:    movdqa {{.*#+}} xmm2 = [1,1,2863311531,2863311531]
+; X86-NEXT:    movapd %xmm1, %xmm0
+; X86-NEXT:    pmuludq %xmm2, %xmm0
+; X86-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]
+; X86-NEXT:    shufps {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; X86-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
+; X86-NEXT:    pmuludq %xmm1, %xmm2
+; X86-NEXT:    pshufd {{.*#+}} xmm1 = xmm2[0,2,2,3]
+; X86-NEXT:    punpckldq {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test8:
 ; X64:       # %bb.0:
-; X64-NEXT:    vpextrd $2, %xmm0, %eax
-; X64-NEXT:    sarl $3, %eax
-; X64-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X64-NEXT:    vpinsrd $2, %eax, %xmm0, %xmm1
-; X64-NEXT:    vpextrd $3, %xmm0, %eax
-; X64-NEXT:    sarl $3, %eax
-; X64-NEXT:    imull $-1431655765, %eax, %eax # imm = 0xAAAAAAAB
-; X64-NEXT:    vpinsrd $3, %eax, %xmm1, %xmm0
+; X64-NEXT:    vpsravd {{.*}}(%rip), %xmm0, %xmm0
+; X64-NEXT:    vpmulld {{.*}}(%rip), %xmm0, %xmm0
 ; X64-NEXT:    retq
   %div = sdiv exact <4 x i32> %x, <i32 1, i32 1, i32 24, i32 24>
   ret <4 x i32> %div
 }