[DAGCombiner] Add fold for `~x & x` -> `0`

[goldstein.w.n]

Summary

This is generally done by the InstCombine, but can be emitted as an
intermediate step and is cheap to handle.

[goldstein.w.n]

More tests

[RKSimon]

Did you look at performing this inside SimplifyDemandedBits instead?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6636

Use isBitwiseNot / getBitwiseNotOperand ?

[goldstein.w.n]

In D145143#4164231, @RKSimon wrote:

Did you look at performing this inside SimplifyDemandedBits instead?

Just took a look. Seems to me SimplifyDemandedBits is not really the place to check for patterns between operands, but could move there if you prefer

[goldstein.w.n]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6636

Made new helper that uses isBitwiseNot.

[goldstein.w.n]

Use new helper + isBitwiseNot

[RKSimon]

LGTM with a couple of minors

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6634

Don't bother with the helper - just inline the check.

6636

Use VT instead of getScalarValueSizeInBits/getValueType

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6634

Keep areBitwiseNotOfEachother - sorry I didn't see D145177 :)

[goldstein.w.n]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6636

Also change for the add patch.

[goldstein.w.n]

Use VT

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

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;
 }
 
+static bool
+areBitwiseNotOfEachother(SDValue Op0, SDValue Op1) {
+  return (isBitwiseNot(Op0) && Op0.getOperand(0) == Op1) ||
+         (isBitwiseNot(Op1) && Op1.getOperand(0) == Op0);
+}
+
 /// Try to fold a node that behaves like an ADD (note that N isn't necessarily
 /// an ISD::ADD here, it could for example be an ISD::OR if we know that there
 /// are no common bits set in the operands).
 SDValue DAGCombiner::visitADDLike(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   SDLoc DL(N);
SDValue DAGCombiner::visitAND(SDNode *N) {
   if (SDValue C = DAG.FoldConstantArithmetic(ISD::AND, SDLoc(N), VT, {N0, N1}))
     return C;
 
   // canonicalize constant to RHS
   if (DAG.isConstantIntBuildVectorOrConstantInt(N0) &&
       !DAG.isConstantIntBuildVectorOrConstantInt(N1))
     return DAG.getNode(ISD::AND, SDLoc(N), VT, N1, N0);
 
+  if (areBitwiseNotOfEachother(N0, N1))
+    return DAG.getConstant(APInt::getZero(N1.getScalarValueSizeInBits()),
+                           SDLoc(N), N1.getValueType());
+
   // fold vector ops
   if (VT.isVector()) {
     if (SDValue FoldedVOp = SimplifyVBinOp(N, SDLoc(N)))
       return FoldedVOp;
 
     // fold (and x, 0) -> 0, vector edition
     if (ISD::isConstantSplatVectorAllZeros(N1.getNode()))
       // do not return N1, because undef node may exist in N1

llvm/test/CodeGen/X86/combine-and.ll

; AVX512-NEXT:    retq
   store <4 x i32> %3, ptr %a2, align 16
   %4 = and <4 x i32> %3, %a1
   ret <4 x i32> %4
 }
 
 define <2 x i64> @andnp_xx(<2 x i64> %v0) nounwind {
 ; SSE-LABEL: andnp_xx:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    andnps %xmm0, %xmm0
+; SSE-NEXT:    xorps %xmm0, %xmm0
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: andnp_xx:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vandnps %xmm0, %xmm0, %xmm0
+; AVX-NEXT:    vxorps %xmm0, %xmm0, %xmm0
 ; AVX-NEXT:    retq
   %x = xor <2 x i64> %v0, <i64 -1, i64 -1>
   %y = and <2 x i64> %v0, %x
   ret <2 x i64> %y
 }
 
 define <2 x i64> @andnp_xx_2(<2 x i64> %v0) nounwind {
 ; SSE-LABEL: andnp_xx_2:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    andnps %xmm0, %xmm0
+; SSE-NEXT:    xorps %xmm0, %xmm0
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: andnp_xx_2:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vandnps %xmm0, %xmm0, %xmm0
+; AVX-NEXT:    vxorps %xmm0, %xmm0, %xmm0
 ; AVX-NEXT:    retq
   %x = xor <2 x i64> %v0, <i64 -1, i64 -1>
   %y = and <2 x i64> %x, %v0
   ret <2 x i64> %y
 }
 
 define i64 @andn_xx(i64 %v0) nounwind {
 ; CHECK-LABEL: andn_xx:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    notq %rax
-; CHECK-NEXT:    andq %rdi, %rax
+; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    retq
   %x = xor i64 %v0, -1
   %y = and i64 %v0, %x
   ret i64 %y
 }
 
 define i64 @andn_xx_2(i64 %v0) nounwind {
 ; CHECK-LABEL: andn_xx_2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    notq %rax
-; CHECK-NEXT:    andq %rdi, %rax
+; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    retq
   %x = xor i64 %v0, -1
   %y = and i64 %x, %v0
   ret i64 %y
 }

llvm/test/CodeGen/X86/fold-masked-merge.ll

; CHECK-NEXT:    retq
   %not = xor i32 %a0, -1
   %not_an_and1 = xor i32 %not, %a2
   %or = or i32 %and0, %not_an_and1
   ret i32 %or
 }
 
 ; not a masked merge: `not` operand must not be on same `and`.
 define i32 @not_a_masked_merge4(i32 %a0, i32 %a1, i32 %a2) {
-; NOBMI-LABEL: not_a_masked_merge4:
-; NOBMI:       # %bb.0:
-; NOBMI-NEXT:    andl %esi, %edi
-; NOBMI-NEXT:    movl %edx, %eax
-; NOBMI-NEXT:    notl %eax
-; NOBMI-NEXT:    andl %edx, %eax
-; NOBMI-NEXT:    orl %edi, %eax
-; NOBMI-NEXT:    retq
-;
-; BMI-LABEL: not_a_masked_merge4:
-; BMI:       # %bb.0:
-; BMI-NEXT:    andl %esi, %edi
-; BMI-NEXT:    andnl %edx, %edx, %eax
-; BMI-NEXT:    orl %edi, %eax
-; BMI-NEXT:    retq
+; CHECK-LABEL: not_a_masked_merge4:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movl %edi, %eax
+; CHECK-NEXT:    andl %esi, %eax
+; CHECK-NEXT:    retq
   %and0 = and i32 %a0, %a1
   %not = xor i32 %a2, -1
   %and1 = and i32 %not, %a2
   %or = or i32 %and0, %and1
   ret i32 %or
 }
 
 ; should not transform when operands have multiple users.

llvm/test/CodeGen/X86/setcc-combine.ll

 }
 
 ; (and (setne X, 0), (setne X, -1)) --> (setuge (add X, 1), 2)
 ; Don't combine with i1 - out of range constant
 define void @test_i1_uge(ptr%A2) {
 ; CHECK-LABEL: test_i1_uge:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movzbl (%rdi), %eax
-; CHECK-NEXT:    movl %eax, %ecx
-; CHECK-NEXT:    xorb $1, %cl
-; CHECK-NEXT:    andb %cl, %al
-; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    negq %rax
-; CHECK-NEXT:    andb $1, %cl
-; CHECK-NEXT:    movb %cl, (%rdi,%rax)
+; CHECK-NEXT:    notb %al
+; CHECK-NEXT:    andb $1, %al
+; CHECK-NEXT:    movb %al, (%rdi)
 ; CHECK-NEXT:    retq
   %L5 = load i1, ptr %A2
   %C3 = icmp ne i1 %L5, true
   %C8 = icmp eq i1 %L5, false
   %C9 = icmp ugt i1 %C3, %C8
   %G3 = getelementptr i1, ptr %A2, i1 %C9
   store i1 %C3, ptr %G3
   ret void