[SystemZ] Expand vector zero-extend into a shuffle.

[jonpa]

Summary

This is a preparatory patch for generating more VLLEZ instructions, although it also has some benefits on its own.

lowerExtendVectorInreg() no longer unpacks ZERO_EXTEND_VECTOR_INREG always, but instead expands to a shuffle with a zero vector.

GeneralShuffle::getNode() now detects and handles cases which involves a zero vector. An advantage to this is that it is now possible to tune when a vperm or unpacking should be used, depending on how many unpacks are needed.
It seemed to work better to use the new UnpackInfo struct to work on the byte level directly, rather than trying to detect byte sequences and from that deduce the unpacks needed.

It is also necessary to handle the cases of a shuffled input source, which must be done cleverly to avoid generating worse code.

An alternative to this - for the purpose of VLLEZ - might be to only expand those potential candidates to shuffles. Expanding all of them reduces the number of vperms generally since more cases can now be handled with unpacks, but there is also need to find the zero vector and make sure to handle it last in getNode().

When realizing that the number of permutes increased at one point I attempted an algorithm to find different orders of shuffling in getNode(). This was however not a simple thing to do since the DAG nodes could then not be created when evaluating an order of the shuffles. I then however found out that putting the new zero vector last handled this problem and now vperms are same or less on all files with this.

