[DAGCombiner] Add Transform for `(and/or (eq/ne A,Pow2),(eq/ne A,-Pow2))`->`(eq/ne (and (and A,Pow2),~(Pow2*2)), 0)`

[goldstein.w.n]

Summary

In many instances this can be preferable if the icmp -> i1 cannot be
done in one instruction (such as X86 for scalars).

At the moment guarded behind TLI.isDesirableToCombineLogicOpOfSETCC.

alive2 links:
https://alive2.llvm.org/ce/z/nLm5sN
https://alive2.llvm.org/ce/z/moEcyE

[goldstein.w.n]

Note, I think this is probably also worth turning on for aarch64: https://godbolt.org/z/8odYov4c1 hence when I put this in DAGCombiner instead of x86 only.

[RKSimon]

llvm/include/llvm/CodeGen/TargetLowering.h

4021

Drop the const from the SDNode args?

[goldstein.w.n]

llvm/include/llvm/CodeGen/TargetLowering.h

4021

Drop the const from the SDNode args?

Really? All the surrounding "should I do this" functions seem to use consts:

  virtual bool isDesirableToCommuteWithShift(const SDNode *N,
                                             CombineLevel Level) const {
    return true;
  }
...
  virtual bool isDesirableToCombineLogicOpOfSETCC(const SDNode *LogicOp,
                                                  const SDNode *SETCC0,
                                                  const SDNode *SETCC1) const {
    return false;
  }

...
  virtual bool isDesirableToCommuteXorWithShift(const SDNode *N) const {
    return true;
  }

[goldstein.w.n]

Remove redundant iszero check

[goldstein.w.n]

Rebase + fix typo + make only oneuse

[goldstein.w.n]

Rebase

[RKSimon]

llvm/include/llvm/CodeGen/TargetLowering.h

4021

OK - never mind

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2414

remove extra newline

5670

Swap over to reduce calling (expensive) hasOneUse calls unnecessarily (or maybe move to the end of the if()):

LHS0 == RHS0 && LHS1C && RHS1C && LHS.hasOneUse() && RHS.hasOneUse() &&

5679

const APInt &C = Pow2->getAPIntValue();

[goldstein.w.n]

Fix style issues, make code a bit better (perf)

[goldstein.w.n]

Fixed up in next version (won't let me submit "done" w.o message).

[goldstein.w.n]

ping.

[RKSimon]

LGTM

llvm/include/llvm/CodeGen/TargetLowering.h

4013

remove trailing w?

llvm/include/llvm/CodeGen/TargetLowering.h

public:
   ///
   /// @param N the shift node
   /// @param Level the current DAGCombine legalization level.
   virtual bool isDesirableToCommuteWithShift(const SDNode *N,
                                              CombineLevel Level) const {
     return true;
   }
 
+  // Return true if its desirable to try and optimize LogicOp(SETCC0, SETCC1).
+  // An example (what is implemented as of writing this) is:
+  //    With C as a power of 2 and C != 0 and C != INT_MIN:
+  //       (icmp eq A, C) | (icmp eq A, -C)
+  //            -> (icmp eq and(add(A, C), ~(C + C)), 0)
+  //     (icmp ne A, C) & (icmp ne A, -C)w
+  //            -> (icmp ne and(add(A, C), ~(C + C)), 0)
+  //
+  // @param LogicOp the logic op
+  // @param SETCC0 the first of the SETCC nodes
+  // @param SETCC0 the second of the SETCC nodes
+  virtual bool isDesirableToCombineLogicOpOfSETCC(const SDNode *LogicOp,
+                                                  const SDNode *SETCC0,
+                                                  const SDNode *SETCC1) const {
+    return false;
+  }
+
   /// Return true if it is profitable to combine an XOR of a logical shift
   /// to create a logical shift of NOT. This transformation may not be desirable
   /// if it disrupts a particularly auspicious target-specific tree (e.g.
   /// BIC on ARM/AArch64). By default, it returns true.
   virtual bool isDesirableToCommuteXorWithShift(const SDNode *N) const {
     return true;
   }
 

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (SDValue NewC = DAG.FoldConstantArithmetic(
     SDValue NewShift = DAG.getNode(IsAdd ? ISD::SRA : ISD::SRL, DL, VT,
                                    Not.getOperand(0), ShAmt);
     return DAG.getNode(ISD::ADD, DL, VT, NewShift, NewC);
   }
 
   return SDValue();
 }
 
+
 static bool isADDLike(SDValue V, const SelectionDAG &DAG) {
   unsigned Opcode = V.getOpcode();
   if (Opcode == ISD::OR)
     return DAG.haveNoCommonBitsSet(V.getOperand(0), V.getOperand(1));
   if (Opcode == ISD::XOR)
     return isMinSignedConstant(V.getOperand(1));
   return false;
 }
if (NewCC != ISD::SETCC_INVALID &&
          (TLI.isCondCodeLegal(NewCC, LL.getSimpleValueType()) &&
           TLI.isOperationLegal(ISD::SETCC, OpVT))))
       return DAG.getSetCC(DL, VT, LL, LR, NewCC);
   }
 
   return SDValue();
 }
 
