[X86] Handle inverted inputs when matching VPTERNLOG from 2 binary ops.

[craig.topper]

Summary

This is a more general version of D109273. Though it doesn't
peek through bitcasts or rearange broadcasts.

[RKSimon]

LGTM but @pengfei might have seen some other cases that D109273 would address.

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

4052

Missing assert messages

llvm/test/CodeGen/X86/avx512vl-logic.ll

989

Please can you precommit this?

[LuoYuanke]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

4232

It seems for VPTERNLOG instruction we can accept the 4th operand whose value is allZero or allOne no matter what is logic operation is.

4234

Is the constant operand canonicalized as operand(1)?

4246

C.getOperand(0)?

[LuoYuanke]

llvm/test/CodeGen/X86/avx512vl-logic.ll

985

Miss the test case for ~B and ~C?

[pengfei]

In D109295#2984246, @RKSimon wrote:

LGTM but @pengfei might have seen some other cases that D109273 would address.

The general approach looks great. I don't have other cases. Thanks Craig.

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

4232

Do you mean the FALSE and TRUE in table 5-10 and 5-11? I think we don't need a VPTERNLOG to generate allZero and allOne.

4234

We checked it in line 4225.

[LuoYuanke]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

4232

VPTERNLOG select all the possible result of 3 bits. I mean it can be extent to 4 bit as long as the 4th bit is compile-time fixed 0 or 1. For this case the node is xor (X, -1), the same approach can be applied to xor(X, 0), and(X, -1), andnp(X, 0) and so on.

[pengfei]

I found another example:

define dso_local <4 x i64> @foo2(<4 x i64> %0, <4 x i64> %1, <4 x i64> %2) {
  %4 = xor <4 x i64> %2, <i64 -1, i64 -1, i64 -1, i64 -1>
  %5 = or <4 x i64> %4, %1
  %6 = or <4 x i64> %0, %1
  %7 = and <4 x i64> %5, %6
  ret <4 x i64> %7
}

Can we simply it to below in the approach?

vpor    %ymm1, %ymm0, %ymm0
vpternlogq      $208, %ymm2, %ymm1, %ymm0
retq

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

4232

But other cases can be simplied directly, e.g. xor(X, 0) -> X, and(X, -1) -> X, andnp(X, 0) -> 0 etc.

[LuoYuanke]

In D109295#2985246, @pengfei wrote:

I found another example:

define dso_local <4 x i64> @foo2(<4 x i64> %0, <4 x i64> %1, <4 x i64> %2) {
  %4 = xor <4 x i64> %2, <i64 -1, i64 -1, i64 -1, i64 -1>
  %5 = or <4 x i64> %4, %1
  %6 = or <4 x i64> %0, %1
  %7 = and <4 x i64> %5, %6
  ret <4 x i64> %7
}

Can we simply it to below in the approach?

vpor    %ymm1, %ymm0, %ymm0
vpternlogq      $208, %ymm2, %ymm1, %ymm0
retq

Seem no with current vpternlog framework. We currently only support A op1 (B op2 C). Not figured out how to extend the framework to accept more operators as long as there is 3 source bit.

[LuoYuanke]

In D109295#2985347, @LuoYuanke wrote:

In D109295#2985246, @pengfei wrote:

I found another example:

define dso_local <4 x i64> @foo2(<4 x i64> %0, <4 x i64> %1, <4 x i64> %2) {
  %4 = xor <4 x i64> %2, <i64 -1, i64 -1, i64 -1, i64 -1>
  %5 = or <4 x i64> %4, %1
  %6 = or <4 x i64> %0, %1
  %7 = and <4 x i64> %5, %6
  ret <4 x i64> %7
}

Can we simply it to below in the approach?

vpor    %ymm1, %ymm0, %ymm0
vpternlogq      $208, %ymm2, %ymm1, %ymm0
retq

How about gcc? Can gcc generate one vpternlogq instruction?

[pengfei]

In D109295#2985347, @LuoYuanke wrote:

In D109295#2985246, @pengfei wrote:

I found another example:

define dso_local <4 x i64> @foo2(<4 x i64> %0, <4 x i64> %1, <4 x i64> %2) {
  %4 = xor <4 x i64> %2, <i64 -1, i64 -1, i64 -1, i64 -1>
  %5 = or <4 x i64> %4, %1
  %6 = or <4 x i64> %0, %1
  %7 = and <4 x i64> %5, %6
  ret <4 x i64> %7
}

Can we simply it to below in the approach?

vpor    %ymm1, %ymm0, %ymm0
vpternlogq      $208, %ymm2, %ymm1, %ymm0
retq

Seem no with current vpternlog framework. We currently only support A op1 (B op2 C). Not figured out how to extend the framework to accept more operators as long as there is 3 source bit.

I meant simplified from current generation:

