[AArch64][DAGCombiner] fold instruction BIC from ISD::AND

[bcl5980]

Summary

This patch add a new target ISD AArch64ISD::SBIC to represent scalar version instruction bic.
And select the ISD in the stage combine from this pattern:
(~X | C) & Y --> bic Y, (X & ~C)

[bcl5980]

add shiftreg selection for bic

[bcl5980]

improve code in td file

[bcl5980]

Ping.

[mingmingl]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

16046

An alternative is and Y, (orn C, X).

https://godbolt.org/z/PGnTdTMKW shows orn is generated if RHS of or is not a constant or RHS is a large constant, but orn not generated for small constant.

https://gist.github.com/minglotus-6/dd2c75a2253b128081125a578e7ff6c6 is the llc ISel debug output for small constant, and https://gist.github.com/minglotus-6/2692d59e5c939941895d3581a4bdcbea for large constant.

I wonder if fixing ISel (after dag-combiner) is a more general solution (i.e., selects ~X | C to orn, and fixes this motivating case as well).

16091

nit: add a comment like LHS won't be a constant sd node if RHS is not a constant, due to canonicalization, or better assert the conditon.

llvm/test/CodeGen/AArch64/logical-op-with-not.ll

39–40

Related with scalar BIC DAG node (probably not a part of this patch)

%4 = xor i32 %3, -1
%5 = and i32 %4, %1

itself could be a BIC as well.

llc with -debug shows xor %3, -1 is combined into or (xor %0, -1), -65281 so tblgen pattern won't see the %4 %5 sequence.

[bcl5980]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

16046

Yeah, we have two ways to fix the issue:

and + orn
and + bic

The problem for orn is it always need to involve a mov. So I choice and+bic to fix the issue.
I also try to add the code into ISelDAG, but it looks the code become complex and it will lose some optimization for the first and. Like the case @bic_shiftedreg_from_and.

[bcl5980]

llvm/test/CodeGen/AArch64/logical-op-with-not.ll

39–40

Yeah, actually what this change do is reverting the xor + or to xor + and.

[dmgreen]

Hello. In general we have found it is better to avoid AArch64ISD nodes if possible. That way the benefits from generic dag combines keep applying, as opposed to becoming black boxes that the rest of the optimizer cannot see. Sometimes they are necessary, and that might be the case here, but is it possible to just adjust the code using standard nodes? It doesn't seem like this applies very often though - perhaps that makes it OK in this case.

[bcl5980]

In D139609#3998214, @dmgreen wrote:

Hello. In general we have found it is better to avoid AArch64ISD nodes if possible. That way the benefits from generic dag combines keep applying, as opposed to becoming black boxes that the rest of the optimizer cannot see. Sometimes they are necessary, and that might be the case here, but is it possible to just adjust the code using standard nodes? It doesn't seem like this applies very often though - perhaps that makes it OK in this case.

The headache thing here is DAGCombiner will revert the pattern to the origin if I use standard node. So I try to add a new AArch64ISD.

[bcl5980]

In D139609#4003099, @bcl5980 wrote:

In D139609#3998214, @dmgreen wrote:

Hello. In general we have found it is better to avoid AArch64ISD nodes if possible. That way the benefits from generic dag combines keep applying, as opposed to becoming black boxes that the rest of the optimizer cannot see. Sometimes they are necessary, and that might be the case here, but is it possible to just adjust the code using standard nodes? It doesn't seem like this applies very often though - perhaps that makes it OK in this case.

The headache thing here is DAGCombiner will revert the pattern to the origin if I use standard node. So I try to add a new AArch64ISD.

Maybe I can put the transform to after legalize to make sure standard nodes exist longer.

[dmgreen]

The headache thing here is DAGCombiner will revert the pattern to the origin if I use standard node. So I try to add a new AArch64ISD.

Maybe I can put the transform to after legalize to make sure standard nodes exist longer.

Putting the transform late can certainly help, thats a good option if it is needed. It can sometimes be better to just prevent the DAG combine that is going in the wrong direction. There are a set of methods like shouldFoldConstantShiftPairToMask and isDesirableToCommuteWithShift that can be used by the target to control how the DAGCombiner acts. There can be problems if the transform is towards a canonical form that other DAG combines rely upon, but it sounds like in this case it might be easy enough to add?

[bcl5980]

In D139609#4004201, @dmgreen wrote:

The headache thing here is DAGCombiner will revert the pattern to the origin if I use standard node. So I try to add a new AArch64ISD.

Maybe I can put the transform to after legalize to make sure standard nodes exist longer.