On Imagick (this time without ffp-contract=fast), this gave a good improvement *without* VLLEZ. Using the other vllez-patch directly (https://reviews.llvm.org/D76275) gave a slightly bigger improvement. Using this patch and also generating VLLEZs gave the exact same improvement as the first patch. So looking at just this benchmark, I see that this patch is beneficial on its own, but if generating VLLEZ it doesn't really play a role.

Apart from Imagick, I see a 2.5% improvement on x264 if using -max-unpackops=2, which is interesting.

Other notes:

lowerExtendVectorInreg(): All extended bytes are defined to 0, even if the original element was -1. Is this needed, or could it be assumed that a zero-extended undefined element have all bytes undefined as well? Not sure if it matters.

unpacking with a permute: There are a few (140) cases with only two defined elements, where the VPERM of Best.Mask can be done with a VREPI. Most of those cases however required 3 unpacks after the VPERM, and just a dozen could be done with 2 unpacks after. I removed that check since it also did not seem to improve any benchmarks.

New tests: fun0: This particular set of values (i8 compares -> i32) seem to not work on trunk while others do.

Use -debug-only=systemz-lower to see what is going on.

[uweigand]

Hi Jonas, I haven't looked into everything in detail, but first one fundmental question: My understanding was that the current GeneralShuffle code would detect the shuffle you generate for a zero-extend as a case of a MERGE. Later, combineMERGE would detect that one input of the MERGE is a zero vector, and replace the merge by an UNPACKL.

Is there some reason why this doesn't work for you? Why do you have to create the UNPACKL already in GeneralShuffle?

llvm/lib/Target/SystemZ/SystemZISelLowering.cpp

5279

Now that this routine shares no code at all between the sign- and zero-extend case, I think it would make more sense to just have two different routines lowerSIGN_EXTEND_VECTOR_INREG and lowerZERO_EXTEND_VECTOR_INREG.

[jonpa]

Hi Jonas, I haven't looked into everything in detail, but first one fundmental question: My understanding was that the current GeneralShuffle code would detect the shuffle you generate for a zero-extend as a case of a MERGE. Later, combineMERGE would detect that one input of the MERGE is a zero vector, and replace the merge by an UNPACKL.

Is there some reason why this doesn't work for you? Why do you have to create the UNPACKL already in GeneralShuffle?

That will only work in cases where only one unpack is needed, and only if the input does not need any permutation of any kind.

Patch changed to use increasing indexes into the zero vector so that the simple case can still be matched with a MERGE_HIGH.

I am not that sure about the actual best tuning yet, but so far I have aimed to reduce the number of VPERMs. I thought originally that using isByteZero() to check if a single byte was known zero would make for detecting more cases where only one element or byte of was zero. This way, any of the operands could have a zero byte which would be detected, like a high 0 byte in a wider immediate operand, for instance. I see now however that this is no improvement compared to simply finding a zero or undef vector input, so I have changed the patch to to this instead.

lowerExtendVectorInreg() split into lowerSIGN_EXTEND_VECTOR_INREG() and lowerZERO_EXTEND_VECTOR_INREG().

[jonpa]

It certainly seems to be an improvement on two benchmarks to do just either one unpack or else a vperm (and not multiple unpacks). In fact, i505.mcf actually regressed (2.5%) when doing two unpacks instead of a vperm (with -ffp-contract=fast). So the initial idea of reducing the number of vperms seems to have been proven wrong - it is better to have a single vperm on the critical path rather than multiple unpacks.

Patch simplified to do just one unpack whenever possible.

Tests updated.

[uweigand]

In D78486#2012867, @jonpa wrote:

It certainly seems to be an improvement on two benchmarks to do just either one unpack or else a vperm (and not multiple unpacks). In fact, i505.mcf actually regressed (2.5%) when doing two unpacks instead of a vperm (with -ffp-contract=fast). So the initial idea of reducing the number of vperms seems to have been proven wrong - it is better to have a single vperm on the critical path rather than multiple unpacks.

Huh, interesting. That's good to know, and certainly makes the code simpler as well.

I'm wondering: unless I'm missing something, there's still one specific case where you generate a vperm followed by an unpack (the case where you already had a permute as source). Wouldn't it be preferable to just use a single vperm there as well?

[jonpa]

I'm wondering: unless I'm missing something, there's still one specific case where you generate a vperm followed by an unpack (the case where you already had a permute as source). Wouldn't it be preferable to just use a single vperm there as well?

This is the case where the input is a permute that has no other users, which means that it's being replaced. So instead of vperm + vperm, we get a vperm + unpack, which follows the same reasoning of replacing a vperm with a single unpack.

For example, in the case with three source ops, where A and B first are combined with a permute, and now AB and C are to be combined: instead of permuting AB and C, the AB permute is changed so that AB and C can be unpacked.

This now happens 100 times on SPEC'17:

                                 patch  <>  "No permute replacement"
vperm          :                23803                23903     +100
vl             :               109720               109797      +77
vuplhb         :                  151                  101      -50
vuplhh         :                  177                  127      -50
vst            :                85032                85078      +46
larl           :               371586               371616      +30
vgbm           :                11637                11644       +7
mvi            :                23380                23381       +1

[uweigand]

In D78486#2014509, @jonpa wrote:

I'm wondering: unless I'm missing something, there's still one specific case where you generate a vperm followed by an unpack (the case where you already had a permute as source). Wouldn't it be preferable to just use a single vperm there as well?

This is the case where the input is a permute that has no other users, which means that it's being replaced. So instead of vperm + vperm, we get a vperm + unpack, which follows the same reasoning of replacing a vperm with a single unpack.

For example, in the case with three source ops, where A and B first are combined with a permute, and now AB and C are to be combined: instead of permuting AB and C, the AB permute is changed so that AB and C can be unpacked.

Ah, that's what I missed: the case where the first permute has already two different inputs!

Now I'm wondering whether this couldn't also apply in other cases, beyond just perm + unpack. Would it be possible to handle all cases by recognizing the case where the source of a permute is itself a (single-use) permute early, e.g. in GeneralShuffle::add ? Hmm, reading that just now, it seems there is already such code:

else if (Op.getOpcode() == ISD::VECTOR_SHUFFLE && Op.hasOneUse()) {
  // See whether the bytes we need come from a contiguous part of one
  // operand.

So now I'm wondering instead: why does your new code ever trigger in the first place; why isn't this already handled in GeneralShuffle::add?

[jonpa]

I ran SPEC'2006 as well once with this new patch and found to my surprise that on z14 I saw a big (7%) regression with this on perlbench which I have never seen before, while on z15 everything was as expected. Even though I was not sure if this was a trustable result (given that perl'17 looked ok), I looked into it a bit. I found that things had changed as expected only - multiple unpacks had become vperms instead. Two things were obvious while looking at the generated code:

1. I see a larl+vl+vgbm inside a single block loop prior to the vperm. Those three instructions are loop-invariant and should (and could) be hoisted to before the loop. It seems that the target instructions look ok (the load is tagged with a 'constant-pool' MO for instance), but MachineLICM (Post-RA) is being way too conservative as regards to when a physreg def cannot be moved. Post-RA, it is keeping track of physreg clobbers for the entire outer loop and then checks if the inner loop clobbers any of those regs, it seems. That means that our LARL in a single-block loop inside a bigger loop cannot be moved out of the inner loop even though that would make sense. MachineLICM is run also pre-RA, but then only outermost loops are visited.

However, this was easy to do in the assembly file, but hoisting those instructions out of the loop proved to be entirely non-effective (no improvement).

2. one more vperm mask in the constant pool adds 16 bytes in memory, which may possibly lead to some bad side-effects, which however seems unlikely to me since inserting that constant in the assembly does not change the function as such - it seems that the constant pool area is separate from the function using the constant. I also tried inserting a dummy use along with the 16-byte constant but that did not slow down the faster version using unpacks.

This is still strange to me and it seems unpredictable to sort out so it is probably not worth further attention for the moment...

[jonpa]

So now I'm wondering instead: why does your new code ever trigger in the first place; why isn't this already handled in GeneralShuffle::add?

I think that be two different cases, where my handling is addressing a *new* permute resulting from combining two operands, when trying to combine (unpack) a third source operand with that first (new) permute.

[uweigand]

In D78486#2020042, @jonpa wrote:

So now I'm wondering instead: why does your new code ever trigger in the first place; why isn't this already handled in GeneralShuffle::add?

I think that be two different cases, where my handling is addressing a *new* permute resulting from combining two operands, when trying to combine (unpack) a third source operand with that first (new) permute.

Ah, I see. So this permute is one that had just been generated via getGeneralPermuteNode earlier in the loop? It's a bit unfortunate to first create that ISD node and then right away delete it again.

Maybe one option to try would be to do the check whether this permutation looks like an unpack (possibly requiring a permutation) at the top level *before* the loop. If this is true, then apply the permutation (in reverse) to the Bytes array, remove the zerovec from the Ops list, and run through the loop. At the end, remember to actually generate the unpack node. This would also remove the need to special-case handing the zerovec through the loop.

The whole operation would be worthwhile only if by performing the unpack we can remove the zerovec (i.e. it isn't still used elsewhere), and if by removing the zerovec the depth of the resulting tree (i.e. the critical path length) is also reduced. The depth is the log2 of the number of operands (rounded up), so if reducing the zerovec takes us from 3 to 2 ops, it is worthwhile, but if it takes us from 2 to 1 ops (or from 4 to 3 ops), then it probably is not, since adding the unpack would then just add one more instruction to the critical path.

Does this make sense?

[jonpa]

Patch updated per suggestions.

Ah, I see. So this permute is one that had just been generated via getGeneralPermuteNode earlier in the loop? It's a bit unfortunate to first create that ISD node and then right away delete it again.

Yes, that's the permute that was replaced.

Maybe one option to try would be to do the check whether this permutation looks like an unpack (possibly requiring a permutation) at the top level *before* the loop. If this is true, then apply the permutation (in reverse) to the Bytes array, remove the zerovec from the Ops list, and run through the loop. At the end, remember to actually generate the unpack node. This would also remove the need to special-case handing the zerovec through the loop.

Ah, yes... :-) Now that it seems clear that we want to use just a single unpack, it is simpler to do it in this more integrated way in getNode().

The whole operation would be worthwhile only if by performing the unpack we can remove the zerovec (i.e. it isn't still used elsewhere), and if by removing the zerovec the depth of the resulting tree (i.e. the critical path length) is also reduced. The depth is the log2 of the number of operands (rounded up), so if reducing the zerovec takes us from 3 to 2 ops, it is worthwhile, but if it takes us from 2 to 1 ops (or from 4 to 3 ops), then it probably is not, since adding the unpack would then just add one more instruction to the critical path.

That's a very good point - the idea behind building the tree of operations in the loop must be to avoid serialization so we shouldn't increase the depth with a trailing unpack. I added a check for this in case of >2 operands. For the case of a single source node shuffled with a zero vector (2 ops), there is instead a check that the unpack is enough by itself.

In rewriting this now I saw a (previous patch version) case where moving the zero-vector to last in Ops resulted in a vpkg (PACK) instead of a vperm. I am not sure if that was just a rare case, or if there are other operations than unpack that could also replace vperm if zero vector is put last. That is a separate issue from this, though, I think. Going to this version of the patch there were some minor changes which I think are the variations that arise from rearranging the Bytes vector when preparing for the unpack.

I still see two nice improvements over night: imagick:13% and x264: 4%. :-)

[jonpa]

Patch rebased.

I updated the tests and noticed that not all VGBMs where going away. In order to achieve that I added look-through of BITCAST in isZeroVector(). This changed a few files on SPEC'17:

In total 11 less VGBMs on SPEC, over 10 files, but also some unexpected changes:

• morphology.s: One *more* vgbm than before. Regalloc seems to now spill the big VGBM interval now and as a result the VGBM is rematerialized in two places which makes for actually one more VGBM with this. Here the VGBM was used also by a VFMAXDB. The VGBM was available over many blocks.

• fx.s: four more new and different VPERM masks (LCPI constants) in the text section. This seems to be because four masks where reused before, while now they are not. This is because only one of of the users of that mask had a zero vector operand. With the zero vector this mask is used:

cp#8: <i8 0, i8 1, i8 2, i8 3, i8 4, i8 5, i8 16, i8 17, i8 6, i8 7, i8 8, i8 9, i8 10, i8 11, i8 18, i8 19>

Without the zero vector, this mask instead:
cp#2: <i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 16, i8 17, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 18, i8 19>

This file also has a few more spills/reloads for some reason, probably because of the increased presence of mask registers. These side-effects are just noticed in this particular file...

It may be possible to treat this as a global problem where the goal is to minimize the number of LCPI vector constants needed, considering that removing the use of the zero vector can instead cause a new mask to be needed where as before an already existing mask could be reused. Not sure how needed or easy that would be...

In addition to this, some NFC changes:

• Removed the check for the undef vector also in this patch.
• Minor fixes such as variable renaming.
• Tests no longer need VGBMs :-)

                               master      <>        patch
