[DAG] Allow build_vector-to-vector_shuffle combine to combine builds from two overly-wide vectors.

[mkuper]

Summary

This allows us to create a vector_shuffle out of a build_vector, when we have extract_elements from two inputs, at least one of which is wider than the output.
(E.g. a <8 x i16> being constructed out of elements from a <16 x i16> and a <8 x i16>).

This is the first patch in a series - the idea is to get all of the "oddshuffles" tests to use shuffles instead of insert/extract sequences. Most (all?) of the remaining cases require building a vector out of more than 2 inputs.

[ABataev]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13054–13055

if (ShuffleNumElems > NumElems)
  Mask.append(ShuffleNumElems-NumElems, -1)

?

[mkuper]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13054–13055

Yeah, I keep writing these loops on auto-pilot. :-)
This should either be an append, or Mask should just be initialized to -1. Thanks!

[RKSimon]

Thanks for looking at this! I've made a few minor observations.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12996

Its not necessarily twice the size here is it? I'm thinking xmm from zmm.

13054–13055

It'd be tidier if you just did SmallVector<int, 8> Mask(ShuffleNumElems, -1) and replaced the push_back() calls with Mask[i]

13079

Use ZeroIdx?

[andreadb]

Hi Michael,

The patch looks good to me . I only have one comment (see below).

-Andrea

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12962–12973

My understanding is that we check if VT is a legal type for the target at the very beginning of this method.

However, (correct me if I am wrong) we don't check if InVT1 and InVT2 are legal types. So, we potentially always enable this canonicalization even on illegal vector types.

I wonder if we should add a early exit for the case where the DAG is not "type legalized" and InVT1 and InVT2 are not legal types for the target. The legalizer would adjust/canonicalize those vector types. We would still end up running your code if eventually types still don't match VT.

Not sure if this makes sense.

[mkuper]

Thanks Alexey, Simon, Andrea!

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12962–12973

I'm not entirely sure. If the inputs are longer than the output, you're probably right.
The case that worries me, though, is something like a build_vector of <4 x i32> from 2 * <2 x i32>. I think we may want to hit this pre-legalization.
I'll add (yet another :-) ) TODO, and we can think about this post-commit. I'm going to keep working on this code anyway.

12996

You're right, that should be another TODO. (This isn't a change made in this patch, we've always supported it only in the "twice the size" case).

13054–13055

Yes, that's what I meant by "should just be initialized to -1".
I think we've already had this conversation in a previous patch, as I said, this is just auto-pilot. Thanks again!

13079

Right, just need to define it in the right scope.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::reduceBuildVecToShuffle(SDNode *N) {
 
   // If we didn't find at least one input vector, bail out.
   if (!VecIn1.getNode())
     return SDValue();
 
   EVT InVT1 = VecIn1.getValueType();
   EVT InVT2 = VecIn2.getNode() ? VecIn2.getValueType() : InVT1;
   unsigned Vec2Offset = InVT1.getVectorNumElements();
+  unsigned ShuffleNumElems = NumElems;
+
+  MVT IdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());
+  SDValue ZeroIdx = DAG.getConstant(0, dl, IdxTy);
 
   // We can't generate a shuffle node with mismatched input and output types.
   // Try to make the types match.
   if (InVT1 != VT || InVT2 != VT) {
     // Both inputs and the output must have the same base element type.
     EVT ElemType = VT.getVectorElementType();
     if (ElemType != InVT1.getVectorElementType() ||
         ElemType != InVT2.getVectorElementType())
       return SDValue();
 
+    // TODO: Canonicalize this so that if the vectors have different lengths,
+    // VecIn1 is always longer.
+
     // The element types match, now figure out the lengths.
     if (InVT1.getSizeInBits() * 2 == VT.getSizeInBits() && InVT1 == InVT2) {
       // If both input vectors are exactly half the size of the output, concat
       // them. If we have only one (non-zero) input, concat it with undef.
       VecIn1 = DAG.getNode(ISD::CONCAT_VECTORS, dl, VT, VecIn1,
                            getRightHandValue(DAG, dl, VecIn2, InVT1, false));
       VecIn2 = SDValue();
       // If we have one "real" input and are blending with zero, we need the
       // zero elements to come from the second input, not the undef part of the
       // first input.
       if (UsesZeroVector)
         Vec2Offset = NumElems;
     } else if (InVT1.getSizeInBits() == VT.getSizeInBits() * 2) {
-      // If we only have one input vector, and it's twice the size of the
-      // output, split it in two.
       if (!TLI.isExtractSubvectorCheap(VT, NumElems))
         return SDValue();
 
-      // TODO: Support the case where we have one input that's too wide, and
-      // another input which is wide/"correct"/narrow. We can do this by
-      // widening the narrow input, shuffling the wide vectors, and then
-      // extracting the low subvector.
-      if (UsesZeroVector || VecIn2.getNode())
+      if (UsesZeroVector)
         return SDValue();
 
-      MVT IdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());
+      if (!VecIn2.getNode()) {
+        // If we only have one input vector, and it's twice the size of the
+        // output, split it in two.        
         VecIn2 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, VecIn1,
                              DAG.getConstant(NumElems, dl, IdxTy));
-      VecIn1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, VecIn1,
-                           DAG.getConstant(0, dl, IdxTy));
+        VecIn1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, VecIn1, ZeroIdx);
         // Since we now have shorter input vectors, adjust the offset of the
         // second vector's start.
         Vec2Offset = NumElems;
