[KnownBits] Add methods for determining if the known bits represent a negative/nonnegative number and add methods for changing the negative/nonnegative state

[craig.topper]

Summary

This patch adds isNegative, isNonNegative for querying whether the sign bit is known. It also adds makeNegative and makeNonNegative for controlling the sign bit.

[RKSimon]

LGTM

llvm/trunk/include/llvm/Support/KnownBits.h

 
 #ifndef LLVM_SUPPORT_KNOWNBITS_H
 #define LLVM_SUPPORT_KNOWNBITS_H
 
 #include "llvm/ADT/APInt.h"
 
 namespace llvm {
 
-// For now this is a simple wrapper around two APInts.
+// Struct for tracking the known zeros and ones of a value.
 struct KnownBits {
   APInt Zero;
   APInt One;
 
   // Default construct Zero and One.
   KnownBits() {}
 
   /// Create a known bits object of BitWidth bits initialized to unknown.
   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
 
   /// Get the bit width of this value.
   unsigned getBitWidth() const {
     assert(Zero.getBitWidth() == One.getBitWidth() &&
            "Zero and One should have the same width!");
     return Zero.getBitWidth();
   }
+
+  /// Returns true if this value is known to be negative.
+  bool isNegative() const { return One.isSignBitSet(); }
+
+  /// Returns true if this value is known to be non-negative.
+  bool isNonNegative() const { return Zero.isSignBitSet(); }
+
+  /// Make this value negative.
+  void makeNegative() {
+    assert(!isNonNegative() && "Can't make a non-negative value negative");
+    One.setSignBit();
+  }
+
+  /// Make this value negative.
+  void makeNonNegative() {
+    assert(!isNegative() && "Can't make a negative value non-negative");
+    Zero.setSignBit();
+  }
 };
 
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Analysis/ValueTracking.cpp

static void computeKnownBitsAddSub(bool Add, const Value *Op0, const Value *Op1,
   KnownOut.Zero = ~PossibleSumOne & Known;
   KnownOut.One = PossibleSumOne & Known;
 
   // Are we still trying to solve for the sign bit?
   if (!Known.isSignBitSet()) {
     if (NSW) {
       // Adding two non-negative numbers, or subtracting a negative number from
       // a non-negative one, can't wrap into negative.
-      if (LHSKnown.Zero.isSignBitSet() && Known2.Zero.isSignBitSet())
-        KnownOut.Zero.setSignBit();
+      if (LHSKnown.isNonNegative() && Known2.isNonNegative())
+        KnownOut.makeNonNegative();
       // Adding two negative numbers, or subtracting a non-negative number from
       // a negative one, can't wrap into non-negative.
-      else if (LHSKnown.One.isSignBitSet() && Known2.One.isSignBitSet())
-        KnownOut.One.setSignBit();
+      else if (LHSKnown.isNegative() && Known2.isNegative())
+        KnownOut.makeNegative();
     }
   }
 }
 
 static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW,
                                 KnownBits &Known, KnownBits &Known2,
                                 unsigned Depth, const Query &Q) {
   unsigned BitWidth = Known.getBitWidth();
   computeKnownBits(Op1, Known, Depth + 1, Q);
   computeKnownBits(Op0, Known2, Depth + 1, Q);
 
   bool isKnownNegative = false;
   bool isKnownNonNegative = false;
   // If the multiplication is known not to overflow, compute the sign bit.
   if (NSW) {
     if (Op0 == Op1) {
       // The product of a number with itself is non-negative.
       isKnownNonNegative = true;
     } else {
-      bool isKnownNonNegativeOp1 = Known.Zero.isSignBitSet();
-      bool isKnownNonNegativeOp0 = Known2.Zero.isSignBitSet();
-      bool isKnownNegativeOp1 = Known.One.isSignBitSet();
-      bool isKnownNegativeOp0 = Known2.One.isSignBitSet();
+      bool isKnownNonNegativeOp1 = Known.isNonNegative();
+      bool isKnownNonNegativeOp0 = Known2.isNonNegative();
+      bool isKnownNegativeOp1 = Known.isNegative();
+      bool isKnownNegativeOp0 = Known2.isNegative();
       // The product of two numbers with the same sign is non-negative.
       isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) ||
         (isKnownNonNegativeOp1 && isKnownNonNegativeOp0);
       // The product of a negative number and a non-negative number is either
       // negative or zero.
       if (!isKnownNonNegative)
         isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 &&
                            isKnownNonZero(Op0, Depth, Q)) ||
static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW,
   Known.Zero.setLowBits(TrailZ);
   Known.Zero.setHighBits(LeadZ);
 
   // Only make use of no-wrap flags if we failed to compute the sign bit
   // directly.  This matters if the multiplication always overflows, in
   // which case we prefer to follow the result of the direct computation,
   // though as the program is invoking undefined behaviour we can choose
   // whatever we like here.
-  if (isKnownNonNegative && !Known.One.isSignBitSet())
-    Known.Zero.setSignBit();
-  else if (isKnownNegative && !Known.Zero.isSignBitSet())
-    Known.One.setSignBit();
+  if (isKnownNonNegative && !Known.isNegative())
+    Known.makeNonNegative();
+  else if (isKnownNegative && !Known.isNonNegative())
+    Known.makeNegative();
 }
 
 void llvm::computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
                                              KnownBits &Known) {
   unsigned BitWidth = Known.getBitWidth();
   unsigned NumRanges = Ranges.getNumOperands() / 2;
   assert(NumRanges >= 1);
 
// assume(~(v >> c) = a)
       Known.One  |= RHSKnown.Zero << C->getZExtValue();
     // assume(v >=_s c) where c is non-negative
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_SGE &&
                isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       KnownBits RHSKnown(BitWidth);
       computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
 
-      if (RHSKnown.Zero.isSignBitSet()) {
+      if (RHSKnown.isNonNegative()) {
         // We know that the sign bit is zero.
-        Known.Zero.setSignBit();
+        Known.makeNonNegative();
       }
     // assume(v >_s c) where c is at least -1.
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_SGT &&
                isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       KnownBits RHSKnown(BitWidth);
       computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
 
-      if (RHSKnown.One.isAllOnesValue() || RHSKnown.Zero.isSignBitSet()) {
+      if (RHSKnown.One.isAllOnesValue() || RHSKnown.isNonNegative()) {
         // We know that the sign bit is zero.
-        Known.Zero.setSignBit();
+        Known.makeNonNegative();
       }
     // assume(v <=_s c) where c is negative
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_SLE &&
                isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       KnownBits RHSKnown(BitWidth);
       computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
 
-      if (RHSKnown.One.isSignBitSet()) {
+      if (RHSKnown.isNegative()) {
         // We know that the sign bit is one.
-        Known.One.setSignBit();
+        Known.makeNegative();
       }
     // assume(v <_s c) where c is non-positive
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_SLT &&
                isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       KnownBits RHSKnown(BitWidth);
       computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
 
-      if (RHSKnown.Zero.isAllOnesValue() || RHSKnown.One.isSignBitSet()) {
+      if (RHSKnown.Zero.isAllOnesValue() || RHSKnown.isNegative()) {
         // We know that the sign bit is one.
-        Known.One.setSignBit();
+        Known.makeNegative();
       }
     // assume(v <=_u c)
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_ULE &&
                isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       KnownBits RHSKnown(BitWidth);
       computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
 
if (SelectPatternResult::isMinOrMax(SPF)) {
       computeKnownBits(I->getOperand(2), Known, Depth + 1, Q);
       computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
     }
 
     unsigned MaxHighOnes = 0;
     unsigned MaxHighZeros = 0;
     if (SPF == SPF_SMAX) {
       // If both sides are negative, the result is negative.
-      if (Known.One.isSignBitSet() && Known2.One.isSignBitSet())
+      if (Known.isNegative() && Known2.isNegative())
         // We can derive a lower bound on the result by taking the max of the
         // leading one bits.
         MaxHighOnes = std::max(Known.One.countLeadingOnes(),
                                Known2.One.countLeadingOnes());
       // If either side is non-negative, the result is non-negative.
-      else if (Known.Zero.isSignBitSet() || Known2.Zero.isSignBitSet())
+      else if (Known.isNonNegative() || Known2.isNonNegative())
         MaxHighZeros = 1;
     } else if (SPF == SPF_SMIN) {
       // If both sides are non-negative, the result is non-negative.
-      if (Known.Zero.isSignBitSet() && Known2.Zero.isSignBitSet())
+      if (Known.isNonNegative() && Known2.isNonNegative())
         // We can derive an upper bound on the result by taking the max of the
         // leading zero bits.
         MaxHighZeros = std::max(Known.Zero.countLeadingOnes(),
                                 Known2.Zero.countLeadingOnes());
       // If either side is negative, the result is negative.
-      else if (Known.One.isSignBitSet() || Known2.One.isSignBitSet())
+      else if (Known.isNegative() || Known2.isNegative())
         MaxHighOnes = 1;
     } else if (SPF == SPF_UMAX) {
       // We can derive a lower bound on the result by taking the max of the
       // leading one bits.
       MaxHighOnes =
           std::max(Known.One.countLeadingOnes(), Known2.One.countLeadingOnes());
     } else if (SPF == SPF_UMIN) {
       // We can derive an upper bound on the result by taking the max of the
if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
         computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
 
         // The low bits of the first operand are unchanged by the srem.
         Known.Zero = Known2.Zero & LowBits;
         Known.One = Known2.One & LowBits;
 
         // If the first operand is non-negative or has all low bits zero, then
         // the upper bits are all zero.
-        if (Known2.Zero.isSignBitSet() || LowBits.isSubsetOf(Known2.Zero))
+        if (Known2.isNonNegative() || LowBits.isSubsetOf(Known2.Zero))
           Known.Zero |= ~LowBits;
 
         // If the first operand is negative and not all low bits are zero, then
         // the upper bits are all one.
-        if (Known2.One.isSignBitSet() && LowBits.intersects(Known2.One))
+        if (Known2.isNegative() && LowBits.intersects(Known2.One))
           Known.One |= ~LowBits;
 
         assert((Known.Zero & Known.One) == 0 && "Bits known to be one AND zero?");
         break;
       }
     }
 
     // The sign bit is the LHS's sign bit, except when the result of the
     // remainder is zero.
     computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
     // If it's known zero, our sign bit is also zero.
-    if (Known2.Zero.isSignBitSet())
-      Known.Zero.setSignBit();
+    if (Known2.isNonNegative())
+      Known.makeNonNegative();
 
     break;
   case Instruction::URem: {
     if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
       const APInt &RA = Rem->getValue();
       if (RA.isPowerOf2()) {
         APInt LowBits = (RA - 1);
         computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
if (P->getNumIncomingValues() == 2) {
             // or poison value regardless of the number of times we execute the
             // add in phi recurrence. If initial value is negative and we are
             // adding a negative number with nsw, the result can only be
             // negative or poison value. Similar arguments apply to sub and mul.
             //
             // (add non-negative, non-negative) --> non-negative
             // (add negative, negative) --> negative
             if (Opcode == Instruction::Add) {
-              if (Known2.Zero.isSignBitSet() && Known3.Zero.isSignBitSet())
-                Known.Zero.setSignBit();
-              else if (Known2.One.isSignBitSet() && Known3.One.isSignBitSet())
-                Known.One.setSignBit();
+              if (Known2.isNonNegative() && Known3.isNonNegative())
+                Known.makeNonNegative();
+              else if (Known2.isNegative() && Known3.isNegative())
+                Known.makeNegative();
             }
 
             // (sub nsw non-negative, negative) --> non-negative
             // (sub nsw negative, non-negative) --> negative
             else if (Opcode == Instruction::Sub && LL == I) {
-              if (Known2.Zero.isSignBitSet() && Known3.One.isSignBitSet())
-                Known.Zero.setSignBit();
-              else if (Known2.One.isSignBitSet() && Known3.Zero.isSignBitSet())
-                Known.One.setSignBit();
+              if (Known2.isNonNegative() && Known3.isNegative())
+                Known.makeNonNegative();
+              else if (Known2.isNegative() && Known3.isNonNegative())
+                Known.makeNegative();
             }
 
             // (mul nsw non-negative, non-negative) --> non-negative
-            else if (Opcode == Instruction::Mul && Known2.Zero.isSignBitSet() &&
-                     Known3.Zero.isSignBitSet())
-              Known.Zero.setSignBit();
+            else if (Opcode == Instruction::Mul && Known2.isNonNegative() &&
+                     Known3.isNonNegative())
+              Known.makeNonNegative();
           }
 
           break;
         }
       }
     }
 
     // Unreachable blocks may have zero-operand PHI nodes.
void ComputeSignBit(const Value *V, bool &KnownZero, bool &KnownOne,
   unsigned BitWidth = getBitWidth(V->getType(), Q.DL);
   if (!BitWidth) {
     KnownZero = false;
     KnownOne = false;
     return;
   }
   KnownBits Bits(BitWidth);
   computeKnownBits(V, Bits, Depth, Q);
-  KnownOne = Bits.One.isSignBitSet();
-  KnownZero = Bits.Zero.isSignBitSet();
+  KnownOne = Bits.isNegative();
+  KnownZero = Bits.isNonNegative();
 }
 
 /// Return true if the given value is known to have exactly one
 /// bit set when defined. For vectors return true if every element is known to
 /// be a power of two when defined. Supports values with integer or pointer
 /// types and vectors of integers.
 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
                             const Query &Q) {
if (const auto *CRHS = dyn_cast<Constant>(U->getOperand(1)))
 
         // If the input is known to be 0 or 1, the output is 0/-1, which is all
         // sign bits set.
         if ((Known.Zero | 1).isAllOnesValue())
           return TyBits;
 
         // If we are subtracting one from a positive number, there is no carry
         // out of the result.
-        if (Known.Zero.isSignBitSet())
+        if (Known.isNonNegative())
           return Tmp;
       }
 
     Tmp2 = ComputeNumSignBits(U->getOperand(1), Depth + 1, Q);
     if (Tmp2 == 1) return 1;
     return std::min(Tmp, Tmp2)-1;
 
   case Instruction::Sub:
     Tmp2 = ComputeNumSignBits(U->getOperand(1), Depth + 1, Q);
     if (Tmp2 == 1) return 1;
 
     // Handle NEG.
     if (const auto *CLHS = dyn_cast<Constant>(U->getOperand(0)))
       if (CLHS->isNullValue()) {
         KnownBits Known(TyBits);
         computeKnownBits(U->getOperand(1), Known, Depth + 1, Q);
         // If the input is known to be 0 or 1, the output is 0/-1, which is all
         // sign bits set.
         if ((Known.Zero | 1).isAllOnesValue())
           return TyBits;
 
         // If the input is known to be positive (the sign bit is known clear),
         // the output of the NEG has the same number of sign bits as the input.
-        if (Known.Zero.isSignBitSet())
+        if (Known.isNonNegative())
           return Tmp2;
 
         // Otherwise, we treat this like a SUB.
       }
 
     // Sub can have at most one carry bit.  Thus we know that the output
     // is, at worst, one more bit than the inputs.
     Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth,
   if (unsigned VecSignBits = computeNumSignBitsVectorConstant(V, TyBits))
     return VecSignBits;
 
   KnownBits Known(TyBits);
   computeKnownBits(V, Known, Depth, Q);
 
   // If we know that the sign bit is either zero or one, determine the number of
   // identical bits in the top of the input value.
-  if (Known.Zero.isSignBitSet())
+  if (Known.isNonNegative())
     return std::max(FirstAnswer, Known.Zero.countLeadingOnes());
 
-  if (Known.One.isSignBitSet())
+  if (Known.isNegative())
     return std::max(FirstAnswer, Known.One.countLeadingOnes());
 
   // computeKnownBits gave us no extra information about the top bits.
   return FirstAnswer;
 }
 
 /// This function computes the integer multiple of Base that equals V.
 /// If successful, it returns true and returns the multiple in

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

case ISD::BSWAP: {
     Known.Zero = Known2.Zero.byteSwap();
     Known.One = Known2.One.byteSwap();
     break;
   }
   case ISD::ABS: {
     computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1);
 
     // If the source's MSB is zero then we know the rest of the bits already.
-    if (Known2.Zero[BitWidth - 1]) {
+    if (Known2.isNonNegative()) {
       Known.Zero = Known2.Zero;
       Known.One = Known2.One;
       break;
     }
 
     // We only know that the absolute values's MSB will be zero iff there is
     // a set bit that isn't the sign bit (otherwise it could be INT_MIN).
     Known2.One.clearSignBit();
if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
 
         // If the input is known to be 0 or 1, the output is 0/-1, which is all
         // sign bits set.
         if ((Known.Zero | 1).isAllOnesValue())
           return VTBits;
 
         // If we are subtracting one from a positive number, there is no carry
         // out of the result.
-        if (Known.Zero.isNegative())
+        if (Known.isNonNegative())
           return Tmp;
       }
 
     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
     if (Tmp2 == 1) return 1;
     return std::min(Tmp, Tmp2)-1;
 
   case ISD::SUB:
     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
     if (Tmp2 == 1) return 1;
 
     // Handle NEG.
     if (ConstantSDNode *CLHS = isConstOrConstSplat(Op.getOperand(0)))
       if (CLHS->isNullValue()) {
         KnownBits Known;
         computeKnownBits(Op.getOperand(1), Known, Depth+1);
         // If the input is known to be 0 or 1, the output is 0/-1, which is all
         // sign bits set.
         if ((Known.Zero | 1).isAllOnesValue())
           return VTBits;
 
         // If the input is known to be positive (the sign bit is known clear),
         // the output of the NEG has the same number of sign bits as the input.
-        if (Known.Zero.isNegative())
+        if (Known.isNonNegative())
           return Tmp2;
 
         // Otherwise, we treat this like a SUB.
       }
 
     // Sub can have at most one carry bit.  Thus we know that the output
     // is, at worst, one more bit than the inputs.
     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
   }
 
   // Finally, if we can prove that the top bits of the result are 0's or 1's,
   // use this information.
   KnownBits Known;
   computeKnownBits(Op, Known, DemandedElts, Depth);
 
   APInt Mask;
