[AArch64] Fix a bug generating incorrect instruction when building small vector.

[kevin.qin]

Summary

This bug is introduced by r211144. When building a v4i8 vector, v4i8 will be widened to v4i16 after legalization. Then the element of operand is smaller than the element of result, but previous commit can only handle the contrary condition. This patch is going to handle this scenario and to generate optimized codes like ZIP1. Please review.

Regard,
Kevin

[mcrosier]

Tim should probably give the final LGTM, but I don't see any glaring issues. I'll kick of regression tests and let you know how it goes.

lib/Target/AArch64/AArch64ISelLowering.cpp

4160

Perhaps, just ResMultiplier.

[mcrosier]

The regressions have been resolved by this patch.

[kevin.qin]

Small changes according to Chad's comments.

[mcrosier]

Ping.

[kevin.qin]

Re-ping...

2014-07-12 0:13 GMT+08:00 Chad Rosier <[e-mail]>:

Ping.

http://reviews.llvm.org/D4385

[t.p.northover]

Hi Kevin,

Sorry this took so long to review. I kept putting it off because the code looked nasty for what it was trying to achieve. It actually turned out much better than I was expecting though (I have comments, but they're superficial rather than horrified).

Cheers.

Tim.

lib/Target/AArch64/AArch64ISelLowering.cpp

4167–4172

I think this is putting too much emphasis on the v4i8 origin of the DAG rather than what's actually in front of us: a v4i16 BUILD_VECTOR made up of a set of v8i8 extractions (and even that's too much of a special case).

This loop also looked more intimidating than it needed to because of this big block comment inside. If the purpose is explained completely outside, the entire thing becomes a fairly trivial 3-4 line loop.

4173

I don't think this is correct. Imagine an output vector of v4i32, produced from SourceVecs with type v8i16 and v16i8. This situation should give ResMultiplier = 4, but it would end up as 2.

4189–4192

This comment seems stale. While you're in the area could you rephrase it to something more accurate?

4269–4270

I don't think this is generic enough. Again in the situation with two mismatched sources (so take a v4i32 VT being produced from a v4i16 and a v8i8 for example).

Anything coming from the v4i16 needs to set *two* elements of Mask properly (and then 2 undefs).

I'm not sure, but a more thorough restructuring of this loop might make the result clearer too. Don't be afraid to move things about if you see anything.

4277–4279

LLVM will omit the bitcast if it's not needed. It's simpler to just "return DAG.getNode(ISD::BITCAST, ...);".

[kevin.qin]

Hi Tim,

Thanks for your review. I also hate this implementation, which is so complex and may introduce some potential bug just like what this patch is going to fix. I hope this patch could bring peace in this area some time, otherwise we should consider to refactor the whole function. Some inline comments below.

Regards,
Kevin

lib/Target/AArch64/AArch64ISelLowering.cpp

4173

Yes, you are right. ResMultiplier should multiply itself with other part.

4269–4270

For your example, v4i32 will bitcast to v16i8, which only 0, 8, 16, 24 are valid lane number, and all other lanes should be undef. The valid lane number is decided by ResMultiplier only, and independent to sources. So I think this code can cover all scenarios including two sources are mismatched(The mismatching of two sources will reflect on their OffsetMultipliers, and finally change the Mask number). But I can make a change for code style.

[kevin.qin]

This is the updated patch. Please review.

Regards,
Kevin

[t.p.northover]

Hi Kevin,

I'm not quite convinced yet:

lib/Target/AArch64/AArch64ISelLowering.cpp

4203

It's actually far easier to just set ResMultiplier once outside the loop: you know SmallestEltTy and VT.getVectorElementType(). Those give the correct ratio.

4269–4270

OK, I don't think I was clear enough. Let's look at a concrete example. Take LHS = v4i16, RHS = v8i8, result = v2i32 and imagine something like

(BUILD_VECTOR (i32 extract_element LHS, 2),
              (i32 extract_element RHS, 0))

I think this should lead to v8i8 as the basic shuffle type (we agree there), with indices <4, 5, u, u, 8, u, u, u>. I think the current loop discards the 5, though.

[kevin.qin]

See comments below.

Regards,
Kevin

lib/Target/AArch64/AArch64ISelLowering.cpp

4203

I got myself limited to the previous solution.... Get it out of the loop is a better idea.

4269–4270