vpcmpeqd        %ymm3, %ymm3, %ymm3
vpternlogq      $222, %ymm2, %ymm1, %ymm3
vpternlogq      $200, %ymm1, %ymm3, %ymm0
retq

We can save one vpternlogq.

[LuoYuanke]

I meant simplified from current generation:

vpcmpeqd        %ymm3, %ymm3, %ymm3
vpternlogq      $222, %ymm2, %ymm1, %ymm3
vpternlogq      $200, %ymm1, %ymm3, %ymm0
retq

We can save one vpternlogq.

I think we may have another algorithm which iterate 8 possible composition of 3 bits and calculate the result with multi-operates and get the immediate operand of VPTERNLOGD.

VPTERNLOGD reg1, reg2, src3
Bit(reg1) Bit(reg2) Bit(src3)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

[craig.topper]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

4232

Right those all should have been simplified by DAGCombine.

4234

DAGCombine should canonicalize XOR with constant to have it on the RHS.

[craig.topper]

Address review comments. Rebase after pre-committing tests.

[craig.topper]

Rename IsNot lambda to PeekThroughNot and sync more code into it.

[xbolva00]

Also some more cases for ternlog

__m512i notBorC(__m512i B, __m512i C) {
    return ~(B|C); // 0x11 
}

__m512i notBandC(__m512i B, __m512i C) {
    return ~(B&C); // 0x77
}

__m512i notBxorC(__m512i B, __m512i C) {
    return ~(B^C); // 0x99
}

[craig.topper]

In D109295#2985534, @xbolva00 wrote:

Also some more cases for ternlog

__m512i notBorC(__m512i B, __m512i C) {
    return ~(B|C); // 0x11 
}

__m512i notBandC(__m512i B, __m512i C) {
    return ~(B&C); // 0x77
}

__m512i notBxorC(__m512i B, __m512i C) {
    return ~(B^C); // 0x99
}

We should be a little careful there. As far as I know, vpternlog doesn't break dependencies on inputs that aren't used by the immediate. So we should try to use one of the other registers twice to prevent false dependencies. If we can fold a load, we need to make sure we don't duplicate that register and prevent the folding.

[LuoYuanke]

LGTM, thanks.

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

 //===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
private:
     bool foldLoadStoreIntoMemOperand(SDNode *Node);
     MachineSDNode *matchBEXTRFromAndImm(SDNode *Node);
     bool matchBitExtract(SDNode *Node);
     bool shrinkAndImmediate(SDNode *N);
     bool isMaskZeroExtended(SDNode *N) const;
     bool tryShiftAmountMod(SDNode *N);
     bool tryShrinkShlLogicImm(SDNode *N);
     bool tryVPTERNLOG(SDNode *N);
-    bool matchVPTERNLOG(SDNode *Root, SDNode *ParentA, SDNode *ParentBC,
-                        SDValue A, SDValue B, SDValue C, uint8_t Imm);
+    bool matchVPTERNLOG(SDNode *Root, SDNode *ParentA, SDNode *ParentB,
+                        SDNode *ParentC, SDValue A, SDValue B, SDValue C,
+                        uint8_t Imm);
     bool tryVPTESTM(SDNode *Root, SDValue Setcc, SDValue Mask);
     bool tryMatchBitSelect(SDNode *N);
 
     MachineSDNode *emitPCMPISTR(unsigned ROpc, unsigned MOpc, bool MayFoldLoad,
                                 const SDLoc &dl, MVT VT, SDNode *Node);
     MachineSDNode *emitPCMPESTR(unsigned ROpc, unsigned MOpc, bool MayFoldLoad,
                                 const SDLoc &dl, MVT VT, SDNode *Node,
                                 SDValue &InFlag);
