[SystemZ] Eliminate the need to create a zero vector by reusing the mask.

[jonpa]

Summary

Try to avoid creating VGBMs by reusing the permutation mask if it contains a zero. If the first byte was into (any byte of) a zero vector, then the first byte of the mask can become zero and reused by putting the mask also as the first operand. If there was a first-byte use of the other source operand, then that zero index can be reused if the mask is placed as the second operand. The first case will be important probably with the upcoming patch for zero_extend_vector_inreg, while the second case affects just a few cases on SPEC'17. The patch could of course be simplified if the second case was skipped...

There is also the case of Intrinsic::s390_vperm, but it seems more complicated to wait until DAGCombine to handle this, since then we have to extract the mask back from a constant-pool or maybe even a SystemZVectorConstant... Besides, the user should be able to do that on his own also, right?

This doesn't seem to have that big of an effect on SPEC'17:

vperm          :                21136                21110      -26
vgbm           :                11385                11368      -17
vl             :               109414               109411       -3
larl           :               371345               371347       +2

...

, but it probably becomes more noticeable with the zero_extend_vector_inreg patch... Should it be committed separately first, or rather incorporated into that other patch?

It seems that now MachineCSE can remove a few VPERMs also. At least one case was because instead of using an undef source operand, the mask was used (it doesn't help any to replace an undef Ops[1] with Op2 on the last line of getGeneralPermuteNode(), which I first thought). The test case I have reduced (not included) shows that MCSE on trunk fails to remove the second vperm if even though the instructions are near identical. The only difference to the success with this patch is that instead of the reused mask, there is an IMPLICIT_DEF. It looks to me that this is a minor deficiency of MCSE (Two different vregs defined by IMPLICIT_DEF should not stop CSE, I would think).

isZeroOrUndefVector(): The check for the undef vector used to be beneficial for the zero_extend_vector_inreg patch, but the way it looks now (just using a single unpack), it is not needed for anymore (NFC). I think it could be removed or we can keep it here to get the few less vperms...

Two tests - one for each case handled. Not quite sure what happened with vector-constrained-fp-intrinsics.ll - I don't understand why v0 is no longer used, but it seems that this patch begins to change things when the second operand of the VPERM is undefined.

[uweigand]

It seems that now MachineCSE can remove a few VPERMs also. At least one case was because instead of using an undef source operand, the mask was used (it doesn't help any to replace an undef Ops[1] with Op2 on the last line of getGeneralPermuteNode(), which I first thought). The test case I have reduced (not included) shows that MCSE on trunk fails to remove the second vperm if even though the instructions are near identical. The only difference to the success with this patch is that instead of the reused mask, there is an IMPLICIT_DEF. It looks to me that this is a minor deficiency of MCSE (Two different vregs defined by IMPLICIT_DEF should not stop CSE, I would think).

isZeroOrUndefVector(): The check for the undef vector used to be beneficial for the zero_extend_vector_inreg patch, but the way it looks now (just using a single unpack), it is not needed for anymore (NFC). I think it could be removed or we can keep it here to get the few less vperms...

Two tests - one for each case handled. Not quite sure what happened with vector-constrained-fp-intrinsics.ll - I don't understand why v0 is no longer used, but it seems that this patch begins to change things when the second operand of the VPERM is undefined.

It seems to me these are related. Currently, for a VPERM that only needs a single input, the second input is set to UNDEF, which gets lowered to an IMPLICIT_DEF at the MI level, which the register allocator just replaced by some (random?) register. In the test case, it chooses %v0, which has nothing to do with the VPERM, and is in fact already used for an unrelated operation. This is not really a good idea, because that creates a register dependency on the instruction that is really unnecessary ...

I think for VPERMs that only need a single input, we should simply use the same register for both input slots. That way, the contents are well-defined, and there are no spurious dependencies. Also, it should fix the CSE problem, I think. (Using the other input seems preferable to using the index vector ...)

If we do that, it follows that a completely undefined input should *not* be treated as a zero vector for this optimization. (However, a not fully undefined vector that is a mixture of zero elements and undefined elements can be treated as zero vector. Not sure if this makes much of a difference in practice.)

Note that fixing the handling of an UNDEF second input can (and probably should) be done as a separate patch, before this optimization is merged.

[jonpa]

Note that fixing the handling of an UNDEF second input can (and probably should) be done as a separate patch, before this optimization is merged.

Committed as 31ecef7.

If we do that, it follows that a completely undefined input should *not* be treated as a zero vector for this optimization. (However, a not fully undefined vector that is a mixture of zero elements and undefined elements can be treated as zero vector. Not sure if this makes much of a difference in practice.)

Removed the check for the undef vector. It also turns out that ISD::isBuildVectorAllZeros() is already accepting some undef elements, as long as they are not all undef, which is exactly what we want.

Patch rebased. The second case (reusing the index into the first byte of the non-zero vector), is eliminating now 13 VGBM.s on SPEC'17, but is not needed for the zero extend inreg patch...

Tests merged into vec-perm-14.ll, which was just committed...

[uweigand]

LGTM, thanks!

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;
 }
 
+static bool isZeroVector(SDValue N) {
+  if (N->getOpcode() == ISD::SPLAT_VECTOR)
+    if (auto *Op = dyn_cast<ConstantSDNode>(N->getOperand(0)))
+      return Op->getZExtValue() == 0;
+  return ISD::isBuildVectorAllZeros(N.getNode());
+}
+
 // 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]);
 
   // First see whether VSLDB can be used.
   unsigned StartIndex, OpNo0, OpNo1;
   if (isShlDoublePermute(Bytes, StartIndex, OpNo0, OpNo1))
     return DAG.getNode(SystemZISD::SHL_DOUBLE, DL, MVT::v16i8, Ops[OpNo0],
                        Ops[OpNo1],
                        DAG.getTargetConstant(StartIndex, DL, MVT::i32));
 
-  // Fall back on VPERM.  Construct an SDNode for the permute vector.
+  // Fall back on VPERM.  Construct an SDNode for the permute vector.  Try to
+  // eliminate a zero vector by reusing any zero index in the permute vector.
+  unsigned ZeroVecIdx =
+    isZeroVector(Ops[0]) ? 0 : (isZeroVector(Ops[1]) ? 1 : UINT_MAX);
+  if (ZeroVecIdx != UINT_MAX) {
+    bool MaskFirst = true;
+    int ZeroIdx = -1;
+    for (unsigned I = 0; I < SystemZ::VectorBytes; ++I) {
+      unsigned OpNo = unsigned(Bytes[I]) / SystemZ::VectorBytes;
+      unsigned Byte = unsigned(Bytes[I]) % SystemZ::VectorBytes;
+      if (OpNo == ZeroVecIdx && I == 0) {
+        // If the first byte is zero, use mask as first operand.
+        ZeroIdx = 0;
+        break;
+      }
+      if (OpNo != ZeroVecIdx && Byte == 0) {
+        // If mask contains a zero, use it by placing that vector first.
+        ZeroIdx = I + SystemZ::VectorBytes;
+        MaskFirst = false;
+        break;
+      }
+    }
+    if (ZeroIdx != -1) {
+      SDValue IndexNodes[SystemZ::VectorBytes];
+      for (unsigned I = 0; I < SystemZ::VectorBytes; ++I) {
+        if (Bytes[I] >= 0) {
+          unsigned OpNo = unsigned(Bytes[I]) / SystemZ::VectorBytes;
+          unsigned Byte = unsigned(Bytes[I]) % SystemZ::VectorBytes;
+          if (OpNo == ZeroVecIdx)
+            IndexNodes[I] = DAG.getConstant(ZeroIdx, DL, MVT::i32);
+          else {
+            unsigned BIdx = MaskFirst ? Byte + SystemZ::VectorBytes : Byte;
+            IndexNodes[I] = DAG.getConstant(BIdx, DL, MVT::i32);
+          }
+        } else
+          IndexNodes[I] = DAG.getUNDEF(MVT::i32);
+      }
+      SDValue Mask = DAG.getBuildVector(MVT::v16i8, DL, IndexNodes);
+      SDValue Src = ZeroVecIdx == 0 ? Ops[1] : Ops[0];
+      if (MaskFirst)
+        return DAG.getNode(SystemZISD::PERMUTE, DL, MVT::v16i8, Mask, Src,
+                           Mask);
+      else
+        return DAG.getNode(SystemZISD::PERMUTE, DL, MVT::v16i8, Src, Mask,
+                           Mask);
+    }
+  }
+
   SDValue IndexNodes[SystemZ::VectorBytes];
   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],