Putting the transform late can certainly help, thats a good option if it is needed. It can sometimes be better to just prevent the DAG combine that is going in the wrong direction. There are a set of methods like shouldFoldConstantShiftPairToMask and isDesirableToCommuteWithShift that can be used by the target to control how the DAGCombiner acts. There can be problems if the transform is towards a canonical form that other DAG combines rely upon, but it sounds like in this case it might be easy enough to add?

These method like shouldFoldConstantShiftPairToMask or isDesirableToCommuteWithShift only prevent DAG to transform a good pattern to bad pattern for us. But if the code is the bad pattern at first, we still can't optimize the case. So if DAGCombiner already has some canonicalization, I prefer to optimize the pattern after DAG combine. And I am not sure if we need add a TLI interface, what interface can we add to make the code general?

[dmgreen]

These method like shouldFoldConstantShiftPairToMask or isDesirableToCommuteWithShift only prevent DAG to transform a good pattern to bad pattern for us. But if the code is the bad pattern at first, we still can't optimize the case. So if DAGCombiner already has some canonicalization, I prefer to optimize the pattern after DAG combine. And I am not sure if we need add a TLI interface, what interface can we add to make the code general?

It appears to be this code that is transforming not(and(x,C)) -> or(not(x), not(C)): https://github.com/llvm/llvm-project/blob/85d049a089d4a6a4a67145429ea5d8e155651138/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp#L8746
There would be advantages and disadvantages to both methods, but it seems like disabling that with a target hook, either universally or in specific cases should work and might be a little more general than this version. mvn_shiftedreg_from_and does get a little worse though, which can maybe be fixed in the DAG2DAG matchers? It could help other architectures if the not constant isn't as cheap as the original too.
If the reverse pattern is needed, it should be OK to add either as a DAG combine or in AArch64ISelLowering, so long as it does not fight with the existing combines.

I would recommend avoiding new AArch64ISD nodes, but if the alternative doesn't work then make sure we only start creating the node late - after the DAG has been legalized.

llvm/lib/Target/AArch64/AArch64ISelLowering.h

enum NodeType : unsigned {
 
   // Arithmetic instructions which write flags.
   ADDS,
   SUBS,
   ADCS,
   SBCS,
   ANDS,
 
+  // Scalar logical instructions with not operand
+  SBIC,
+
   // Conditional compares. Operands: left,right,falsecc,cc,flags
   CCMP,
   CCMN,
   FCCMP,
 
   // Floating point comparison
   FCMP,
 

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

case AArch64ISD::FIRST_NUMBER:
     MAKE_CASE(AArch64ISD::SETCC_MERGE_ZERO)
     MAKE_CASE(AArch64ISD::ADC)
     MAKE_CASE(AArch64ISD::SBC)
     MAKE_CASE(AArch64ISD::ADDS)
     MAKE_CASE(AArch64ISD::SUBS)
     MAKE_CASE(AArch64ISD::ADCS)
     MAKE_CASE(AArch64ISD::SBCS)
     MAKE_CASE(AArch64ISD::ANDS)
+    MAKE_CASE(AArch64ISD::SBIC)
     MAKE_CASE(AArch64ISD::CCMP)
     MAKE_CASE(AArch64ISD::CCMN)
     MAKE_CASE(AArch64ISD::FCCMP)
     MAKE_CASE(AArch64ISD::FCMP)
     MAKE_CASE(AArch64ISD::STRICT_FCMP)
     MAKE_CASE(AArch64ISD::STRICT_FCMPE)
     MAKE_CASE(AArch64ISD::DUP)
     MAKE_CASE(AArch64ISD::DUPLANE8)
static SDValue performSVEAndCombine(SDNode *N,
   }
 
   if (isConstantSplatVectorMaskForType(Mask.getNode(), MemVT))
     return Src;
 
   return SDValue();
 }
 
