X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FConstantRange.cpp;h=5c5895026b67343c8fb14b2766d783d28c3b661d;hb=a3fb49cd851cd3b593fc653dc3ba4434c2e1232f;hp=beb61754fc7468f163bd6bfda0951064fbd986a5;hpb=193c2d886f96944fa5e4ecb9298a829a84bb8127;p=oota-llvm.git diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index beb61754fc7..5c5895026b6 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. // //===----------------------------------------------------------------------===// // @@ -21,312 +21,711 @@ // //===----------------------------------------------------------------------===// +#include "llvm/IR/InstrTypes.h" #include "llvm/Support/ConstantRange.h" -#include "llvm/Constants.h" -#include "llvm/Instruction.h" -#include "llvm/Type.h" -#include - +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; -static ConstantIntegral *Next(ConstantIntegral *CI) { - if (ConstantBool *CB = dyn_cast(CI)) - return ConstantBool::get(!CB->getValue()); - - Constant *Result = ConstantExpr::getAdd(CI, - ConstantInt::get(CI->getType(), 1)); - return cast(Result); -} - -static bool LT(ConstantIntegral *A, ConstantIntegral *B) { - Constant *C = ConstantExpr::getSetLT(A, B); - assert(isa(C) && "Constant folding of integrals not impl??"); - return cast(C)->getValue(); -} - -static bool LTE(ConstantIntegral *A, ConstantIntegral *B) { - Constant *C = ConstantExpr::getSetLE(A, B); - assert(isa(C) && "Constant folding of integrals not impl??"); - return cast(C)->getValue(); -} - -static bool GT(ConstantIntegral *A, ConstantIntegral *B) { return LT(B, A); } - -static ConstantIntegral *Min(ConstantIntegral *A, ConstantIntegral *B) { - return LT(A, B) ? A : B; -} -static ConstantIntegral *Max(ConstantIntegral *A, ConstantIntegral *B) { - return GT(A, B) ? 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 = ConstantIntegral::getMaxValue(Ty); + Lower = Upper = APInt::getMaxValue(BitWidth); else - Lower = Upper = ConstantIntegral::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))) { +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 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 == ConstantIntegral::getMaxValue(L->getType()) || - L == ConstantIntegral::getMinValue(L->getType()))) && - "Lower == Upper, but they aren't min or max for type!"); -} - -/// Initialize a set of values that all satisfy the condition with C. -/// -ConstantRange::ConstantRange(unsigned SetCCOpcode, ConstantIntegral *C) { - switch (SetCCOpcode) { - default: assert(0 && "Invalid SetCC opcode to ConstantRange ctor!"); - case Instruction::SetEQ: Lower = C; Upper = Next(C); return; - case Instruction::SetNE: Upper = C; Lower = Next(C); return; - case Instruction::SetLT: - Lower = ConstantIntegral::getMinValue(C->getType()); - Upper = C; - return; - case Instruction::SetGT: - Lower = Next(C); - Upper = ConstantIntegral::getMinValue(C->getType()); // Min = Next(Max) - return; - case Instruction::SetLE: - Lower = ConstantIntegral::getMinValue(C->getType()); - Upper = Next(C); - return; - case Instruction::SetGE: - Lower = C; - Upper = ConstantIntegral::getMinValue(C->getType()); // Min = Next(Max) - return; +ConstantRange ConstantRange::makeICmpRegion(unsigned Pred, + const ConstantRange &CR) { + if (CR.isEmptySet()) + return CR; + + uint32_t W = CR.getBitWidth(); + switch (Pred) { + default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()"); + case CmpInst::ICMP_EQ: + return CR; + case CmpInst::ICMP_NE: + if (CR.isSingleElement()) + return ConstantRange(CR.getUpper(), CR.getLower()); + return ConstantRange(W); + case CmpInst::ICMP_ULT: { + APInt UMax(CR.getUnsignedMax()); + if (UMax.isMinValue()) + return ConstantRange(W, /* empty */ false); + return ConstantRange(APInt::getMinValue(W), UMax); + } + case CmpInst::ICMP_SLT: { + APInt SMax(CR.getSignedMax()); + if (SMax.isMinSignedValue()) + return ConstantRange(W, /* empty */ false); + return ConstantRange(APInt::getSignedMinValue(W), SMax); + } + case CmpInst::ICMP_ULE: { + APInt UMax(CR.getUnsignedMax()); + if (UMax.isMaxValue()) + return ConstantRange(W); + return ConstantRange(APInt::getMinValue(W), UMax + 1); + } + case CmpInst::ICMP_SLE: { + APInt SMax(CR.getSignedMax()); + if (SMax.isMaxSignedValue()) + return ConstantRange(W); + return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); + } + case CmpInst::ICMP_UGT: { + APInt UMin(CR.getUnsignedMin()); + if (UMin.isMaxValue()) + return ConstantRange(W, /* empty */ false); + return ConstantRange(UMin + 1, APInt::getNullValue(W)); + } + case CmpInst::ICMP_SGT: { + APInt SMin(CR.getSignedMin()); + if (SMin.isMaxSignedValue()) + return ConstantRange(W, /* empty */ false); + return ConstantRange(SMin + 1, APInt::getSignedMinValue(W)); + } + case CmpInst::ICMP_UGE: { + APInt UMin(CR.getUnsignedMin()); + if (UMin.isMinValue()) + return ConstantRange(W); + return ConstantRange(UMin, APInt::getNullValue(W)); + } + case CmpInst::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 == ConstantIntegral::getMaxValue(getType()); + return Lower == Upper && Lower.isMaxValue(); } /// isEmptySet - Return true if this set contains no members. /// bool ConstantRange::isEmptySet() const { - return Lower == Upper && Lower == ConstantIntegral::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() const { - return GT(Lower, Upper); + return Lower.ugt(Upper); } - -/// getSingleElement - If this set contains a single element, return it, -/// otherwise return null. -ConstantIntegral *ConstantRange::getSingleElement() const { - if (Upper == Next(Lower)) // Is it a single element range? - return Lower; - return 0; +/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of +/// its bitwidth, for example: i8 [120, 140). +/// +bool ConstantRange::isSignWrappedSet() const { + return contains(APInt::getSignedMaxValue(getBitWidth())) && + contains(APInt::getSignedMinValue(getBitWidth())); } /// getSetSize - Return the number of elements in this set. /// -uint64_t ConstantRange::getSetSize() const { - if (isEmptySet()) return 0; - if (getType() == Type::BoolTy) { - if (Lower != Upper) // One of T or F in the set... - return 1; - return 2; // Must be full set... +APInt ConstantRange::getSetSize() const { + if (isEmptySet()) + return APInt(getBitWidth()+1, 0); + + if (isFullSet()) { + APInt Size(getBitWidth()+1, 0); + Size.setBit(getBitWidth()); + return Size; } - // Simply subtract the bounds... - Constant *Result = ConstantExpr::getSub(Upper, Lower); - return cast(Result)->getRawValue(); + // This is also correct for wrapped sets. + return (Upper - Lower).zext(getBitWidth()+1); } -/// contains - Return true if the specified value is in the set. +/// getUnsignedMax - Return the largest unsigned value contained in the +/// ConstantRange. +/// +APInt ConstantRange::getUnsignedMax() const { + if (isFullSet() || isWrappedSet()) + return APInt::getMaxValue(getBitWidth()); + 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()); + 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; + return SignedMax; + } + if (getLower().isNegative() == getUpper().isNegative()) + return SignedMax; + return getUpper() - 1; +} + +/// getSignedMin - Return the smallest signed value contained in the +/// ConstantRange. /// -bool ConstantRange::contains(ConstantInt *Val) const { - if (Lower == Upper) { - if (isFullSet()) return true; - return false; +APInt ConstantRange::getSignedMin() const { + APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); + if (!isWrappedSet()) { + if (getLower().sle(getUpper() - 1)) + return getLower(); + return SignedMin; + } + if ((getUpper() - 1).slt(getLower())) { + if (getUpper() != SignedMin) + return SignedMin; } + 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 LTE(Lower, Val) && LT(Val, Upper); - return LTE(Lower, Val) || LT(Val, Upper); + return Lower.ule(V) && V.ult(Upper); + return Lower.ule(V) || V.ult(Upper); } +/// contains - Return true if the argument is a subset of this range. +/// Two equal sets contain each other. The empty set contained by all other +/// sets. +/// +bool ConstantRange::contains(const ConstantRange &Other) const { + if (isFullSet() || Other.isEmptySet()) return true; + if (isEmptySet() || Other.isFullSet()) return false; + + if (!isWrappedSet()) { + if (Other.isWrappedSet()) + return false; + return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); + } + + 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()->isInteger() && - "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); } +/// \brief Subtract the specified range from this range (aka relative complement +/// of the sets). +ConstantRange ConstantRange::difference(const ConstantRange &CR) const { + return intersectWith(CR.inverse()); +} -// 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) { - assert(LHS.isWrappedSet() && !RHS.isWrappedSet()); - - // Check to see if we overlap on the Left side of RHS... - // - if (LT(RHS.getLower(), LHS.getUpper())) { - // We do overlap on the left side of RHS, see if we overlap on the right of - // RHS... - if (GT(RHS.getUpper(), LHS.getLower())) { - // 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()) - return LHS; - else - return RHS; - - } else { - // No overlap on the right, just on the left. - return ConstantRange(RHS.getLower(), LHS.getUpper()); - } +/// 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; - } 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())) { - // Simple overlap... - return ConstantRange(LHS.getLower(), RHS.getUpper()); - } else { - // No overlap... - return ConstantRange(LHS.getType(), false); + 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; } + if (Upper.ult(CR.Upper)) + return *this; + + if (Lower.ult(CR.Upper)) + return ConstantRange(Lower, CR.Upper); + + return ConstantRange(getBitWidth(), false); } -} -/// intersect - Return the range that results from the intersection of this -/// range with another range. -/// -ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) 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() && !CR.isWrappedSet()) { + if (CR.Lower.ult(Upper)) { + if (CR.Upper.ult(Upper)) + return CR; - if (!isWrappedSet()) { - if (!CR.isWrappedSet()) { - ConstantIntegral *L = Max(Lower, CR.Lower); - ConstantIntegral *U = Min(Upper, CR.Upper); - - if (LT(L, U)) // If range isn't empty... - return ConstantRange(L, U); - else - return ConstantRange(getType(), false); // Otherwise, return empty set - } else - return intersect1Wrapped(CR, *this); - } else { // We know "this" is wrapped... - if (!CR.isWrappedSet()) - return intersect1Wrapped(*this, CR); - else { - // Both ranges are wrapped... - ConstantIntegral *L = Max(Lower, CR.Lower); - ConstantIntegral *U = Min(Upper, CR.Upper); - return ConstantRange(L, U); + if (CR.Upper.ule(Lower)) + return ConstantRange(CR.Lower, Upper); + + if (getSetSize().ult(CR.getSetSize())) + return *this; + return CR; + } + 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; + return CR; + } + + if (CR.Lower.ult(Lower)) + return ConstantRange(Lower, CR.Upper); + + return CR; + } + if (CR.Upper.ule(Lower)) { + if (CR.Lower.ult(Lower)) + return *this; + + return ConstantRange(CR.Lower, Upper); + } + if (getSetSize().ult(CR.getSetSize())) + return *this; + 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) const { - assert(getType() == CR.getType() && "ConstantRange types don't agree!"); + 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); + + 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); + return ConstantRange(CR.Lower, Upper); + } + + APInt L = Lower, U = Upper; + if (CR.Lower.ult(L)) + L = CR.Lower; + if ((CR.Upper - 1).ugt(U - 1)) + U = CR.Upper; + + 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); + 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 + assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && + "ConstantRange::unionWith missed a case with one range wrapped"); + return ConstantRange(Lower, CR.Upper); + } + + // ------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 if the source range had been +/// correspond to the possible range of values as if the source range had been /// zero extended. -ConstantRange ConstantRange::zeroExtend(const Type *Ty) const { - assert(getLower()->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() && - "Not a value extension"); - if (isFullSet()) { - // Change a source full set into [0, 1 << 8*numbytes) - unsigned SrcTySize = getLower()->getType()->getPrimitiveSize(); - return ConstantRange(Constant::getNullValue(Ty), - ConstantUInt::get(Ty, 1ULL << SrcTySize*8)); +ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { + if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); + + unsigned SrcTySize = getBitWidth(); + assert(SrcTySize < DstTySize && "Not a value extension"); + if (isFullSet() || isWrappedSet()) { + // Change into [0, 1 << src bit width) + APInt LowerExt(DstTySize, 0); + if (!Upper) // special case: [X, 0) -- not really wrapping around + LowerExt = Lower.zext(DstTySize); + return ConstantRange(LowerExt, APInt(DstTySize, 1).shl(SrcTySize)); } - Constant *Lower = getLower(); - Constant *Upper = getUpper(); - if (Lower->getType()->isInteger() && !Lower->getType()->isUnsigned()) { - // Ensure we are doing a ZERO extension even if the input range is signed. - Lower = ConstantExpr::getCast(Lower, Ty->getUnsignedVersion()); - Upper = ConstantExpr::getCast(Upper, Ty->getUnsignedVersion()); + return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); +} + +/// 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 { + if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); + + unsigned SrcTySize = getBitWidth(); + assert(SrcTySize < DstTySize && "Not a value extension"); + if (isFullSet() || isSignWrappedSet()) { + return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), + APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); } - return ConstantRange(ConstantExpr::getCast(Lower, Ty), - ConstantExpr::getCast(Upper, Ty)); + return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); } /// 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 if the source range had been +/// 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 { - assert(getLower()->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() && - "Not a value truncation"); - uint64_t Size = 1ULL << Ty->getPrimitiveSize()*8; - if (isFullSet() || getSetSize() >= Size) - return ConstantRange(getType()); +ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { + assert(getBitWidth() > DstTySize && "Not a value truncation"); + if (isEmptySet()) + return ConstantRange(DstTySize, /*isFullSet=*/false); + if (isFullSet()) + return ConstantRange(DstTySize, /*isFullSet=*/true); + + APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth()); + APInt MaxBitValue(getBitWidth(), 0); + MaxBitValue.setBit(DstTySize); + + APInt LowerDiv(Lower), UpperDiv(Upper); + ConstantRange Union(DstTySize, /*isFullSet=*/false); + + // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] + // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and + // then we do the union with [MaxValue, Upper) + if (isWrappedSet()) { + // if Upper is greater than Max Value, it covers the whole truncated range. + if (Upper.uge(MaxValue)) + return ConstantRange(DstTySize, /*isFullSet=*/true); + + Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); + UpperDiv = APInt::getMaxValue(getBitWidth()); + + // Union covers the MaxValue case, so return if the remaining range is just + // MaxValue. + if (LowerDiv == UpperDiv) + return Union; + } + + // Chop off the most significant bits that are past the destination bitwidth. + if (LowerDiv.uge(MaxValue)) { + APInt Div(getBitWidth(), 0); + APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv); + UpperDiv = UpperDiv - MaxBitValue * Div; + } + + if (UpperDiv.ule(MaxValue)) + return ConstantRange(LowerDiv.trunc(DstTySize), + UpperDiv.trunc(DstTySize)).unionWith(Union); + + // The truncated value wrapps around. Check if we can do better than fullset. + APInt UpperModulo = UpperDiv - MaxBitValue; + if (UpperModulo.ult(LowerDiv)) + return ConstantRange(LowerDiv.trunc(DstTySize), + UpperModulo.trunc(DstTySize)).unionWith(Union); + + return ConstantRange(DstTySize, /*isFullSet=*/true); +} + +/// 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); + if (SrcTySize < DstTySize) + return zeroExtend(DstTySize); + return *this; +} - return ConstantRange(ConstantExpr::getCast(getLower(), Ty), - ConstantExpr::getCast(getUpper(), Ty)); +/// 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); + if (SrcTySize < DstTySize) + return signExtend(DstTySize); + 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::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.getUpper() + 1; + APInt NewUpper = getUpper() - Other.getLower(); + 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 + // multiple of that element. If wrapping is possible, at least adjust the + // range according to the greatest power-of-two factor of the single element. + + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + + 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(Lower, Upper); +} + +ConstantRange +ConstantRange::binaryAnd(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + + // TODO: replace this with something less conservative + + APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); + if (umin.isAllOnesValue()) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); +} + +ConstantRange +ConstantRange::binaryOr(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + + // TODO: replace this with something less conservative + + APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); + if (umax.isMinValue()) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + return ConstantRange(umax, APInt::getNullValue(getBitWidth())); +} + +ConstantRange +ConstantRange::shl(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + + APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); + APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); + + // there's no overflow! + APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); + if (Zeros.ugt(Other.getUnsignedMax())) + return ConstantRange(min, max + 1); + + // FIXME: implement the other tricky cases + return ConstantRange(getBitWidth(), /*isFullSet=*/true); +} + +ConstantRange +ConstantRange::lshr(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + + 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(getBitWidth(), /*isFullSet=*/false); + if (isEmptySet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + return ConstantRange(Upper, Lower); +} /// 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 { + if (isFullSet()) + OS << "full-set"; + else if (isEmptySet()) + OS << "empty-set"; + else + OS << "[" << Lower << "," << Upper << ")"; } /// dump - Allow printing from a debugger easily... /// void ConstantRange::dump() const { - print(std::cerr); + print(dbgs()); }