[X86] Support ANDNP combine through vector_shuffle

[e-kud]

Summary

Combine

and (vector_shuffle<Z,...,Z>
         (insert_vector_elt undef, (xor X, -1), Z), undef), Y
->
andnp (vector_shuffle<Z,...,Z>
           (insert_vector_elt undef, X, Z), undef), Y

[e-kud]

Guard bitcasts and pshufd with single use

[pengfei]

llvm/test/CodeGen/X86/combine-bitselect.ll

568 ↗

(On Diff #477323)

The name seems a bit confusing. It is not just a v4i32 version of bitselect_v4i64_broadcast_rrr. Better give a meaningful name. Besides, why don't use i64 type like others? And it's better to pre-commit the test to just show the diff in this patch.

[RKSimon]

llvm/test/CodeGen/X86/combine-bitselect.ll

615 ↗

(On Diff #477323)

This test would probably be better inside combine-and.ll - I've improved test coverage in rG6f11c395f5899a10cbcc823cfd6ef7b08525a17e

[e-kud]

llvm/test/CodeGen/X86/combine-bitselect.ll

615 ↗

(On Diff #477323)

Yes, thank you! I'll move the test to combine-and.ll. I'd like to check with both AVX512 (broadcast) and SSE (pshufd). So I'm going to add another RUN with AVX512F prefix. Should I rename existing CHECK to something like SSE42 or leave it as is?

[e-kud]

Address to comments and put tests into https://reviews.llvm.org/D138734

[e-kud]

Add peeking through bitcasts for BROADCAST as well.

[e-kud]

Rebased on precommit tests

[pengfei]

LGTM.

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

48173

Did you look at matching a generic ShuffleSDNode with a broadcast mask instead of PSHUFD?

[e-kud]

Propose more generic approach using vector_shuffle

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

48201

(style) Missing assert message

48205

256-bit vectors should be OK on AVX1 - but OK to just add a TODO if there's no current test coverage.

48212

(style) Use early-out instead of nested ifs (and move oneuse to the end as its the most expensive call)

if (!SVN || !SVN->isSplat() || !SVN->getOperand(1).isUndef() || !SVN->hasOneUse())
  return SDValue();

48237

(style) Missing assert message

[RKSimon]

Do we have any 256/512 bit test coverage?

[e-kud]

In D138521#3974292, @RKSimon wrote:

Do we have any 256/512 bit test coverage?

Unfortunately, no. I only tested locally with 256 bits.

I found out that the generic approach has a problem. If we have a 256 or 512 bit vector, then we can't generate ANDNP with SSE because there is no type for 256 bits. But after type-legalizer we have several ISD::AND that can be combined into ANDNP.
It works with BROADCAST/PSHUFD approach but performing the generic-combine before type-legalization prevents it.

I think about and (shuffle(not)) -> and(not(shuffle)) reordering before type-legalization and then after legalization we combine them into ANDNP. However I'm not sure about such two-step combine. What do you think?

[RKSimon]

SplitOpsAndApply might be able to help here

[e-kud]

Added vector splitting

[RKSimon]

LGTM with one minor comment - cheers

llvm/lib/Target/X86/X86ISelLowering.cpp

48209

You might need to bitcast this back to Src.getValueType() - its less likely for scalars but IsNOT can peek through bitcasts

[e-kud]

Rebased and added a bitcast of IsNOT.

[e-kud]

llvm/lib/Target/X86/X86ISelLowering.cpp

48209

Indeed, I added a test where a result of xor is bitcasted and got a failed assertion. Thank you!

[e-kud]

Rebased.

[RKSimon]

LGTM

llvm/lib/Target/X86/X86ISelLowering.cpp

 }
 
 // Match (xor X, -1) -> X.
 // Match extract_subvector(xor X, -1) -> extract_subvector(X).
 // Match concat_vectors(xor X, -1, xor Y, -1) -> concat_vectors(X, Y).
 static SDValue IsNOT(SDValue V, SelectionDAG &DAG) {
   V = peekThroughBitcasts(V);
   if (V.getOpcode() == ISD::XOR &&
-      ISD::isBuildVectorAllOnes(V.getOperand(1).getNode()))
+      (ISD::isBuildVectorAllOnes(V.getOperand(1).getNode()) ||
+       isAllOnesConstant(V.getOperand(1))))
     return V.getOperand(0);
   if (V.getOpcode() == ISD::EXTRACT_SUBVECTOR &&
       (isNullConstant(V.getOperand(1)) || V.getOperand(0).hasOneUse())) {
     if (SDValue Not = IsNOT(V.getOperand(0), DAG)) {
       Not = DAG.getBitcast(V.getOperand(0).getValueType(), Not);
       return DAG.getNode(ISD::EXTRACT_SUBVECTOR, SDLoc(Not), V.getValueType(),
                          Not, V.getOperand(1));
     }
static SDValue combineAndNotIntoANDNP(SDNode *N, SelectionDAG &DAG) {
   auto GetNot = [&VT, &DAG](SDValue V) {
     // Basic X = NOT(Y) detection.
     if (SDValue Not = IsNOT(V, DAG))
       return Not;
     // Fold BROADCAST(NOT(Y)) -> BROADCAST(Y).
     if (V.getOpcode() == X86ISD::VBROADCAST) {
       SDValue Src = V.getOperand(0);
       EVT SrcVT = Src.getValueType();
-      if (!SrcVT.isVector())
+      if (!SrcVT.isVector() && !(Src.hasOneUse() && V.hasOneUse()))
         return SDValue();
       if (SDValue Not = IsNOT(Src, DAG))
         return DAG.getNode(X86ISD::VBROADCAST, SDLoc(V), VT,
                            DAG.getBitcast(SrcVT, Not));
     }
+    // Fold PSHUFD(SCALAR_TO_VECTOR(NOT(Y))) -> PSHUFD(SCALAR_TO_VECTOR(Y))
+    SDValue Shuffle = peekThroughOneUseBitcasts(V);
+    if (Shuffle.getOpcode() == X86ISD::PSHUFD && Shuffle.hasOneUse()) {
+      SDValue Src = Shuffle.getOperand(0);
+      SDValue S2V = peekThroughOneUseBitcasts(Src);
+      if (S2V.getOpcode() != ISD::SCALAR_TO_VECTOR || !S2V.hasOneUse())
+        return SDValue();
+      if (SDValue Not = IsNOT(S2V.getOperand(0), DAG)) {
+        SDValue NotS2V = DAG.getNode(ISD::SCALAR_TO_VECTOR, SDLoc(S2V),
+                                     S2V.getValueType(), Not);
+        SDValue NotSrc = DAG.getBitcast(Src.getValueType(), NotS2V);
+        return DAG.getNode(X86ISD::PSHUFD, SDLoc(Shuffle),
+                           Shuffle.getValueType(), NotSrc,
+                           Shuffle.getOperand(1));
+      }
+    }
     return SDValue();
   };
 
   if (SDValue Not = GetNot(N0)) {
     X = Not;
     Y = N1;
   } else if (SDValue Not = GetNot(N1)) {
     X = Not;

 // Try to widen AND, OR and XOR nodes to VT in order to remove casts around
 // logical operations, like in the example below.
 //   or (and (truncate x, truncate y)),
 //      (xor (truncate z, build_vector (constants)))
 // Given a target type \p VT, we generate
 //   or (and x, y), (xor z, zext(build_vector (constants)))
 // given x, y and z are of type \p VT. We can do so, if operands are either
 // truncates from VT types, the second operand is a vector of constants or can
 // be recursively promoted.
 static SDValue PromoteMaskArithmetic(SDNode *N, EVT VT, SelectionDAG &DAG,
                                      unsigned Depth) {
   // Limit recursion to avoid excessive compile times.
   if (Depth >= SelectionDAG::MaxRecursionDepth)
     return SDValue();
 
   if (N->getOpcode() != ISD::XOR && N->getOpcode() != ISD::AND &&
       N->getOpcode() != ISD::OR)
     return SDValue();
 
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDLoc DL(N);
 
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   if (!TLI.isOperationLegalOrPromote(N->getOpcode(), VT))
     return SDValue();
 
   if (SDValue NN0 = PromoteMaskArithmetic(N0.getNode(), VT, DAG, Depth + 1))
     N0 = NN0;
   else {
     // The Left side has to be a trunc.
     if (N0.getOpcode() != ISD::TRUNCATE)
       return SDValue();
 
     // The type of the truncated inputs.
     if (N0.getOperand(0).getValueType() != VT)
       return SDValue();
 
     N0 = N0.getOperand(0);
   }
 
   if (SDValue NN1 = PromoteMaskArithmetic(N1.getNode(), VT, DAG, Depth + 1))
     N1 = NN1;
   else {
     // The right side has to be a 'trunc' or a constant vector.
     bool RHSTrunc = N1.getOpcode() == ISD::TRUNCATE &&
                     N1.getOperand(0).getValueType() == VT;
     if (!RHSTrunc && !ISD::isBuildVectorOfConstantSDNodes(N1.getNode()))
       return SDValue();
 
     if (RHSTrunc)
       N1 = N1.getOperand(0);
     else