[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

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

[nikic]

Implement in haveNoCommonBitsSet().

[RKSimon]

LGTM - cheers

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitADDLikeCommutative(SDValue N0, SDValue N1,
 
   // (add X, Carry) -> (addcarry X, 0, Carry)
   if (TLI.isOperationLegalOrCustom(ISD::ADDCARRY, VT))
     if (SDValue Carry = getAsCarry(TLI, N1))
       return DAG.getNode(ISD::ADDCARRY, DL,
                          DAG.getVTList(VT, Carry.getValueType()), N0,
                          DAG.getConstant(0, DL, VT), Carry);
 
+  if (N1.getOpcode() == ISD::AND) {
+    // (add X, (and ~X, Y)) -> (or X, Y)
+    if (isBitwiseNot(N1.getOperand(0)) && N1.getOperand(0).getOperand(0) == N0)
+      return DAG.getNode(ISD::OR, DL, VT, N0, N1.getOperand(1));
+    // (add X, (and Y, ~X)) -> (or X, Y)
+    if (isBitwiseNot(N1.getOperand(1)) && N1.getOperand(1).getOperand(0) == N0)
+      return DAG.getNode(ISD::OR, DL, VT, N0, N1.getOperand(0));
+  }
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDC(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   SDLoc DL(N);

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:    notb %al
 ; CHECK-NEXT:    movzbl %al, %ebx
 ; CHECK-NEXT:    movl %ebx, %edi
 ; CHECK-NEXT:    callq use@PLT
 ; CHECK-NEXT:    andb %r14b, %bl
-; CHECK-NEXT:    movzbl %bl, %ebx
-; CHECK-NEXT:    movl %ebx, %edi
+; CHECK-NEXT:    movzbl %bl, %edi
 ; CHECK-NEXT:    callq use@PLT
-; CHECK-NEXT:    addb %bpl, %bl
-; CHECK-NEXT:    movl %ebx, %eax
+; CHECK-NEXT:    orb %r14b, %bpl
+; CHECK-NEXT:    movl %ebp, %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
 }