[DagCombine] Fold (X & ~Y) | Y with truncated not

[nikic]

Summary

This extends the (X & ~Y) | Y to X | Y fold to also work if ~Y is a truncated not (when taking into account the mask X). This is done by exporting the infrastructure added in D124856 and reusing it here.

I've retained the old value of AllowUndefs=false, though probably this can be switched to true with extra test coverage.

[RKSimon]

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

1691

note -> node

1692

an empty SDValue

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4688–4689

Would this be more generally useful if we replaced Mask with a APInt DemandedBits?

[nikic]

Fix comment typos

[nikic]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4688–4689

Yes -- though it would make the current callers, which all have the mask as an SDValue, more complicated. Would have to extract the isConstOrConstSplat part plus a fallback to an all-ones mask to each caller. I'd personally delay that until we have a use-case that requires passing an APInt.

[RKSimon]

LGTM

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4688–4689

OK - that's fine, there might be a couple of cases in SimplifyDemandedBits, but we can handle that if/when its useful to convert them to use this.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

 /// Return the non-extracted vector source operand of \p V if it exists.
 /// If \p V is not an extracted subvector, it is returned as-is.
 SDValue peekThroughExtractSubvectors(SDValue V);
 
 /// Returns true if \p V is a bitwise not operation. Assumes that an all ones
 /// constant is canonicalized to be operand 1.
 bool isBitwiseNot(SDValue V, bool AllowUndefs = false);
 