+static SDValue foldAndOrOfSETCC(SDNode *LogicOp, SelectionDAG &DAG) {
+  assert(
+      (LogicOp->getOpcode() == ISD::AND || LogicOp->getOpcode() == ISD::OR) &&
+      "Invalid Op to combine SETCC with");
+
+  // TODO: Search past casts/truncates.
+  SDValue LHS = LogicOp->getOperand(0);
+  SDValue RHS = LogicOp->getOperand(1);
+  if (LHS->getOpcode() != ISD::SETCC || RHS->getOpcode() != ISD::SETCC)
+    return SDValue();
+
+  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+  if (!TLI.isDesirableToCombineLogicOpOfSETCC(LogicOp, LHS.getNode(),
+                                              RHS.getNode()))
+    return SDValue();
+
+  ISD::CondCode CCL = cast<CondCodeSDNode>(LHS.getOperand(2))->get();
+  ISD::CondCode CCR = cast<CondCodeSDNode>(RHS.getOperand(2))->get();
+
+  SDValue LHS0 = LHS->getOperand(0);
+  SDValue RHS0 = RHS->getOperand(0);
+  SDValue LHS1 = LHS->getOperand(1);
+  SDValue RHS1 = RHS->getOperand(1);
+
+  auto *LHS1C = dyn_cast<ConstantSDNode>(LHS1);
+  auto *RHS1C = dyn_cast<ConstantSDNode>(RHS1);
+  EVT VT = LogicOp->getValueType(0);
+  EVT OpVT = LHS0.getValueType();
+  SDLoc DL(LogicOp);
+
+  // With C as a power of 2 and C != 0 and C != INT_MIN:
+  //   (icmp eq A, C) | (icmp eq A, -C)
+  //        -> (icmp eq and(add(A, C), ~(C + C)), 0)
+  //   (icmp ne A, C) & (icmp ne A, -C)w
+  //        -> (icmp ne and(add(A, C), ~(C + C)), 0)
+  if (CCL == CCR &&
+      CCL == (LogicOp->getOpcode() == ISD::AND ? ISD::SETNE : ISD::SETEQ) &&
+      LHS.hasOneUse() && RHS.hasOneUse() && LHS0 == RHS0 && LHS1C && RHS1C &&
+      OpVT.isInteger() && LHS1C->getAPIntValue() == (-RHS1C->getAPIntValue())) {
+    const ConstantSDNode *Pow2 = nullptr;
+    if (LHS1C->getAPIntValue().isPowerOf2())
+      Pow2 = LHS1C;
+    else if (RHS1C->getAPIntValue().isPowerOf2())
+      Pow2 = RHS1C;
+    // isPowerOf2 is only for non-zero powers of 2.
+    if (Pow2 != nullptr && !Pow2->getAPIntValue().isMinSignedValue()) {
+      APInt C = Pow2->getAPIntValue();
+      SDValue AddOp =
+          DAG.getNode(ISD::ADD, DL, OpVT, LHS0, DAG.getConstant(C, DL, OpVT));
+      SDValue AndOp = DAG.getNode(ISD::AND, DL, OpVT, AddOp,
+                                  DAG.getConstant(~(C + C), DL, OpVT));
+      return DAG.getNode(ISD::SETCC, DL, VT, AndOp,
+                         DAG.getConstant(0, DL, OpVT), LHS.getOperand(2));
+    }
+  }
+
+  return SDValue();
+}
+
 /// This contains all DAGCombine rules which reduce two values combined by
 /// an And operation to a single value. This makes them reusable in the context
 /// of visitSELECT(). Rules involving constants are not included as
 /// visitSELECT() already handles those cases.
 SDValue DAGCombiner::visitANDLike(SDValue N0, SDValue N1, SDNode *N) {
   EVT VT = N1.getValueType();
   SDLoc DL(N);
 
if (isAllOnesConstant(N1))
     return N0;
 
   // if (and x, c) is known to be zero, return 0
   unsigned BitWidth = VT.getScalarSizeInBits();
   ConstantSDNode *N1C = isConstOrConstSplat(N1);
   if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0), APInt::getAllOnes(BitWidth)))
     return DAG.getConstant(0, SDLoc(N), VT);
 