vuplhh         :                 3323                  241    -3082
vuplhb         :                 3137                  220    -2917
vperm          :                20996                23777    +2781
vpkg           :                 1535                  750     -785
vl             :               109474               109943     +469
vuplhf         :                  778                  329     -449
vmrlg          :                 4481                 4088     -393
vsldb          :                  566                  191     -375
larl           :               371292               371627     +335
cghsi          :                34550                34393     -157
lg             :              1092297              1092153     -144

...

                               master      <>        patch
Spill|Reload   :               683254               683105     -149
Copies         :              1036372              1036441      +69
grep "LCPI.*:" :                17540                17741     +203

[jonpa]

About the LCPI vector constants: It seems that those 200 extra constants I noticed were not really due to the optimization of eliminating the zero-vector for PERMUTE. That optimization eliminates 239 VGBMs on SPEC, while adding only 5 more LCPIs. All the other new LCPIs caused by this patch seem to be regular VPERM masks for zero extension that are duplicated once for each function. In other words, I see the same mask in the constant pool with one copy for each function. I looked at this at file scope only (.s / .o), and I am hoping that either that is not a problem, or maybe that the linker optimizes this?

Over night results look good both with and w/out the zero-vector optimization (not much difference).

[jonpa]

llvm/lib/Target/SystemZ/SystemZISelLowering.cpp

5310

I rewrote this loop from the version on Apr 20 2020, 14:06, so that the indexes into the zero vector would be not just the first byte, but increasing. Back then that lead to some matches of MERGE_HIGH, but I see now that it's a no-op, given the optimization of the zero vector we have now added. But i suppose, it doesn't matter much either way...

[uweigand]

This looks all good to me now, we should verify that performance results are still good, and then it can go in.

llvm/lib/Target/SystemZ/SystemZISelLowering.h