llvm/test/CodeGen/SystemZ/vec-perm-14.ll

 ; RUN: llc < %s -mtriple=s390x-linux-gnu -mcpu=z14 | FileCheck %s
 ;
 ; Test that only one vperm of the vector compare is needed for both extracts.
 
 define void @fun() {
-; CHECK-LABEL: fun
+; CHECK-LABEL: fun:
 ; CHECK: vperm
 ; CHECK-NOT: vperm
 bb:
   %tmp = load <4 x i8>, <4 x i8>* undef
   %tmp1 = icmp eq <4 x i8> zeroinitializer, %tmp
   %tmp2 = extractelement <4 x i1> %tmp1, i32 0
   br i1 %tmp2, label %bb1, label %bb2
 
 bb1:
   unreachable
 
 bb2:
   %tmp3 = extractelement <4 x i1> %tmp1, i32 1
   br i1 %tmp3, label %bb3, label %bb4
 
 bb3:
   unreachable
 
 bb4:
   unreachable
 }
+
+; Test that a zero index in the permute vector is used instead of VGBM, with
+; a zero index into the other source operand.
+define <4 x i8> @fun1(<2 x i8> %arg) {
+; CHECK-LABEL:.LCPI1_0:
+; CHECK-NEXT:        .byte   1                       # 0x1
+; CHECK-NEXT:        .byte   18                      # 0x12
+; CHECK-NEXT:        .byte   0                       # 0x0
+; CHECK-NEXT:        .byte   18                      # 0x12
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .text
+; CHECK-NEXT:        .globl  fun1
+; CHECK-NEXT:        .p2align        4
+; CHECK-NEXT:        .type   fun1,@function
+; CHECK-NEXT: fun1:                                  # @fun1
+; CHECK-NEXT:        .cfi_startproc
+; CHECK-NEXT: # %bb.0:
+; CHECK-NEXT:        larl    %r1, .LCPI1_0
+; CHECK-NEXT:        vl      %v0, 0(%r1), 3
+; CHECK-NEXT:        vperm   %v24, %v24, %v0, %v0
+; CHECK-NEXT:        br      %r14
+   %res = shufflevector <2 x i8> %arg, <2 x i8> zeroinitializer,
+                        <4 x i32> <i32 1, i32 2, i32 0, i32 3>
+   ret <4 x i8> %res
+}
+
+; Same, but with the first byte indexing into an element of the zero vector.
+define <4 x i8> @fun2(<2 x i8> %arg) {
+; CHECK-LABEL:.LCPI2_0:
+; CHECK-NEXT:        .byte   0                       # 0x0
+; CHECK-NEXT:        .byte   17                      # 0x11
+; CHECK-NEXT:        .byte   17                      # 0x11
+; CHECK-NEXT:        .byte   0                       # 0x0
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .space  1
+; CHECK-NEXT:        .text
+; CHECK-NEXT:        .globl  fun2
+; CHECK-NEXT:        .p2align        4
+; CHECK-NEXT:        .type   fun2,@function
+; CHECK-NEXT:fun2:                                   # @fun2
+; CHECK-NEXT:        .cfi_startproc
+; CHECK-NEXT:# %bb.0:
+; CHECK-NEXT:        larl    %r1, .LCPI2_0
+; CHECK-NEXT:        vl      %v0, 0(%r1), 3
+; CHECK-NEXT:        vperm   %v24, %v0, %v24, %v0
+; CHECK-NEXT:        br      %r14
+   %res = shufflevector <2 x i8> %arg, <2 x i8> zeroinitializer,
+                        <4 x i32> <i32 3, i32 1, i32 1, i32 2>
+   ret <4 x i8> %res
+}