+  if (SDValue R = foldAndOrOfSETCC(N, DAG))
+    return R;
+
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   // reassociate and
   if (SDValue RAND = reassociateOps(ISD::AND, SDLoc(N), N0, N1, N->getFlags()))
     return RAND;
 
   // fold (and (or x, C), D) -> D if (C & D) == D
SDValue DAGCombiner::visitOR(SDNode *N) {
   if (SDValue NewSel = foldBinOpIntoSelect(N))
     return NewSel;
 
   // fold (or x, c) -> c iff (x & ~c) == 0
   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
   if (N1C && DAG.MaskedValueIsZero(N0, ~N1C->getAPIntValue()))
     return N1;
 
+  if (SDValue R = foldAndOrOfSETCC(N, DAG))
+    return R;
+
   if (SDValue Combined = visitORLike(N0, N1, N))
     return Combined;
 
   if (SDValue Combined = combineCarryDiamond(DAG, TLI, N0, N1, N))
     return Combined;
 
   // Recognize halfword bswaps as (bswap + rotl 16) or (bswap + shl 16)
   if (SDValue BSwap = MatchBSwapHWord(N, N0, N1))

llvm/lib/Target/X86/X86ISelLowering.h

public:
     bool isTypeDesirableForOp(unsigned Opc, EVT VT) const override;
 
     /// Return true if the target has native support for the
     /// specified value type and it is 'desirable' to use the type. e.g. On x86
     /// i16 is legal, but undesirable since i16 instruction encodings are longer
     /// and some i16 instructions are slow.
     bool IsDesirableToPromoteOp(SDValue Op, EVT &PVT) const override;
 
+    /// Return true if this is operating on scalar integers.
+    bool
+    isDesirableToCombineLogicOpOfSETCC(const SDNode *LogicOp,
+                                       const SDNode *SETCC0,
+                                       const SDNode *SETCC1) const override;
+
     /// Return the newly negated expression if the cost is not expensive and
     /// set the cost in \p Cost to indicate that if it is cheaper or neutral to
     /// do the negation.
     SDValue getNegatedExpression(SDValue Op, SelectionDAG &DAG,
                                  bool LegalOperations, bool ForCodeSize,
                                  NegatibleCost &Cost,
                                  unsigned Depth) const override;
 

llvm/lib/Target/X86/X86ISelLowering.cpp

     // In order to do that we create NT_BRIND SDNode.
     // Upon ISEL, the pattern will convert it to jmp with NoTrack prefix.
     return DAG.getNode(X86ISD::NT_BRIND, dl, MVT::Other, Value, Addr);
   }
 
   return TargetLowering::expandIndirectJTBranch(dl, Value, Addr, DAG);
 }
 
