[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 ↗

(On Diff #38489)

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 ↗

(On Diff #38489)

Will fix and check in.

[sanjoy]

• address Nick's review

[nlewycky]

LGTM

llvm/trunk/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.

llvm/trunk/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);
 
-  // Use the high end of the ranges to find leading zeros.
-  unsigned MinLeadingZeros = BitWidth;
+  KnownZero.setAllBits();
+  KnownOne.setAllBits();
+
   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);
-  }
 
-  KnownZero = APInt::getHighBitsSet(BitWidth, MinLeadingZeros);
+    // The first CommonPrefixBits of all values in Range are equal.
+    unsigned CommonPrefixBits =
+        (Range.getUnsignedMax() ^ Range.getUnsignedMin()).countLeadingZeros();
+
+    APInt Mask = APInt::getHighBitsSet(BitWidth, CommonPrefixBits);
+    KnownOne &= Range.getUnsignedMax() & Mask;
+    KnownZero &= ~Range.getUnsignedMax() & Mask;
+  }
 }
 
 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,

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

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()) {
       if (LD->getExtensionType() == ISD::NON_EXTLOAD)
-        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);

llvm/trunk/test/Analysis/ValueTracking/known-bits-from-range-md.ll

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