[x86] Improve build_vector v8i16 codegen

[bruno]

Summary

Currently, even with SSE2 enabled, we're generating a series of movds and punpckl to insert elements in v8i16. The testcase in the patch is currently transformed to:

movd    %r8d, %xmm0
movd    24(%rsp), %xmm1
punpcklwd       %xmm1, %xmm0
movd    %edx, %xmm1
movd    8(%rsp), %xmm2
punpcklwd       %xmm2, %xmm1
punpcklwd       %xmm0, %xmm1
movd    %ecx, %xmm0
movd    16(%rsp), %xmm2
punpcklwd       %xmm2, %xmm0
movd    %r9d, %xmm2
movd    %esi, %xmm3
punpcklwd       %xmm2, %xmm3
punpcklwd       %xmm0, %xmm3
punpcklwd       %xmm1, %xmm3

Where it could be replaced by a series of pinsrw instructions, saving 8 instructions:

pinsrw  $0, %esi, %xmm0
pinsrw  $1, %edx, %xmm0
pinsrw  $2, %ecx, %xmm0
pinsrw  $3, %r8d, %xmm0
pinsrw  $4, %r9d, %xmm0
pinsrw  $5, 8(%rsp), %xmm0
pinsrw  $6, 16(%rsp), %xmm0
pinsrw  $7, 24(%rsp), %xmm0

This patch adds this change while it also looks for an opportunity where we could transform this into a SHUFFLE+VEC_INSERT_ELTS first. Most part of this patch is about moving some functions around, that will come in a separated commit.

[qcolombet]

Hi Bruno,

I am not sure this is the right thing to do.
Do you see any performance improvement with the new sequence?

My concern here is, with the new sequence, we have a complete linear sequence of instructions whereas the old sequence can be partly parallelized. Running both the new and old sequence through IACA, I see the following throughputs:
Old:

• Sandy Bridge: 6.15 cycles.
• Ivy Bridge: 6.15 cycles.
• Haswell: 12 cycles.

New:

• Sandy Bridge: 13 cycles.
• Ivy Bridge: 13 cycles.
• Haswell: 13 cycles.

This seems to concur my hypothesis.

Thanks,
-Quentin

[bruno]

Thanks for the detailed measurements Quentin.

I've received a report about a performance degradation regarding this code against hand-written pinsrw assembly and trusted the source =(
I'll try it out myself and get back if it really shows up some performance improvements.

[hfinkel]

• Original Message -----

From: "Bruno Cardoso Lopes" <[e-mail]>
To: "bruno cardoso" <[e-mail]>, [e-mail], [e-mail], [e-mail],
[e-mail]
Cc: [e-mail]
Sent: Monday, January 26, 2015 11:56:27 AM
Subject: Re: [PATCH] [x86] Improve build_vector v8i16 codegen

Thanks for the detailed measurements Quentin.

I've received a report about a performance degradation regarding this
code against hand-written pinsrw assembly and trusted the source =(
I'll try it out myself and get back if it really shows up some
performance improvements.

I'm not particularly familiar with the problem or the solution space, so take this with a grain of salt...

I've seen this kind of thing vary in utility depending on whether the instruction sequence in question is on the critical path or not. If it is on the critical path, then having a longer sequence with more ILP is normally a win. Otherwise, the shorter sequence is normally a win.

I'll also point out that we have the lib/CodeGen/MachineCombiner.cpp pass, that is specifically designed to do this kind of sequence substitution only in cases where we don't increase the critical path length. If my hypothesis is right, this would be a good potential use of that pass (which is theoretically target independent, although currently used only by AArch64).

-Hal

http://reviews.llvm.org/D7177

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[bruno]

Hi Hal,

I wasn't aware of that pass, thanks for the heads up! :-)

[chandlerc]

Just marking that if this is still useful, it will need changes to at least avoid the severe performance regression Quentin pointed out.

[bruno]

I ran this through IACA a few years ago, and didn't prove to be any better.

Current:

• Sandy Bridge: 6.15 cycles.
• Ivy Bridge: 6.15 cycles.
• Haswell: 12 cycles.

New:

• Sandy Bridge: 13 cycles.
• Ivy Bridge: 13 cycles.
• Haswell: 13 cycles.

Abandoning.

lib/Target/X86/X86ISelLowering.cpp

if ((i & 1) != 0) {
         V = DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, MVT::v8i16, V, ThisElt,
                         DAG.getIntPtrConstant(i/2));
     }
   }
 
   return DAG.getNode(ISD::BITCAST, dl, MVT::v16i8, V);
 }
 
