Optimization for certain shufflevector by using insertps.

[filcab]

Summary

If we're doing a v4f32 shuffle on x86 with SSE4.1, we can lower certain
shufflevectors to an insertps instruction:
When most of the shufflevector result's elements come from one vector (and
keep their index), and one element comes from another vector or a memory
operand.

Added tests for insertps optimizations on shufflevector.

[silvas]

lib/Target/X86/X86ISelLowering.cpp

3944

Tiny style nit: the canonical LLVM counted loop is

for (int i = 0, e = Foo.size(); i != e; ++i)

[filcab]

Fixed llvm-style nit pointed by Sean Silva.

[nadav]

I did not review the patch carefully but from a quick look it looks fine. Andrea, what do you say?

[delena]

Hi Filipe,

1. you can check INSERTPS mask outside NormalizeVectorShuffle(), where all other masks have been checked.
2. you can use insertps for v4i32 as well.

3. I think that folding load in insertps is not fully correct

you translate this IR to (add + insertps) commands.

%0 = load <4 x float>* %pb, align 16
%vecinit6 = shufflevector <4 x float> %a, <4 x float> %0, <4 x i32> <i32 0, i32 1, i32 2, i32 4>

insertps loads 4 bytes instead of 32. You lose exceptions. It is ok for OpenCL but other compilers can't ignore exceptions.

And in general, I'm not sure that
add + insertps-load-form is better than load + insertps

4. About tests: Why do you check X32 and X64 separately?

• Elena

[andreadb]

Hi filipe,

I think your patch in general looks good except for a few things (see comments below).

lib/Target/X86/X86ISelLowering.cpp

3939

I would change this into:

if (VT != MVT::v4i32 && VT != MVT::v4f32)

7289

It probably makes sense to add a comment explaining that it is safe to call this function only when the shuffle mask is a valid INSERTPS mask (according to your new isINSERTPSMask function). Otherwise, DestIndex would be wrongly computed.

7290

I would remove the bool 'HasAVX' since it is not used.
That extra argument can be added in future once we decide to optimize for AVX cases too.

7299

You should also support MVT::v4i32.

7321–7342

As Elena pointed out,
it is unsafe to transform the load+insertps into an add+insertps with memory operand. If you force that transformation, then the alignment constraint would not be honored.

According to the instruction set reference, no alignment is required for the insertps instruction (unless alignment checking is enabled). If alignment checking is enabled, the check would ensure that the address is aligned to 4 (and not 16).

The good thing is that, even without that if-stmt, your transformation would still improve all the test cases you added (i.e. for the load+shuffle case, you would get a movaps+insertps instead of movaps+shufps+shufps).

test/CodeGen/X86/sse41.ll

252–265

Without the 'load+insertps -> add+insertps' transformation, this test would still be improved by your patch.

With your patch (excluding the if-stmt between lines 7315:7336 ), the code generate is better than it was before applying your patch. We now get a movaps+insertps; before we produced instead a movaps followed by two shufps instructions.

I would change the test adding explicit checks for the aligned load (movaps) and the insertps.

252–279

Elena is right.
Since you are matching the same code for X64 and X32, I would suggest adding a common check-prefix (example: --check-prefix=CHECK) to both RUN lines.

You can use a single CHECK-LABEL in each test function (rather than having two identical checks [X32-LABEL and X64-LABEL] for every function).
Your new tests would only use CHECK (and not X32/X64).

I would add extra tests to verify that your lowering rule works fine with <4 x i32> vectors.

252–279

Your parch improves the code generation also in the following case:

define <4 x float> @foo(<4 x float> %a, float* %b) {
  %1 = load float* %b, align 4
  %2 = insertelement <4 x float> undef, float %1, i32 0
  %result = shufflevector <4 x float> %a, <4 x float> %2, <4 x i32> <i32 0, i32 1, i32 2, i32 4>
  ret <4 x i32> %result
}