If LHS = v4i16, RHS = v8i8, result = v2i32, it must be LHS = v4i8, RHS = v8i8, result = v2i8 before legalization. Because the actual lane size is decided by the smallest element size among result and 2 operands, and all other larger element sizes must come from legalization. Please correct me if I'm wrong. Based on this logic, the mask <4, u, u, u, 8, u, u, u> is correct.

[t.p.northover]

If LHS = v4i16, RHS = v8i8, result = v2i32, it must be LHS = v4i8, RHS = v8i8, result = v2i8 before legalization. Because the actual lane size is decided by the smallest element size among result and 2 operands, and all other larger element sizes must come from legalization. Please correct me if I'm wrong. Based on this logic, the mask <4, u, u, u, 8, u, u, u> is correct.

You shouldn't be assuming that these nodes come from some specific
path through legalisation that you understand. The node we're given
has clear semantics, no matter how it got to us, and it says that 16
bits from LHS need to be inserted into the final vector.

This isn't even theoretical, see the attached file for something that
reaches ReconstructShuffle very much as I described (I had to use
v4i32 as the result since only results with >= 4 vectors call
ReconstructShuffle).

Cheers.

Tim.

• simple.ll450 BDownload

[t.p.northover]

Actually, the more I think about that .ll file the more I worry that it's really showing a bug in DAGCombiner. It just happened to be the first AND-elision code I spotted that I thought I could exploit.

I think the point still stands though: these nodes can come from anywhere and we have to deal with them properly.

Cheers.

Tim.

[kevin.qin]

Hi Tim,

Here is the new revision adding codes to compute how many parts of split lane should be inserted. Please have a look.

Thanks,
Kevin

[t.p.northover]

Hi Kevin,

I think the function is correct now, but that second test is pretty much useless if it really is relying on a bug in the DAG-combiner. As soon as someone fixes that it'll no longer even exercise the code it's supposed to.

I've got one or two ideas to improve this function with refactoring, though, so I think you should probably just commit and then I can take a look afterwards.

So LGTM! Thanks for working on this for so long (and being patient at the beginning).

Cheers.

Tim.

[kevin.qin]

Hi Tim,

I removed the new test and committed at r213830.

Cheers,
Kevin

[mcrosier]

Committed in r213830.

lib/Target/AArch64/AArch64ISelLowering.cpp

   if (SourceVecs.size() > 2)
     return SDValue();
 
-  SDValue ShuffleSrcs[2] = { DAG.getUNDEF(VT), DAG.getUNDEF(VT) };
+  // Find out the smallest element size among result and two sources, and use
+  // it as element size to build the shuffle_vector.
+  EVT SmallestEltTy = VT.getVectorElementType();
+  for (unsigned i = 0; i < SourceVecs.size(); ++i) {
+    EVT SrcEltTy = SourceVecs[i].getValueType().getVectorElementType();
+    if (SrcEltTy.bitsLT(SmallestEltTy)) {
+      SmallestEltTy = SrcEltTy;
+    }
+  }
+  unsigned ResMultiplier =
+      VT.getVectorElementType().getSizeInBits() / SmallestEltTy.getSizeInBits();
   int VEXTOffsets[2] = { 0, 0 };
   int OffsetMultipliers[2] = { 1, 1 };
+  NumElts = VT.getSizeInBits() / SmallestEltTy.getSizeInBits();
+  EVT ShuffleVT = EVT::getVectorVT(*DAG.getContext(), SmallestEltTy, NumElts);
+  SDValue ShuffleSrcs[2] = {DAG.getUNDEF(ShuffleVT), DAG.getUNDEF(ShuffleVT)};
 
   // This loop extracts the usage patterns of the source vectors
   // and prepares appropriate SDValues for a shuffle if possible.

     unsigned NumSrcElts = SourceVecs[i].getValueType().getVectorNumElements();
     SDValue CurSource = SourceVecs[i];
     if (SourceVecs[i].getValueType().getVectorElementType() !=
-        VT.getVectorElementType()) {
-      // It may hit this case if SourceVecs[i] is AssertSext/AssertZext.
-      // Then bitcast it to the vector which holds asserted element type,
-      // and record the multiplier of element width between SourceVecs and
-      // Build_vector which is needed to extract the correct lanes later.
-      EVT CastVT =
-          EVT::getVectorVT(*DAG.getContext(), VT.getVectorElementType(),
-                           SourceVecs[i].getValueSizeInBits() /
-                               VT.getVectorElementType().getSizeInBits());
+        ShuffleVT.getVectorElementType()) {
+      // As ShuffleVT holds smallest element size, it may hit here only if
+      // the element type of SourceVecs is bigger than that of ShuffleVT.
+      // Adjust the element size of SourceVecs to match ShuffleVT, and record
+      // the multipliers.
+      EVT CastVT = EVT::getVectorVT(
+          *DAG.getContext(), ShuffleVT.getVectorElementType(),
+              ShuffleVT.getVectorElementType().getSizeInBits());
 
       CurSource = DAG.getNode(ISD::BITCAST, dl, CastVT, SourceVecs[i]);
       OffsetMultipliers[i] = CastVT.getVectorNumElements() / NumSrcElts;

       MinElts[i] *= OffsetMultipliers[i];
     }
 
