[ValueTracking] Use !range metadata more aggressively in KnownBits

[sanjoy]

Summary

Teach computeKnownBitsFromRangeMetadata to use !range metadata more
aggressively.

[jingyue]

test/Analysis/ValueTracking/sign-bit-from-md.ll

10

ret i1 true

I'd be slightly more verbose to filter out unwanted cases such as and i8 true, ....

[sanjoy]

test/Analysis/ValueTracking/sign-bit-from-md.ll

10

Will fix and check in.

[sanjoy]

• address Nick's review

[nlewycky]

LGTM

include/llvm/Analysis/ValueTracking.h

namespace llvm {
   /// for all of the elements in the vector.
   void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
                         const DataLayout &DL, unsigned Depth = 0,
                         AssumptionCache *AC = nullptr,
                         const Instruction *CxtI = nullptr,
                         const DominatorTree *DT = nullptr);
   /// Compute known bits from the range metadata.
   /// \p KnownZero the set of bits that are known to be zero
+  /// \p KnownOne the set of bits that are known to be one
   void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
-                                         APInt &KnownZero);
+                                         APInt &KnownZero, APInt &KnownOne);
   /// Return true if LHS and RHS have no common bits set.
   bool haveNoCommonBitsSet(Value *LHS, Value *RHS, const DataLayout &DL,
                            AssumptionCache *AC = nullptr,
                            const Instruction *CxtI = nullptr,
                            const DominatorTree *DT = nullptr);
 
   /// ComputeSignBit - Determine whether the sign bit is known to be zero or
   /// one.  Convenience wrapper around computeKnownBits.

lib/Analysis/ValueTracking.cpp

static void computeKnownBitsMul(Value *Op0, Value *Op1, bool NSW,
   // whatever we like here.
   if (isKnownNonNegative && !KnownOne.isNegative())
     KnownZero.setBit(BitWidth - 1);
   else if (isKnownNegative && !KnownZero.isNegative())
     KnownOne.setBit(BitWidth - 1);
 }
 
 void llvm::computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
-                                             APInt &KnownZero) {
+                                             APInt &KnownZero,
+                                             APInt &KnownOne) {
   unsigned BitWidth = KnownZero.getBitWidth();
   unsigned NumRanges = Ranges.getNumOperands() / 2;
   assert(NumRanges >= 1);
 
+  bool AlwaysNegative = true;
+
   // Use the high end of the ranges to find leading zeros.
   unsigned MinLeadingZeros = BitWidth;
   for (unsigned i = 0; i < NumRanges; ++i) {
     ConstantInt *Lower =
         mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
     ConstantInt *Upper =
         mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
     ConstantRange Range(Lower->getValue(), Upper->getValue());
     unsigned LeadingZeros = Range.getUnsignedMax().countLeadingZeros();
     MinLeadingZeros = std::min(LeadingZeros, MinLeadingZeros);
+    AlwaysNegative &= Range.getSignedMax().isNegative();
   }
 
   KnownZero = APInt::getHighBitsSet(BitWidth, MinLeadingZeros);
+  if (AlwaysNegative) {
+    assert(MinLeadingZeros == 0 && "We found at least one negative number!");
+    KnownOne = APInt::getHighBitsSet(BitWidth, 1);
+  }
 }
 
 static bool isEphemeralValueOf(Instruction *I, const Value *E) {
   SmallVector<const Value *, 16> WorkSet(1, I);
   SmallPtrSet<const Value *, 32> Visited;
   SmallPtrSet<const Value *, 16> EphValues;
 
   // The instruction defining an assumption's condition itself is always
static void computeKnownBitsFromOperator(Operator *I, APInt &KnownZero,
                                          unsigned Depth, const Query &Q) {
   unsigned BitWidth = KnownZero.getBitWidth();
 
   APInt KnownZero2(KnownZero), KnownOne2(KnownOne);
   switch (I->getOpcode()) {
   default: break;
   case Instruction::Load:
     if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range))
-      computeKnownBitsFromRangeMetadata(*MD, KnownZero);
+      computeKnownBitsFromRangeMetadata(*MD, KnownZero, KnownOne);
     break;
   case Instruction::And: {
     // If either the LHS or the RHS are Zero, the result is zero.
     computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q);
     computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q);
 
     // Output known-1 bits are only known if set in both the LHS & RHS.
     KnownOne &= KnownOne2;
if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) {
           break;
       }
     }
     break;
   }
   case Instruction::Call:
   case Instruction::Invoke:
     if (MDNode *MD = cast<Instruction>(I)->getMetadata(LLVMContext::MD_range))
-      computeKnownBitsFromRangeMetadata(*MD, KnownZero);
+      computeKnownBitsFromRangeMetadata(*MD, KnownZero, KnownOne);
     // If a range metadata is attached to this IntrinsicInst, intersect the
     // explicit range specified by the metadata and the implicit range of
     // the intrinsic.
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
       switch (II->getIntrinsicID()) {
       default: break;
       case Intrinsic::bswap:
         computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL,

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
   case ISD::LOAD: {
     LoadSDNode *LD = cast<LoadSDNode>(Op);
     // If this is a ZEXTLoad and we are looking at the loaded value.
     if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
       EVT VT = LD->getMemoryVT();
       unsigned MemBits = VT.getScalarType().getSizeInBits();
       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
     } else if (const MDNode *Ranges = LD->getRanges()) {
-      computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
+      computeKnownBitsFromRangeMetadata(*Ranges, KnownZero, KnownOne);
     }
     break;
   }
   case ISD::ZERO_EXTEND: {
     EVT InVT = Op.getOperand(0).getValueType();
     unsigned InBits = InVT.getScalarType().getSizeInBits();
     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
     KnownZero = KnownZero.trunc(InBits);

test/Analysis/ValueTracking/sign-bit-from-md.ll

+; RUN: opt -S -instsimplify < %s | FileCheck %s
+
+define i1 @f(i8* %ptr) {
+; CHECK-LABEL: @f(
+ entry:
+  %val = load i8, i8* %ptr, !range !0
+  %and = and i8 %val, 128
+  %is.eq = icmp eq i8 %and, 128
+  ret i1 %is.eq
+; CHECK: true
+}
+
+!0 = !{i8 -50, i8 0}