+      } else if (InVT2.getSizeInBits() <= InVT1.getSizeInBits()) {
+        // VecIn1 is wider than the output, and we have another, possibly
+        // smaller input. Pad the smaller input with undefs, shuffle at the
+        // input vector width, and extract the output.
+
+        // The shuffle type is different than VT, so check legality again.
+        if (LegalOperations &&
+            !TLI.isOperationLegal(ISD::VECTOR_SHUFFLE, InVT1))
+          return SDValue();
+
+        if (InVT1 != InVT2)
+          VecIn2 = DAG.getNode(ISD::INSERT_SUBVECTOR, dl, InVT1,
+                               DAG.getUNDEF(InVT1), VecIn2, ZeroIdx);
+        ShuffleNumElems = NumElems * 2;
+      }
     } else {
       // TODO: Support cases where the length mismatch isn't exactly by a
       // factor of 2.
       return SDValue();
     }
   }
 
   SmallVector<int, 8> Mask;
if (VectorMask[i] == 1) {
       Mask.push_back(ExtIndex);
       continue;
     }
 
     assert(VectorMask[i] == 2 && "Expected input to be from second vector");
     Mask.push_back(Vec2Offset + ExtIndex);
   }
 
+  // If the width of the shuffle is larger than the width of the output, we
+  // only care about the low elements anyway. Pad the mask with undef.
+  for (unsigned i = NumElems; i != ShuffleNumElems; ++i)
+    Mask.push_back(-1);
+
   // Avoid introducing illegal shuffles with zero.
   // TODO: This doesn't actually do anything smart at the moment.
   // We should either delete this, or check legality for all the shuffles
   // we create.
   if (UsesZeroVector && !TLI.isVectorClearMaskLegal(Mask, VT))
     return SDValue();
 
+  // The type the input vectors may have changed above.
+  InVT1 = VecIn1.getValueType();
+
   // If we already have a VecIn2, it should have the same type as VecIn1.
   // If we don't, get an undef/zero vector of the appropriate type.
-  VecIn2 =
-      getRightHandValue(DAG, dl, VecIn2, VecIn1.getValueType(), UsesZeroVector);
-  assert(VecIn1.getValueType() == VecIn2.getValueType() &&
-         "Unexpected second input type.");
+  VecIn2 = getRightHandValue(DAG, dl, VecIn2, InVT1, UsesZeroVector);
+  assert(InVT1 == VecIn2.getValueType() && "Unexpected second input type.");
 
   // Return the new VECTOR_SHUFFLE node.
   SDValue Ops[2];
   Ops[0] = VecIn1;
   Ops[1] = VecIn2;
