From 7f9ef4bb514d5a28637789d8f397dadd4344dc1b Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Wed, 11 Aug 2010 22:04:36 +0000 Subject: 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 --- lib/Support/ConstantRange.cpp | 124 ++++++++++++++++-------------------------- 1 file changed, 46 insertions(+), 78 deletions(-) (limited to 'lib/Support/ConstantRange.cpp') diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index d4e91a9..8ef3785 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()); } - - -- cgit v1.1