-    if (CurSource.getValueType() == VT) {
+    if (CurSource.getValueType() == ShuffleVT) {
       // No VEXT necessary
       ShuffleSrcs[i] = CurSource;
       VEXTOffsets[i] = 0;

     } else if (NumSrcElts < NumElts) {
       // We can pad out the smaller vector for free, so if it's part of a
       // shuffle...
-      ShuffleSrcs[i] = DAG.getNode(ISD::CONCAT_VECTORS, dl, VT, CurSource,
-                                   DAG.getUNDEF(CurSource.getValueType()));
+      ShuffleSrcs[i] =
+          DAG.getNode(ISD::CONCAT_VECTORS, dl, ShuffleVT, CurSource,
+                      DAG.getUNDEF(CurSource.getValueType()));
       continue;
     }
 

     if (MinElts[i] >= NumElts) {
       // The extraction can just take the second half
       VEXTOffsets[i] = NumElts;
-      ShuffleSrcs[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, CurSource,
-                                   DAG.getIntPtrConstant(NumElts));
+      ShuffleSrcs[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, ShuffleVT,
+                                   CurSource, DAG.getIntPtrConstant(NumElts));
     } else if (MaxElts[i] < NumElts) {
       // The extraction can just take the first half
       VEXTOffsets[i] = 0;
-      ShuffleSrcs[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, CurSource,
-                                   DAG.getIntPtrConstant(0));
+      ShuffleSrcs[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, ShuffleVT,
+                                   CurSource, DAG.getIntPtrConstant(0));
     } else {
       // An actual VEXT is needed
       VEXTOffsets[i] = MinElts[i];
-      SDValue VEXTSrc1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, CurSource,
-                                     DAG.getIntPtrConstant(0));
-      SDValue VEXTSrc2 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, VT, CurSource,
-                                     DAG.getIntPtrConstant(NumElts));
+      SDValue VEXTSrc1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, ShuffleVT,
+                                     CurSource, DAG.getIntPtrConstant(0));
+      SDValue VEXTSrc2 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, ShuffleVT,
+                                     CurSource, DAG.getIntPtrConstant(NumElts));
       unsigned Imm = VEXTOffsets[i] * getExtFactor(VEXTSrc1);
-      ShuffleSrcs[i] = DAG.getNode(AArch64ISD::EXT, dl, VT, VEXTSrc1, VEXTSrc2,
-                                   DAG.getConstant(Imm, MVT::i32));
+      ShuffleSrcs[i] = DAG.getNode(AArch64ISD::EXT, dl, ShuffleVT, VEXTSrc1,
+                                   VEXTSrc2, DAG.getConstant(Imm, MVT::i32));
     }
   }
 
   SmallVector<int, 8> Mask;
+  unsigned VTEltSize = VT.getVectorElementType().getSizeInBits();
 