-  if (Known.Zero.isNegative()) {        // sign bit is 0
+  if (Known.isNonNegative()) {        // sign bit is 0
     Mask = Known.Zero;
-  } else if (Known.One.isNegative()) {  // sign bit is 1;
+  } else if (Known.isNegative()) {  // sign bit is 1;
     Mask = Known.One;
   } else {
     // Nothing known.
     return FirstAnswer;
   }
 
   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
   // the number of identical bits in the top of the input value.

llvm/trunk/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
           return I;
 
         // The low bits of LHS are unchanged by the srem.
         Known.Zero = LHSKnown.Zero & LowBits;
         Known.One = LHSKnown.One & LowBits;
 
         // If LHS is non-negative or has all low bits zero, then the upper bits
         // are all zero.
-        if (LHSKnown.Zero.isSignBitSet() || LowBits.isSubsetOf(LHSKnown.Zero))
+        if (LHSKnown.isNonNegative() || LowBits.isSubsetOf(LHSKnown.Zero))
           Known.Zero |= ~LowBits;
 
         // If LHS is negative and not all low bits are zero, then the upper bits
         // are all one.
-        if (LHSKnown.One.isSignBitSet() && LowBits.intersects(LHSKnown.One))
+        if (LHSKnown.isNegative() && LowBits.intersects(LHSKnown.One))
           Known.One |= ~LowBits;
 
         assert(!(Known.Zero & Known.One) && "Bits known to be one AND zero?");
         break;
       }
     }
 
     // The sign bit is the LHS's sign bit, except when the result of the
     // remainder is zero.
     if (DemandedMask.isSignBitSet()) {
       computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI);
       // If it's known zero, our sign bit is also zero.
-      if (LHSKnown.Zero.isSignBitSet())
-        Known.Zero.setSignBit();
+      if (LHSKnown.isNonNegative())
+        Known.makeNonNegative();
     }
     break;
   case Instruction::URem: {
     KnownBits Known2(BitWidth);
     APInt AllOnes = APInt::getAllOnesValue(BitWidth);
     if (SimplifyDemandedBits(I, 0, AllOnes, Known2, Depth + 1) ||
         SimplifyDemandedBits(I, 1, AllOnes, Known2, Depth + 1))
       return I;