-  return DAG.getVectorShuffle(VT, dl, Ops[0], Ops[1], Mask);
+  SDValue Shuffle = DAG.getVectorShuffle(InVT1, dl, Ops[0], Ops[1], Mask);
+  if (ShuffleNumElems > NumElems)
+    Shuffle = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, Shuffle,
+                          DAG.getConstant(0, dl, IdxTy));
+
+  return Shuffle;
 }
 
 SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) {
   EVT VT = N->getValueType(0);
 
   // A vector built entirely of undefs is undef.
   if (ISD::allOperandsUndef(N))
     return DAG.getUNDEF(VT);

test/CodeGen/X86/oddshuffles.ll

 ; SSE42-NEXT:    movdqu %xmm4, (%rcx)
 ; SSE42-NEXT:    popq %rbx
 ; SSE42-NEXT:    popq %rbp
 ; SSE42-NEXT:    retq
 ;
 ; AVX1-LABEL: interleave_24i16_out:
 ; AVX1:       # BB#0:
 ; AVX1-NEXT:    vmovdqu 32(%rdi), %xmm0
-; AVX1-NEXT:    vmovdqu (%rdi), %ymm2
-; AVX1-NEXT:    vpextrw $3, %xmm2, %eax
-; AVX1-NEXT:    vpinsrw $1, %eax, %xmm2, %xmm1
-; AVX1-NEXT:    vpextrw $6, %xmm2, %eax
-; AVX1-NEXT:    vpinsrw $2, %eax, %xmm1, %xmm3
-; AVX1-NEXT:    vextractf128 $1, %ymm2, %xmm1
-; AVX1-NEXT:    vpextrw $1, %xmm1, %eax
-; AVX1-NEXT:    vpinsrw $3, %eax, %xmm3, %xmm3
-; AVX1-NEXT:    vpextrw $4, %xmm1, %eax
-; AVX1-NEXT:    vpinsrw $4, %eax, %xmm3, %xmm3
-; AVX1-NEXT:    vpextrw $7, %xmm1, %eax
-; AVX1-NEXT:    vpinsrw $5, %eax, %xmm3, %xmm3
-; AVX1-NEXT:    vpextrw $2, %xmm0, %eax
-; AVX1-NEXT:    vpinsrw $6, %eax, %xmm3, %xmm3
-; AVX1-NEXT:    vpextrw $5, %xmm0, %eax
-; AVX1-NEXT:    vpinsrw $7, %eax, %xmm3, %xmm3
-; AVX1-NEXT:    vpextrw $4, %xmm2, %eax
-; AVX1-NEXT:    vpextrw $1, %xmm2, %edi
-; AVX1-NEXT:    vmovd %edi, %xmm4
-; AVX1-NEXT:    vpinsrw $1, %eax, %xmm4, %xmm4
-; AVX1-NEXT:    vpextrw $7, %xmm2, %eax
-; AVX1-NEXT:    vpinsrw $2, %eax, %xmm4, %xmm4
-; AVX1-NEXT:    vpextrw $2, %xmm1, %eax
-; AVX1-NEXT:    vpinsrw $3, %eax, %xmm4, %xmm4
-; AVX1-NEXT:    vpextrw $5, %xmm1, %eax
-; AVX1-NEXT:    vpinsrw $4, %eax, %xmm4, %xmm4
-; AVX1-NEXT:    vmovd %xmm0, %eax
-; AVX1-NEXT:    vpinsrw $5, %eax, %xmm4, %xmm4
-; AVX1-NEXT:    vpextrw $3, %xmm0, %eax
-; AVX1-NEXT:    vpinsrw $6, %eax, %xmm4, %xmm4
-; AVX1-NEXT:    vpextrw $6, %xmm0, %eax
-; AVX1-NEXT:    vpinsrw $7, %eax, %xmm4, %xmm4
-; AVX1-NEXT:    vpextrw $5, %xmm2, %eax
-; AVX1-NEXT:    vpextrw $2, %xmm2, %edi
-; AVX1-NEXT:    vmovd %edi, %xmm2
-; AVX1-NEXT:    vpinsrw $1, %eax, %xmm2, %xmm2
-; AVX1-NEXT:    vmovd %xmm1, %eax
-; AVX1-NEXT:    vpinsrw $2, %eax, %xmm2, %xmm2
-; AVX1-NEXT:    vpextrw $3, %xmm1, %eax
-; AVX1-NEXT:    vpinsrw $3, %eax, %xmm2, %xmm2
-; AVX1-NEXT:    vpextrw $6, %xmm1, %eax
-; AVX1-NEXT:    vpinsrw $4, %eax, %xmm2, %xmm1
-; AVX1-NEXT:    vpextrw $1, %xmm0, %eax
-; AVX1-NEXT:    vpinsrw $5, %eax, %xmm1, %xmm1
-; AVX1-NEXT:    vpextrw $4, %xmm0, %eax
-; AVX1-NEXT:    vpinsrw $6, %eax, %xmm1, %xmm1
-; AVX1-NEXT:    vpextrw $7, %xmm0, %eax
-; AVX1-NEXT:    vpinsrw $7, %eax, %xmm1, %xmm0
+; AVX1-NEXT:    vmovups (%rdi), %ymm1
+; AVX1-NEXT:    vextractf128 $1, %ymm1, %xmm2
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm3 = xmm1[0],xmm2[1],xmm1[2,3],xmm2[4],xmm1[5,6],xmm2[7]
+; AVX1-NEXT:    vpshufb {{.*#+}} xmm3 = xmm3[0,1,6,7,12,13,2,3,8,9,14,15,12,13,14,15]
+; AVX1-NEXT:    vpshufd {{.*#+}} xmm4 = xmm0[0,1,2,1]
+; AVX1-NEXT:    vpshufhw {{.*#+}} xmm4 = xmm4[0,1,2,3,4,5,6,5]
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm3 = xmm3[0,1,2,3,4,5],xmm4[6,7]
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm4 = xmm1[0,1],xmm2[2],xmm1[3,4],xmm2[5],xmm1[6,7]
+; AVX1-NEXT:    vpshufb {{.*#+}} xmm4 = xmm4[2,3,8,9,14,15,4,5,10,11,10,11,8,9,14,15]
+; AVX1-NEXT:    vpshufb {{.*#+}} xmm5 = xmm0[0,1,6,7,4,5,6,7,0,1,0,1,6,7,12,13]
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm4 = xmm4[0,1,2,3,4],xmm5[5,6,7]
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm1 = xmm2[0,1],xmm1[2],xmm2[3,4],xmm1[5],xmm2[6,7]
+; AVX1-NEXT:    vpshufb {{.*#+}} xmm1 = xmm1[4,5,10,11,0,1,6,7,12,13,14,15,0,1,2,3]
+; AVX1-NEXT:    vpshufb {{.*#+}} xmm0 = xmm0[0,1,2,3,4,5,6,7,8,9,2,3,8,9,14,15]
+; AVX1-NEXT:    vpblendw {{.*#+}} xmm0 = xmm1[0,1,2,3,4],xmm0[5,6,7]
 ; 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 32(%rdi), %xmm0
-; AVX2-NEXT:    vmovdqu (%rdi), %ymm2
-; AVX2-NEXT:    vpextrw $3, %xmm2, %eax
-; AVX2-NEXT:    vpinsrw $1, %eax, %xmm2, %xmm1
-; AVX2-NEXT:    vpextrw $6, %xmm2, %eax
-; AVX2-NEXT:    vpinsrw $2, %eax, %xmm1, %xmm3
-; AVX2-NEXT:    vextracti128 $1, %ymm2, %xmm1
-; AVX2-NEXT:    vpextrw $1, %xmm1, %eax
-; AVX2-NEXT:    vpinsrw $3, %eax, %xmm3, %xmm3
-; AVX2-NEXT:    vpextrw $4, %xmm1, %eax
-; AVX2-NEXT:    vpinsrw $4, %eax, %xmm3, %xmm3
-; AVX2-NEXT:    vpextrw $7, %xmm1, %eax
-; AVX2-NEXT:    vpinsrw $5, %eax, %xmm3, %xmm3
-; AVX2-NEXT:    vpextrw $2, %xmm0, %eax
-; AVX2-NEXT:    vpinsrw $6, %eax, %xmm3, %xmm3
-; AVX2-NEXT:    vpextrw $5, %xmm0, %eax
-; AVX2-NEXT:    vpinsrw $7, %eax, %xmm3, %xmm3
-; AVX2-NEXT:    vpextrw $4, %xmm2, %eax
-; AVX2-NEXT:    vpextrw $1, %xmm2, %edi
-; AVX2-NEXT:    vmovd %edi, %xmm4
-; AVX2-NEXT:    vpinsrw $1, %eax, %xmm4, %xmm4
-; AVX2-NEXT:    vpextrw $7, %xmm2, %eax
-; AVX2-NEXT:    vpinsrw $2, %eax, %xmm4, %xmm4
-; AVX2-NEXT:    vpextrw $2, %xmm1, %eax
-; AVX2-NEXT:    vpinsrw $3, %eax, %xmm4, %xmm4
-; AVX2-NEXT:    vpextrw $5, %xmm1, %eax
-; AVX2-NEXT:    vpinsrw $4, %eax, %xmm4, %xmm4
-; AVX2-NEXT:    vmovd %xmm0, %eax
-; AVX2-NEXT:    vpinsrw $5, %eax, %xmm4, %xmm4
-; AVX2-NEXT:    vpextrw $3, %xmm0, %eax
-; AVX2-NEXT:    vpinsrw $6, %eax, %xmm4, %xmm4
-; AVX2-NEXT:    vpextrw $6, %xmm0, %eax
-; AVX2-NEXT:    vpinsrw $7, %eax, %xmm4, %xmm4
-; AVX2-NEXT:    vpextrw $5, %xmm2, %eax
-; AVX2-NEXT:    vpextrw $2, %xmm2, %edi
-; AVX2-NEXT:    vmovd %edi, %xmm2
-; AVX2-NEXT:    vpinsrw $1, %eax, %xmm2, %xmm2
-; AVX2-NEXT:    vmovd %xmm1, %eax
-; AVX2-NEXT:    vpinsrw $2, %eax, %xmm2, %xmm2
-; AVX2-NEXT:    vpextrw $3, %xmm1, %eax
-; AVX2-NEXT:    vpinsrw $3, %eax, %xmm2, %xmm2
-; AVX2-NEXT:    vpextrw $6, %xmm1, %eax
-; AVX2-NEXT:    vpinsrw $4, %eax, %xmm2, %xmm1
-; AVX2-NEXT:    vpextrw $1, %xmm0, %eax
-; AVX2-NEXT:    vpinsrw $5, %eax, %xmm1, %xmm1
-; AVX2-NEXT:    vpextrw $4, %xmm0, %eax
-; AVX2-NEXT:    vpinsrw $6, %eax, %xmm1, %xmm1
-; AVX2-NEXT:    vpextrw $7, %xmm0, %eax
-; AVX2-NEXT:    vpinsrw $7, %eax, %xmm1, %xmm0
-; AVX2-NEXT:    vmovdqu %xmm3, (%rsi)
-; AVX2-NEXT:    vmovdqu %xmm4, (%rdx)
+; 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:    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:    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:    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
   %wide.vec = load <24 x i16>, <24 x i16>* %p, align 4
   %s1 = shufflevector <24 x i16> %wide.vec, <24 x i16> undef, <8 x i32> <i32 0, i32 3, i32 6, i32 9, i32 12, i32 15, i32 18, i32 21>
   %s2 = shufflevector <24 x i16> %wide.vec, <24 x i16> undef, <8 x i32> <i32 1, i32 4, i32 7, i32 10, i32 13, i32 16, i32 19, i32 22>
   %s3 = shufflevector <24 x i16> %wide.vec, <24 x i16> undef, <8 x i32> <i32 2, i32 5, i32 8, i32 11, i32 14, i32 17, i32 20, i32 23>
   store <8 x i16> %s1, <8 x i16>* %q1, align 4