[SDAG] Handle truncated not in haveNoCommonBitsSet()

[nikic]

Summary

Demanded bits analysis may replace a full-width not with a any_extend (not (truncate X)) pattern. This patch looks through this kind of pattern in haveNoCommonBitsSet(). Of course, we can only do this if we only need negated bits in the non-extended part, as the other bits may now be arbitrary. For example, if we have haveNoCommonBitsSet(~X & Y, X) then ~X only needs to actually negate bits set in Y.

This is only a partial solution to the problem in that it allows add -> or conversion, but the resulting or doesn't get folded yet. (I guess that will involve exposing getBitwiseNotOperand() as a more general helper and using that in the relevant transform.)

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4702

Sorry I haven't checked this properly - but do we need to confirm the size of the pre-truncated value?

[nikic]

Check size of truncated value.

[nikic]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4702

I don't think this is strictly necessary, because we'd just fail the comparison between different-sized SDValues later on. However, I still think it makes sense to include the check from an API perspective, so that getBitwiseNotOperand always returns a value of the same size as its argument.

[nikic]

Slightly simplify condition -- directly compare VTs rather than sizes.

[RKSimon]

LGTM - cheers

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
   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))
+    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) &&
+      ExtArg.getOperand(0).getOpcode() == ISD::TRUNCATE &&
+      ExtArg.getOperand(0).getOperand(0).getScalarValueSizeInBits() ==
+          V.getScalarValueSizeInBits())
+    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 NotM, SDValue Other) {
-    if (isBitwiseNot(NotM, true)) {
-      SDValue NotOperand = NotM->getOperand(0);
+  auto MatchNoCommonBitsPattern = [&](SDValue Not, SDValue Mask,
+                                      SDValue Other) {
+    if (SDValue NotOperand = getBitwiseNotOperand(Not, Mask)) {
       if (Other == NotOperand)
         return true;
       if (Other->getOpcode() == ISD::AND)
         return NotOperand == Other->getOperand(0) ||
                NotOperand == Other->getOperand(1);
     }
     return false;
   };
   if (A->getOpcode() == ISD::AND)
-    return MatchNoCommonBitsPattern(A->getOperand(0), B) ||
-           MatchNoCommonBitsPattern(A->getOperand(1), B);
+    return MatchNoCommonBitsPattern(A->getOperand(0), A->getOperand(1), B) ||
+           MatchNoCommonBitsPattern(A->getOperand(1), A->getOperand(0), 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

 }
 
 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:    addq %rdi, %rax
+; CHECK-NEXT:    orq %rdi, %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) {

 }
 
 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:    addq %rdi, %rax
+; CHECK-NEXT:    orq %rdi, %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
 }

 }
 
 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:    addq %rdi, %rax
+; CHECK-NEXT:    orq %rdi, %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
 }