X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FConstantRange.cpp;h=4593eb9dff9e925a85063a174658ac77ed8c419e;hb=34e992da381bf8b1a9cbcc1bde0b117207809649;hp=a1b5247595b25281a4f887a2ed401f49fe1a88f9;hpb=b2f3e703bcde5833ff5910922f7a5313cc6b1c64;p=oota-llvm.git diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index a1b5247595b..4593eb9dff9 100644 --- a/lib/Support/ConstantRange.cpp +++ b/lib/Support/ConstantRange.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -22,350 +22,640 @@ //===----------------------------------------------------------------------===// #include "llvm/Support/ConstantRange.h" -#include "llvm/Constants.h" -#include "llvm/Instruction.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/Support/Streams.h" -#include using namespace llvm; -static ConstantInt *getMaxValue(const Type *Ty, bool isSigned = false) { - if (Ty->isIntegral()) { - if (isSigned) { - // Calculate 011111111111111... - unsigned TypeBits = Ty->getPrimitiveSizeInBits(); - int64_t Val = INT64_MAX; // All ones - Val >>= 64-TypeBits; // Shift out unwanted 1 bits... - return ConstantInt::get(Ty, Val); - } - return ConstantInt::getAllOnesValue(Ty); - } - return 0; -} - -// Static constructor to create the minimum constant for an integral type... -static ConstantInt *getMinValue(const Type *Ty, bool isSigned = false) { - if (Ty->isIntegral()) { - if (isSigned) { - // Calculate 1111111111000000000000 - unsigned TypeBits = Ty->getPrimitiveSizeInBits(); - int64_t Val = -1; // All ones - Val <<= TypeBits-1; // Shift over to the right spot - return ConstantInt::get(Ty, Val); - } - return ConstantInt::get(Ty, 0); - } - return 0; -} -static ConstantInt *Next(ConstantInt *CI) { - Constant *Result = ConstantExpr::getAdd(CI, - ConstantInt::get(CI->getType(), 1)); - return cast(Result); -} - -static bool LT(ConstantInt *A, ConstantInt *B, bool isSigned) { - Constant *C = ConstantExpr::getICmp( - (isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT), A, B); - assert(isa(C) && "Constant folding of integrals not impl??"); - return cast(C)->getZExtValue(); -} - -static bool LTE(ConstantInt *A, ConstantInt *B, bool isSigned) { - Constant *C = ConstantExpr::getICmp( - (isSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE), A, B); - assert(isa(C) && "Constant folding of integrals not impl??"); - return cast(C)->getZExtValue(); -} - -static bool GT(ConstantInt *A, ConstantInt *B, bool isSigned) { - return LT(B, A, isSigned); } - -static ConstantInt *Min(ConstantInt *A, ConstantInt *B, - bool isSigned) { - return LT(A, B, isSigned) ? A : B; -} -static ConstantInt *Max(ConstantInt *A, ConstantInt *B, - bool isSigned) { - return GT(A, B, isSigned) ? A : B; -} - /// Initialize a full (the default) or empty set for the specified type. /// -ConstantRange::ConstantRange(const Type *Ty, bool Full) { - assert(Ty->isIntegral() && - "Cannot make constant range of non-integral type!"); +ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { if (Full) - Lower = Upper = getMaxValue(Ty); + Lower = Upper = APInt::getMaxValue(BitWidth); else - Lower = Upper = getMinValue(Ty); + Lower = Upper = APInt::getMinValue(BitWidth); } /// Initialize a range to hold the single specified value. /// -ConstantRange::ConstantRange(Constant *V) - : Lower(cast(V)), Upper(Next(cast(V))) { } - -/// Initialize a range of values explicitly... this will assert out if -/// Lower==Upper and Lower != Min or Max for its type (or if the two constants -/// have different types) -/// -ConstantRange::ConstantRange(Constant *L, Constant *U) - : Lower(cast(L)), Upper(cast(U)) { - assert(Lower->getType() == Upper->getType() && - "Incompatible types for ConstantRange!"); - - // Make sure that if L & U are equal that they are either Min or Max... - assert((L != U || (L == getMaxValue(L->getType()) || - L == getMinValue(L->getType()))) - && "Lower == Upper, but they aren't min or max for type!"); +ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) {} + +ConstantRange::ConstantRange(const APInt &L, const APInt &U) : + Lower(L), Upper(U) { + assert(L.getBitWidth() == U.getBitWidth() && + "ConstantRange with unequal bit widths"); + 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, ConstantInt *C) { - switch (ICmpOpcode) { - default: assert(0 && "Invalid ICmp opcode to ConstantRange ctor!"); - case ICmpInst::ICMP_EQ: Lower = C; Upper = Next(C); return; - case ICmpInst::ICMP_NE: Upper = C; Lower = Next(C); return; - case ICmpInst::ICMP_ULT: - Lower = getMinValue(C->getType()); - Upper = C; - return; - case ICmpInst::ICMP_SLT: - Lower = getMinValue(C->getType(), true); - Upper = C; - return; - case ICmpInst::ICMP_UGT: - Lower = Next(C); - Upper = getMinValue(C->getType()); // Min = Next(Max) - return; - case ICmpInst::ICMP_SGT: - Lower = Next(C); - Upper = getMinValue(C->getType(), true); // Min = Next(Max) - return; - case ICmpInst::ICMP_ULE: - Lower = getMinValue(C->getType()); - Upper = Next(C); - return; - case ICmpInst::ICMP_SLE: - Lower = getMinValue(C->getType(), true); - Upper = Next(C); - return; - case ICmpInst::ICMP_UGE: - Lower = C; - Upper = getMinValue(C->getType()); // Min = Next(Max) - return; - case ICmpInst::ICMP_SGE: - Lower = C; - Upper = getMinValue(C->getType(), true); // Min = Next(Max) - return; +ConstantRange ConstantRange::makeICmpRegion(unsigned Pred, + const ConstantRange &CR) { + uint32_t W = CR.getBitWidth(); + switch (Pred) { + default: assert(!"Invalid ICmp predicate to makeICmpRegion()"); + case ICmpInst::ICMP_EQ: + return CR; + case ICmpInst::ICMP_NE: + if (CR.isSingleElement()) + return ConstantRange(CR.getUpper(), CR.getLower()); + return ConstantRange(W); + case ICmpInst::ICMP_ULT: + return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax()); + case ICmpInst::ICMP_SLT: + return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax()); + case ICmpInst::ICMP_ULE: { + APInt UMax(CR.getUnsignedMax()); + if (UMax.isMaxValue()) + return ConstantRange(W); + return ConstantRange(APInt::getMinValue(W), UMax + 1); + } + case ICmpInst::ICMP_SLE: { + APInt SMax(CR.getSignedMax()); + if (SMax.isMaxSignedValue() || (SMax+1).isMaxSignedValue()) + return ConstantRange(W); + return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); + } + case ICmpInst::ICMP_UGT: + return ConstantRange(CR.getUnsignedMin() + 1, APInt::getNullValue(W)); + case ICmpInst::ICMP_SGT: + return ConstantRange(CR.getSignedMin() + 1, + APInt::getSignedMinValue(W)); + case ICmpInst::ICMP_UGE: { + APInt UMin(CR.getUnsignedMin()); + if (UMin.isMinValue()) + return ConstantRange(W); + return ConstantRange(UMin, APInt::getNullValue(W)); + } + case ICmpInst::ICMP_SGE: { + APInt SMin(CR.getSignedMin()); + if (SMin.isMinSignedValue()) + return ConstantRange(W); + return ConstantRange(SMin, APInt::getSignedMinValue(W)); + } } } -/// getType - Return the LLVM data type of this range. -/// -const Type *ConstantRange::getType() const { return Lower->getType(); } - /// isFullSet - Return true if this set contains all of the elements possible /// for this data-type bool ConstantRange::isFullSet() const { - return Lower == Upper && Lower == getMaxValue(getType()); + return Lower == Upper && Lower.isMaxValue(); } /// isEmptySet - Return true if this set contains no members. /// bool ConstantRange::isEmptySet() const { - return Lower == Upper && Lower == getMinValue(getType()); + 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 { - return GT(Lower, Upper, isSigned); -} - -/// getSingleElement - If this set contains a single element, return it, -/// otherwise return null. -ConstantInt *ConstantRange::getSingleElement() const { - if (Upper == Next(Lower)) // Is it a single element range? - return Lower; - return 0; +bool ConstantRange::isWrappedSet() const { + return Lower.ugt(Upper); } /// getSetSize - Return the number of elements in this set. /// -uint64_t ConstantRange::getSetSize() const { - if (isEmptySet()) return 0; - if (getType() == Type::Int1Ty) { +APInt ConstantRange::getSetSize() const { + if (isEmptySet()) + return APInt(getBitWidth(), 0); + if (getBitWidth() == 1) { if (Lower != Upper) // One of T or F in the set... - return 1; - return 2; // Must be full set... + return APInt(2, 1); + return APInt(2, 2); // Must be full set... } // Simply subtract the bounds... - Constant *Result = ConstantExpr::getSub(Upper, Lower); - return cast(Result)->getZExtValue(); + return Upper - Lower; +} + +/// getUnsignedMax - Return the largest unsigned value contained in the +/// ConstantRange. +/// +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 (getLower().isNegative() == getUpper().isNegative()) + return SignedMax; + else + return getUpper() - 1; + } +} + +/// 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 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(ConstantInt *Val, bool isSigned) const { - if (Lower == Upper) { - if (isFullSet()) return true; - return false; +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); +} + +/// 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. +/// +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 (!isWrappedSet()) { + if (Other.isWrappedSet()) + return false; + + return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); } - if (!isWrappedSet(isSigned)) - return LTE(Lower, Val, isSigned) && LT(Val, Upper, isSigned); - return LTE(Lower, Val, isSigned) || LT(Val, Upper, isSigned); + if (!Other.isWrappedSet()) + return Other.getUpper().ule(Upper) || + Lower.ule(Other.getLower()); + + return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); } /// subtract - Subtract the specified constant from the endpoints of this /// constant range. -ConstantRange ConstantRange::subtract(ConstantInt *CI) const { - assert(CI->getType() == getType() && getType()->isIntegral() && - "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; - return ConstantRange(ConstantExpr::getSub(Lower, CI), - ConstantExpr::getSub(Upper, CI)); + if (Lower == Upper) + return *this; + 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. // -static ConstantRange intersect1Wrapped(const ConstantRange &LHS, - const ConstantRange &RHS, - bool isSigned) { - assert(LHS.isWrappedSet(isSigned) && !RHS.isWrappedSet(isSigned)); +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 (LT(RHS.getLower(), LHS.getUpper(), isSigned)) { + 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(RHS.getUpper(), LHS.getLower(), isSigned)) { + 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() < RHS.getSetSize()) + if (LHS.getSetSize().ult(RHS.getSetSize())) return LHS; else return RHS; } else { // No overlap on the right, just on the left. - return ConstantRange(RHS.getLower(), LHS.getUpper()); + 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 (GT(RHS.getUpper(), LHS.getLower(), isSigned)) { + if (RHS.Upper.ugt(LHS.Lower)) { // Simple overlap... - return ConstantRange(LHS.getLower(), RHS.getUpper()); + return ConstantRange(LHS.Lower, RHS.Upper); } else { // No overlap... - return ConstantRange(LHS.getType(), false); + return ConstantRange(LHS.getBitWidth(), false); } } } -/// intersect - 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!"); - // Handle common special cases - if (isEmptySet() || CR.isFullSet()) return *this; - if (isFullSet() || CR.isEmptySet()) return CR; - - if (!isWrappedSet(isSigned)) { - if (!CR.isWrappedSet(isSigned)) { - ConstantInt *L = Max(Lower, CR.Lower, isSigned); - ConstantInt *U = Min(Upper, CR.Upper, isSigned); - - if (LT(L, U, isSigned)) // If range isn't empty... - return ConstantRange(L, U); +/// 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 +/// set size that does so. Because there may be two intersections with the +/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). +ConstantRange ConstantRange::intersectWith(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.intersectWith(*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 ConstantRange(getType(), false); // Otherwise, return empty set - } else - return intersect1Wrapped(CR, *this, isSigned); - } else { // We know "this" is wrapped... - if (!CR.isWrappedSet(isSigned)) - return intersect1Wrapped(*this, CR, isSigned); - else { - // Both ranges are wrapped... - ConstantInt *L = Max(Lower, CR.Lower, isSigned); - ConstantInt *U = Min(Upper, CR.Upper, isSigned); - return ConstantRange(L, U); + return CR; + } else if (CR.Lower.ult(Lower)) { + if (CR.Upper.ule(Lower)) + return ConstantRange(getBitWidth(), false); + + return ConstantRange(Lower, CR.Upper); } + return CR; } - return *this; + + 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; } -/// union - Return the range that results from the union of this range with + +/// 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!"); + + if ( isFullSet() || CR.isEmptySet()) return *this; + if (CR.isFullSet() || isEmptySet()) return CR; + + if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); + + if (!isWrappedSet() && !CR.isWrappedSet()) { + if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { + // If the two ranges are disjoint, find the smaller gap and bridge it. + APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; + if (d1.ult(d2)) + return ConstantRange(Lower, CR.Upper); + else + return ConstantRange(CR.Lower, Upper); + } - assert(0 && "Range union not implemented yet!"); + APInt L = Lower, U = Upper; + if (CR.Lower.ult(L)) + L = CR.Lower; + if ((CR.Upper - 1).ugt(U - 1)) + U = CR.Upper; - return *this; + if (L == 0 && U == 0) + return ConstantRange(getBitWidth()); + + return ConstantRange(L, U); + } + + if (!CR.isWrappedSet()) { + // ------U L----- and ------U L----- : this + // L--U L--U : CR + if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) + return *this; + + // ------U L----- : this + // L---------U : CR + if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) + return ConstantRange(getBitWidth()); + + // ----U L---- : this + // L---U : CR + // + if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { + APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; + if (d1.ult(d2)) + return ConstantRange(Lower, CR.Upper); + else + return ConstantRange(CR.Lower, Upper); + } + + // ----U L----- : this + // L----U : CR + if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) + return ConstantRange(CR.Lower, Upper); + + // ------U L---- : this + // L-----U : CR + if (CR.Lower.ult(Upper) && CR.Upper.ult(Lower)) + return ConstantRange(Lower, CR.Upper); + } + + assert(isWrappedSet() && CR.isWrappedSet() && + "ConstantRange::unionWith missed wrapped union unwrapped case"); + + // ------U L---- and ------U L---- : this + // -U L----------- and ------------U L : CR + if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) + return ConstantRange(getBitWidth()); + + APInt L = Lower, U = Upper; + if (CR.Upper.ugt(U)) + U = CR.Upper; + if (CR.Lower.ult(L)) + L = CR.Lower; + + 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 = getLower()->getType()->getPrimitiveSizeInBits(); - assert(SrcTySize < Ty->getPrimitiveSizeInBits() && "Not a value extension"); - if (isFullSet()) { +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) - return ConstantRange(Constant::getNullValue(Ty), - ConstantInt::get(Ty, 1ULL << SrcTySize)); - } + return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize)); + + APInt L = Lower; L.zext(DstTySize); + APInt U = Upper; U.zext(DstTySize); + return ConstantRange(L, U); +} - Constant *Lower = getLower(); - Constant *Upper = getUpper(); +/// 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) + 1); + } - return ConstantRange(ConstantExpr::getZExt(Lower, Ty), - ConstantExpr::getZExt(Upper, Ty)); + 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 = getLower()->getType()->getPrimitiveSizeInBits(); - assert(SrcTySize > Ty->getPrimitiveSizeInBits() && "Not a value truncation"); - uint64_t Size = 1ULL << Ty->getPrimitiveSizeInBits(); - if (isFullSet() || getSetSize() >= Size) - return ConstantRange(getType()); +ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { + unsigned SrcTySize = getBitWidth(); + assert(SrcTySize > DstTySize && "Not a value truncation"); + APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize)); + if (isFullSet() || getSetSize().ugt(Size)) + return ConstantRange(DstTySize); + + APInt L = Lower; L.trunc(DstTySize); + APInt U = Upper; U.trunc(DstTySize); + return ConstantRange(L, U); +} + +/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The +/// value is zero extended, truncated, or left alone to make it that width. +ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { + unsigned SrcTySize = getBitWidth(); + if (SrcTySize > DstTySize) + return truncate(DstTySize); + else if (SrcTySize < DstTySize) + return zeroExtend(DstTySize); + else + return *this; +} + +/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The +/// value is sign extended, truncated, or left alone to make it that width. +ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { + unsigned SrcTySize = getBitWidth(); + if (SrcTySize > DstTySize) + return truncate(DstTySize); + else if (SrcTySize < DstTySize) + return signExtend(DstTySize); + else + return *this; +} + +ConstantRange +ConstantRange::add(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 { + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + if (isFullSet() || Other.isFullSet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + + APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); + APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); + APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); + APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); + + ConstantRange Result_zext = ConstantRange(this_min * Other_min, + this_max * Other_max + 1); + return Result_zext.truncate(getBitWidth()); +} + +ConstantRange +ConstantRange::smax(const ConstantRange &Other) const { + // X smax Y is: range(smax(X_smin, Y_smin), + // smax(X_smax, Y_smax)) + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); + APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; + if (NewU == NewL) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + return ConstantRange(NewL, NewU); +} + +ConstantRange +ConstantRange::umax(const ConstantRange &Other) const { + // X umax Y is: range(umax(X_umin, Y_umin), + // umax(X_umax, Y_umax)) + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); + APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; + if (NewU == NewL) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + return ConstantRange(NewL, NewU); +} + +ConstantRange +ConstantRange::udiv(const ConstantRange &RHS) const { + if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + if (RHS.isFullSet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + + APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); + + APInt RHS_umin = RHS.getUnsignedMin(); + if (RHS_umin == 0) { + // We want the lowest value in RHS excluding zero. Usually that would be 1 + // except for a range in the form of [X, 1) in which case it would be X. + if (RHS.getUpper() == 1) + RHS_umin = RHS.getLower(); + else + RHS_umin = APInt(getBitWidth(), 1); + } + + APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; + + // If the LHS is Full and the RHS is a wrapped interval containing 1 then + // this could occur. + if (Lower == Upper) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); - return ConstantRange( - ConstantExpr::getTrunc(getLower(), Ty), - ConstantExpr::getTrunc(getUpper(), Ty)); + return ConstantRange(Lower, Upper); +} + +ConstantRange +ConstantRange::shl(const ConstantRange &Amount) const { + if (isEmptySet()) + return *this; + + APInt min = getUnsignedMin() << Amount.getUnsignedMin(); + APInt max = getUnsignedMax() << Amount.getUnsignedMax(); + + // there's no overflow! + APInt Zeros(sizeof(unsigned)*8, getUnsignedMax().countLeadingZeros()); + if (Zeros.uge(Amount.getUnsignedMax())) + return ConstantRange(min, max); + + // FIXME: implement the other tricky cases + return ConstantRange(getBitWidth()); +} + +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; + + APInt min = getUnsignedMax().lshr(Amount.getUnsignedMin()); + APInt max = getUnsignedMin().lshr(Amount.getUnsignedMax()); + return ConstantRange(min, max); } /// print - Print out the bounds to a stream... /// -void ConstantRange::print(std::ostream &OS) const { - OS << "[" << *Lower << "," << *Upper << " )"; +void ConstantRange::print(raw_ostream &OS) const { + OS << "[" << Lower << "," << Upper << ")"; } /// dump - Allow printing from a debugger easily... /// void ConstantRange::dump() const { - print(cerr); + print(errs()); } + +