+// (~X | C) & Y --> bic Y, (X & ~C)
+static SDValue performAndCombineWithNotOp(SDNode *N, SelectionDAG &DAG) {
+  EVT VT = N->getValueType(0);
+  if (VT != MVT::i32 && VT != MVT::i64)
+    return SDValue();
+
+  SDValue LHS = N->getOperand(0);
+  SDValue RHS = N->getOperand(1);
+
+  SDLoc DL(N);
+  SDValue X, C;
+  auto canGetNotFromOrXor = [&](SDNode *N, SDValue Op0) {
+    if (Op0.getOpcode() != ISD::OR || !Op0.hasOneUse())
+      return false;
+
+    if (!isa<ConstantSDNode>(Op0.getOperand(1)))
+      return false;
+
+    SDValue Op0LHS = Op0.getOperand(0);
+    if (!Op0LHS.hasOneUse())
+      return false;
+
+    if (Op0LHS->getOpcode() == ISD::ANY_EXTEND && VT == MVT::i64 &&
+        Op0LHS->getOperand(0).getValueType() == MVT::i32)
+      Op0LHS = Op0LHS->getOperand(0);
+
+    if (Op0LHS.getOpcode() != ISD::XOR || !Op0LHS.hasOneUse())
+      return false;
+
+    ConstantSDNode *XorC = dyn_cast<ConstantSDNode>(Op0LHS.getOperand(1));
+    if (!XorC || !XorC->isAllOnes())
+      return false;
+
+    C = DAG.getNOT(DL, Op0.getOperand(1), VT);
+    X = Op0LHS.getOperand(0);
+    return true;
+  };
+
+  if (canGetNotFromOrXor(N, LHS) && !isa<ConstantSDNode>(RHS)) {
+    if (X.getValueType() != VT)
+      X = DAG.getNode(ISD::ANY_EXTEND, DL, VT, X);
+    SDValue AndVal = DAG.getNode(ISD::AND, DL, VT, X, C);
+    return DAG.getNode(AArch64ISD::SBIC, DL, VT, RHS, AndVal);
+  }
+
+  if (canGetNotFromOrXor(N, RHS)) {
+    if (X.getValueType() != VT)
+      X = DAG.getNode(ISD::ANY_EXTEND, DL, VT, X);
+    SDValue AndVal = DAG.getNode(ISD::AND, DL, VT, X, C);
+    return DAG.getNode(AArch64ISD::SBIC, DL, VT, LHS, AndVal);
+  }
+
+  return SDValue();
+}
+
 static SDValue performANDCombine(SDNode *N,
                                  TargetLowering::DAGCombinerInfo &DCI) {
   SelectionDAG &DAG = DCI.DAG;
   SDValue LHS = N->getOperand(0);
   SDValue RHS = N->getOperand(1);
   EVT VT = N->getValueType(0);
 
   if (SDValue R = performANDORCSELCombine(N, DAG))
     return R;
 
   if (!DAG.getTargetLoweringInfo().isTypeLegal(VT))
     return SDValue();
 
   if (VT.isScalableVector())
     return performSVEAndCombine(N, DCI);
 
+  if (SDValue R = performAndCombineWithNotOp(N, DAG))
+    return R;
+
   // The combining code below works only for NEON vectors. In particular, it
   // does not work for SVE when dealing with vectors wider than 128 bits.
   if (!VT.is64BitVector() && !VT.is128BitVector())
     return SDValue();
 
   BuildVectorSDNode *BVN = dyn_cast<BuildVectorSDNode>(RHS.getNode());
   if (!BVN)
     return SDValue();

llvm/lib/Target/AArch64/AArch64InstrInfo.td

def AArch64and_flag  : SDNode<"AArch64ISD::ANDS",  SDTBinaryArithWithFlagsOut,
                             [SDNPCommutative]>;
 def AArch64adc_flag  : SDNode<"AArch64ISD::ADCS",  SDTBinaryArithWithFlagsInOut>;
 def AArch64sbc_flag  : SDNode<"AArch64ISD::SBCS",  SDTBinaryArithWithFlagsInOut>;
 
 def AArch64ccmp      : SDNode<"AArch64ISD::CCMP",  SDT_AArch64CCMP>;
 def AArch64ccmn      : SDNode<"AArch64ISD::CCMN",  SDT_AArch64CCMP>;
 def AArch64fccmp     : SDNode<"AArch64ISD::FCCMP", SDT_AArch64FCCMP>;
 
+def AArch64sbic  : SDNode<"AArch64ISD::SBIC",  SDTIntBinOp>;
+
 def AArch64threadpointer : SDNode<"AArch64ISD::THREAD_POINTER", SDTPtrLeaf>;
 
 def AArch64fcmp         : SDNode<"AArch64ISD::FCMP", SDT_AArch64FCmp>;
 def AArch64strict_fcmp  : SDNode<"AArch64ISD::STRICT_FCMP", SDT_AArch64FCmp,
                                  [SDNPHasChain]>;
 def AArch64strict_fcmpe : SDNode<"AArch64ISD::STRICT_FCMPE", SDT_AArch64FCmp,
                                  [SDNPHasChain]>;
 def AArch64any_fcmp     : PatFrags<(ops node:$lhs, node:$rhs),
def : InstAlias<"tst $src1, $src2$sh",
                (ANDSWrs WZR, GPR32:$src1, GPR32:$src2, logical_shift32:$sh), 2>;
 def : InstAlias<"tst $src1, $src2$sh",
                (ANDSXrs XZR, GPR64:$src1, GPR64:$src2, logical_shift64:$sh), 2>;
 
 
 def : Pat<(not GPR32:$Wm), (ORNWrr WZR, GPR32:$Wm)>;
 def : Pat<(not GPR64:$Xm), (ORNXrr XZR, GPR64:$Xm)>;
 
+multiclass LogicalRegPat<SDPatternOperator OpNode, string INST> {
+  def : Pat<(OpNode GPR32:$Wn, GPR32:$Wm), 
+            (!cast<Instruction>(INST # Wrr) GPR32:$Wn, GPR32:$Wm)>;
+
+  def : Pat<(OpNode GPR64:$Xn, GPR64:$Xm), 
+            (!cast<Instruction>(INST # Xrr) GPR64:$Xn, GPR64:$Xm)>;
+
+  def : Pat<(OpNode GPR32:$Wn, 
+              (logical_shifted_reg32 GPR32:$Wm, logical_shift32:$shift)), 
+            (!cast<Instruction>(INST # Wrs) GPR32:$Wn, GPR32:$Wm, 
+              logical_shift32:$shift)>;
+
+  def : Pat<(OpNode GPR64:$Xn, 
+              (logical_shifted_reg64 GPR64:$Xm, logical_shift64:$shift)), 
+            (!cast<Instruction>(INST # Xrs) GPR64:$Xn, GPR64:$Xm, 
+              logical_shift64:$shift)>;
+}
+
+defm : LogicalRegPat<AArch64sbic, "BIC">;
+
 
 //===----------------------------------------------------------------------===//
 // One operand data processing instructions.
 //===----------------------------------------------------------------------===//
 
 defm CLS    : OneOperandData<0b000101, "cls">;
 defm CLZ    : OneOperandData<0b000100, "clz", ctlz>;
 defm RBIT   : OneOperandData<0b000000, "rbit", bitreverse>;

llvm/test/CodeGen/AArch64/logical-op-with-not.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -verify-machineinstrs < %s -mtriple=aarch64-none-linux-gnu | FileCheck %s
 
 define i64 @and_bic(i64 %0, i64 %1) {
 ; CHECK-LABEL: and_bic:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mvn w8, w0
-; CHECK-NEXT:    orr x8, x8, #0xffffffffffff00ff
-; CHECK-NEXT:    and x0, x8, x1
+; CHECK-NEXT:    and x8, x0, #0xff00
+; CHECK-NEXT:    bic x0, x1, x8
 ; CHECK-NEXT:    ret
   %3 = and i64 %0, 65280
   %4 = xor i64 %3, -1
   %5 = and i64 %4, %1
   ret i64 %5
 }
 
 define i64 @and_bic2(i32 %0, i64 %1) {
 ; CHECK-LABEL: and_bic2:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mvn w8, w0
 ; CHECK-NEXT:    orr w8, w8, #0xffff00ff
 ; CHECK-NEXT:    and x0, x8, x1
 ; CHECK-NEXT:    ret
   %3 = and i32 %0, 65280
   %4 = xor i32 %3, -1
   %5 = zext i32 %4 to i64
   %6 = and i64 %5, %1
   ret i64 %6
 }
 
 define i32 @and_bic3(i32 %0, i32 %1) {
 ; CHECK-LABEL: and_bic3:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mvn w8, w0
-; CHECK-NEXT:    orr w8, w8, #0xffff00ff
-; CHECK-NEXT:    and w0, w8, w1
+; CHECK-NEXT:    and w8, w0, #0xff00
+; CHECK-NEXT:    bic w0, w1, w8
 ; CHECK-NEXT:    ret
   %3 = and i32 %0, 65280
   %4 = xor i32 %3, -1
   %5 = and i32 %4, %1
   ret i32 %5
 }
 
 define i64 @and_eon(i64 %0, i64 %1) {
 ; CHECK-LABEL: and_eon:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    and x8, x0, #0xff00
 ; CHECK-NEXT:    eon x0, x8, x1

llvm/test/CodeGen/AArch64/shiftregister-from-and.ll

 ; CHECK-NEXT:    and x0, x8, #0xffffffffff000000
 ; CHECK-NEXT:    ret
   %ashr = ashr i64 %a, 23
   %and = and i64 %ashr, -16777216
   %r = and i64 %b, %and
   ret i64 %r
 }
 
-; TODO: logic shift reg pattern: bic
-
 define i64 @bic_shiftedreg_from_and(i64 %a, i64 %b) {
 ; CHECK-LABEL: bic_shiftedreg_from_and:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w8, #16777215
-; CHECK-NEXT:    orn x8, x8, x0, asr #23
-; CHECK-NEXT:    and x0, x1, x8
+; CHECK-NEXT:    asr x8, x0, #47
+; CHECK-NEXT:    bic x0, x1, x8, lsl #24
 ; CHECK-NEXT:    ret
   %ashr = ashr i64 %a, 23
   %and = and i64 %ashr, -16777216
   %not = xor i64 %and, -1
   %r = and i64 %b, %not
   ret i64 %r
 }