From a1bccc58b83479dc744127a4a2c79f2f7d4f8862 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Wed, 11 Aug 2010 22:04:36 +0000 Subject: [PATCH] Clean up ConstantRange a bit: - remove ashr which never worked. - fix lshr and shl and add tests. - remove dead function "intersect1Wrapped". - add a new sub method to subtract ranges, with test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110861 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/ConstantRange.h | 35 ++++----- lib/Support/ConstantRange.cpp | 124 ++++++++++++-------------------- unittests/Support/ConstantRangeTest.cpp | 66 ++++++++++++++++- 3 files changed, 127 insertions(+), 98 deletions(-) diff --git a/include/llvm/Support/ConstantRange.h b/include/llvm/Support/ConstantRange.h index e32426130a..29086b2ac4 100644 --- a/include/llvm/Support/ConstantRange.h +++ b/include/llvm/Support/ConstantRange.h @@ -41,8 +41,6 @@ namespace llvm { /// class ConstantRange { APInt Lower, Upper; - static ConstantRange intersect1Wrapped(const ConstantRange &LHS, - const ConstantRange &RHS); public: /// Initialize a full (the default) or empty set for the specified bit width. @@ -196,40 +194,43 @@ public: ConstantRange sextOrTrunc(uint32_t BitWidth) const; /// add - Return a new range representing the possible values resulting - /// from an addition of a value in this range and a value in Other. + /// from an addition of a value in this range and a value in \p Other. ConstantRange add(const ConstantRange &Other) const; + /// sub - Return a new range representing the possible values resulting + /// from a subtraction of a value in this range and a value in \p Other. + ConstantRange sub(const ConstantRange &Other) const; + /// multiply - Return a new range representing the possible values resulting - /// from a multiplication of a value in this range and a value in Other. + /// from a multiplication of a value in this range and a value in \p Other. /// TODO: This isn't fully implemented yet. ConstantRange multiply(const ConstantRange &Other) const; /// smax - Return a new range representing the possible values resulting - /// from a signed maximum of a value in this range and a value in Other. + /// from a signed maximum of a value in this range and a value in \p Other. ConstantRange smax(const ConstantRange &Other) const; /// umax - Return a new range representing the possible values resulting - /// from an unsigned maximum of a value in this range and a value in Other. + /// from an unsigned maximum of a value in this range and a value in \p Other. ConstantRange umax(const ConstantRange &Other) const; /// udiv - Return a new range representing the possible values resulting - /// from an unsigned division of a value in this range and a value in Other. - /// TODO: This isn't fully implemented yet. + /// from an unsigned division of a value in this range and a value in + /// \p Other. ConstantRange udiv(const ConstantRange &Other) const; /// shl - Return a new range representing the possible values resulting - /// from a left shift of a value in this range by the Amount value. - ConstantRange shl(const ConstantRange &Amount) const; - - /// ashr - Return a new range representing the possible values resulting from - /// an arithmetic right shift of a value in this range by the Amount value. - ConstantRange ashr(const ConstantRange &Amount) const; + /// from a left shift of a value in this range by a value in \p Other. + /// TODO: This isn't fully implemented yet. + ConstantRange shl(const ConstantRange &Other) const; - /// shr - Return a new range representing the possible values resulting - /// from a logical right shift of a value in this range by the Amount value. - ConstantRange lshr(const ConstantRange &Amount) const; + /// lshr - Return a new range representing the possible values resulting + /// from a logical right shift of a value in this range and a value in + /// \p Other. + ConstantRange lshr(const ConstantRange &Other) const; /// inverse - Return a new range that is the logical not of the current set. + /// ConstantRange inverse() const; /// print - Print out the bounds to a stream... diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index d4e91a95fb..8ef3785f53 100644 --- a/lib/Support/ConstantRange.cpp +++ b/lib/Support/ConstantRange.cpp @@ -39,7 +39,7 @@ ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { /// Initialize a range to hold the single specified value. /// -ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) {} +ConstantRange::ConstantRange(const APInt &V) : Lower(V), Upper(V + 1) {} ConstantRange::ConstantRange(const APInt &L, const APInt &U) : Lower(L), Upper(U) { @@ -203,14 +203,12 @@ bool ConstantRange::contains(const APInt &V) const { } /// contains - Return true if the argument is a subset of this range. -/// Two equal set contain each other. The empty set is considered to be -/// contained by all other sets. +/// Two equal sets contain each other. The empty set contained by all other +/// sets. /// bool ConstantRange::contains(const ConstantRange &Other) const { - if (isFullSet()) return true; - if (Other.isFullSet()) return false; - if (Other.isEmptySet()) return true; - if (isEmptySet()) return false; + if (isFullSet() || Other.isEmptySet()) return true; + if (isEmptySet() || Other.isFullSet()) return false; if (!isWrappedSet()) { if (Other.isWrappedSet()) @@ -236,46 +234,6 @@ ConstantRange ConstantRange::subtract(const APInt &Val) const { return ConstantRange(Lower - Val, Upper - Val); } - -// intersect1Wrapped - This helper function is used to intersect two ranges when -// it is known that LHS is wrapped and RHS isn't. -// -ConstantRange -ConstantRange::intersect1Wrapped(const ConstantRange &LHS, - const ConstantRange &RHS) { - assert(LHS.isWrappedSet() && !RHS.isWrappedSet()); - - // Check to see if we overlap on the Left side of RHS... - // - if (RHS.Lower.ult(LHS.Upper)) { - // We do overlap on the left side of RHS, see if we overlap on the right of - // RHS... - if (RHS.Upper.ugt(LHS.Lower)) { - // Ok, the result overlaps on both the left and right sides. See if the - // resultant interval will be smaller if we wrap or not... - // - if (LHS.getSetSize().ult(RHS.getSetSize())) - return LHS; - else - return RHS; - - } else { - // No overlap on the right, just on the left. - return ConstantRange(RHS.Lower, LHS.Upper); - } - } else { - // We don't overlap on the left side of RHS, see if we overlap on the right - // of RHS... - if (RHS.Upper.ugt(LHS.Lower)) { - // Simple overlap... - return ConstantRange(LHS.Lower, RHS.Upper); - } else { - // No overlap... - return ConstantRange(LHS.getBitWidth(), false); - } - } -} - /// intersectWith - Return the range that results from the intersection of this /// range with another range. The resultant range is guaranteed to include all /// elements contained in both input ranges, and to have the smallest possible @@ -487,7 +445,7 @@ ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { assert(SrcTySize > DstTySize && "Not a value truncation"); APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize)); if (isFullSet() || getSetSize().ugt(Size)) - return ConstantRange(DstTySize); + return ConstantRange(DstTySize, /*isFullSet=*/true); APInt L = Lower; L.trunc(DstTySize); APInt U = Upper; U.trunc(DstTySize); @@ -540,6 +498,27 @@ ConstantRange::add(const ConstantRange &Other) const { } ConstantRange +ConstantRange::sub(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + if (isFullSet() || Other.isFullSet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + + APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); + APInt NewLower = getLower() - Other.getLower(); + APInt NewUpper = getUpper() - Other.getUpper() + 1; + if (NewLower == NewUpper) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + + ConstantRange X = ConstantRange(NewLower, NewUpper); + if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) + // We've wrapped, therefore, full set. + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + + return X; +} + +ConstantRange ConstantRange::multiply(const ConstantRange &Other) const { // TODO: If either operand is a single element and the multiply is known to // be non-wrapping, round the result min and max value to the appropriate @@ -617,49 +596,40 @@ ConstantRange::udiv(const ConstantRange &RHS) const { } ConstantRange -ConstantRange::shl(const ConstantRange &Amount) const { - if (isEmptySet()) - return *this; +ConstantRange::shl(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); - APInt min = getUnsignedMin() << Amount.getUnsignedMin(); - APInt max = getUnsignedMax() << Amount.getUnsignedMax(); + APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); + APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); // there's no overflow! APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); - if (Zeros.uge(Amount.getUnsignedMax())) - return ConstantRange(min, max); + if (Zeros.ugt(Other.getUnsignedMax())) + return ConstantRange(min, max + 1); // FIXME: implement the other tricky cases - return ConstantRange(getBitWidth()); + return ConstantRange(getBitWidth(), /*isFullSet=*/true); } ConstantRange -ConstantRange::ashr(const ConstantRange &Amount) const { - if (isEmptySet()) - return *this; - - APInt min = getUnsignedMax().ashr(Amount.getUnsignedMin()); - APInt max = getUnsignedMin().ashr(Amount.getUnsignedMax()); - return ConstantRange(min, max); -} - -ConstantRange -ConstantRange::lshr(const ConstantRange &Amount) const { - if (isEmptySet()) - return *this; +ConstantRange::lshr(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); - APInt min = getUnsignedMax().lshr(Amount.getUnsignedMin()); - APInt max = getUnsignedMin().lshr(Amount.getUnsignedMax()); - return ConstantRange(min, max); + APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); + APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); + if (min == max + 1) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + + return ConstantRange(min, max + 1); } ConstantRange ConstantRange::inverse() const { if (isFullSet()) { - return ConstantRange(APInt::getNullValue(Lower.getBitWidth()), - APInt::getNullValue(Lower.getBitWidth())); + return ConstantRange(getBitWidth(), /*isFullSet=*/false); } else if (isEmptySet()) { - return ConstantRange(APInt::getAllOnesValue(Lower.getBitWidth()), - APInt::getAllOnesValue(Lower.getBitWidth())); + return ConstantRange(getBitWidth(), /*isFullSet=*/true); } return ConstantRange(Upper, Lower); } @@ -680,5 +650,3 @@ void ConstantRange::print(raw_ostream &OS) const { void ConstantRange::dump() const { print(dbgs()); } - - diff --git a/unittests/Support/ConstantRangeTest.cpp b/unittests/Support/ConstantRangeTest.cpp index fc1f5b8d06..091ecd4aad 100644 --- a/unittests/Support/ConstantRangeTest.cpp +++ b/unittests/Support/ConstantRangeTest.cpp @@ -259,11 +259,31 @@ TEST_F(ConstantRangeTest, Add) { EXPECT_EQ(Empty.add(Wrap), Empty); EXPECT_EQ(Empty.add(APInt(16, 4)), Empty); EXPECT_EQ(Some.add(APInt(16, 4)), - ConstantRange(APInt(16, 0xe), APInt(16, 0xaae))); + ConstantRange(APInt(16, 0xe), APInt(16, 0xaae))); EXPECT_EQ(Wrap.add(APInt(16, 4)), - ConstantRange(APInt(16, 0xaae), APInt(16, 0xe))); + ConstantRange(APInt(16, 0xaae), APInt(16, 0xe))); EXPECT_EQ(One.add(APInt(16, 4)), - ConstantRange(APInt(16, 0xe))); + ConstantRange(APInt(16, 0xe))); +} + +TEST_F(ConstantRangeTest, Sub) { + EXPECT_EQ(Full.sub(APInt(16, 4)), Full); + EXPECT_EQ(Full.sub(Full), Full); + EXPECT_EQ(Full.sub(Empty), Empty); + EXPECT_EQ(Full.sub(One), Full); + EXPECT_EQ(Full.sub(Some), Full); + EXPECT_EQ(Full.sub(Wrap), Full); + EXPECT_EQ(Empty.sub(Empty), Empty); + EXPECT_EQ(Empty.sub(One), Empty); + EXPECT_EQ(Empty.sub(Some), Empty); + EXPECT_EQ(Empty.sub(Wrap), Empty); + EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty); + EXPECT_EQ(Some.sub(APInt(16, 4)), + ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6))); + EXPECT_EQ(Wrap.sub(APInt(16, 4)), + ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6))); + EXPECT_EQ(One.sub(APInt(16, 4)), + ConstantRange(APInt(16, 0x6))); } TEST_F(ConstantRangeTest, Multiply) { @@ -351,4 +371,44 @@ TEST_F(ConstantRangeTest, UDiv) { EXPECT_EQ(Wrap.udiv(Wrap), Full); } +TEST_F(ConstantRangeTest, Shl) { + EXPECT_EQ(Full.shl(Full), Full); + EXPECT_EQ(Full.shl(Empty), Empty); + EXPECT_EQ(Full.shl(One), Full); // TODO: [0, (-1 << 0xa) + 1) + EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1) + EXPECT_EQ(Full.shl(Wrap), Full); + EXPECT_EQ(Empty.shl(Empty), Empty); + EXPECT_EQ(Empty.shl(One), Empty); + EXPECT_EQ(Empty.shl(Some), Empty); + EXPECT_EQ(Empty.shl(Wrap), Empty); + EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa), + APInt(16, (0xa << 0xa) + 1))); + EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0) + EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1) + EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01) + EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1) + EXPECT_EQ(Wrap.shl(Wrap), Full); +} + +TEST_F(ConstantRangeTest, Lshr) { + EXPECT_EQ(Full.lshr(Full), Full); + EXPECT_EQ(Full.lshr(Empty), Empty); + EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0), + APInt(16, (0xffff >> 0xa) + 1))); + EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0), + APInt(16, (0xffff >> 0xa) + 1))); + EXPECT_EQ(Full.lshr(Wrap), Full); + EXPECT_EQ(Empty.lshr(Empty), Empty); + EXPECT_EQ(Empty.lshr(One), Empty); + EXPECT_EQ(Empty.lshr(Some), Empty); + EXPECT_EQ(Empty.lshr(Wrap), Empty); + EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0))); + EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0))); + EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); + EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0), + APInt(16, (0xaaa >> 0xa) + 1))); + EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); + EXPECT_EQ(Wrap.lshr(Wrap), Full); +} + } // anonymous namespace -- 2.11.4.GIT