[PowerPC] Avoid perfect shuffle when mask has multiple uses

[qiucf]

Summary

The perfect shuffle (only enabled in big endian yet) may transform a shuffle vector into multiple merge/inserts, but when the shuffle mask is shared between multiple shuffles, it's better to use a single load with multiple vperm.

An obvious blocker is the mask is not operand of vector_shuffle in DAG, so I have to record all masks and check number of uses of each mask.

[shchenz]

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

10050

Please fix all the Lint warnings.

10063

Can we first check isLittleEndian and then isFourElementShuffle and then MaskMap[PermMask].second to improve the compile time?

[qiucf]

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

10063

isFourElementShuffle is also computed, when we think it's unprofitable to do perfect shuffle, it's meaningless to compute it.

Do you mean we check endian first, and only calculate MaskMap on big endian? That may improve compile time, but only before little-endian perfect shuffles are implemented.

[qiucf]

Fix clang-format warnings

[shchenz]

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

10063

yes, right, I mean we first check the expressions which have lower complexity.

[qiucf]

This method isn't sound, because there're many other optimizations (before perfect shuffle and vperm), these lowered shuffles shouldn't be counted.

[nemanjai]

This adds a whole lot of computation on the DAG in addition to having thread safety issues and the gain is very small. I am not in favour of something similar to this.

[qiucf]

Abandon this in favor of D121082.

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

        PPC::isVMRGEOShuffleMask(SVOp, true, ShuffleKind, DAG) ||
        PPC::isVMRGEOShuffleMask(SVOp, false, ShuffleKind, DAG))))
     return Op;
 
   // Check to see if this is a shuffle of 4-byte values.  If so, we can use our
   // perfect shuffle table to emit an optimal matching sequence.
   ArrayRef<int> PermMask = SVOp->getMask();
 