+bool X86TargetLowering::isDesirableToCombineLogicOpOfSETCC(
+    const SDNode *LogicOp, const SDNode *SETCC0, const SDNode *SETCC1) const {
+  EVT VT = LogicOp->getValueType(0);
+  return VT.isScalarInteger();
+}
+
 bool X86TargetLowering::IsDesirableToPromoteOp(SDValue Op, EVT &PVT) const {
   EVT VT = Op.getValueType();
   bool Is8BitMulByConstant = VT == MVT::i8 && Op.getOpcode() == ISD::MUL &&
                              isa<ConstantSDNode>(Op.getOperand(1));
 
   // i16 is legal, but undesirable since i16 instruction encodings are longer
   // and some i16 instructions are slow.
   // 8-bit multiply-by-constant can usually be expanded to something cheaper

llvm/test/CodeGen/X86/icmp-pow2-logic-npow2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=i686-unknown-linux-gnu < %s | FileCheck %s --check-prefixes=X86
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s --check-prefixes=X64
 
 
 declare i64 @llvm.abs.i64(i64, i1)
 declare i32 @llvm.abs.i32(i32, i1)
 declare i16 @llvm.abs.i16(i16, i1)
 declare i8 @llvm.abs.i8(i8, i1)
 
 define i1 @eq_pow_or(i32 %0) nounwind {
 ; X86-LABEL: eq_pow_or:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    cmpl $32, %eax
-; X86-NEXT:    sete %cl
-; X86-NEXT:    cmpl $-32, %eax
+; X86-NEXT:    addl $32, %eax
+; X86-NEXT:    testl $-65, %eax
 ; X86-NEXT:    sete %al
-; X86-NEXT:    orb %cl, %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: eq_pow_or:
 ; X64:       # %bb.0:
-; X64-NEXT:    cmpl $32, %edi
-; X64-NEXT:    sete %cl
-; X64-NEXT:    cmpl $-32, %edi
+; X64-NEXT:    addl $32, %edi
+; X64-NEXT:    testl $-65, %edi
 ; X64-NEXT:    sete %al
-; X64-NEXT:    orb %cl, %al
 ; X64-NEXT:    retq
   %2 = icmp eq i32 %0, 32
   %3 = icmp eq i32 %0, -32
   %4 = or i1 %2, %3
   ret i1 %4
 }
 
 define i1 @ne_pow_and(i8 %0) nounwind {
 ; X86-LABEL: ne_pow_and:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    cmpb $16, %al
-; X86-NEXT:    setne %cl
-; X86-NEXT:    cmpb $-16, %al
+; X86-NEXT:    addb $16, %al
+; X86-NEXT:    testb $-33, %al
 ; X86-NEXT:    setne %al
-; X86-NEXT:    andb %cl, %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: ne_pow_and:
 ; X64:       # %bb.0:
-; X64-NEXT:    cmpb $16, %dil
-; X64-NEXT:    setne %cl
-; X64-NEXT:    cmpb $-16, %dil
+; X64-NEXT:    addb $16, %dil
+; X64-NEXT:    testb $-33, %dil
 ; X64-NEXT:    setne %al
-; X64-NEXT:    andb %cl, %al
 ; X64-NEXT:    retq
   %2 = icmp ne i8 %0, 16
   %3 = icmp ne i8 %0, -16
   %4 = and i1 %2, %3
   ret i1 %4
 }
 
 define i1 @abs_eq_pow2(i32 %0) nounwind {