[TargetLowering] add special-case for demanded bits analysis of 'not'

[spatel]

Summary

We treat bitwise 'not' as a special operation and try not to reduce its all-ones mask. Presumably, this is because a 'not' may be cheaper than a generic 'xor' or it may get folded into another logic op if the target has those. However, if we can remove a logic instruction by changing the xor's constant mask value, I think that's always a win.

Note that the IR version of SimplifyDemandedBits() does not treat 'not' as a special-case currently (although that's marked with a FIXME). So if you run this IR through -instcombine first, you should get the same result. But I'm hoping to add a different backend transform that will expose this problem, so I need to solve this first.

llvm/trunk/lib/CodeGen/SelectionDAG/TargetLowering.cpp

case ISD::BUILD_VECTOR:
     }
     return false;   // Don't fall through, will infinitely loop.
   case ISD::AND:
     // If the RHS is a constant, check to see if the LHS would be zero without
     // using the bits from the RHS.  Below, we use knowledge about the RHS to
     // simplify the LHS, here we're using information from the LHS to simplify
     // the RHS.
     if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
+      SDValue Op0 = Op.getOperand(0);
       APInt LHSZero, LHSOne;
       // Do not increment Depth here; that can cause an infinite loop.
-      TLO.DAG.computeKnownBits(Op.getOperand(0), LHSZero, LHSOne, Depth);
+      TLO.DAG.computeKnownBits(Op0, LHSZero, LHSOne, Depth);
       // If the LHS already has zeros where RHSC does, this and is dead.
       if ((LHSZero & NewMask) == (~RHSC->getAPIntValue() & NewMask))
-        return TLO.CombineTo(Op, Op.getOperand(0));
+        return TLO.CombineTo(Op, Op0);
+
       // If any of the set bits in the RHS are known zero on the LHS, shrink
       // the constant.
       if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & NewMask))
         return true;
+
+      // Bitwise-not (xor X, -1) is a special case: we don't usually shrink its
+      // constant, but if this 'and' is only clearing bits that were just set by
+      // the xor, then this 'and' can be eliminated by shrinking the mask of
+      // the xor. For example, for a 32-bit X:
+      // and (xor (srl X, 31), -1), 1 --> xor (srl X, 31), 1
+      if (isBitwiseNot(Op0) && Op0.hasOneUse() &&
+          LHSOne == ~RHSC->getAPIntValue()) {
+        SDValue Xor = TLO.DAG.getNode(ISD::XOR, dl, Op.getValueType(),
+                                      Op0.getOperand(0), Op.getOperand(1));
+        return TLO.CombineTo(Op, Xor);
+      }
     }
 
     if (SimplifyDemandedBits(Op.getOperand(1), NewMask, KnownZero,
                              KnownOne, TLO, Depth+1))
       return true;
     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
     if (SimplifyDemandedBits(Op.getOperand(0), ~KnownZero & NewMask,
                              KnownZero2, KnownOne2, TLO, Depth+1))
if ((NewMask & (KnownZero|KnownOne)) == NewMask) { // all known on one side
         SDValue ANDC = TLO.DAG.getConstant(~KnownOne & NewMask, dl, VT);
         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, dl, VT,
                                                  Op.getOperand(0), ANDC));
       }
     }
 
     // If the RHS is a constant, see if we can simplify it.
     // for XOR, we prefer to force bits to 1 if they will make a -1.
-    // if we can't force bits, try to shrink constant
+    // If we can't force bits, try to shrink the constant.
     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
       APInt Expanded = C->getAPIntValue() | (~NewMask);
-      // if we can expand it to have all bits set, do it
+      // If we can expand it to have all bits set, do it.
       if (Expanded.isAllOnesValue()) {
         if (Expanded != C->getAPIntValue()) {
           EVT VT = Op.getValueType();
           SDValue New = TLO.DAG.getNode(Op.getOpcode(), dl,VT, Op.getOperand(0),
                                         TLO.DAG.getConstant(Expanded, dl, VT));
           return TLO.CombineTo(Op, New);
         }
-        // if it already has all the bits set, nothing to change
+        // If it already has all the bits set, nothing to change
         // but don't shrink either!
       } else if (TLO.ShrinkDemandedConstant(Op, NewMask)) {
         return true;
       }
     }
 
     KnownZero = KnownZeroOut;
     KnownOne  = KnownOneOut;

llvm/trunk/test/CodeGen/X86/not-and-simplify.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=-bmi | FileCheck %s --check-prefix=ALL --check-prefix=NO_BMI
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+bmi | FileCheck %s --check-prefix=ALL --check-prefix=BMI
 
 ; Clear high bits via shift, set them with xor (not), then mask them off.
 
 define i32 @shrink_xor_constant1(i32 %x) {
-; NO_BMI-LABEL: shrink_xor_constant1:
-; NO_BMI:       # BB#0:
-; NO_BMI-NEXT:    shrl $31, %edi
-; NO_BMI-NEXT:    notl %edi
-; NO_BMI-NEXT:    andl $1, %edi
-; NO_BMI-NEXT:    movl %edi, %eax
-; NO_BMI-NEXT:    retq
-;
-; BMI-LABEL: shrink_xor_constant1:
-; BMI:       # BB#0:
-; BMI-NEXT:    shrl $31, %edi
-; BMI-NEXT:    movl $1, %eax
-; BMI-NEXT:    andnl %eax, %edi, %eax
-; BMI-NEXT:    retq
+; ALL-LABEL: shrink_xor_constant1:
+; ALL:       # BB#0:
+; ALL-NEXT:    shrl $31, %edi
+; ALL-NEXT:    xorl $1, %edi
+; ALL-NEXT:    movl %edi, %eax
+; ALL-NEXT:    retq
 ;
   %sh = lshr i32 %x, 31
   %not = xor i32 %sh, -1
   %and = and i32 %not, 1
   ret i32 %and
 }
 
 ; Clear low bits via shift, set them with xor (not), then mask them off.
 
 define i8 @shrink_xor_constant2(i8 %x) {
 ; ALL-LABEL: shrink_xor_constant2:
 ; ALL:       # BB#0:
 ; ALL-NEXT:    shlb $5, %dil
-; ALL-NEXT:    notb %dil
-; ALL-NEXT:    andb $-32, %dil
+; ALL-NEXT:    xorb $-32, %dil
 ; ALL-NEXT:    movl %edi, %eax
 ; ALL-NEXT:    retq
 ;
   %sh = shl i8 %x, 5
   %not = xor i8 %sh, -1
   %and = and i8 %not, 224 ; 0xE0
   ret i8 %and
 }