[DAGCombiner] Extending pattern detection for vector shuffle.

[jbhateja]

Summary

If all the operands of a BUILD_VECTOR extract elements from same vector then split the
vector efficiently based on the maximum vector access index.

This will also fix PR 33784

[zvi]

test/CodeGen/X86/pr33784-vector-shuffle.ll

1 ↗

(On Diff #107862)

Can you please commit the test and re-apply the patch so that we can see the change in the generated code?

[RKSimon]

test/CodeGen/X86/pr33784-vector-shuffle.ll

1 ↗

(On Diff #107862)

Please can you add this test to shuffle-vs-trunc-512.ll instead of creating a new test file?

[zvi]

See D35700 where pr33784 is handled a bit differently.

test/CodeGen/X86/pr33784-vector-shuffle.ll

1 ↗

(On Diff #107862)

This case already exists in test/CodeGen/X86/shuffle-strided-with-offset-512.ll?
Can you please verify you are rebased on top-of-trunk?

[jbhateja]

Hi Zvi , I'm in process of uploading patch post rebase which should show the changes in asm with the diff. Thanks

[jbhateja]

Patch updation post rebase.

[jbhateja]

Hi Simon, Zvi since D35700 also taking care of shuffle_vectors extraction, and this patch is also extending the pattern should it be ok to merge this patch with it.

[zvi]

IIUC, this patch affect reduceBuildVecToShuffle(). D35700 affect the reduceBuildVecToTruncate() which has precedence to fire before reduceBuildVecToShuffle(), so would it make sense that you rebase this patch on top of D35700, assuming D35700 will be approved.

[RKSimon]

In D35788#821310, @zvi wrote:

IIUC, this patch affect reduceBuildVecToShuffle(). D35700 affect the reduceBuildVecToTruncate() which has precedence to fire before reduceBuildVecToShuffle(), so would it make sense that you rebase this patch on top of D35700, assuming D35700 will be approved.

+1

[jbhateja]

Updating post rebase.

Splitting of a vector argument of shuffle vector based on extracted shuffle_mask from the build_vector
is pattern independent w.r.t shuffle mask and looks at the maximal index of vector access.

[zvi]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14266

Please fix indentation to units of two spaces. The clang-format tool can help.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14215

Very minor - but please keep these newlines - it makes everything easier to understand!

[jbhateja]

Resolving formatting comments.

[RKSimon]

A few minors but it looks like its almost there

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14090

SDValue has a bool operator for this - you should be able to just test with:

if (!(VecIn1 && VecIn2 &&

14301

Add a TODO to support UNDEF and zero entries?

14316

Don't calculate NearestPow2 inside the if, pull it out and just test for non-zero NearestPow2 in the if:

NearestPow2 = PowerOf2Ceil(MaxIndex);
if (NearestPow2 && ((NumElems * 2) < NearestPow2)) {

14318

Isn't this just SplitSize > 1 ?

[jbhateja]

Review comment resolution.

[jbhateja]

@Reviewers : All the comments have been resolved. Thanks

[jbhateja]

Ping @ reviewers.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14090

Is there any case where VecIn1 can be null? InVT1 above assumes not

14315

You can use std::max here

[jbhateja]

Review comments resolution.

[RKSimon]

A few final minor comments, but otherwise LGTM

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14092

Add an explanation comment. It might be more obvious if you 'de-morgan'-ising the if() as well (but that's up to you):

if (!VecIn2 || VecIn1.getOpcode() != ISD::EXTRACT_SUBVECTOR ||
    VecIn2.getOpcode() !== ISD::EXTRACT_SUBVECTOR ||
    VecIn1.getOperand(0) != VecIn2.getOperand(0))

14321

You can probably do the test as NearestPow2 > 2, and merge it with the outer if and pull SplitSize inside:

if (NearestPow2 > 2 && ((NumElems * 2) < NearestPow2)) {
  unsigned SplitSize = NearestPow2 / 2;
  EVT SplitVT = ......

[jbhateja]

• Updations to tests post commit rL309963.
• Synthetic changes to cover review comments.
• Merge branch 'master' of git://github.com/llvm-mirror/llvm

[RKSimon]

LGTM (again)

[jbhateja]

Please land this in trunk if its ok. I do not have commit rights yet.
Thanks

[RKSimon]

Reopening as it was reverted at rL310118 due to PR34073

[RKSimon]

PR34073

[jbhateja]

• Merge branch 'master' of git://github.com/llvm-mirror/llvm
• D35788 : Limiting this patch to simple value types.

[RKSimon]

Is there a suitable repro test from PR34073 that you can add?

[jbhateja]

In D35788#835018, @RKSimon wrote:

Is there a suitable repro test from PR34073 that you can add?

PR34073 is a huge .cpp test which is running fine now.
There already exist a test case "test/CodeGen/X86/oddshuffles.ll" where shuffle
vector with non-simple vector type was getting split earlier is now not splitting the vector.

[jbhateja]

Hi Simon, Can you please update this patch in trunk. Thanks

[jbhateja]

@ Simon, patch has been updated and good to land, please let me know if anything more is needed here.
Thanks

[jbhateja]

Hi Simon, patch has been updated and good to land, please let me know if anything more is needed here.
Thanks

[jbhateja]

This comment was removed by jbhateja.

[RKSimon]

LGTM

@jbhateja Sorry for the delay - I highly recommend that you request commit rights yourself

[jbhateja]

Thanks Simon

[eladcohen]

Reopening as it was reverted at rL310822 due to PR34175.

[jbhateja]

• Handling for undef in vector shuffle mask.
• Fix for PR34175 caused due to l310782

[chandlerc]

Folks, please consider using utils/shuffle_fuzz.py or some other fuzz testing device. The number of times this lands and gets reverted is becoming fairly disruptive.

[jbhateja]

• Rebasing patch to latest trunk.
• Merge branch 'master' of git://github.com/llvm-mirror/llvm

[jbhateja]

• Updating test case ref post rebase

[jbhateja]

Closed by commit rL311255: [DAGCombiner] Extending pattern detection for vector shuffle.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::createBuildVecShuffle(const SDLoc &DL, SDNode *N,
                                            unsigned LeftIdx) {
   MVT IdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());
   SDValue ZeroIdx = DAG.getConstant(0, DL, IdxTy);
 
   EVT VT = N->getValueType(0);
   EVT InVT1 = VecIn1.getValueType();
   EVT InVT2 = VecIn2.getNode() ? VecIn2.getValueType() : InVT1;
 
-  unsigned Vec2Offset = InVT1.getVectorNumElements();
+  unsigned Vec2Offset = 0;
   unsigned NumElems = VT.getVectorNumElements();
   unsigned ShuffleNumElems = NumElems;
 
+  if (!(VecIn1.getNode()  && VecIn2.getNode() &&
+       (VecIn1.getOpcode()   == ISD::EXTRACT_SUBVECTOR) &&
+       (VecIn2.getOpcode()   == ISD::EXTRACT_SUBVECTOR) &&
+       (VecIn1.getOperand(0) == VecIn2.getOperand(0))))
+    Vec2Offset = InVT1.getVectorNumElements();
+
   // We can't generate a shuffle node with mismatched input and output types.
   // Try to make the types match the type of the output.
   if (InVT1 != VT || InVT2 != VT) {
     if ((VT.getSizeInBits() % InVT1.getSizeInBits() == 0) && InVT1 == InVT2) {
       // If the output vector length is a multiple of both input lengths,
       // we can concatenate them and pad the rest with undefs.
       unsigned NumConcats = VT.getSizeInBits() / InVT1.getSizeInBits();
       assert(NumConcats >= 2 && "Concat needs at least two inputs!");
SDValue DAGCombiner::reduceBuildVecToShuffle(SDNode *N) {
   unsigned NumElems = N->getNumOperands();
 
   // Record, for each element of the newly built vector, which input vector
   // that element comes from. -1 stands for undef, 0 for the zero vector,
   // and positive values for the input vectors.
   // VectorMask maps each element to its vector number, and VecIn maps vector
   // numbers to their initial SDValues.
 
+  unsigned ValidElems = 0;
   SmallVector<int, 8> VectorMask(NumElems, -1);
   SmallVector<SDValue, 8> VecIn;
   VecIn.push_back(SDValue());
-
   for (unsigned i = 0; i != NumElems; ++i) {
     SDValue Op = N->getOperand(i);
-
     if (Op.isUndef())
       continue;
 
     // See if we can use a blend with a zero vector.
     // TODO: Should we generalize this to a blend with an arbitrary constant
     // vector?
     if (isNullConstant(Op) || isNullFPConstant(Op)) {
       UsesZeroVector = true;
       VectorMask[i] = 0;
       continue;
     }
-
     // Not an undef or zero. If the input is something other than an
     // EXTRACT_VECTOR_ELT with a constant index, bail out.
     if (Op.getOpcode() != ISD::EXTRACT_VECTOR_ELT ||
         !isa<ConstantSDNode>(Op.getOperand(1)))
       return SDValue();
-
     SDValue ExtractedFromVec = Op.getOperand(0);
 
     // All inputs must have the same element type as the output.
     if (VT.getVectorElementType() !=
         ExtractedFromVec.getValueType().getVectorElementType())
       return SDValue();
 
     // Have we seen this input vector before?
     // The vectors are expected to be tiny (usually 1 or 2 elements), so using
     // a map back from SDValues to numbers isn't worth it.
     unsigned Idx = std::distance(
         VecIn.begin(), std::find(VecIn.begin(), VecIn.end(), ExtractedFromVec));
     if (Idx == VecIn.size())
       VecIn.push_back(ExtractedFromVec);
-
     VectorMask[i] = Idx;
+    ValidElems++;
   }
 
   // If we didn't find at least one input vector, bail out.
   if (VecIn.size() < 2)
     return SDValue();
   
+  // If all the Operands of BUILD_VECTOR extract from same
+  // vector, then split the vector efficiently based on the maximum 
+  // vector access index and adjust the VectorMask and
+  // VecIn accordingly.
+  if (VecIn.size() == 2 && NumElems == ValidElems) {
+     unsigned MaxIndex = 0;
+     unsigned NearestPow2 = 0;
+     SDValue Vec = VecIn.back();
+     EVT InVT    = Vec.getValueType();
+     MVT IdxTy   = TLI.getVectorIdxTy(DAG.getDataLayout());
+     SmallVector<unsigned, 8> IndexVec(NumElems, 0);
+
+     for(unsigned i = 0 ; i < NumElems ; i++) {
+          unsigned Index = N->getOperand(i).getConstantOperandVal(1);
+          IndexVec[i] = Index;
+          MaxIndex = (MaxIndex < Index) ? Index : MaxIndex;
+     }
+     if ((NearestPow2 = PowerOf2Ceil(MaxIndex)) && ((NumElems*2) < NearestPow2)) {
+        unsigned SplitSize = NearestPow2 / 2;
+        if ( 0 == SplitSize % 2) {
+           EVT SplitVT = EVT::getVectorVT(*DAG.getContext(),
+                                          InVT.getVectorElementType(), SplitSize);
+           SDValue VecIn2 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, SplitVT, Vec,
+                                        DAG.getConstant(SplitSize, DL, IdxTy));
+           SDValue VecIn1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, SplitVT, Vec,
+                                        DAG.getConstant(0, DL, IdxTy));
+           VecIn.pop_back();
+           VecIn.push_back(VecIn1); 
+           VecIn.push_back(VecIn2); 
+
+           for(unsigned i = 0 ; i < NumElems ; i++)
+              VectorMask[i] = (IndexVec[i] < SplitSize) ? 1 : 2;
+        }
+     }
+  }
+
   // TODO: We want to sort the vectors by descending length, so that adjacent
   // pairs have similar length, and the longer vector is always first in the
   // pair.
 
   // TODO: Should this fire if some of the input vectors has illegal type (like
   // it does now), or should we let legalization run its course first?
 
   // Shuffle phase:
   // Take pairs of vectors, and shuffle them so that the result has elements
   // from these vectors in the correct places.
   // For example, given:
   // t10: i32 = extract_vector_elt t1, Constant:i64<0>
   // t11: i32 = extract_vector_elt t2, Constant:i64<0>
   // t12: i32 = extract_vector_elt t3, Constant:i64<0>
   // t13: i32 = extract_vector_elt t1, Constant:i64<1>
   // t14: v4i32 = BUILD_VECTOR t10, t11, t12, t13
   // We will generate:
   // t20: v4i32 = vector_shuffle<0,4,u,1> t1, t2
   // t21: v4i32 = vector_shuffle<u,u,0,u> t3, undef
   SmallVector<SDValue, 4> Shuffles;
   for (unsigned In = 0, Len = (VecIn.size() / 2); In < Len; ++In) {
     unsigned LeftIdx = 2 * In + 1;
     SDValue VecLeft = VecIn[LeftIdx];
     SDValue VecRight =
         (LeftIdx + 1) < VecIn.size() ? VecIn[LeftIdx + 1] : SDValue();
 
     if (SDValue Shuffle = createBuildVecShuffle(DL, N, VectorMask, VecLeft,
                                                 VecRight, LeftIdx))
       Shuffles.push_back(Shuffle);
     else
       return SDValue();
   }
for (unsigned In = 0, Len = CurSize / 2; In < Len; ++In) {
           VectorMask[i] = In;
         }
       }
 
       Shuffles[In] =
           DAG.getVectorShuffle(VT, DL, Shuffles[Left], Shuffles[Right], Mask);
     }
   }
-
   return Shuffles[0];
 }
 
 // Check to see if this is a BUILD_VECTOR of a bunch of EXTRACT_VECTOR_ELT
 // operations which can be matched to a truncate or to a shuffle-truncate.
 SDValue DAGCombiner::reduceBuildVecToTrunc(SDNode *N) {
   // TODO: Add support for big-endian.
   if (DAG.getDataLayout().isBigEndian())

test/CodeGen/X86/oddshuffles.ll

 ; AVX1-NEXT:    vmovdqu %xmm3, (%rsi)
 ; AVX1-NEXT:    vmovdqu %xmm4, (%rdx)
 ; AVX1-NEXT:    vmovdqu %xmm0, (%rcx)
 ; AVX1-NEXT:    vzeroupper
 ; AVX1-NEXT:    retq
 ;
 ; AVX2-LABEL: interleave_24i16_out:
 ; AVX2:       # BB#0:
-; AVX2-NEXT:    vmovdqu (%rdi), %ymm0
-; AVX2-NEXT:    vmovdqu 32(%rdi), %xmm1
-; AVX2-NEXT:    vpblendw {{.*#+}} ymm2 = ymm0[0,1],ymm1[2],ymm0[3,4],ymm1[5],ymm0[6,7,8,9],ymm1[10],ymm0[11,12],ymm1[13],ymm0[14,15]
+; AVX2-NEXT:    vmovdqu 32(%rdi), %xmm0
+; AVX2-NEXT:    vmovdqu (%rdi), %ymm1
+; AVX2-NEXT:    vpblendw {{.*#+}} ymm2 = ymm1[0,1],ymm0[2],ymm1[3,4],ymm0[5],ymm1[6,7,8,9],ymm0[10],ymm1[11,12],ymm0[13],ymm1[14,15]
 ; AVX2-NEXT:    vextracti128 $1, %ymm2, %xmm3
 ; AVX2-NEXT:    vpblendw {{.*#+}} xmm2 = xmm2[0],xmm3[1],xmm2[2,3],xmm3[4],xmm2[5,6],xmm3[7]
 ; AVX2-NEXT:    vpshufb {{.*#+}} xmm2 = xmm2[0,1,6,7,12,13,2,3,8,9,14,15,4,5,10,11]
-; AVX2-NEXT:    vpblendw {{.*#+}} ymm3 = ymm1[0],ymm0[1,2],ymm1[3],ymm0[4,5],ymm1[6],ymm0[7],ymm1[8],ymm0[9,10],ymm1[11],ymm0[12,13],ymm1[14],ymm0[15]
+; AVX2-NEXT:    vpblendw {{.*#+}} ymm3 = ymm0[0],ymm1[1,2],ymm0[3],ymm1[4,5],ymm0[6],ymm1[7],ymm0[8],ymm1[9,10],ymm0[11],ymm1[12,13],ymm0[14],ymm1[15]
 ; AVX2-NEXT:    vextracti128 $1, %ymm3, %xmm4
 ; AVX2-NEXT:    vpblendw {{.*#+}} xmm3 = xmm3[0,1],xmm4[2],xmm3[3,4],xmm4[5],xmm3[6,7]
 ; AVX2-NEXT:    vpshufb {{.*#+}} xmm3 = xmm3[2,3,8,9,14,15,4,5,10,11,0,1,6,7,12,13]
-; AVX2-NEXT:    vpblendw {{.*#+}} ymm0 = ymm0[0],ymm1[1],ymm0[2,3],ymm1[4],ymm0[5,6],ymm1[7],ymm0[8],ymm1[9],ymm0[10,11],ymm1[12],ymm0[13,14],ymm1[15]
+; AVX2-NEXT:    vpblendw {{.*#+}} ymm0 = ymm1[0],ymm0[1],ymm1[2,3],ymm0[4],ymm1[5,6],ymm0[7],ymm1[8],ymm0[9],ymm1[10,11],ymm0[12],ymm1[13,14],ymm0[15]
 ; AVX2-NEXT:    vextracti128 $1, %ymm0, %xmm1
 ; AVX2-NEXT:    vpblendw {{.*#+}} xmm0 = xmm1[0],xmm0[1,2],xmm1[3],xmm0[4,5],xmm1[6],xmm0[7]
 ; AVX2-NEXT:    vpshufb {{.*#+}} xmm0 = xmm0[4,5,10,11,0,1,6,7,12,13,2,3,8,9,14,15]
 ; AVX2-NEXT:    vmovdqu %xmm2, (%rsi)
 ; AVX2-NEXT:    vmovdqu %xmm3, (%rdx)
 ; AVX2-NEXT:    vmovdqu %xmm0, (%rcx)
 ; AVX2-NEXT:    vzeroupper
 ; AVX2-NEXT:    retq

test/CodeGen/X86/vector-shuffle-512-v16.ll

; ALL-NEXT:    retq
   %res = shufflevector <16 x i32> %v, <16 x i32> undef, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
   ret <8 x i32> %res
 }
 
 ;FIXME: can do better with vpcompress
 define <4 x i32> @test_v16i32_0_1_2_12 (<16 x i32> %v) {
 ; ALL-LABEL: test_v16i32_0_1_2_12:
 ; ALL:       # BB#0:
-; ALL-NEXT:    vpextrd $1, %xmm0, %eax
-; ALL-NEXT:    vpinsrd $1, %eax, %xmm0, %xmm1
-; ALL-NEXT:    vpextrd $2, %xmm0, %eax
-; ALL-NEXT:    vpinsrd $2, %eax, %xmm1, %xmm1
-; ALL-NEXT:    vextracti32x4 $3, %zmm0, %xmm0
-; ALL-NEXT:    vmovd %xmm0, %eax
-; ALL-NEXT:    vpinsrd $3, %eax, %xmm1, %xmm0
+; ALL-NEXT:    vextracti32x8 $1, %zmm0, %ymm1
+; ALL-NEXT:    vextracti128 $1, %ymm1, %xmm1
+; ALL-NEXT:    vpbroadcastd %xmm1, %xmm1
+; ALL-NEXT:    vpblendd {{.*#+}} xmm0 = xmm0[0,1,2],xmm1[3]
 ; ALL-NEXT:    vzeroupper
 ; ALL-NEXT:    retq
   %res = shufflevector <16 x i32> %v, <16 x i32> undef, <4 x i32> <i32 0, i32 1, i32 2, i32 12>
   ret <4 x i32> %res
 }
 
 define <8 x float> @shuffle_v16f32_extract_256(float* %RET, float* %a) {
 ; ALL-LABEL: shuffle_v16f32_extract_256:

test/CodeGen/X86/vector-shuffle-512-v8.ll

 ; AVX512F-32-NEXT:    retl
   %res = shufflevector <8 x i64> %v, <8 x i64> undef, <4 x i32> <i32 1, i32 2, i32 5, i32 7>
   ret <4 x i64> %res
 }
 
 define <2 x i64> @test_v8i64_2_5 (<8 x i64> %v) {
 ; AVX512F-LABEL: test_v8i64_2_5:
 ; AVX512F:       # BB#0:
-; AVX512F-NEXT:    vextracti32x4 $2, %zmm0, %xmm1
-; AVX512F-NEXT:    vextracti32x4 $1, %zmm0, %xmm0
+; AVX512F-NEXT:    vextracti64x4 $1, %zmm0, %ymm1
+; AVX512F-NEXT:    vextracti128 $1, %ymm0, %xmm0
 ; AVX512F-NEXT:    vpblendd {{.*#+}} xmm0 = xmm0[0,1],xmm1[2,3]
 ; AVX512F-NEXT:    vzeroupper
 ; AVX512F-NEXT:    retq
 ;
 ; AVX512F-32-LABEL: test_v8i64_2_5:
 ; AVX512F-32:       # BB#0:
-; AVX512F-32-NEXT:    vextracti32x4 $1, %zmm0, %xmm1
-; AVX512F-32-NEXT:    vextracti32x4 $2, %zmm0, %xmm0
-; AVX512F-32-NEXT:    vpextrd $2, %xmm0, %eax
-; AVX512F-32-NEXT:    vpinsrd $2, %eax, %xmm1, %xmm1
-; AVX512F-32-NEXT:    vpextrd $3, %xmm0, %eax
-; AVX512F-32-NEXT:    vpinsrd $3, %eax, %xmm1, %xmm0
+; AVX512F-32-NEXT:    vextracti64x4 $1, %zmm0, %ymm1
+; AVX512F-32-NEXT:    vextracti128 $1, %ymm0, %xmm0
+; AVX512F-32-NEXT:    vpblendd {{.*#+}} xmm0 = xmm0[0,1],xmm1[2,3]
 ; AVX512F-32-NEXT:    vzeroupper
 ; AVX512F-32-NEXT:    retl
   %res = shufflevector <8 x i64> %v, <8 x i64> undef, <2 x i32> <i32 2, i32 5>
   ret <2 x i64> %res
 }