private:
   bool isVectorElementLoad(SDValue Op) const;
   SDValue buildVector(SelectionDAG &DAG, const SDLoc &DL, EVT VT,
                       SmallVectorImpl<SDValue> &Elems) const;
   SDValue lowerBUILD_VECTOR(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerVECTOR_SHUFFLE(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerSCALAR_TO_VECTOR(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerINSERT_VECTOR_ELT(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerEXTRACT_VECTOR_ELT(SDValue Op, SelectionDAG &DAG) const;
-  SDValue lowerExtendVectorInreg(SDValue Op, SelectionDAG &DAG,
-                                 unsigned UnpackHigh) const;
+  SDValue lowerSIGN_EXTEND_VECTOR_INREG(SDValue Op, SelectionDAG &DAG) const;
+  SDValue lowerZERO_EXTEND_VECTOR_INREG(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerShift(SDValue Op, SelectionDAG &DAG, unsigned ByScalar) const;
 
   bool canTreatAsByteVector(EVT VT) const;
   SDValue combineExtract(const SDLoc &DL, EVT ElemVT, EVT VecVT, SDValue OrigOp,
                          unsigned Index, DAGCombinerInfo &DCI,
                          bool Force) const;
   SDValue combineTruncateExtract(const SDLoc &DL, EVT TruncVT, SDValue Op,
                                  DAGCombinerInfo &DCI) const;

llvm/lib/Target/SystemZ/SystemZISelLowering.cpp

MVT OutVT = MVT::getVectorVT(MVT::getIntegerVT(P.Operand * 8),
                                  SystemZ::VectorBytes / P.Operand);
     Op = DAG.getNode(SystemZISD::PACK, DL, OutVT, Op0, Op1);
   } else {
     Op = DAG.getNode(P.Opcode, DL, InVT, Op0, Op1);
   }
   return Op;
 }
 
+bool isZeroOrUndefVector(SDValue N) {
+  if (N->getOpcode() == ISD::SPLAT_VECTOR)
+    if (auto *Op = dyn_cast<ConstantSDNode>(N->getOperand(0)))
+      return Op->getZExtValue() == 0;
+  return N.isUndef() || ISD::isBuildVectorAllZeros(N.getNode());
+}
+
+// Keeps track of the bytes that would result after applying one or several
+// unpacks.
+struct UnpackInfo {
+  enum { ZEXT_VAL = -2 };
+  SmallVector<int, SystemZ::VectorBytes> UnpackedBytes;
+  SmallVector<unsigned, 4> AppliedUnpacks;
+  SmallVector<int, SystemZ::VectorBytes> Mask;
+  bool NeedsPermute;
+  SDValue SourceOp;
+  UnpackInfo() : NeedsPermute(false) {
+    for (unsigned El = 0; El < SystemZ::VectorBytes; El++)
+      UnpackedBytes.push_back(El);
+  }
+
+  // Apply one unpack on UnpackedBytes and insert ZEXT_VAL on the bytes that
+  // become zero.
+  void applyUnpack(unsigned FromSize) {
+    SmallVector<int, SystemZ::VectorBytes> Tmp;
+    unsigned El = 0;
+    while (El < SystemZ::VectorBytes / 2) {
+      for (unsigned i = 0; i < FromSize; i++)
+        Tmp.push_back(ZEXT_VAL);
+      for (unsigned i = 0; i < FromSize; i++)
+        Tmp.push_back(UnpackedBytes[El++]);
+    }
+    UnpackedBytes = Tmp;
+    AppliedUnpacks.push_back(FromSize);
+  }
+
+  // Return true if the applied unpacks can be used to produce the result
+  // required by Bytes of Ops[OpIdx]. If the used source operand needs
+  // rearrangement before unpacking, NeedsPermute is set and Mask holds the
+  // required order. ZeroOpIdx is the index of the known zero vector in Ops.
+  bool tryApply(const SmallVectorImpl<int> &Bytes, SDValue *Ops,
+                unsigned ZeroOpIdx) {
+    unsigned OpIdx = ZeroOpIdx == 0 ? 1 : 0;
+    Mask.assign(SystemZ::VectorBytes, -1);
+    NeedsPermute = false;
+    for (unsigned i = 0; i < SystemZ::VectorBytes; ++i) {
+      if (Bytes[i] == -1)
+        continue;
+      unsigned OpNo = Bytes[i] / SystemZ::VectorBytes;
+      unsigned Byte = Bytes[i] % SystemZ::VectorBytes;
+      if (OpNo == ZeroOpIdx && UnpackedBytes[i] == ZEXT_VAL)
+        continue;
+      if (OpNo != OpIdx || UnpackedBytes[i] == ZEXT_VAL)
+        return false;
+      Mask[UnpackedBytes[i]] = Byte;
+    }
+    for (unsigned i = 0; i < SystemZ::VectorBytes; ++i)
+      if (Mask[i] != -1 && Mask[i] != int(i)) {
+        NeedsPermute = true;
+        break;
+      }
+    SourceOp = Ops[OpIdx];
+    return true;
+  }
+
+  uint32_t getCost() {
+    if (AppliedUnpacks.empty() && !NeedsPermute)
+      return UINT32_MAX;
+    return AppliedUnpacks.size() + (NeedsPermute ? 4 : 0);
+  }
+};
+
+#ifndef NDEBUG
+static void dumpBytes(const SmallVectorImpl<int> &Bytes, std::string Msg) {
+  dbgs() << Msg.c_str() << " { ";
+  for (unsigned i = 0; i < Bytes.size(); i++) {
+    if (Bytes[i] == UnpackInfo::ZEXT_VAL)
+      dbgs() << "Z";
+    else
+      dbgs() << Bytes[i];
+    dbgs() << ", ";
+  }
+  dbgs() << "}\n";
+}
+#endif
+
 // Bytes is a VPERM-like permute vector, except that -1 is used for
 // undefined bytes.  Implement it on operands Ops[0] and Ops[1] using
 // VSLDB or VPERM.
 static SDValue getGeneralPermuteNode(SelectionDAG &DAG, const SDLoc &DL,
                                      SDValue *Ops,
                                      const SmallVectorImpl<int> &Bytes) {
   for (unsigned I = 0; I < 2; ++I)
     Ops[I] = DAG.getNode(ISD::BITCAST, DL, MVT::v16i8, Ops[I]);
for (unsigned I = 0; I < SystemZ::VectorBytes; ++I)
     if (Bytes[I] >= 0)
       IndexNodes[I] = DAG.getConstant(Bytes[I], DL, MVT::i32);
     else
       IndexNodes[I] = DAG.getUNDEF(MVT::i32);
   SDValue Op2 = DAG.getBuildVector(MVT::v16i8, DL, IndexNodes);
   return DAG.getNode(SystemZISD::PERMUTE, DL, MVT::v16i8, Ops[0], Ops[1], Op2);
 }
 
+// EXPERIMENTAL This can be used to tune the threshold as to when unpacking
+// would be used instead of a vperm. It is compared to the total number of
+// instrucions needed, which may include also shufffling of the source
+// operand before unpacking.
+static cl::opt<unsigned> MAXUNPACKOPS("max-unpackops", cl::init(4));
+
+// Detect cases where one of the source operands can be used while the other
+// bytes are zero or undefined.
+static SDValue tryShuffleWithZeroVec(SelectionDAG &DAG,
+                                     const SDLoc &DL, SDValue *Ops,
+                                     const SmallVectorImpl<int> &Bytes) {
+  // Don't use unpacks if a single VSLDB could be used.
+  unsigned StartIndex, OpNo0, OpNo1;
+  if (isShlDoublePermute(Bytes, StartIndex, OpNo0, OpNo1))
+    return SDValue();
+
+  // Try unpack(s)
+  unsigned ZeroOpIdx = (isZeroOrUndefVector(Ops[0]) ? 0 :
+                        (isZeroOrUndefVector(Ops[1]) ? 1 : UINT32_MAX));
+  if (ZeroOpIdx == UINT32_MAX)
+    return SDValue();
+  UnpackInfo Best;
+  for (unsigned Start = 1; Start <= 4; Start *= 2) {
+    UnpackInfo UPI;
+    for (unsigned From = Start; From <= 4; From *= 2) {
+      UPI.applyUnpack(From);
+      if (UPI.tryApply(Bytes, Ops, ZeroOpIdx) && Best.getCost() > UPI.getCost())
+        Best = UPI;
+    }
+  }
+  if (Best.getCost() == UINT32_MAX || Best.AppliedUnpacks.size() > MAXUNPACKOPS)
+    return SDValue();
+
+  LLVM_DEBUG(dbgs() << "\nUnpacking:\n";
+             Ops[0].dump();
+             Ops[1].dump();
+             dumpBytes(Bytes, "Given this 'Bytes' mask:"););
+  LLVM_DEBUG(dbgs() << Best.AppliedUnpacks.size()
+             << " unpack(s) needed of t" <<
+             Best.SourceOp.getNode()->PersistentId << " to produce ";
+             dumpBytes(Best.UnpackedBytes, ""););
+  if (Best.NeedsPermute) {
+    LLVM_DEBUG(dumpBytes(Best.Mask, "Shuffling before unpacking with mask:"););
+    unsigned OpNo0, OpNo1;
+    if (Best.SourceOp->use_empty() &&
+        Best.SourceOp->getOpcode() == SystemZISD::PERMUTE) {
+      // If source is a PERMUTE then modify it instead of emitting another one.
+      SDValue OrigMask = Best.SourceOp->getOperand(2);
+      SDValue IndexNodes[SystemZ::VectorBytes];
+      for (unsigned I = 0; I < SystemZ::VectorBytes; ++I) {
+        int MaskEl = Best.Mask[I];
+        if (MaskEl < 0 || OrigMask.getOperand(MaskEl).isUndef())
+          IndexNodes[I] = DAG.getUNDEF(MVT::i32);
+        else {
+          auto *COp = cast<ConstantSDNode>(OrigMask.getOperand(MaskEl));
+          IndexNodes[I] = DAG.getConstant(COp->getZExtValue(), DL, MVT::i32);
+        }
+      }
+      SDValue Op2 = DAG.getBuildVector(MVT::v16i8, DL, IndexNodes);
+      Best.SourceOp = DAG.getNode(SystemZISD::PERMUTE, DL, MVT::v16i8,
+                                  Best.SourceOp.getOperand(0),
+                                  Best.SourceOp.getOperand(1), Op2);
+    }
+    else if (const Permute *P = matchPermute(Best.Mask, OpNo0, OpNo1)) {
+      if (Best.AppliedUnpacks.size() + 1 > MAXUNPACKOPS)
+        return SDValue();
+      Best.SourceOp = getPermuteNode(DAG, DL, *P, Best.SourceOp, Best.SourceOp);
+    }
+    else {
+      if (isShlDoublePermute(Best.Mask, StartIndex, OpNo0, OpNo1)) {
+        if (Best.AppliedUnpacks.size() + 1 > MAXUNPACKOPS)
+          return SDValue();
+      } else {
+        // In order to unpack, a permute of the source is needed. If it's not a
+        // VSLDB then only do this in the cases where a single unpack is needed
+        // after the VPERM.
+        if (Best.AppliedUnpacks.size() > 1)
+          return SDValue();
+      }
+      SDValue SubOps[] = { Best.SourceOp, Best.SourceOp};
+      Best.SourceOp = getGeneralPermuteNode(DAG, DL, SubOps, Best.Mask);
+    }
+  }
+
+  // Build the unpacks.
+  unsigned FromBits = Best.AppliedUnpacks.front() * 8;
+  EVT FromVT = MVT::getVectorVT(MVT::getIntegerVT(FromBits),
+                                SystemZ::VectorBits / FromBits);
+  SDValue PackedOp = DAG.getNode(ISD::BITCAST, DL, FromVT, Best.SourceOp);
+  for (unsigned FromSize : Best.AppliedUnpacks) {
+    unsigned ToBits = FromSize * 8 * 2;
+    EVT OutVT = MVT::getVectorVT(MVT::getIntegerVT(ToBits),
+                                 SystemZ::VectorBits / ToBits);
+    PackedOp = DAG.getNode(SystemZISD::UNPACKL_HIGH, DL, OutVT, PackedOp);
+  }
+  return PackedOp;
+}
+
 namespace {
 // Describes a general N-operand vector shuffle.
 struct GeneralShuffle {
   GeneralShuffle(EVT vt) : VT(vt) {}
   void addUndef();
   bool add(SDValue, unsigned);
   SDValue getNode(SelectionDAG &, const SDLoc &);
 
SDValue GeneralShuffle::getNode(SelectionDAG &DAG, const SDLoc &DL) {
 
   if (Ops.size() == 0)
     return DAG.getUNDEF(VT);
 
   // Make sure that there are at least two shuffle operands.
   if (Ops.size() == 1)
     Ops.push_back(DAG.getUNDEF(MVT::v16i8));
 
+  // Put a zero vector last to attempt unpacking as the last operation if
+  // there are more than two operands.
+  uint32_t ZeroVecOpNo = UINT32_MAX;
+  if (Ops.size() > 2) {
+    // Find the zero vector.
+    for (unsigned I = 0; I < Ops.size() ; I++)
+      if (ISD::isBuildVectorAllZeros(Ops[I].getNode()) ||
+          (Ops[I]->getOpcode() == ISD::SPLAT_VECTOR &&
+           isa<ConstantSDNode>(Ops[I]->getOperand(0)) &&
+           cast<ConstantSDNode>(Ops[I]->getOperand(0))->getZExtValue() == 0)) {
+        ZeroVecOpNo = I;
+        break;
+      }
+    // Move it to the last position without rearranging the others.
+    unsigned LastOpNo = Ops.size() - 1;
+    if (ZeroVecOpNo != UINT32_MAX && ZeroVecOpNo != LastOpNo) {
+      SDValue ZeroOp = Ops[ZeroVecOpNo];
+      for (unsigned I = ZeroVecOpNo; I < Ops.size() - 1 ; I++)
+        Ops[I] = Ops[I + 1];
+      Ops[LastOpNo] = ZeroOp;
+      for (unsigned I = 0; I < SystemZ::VectorBytes; ++I) {
+        if (Bytes[I] >= 0) {
+          unsigned OpNo = unsigned(Bytes[I]) / SystemZ::VectorBytes;
+          if (OpNo > ZeroVecOpNo)
+            Bytes[I] -= SystemZ::VectorBytes;
+          else if (OpNo == ZeroVecOpNo)
+            Bytes[I] += SystemZ::VectorBytes * (LastOpNo - ZeroVecOpNo);
+        }
+      }
+      ZeroVecOpNo = LastOpNo;
+    }
+  }
+
   // Create a tree of shuffles, deferring root node until after the loop.
   // Try to redistribute the undefined elements of non-root nodes so that
   // the non-root shuffles match something like a pack or merge, then adjust
   // the parent node's permute vector to compensate for the new order.
   // Among other things, this copes with vectors like <2 x i16> that were
   // padded with undefined elements during type legalization.
   //
   // In the best case this redistribution will lead to the whole tree
   // using packs and merges.  It should rarely be a loss in other cases.
   unsigned Stride = 1;
-  for (; Stride * 2 < Ops.size(); Stride *= 2) {
+  // The Zero vector needs to be handled at last. Do this by skipping it
+  // below while doing one more iteration with the rest leaving only one
+  // other result.
+  unsigned ItersFactor = (ZeroVecOpNo == UINT32_MAX ? 2 : 1);
+  for (; Stride * ItersFactor < Ops.size(); Stride *= 2) {
     for (unsigned I = 0; I < Ops.size() - Stride; I += Stride * 2) {
+      if (I + Stride == ZeroVecOpNo)
+        continue;
       SDValue SubOps[] = { Ops[I], Ops[I + Stride] };
 
       // Create a mask for just these two operands.
       SmallVector<int, SystemZ::VectorBytes> NewBytes(SystemZ::VectorBytes);
       for (unsigned J = 0; J < SystemZ::VectorBytes; ++J) {
         unsigned OpNo = unsigned(Bytes[J]) / SystemZ::VectorBytes;
         unsigned Byte = unsigned(Bytes[J]) % SystemZ::VectorBytes;
         if (OpNo == I)
for (unsigned I = 0; I < Ops.size() - Stride; I += Stride * 2) {
         for (unsigned J = 0; J < SystemZ::VectorBytes; ++J)
           if (NewBytes[J] >= 0)
             Bytes[J] = I * SystemZ::VectorBytes + J;
       }
     }
   }
 
   // Now we just have 2 inputs.  Put the second operand in Ops[1].
-  if (Stride > 1) {
-    Ops[1] = Ops[Stride];
+  unsigned RHSOpNo = ZeroVecOpNo == UINT32_MAX ? Stride :ZeroVecOpNo;
+  if (RHSOpNo > 1) {
+    Ops[1] = Ops[RHSOpNo];
     for (unsigned I = 0; I < SystemZ::VectorBytes; ++I)
       if (Bytes[I] >= int(SystemZ::VectorBytes))
-        Bytes[I] -= (Stride - 1) * SystemZ::VectorBytes;
+        Bytes[I] -= (RHSOpNo - 1) * SystemZ::VectorBytes;
   }
-
   // Look for an instruction that can do the permute without resorting
   // to VPERM.
   unsigned OpNo0, OpNo1;
   SDValue Op;
   if (const Permute *P = matchPermute(Bytes, OpNo0, OpNo1))
     Op = getPermuteNode(DAG, DL, *P, Ops[OpNo0], Ops[OpNo1]);
-  else
+  else {
+    Op = tryShuffleWithZeroVec(DAG, DL, &Ops[0], Bytes);
+    if (!Op.getNode())
       Op = getGeneralPermuteNode(DAG, DL, &Ops[0], Bytes);
+  }
+
   return DAG.getNode(ISD::BITCAST, DL, VT, Op);
 }
 
 // Return true if the given BUILD_VECTOR is a scalar-to-vector conversion.
 static bool isScalarToVector(SDValue Op) {
   for (unsigned I = 1, E = Op.getNumOperands(); I != E; ++I)
     if (!Op.getOperand(I).isUndef())
       return false;
SystemZTargetLowering::lowerEXTRACT_VECTOR_ELT(SDValue Op,
   // Otherwise bitcast to the equivalent integer form and extract via a GPR.
   MVT IntVT = MVT::getIntegerVT(VT.getSizeInBits());
   MVT IntVecVT = MVT::getVectorVT(IntVT, VecVT.getVectorNumElements());
   SDValue Res = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, IntVT,
                             DAG.getNode(ISD::BITCAST, DL, IntVecVT, Op0), Op1);
   return DAG.getNode(ISD::BITCAST, DL, VT, Res);
 }
 
-SDValue
-SystemZTargetLowering::lowerExtendVectorInreg(SDValue Op, SelectionDAG &DAG,
-                                              unsigned UnpackHigh) const {
+SDValue SystemZTargetLowering::
+lowerSIGN_EXTEND_VECTOR_INREG(SDValue Op, SelectionDAG &DAG) const {
   SDValue PackedOp = Op.getOperand(0);
   EVT OutVT = Op.getValueType();
   EVT InVT = PackedOp.getValueType();
   unsigned ToBits = OutVT.getScalarSizeInBits();
   unsigned FromBits = InVT.getScalarSizeInBits();
   do {
     FromBits *= 2;
     EVT OutVT = MVT::getVectorVT(MVT::getIntegerVT(FromBits),
                                  SystemZ::VectorBits / FromBits);
-    PackedOp = DAG.getNode(UnpackHigh, SDLoc(PackedOp), OutVT, PackedOp);
+    PackedOp =
+      DAG.getNode(SystemZISD::UNPACK_HIGH, SDLoc(PackedOp), OutVT, PackedOp);
   } while (FromBits != ToBits);
   return PackedOp;
 }
 
+// Lower a ZERO_EXTEND_VECTOR_INREG to a vector shuffle with a zero vector.
+SDValue SystemZTargetLowering::
+lowerZERO_EXTEND_VECTOR_INREG(SDValue Op, SelectionDAG &DAG) const {
+  SDValue PackedOp = Op.getOperand(0);
+  SDLoc DL(Op);
+  EVT OutVT = Op.getValueType();
+  EVT InVT = PackedOp.getValueType();
+  unsigned InNumElts = InVT.getVectorNumElements();
+  unsigned OutNumElts = OutVT.getVectorNumElements();
+  unsigned NumInPerOut = InNumElts / OutNumElts;
+
+  SDValue ZeroVec =
+    DAG.getSplatVector(InVT, DL, DAG.getConstant(0, DL, InVT.getScalarType()));
+
+  SmallVector<int, 16> Mask(InNumElts);
+  unsigned ZeroVecElt = InNumElts;
+  for (unsigned PackedElt = 0; PackedElt < OutNumElts; PackedElt++) {
+    unsigned MaskElt = PackedElt * NumInPerOut;
+    unsigned End = MaskElt + NumInPerOut - 1;
+    for (; MaskElt < End; MaskElt++)
+      Mask[MaskElt] = ZeroVecElt++;
+    Mask[MaskElt] = PackedElt;
+  }
+  SDValue Shuf = DAG.getVectorShuffle(InVT, DL, PackedOp, ZeroVec, Mask);
+  return DAG.getNode(ISD::BITCAST, DL, OutVT, Shuf);
+}
+
 SDValue SystemZTargetLowering::lowerShift(SDValue Op, SelectionDAG &DAG,
                                           unsigned ByScalar) const {
   // Look for cases where a vector shift can use the *_BY_SCALAR form.
   SDValue Op0 = Op.getOperand(0);
   SDValue Op1 = Op.getOperand(1);
   SDLoc DL(Op);
   EVT VT = Op.getValueType();
   unsigned ElemBitSize = VT.getScalarSizeInBits();
case ISD::VECTOR_SHUFFLE:
     return lowerVECTOR_SHUFFLE(Op, DAG);
   case ISD::SCALAR_TO_VECTOR:
     return lowerSCALAR_TO_VECTOR(Op, DAG);
   case ISD::INSERT_VECTOR_ELT:
     return lowerINSERT_VECTOR_ELT(Op, DAG);
   case ISD::EXTRACT_VECTOR_ELT:
     return lowerEXTRACT_VECTOR_ELT(Op, DAG);
   case ISD::SIGN_EXTEND_VECTOR_INREG:
-    return lowerExtendVectorInreg(Op, DAG, SystemZISD::UNPACK_HIGH);
+    return lowerSIGN_EXTEND_VECTOR_INREG(Op, DAG);
   case ISD::ZERO_EXTEND_VECTOR_INREG:
-    return lowerExtendVectorInreg(Op, DAG, SystemZISD::UNPACKL_HIGH);
+    return lowerZERO_EXTEND_VECTOR_INREG(Op, DAG);
   case ISD::SHL:
     return lowerShift(Op, DAG, SystemZISD::VSHL_BY_SCALAR);
   case ISD::SRL:
     return lowerShift(Op, DAG, SystemZISD::VSRL_BY_SCALAR);
   case ISD::SRA:
     return lowerShift(Op, DAG, SystemZISD::VSRA_BY_SCALAR);
   default:
     llvm_unreachable("Unexpected node to lower");

llvm/test/CodeGen/SystemZ/vec-move-24.ll

+; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z14 | FileCheck %s
+;
+; Test that not vperm is used if not necessary in some cases.
+
+; Zero extension of a vector compare.
+define <4 x i32> @fun0(<4 x i8> %arg0, <4 x i8> %arg1) nounwind {
+; CHECK-LABEL: fun0:
+; CHECK-NOT: vperm
+  %tmp = icmp uge <4 x i8> %arg0, %arg1
+  %tmp1 = zext <4 x i1> %tmp to <4 x i32>
+  ret <4 x i32> %tmp1
+}
+
+; Don't do unpacks + vperm if vsldb can be used
+define <4 x i16> @fun1() {
+; CHECK-LABEL: fun1:
+; CHECK: vlrepg
+; CHECK-NEXT: vsldb
+; CHECK-NEXT: veslh
+; CHECK-NEXT: br
+  %tmp = load <8 x i8>, <8 x i8>* undef
+  %tmp3 = shufflevector <8 x i8> %tmp, <8 x i8> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %tmp4 = zext <4 x i8> %tmp3 to <4 x i16>
+  %tmp5 = shl nuw <4 x i16> %tmp4, <i16 8, i16 8, i16 8, i16 8>
+  ret <4 x i16> %tmp5
+}
+
+; Some cases of zero extensions by shuffling with a zero vector.
+define <16 x i8> @fun2(<16 x i8>* %Src) nounwind {
+; CHECK-LABEL: fun2:
+; CHECK-NOT: vperm
+  %tmp = load <16 x i8>, <16 x i8>* %Src
+  %tmp2 = shufflevector <16 x i8> zeroinitializer, <16 x i8> %tmp, <16 x i32> <i32 0, i32 1, i32 2, i32 16, i32 4, i32 5, i32 6, i32 17, i32 8, i32 9, i32 10, i32 18, i32 12, i32 13, i32 14, i32 19>
+  ret <16 x i8> %tmp2
+}
+
+define <8 x i16> @fun3(<8 x i16>* %Src) nounwind {
+; CHECK-LABEL: fun3:
+; CHECK-NOT: vperm
+  %tmp = load <8 x i16>, <8 x i16>* %Src
+  %tmp2 = shufflevector <8 x i16> zeroinitializer, <8 x i16> %tmp, <8 x i32> <i32 0, i32 1, i32 2, i32 8, i32 3, i32 4, i32 5, i32 9>
+  ret <8 x i16> %tmp2
+}
+
+define <4 x i32> @fun4(<4 x i32>* %Src) nounwind {
+; CHECK-LABEL: fun4:
+; CHECK-NOT: vperm
+  %tmp = load <4 x i32>, <4 x i32>* %Src
+  %tmp2 = shufflevector <4 x i32> zeroinitializer, <4 x i32> %tmp, <4 x i32> <i32 0, i32 4, i32 2, i32 5>
+  ret <4 x i32> %tmp2
+}
+
+; This does not require a vperm, but only a single unpack.
+define  void @fun5(i8 %Src, <32 x i8>* %Dst) nounwind {
+; CHECK-LABEL: fun5:
+; CHECK-NOT: vperm
+  %I0 = insertelement <16 x i8> undef, i8 %Src, i32 0
+  %I1 = insertelement <16 x i8> %I0, i8 %Src, i32 1
+  %I2 = insertelement <16 x i8> %I1, i8 %Src, i32 2
+  %I3 = insertelement <16 x i8> %I2, i8 %Src, i32 3
+  %I4 = insertelement <16 x i8> %I3, i8 %Src, i32 4
+  %I5 = insertelement <16 x i8> %I4, i8 %Src, i32 5
+  %I6 = insertelement <16 x i8> %I5, i8 %Src, i32 6
+  %I7 = insertelement <16 x i8> %I6, i8 %Src, i32 7
+  %I8 = insertelement <16 x i8> %I7, i8 %Src, i32 8
+  %I9 = insertelement <16 x i8> %I8, i8 %Src, i32 9
+  %I10 = insertelement <16 x i8> %I9, i8 %Src, i32 10
+  %I11 = insertelement <16 x i8> %I10, i8 %Src, i32 11
+  %I12 = insertelement <16 x i8> %I11, i8 %Src, i32 12
+  %I13 = insertelement <16 x i8> %I12, i8 %Src, i32 13
+  %I14 = insertelement <16 x i8> %I13, i8 %Src, i32 14
+  %I15 = insertelement <16 x i8> %I14, i8 %Src, i32 15
+
+  %tmp = shufflevector <16 x i8> zeroinitializer,
+                       <16 x i8> %I15,
+                       <32 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7,
+                                   i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15,
+                                   i32 16, i32 17, i32 18, i32 19, i32 20, i32 21, i32 22, i32 23,
+                                   i32 24, i32 25, i32 26, i32 27, i32 28, i32 29, i32 30, i32 31>
+  %tmp9 = shufflevector <32 x i8> undef,
+                        <32 x i8> %tmp,
+                        <32 x i32> <i32 33, i32 32, i32 48, i32 49, i32 1, i32 17, i32 50, i32 51,
+                                    i32 2, i32 18, i32 52, i32 53, i32 3, i32 19, i32 54, i32 55,
+                                    i32 4, i32 20, i32 56, i32 57, i32 5, i32 21, i32 58, i32 59,
+                                    i32 6, i32 22, i32 60, i32 61, i32 7, i32 62, i32 55, i32 63>
+
+  store <32 x i8> %tmp9, <32 x i8>* %Dst
+  ret void
+}
+
+; Unpacking after a vsldb, and not a vperm.
+define void @fun6()  {
+; CHECK-LABEL: fun6:
+; CHECK-NOT: vperm
+  %tmp = load <16 x i8>, <16 x i8>* undef, align 1
+  %tmp2 = shufflevector <16 x i8> zeroinitializer, <16 x i8> %tmp, <16 x i32> <i32 0, i32 1, i32 2, i32 28, i32 4, i32 5, i32 6, i32 29, i32 8, i32 9, i32 10, i32 30, i32 12, i32 13, i32 14, i32 31>
+  store <16 x i8> %tmp2, <16 x i8>* undef
+  ret void
+}
+
+; This should only require one vperm.
+define void @fun7(<4 x i16>* %Src, <4 x i16>* %Src2, <4 x i32>* %Dst) {
+; CHECK-LABEL: fun7:
+; CHECK: vperm
+; CHECK-NOT: vperm
+  %l = load <4 x i16>, <4 x i16>* %Src
+  %l2 = load <4 x i16>, <4 x i16>* %Src2
+  %sh = shufflevector <4 x i16> %l, <4 x i16> %l2, <4 x i32> <i32 1, i32 0, i32 5, i32 6>
+  %z = zext <4 x i16> %sh to <4 x i32>
+  store <4 x i32> %z, <4 x i32>* %Dst
+  ret void
+}
+
+; Should only require two vperms.
+define void @fun8()  {
+; CHECK-LABEL: fun8:
+; CHECK: vperm
+; CHECK: vperm
+; CHECK-NOT: vperm
+  %tmp = load <48 x i8>, <48 x i8>* null, align 1
+  %tmp6 = shufflevector <48 x i8> %tmp, <48 x i8> undef, <8 x i32> <i32 0, i32 6, i32 12, i32 18, i32 24, i32 30, i32 36, i32 42>
+  %tmp7 = zext <8 x i8> %tmp6 to <8 x i16>
+  %tmp8 = shufflevector <8 x i16> %tmp7, <8 x i16> undef, <16 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15>
+  %tmp9 = shufflevector <16 x i16> %tmp8, <16 x i16> undef, <32 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15, i32 16, i32 17, i32 18, i32 19, i32 20, i32 21, i32 22, i32 23, i32 24, i32 25, i32 26, i32 27, i32 28, i32 29, i32 30, i32 31>
+  %tmp10 = shufflevector <32 x i16> %tmp9, <32 x i16> undef, <40 x i32> <i32 0, i32 8, i32 16, i32 24, i32 32, i32 1, i32 9, i32 17, i32 25, i32 33, i32 2, i32 10, i32 18, i32 26, i32 34, i32 3, i32 11, i32 19, i32 27, i32 35, i32 4, i32 12, i32 20, i32 28, i32 36, i32 5, i32 13, i32 21, i32 29, i32 37, i32 6, i32 14, i32 22, i32 30, i32 38, i32 7, i32 15, i32 23, i32 31, i32 39>
+  store <40 x i16> %tmp10, <40 x i16>* undef, align 2
+  ret void
+}