-  unsigned PFIndexes[4];
-  bool isFourElementShuffle = true;
-  for (unsigned i = 0; i != 4 && isFourElementShuffle; ++i) { // Element number
-    unsigned EltNo = 8;   // Start out undef.
-    for (unsigned j = 0; j != 4; ++j) {  // Intra-element byte.
-      if (PermMask[i*4+j] < 0)
-        continue;   // Undef, ignore it.
-
-      unsigned ByteSource = PermMask[i*4+j];
-      if ((ByteSource & 3) != j) {
-        isFourElementShuffle = false;
-        break;
+  // Record all shuffle masks in the DAG. The first integer in value part is
+  // occurance of the mask, and the second means whether it occured multiple
+  // times, because the integer will decrement and all entries should be removed
+  // after visiting current DAG.
+  static DenseMap<ArrayRef<int>, std::pair<int, bool>> MaskMap;
+
+  if (MaskMap.find(PermMask) == MaskMap.end()) {
+    for (const SDNode &Node: DAG.allnodes()) {
+      if (const auto *Shuffle = dyn_cast<ShuffleVectorSDNode>(&Node)) {
+        ArrayRef<int> TheMask = Shuffle->getMask();
+        if (MaskMap.find(TheMask) == MaskMap.end())
+          MaskMap.insert(std::make_pair(TheMask, std::make_pair(0, false)));
+        if (++MaskMap[TheMask].first > 1)
+          MaskMap[TheMask].second = true;
       }
+    }
+  }
 
-      if (EltNo == 8) {
-        EltNo = ByteSource/4;
-      } else if (EltNo != ByteSource/4) {
-        isFourElementShuffle = false;
-        break;
+  // When there're multiple shuffles sharing the same mask, we think it's
+  // cheaper to use load+vperm.
+  if (!MaskMap[PermMask].second) {
+    unsigned PFIndexes[4];
+    bool isFourElementShuffle = true;
+    for (unsigned i = 0; i != 4 && isFourElementShuffle; ++i) { // Element number
+      unsigned EltNo = 8;   // Start out undef.
+      for (unsigned j = 0; j != 4; ++j) {  // Intra-element byte.
+        if (PermMask[i*4+j] < 0)
+          continue;   // Undef, ignore it.
+
+        unsigned ByteSource = PermMask[i*4+j];
+        if ((ByteSource & 3) != j) {
+          isFourElementShuffle = false;
+          break;
+        }
+
+        if (EltNo == 8) {
+          EltNo = ByteSource/4;
+        } else if (EltNo != ByteSource/4) {
+          isFourElementShuffle = false;
+          break;
+        }
       }
+      PFIndexes[i] = EltNo;
+    }
+
+    // Remove entry of this mask from map since it's unique in current DAG.
+    MaskMap.erase(PermMask);
+
+    // If this shuffle can be expressed as a shuffle of 4-byte elements, use the
+    // perfect shuffle vector to determine if it is cost effective to do this as
+    // discrete instructions, or whether we should use a vperm.
+    // For now, we skip this for little endian until such time as we have a
+    // little-endian perfect shuffle table.
+    if (isFourElementShuffle && !isLittleEndian) {
+      // Compute the index in the perfect shuffle table.
+      unsigned PFTableIndex =
+        PFIndexes[0]*9*9*9+PFIndexes[1]*9*9+PFIndexes[2]*9+PFIndexes[3];
+
+      unsigned PFEntry = PerfectShuffleTable[PFTableIndex];
+      unsigned Cost  = (PFEntry >> 30);
+
+      // Determining when to avoid vperm is tricky.  Many things affect the cost
+      // of vperm, particularly how many times the perm mask needs to be computed.
+      // For example, if the perm mask can be hoisted out of a loop or is already
+      // used (perhaps because there are multiple permutes with the same shuffle
+      // mask?) the vperm has a cost of 1.  OTOH, hoisting the permute mask out of
+      // the loop requires an extra register.
+      //
+      // As a compromise, we only emit discrete instructions if the shuffle can be
+      // generated in 3 or fewer operations.  When we have loop information
+      // available, if this block is within a loop, we should avoid using vperm
+      // for 3-operation perms and use a constant pool load instead.
+      if (Cost < 3)
+        return GeneratePerfectShuffle(PFEntry, V1, V2, DAG, dl);
     }
-    PFIndexes[i] = EltNo;
-  }
-
-  // If this shuffle can be expressed as a shuffle of 4-byte elements, use the
-  // perfect shuffle vector to determine if it is cost effective to do this as
-  // discrete instructions, or whether we should use a vperm.
-  // For now, we skip this for little endian until such time as we have a
-  // little-endian perfect shuffle table.
-  if (isFourElementShuffle && !isLittleEndian) {
-    // Compute the index in the perfect shuffle table.
-    unsigned PFTableIndex =
-      PFIndexes[0]*9*9*9+PFIndexes[1]*9*9+PFIndexes[2]*9+PFIndexes[3];
-
-    unsigned PFEntry = PerfectShuffleTable[PFTableIndex];
-    unsigned Cost  = (PFEntry >> 30);
-
-    // Determining when to avoid vperm is tricky.  Many things affect the cost
-    // of vperm, particularly how many times the perm mask needs to be computed.
-    // For example, if the perm mask can be hoisted out of a loop or is already
-    // used (perhaps because there are multiple permutes with the same shuffle
-    // mask?) the vperm has a cost of 1.  OTOH, hoisting the permute mask out of
-    // the loop requires an extra register.
-    //
-    // As a compromise, we only emit discrete instructions if the shuffle can be
-    // generated in 3 or fewer operations.  When we have loop information
-    // available, if this block is within a loop, we should avoid using vperm
-    // for 3-operation perms and use a constant pool load instead.
-    if (Cost < 3)
-      return GeneratePerfectShuffle(PFEntry, V1, V2, DAG, dl);
   }
 
+  if (--MaskMap[PermMask].first == 0)
+    MaskMap.erase(PermMask);
+
   // Lower this to a VPERM(V1, V2, V3) expression, where V3 is a constant
   // vector that will get spilled to the constant pool.
   if (V2.isUndef()) V2 = V1;
 
   // The SHUFFLE_VECTOR mask is almost exactly what we want for vperm, except
   // that it is in input element units, not in bytes.  Convert now.
 
   // For little endian, the order of the input vectors is reversed, and

llvm/test/CodeGen/PowerPC/perfect-shuffle.ll

; LE-NEXT:    blr
   %shuf = shufflevector <16 x i8> %v1, <16 x i8> %v2, <16 x i32> <i32 4, i32 5, i32 6, i32 7, i32 12, i32 13, i32 14, i32 15, i32 20, i32 21, i32 22, i32 23, i32 28, i32 29, i32 30, i32 31>
   %cast = bitcast <16 x i8> %shuf to <4 x float>
   ret <4 x float> %cast
 }
 
 define <4 x float> @shuffle3(<16 x i8> %v1, <16 x i8> %v2, <16 x i8> %v3, <16 x i8> %v4) {
 ; BE-LABEL: shuffle3:
 ; BE:       # %bb.0:
-; BE-NEXT:    vmrglw 0, 2, 3
-; BE-NEXT:    vmrghw 2, 2, 3
-; BE-NEXT:    vmrglw 3, 4, 5
-; BE-NEXT:    vmrghw 4, 4, 5
-; BE-NEXT:    vmrghw 2, 2, 0
-; BE-NEXT:    vmrghw 3, 4, 3
+; BE-NEXT:    addis 3, 2, .LCPI2_0@toc@ha
+; BE-NEXT:    addi 3, 3, .LCPI2_0@toc@l
+; BE-NEXT:    lxv 32, 0(3)
+; BE-NEXT:    vperm 2, 2, 3, 0
+; BE-NEXT:    vperm 3, 4, 5, 0
 ; BE-NEXT:    xvaddsp 34, 34, 35
 ; BE-NEXT:    blr
 ;
 ; LE-LABEL: shuffle3:
 ; LE:       # %bb.0:
 ; LE-NEXT:    vpkudum 2, 3, 2
 ; LE-NEXT:    vpkudum 3, 5, 4
 ; LE-NEXT:    xvaddsp 34, 34, 35