That is because your fix helps matching the pattern defined for def rm : SS4AI8 that selects an INSERTPS with a memory operand. (See X86InstrSSE.td - multiclass SS41I_insertf32).

With your patch, the backend would produce a single insertps for the test above. Before (i.e. without your patch), we produced the following long sequence of instructions (on X64):

movss  (%rdi), %xmm1
movaps %xmm0, %xmm2
movss %xmm1, %xmm2
shufps $36, %xmm2, %xmm0

I suggest to add that test as well (and another test to verify that the code is simplifed even if we have <4 x i32> vector types).

[filcab]

Hi Elena and Andrea,

1 - I've changed the check + change to NormalizeVectorShuffe(), I will update the patch soon;

2 - This won't be as easy as it looks (see below);

3 - I don't understand what the problem would be in making the load smaller. Especially since we do these kinds of load reductions in other places (including target independent opts like in DAGCombiner::ReduceLoadOpStoreWidth, and others). The alignment requirements don't get stricter, so we shouldn't output code that might break when the original wouldn't. And if I'm not mistaken, the alignment exceptions would fall under undefined behaviour, which wouldn't make this optimization invalid;

By the way, with the current transform, we would never generate an add instruction for the insertps. We just generate the insertps with the address calculation in it (just to be sure we're on the same page).

4 - I will change the test. After this fix I'll also change other tests in the same file that similarly check for the same text on X32 and X64.

About supporting i32 besides f32:

I can simply do the transform for MVT::v4i32 too, but it will not optimize as much as the current one does for f32.
It will optimize some cases but, for example, we might still get movsd+insertps when insertps should suffice.

To fix this problem, we add a bunch of new ones:

I don't know that much about the backend, but there doesn't seem to be a way to do it without creating a new SDNode type for INSERTPS (I don't know what it would be called, since INSERTPS is already used). (X86InstrFragmentsSIMD.td:84)
I can't find a way to have, on the type profile, an OR condition, which would allow us to define X86insertps as getting a f32 or i32 from memory.
Without this, the pattern we generate in X86InstrSSE.td:6522 won't match due to its types (even if we define a whole new multiclass for the i32 case).

I think the best course of action would be to:

• Add some more tests, for the i32 cases (and collapse the tests to a common check-prefix);
• Do the transform on both i32 and f32, for now, even if the generated instructions aren't perfect;
• Later figure out how to better express the insertps for i32 in the backed (either with a new instruction, or a simpler one-time hack for this one).

What do you think?

Filipe

[filcab]

Just a small addition that I will investigate tomorrow:
The whole “get an i32 from memory into an xmm element” gets much easier if my transform emits a pinsrd for that case. I will change it to use pinsrd (for the i32 from mem case) tomorrow.

Filipe

[filcab]

Added the optimization for v4i32 (but we emit pinsrd instead of insertps when loading from memory).
Addresses the concerns in the review, except for the load minimization, due to discussion on IRC, existing optimizations that reduce load sizes, and lack of response to my question.

lib/Target/X86/X86ISelLowering.cpp

static bool isMOVLHPSMask(ArrayRef<int> Mask, MVT VT) {
 
   for (unsigned i = 0, e = NumElems/2; i != e; ++i)
     if (!isUndefOrEqual(Mask[i + e], i + NumElems))
       return false;
 
   return true;
 }
 
+/// isINSERTPSMask - Return true if the specified VECTOR_SHUFFLE operand
+/// specifies a shuffle of elements that is suitable for input to INSERTPS.
+/// i. e: If all but one element come from the same vector.
+static bool isINSERTPSMask(ArrayRef<int> Mask, MVT VT) {
+  // TODO: Deal with AVX's VINSERTPS
+  if (!VT.is128BitVector() || (VT != MVT::v4f32 && VT != MVT::v4i32))
+    return false;
+
+  unsigned CorrectPosV1 = 0;
+  unsigned CorrectPosV2 = 0;
+  for (int i = 0, e = (int)VT.getVectorNumElements(); i != e; ++i)
+    if (Mask[i] == i)
+      ++CorrectPosV1;
+    else if (Mask[i] == i + 4)
+      ++CorrectPosV2;
+
+  if (CorrectPosV1 == 3 || CorrectPosV2 == 3)
+    // We have 3 elements from one vector, and one from another.
+    return true;
+
+  return false;
+}
+
 //
 // Some special combinations that can be optimized.
 //
 static
 SDValue Compact8x32ShuffleNode(ShuffleVectorSDNode *SVOp,
                                SelectionDAG &DAG) {
   MVT VT = SVOp->getSimpleValueType(0);
   SDLoc dl(SVOp);
SDValue getMOVLP(SDValue &Op, SDLoc &dl, SelectionDAG &DAG, bool HasSSE2) {
 
   assert(VT != MVT::v4i32 && "unsupported shuffle type");
 
   // Invert the operand order and use SHUFPS to match it.
   return getTargetShuffleNode(X86ISD::SHUFP, dl, VT, V2, V1,
                               getShuffleSHUFImmediate(SVOp), DAG);
 }
 
+// It is only safe to call this function if isINSERTPSMask is true for
+// this shufflevector mask.
+static SDValue getINSERTPS(ShuffleVectorSDNode *SVOp, SDLoc &dl,
+                           SelectionDAG &DAG) {
+  // Generate an insertps instruction when inserting an f32 from memory onto a
+  // v4f32 or when copying a member from one v4f32 to another.
+  // We also use it for transferring i32 from one register to another,
+  // since it simply copies the same bits.
+  // If we're transfering an i32 from memory to a specific element in a
+  // register, we output a generic DAG that will match the PINSRD
+  // instruction.
+  // TODO: Optimize for AVX cases too (VINSERTPS)
+  MVT VT = SVOp->getSimpleValueType(0);
+  MVT EVT = VT.getVectorElementType();
+  SDValue V1 = SVOp->getOperand(0);
+  SDValue V2 = SVOp->getOperand(1);
+  auto Mask = SVOp->getMask();
+  assert((VT == MVT::v4f32 || VT == MVT::v4i32) &&
+         "unsupported vector type for insertps/pinsrd");
+
+  int FromV1 = std::count_if(Mask.begin(), Mask.end(),
+                             [](const int &i) { return i < 4; });
+
+  SDValue From;
+  SDValue To;
+  unsigned DestIndex;
+  if (FromV1 == 1) {
+    From = V1;
+    To = V2;
+    DestIndex = std::find_if(Mask.begin(), Mask.end(),
+                             [](const int &i) { return i < 4; }) -
+                Mask.begin();
+  } else {
+    From = V2;
+    To = V1;
+    DestIndex = std::find_if(Mask.begin(), Mask.end(),
+                             [](const int &i) { return i >= 4; }) -
+                Mask.begin();
+  }
+
+  if (MayFoldLoad(From)) {
+    // Trivial case, when From comes from a load and is only used by the
+    // shuffle. Make it use insertps from the vector that we need from that
+    // load.
+    SDValue Addr = From.getOperand(1);
+    SDValue NewAddr =
+        DAG.getNode(ISD::ADD, dl, Addr.getSimpleValueType(), Addr,
+                    DAG.getConstant(DestIndex * EVT.getStoreSize(),
+                                    Addr.getSimpleValueType()));
+
+    LoadSDNode *Load = cast<LoadSDNode>(From);
+    SDValue NewLoad =
+        DAG.getLoad(EVT, dl, Load->getChain(), NewAddr,
+                    DAG.getMachineFunction().getMachineMemOperand(
+                        Load->getMemOperand(), 0, EVT.getStoreSize()));
+
+    if (EVT == MVT::f32) {
+      // Create this as a scalar to vector to match the instruction pattern.
+      SDValue LoadScalarToVector =
+          DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, NewLoad);
+      SDValue InsertpsMask = DAG.getIntPtrConstant(DestIndex << 4);
+      return DAG.getNode(X86ISD::INSERTPS, dl, VT, To, LoadScalarToVector,
+                         InsertpsMask);
+    } else { // EVT == MVT::i32
+      // If we're getting an i32 from memory, use an INSERT_VECTOR_ELT
+      // instruction, to match the PINSRD instruction, which loads an i32 to a
+      // certain vector element.
+      return DAG.getNode(ISD::INSERT_VECTOR_ELT, dl, VT, To, NewLoad,
+                         DAG.getConstant(DestIndex, MVT::i32));
+    }
+  }
+
+  // Vector-element-to-vector
+  unsigned SrcIndex = Mask[DestIndex] % 4;
+  SDValue InsertpsMask = DAG.getIntPtrConstant(DestIndex << 4 | SrcIndex << 6);
+  return DAG.getNode(X86ISD::INSERTPS, dl, VT, To, From, InsertpsMask);
+}
+
 // Reduce a vector shuffle to zext.
 static SDValue LowerVectorIntExtend(SDValue Op, const X86Subtarget *Subtarget,
                                     SelectionDAG &DAG) {
   // PMOVZX is only available from SSE41.
   if (!Subtarget->hasSSE41())
     return SDValue();
 
   MVT VT = Op.getSimpleValueType();
X86TargetLowering::LowerVECTOR_SHUFFLE(SDValue Op, SelectionDAG &DAG) const {
   if (isVPERM2X128Mask(M, VT, HasFp256))
     return getTargetShuffleNode(X86ISD::VPERM2X128, dl, VT, V1,
                                 V2, getShuffleVPERM2X128Immediate(SVOp), DAG);
 
   SDValue BlendOp = LowerVECTOR_SHUFFLEtoBlend(SVOp, Subtarget, DAG);
   if (BlendOp.getNode())
     return BlendOp;
 
+  if (Subtarget->hasSSE41() && isINSERTPSMask(M, VT))
+    return getINSERTPS(SVOp, dl, DAG);
+
   unsigned Imm8;
   if (V2IsUndef && HasInt256 && isPermImmMask(M, VT, Imm8))
     return getTargetShuffleNode(X86ISD::VPERMI, dl, VT, V1, Imm8, DAG);
 
   if ((V2IsUndef && HasInt256 && VT.is256BitVector() && NumElems == 8) ||
       VT.is512BitVector()) {
     MVT MaskEltVT = MVT::getIntegerVT(VT.getVectorElementType().getSizeInBits());
     MVT MaskVectorVT = MVT::getVectorVT(MaskEltVT, NumElems);

test/CodeGen/X86/sse41.ll

-; RUN: llc < %s -mtriple=i686-apple-darwin9 -mattr=sse4.1 -mcpu=penryn | FileCheck %s -check-prefix=X32
-; RUN: llc < %s -mtriple=x86_64-apple-darwin9 -mattr=sse4.1 -mcpu=penryn | FileCheck %s -check-prefix=X64
+; RUN: llc < %s -mtriple=i686-apple-darwin9 -mattr=sse4.1 -mcpu=penryn | FileCheck %s -check-prefix=X32 --check-prefix=CHECK
+; RUN: llc < %s -mtriple=x86_64-apple-darwin9 -mattr=sse4.1 -mcpu=penryn | FileCheck %s -check-prefix=X64 --check-prefix=CHECK
 
 @g16 = external global i16
 
 define <4 x i32> @pinsrd_1(i32 %s, <4 x i32> %tmp) nounwind {
         %tmp1 = insertelement <4 x i32> %tmp, i32 %s, i32 1
         ret <4 x i32> %tmp1
 ; X32-LABEL: pinsrd_1:
 ; X32:    pinsrd $1, 4(%esp), %xmm0

 ; X32: ret
 ; X64-LABEL: buildvector:
 ; X64-NOT: insertps $0
 ; X64: insertps $16
 ; X64-NOT: insertps $0
 ; X64: ret
 }
 
+define <4 x float> @insertps_from_shufflevector_1(<4 x float> %a, <4 x float>* nocapture readonly %pb) {
+entry:
+  %0 = load <4 x float>* %pb, align 16
+  %vecinit6 = shufflevector <4 x float> %a, <4 x float> %0, <4 x i32> <i32 0, i32 1, i32 2, i32 4>
+  ret <4 x float> %vecinit6
+; CHECK-LABEL: insertps_from_shufflevector_1:
+; CHECK-NOT: shufps
+; CHECK: insertps    $48,
+; CHECK: ret
+}
+
+define <4 x float> @insertps_from_shufflevector_2(<4 x float> %a, <4 x float> %b) {
+entry:
+  %vecinit6 = shufflevector <4 x float> %a, <4 x float> %b, <4 x i32> <i32 0, i32 1, i32 5, i32 3>
+  ret <4 x float> %vecinit6
+; CHECK-LABEL: insertps_from_shufflevector_2:
+; CHECK-NOT: mov
+; CHECK-NOT: shufps
+; CHECK: insertps    $96,
+; CHECK: ret
+}
+
+; For loading an i32 from memory into an xmm register we use pinsrd
+; instead of insertps
+define <4 x i32> @pinsrd_from_shufflevector_i32(<4 x i32> %a, <4 x i32>* nocapture readonly %pb) {
+entry:
+  %0 = load <4 x i32>* %pb, align 16
+  %vecinit6 = shufflevector <4 x i32> %a, <4 x i32> %0, <4 x i32> <i32 0, i32 1, i32 2, i32 4>
+  ret <4 x i32> %vecinit6
+; CHECK-LABEL: pinsrd_from_shufflevector_i32:
+; CHECK-NOT: mov
+; CHECK-NOT: shufps
+; CHECK: pinsrd  $3,
+; CHECK: ret
+}
+
+define <4 x i32> @insertps_from_shufflevector_i32_2(<4 x i32> %a, <4 x i32> %b) {
+entry:
+  %vecinit6 = shufflevector <4 x i32> %a, <4 x i32> %b, <4 x i32> <i32 0, i32 7, i32 2, i32 3>
+  ret <4 x i32> %vecinit6
+; CHECK-LABEL: insertps_from_shufflevector_i32_2:
+; CHECK-NOT: mov
+; CHECK-NOT: shufps
+; CHECK: insertps    $208,
+; CHECK: ret
+}
+
+define <4 x float> @insertps_from_load_ins_elt_undef(<4 x float> %a, float* %b) {
+; CHECK-LABEL: insertps_from_load_ins_elt_undef:
+; CHECK-NOT: mov
+; CHECK-NOT: shufps
+; CHECK: insertps    $16,
+; CHECK: ret
+  %1 = load float* %b, align 4
+  %2 = insertelement <4 x float> undef, float %1, i32 0
+  %result = shufflevector <4 x float> %a, <4 x float> %2, <4 x i32> <i32 0, i32 4, i32 2, i32 3>
+  ret <4 x float> %result
+}
+
+define <4 x i32> @insertps_from_load_ins_elt_undef_i32(<4 x i32> %a, i32* %b) {
+; CHECK-LABEL: insertps_from_load_ins_elt_undef_i32:
+; TODO: Like on pinsrd_from_shufflevector_i32, remove this mov instr
+;; aCHECK-NOT: mov
+; CHECK-NOT: shufps
+; CHECK: insertps    $32,
+; CHECK: ret
+  %1 = load i32* %b, align 4
+  %2 = insertelement <4 x i32> undef, i32 %1, i32 0
+  %result = shufflevector <4 x i32> %a, <4 x i32> %2, <4 x i32> <i32 0, i32 1, i32 4, i32 3>
+  ret <4 x i32> %result
+}