[RISCV] Apply DeMorgan's law to (and/or (xor X, 1), (xor Y, 1)) if X and Y are 0/1.

[craig.topper]

Summary

This optimizes xors that appear due to legalizing setge/setle which
require an xor with 1. This reduces the number of xors and may
allow the xor to fold with a beqz or bnez.

[reames]

LGTM

[craig.topper]

I didn't notice, but this only handled or. The and case ended up with an not due to SimplifyDemandedBits.

[craig.topper]

Fix the AND case

[reames]

Can you land the prior version and post the xor n, -1 bit as a separate patch? It's slightly non-obvious.

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

static SDValue performSUBCombine(SDNode *N, SelectionDAG &DAG) {
 
   // fold (sub x, (select lhs, rhs, cc, 0, y)) ->
   //      (select lhs, rhs, cc, x, (sub x, y))
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   return combineSelectAndUse(N, N1, N0, DAG, /*AllOnes*/ false);
 }
 
-static SDValue performANDCombine(SDNode *N, SelectionDAG &DAG,
+// Apply DeMorgan's law to (and/or (xor X, 1), (xor Y, 1)) if X and Y are 0/1.
+// Legalizing setcc can introduce xors like this. Doing this transform reduces
+// the number of xors and may allow the xor to fold into a branch condition.
+static SDValue combineDeMorganOfBoolean(SDNode *N, SelectionDAG &DAG) {
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+  bool IsAnd = N->getOpcode() == ISD::AND;
+
+  if (N0.getOpcode() != ISD::XOR || N1.getOpcode() != ISD::XOR)
+    return SDValue();
+
+  if (!N0.hasOneUse() || !N1.hasOneUse())
+    return SDValue();
+
+  // RHS of both xors needs to be 1.
+  if (!isOneConstant(N0.getOperand(1)) || !isOneConstant(N1.getOperand(1)))
+    return SDValue();
+
+  EVT VT = N->getValueType(0);
+
+  SDValue N00 = N0.getOperand(0);
+  SDValue N10 = N1.getOperand(0);
+
+  // The LHS of the xors needs to be 0/1.
+  APInt Mask = APInt::getBitsSetFrom(VT.getSizeInBits(), 1);
+  if (!DAG.MaskedValueIsZero(N00, Mask) || !DAG.MaskedValueIsZero(N10, Mask))
+    return SDValue();
+
+  // Invert the opcode and insert a new xor.
+  SDLoc DL(N);
+  unsigned Opc = IsAnd ? ISD::OR : ISD::AND;
+  SDValue Logic = DAG.getNode(Opc, DL, VT, N00, N10);
+  return DAG.getNode(ISD::XOR, DL, VT, Logic, DAG.getConstant(1, DL, VT));
+}
+
+static SDValue performANDCombine(SDNode *N,
+                                 TargetLowering::DAGCombinerInfo &DCI,
                                  const RISCVSubtarget &Subtarget) {
+  SelectionDAG &DAG = DCI.DAG;
+
   SDValue N0 = N->getOperand(0);
   // Pre-promote (i32 (and (srl X, Y), 1)) on RV64 with Zbs without zero
   // extending X. This is safe since we only need the LSB after the shift and
   // shift amounts larger than 31 would produce poison. If we wait until
   // type legalization, we'll create RISCVISD::SRLW and we can't recover it
   // to use a BEXT instruction.
   if (Subtarget.is64Bit() && Subtarget.hasStdExtZbs() &&
       N->getValueType(0) == MVT::i32 && isOneConstant(N->getOperand(1)) &&
       N0.getOpcode() == ISD::SRL && !isa<ConstantSDNode>(N0.getOperand(1)) &&
       N0.hasOneUse()) {
     SDLoc DL(N);
     SDValue Op0 = DAG.getNode(ISD::ANY_EXTEND, DL, MVT::i64, N0.getOperand(0));
     SDValue Op1 = DAG.getNode(ISD::ZERO_EXTEND, DL, MVT::i64, N0.getOperand(1));
     SDValue Srl = DAG.getNode(ISD::SRL, DL, MVT::i64, Op0, Op1);
     SDValue And = DAG.getNode(ISD::AND, DL, MVT::i64, Srl,
                               DAG.getConstant(1, DL, MVT::i64));
     return DAG.getNode(ISD::TRUNCATE, DL, MVT::i32, And);
   }
 
   if (SDValue V = combineBinOpToReduce(N, DAG))
     return V;
 
+  if (DCI.isAfterLegalizeDAG())
+    if (SDValue V = combineDeMorganOfBoolean(N, DAG))
+      return V;
+
   // fold (and (select lhs, rhs, cc, -1, y), x) ->
   //      (select lhs, rhs, cc, x, (and x, y))
   return combineSelectAndUseCommutative(N, DAG, /*AllOnes*/ true);
 }
 
-static SDValue performORCombine(SDNode *N, SelectionDAG &DAG,
+static SDValue performORCombine(SDNode *N, TargetLowering::DAGCombinerInfo &DCI,
                                 const RISCVSubtarget &Subtarget) {
+  SelectionDAG &DAG = DCI.DAG;
+
   if (Subtarget.hasStdExtZbp()) {
     if (auto GREV = combineORToGREV(SDValue(N, 0), DAG, Subtarget))
       return GREV;
     if (auto GORC = combineORToGORC(SDValue(N, 0), DAG, Subtarget))
       return GORC;
     if (auto SHFL = combineORToSHFL(SDValue(N, 0), DAG, Subtarget))
       return SHFL;
   }
 
   if (SDValue V = combineBinOpToReduce(N, DAG))
     return V;
+
+  if (DCI.isAfterLegalizeDAG())
+    if (SDValue V = combineDeMorganOfBoolean(N, DAG))
+      return V;
+
   // fold (or (select cond, 0, y), x) ->
   //      (select cond, x, (or x, y))
   return combineSelectAndUseCommutative(N, DAG, /*AllOnes*/ false);
 }
 
 static SDValue performXORCombine(SDNode *N, SelectionDAG &DAG) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
case RISCVISD::FMV_X_ANYEXTW_RV64: {
     return DAG.getNode(ISD::AND, DL, VT, NewFMV,
                        DAG.getConstant(~SignBit, DL, VT));
   }
   case ISD::ADD:
     return performADDCombine(N, DAG, Subtarget);
   case ISD::SUB:
     return performSUBCombine(N, DAG);
   case ISD::AND:
-    return performANDCombine(N, DAG, Subtarget);
+    return performANDCombine(N, DCI, Subtarget);
   case ISD::OR:
-    return performORCombine(N, DAG, Subtarget);
+    return performORCombine(N, DCI, Subtarget);
   case ISD::XOR:
     return performXORCombine(N, DAG);
   case ISD::FADD:
   case ISD::UMAX:
   case ISD::UMIN:
   case ISD::SMAX:
   case ISD::SMIN:
   case ISD::FMAXNUM:

llvm/test/CodeGen/RISCV/setcc-logic.ll

; RV64I-NEXT:    ret
   %and = and i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 define i1 @or_icmp_sge(i32 signext %a, i32 signext %b, i32 signext %c, i32 signext %d) nounwind {
 ; RV32I-LABEL: or_icmp_sge:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    slt a0, a0, a1
-; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    slt a1, a2, a3
-; RV32I-NEXT:    xori a1, a1, 1
-; RV32I-NEXT:    or a0, a0, a1
+; RV32I-NEXT:    and a0, a0, a1
+; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: or_icmp_sge:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    slt a0, a0, a1
-; RV64I-NEXT:    xori a0, a0, 1
 ; RV64I-NEXT:    slt a1, a2, a3
-; RV64I-NEXT:    xori a1, a1, 1
-; RV64I-NEXT:    or a0, a0, a1
+; RV64I-NEXT:    and a0, a0, a1
+; RV64I-NEXT:    xori a0, a0, 1
 ; RV64I-NEXT:    ret
   %cmp1 = icmp sge i32 %a, %b
   %cmp2 = icmp sge i32 %c, %d
   %and = or i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 define i1 @or_icmp_sle(i32 signext %a, i32 signext %b, i32 signext %c, i32 signext %d) nounwind {
 ; RV32I-LABEL: or_icmp_sle:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    slt a0, a1, a0
-; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    slt a1, a3, a2
-; RV32I-NEXT:    xori a1, a1, 1
-; RV32I-NEXT:    or a0, a0, a1
+; RV32I-NEXT:    and a0, a0, a1
+; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: or_icmp_sle:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    slt a0, a1, a0
-; RV64I-NEXT:    xori a0, a0, 1
 ; RV64I-NEXT:    slt a1, a3, a2
-; RV64I-NEXT:    xori a1, a1, 1
-; RV64I-NEXT:    or a0, a0, a1
+; RV64I-NEXT:    and a0, a0, a1
+; RV64I-NEXT:    xori a0, a0, 1
 ; RV64I-NEXT:    ret
   %cmp1 = icmp sle i32 %a, %b
   %cmp2 = icmp sle i32 %c, %d
   %and = or i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 define i1 @or_icmp_uge(i32 signext %a, i32 signext %b, i32 signext %c, i32 signext %d) nounwind {
 ; RV32I-LABEL: or_icmp_uge:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    sltu a0, a0, a1
-; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    sltu a1, a2, a3
-; RV32I-NEXT:    xori a1, a1, 1
-; RV32I-NEXT:    or a0, a0, a1
+; RV32I-NEXT:    and a0, a0, a1
+; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: or_icmp_uge:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    sltu a0, a0, a1
-; RV64I-NEXT:    xori a0, a0, 1
 ; RV64I-NEXT:    sltu a1, a2, a3
-; RV64I-NEXT:    xori a1, a1, 1
-; RV64I-NEXT:    or a0, a0, a1
+; RV64I-NEXT:    and a0, a0, a1
+; RV64I-NEXT:    xori a0, a0, 1
 ; RV64I-NEXT:    ret
   %cmp1 = icmp uge i32 %a, %b
   %cmp2 = icmp uge i32 %c, %d
   %and = or i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 define i1 @or_icmp_ule(i32 signext %a, i32 signext %b, i32 signext %c, i32 signext %d) nounwind {
 ; RV32I-LABEL: or_icmp_ule:
 ; RV32I:       # %bb.0:
 ; RV32I-NEXT:    sltu a0, a1, a0
-; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    sltu a1, a3, a2
-; RV32I-NEXT:    xori a1, a1, 1
-; RV32I-NEXT:    or a0, a0, a1
+; RV32I-NEXT:    and a0, a0, a1
+; RV32I-NEXT:    xori a0, a0, 1
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: or_icmp_ule:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    sltu a0, a1, a0
-; RV64I-NEXT:    xori a0, a0, 1
 ; RV64I-NEXT:    sltu a1, a3, a2
-; RV64I-NEXT:    xori a1, a1, 1
-; RV64I-NEXT:    or a0, a0, a1
+; RV64I-NEXT:    and a0, a0, a1
+; RV64I-NEXT:    xori a0, a0, 1
 ; RV64I-NEXT:    ret
   %cmp1 = icmp ule i32 %a, %b
   %cmp2 = icmp ule i32 %c, %d
   %and = or i1 %cmp1, %cmp2
   ret i1 %and
 }