-/// LowerBuildVectorv8i16 - Custom lower build_vector of v8i16.
+/// \brief For an EXTRACT_VECTOR_ELT with a constant index return the real
+/// underlying vector and index.
+///
+/// Modifies \p ExtractedFromVec to the real vector and returns the real
+/// index.
+static int getUnderlyingExtractedFromVec(SDValue &ExtractedFromVec,
+                                         SDValue ExtIdx) {
+  int Idx = cast<ConstantSDNode>(ExtIdx)->getZExtValue();
+  if (!isa<ShuffleVectorSDNode>(ExtractedFromVec))
+    return Idx;
+
+  // For 256-bit vectors, LowerEXTRACT_VECTOR_ELT_SSE4 may have already
+  // lowered this:
+  //   (extract_vector_elt (v8f32 %vreg1), Constant<6>)
+  // to:
+  //   (extract_vector_elt (vector_shuffle<2,u,u,u>
+  //                           (extract_subvector (v8f32 %vreg0), Constant<4>),
+  //                           undef)
+  //                       Constant<0>)
+  // In this case the vector is the extract_subvector expression and the index
+  // is 2, as specified by the shuffle.
+  ShuffleVectorSDNode *SVOp = cast<ShuffleVectorSDNode>(ExtractedFromVec);
+  SDValue ShuffleVec = SVOp->getOperand(0);
+  MVT ShuffleVecVT = ShuffleVec.getSimpleValueType();
+  assert(ShuffleVecVT.getVectorElementType() ==
+         ExtractedFromVec.getSimpleValueType().getVectorElementType());
+
+  int ShuffleIdx = SVOp->getMaskElt(Idx);
+  if (isUndefOrInRange(ShuffleIdx, 0, ShuffleVecVT.getVectorNumElements())) {
+    ExtractedFromVec = ShuffleVec;
+    return ShuffleIdx;
+  }
+  return Idx;
+}
+
+/// \brief - If BUILD_VECTOR uses several extractelts and few insertions (currently
+/// one), transform it into a SHUFFLE + INSERT_VECTOR_ELT.
+static SDValue buildFromShuffleMostly(SDValue Op, SelectionDAG &DAG) {
+  MVT VT = Op.getSimpleValueType();
+
+  // Skip if insert_vec_elt is not supported.
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+  if (!TLI.isOperationLegalOrCustom(ISD::INSERT_VECTOR_ELT, VT))
+    return SDValue();
+
+  SDLoc DL(Op);
+  unsigned NumElems = Op.getNumOperands();
+
+  SDValue VecIn1;
+  SDValue VecIn2;
+  SmallVector<unsigned, 4> InsertIndices;
+  SmallVector<int, 8> Mask(NumElems, -1);
+
+  for (unsigned i = 0; i != NumElems; ++i) {
+    unsigned Opc = Op.getOperand(i).getOpcode();
+
+    if (Opc == ISD::UNDEF)
+      continue;
+
+    if (Opc != ISD::EXTRACT_VECTOR_ELT) {
+      // Quit if more than 1 elements need inserting.
+      if (InsertIndices.size() > 1)
+        return SDValue();
+
+      InsertIndices.push_back(i);
+      continue;
+    }
+
+    SDValue ExtractedFromVec = Op.getOperand(i).getOperand(0);
+    SDValue ExtIdx = Op.getOperand(i).getOperand(1);
+    // Quit if non-constant index.
+    if (!isa<ConstantSDNode>(ExtIdx))
+      return SDValue();
+    int Idx = getUnderlyingExtractedFromVec(ExtractedFromVec, ExtIdx);
+
+    // Quit if extracted from vector of different type.
+    if (ExtractedFromVec.getValueType() != VT)
+      return SDValue();
+
+    if (!VecIn1.getNode())
+      VecIn1 = ExtractedFromVec;
+    else if (VecIn1 != ExtractedFromVec) {
+      if (!VecIn2.getNode())
+        VecIn2 = ExtractedFromVec;
+      else if (VecIn2 != ExtractedFromVec)
+        // Quit if more than 2 vectors to shuffle
+        return SDValue();
+    }
+
+    if (ExtractedFromVec == VecIn1)
+      Mask[i] = Idx;
+    else if (ExtractedFromVec == VecIn2)
+      Mask[i] = Idx + NumElems;
+  }
+
+  if (!VecIn1.getNode())
+    return SDValue();
+
+  VecIn2 = VecIn2.getNode() ? VecIn2 : DAG.getUNDEF(VT);
+  SDValue NV = DAG.getVectorShuffle(VT, DL, VecIn1, VecIn2, &Mask[0]);
+  for (unsigned i = 0, e = InsertIndices.size(); i != e; ++i) {
+    unsigned Idx = InsertIndices[i];
+    NV = DAG.getNode(ISD::INSERT_VECTOR_ELT, DL, VT, NV, Op.getOperand(Idx),
+                     DAG.getIntPtrConstant(Idx));
+  }
+
+  return NV;
+}
+
+
+/// \brief Custom lower build_vector of v8i16. Couple of options available:
+///
+/// (1) More than half non zero elts without SSE2 fallback to a likely series
+///     of unpck*.
+/// (2) With SSE2 support use several insert_vector_elts to get PINSRWs.
+/// (3) Use a shuffle.
 ///
 static SDValue LowerBuildVectorv8i16(SDValue Op, unsigned NonZeros,
                                      unsigned NumNonZero, unsigned NumZero,
                                      SelectionDAG &DAG,
                                      const X86Subtarget* Subtarget,
                                      const TargetLowering &TLI) {
-  if (NumNonZero > 4)
+  SDValue Sh = buildFromShuffleMostly(Op, DAG);
+  if (Sh.getNode())
+    return Sh;
+
+  if (NumNonZero > 4 && !Subtarget->hasSSE2())
     return SDValue();
 
   SDLoc dl(Op);
   SDValue V;
   bool First = true;
   for (unsigned i = 0; i < 8; ++i) {
     bool isNonZero = (NonZeros & (1 << i)) != 0;
     if (isNonZero) {
if (Subtarget->hasInt256() && Ld.getValueType().isInteger()) {
     if (ScalarSize == 8 || ScalarSize == 16 || ScalarSize == 64)
       return DAG.getNode(X86ISD::VBROADCAST, dl, VT, Ld);
   }
 
   // Unsupported broadcast.
   return SDValue();
 }
 
-/// \brief For an EXTRACT_VECTOR_ELT with a constant index return the real
-/// underlying vector and index.
-///
-/// Modifies \p ExtractedFromVec to the real vector and returns the real
-/// index.
-static int getUnderlyingExtractedFromVec(SDValue &ExtractedFromVec,
-                                         SDValue ExtIdx) {
-  int Idx = cast<ConstantSDNode>(ExtIdx)->getZExtValue();
-  if (!isa<ShuffleVectorSDNode>(ExtractedFromVec))
-    return Idx;
-
-  // For 256-bit vectors, LowerEXTRACT_VECTOR_ELT_SSE4 may have already
-  // lowered this:
-  //   (extract_vector_elt (v8f32 %vreg1), Constant<6>)
-  // to:
-  //   (extract_vector_elt (vector_shuffle<2,u,u,u>
-  //                           (extract_subvector (v8f32 %vreg0), Constant<4>),
-  //                           undef)
-  //                       Constant<0>)
-  // In this case the vector is the extract_subvector expression and the index
-  // is 2, as specified by the shuffle.
-  ShuffleVectorSDNode *SVOp = cast<ShuffleVectorSDNode>(ExtractedFromVec);
-  SDValue ShuffleVec = SVOp->getOperand(0);
-  MVT ShuffleVecVT = ShuffleVec.getSimpleValueType();
-  assert(ShuffleVecVT.getVectorElementType() ==
-         ExtractedFromVec.getSimpleValueType().getVectorElementType());
-
-  int ShuffleIdx = SVOp->getMaskElt(Idx);
-  if (isUndefOrInRange(ShuffleIdx, 0, ShuffleVecVT.getVectorNumElements())) {
-    ExtractedFromVec = ShuffleVec;
-    return ShuffleIdx;
-  }
-  return Idx;
-}
-
-static SDValue buildFromShuffleMostly(SDValue Op, SelectionDAG &DAG) {
-  MVT VT = Op.getSimpleValueType();
-
-  // Skip if insert_vec_elt is not supported.
-  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
-  if (!TLI.isOperationLegalOrCustom(ISD::INSERT_VECTOR_ELT, VT))
-    return SDValue();
-
-  SDLoc DL(Op);
-  unsigned NumElems = Op.getNumOperands();
-
-  SDValue VecIn1;
-  SDValue VecIn2;
-  SmallVector<unsigned, 4> InsertIndices;
-  SmallVector<int, 8> Mask(NumElems, -1);
-
-  for (unsigned i = 0; i != NumElems; ++i) {
-    unsigned Opc = Op.getOperand(i).getOpcode();
-
-    if (Opc == ISD::UNDEF)
-      continue;
-
-    if (Opc != ISD::EXTRACT_VECTOR_ELT) {
-      // Quit if more than 1 elements need inserting.
-      if (InsertIndices.size() > 1)
-        return SDValue();
-
-      InsertIndices.push_back(i);
-      continue;
-    }
-
-    SDValue ExtractedFromVec = Op.getOperand(i).getOperand(0);
-    SDValue ExtIdx = Op.getOperand(i).getOperand(1);
-    // Quit if non-constant index.
-    if (!isa<ConstantSDNode>(ExtIdx))
-      return SDValue();
-    int Idx = getUnderlyingExtractedFromVec(ExtractedFromVec, ExtIdx);
-
-    // Quit if extracted from vector of different type.
-    if (ExtractedFromVec.getValueType() != VT)
-      return SDValue();
-
-    if (!VecIn1.getNode())
-      VecIn1 = ExtractedFromVec;
-    else if (VecIn1 != ExtractedFromVec) {
-      if (!VecIn2.getNode())
-        VecIn2 = ExtractedFromVec;
-      else if (VecIn2 != ExtractedFromVec)
-        // Quit if more than 2 vectors to shuffle
-        return SDValue();
-    }
-
-    if (ExtractedFromVec == VecIn1)
-      Mask[i] = Idx;
-    else if (ExtractedFromVec == VecIn2)
-      Mask[i] = Idx + NumElems;
-  }
-
-  if (!VecIn1.getNode())
-    return SDValue();
-
-  VecIn2 = VecIn2.getNode() ? VecIn2 : DAG.getUNDEF(VT);
-  SDValue NV = DAG.getVectorShuffle(VT, DL, VecIn1, VecIn2, &Mask[0]);
-  for (unsigned i = 0, e = InsertIndices.size(); i != e; ++i) {
-    unsigned Idx = InsertIndices[i];
-    NV = DAG.getNode(ISD::INSERT_VECTOR_ELT, DL, VT, NV, Op.getOperand(Idx),
-                     DAG.getIntPtrConstant(Idx));
-  }
-
-  return NV;
-}
-
 // Lower BUILD_VECTOR operation for v8i1 and v16i1 types.
 SDValue
 X86TargetLowering::LowerBUILD_VECTORvXi1(SDValue Op, SelectionDAG &DAG) const {
 
   MVT VT = Op.getSimpleValueType();
   assert((VT.getVectorElementType() == MVT::i1) && (VT.getSizeInBits() <= 16) &&
          "Unexpected type in LowerBUILD_VECTORvXi1!");
 

test/CodeGen/X86/vec_set.ll

-; RUN: llc < %s -march=x86 -mattr=+sse2,-sse4.1 | grep punpckl | count 7
+; RUN: llc < %s -march=x86-64 -mattr=+sse2,-sse4.1 | FileCheck %s
 
-define void @test(<8 x i16>* %b, i16 %a0, i16 %a1, i16 %a2, i16 %a3, i16 %a4, i16 %a5, i16 %a6, i16 %a7) nounwind {
-        %tmp = insertelement <8 x i16> zeroinitializer, i16 %a0, i32 0          ; <<8 x i16>> [#uses=1]
-        %tmp2 = insertelement <8 x i16> %tmp, i16 %a1, i32 1            ; <<8 x i16>> [#uses=1]
-        %tmp4 = insertelement <8 x i16> %tmp2, i16 %a2, i32 2           ; <<8 x i16>> [#uses=1]
-        %tmp6 = insertelement <8 x i16> %tmp4, i16 %a3, i32 3           ; <<8 x i16>> [#uses=1]
-        %tmp8 = insertelement <8 x i16> %tmp6, i16 %a4, i32 4           ; <<8 x i16>> [#uses=1]
-        %tmp10 = insertelement <8 x i16> %tmp8, i16 %a5, i32 5          ; <<8 x i16>> [#uses=1]
-        %tmp12 = insertelement <8 x i16> %tmp10, i16 %a6, i32 6         ; <<8 x i16>> [#uses=1]
-        %tmp14 = insertelement <8 x i16> %tmp12, i16 %a7, i32 7         ; <<8 x i16>> [#uses=1]
-        store <8 x i16> %tmp14, <8 x i16>* %b
-        ret void
+; CHECK-LABEL: test0
+define void @test0(<8 x i16>* %b, i16 %a0, i16 %a1, i16 %a2, i16 %a3, i16 %a4, i16 %a5, i16 %a6, i16 %a7) nounwind {
+; CHECK-LABEL: test0:
+; CHECK:       ## BB#0:
+; CHECK-NEXT:    pinsrw $0, %esi, %xmm0
+; CHECK-NEXT:    pinsrw $1, %edx, %xmm0
+; CHECK-NEXT:    pinsrw $2, %ecx, %xmm0
+; CHECK-NEXT:    pinsrw $3, %r8d, %xmm0
+; CHECK-NEXT:    pinsrw $4, %r9d, %xmm0
+; CHECK-NEXT:    pinsrw $5, {{[0-9]+}}(%rsp), %xmm0
+; CHECK-NEXT:    pinsrw $6, {{[0-9]+}}(%rsp), %xmm0
+; CHECK-NEXT:    pinsrw $7, {{[0-9]+}}(%rsp), %xmm0
+; CHECK-NEXT:    movdqa %xmm0, (%rdi)
+; CHECK-NEXT:    retq
+  %tmp = insertelement <8 x i16> zeroinitializer, i16 %a0, i32 0
+  %tmp2 = insertelement <8 x i16> %tmp, i16 %a1, i32 1
+  %tmp4 = insertelement <8 x i16> %tmp2, i16 %a2, i32 2
+  %tmp6 = insertelement <8 x i16> %tmp4, i16 %a3, i32 3
+  %tmp8 = insertelement <8 x i16> %tmp6, i16 %a4, i32 4
+  %tmp10 = insertelement <8 x i16> %tmp8, i16 %a5, i32 5
+  %tmp12 = insertelement <8 x i16> %tmp10, i16 %a6, i32 6
+  %tmp14 = insertelement <8 x i16> %tmp12, i16 %a7, i32 7
 }
-