[DAGCombine] Fold A + (B & ~A) to A | B

[nikic]

Summary

This is the DAGCombine companion fold for the InstCombine version in D124763. This time we only need to handle A + (B & ~A) to A | B (https://alive2.llvm.org/ce/z/N5fWZ9), because there's only one canonical form.

The reason why this needs to be a DAGCombine is that in the motivating case the add is actually a getelementptr, which only gets converted into an add on the DAG level. This patch is not quite sufficient to handle the getelementptr case yet, because of an interfering demanded bits simplification.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2842 ↗

(On Diff #426415)

Similar question to D124763 - can this be done in SelectionDAG::haveNoCommonBitsSet?

[nikic]

Implement in haveNoCommonBitsSet().

[RKSimon]

LGTM - cheers

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
       if (CA->isZero() && CB->isZero()) return true;
 
   // Otherwise they may not be equal.
   return false;
 }
 
 static bool haveNoCommonBitsSetCommutative(SDValue A, SDValue B) {
   // Match masked merge pattern (X & ~M) op (Y & M)
-  if (A->getOpcode() == ISD::AND && B->getOpcode() == ISD::AND) {
-    auto MatchNoCommonBitsPattern = [&](SDValue NotM, SDValue And) {
-      if (isBitwiseNot(NotM, true)) {
-        SDValue NotOperand = NotM->getOperand(0);
-        return NotOperand == And->getOperand(0) ||
-               NotOperand == And->getOperand(1);
-      }
-      return false;
-    };
+  // Including degenerate case (X & ~M) op M
+  auto MatchNoCommonBitsPattern = [&](SDValue NotM, SDValue Other) {
+      if (Other == NotOperand)
+        return true;
+      if (Other->getOpcode() == ISD::AND)
+        return NotOperand == Other->getOperand(0) ||
+               NotOperand == Other->getOperand(1);
+  if (A->getOpcode() == ISD::AND)
     return MatchNoCommonBitsPattern(A->getOperand(0), B) ||
            MatchNoCommonBitsPattern(A->getOperand(1), B);
-  }
   return false;
 }
 
 // FIXME: unify with llvm::haveNoCommonBitsSet.
 bool SelectionDAG::haveNoCommonBitsSet(SDValue A, SDValue B) const {
   assert(A.getValueType() == B.getValueType() &&
          "Values must have the same type");
   if (haveNoCommonBitsSetCommutative(A, B) ||

llvm/test/CodeGen/X86/add-and-not.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-linux | FileCheck %s
 
 declare void @use(i8)
 
 define i8 @add_and_xor(i8 %x, i8 %y) {
 ; CHECK-LABEL: add_and_xor:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    notb %al
-; CHECK-NEXT:    andb %sil, %al
-; CHECK-NEXT:    addb %dil, %al
+; CHECK-NEXT:    orl %esi, %eax
+; CHECK-NEXT:    # kill: def $al killed $al killed $eax
 ; CHECK-NEXT:    retq
   %xor = xor i8 %x, -1
   %and = and i8 %xor, %y
   %add = add i8 %and, %x
   ret i8 %add
 }
 
 define i8 @add_and_xor_wrong_const(i8 %x, i8 %y) {
; CHECK-NEXT:    retq
   %add = add i8 %and, %x
   ret i8 %add
 }
 
 define i8 @add_and_xor_commuted1(i8 %x, i8 %y) {
 ; CHECK-LABEL: add_and_xor_commuted1:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    notb %al
-; CHECK-NEXT:    andb %sil, %al
-; CHECK-NEXT:    addb %dil, %al
+; CHECK-NEXT:    orl %esi, %eax
+; CHECK-NEXT:    # kill: def $al killed $al killed $eax
 ; CHECK-NEXT:    retq
   %xor = xor i8 %x, -1
   %and = and i8 %y, %xor
   %add = add i8 %and, %x
   ret i8 %add
 }
 
 define i8 @add_and_xor_commuted2(i8 %x, i8 %y) {
 ; CHECK-LABEL: add_and_xor_commuted2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    notb %al
-; CHECK-NEXT:    andb %sil, %al
-; CHECK-NEXT:    addb %dil, %al
+; CHECK-NEXT:    orl %esi, %eax
+; CHECK-NEXT:    # kill: def $al killed $al killed $eax
 ; CHECK-NEXT:    retq
   %xor = xor i8 %x, -1
   %and = and i8 %xor, %y
   %add = add i8 %x, %and
   ret i8 %add
 }
 
 define i8 @add_and_xor_commuted3(i8 %x, i8 %y) {
 ; CHECK-LABEL: add_and_xor_commuted3:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    notb %al
-; CHECK-NEXT:    andb %sil, %al
-; CHECK-NEXT:    addb %dil, %al
+; CHECK-NEXT:    orl %esi, %eax
+; CHECK-NEXT:    # kill: def $al killed $al killed $eax
 ; CHECK-NEXT:    retq
   %xor = xor i8 %x, -1
   %and = and i8 %y, %xor
   %add = add i8 %x, %and
   ret i8 %add
 }
 
 define i8 @add_and_xor_extra_use(i8 %x, i8 %y) nounwind {
 ; CHECK-LABEL: add_and_xor_extra_use:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    pushq %rbp
 ; CHECK-NEXT:    pushq %r14
 ; CHECK-NEXT:    pushq %rbx
-; CHECK-NEXT:    movl %esi, %r14d
-; CHECK-NEXT:    movl %edi, %ebp
-; CHECK-NEXT:    movl %ebp, %eax
+; CHECK-NEXT:    movl %esi, %ebx
+; CHECK-NEXT:    movl %edi, %r14d
+; CHECK-NEXT:    movl %r14d, %eax
 ; CHECK-NEXT:    notb %al
-; CHECK-NEXT:    movzbl %al, %ebx
-; CHECK-NEXT:    movl %ebx, %edi
+; CHECK-NEXT:    movzbl %al, %ebp
+; CHECK-NEXT:    movl %ebp, %edi
 ; CHECK-NEXT:    callq use@PLT
-; CHECK-NEXT:    andb %r14b, %bl
-; CHECK-NEXT:    movzbl %bl, %ebx
-; CHECK-NEXT:    movl %ebx, %edi
+; CHECK-NEXT:    andb %bl, %bpl
+; CHECK-NEXT:    movzbl %bpl, %edi
 ; CHECK-NEXT:    callq use@PLT
-; CHECK-NEXT:    addb %bpl, %bl
+; CHECK-NEXT:    orb %r14b, %bl
 ; CHECK-NEXT:    movl %ebx, %eax
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    popq %r14
 ; CHECK-NEXT:    popq %rbp
 ; CHECK-NEXT:    retq
   %xor = xor i8 %x, -1
   call void @use(i8 %xor)
   %and = and i8 %xor, %y
   call void @use(i8 %and)
   %add = add i8 %and, %x
   ret i8 %add
 }