diff --git a/llvm/include/llvm/IR/ConstantRange.h b/llvm/include/llvm/IR/ConstantRange.h --- a/llvm/include/llvm/IR/ConstantRange.h +++ b/llvm/include/llvm/IR/ConstantRange.h @@ -92,6 +92,9 @@ /// unsigned domain. static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned); + /// Get the known bits valid for the given range. + KnownBits toKnownBits() const; + /// Produce the smallest range such that all values that may satisfy the given /// predicate with any value contained within Other is contained in the /// returned range. Formally, this returns a superset of diff --git a/llvm/include/llvm/Support/KnownBits.h b/llvm/include/llvm/Support/KnownBits.h --- a/llvm/include/llvm/Support/KnownBits.h +++ b/llvm/include/llvm/Support/KnownBits.h @@ -35,6 +35,12 @@ /// Create a known bits object of BitWidth bits initialized to unknown. KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {} + /// Return true if this KnownBits is equal to another KnownBits. + bool operator==(const KnownBits &CR) const { + return Zero == CR.Zero && One == CR.One; + } + bool operator!=(const KnownBits &KB) const { return !operator==(KB); } + /// Get the bit width of this value. unsigned getBitWidth() const { assert(Zero.getBitWidth() == One.getBitWidth() && @@ -209,8 +215,19 @@ /// Compute known bits resulting from adding LHS and RHS. static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS); + + /// Print out the bounds to a stream. + void print(raw_ostream &OS) const; + + /// Allow printing from a debugger easily. + void dump() const; }; +inline raw_ostream &operator<<(raw_ostream &OS, const KnownBits &KB) { + KB.print(OS); + return OS; +} + } // end namespace llvm #endif diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp --- a/llvm/lib/IR/ConstantRange.cpp +++ b/llvm/lib/IR/ConstantRange.cpp @@ -74,6 +74,42 @@ return ConstantRange(Lower, Upper + 1); } +KnownBits ConstantRange::toKnownBits() const { + KnownBits Known(getBitWidth()); + + // If the range has no/all members, or has a wrap, then "no known bits" + // is as precise as we can get. + if (isEmptySet() || isFullSet() || isSignWrappedSet() || isWrappedSet()) + return Known; // No bits known. + + // We know all bits of a constant. + if (const APInt *SingleElement = getSingleElement()) { + Known.One = *SingleElement; + Known.Zero = ~*SingleElement; + return Known; + } + + Known.One = getUnsignedMin(); + Known.Zero = ~getUnsignedMin(); + + auto HighestTransientBit = APIntOps::GetMostSignificantDifferentBit( + getUnsignedMin(), getUnsignedMax()); + assert( + HighestTransientBit.hasValue() && + "Since the constant range does not consist of a single constant, there " + "must be some some different bits, so we must have found the threshold."); + assert((getBitWidth() - (1 + *HighestTransientBit)) >= 1 && + "If we get here, we know *at least* the (common) sign bit."); + + // We need to claim to not know all low bits up to and including + // HighestTransientBit. But since `getUnsignedMin()` was used as baseline, + // that bit itself isn't known to be One, so we don't need to unset it as One. + Known.One.clearLowBits(*HighestTransientBit); + Known.Zero.clearLowBits(1 + *HighestTransientBit); + + return Known; +} + ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &CR) { if (CR.isEmptySet()) diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp --- a/llvm/lib/Support/KnownBits.cpp +++ b/llvm/lib/Support/KnownBits.cpp @@ -12,6 +12,8 @@ //===----------------------------------------------------------------------===// #include "llvm/Support/KnownBits.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -81,3 +83,11 @@ return KnownOut; } + +void KnownBits::print(raw_ostream &OS) const { + OS << "Known-zero: " << Zero << ", Known-one: " << One; +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void KnownBits::dump() const { print(dbgs()); } +#endif diff --git a/llvm/unittests/IR/ConstantRangeTest.cpp b/llvm/unittests/IR/ConstantRangeTest.cpp --- a/llvm/unittests/IR/ConstantRangeTest.cpp +++ b/llvm/unittests/IR/ConstantRangeTest.cpp @@ -2121,6 +2121,7 @@ if (Num.sgt(MaxSigned)) MaxSigned = Num; } + // KB -> CR conversion is precisely identical to brute-force approach. ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1); ConstantRange SignedCR(MinSigned, MaxSigned + 1); EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false)); @@ -2129,6 +2130,39 @@ } } +TEST_F(ConstantRangeTest, ToKnownBitsExhaustive) { + unsigned Bits = 6; + KnownBits Known(Bits); + EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) { + if (CR.isEmptySet()) + return; + + // Acquire precise KnownBits knowledge for a given constant range via the + // brute-force approach. That results in conservatively-larger value range. + Known.Zero.setAllBits(); + Known.One.setAllBits(); + ForeachNumInConstantRange(CR, [&](const APInt &N) { + Known.Zero &= ~N; + Known.One &= N; + }); + ASSERT_FALSE(Known.hasConflict()); + // But not every value found in known bits is found in constant range! + + // If we produce constant range from known bits, it may be conservatively + // larger than the reference constant range. The reference constant range + // must be contained within the new constant range. + ConstantRange UnsignedCRFromKB(ConstantRange::fromKnownBits(Known, false)); + ConstantRange SignedCRFromKB(ConstantRange::fromKnownBits(Known, true)); + EXPECT_EQ(SignedCRFromKB, UnsignedCRFromKB); + EXPECT_TRUE(UnsignedCRFromKB.contains(CR)); + + // If we distill constant range into known bits, the result is a precise + // match to the known-bits we got via brute-force. + KnownBits KBFromCR(CR.toKnownBits()); + EXPECT_EQ(KBFromCR, Known); + }); +} + TEST_F(ConstantRangeTest, Negative) { // All elements in an empty set (of which there are none) are both negative // and non-negative. Empty & full sets checked explicitly for clarity, but