-  for (unsigned i = 0; i < NumElts; ++i) {
+  for (unsigned i = 0; i < VT.getVectorNumElements(); ++i) {
     SDValue Entry = Op.getOperand(i);
-    if (Entry.getOpcode() == ISD::UNDEF) {
-      Mask.push_back(-1);
-      continue;
+    int SourceNum = 1;
+    unsigned LanePartNum = 0;
+    int ExtractElt;
+    if (Entry.getOpcode() != ISD::UNDEF) {
+      // Check how many parts of source lane should be inserted.
+      SDValue ExtractVec = Entry.getOperand(0);
+      if (ExtractVec == SourceVecs[0])
+        SourceNum = 0;
+      ExtractElt = cast<ConstantSDNode>(Entry.getOperand(1))->getSExtValue();
+      unsigned ExtEltSize =
+          ExtractVec.getValueType().getVectorElementType().getSizeInBits();
+      unsigned SmallerSize = ExtEltSize < VTEltSize ? ExtEltSize : VTEltSize;
+      LanePartNum = SmallerSize / SmallestEltTy.getSizeInBits();
     }
 
-    SDValue ExtractVec = Entry.getOperand(0);
-    int ExtractElt =
-        cast<ConstantSDNode>(Op.getOperand(i).getOperand(1))->getSExtValue();
-    if (ExtractVec == SourceVecs[0]) {
-      Mask.push_back(ExtractElt * OffsetMultipliers[0] - VEXTOffsets[0]);
-    } else {
-      Mask.push_back(ExtractElt * OffsetMultipliers[1] + NumElts -
-                     VEXTOffsets[1]);
+    for (unsigned j = 0; j != ResMultiplier; ++j) {
+      if (j < LanePartNum)
+        Mask.push_back(ExtractElt * OffsetMultipliers[SourceNum] +
+                       NumElts * SourceNum - VEXTOffsets[SourceNum] + j);
+      else
+        Mask.push_back(-1);
     }
   }
 
   // Final check before we try to produce nonsense...
-  if (isShuffleMaskLegal(Mask, VT))
-    return DAG.getVectorShuffle(VT, dl, ShuffleSrcs[0], ShuffleSrcs[1],
-                                &Mask[0]);
+  if (isShuffleMaskLegal(Mask, ShuffleVT)) {
+    SDValue Shuffle = DAG.getVectorShuffle(ShuffleVT, dl, ShuffleSrcs[0],
+                                           ShuffleSrcs[1], &Mask[0]);
+    return DAG.getNode(ISD::BITCAST, dl, VT, Shuffle);
+  }
 
   return SDValue();
 }

test/CodeGen/AArch64/arm64-neon-copy.ll

  %r = shufflevector <1 x i8> %a, <1 x i8> undef, <16 x i32> zeroinitializer
  ret <16 x i8> %r
 }
+
+define <4 x i32> @build_vector_diff(<4 x i16>* %lhs.addr, <8 x i8>* %rhs.addr) {
+; CHECK-LABEL: build_vector_diff:
+; CHECK:  ldr  d[[TMP_VREG0:[0-9]+]], [x0]
+; CHECK:  ldr  d[[TMP_VREG1:[0-9]+]], [x1]
+; CHECK:  umov  w[[TMP_GREG0:[0-9]+]], v[[TMP_VREG0]].h[2]
+; CHECK:  umov  w[[TMP_GREG1:[0-9]+]], v[[TMP_VREG1]].b[0]
+; CHECK:  fmov  s0, w[[TMP_GREG0]]
+; CHECK:  ins v0.s[1], w[[TMP_GREG1]]
+
+  %lhs = load <4 x i16>* %lhs.addr
+  %elt1.tmp = extractelement <4 x i16> %lhs, i32 2
+  %elt1 = zext i16 %elt1.tmp to i32
+
+  %rhs = load <8 x i8>* %rhs.addr
+  %elt2.tmp = extractelement <8 x i8> %rhs, i32 0
+  %elt2 = zext i8 %elt2.tmp to i32
+
+  %vec0 = insertelement <4 x i32> undef, i32 %elt1, i32 0
+  %vec1 = insertelement <4 x i32> %vec0, i32 %elt2, i32 1
+
+  ret <4 x i32> %vec1
+}
+

test/CodeGen/AArch64/neon-perm.ll

   ret <8 x i16> %shuffle.i
 }
 
+define <4 x i8> @test_vzip1_v4i8(<8 x i8> %p) {
+; CHECK-LABEL: test_vzip1_v4i8:
+; CHECK: zip1 {{v[0-9]+}}.8b, {{v[0-9]+}}.8b, {{v[0-9]+}}.8b
+ %lo = shufflevector <8 x i8> %p, <8 x i8> undef, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
+ ret <4 x i8> %lo
+}
+
 define <8 x i8> @test_same_vzip2_s8(<8 x i8> %a) {
 ; CHECK-LABEL: test_same_vzip2_s8:
 ; CHECK: zip2 {{v[0-9]+}}.8b, {{v[0-9]+}}.8b, {{v[0-9]+}}.8b