+/// If \p V is a bitwise not, returns the inverted operand. Otherwise returns
+/// an empty SDValue. Only bits set in \p Mask are required to be inverted,
+/// other bits may be arbitrary.
+SDValue getBitwiseNotOperand(SDValue V, SDValue Mask, bool AllowUndefs);
+
 /// Returns the SDNode if it is a constant splat BuildVector or constant int.
 ConstantSDNode *isConstOrConstSplat(SDValue N, bool AllowUndefs = false,
                                     bool AllowTruncation = false);
 
 /// Returns the SDNode if it is a demanded constant splat BuildVector or
 /// constant int.
 ConstantSDNode *isConstOrConstSplat(SDValue N, const APInt &DemandedElts,
                                     bool AllowUndefs = false,

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 }
 
 /// OR combines for which the commuted variant will be tried as well.
 static SDValue visitORCommutative(
     SelectionDAG &DAG, SDValue N0, SDValue N1, SDNode *N) {
   EVT VT = N0.getValueType();
   if (N0.getOpcode() == ISD::AND) {
     // fold (or (and X, (xor Y, -1)), Y) -> (or X, Y)
-    if (isBitwiseNot(N0.getOperand(1)) && N0.getOperand(1).getOperand(0) == N1)
+    // TODO: Set AllowUndefs = true.
+    if (getBitwiseNotOperand(N0.getOperand(1), N0.getOperand(0),
+                             /* AllowUndefs */ false) == N1)
       return DAG.getNode(ISD::OR, SDLoc(N), VT, N0.getOperand(0), N1);
 
     // fold (or (and (xor Y, -1), X), Y) -> (or X, Y)
-    if (isBitwiseNot(N0.getOperand(0)) && N0.getOperand(0).getOperand(0) == N1)
+    if (getBitwiseNotOperand(N0.getOperand(0), N0.getOperand(1),
+                             /* AllowUndefs */ false) == N1)
       return DAG.getNode(ISD::OR, SDLoc(N), VT, N0.getOperand(1), N1);
   }
 
   if (SDValue R = foldLogicOfShifts(N, N0, N1, DAG))
     return R;
 
   auto peekThroughZext = [](SDValue V) {
     if (V->getOpcode() == ISD::ZERO_EXTEND)

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
     if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
       if (CA->isZero() && CB->isZero()) return true;
 
   // Otherwise they may not be equal.
   return false;
 }
 
 // Only bits set in Mask must be negated, other bits may be arbitrary.
-static SDValue getBitwiseNotOperand(SDValue V, SDValue Mask) {
-  if (isBitwiseNot(V, true))
+SDValue llvm::getBitwiseNotOperand(SDValue V, SDValue Mask, bool AllowUndefs) {
+  if (isBitwiseNot(V, AllowUndefs))
     return V.getOperand(0);
 
   // Handle any_extend (not (truncate X)) pattern, where Mask only sets
   // bits in the non-extended part.
   ConstantSDNode *MaskC = isConstOrConstSplat(Mask);
   if (!MaskC || V.getOpcode() != ISD::ANY_EXTEND)
     return SDValue();
   SDValue ExtArg = V.getOperand(0);
   if (ExtArg.getScalarValueSizeInBits() >=
           MaskC->getAPIntValue().getActiveBits() &&
-      isBitwiseNot(ExtArg, true) &&
+      isBitwiseNot(ExtArg, AllowUndefs) &&
       ExtArg.getOperand(0).getOpcode() == ISD::TRUNCATE &&
       ExtArg.getOperand(0).getOperand(0).getValueType() == V.getValueType())
     return ExtArg.getOperand(0).getOperand(0);
   return SDValue();
 }
 
 static bool haveNoCommonBitsSetCommutative(SDValue A, SDValue B) {
   // Match masked merge pattern (X & ~M) op (Y & M)
   // Including degenerate case (X & ~M) op M
   auto MatchNoCommonBitsPattern = [&](SDValue Not, SDValue Mask,
                                       SDValue Other) {
-    if (SDValue NotOperand = getBitwiseNotOperand(Not, Mask)) {
+    if (SDValue NotOperand =
+            getBitwiseNotOperand(Not, Mask, /* AllowUndefs */ true)) {
       if (Other == NotOperand)
         return true;
       if (Other->getOpcode() == ISD::AND)
         return NotOperand == Other->getOperand(0) ||
                NotOperand == Other->getOperand(1);
     }
     return false;
   };

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

; CHECK-NEXT:    retq
   call void @use(i8 %and)
   %add = add i8 %and, %x
   ret i8 %add
 }
 
 define i64 @add_and_xor_const(i64 %x) {
 ; CHECK-LABEL: add_and_xor_const:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    notl %eax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    orq %rdi, %rax
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    orq $1, %rax
 ; CHECK-NEXT:    retq
   %xor = xor i64 %x, -1
   %and = and i64 %xor, 1
   %add = add i64 %and, %x
   ret i64 %add
 }
 
 define i64 @add_and_xor_const_wrong_op(i64 %x, i64 %y) {
 ; CHECK-LABEL: add_and_xor_const_wrong_op:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    notl %esi
 ; CHECK-NEXT:    andl $1, %esi
 ; CHECK-NEXT:    leaq (%rsi,%rdi), %rax
 ; CHECK-NEXT:    retq
   %xor = xor i64 %y, -1
   %and = and i64 %xor, 1
   %add = add i64 %and, %x
   ret i64 %add
 }
 
 define i64 @add_and_xor_const_explicit_trunc(i64 %x) {
 ; CHECK-LABEL: add_and_xor_const_explicit_trunc:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    notl %eax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    orq %rdi, %rax
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    orq $1, %rax
 ; CHECK-NEXT:    retq
   %trunc = trunc i64 %x to i32
   %xor = xor i32 %trunc, -1
   %ext = sext i32 %xor to i64
   %and = and i64 %ext, 1
   %add = add i64 %and, %x
   ret i64 %add
 }
; CHECK-NEXT:    retq
   %offset = xor i64 %old.not, %m
   %p = getelementptr i8, i8* %a, i64 %offset
   ret i8* %p
 }
 
 define i8* @gep_and_xor_const(i8* %a) {
 ; CHECK-LABEL: gep_and_xor_const:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    notl %eax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    orq %rdi, %rax
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    orq $1, %rax
 ; CHECK-NEXT:    retq
   %old = ptrtoint i8* %a to i64
   %old.not = and i64 %old, 1
   %offset = xor i64 %old.not, 1
   %p = getelementptr i8, i8* %a, i64 %offset
   ret i8* %p
 }