bool X86DAGToDAGISel::tryShrinkShlLogicImm(SDNode *N) {
   SDValue NewSHL = CurDAG->getNode(ISD::SHL, dl, NVT, NewBinOp,
                                    Shift.getOperand(1));
   ReplaceNode(N, NewSHL.getNode());
   SelectCode(NewSHL.getNode());
   return true;
 }
 
 bool X86DAGToDAGISel::matchVPTERNLOG(SDNode *Root, SDNode *ParentA,
-                                     SDNode *ParentBC, SDValue A, SDValue B,
-                                     SDValue C, uint8_t Imm) {
+                                     SDNode *ParentB, SDNode *ParentC,
+                                     SDValue A, SDValue B, SDValue C,
+                                     uint8_t Imm) {
   assert(A.isOperandOf(ParentA));
-  assert(B.isOperandOf(ParentBC));
-  assert(C.isOperandOf(ParentBC));
+  assert(B.isOperandOf(ParentB));
+  assert(C.isOperandOf(ParentC));
 
   auto tryFoldLoadOrBCast =
       [this](SDNode *Root, SDNode *P, SDValue &L, SDValue &Base, SDValue &Scale,
              SDValue &Index, SDValue &Disp, SDValue &Segment) {
         if (tryFoldLoad(Root, P, L, Base, Scale, Index, Disp, Segment))
           return true;
 
         // Not a load, check for broadcast which may be behind a bitcast.
auto tryFoldLoadOrBCast =
         if (Size != 32 && Size != 64)
           return false;
 
         return tryFoldBroadcast(Root, P, L, Base, Scale, Index, Disp, Segment);
       };
 
   bool FoldedLoad = false;
   SDValue Tmp0, Tmp1, Tmp2, Tmp3, Tmp4;
-  if (tryFoldLoadOrBCast(Root, ParentBC, C, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) {
+  if (tryFoldLoadOrBCast(Root, ParentC, C, Tmp0, Tmp1, Tmp2, Tmp3, Tmp4)) {
     FoldedLoad = true;
   } else if (tryFoldLoadOrBCast(Root, ParentA, A, Tmp0, Tmp1, Tmp2, Tmp3,
                                 Tmp4)) {
     FoldedLoad = true;
     std::swap(A, C);
     // Swap bits 1/4 and 3/6.
     uint8_t OldImm = Imm;
     Imm = OldImm & 0xa5;
     if (OldImm & 0x02) Imm |= 0x10;
     if (OldImm & 0x10) Imm |= 0x02;
     if (OldImm & 0x08) Imm |= 0x40;
     if (OldImm & 0x40) Imm |= 0x08;
-  } else if (tryFoldLoadOrBCast(Root, ParentBC, B, Tmp0, Tmp1, Tmp2, Tmp3,
+  } else if (tryFoldLoadOrBCast(Root, ParentB, B, Tmp0, Tmp1, Tmp2, Tmp3,
                                 Tmp4)) {
     FoldedLoad = true;
     std::swap(B, C);
     // Swap bits 1/2 and 5/6.
     uint8_t OldImm = Imm;
     Imm = OldImm & 0x99;
     if (OldImm & 0x02) Imm |= 0x04;
     if (OldImm & 0x04) Imm |= 0x02;
bool X86DAGToDAGISel::matchVPTERNLOG(SDNode *Root, SDNode *ParentA,
   }
 
   ReplaceUses(SDValue(Root, 0), SDValue(MNode, 0));
   CurDAG->RemoveDeadNode(Root);
   return true;
 }
 
 // Try to match two logic ops to a VPTERNLOG.
-// FIXME: Handle inverted inputs?
 // FIXME: Handle more complex patterns that use an operand more than once?
 bool X86DAGToDAGISel::tryVPTERNLOG(SDNode *N) {
   MVT NVT = N->getSimpleValueType(0);
 
   // Make sure we support VPTERNLOG.
   if (!NVT.isVector() || !Subtarget->hasAVX512() ||
       NVT.getVectorElementType() == MVT::i1)
     return false;
if ((FoldableOp = getFoldableLogicOp(N1))) {
     A = N0;
   } else if ((FoldableOp = getFoldableLogicOp(N0))) {
     A = N1;
   } else
     return false;
 
   SDValue B = FoldableOp.getOperand(0);
   SDValue C = FoldableOp.getOperand(1);
+  SDNode *ParentA = N;
+  SDNode *ParentB = FoldableOp.getNode();
+  SDNode *ParentC = FoldableOp.getNode();
 
   // We can build the appropriate control immediate by performing the logic
   // operation we're matching using these constants for A, B, and C.
-  const uint8_t TernlogMagicA = 0xf0;
-  const uint8_t TernlogMagicB = 0xcc;
-  const uint8_t TernlogMagicC = 0xaa;
+  uint8_t TernlogMagicA = 0xf0;
+  uint8_t TernlogMagicB = 0xcc;
+  uint8_t TernlogMagicC = 0xaa;
+
+  auto IsNot = [](SDValue Op) {
+    return Op.getOpcode() == ISD::XOR && Op.hasOneUse() &&
+      ISD::isBuildVectorAllOnes(Op.getOperand(1).getNode());
+  };
+
+  // Some of the inputs may be inverted, peek through them and invert the
+  // magic values accordingly.
+  // TODO: There may be a bitcast before the xor that we should peek through.
+  if (IsNot(A)) {
+    TernlogMagicA = ~TernlogMagicA;
+    ParentA = A.getNode();
+    A = A.getOperand(0);
+  }
+
+  if (IsNot(B)) {
+    TernlogMagicB = ~TernlogMagicB;
+    ParentB = B.getNode();
+    B = B.getOperand(0);
+  }
+
+  if (IsNot(C)) {
+    TernlogMagicC = ~TernlogMagicC;
+    ParentC = C.getNode();
+    C = B.getOperand(0);
+  }
 
   uint8_t Imm;
   switch (FoldableOp.getOpcode()) {
   default: llvm_unreachable("Unexpected opcode!");
   case ISD::AND:      Imm = TernlogMagicB & TernlogMagicC; break;
   case ISD::OR:       Imm = TernlogMagicB | TernlogMagicC; break;
   case ISD::XOR:      Imm = TernlogMagicB ^ TernlogMagicC; break;
   case X86ISD::ANDNP: Imm = ~(TernlogMagicB) & TernlogMagicC; break;
   }
 
   switch (N->getOpcode()) {
   default: llvm_unreachable("Unexpected opcode!");
   case X86ISD::ANDNP:
     if (A == N0)
       Imm &= ~TernlogMagicA;
     else
       Imm = ~(Imm) & TernlogMagicA;
     break;
   case ISD::AND: Imm &= TernlogMagicA; break;
   case ISD::OR:  Imm |= TernlogMagicA; break;
   case ISD::XOR: Imm ^= TernlogMagicA; break;
   }
 
-  return matchVPTERNLOG(N, N, FoldableOp.getNode(), A, B, C, Imm);
+  return matchVPTERNLOG(N, ParentA, ParentB, ParentC, A, B, C, Imm);
 }
 
 /// If the high bits of an 'and' operand are known zero, try setting the
 /// high bits of an 'and' constant operand to produce a smaller encoding by
 /// creating a small, sign-extended negative immediate rather than a large
 /// positive one. This reverses a transform in SimplifyDemandedBits that
 /// shrinks mask constants by clearing bits. There is also a possibility that
 /// the 'and' mask can be made -1, so the 'and' itself is unnecessary. In that
else
     return false;
 
   SDLoc dl(N);
   SDValue Imm = CurDAG->getTargetConstant(0xCA, dl, MVT::i8);
   SDValue Ternlog = CurDAG->getNode(X86ISD::VPTERNLOG, dl, NVT, A, B, C, Imm);
   ReplaceNode(N, Ternlog.getNode());
 
   return matchVPTERNLOG(Ternlog.getNode(), Ternlog.getNode(), Ternlog.getNode(),
-                        A, B, C, 0xCA);
+                        Ternlog.getNode(), A, B, C, 0xCA);
 }
 
 void X86DAGToDAGISel::Select(SDNode *Node) {
   MVT NVT = Node->getSimpleValueType(0);
   unsigned Opcode = Node->getOpcode();
   SDLoc dl(Node);
 
   if (Node->isMachineOpcode()) {
void X86DAGToDAGISel::Select(SDNode *Node) {
   case ISD::SRA:
   case ISD::SHL:
     if (tryShiftAmountMod(Node))
       return;
     break;
 
   case X86ISD::VPTERNLOG: {
     uint8_t Imm = cast<ConstantSDNode>(Node->getOperand(3))->getZExtValue();
-    if (matchVPTERNLOG(Node, Node, Node, Node->getOperand(0),
+    if (matchVPTERNLOG(Node, Node, Node, Node, Node->getOperand(0),
                        Node->getOperand(1), Node->getOperand(2), Imm))
       return;
     break;
   }
 
   case X86ISD::ANDNP:
     if (tryVPTERNLOG(Node))
       return;

llvm/test/CodeGen/X86/avx512vl-logic.ll

 ; CHECK-NEXT:    vpternlogd $206, %xmm1, %xmm2, %xmm0
 ; CHECK-NEXT:    retq
   %a = xor <4 x i32> %x, <i32 -1, i32 -1, i32 -1, i32 -1>
   %b = and <4 x i32> %y, %a
   %c = or <4 x i32> %b, %z
   ret <4 x i32> %c
 }
 
+define <4 x i32> @ternlog_and_orn(<4 x i32> %x, <4 x i32> %y, <4 x i32> %z) {
+; CHECK-LABEL: ternlog_and_orn:
+; CHECK:       ## %bb.0:
+; CHECK-NEXT:    vpternlogd $176, %xmm1, %xmm2, %xmm0
+; CHECK-NEXT:    retq
+  %a = xor <4 x i32> %z, <i32 -1, i32 -1, i32 -1, i32 -1>
+  %b = or <4 x i32> %a, %y
+  %c = and <4 x i32> %b, %x
+  ret <4 x i32> %c
+}
+
 define <4 x i32> @ternlog_xor_andn(<4 x i32> %x, <4 x i32> %y, <4 x i32> %z) {
 ; CHECK-LABEL: ternlog_xor_andn:
 ; CHECK:       ## %bb.0:
 ; CHECK-NEXT:    vpternlogd $198, %xmm1, %xmm2, %xmm0
 ; CHECK-NEXT:    retq
   %a = xor <4 x i32> %x, <i32 -1, i32 -1, i32 -1, i32 -1>
   %b = and <4 x i32> %y, %a
   %c = xor <4 x i32> %b, %z