X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FConstantRange.cpp;h=fdfe28aaa95c88289d6cb830422f66f46f271e8a;hb=e15c2db9935eee66a8008f1bd09882aff2ed3aae;hp=c000c73e8b2c9011b323f9fad47c9fb932f58a68;hpb=dc5c1597014fa5c47c94db2b9fd424d2266053db;p=oota-llvm.git diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index c000c73e8b2..fdfe28aaa95 100644 --- a/lib/Support/ConstantRange.cpp +++ b/lib/Support/ConstantRange.cpp @@ -22,21 +22,14 @@ //===----------------------------------------------------------------------===// #include "llvm/Support/ConstantRange.h" -#include "llvm/Constants.h" -#include "llvm/Instruction.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/DerivedTypes.h" #include "llvm/Support/Streams.h" #include using namespace llvm; /// Initialize a full (the default) or empty set for the specified type. /// -ConstantRange::ConstantRange(const Type *Ty, bool Full) : - Lower(cast(Ty)->getBitWidth(), 0), - Upper(cast(Ty)->getBitWidth(), 0) { - uint32_t BitWidth = cast(Ty)->getBitWidth(); +ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) : + Lower(BitWidth, 0), Upper(BitWidth, 0) { if (Full) Lower = Upper = APInt::getMaxValue(BitWidth); else @@ -51,145 +44,127 @@ ConstantRange::ConstantRange(const APInt &L, const APInt &U) : Lower(L), Upper(U) { assert(L.getBitWidth() == U.getBitWidth() && "ConstantRange with unequal bit widths"); - uint32_t BitWidth = L.getBitWidth(); - assert((L != U || (L == APInt::getMaxValue(BitWidth) || - L == APInt::getMinValue(BitWidth))) && + assert((L != U || (L.isMaxValue() || L.isMinValue())) && "Lower == Upper, but they aren't min or max value!"); } -/// Initialize a set of values that all satisfy the condition with C. -/// -ConstantRange::ConstantRange(unsigned short ICmpOpcode, const APInt &C) - : Lower(C.getBitWidth(), 0), Upper(C.getBitWidth(), 0) { - uint32_t BitWidth = C.getBitWidth(); - switch (ICmpOpcode) { - default: assert(0 && "Invalid ICmp opcode to ConstantRange ctor!"); - case ICmpInst::ICMP_EQ: Lower = C; Upper = C + 1; return; - case ICmpInst::ICMP_NE: Upper = C; Lower = C + 1; return; - case ICmpInst::ICMP_ULT: - Lower = APInt::getMinValue(BitWidth); - Upper = C; - return; - case ICmpInst::ICMP_SLT: - Lower = APInt::getSignedMinValue(BitWidth); - Upper = C; - return; - case ICmpInst::ICMP_UGT: - Lower = C + 1; - Upper = APInt::getMinValue(BitWidth); // Min = Next(Max) - return; - case ICmpInst::ICMP_SGT: - Lower = C + 1; - Upper = APInt::getSignedMinValue(BitWidth); // Min = Next(Max) - return; - case ICmpInst::ICMP_ULE: - Lower = APInt::getMinValue(BitWidth); - Upper = C + 1; - return; - case ICmpInst::ICMP_SLE: - Lower = APInt::getSignedMinValue(BitWidth); - Upper = C + 1; - return; - case ICmpInst::ICMP_UGE: - Lower = C; - Upper = APInt::getMinValue(BitWidth); // Min = Next(Max) - return; - case ICmpInst::ICMP_SGE: - Lower = C; - Upper = APInt::getSignedMinValue(BitWidth); // Min = Next(Max) - return; - } -} - -/// getType - Return the LLVM data type of this range. -/// -const Type *ConstantRange::getType() const { - return IntegerType::get(Lower.getBitWidth()); -} - -ConstantInt *ConstantRange::getLower() const { - return ConstantInt::get(getType(), Lower); -} - -ConstantInt *ConstantRange::getUpper() const { - return ConstantInt::get(getType(), Upper); -} - /// isFullSet - Return true if this set contains all of the elements possible /// for this data-type bool ConstantRange::isFullSet() const { - return Lower == Upper && Lower == APInt::getMaxValue(Lower.getBitWidth()); + return Lower == Upper && Lower.isMaxValue(); } /// isEmptySet - Return true if this set contains no members. /// bool ConstantRange::isEmptySet() const { - return Lower == Upper && Lower == APInt::getMinValue(Lower.getBitWidth()); + return Lower == Upper && Lower.isMinValue(); } /// isWrappedSet - Return true if this set wraps around the top of the range, /// for example: [100, 8) /// -bool ConstantRange::isWrappedSet(bool isSigned) const { - if (isSigned) - return Lower.sgt(Upper); +bool ConstantRange::isWrappedSet() const { return Lower.ugt(Upper); } -/// getSingleElement - If this set contains a single element, return it, -/// otherwise return null. -ConstantInt *ConstantRange::getSingleElement() const { - if (Upper == Lower + 1) // Is it a single element range? - return ConstantInt::get(getType(), Lower); - return 0; -} - /// getSetSize - Return the number of elements in this set. /// APInt ConstantRange::getSetSize() const { if (isEmptySet()) - return APInt(Lower.getBitWidth(), 0); - if (getType() == Type::Int1Ty) { + return APInt(getBitWidth(), 0); + if (getBitWidth() == 1) { if (Lower != Upper) // One of T or F in the set... - return APInt(Lower.getBitWidth(), 1); - return APInt(Lower.getBitWidth(), 2); // Must be full set... + return APInt(2, 1); + return APInt(2, 2); // Must be full set... } // Simply subtract the bounds... return Upper - Lower; } -/// contains - Return true if the specified value is in the set. +/// getUnsignedMax - Return the largest unsigned value contained in the +/// ConstantRange. /// -bool ConstantRange::contains(ConstantInt *Val, bool isSigned) const { - if (Lower == Upper) { - if (isFullSet()) - return true; - return false; +APInt ConstantRange::getUnsignedMax() const { + if (isFullSet() || isWrappedSet()) + return APInt::getMaxValue(getBitWidth()); + else + return getUpper() - 1; +} + +/// getUnsignedMin - Return the smallest unsigned value contained in the +/// ConstantRange. +/// +APInt ConstantRange::getUnsignedMin() const { + if (isFullSet() || (isWrappedSet() && getUpper() != 0)) + return APInt::getMinValue(getBitWidth()); + else + return getLower(); +} + +/// getSignedMax - Return the largest signed value contained in the +/// ConstantRange. +/// +APInt ConstantRange::getSignedMax() const { + APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); + if (!isWrappedSet()) { + if (getLower().sle(getUpper() - 1)) + return getUpper() - 1; + else + return SignedMax; + } else { + if ((getUpper() - 1).slt(getLower())) { + if (getLower() != SignedMax) + return SignedMax; + else + return getUpper() - 1; + } else { + return getUpper() - 1; + } } +} - const APInt &V = Val->getValue(); - if (!isWrappedSet(isSigned)) - if (isSigned) - return Lower.sle(V) && V.slt(Upper); +/// getSignedMin - Return the smallest signed value contained in the +/// ConstantRange. +/// +APInt ConstantRange::getSignedMin() const { + APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); + if (!isWrappedSet()) { + if (getLower().sle(getUpper() - 1)) + return getLower(); else - return Lower.ule(V) && V.ult(Upper); - if (isSigned) - return Lower.sle(V) || V.slt(Upper); + return SignedMin; + } else { + if ((getUpper() - 1).slt(getLower())) { + if (getUpper() != SignedMin) + return SignedMin; + else + return getLower(); + } else { + return getLower(); + } + } +} + +/// contains - Return true if the specified value is in the set. +/// +bool ConstantRange::contains(const APInt &V) const { + if (Lower == Upper) + return isFullSet(); + + if (!isWrappedSet()) + return Lower.ule(V) && V.ult(Upper); else return Lower.ule(V) || V.ult(Upper); } /// subtract - Subtract the specified constant from the endpoints of this /// constant range. -ConstantRange ConstantRange::subtract(ConstantInt *CI) const { - assert(CI->getType() == getType() && - "Cannot subtract from different type range or non-integer!"); +ConstantRange ConstantRange::subtract(const APInt &Val) const { + assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); // If the set is empty or full, don't modify the endpoints. if (Lower == Upper) return *this; - - const APInt &Val = CI->getValue(); return ConstantRange(Lower - Val, Upper - Val); } @@ -199,17 +174,15 @@ ConstantRange ConstantRange::subtract(ConstantInt *CI) const { // ConstantRange ConstantRange::intersect1Wrapped(const ConstantRange &LHS, - const ConstantRange &RHS, bool isSigned) { - assert(LHS.isWrappedSet(isSigned) && !RHS.isWrappedSet(isSigned)); + const ConstantRange &RHS) { + assert(LHS.isWrappedSet() && !RHS.isWrappedSet()); // Check to see if we overlap on the Left side of RHS... // - bool LT = (isSigned ? RHS.Lower.slt(LHS.Upper) : RHS.Lower.ult(LHS.Upper)); - bool GT = (isSigned ? RHS.Upper.sgt(LHS.Lower) : RHS.Upper.ugt(LHS.Lower)); - if (LT) { + 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 (GT) { + 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... // @@ -225,12 +198,12 @@ ConstantRange::intersect1Wrapped(const ConstantRange &LHS, } else { // We don't overlap on the left side of RHS, see if we overlap on the right // of RHS... - if (GT) { + if (RHS.Upper.ugt(LHS.Lower)) { // Simple overlap... return ConstantRange(LHS.Lower, RHS.Upper); } else { // No overlap... - return ConstantRange(LHS.getType(), false); + return ConstantRange(LHS.getBitWidth(), false); } } } @@ -238,63 +211,212 @@ ConstantRange::intersect1Wrapped(const ConstantRange &LHS, /// intersectWith - Return the range that results from the intersection of this /// range with another range. /// -ConstantRange ConstantRange::intersectWith(const ConstantRange &CR, - bool isSigned) const { - assert(getType() == CR.getType() && "ConstantRange types don't agree!"); +ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { + assert(getBitWidth() == CR.getBitWidth() && + "ConstantRange types don't agree!"); // Handle common special cases if (isEmptySet() || CR.isFullSet()) return *this; if (isFullSet() || CR.isEmptySet()) return CR; - if (!isWrappedSet(isSigned)) { - if (!CR.isWrappedSet(isSigned)) { + if (!isWrappedSet()) { + if (!CR.isWrappedSet()) { using namespace APIntOps; - APInt L = isSigned ? smax(Lower, CR.Lower) : umax(Lower, CR.Lower); - APInt U = isSigned ? smin(Upper, CR.Upper) : umin(Upper, CR.Upper); + APInt L = umax(Lower, CR.Lower); + APInt U = umin(Upper, CR.Upper); - if (isSigned ? L.slt(U) : L.ult(U)) // If range isn't empty... + if (L.ult(U)) // If range isn't empty... return ConstantRange(L, U); else - return ConstantRange(getType(), false); // Otherwise, return empty set + return ConstantRange(getBitWidth(), false);// Otherwise, empty set } else - return intersect1Wrapped(CR, *this, isSigned); + return intersect1Wrapped(CR, *this); } else { // We know "this" is wrapped... - if (!CR.isWrappedSet(isSigned)) - return intersect1Wrapped(*this, CR, isSigned); + if (!CR.isWrappedSet()) + return intersect1Wrapped(*this, CR); else { // Both ranges are wrapped... using namespace APIntOps; - APInt L = isSigned ? smax(Lower, CR.Lower) : umax(Lower, CR.Lower); - APInt U = isSigned ? smin(Upper, CR.Upper) : umin(Upper, CR.Upper); + APInt L = umax(Lower, CR.Lower); + APInt U = umin(Upper, CR.Upper); return ConstantRange(L, U); } } return *this; } +/// maximalIntersectWith - 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 set size that does so. Because there may be two +/// intersections with the same set size, A.maximalIntersectWith(B) might not +/// be equal to B.maximalIntersect(A). +ConstantRange ConstantRange::maximalIntersectWith(const ConstantRange &CR) const { + assert(getBitWidth() == CR.getBitWidth() && + "ConstantRange types don't agree!"); + + // Handle common cases. + if ( isEmptySet() || CR.isFullSet()) return *this; + if (CR.isEmptySet() || isFullSet()) return CR; + + if (!isWrappedSet() && CR.isWrappedSet()) + return CR.maximalIntersectWith(*this); + + if (!isWrappedSet() && !CR.isWrappedSet()) { + if (Lower.ult(CR.Lower)) { + if (Upper.ule(CR.Lower)) + return ConstantRange(getBitWidth(), false); + + if (Upper.ult(CR.Upper)) + return ConstantRange(CR.Lower, Upper); + + return CR; + } else { + if (Upper.ult(CR.Upper)) + return *this; + + if (Lower.ult(CR.Upper)) + return ConstantRange(Lower, CR.Upper); + + return ConstantRange(getBitWidth(), false); + } + } + + if (isWrappedSet() && !CR.isWrappedSet()) { + if (CR.Lower.ult(Upper)) { + if (CR.Upper.ult(Upper)) + return CR; + + if (CR.Upper.ult(Lower)) + return ConstantRange(CR.Lower, Upper); + + if (getSetSize().ult(CR.getSetSize())) + return *this; + else + return CR; + } else if (CR.Lower.ult(Lower)) { + if (CR.Upper.ule(Lower)) + return ConstantRange(getBitWidth(), false); + + return ConstantRange(Lower, CR.Upper); + } + return CR; + } + + if (CR.Upper.ult(Upper)) { + if (CR.Lower.ult(Upper)) { + if (getSetSize().ult(CR.getSetSize())) + return *this; + else + return CR; + } + + if (CR.Lower.ult(Lower)) + return ConstantRange(Lower, CR.Upper); + + return CR; + } else if (CR.Upper.ult(Lower)) { + if (CR.Lower.ult(Lower)) + return *this; + + return ConstantRange(CR.Lower, Upper); + } + if (getSetSize().ult(CR.getSetSize())) + return *this; + else + return CR; +} + + /// unionWith - Return the range that results from the union of this range with /// another range. The resultant range is guaranteed to include the elements of -/// both sets, but may contain more. For example, [3, 9) union [12,15) is [3, -/// 15), which includes 9, 10, and 11, which were not included in either set -/// before. +/// both sets, but may contain more. For example, [3, 9) union [12,15) is +/// [3, 15), which includes 9, 10, and 11, which were not included in either +/// set before. /// -ConstantRange ConstantRange::unionWith(const ConstantRange &CR, - bool isSigned) const { - assert(getType() == CR.getType() && "ConstantRange types don't agree!"); +ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { + assert(getBitWidth() == CR.getBitWidth() && + "ConstantRange types don't agree!"); - assert(0 && "Range union not implemented yet!"); + if ( isFullSet() || CR.isEmptySet()) return *this; + if (CR.isFullSet() || isEmptySet()) return CR; - return *this; + if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); + + APInt L = Lower, U = Upper; + + if (!isWrappedSet() && !CR.isWrappedSet()) { + if (CR.Lower.ult(L)) + L = CR.Lower; + + if (CR.Upper.ugt(U)) + U = CR.Upper; + } + + if (isWrappedSet() && !CR.isWrappedSet()) { + if ((CR.Lower.ult(Upper) && CR.Upper.ult(Upper)) || + (CR.Lower.ugt(Lower) && CR.Upper.ugt(Lower))) { + return *this; + } + + if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) { + return ConstantRange(getBitWidth()); + } + + if (CR.Lower.ule(Upper) && CR.Upper.ule(Lower)) { + APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper; + if (d1.ult(d2)) { + U = CR.Upper; + } else { + L = CR.Upper; + } + } + + if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) { + APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; + if (d1.ult(d2)) { + U = CR.Lower + 1; + } else { + L = CR.Upper - 1; + } + } + + if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) { + APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower; + + if (d1.ult(d2)) { + U = CR.Lower + 1; + } else { + L = CR.Lower; + } + } + } + + if (isWrappedSet() && CR.isWrappedSet()) { + if (Lower.ult(CR.Upper) || CR.Lower.ult(Upper)) + return ConstantRange(getBitWidth()); + + if (CR.Upper.ugt(U)) { + U = CR.Upper; + } + + if (CR.Lower.ult(L)) { + L = CR.Lower; + } + + if (L == U) return ConstantRange(getBitWidth()); + } + + return ConstantRange(L, U); } /// zeroExtend - Return a new range in the specified integer type, which must /// be strictly larger than the current type. The returned range will /// correspond to the possible range of values as if the source range had been /// zero extended. -ConstantRange ConstantRange::zeroExtend(const Type *Ty) const { - unsigned SrcTySize = Lower.getBitWidth(); - unsigned DstTySize = Ty->getPrimitiveSizeInBits(); +ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { + unsigned SrcTySize = getBitWidth(); assert(SrcTySize < DstTySize && "Not a value extension"); if (isFullSet()) // Change a source full set into [0, 1 << 8*numbytes) @@ -305,17 +427,33 @@ ConstantRange ConstantRange::zeroExtend(const Type *Ty) const { return ConstantRange(L, U); } +/// signExtend - Return a new range in the specified integer type, which must +/// be strictly larger than the current type. The returned range will +/// correspond to the possible range of values as if the source range had been +/// sign extended. +ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { + unsigned SrcTySize = getBitWidth(); + assert(SrcTySize < DstTySize && "Not a value extension"); + if (isFullSet()) { + return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), + APInt::getLowBitsSet(DstTySize, SrcTySize-1)); + } + + APInt L = Lower; L.sext(DstTySize); + APInt U = Upper; U.sext(DstTySize); + return ConstantRange(L, U); +} + /// truncate - Return a new range in the specified integer type, which must be /// strictly smaller than the current type. The returned range will /// correspond to the possible range of values as if the source range had been /// truncated to the specified type. -ConstantRange ConstantRange::truncate(const Type *Ty) const { - unsigned SrcTySize = Lower.getBitWidth(); - unsigned DstTySize = Ty->getPrimitiveSizeInBits(); +ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { + unsigned SrcTySize = getBitWidth(); assert(SrcTySize > DstTySize && "Not a value truncation"); - APInt Size = APInt::getMaxValue(DstTySize).zext(SrcTySize); + APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize)); if (isFullSet() || getSetSize().ugt(Size)) - return ConstantRange(getType()); + return ConstantRange(DstTySize); APInt L = Lower; L.trunc(DstTySize); APInt U = Upper; U.trunc(DstTySize);