3 files changed, 63 insertions, 0 deletions

diff --git a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
index 762b34a8fbe..6faad8b8151 100644
--- a/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -1304,6 +1304,52 @@ bool TargetLowering::isExtendedTrueVal(const ConstantSDNode *N, EVT VT,
   llvm_unreachable("Unexpected enumeration.");
 }
 
+/// If the target supports an 'and-not' or 'and-complement' logic operation,
+/// try to use that to make a comparison operation more efficient.
+static SDValue createAndNotSetCC(EVT VT, SDValue N0, SDValue N1,
+                                 ISD::CondCode Cond, SelectionDAG &DAG,
+                                 SDLoc dl) {
+  // Match these patterns in any of their permutations:
+  // (X & Y) == Y
+  // (X & Y) != Y
+  if (N1.getOpcode() == ISD::AND && N0.getOpcode() != ISD::AND)
+    std::swap(N0, N1);
+
+  if (N0.getOpcode() != ISD::AND || !N0.hasOneUse() ||
+      (Cond != ISD::SETEQ && Cond != ISD::SETNE))
+    return SDValue();
+
+  SDValue X, Y;
+  if (N0.getOperand(0) == N1) {
+    X = N0.getOperand(1);
+    Y = N0.getOperand(0);
+  } else if (N0.getOperand(1) == N1) {
+    X = N0.getOperand(0);
+    Y = N0.getOperand(1);
+  } else {
+    return SDValue();
+  }
+
+  // Bail out if the compare operand that we want to turn into a zero is already
+  // a zero (otherwise, infinite loop).
+  auto *YConst = dyn_cast<ConstantSDNode>(Y);
+  if (YConst && YConst->isNullValue())
+    return SDValue();
+
+  // We don't want to do this transform if the mask is a single bit because
+  // there are more efficient ways to deal with that case (for example, 'bt' on
+  // x86 or 'rlwinm' on PPC).
+  if (!DAG.getTargetLoweringInfo().hasAndNotCompare(Y) ||
+      valueHasExactlyOneBitSet(Y, DAG))
+    return SDValue();
+
+  // Transform this into: ~X & Y == 0.
+  EVT OpVT = X.getValueType();
+  SDValue NotX = DAG.getNOT(SDLoc(X), X, OpVT);
+  SDValue NewAnd = DAG.getNode(ISD::AND, SDLoc(N0), OpVT, NotX, Y);
+  return DAG.getSetCC(dl, VT, NewAnd, DAG.getConstant(0, dl, OpVT), Cond);
+}
+
 /// Try to simplify a setcc built with the specified operands and cc. If it is
 /// unable to simplify it, return a null SDValue.
 SDValue
@@ -2166,6 +2212,9 @@ TargetLowering::SimplifySetCC(EVT VT, SDValue N0, SDValue N1,
     return N0;
   }
 
+  if (SDValue AndNotCC = createAndNotSetCC(VT, N0, N1, Cond, DAG, dl))
+    return AndNotCC;
+
   // Could not fold it.
   return SDValue();
 }
diff --git a/llvm/lib/Target/X86/X86ISelLowering.cpp b/llvm/lib/Target/X86/X86ISelLowering.cpp
index eeaffe9609a..53a1800a2b9 100644
--- a/llvm/lib/Target/X86/X86ISelLowering.cpp
+++ b/llvm/lib/Target/X86/X86ISelLowering.cpp
@@ -4122,6 +4122,18 @@ bool X86TargetLowering::isCheapToSpeculateCtlz() const {
   return Subtarget.hasLZCNT();
 }
 
+bool X86TargetLowering::hasAndNotCompare(SDValue Y) const {
+  if (!Subtarget.hasBMI())
+    return false;
+
+  // There are only 32-bit and 64-bit forms for 'andn'.
+  EVT VT = Y.getValueType();
+  if (VT != MVT::i32 && VT != MVT::i64)
+    return false;
+
+  return true;
+}
+
 /// Return true if every element in Mask, beginning
 /// from position Pos and ending in Pos+Size is undef.
 static bool isUndefInRange(ArrayRef<int> Mask, unsigned Pos, unsigned Size) {
diff --git a/llvm/lib/Target/X86/X86ISelLowering.h b/llvm/lib/Target/X86/X86ISelLowering.h
index 3a99d4d089f..52c4553082d 100644
--- a/llvm/lib/Target/X86/X86ISelLowering.h
+++ b/llvm/lib/Target/X86/X86ISelLowering.h
@@ -751,6 +751,8 @@ namespace llvm {
 
     bool isCheapToSpeculateCtlz() const override;
 
+    bool hasAndNotCompare(SDValue Y) const override;
+
     /// Return the value type to use for ISD::SETCC.
     EVT getSetCCResultType(const DataLayout &DL, LLVMContext &Context,
                            EVT VT) const override;