X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FConstantRange.cpp;h=5c5895026b67343c8fb14b2766d783d28c3b661d;hb=0b8c9a80f20772c3793201ab5b251d3520b9cea3;hp=493f7083dbb35c675da0d7d9b8d0835ebe6a33f6;hpb=40f8f6264d5af2c38e797e0dc59827cd231e8ff7;p=oota-llvm.git diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index 493f7083dbb..5c5895026b6 100644 --- a/lib/Support/ConstantRange.cpp +++ b/lib/Support/ConstantRange.cpp @@ -21,11 +21,10 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Constants.h" +#include "llvm/IR/InstrTypes.h" #include "llvm/Support/ConstantRange.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Instructions.h" using namespace llvm; /// Initialize a full (the default) or empty set for the specified type. @@ -56,56 +55,56 @@ ConstantRange ConstantRange::makeICmpRegion(unsigned Pred, uint32_t W = CR.getBitWidth(); switch (Pred) { - default: assert(!"Invalid ICmp predicate to makeICmpRegion()"); - case ICmpInst::ICMP_EQ: + default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()"); + case CmpInst::ICMP_EQ: return CR; - case ICmpInst::ICMP_NE: + case CmpInst::ICMP_NE: if (CR.isSingleElement()) return ConstantRange(CR.getUpper(), CR.getLower()); return ConstantRange(W); - case ICmpInst::ICMP_ULT: { + case CmpInst::ICMP_ULT: { APInt UMax(CR.getUnsignedMax()); if (UMax.isMinValue()) return ConstantRange(W, /* empty */ false); return ConstantRange(APInt::getMinValue(W), UMax); } - case ICmpInst::ICMP_SLT: { + case CmpInst::ICMP_SLT: { APInt SMax(CR.getSignedMax()); if (SMax.isMinSignedValue()) return ConstantRange(W, /* empty */ false); return ConstantRange(APInt::getSignedMinValue(W), SMax); } - case ICmpInst::ICMP_ULE: { + case CmpInst::ICMP_ULE: { APInt UMax(CR.getUnsignedMax()); if (UMax.isMaxValue()) return ConstantRange(W); return ConstantRange(APInt::getMinValue(W), UMax + 1); } - case ICmpInst::ICMP_SLE: { + case CmpInst::ICMP_SLE: { APInt SMax(CR.getSignedMax()); if (SMax.isMaxSignedValue()) return ConstantRange(W); return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); } - case ICmpInst::ICMP_UGT: { + case CmpInst::ICMP_UGT: { APInt UMin(CR.getUnsignedMin()); if (UMin.isMaxValue()) return ConstantRange(W, /* empty */ false); return ConstantRange(UMin + 1, APInt::getNullValue(W)); } - case ICmpInst::ICMP_SGT: { + case CmpInst::ICMP_SGT: { APInt SMin(CR.getSignedMin()); if (SMin.isMaxSignedValue()) return ConstantRange(W, /* empty */ false); return ConstantRange(SMin + 1, APInt::getSignedMinValue(W)); } - case ICmpInst::ICMP_UGE: { + case CmpInst::ICMP_UGE: { APInt UMin(CR.getUnsignedMin()); if (UMin.isMinValue()) return ConstantRange(W); return ConstantRange(UMin, APInt::getNullValue(W)); } - case ICmpInst::ICMP_SGE: { + case CmpInst::ICMP_SGE: { APInt SMin(CR.getSignedMin()); if (SMin.isMinSignedValue()) return ConstantRange(W); @@ -144,16 +143,17 @@ bool ConstantRange::isSignWrappedSet() const { /// getSetSize - Return the number of elements in this set. /// 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 APInt(2, 1); - return APInt(2, 2); // Must be full set... + if (isEmptySet()) + return APInt(getBitWidth()+1, 0); + + if (isFullSet()) { + APInt Size(getBitWidth()+1, 0); + Size.setBit(getBitWidth()); + return Size; } - // Simply subtract the bounds... - return Upper - Lower; + // This is also correct for wrapped sets. + return (Upper - Lower).zext(getBitWidth()+1); } /// getUnsignedMax - Return the largest unsigned value contained in the @@ -162,8 +162,7 @@ APInt ConstantRange::getSetSize() const { APInt ConstantRange::getUnsignedMax() const { if (isFullSet() || isWrappedSet()) return APInt::getMaxValue(getBitWidth()); - else - return getUpper() - 1; + return getUpper() - 1; } /// getUnsignedMin - Return the smallest unsigned value contained in the @@ -172,8 +171,7 @@ APInt ConstantRange::getUnsignedMax() const { APInt ConstantRange::getUnsignedMin() const { if (isFullSet() || (isWrappedSet() && getUpper() != 0)) return APInt::getMinValue(getBitWidth()); - else - return getLower(); + return getLower(); } /// getSignedMax - Return the largest signed value contained in the @@ -184,14 +182,11 @@ APInt ConstantRange::getSignedMax() const { 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; + return SignedMax; } + if (getLower().isNegative() == getUpper().isNegative()) + return SignedMax; + return getUpper() - 1; } /// getSignedMin - Return the smallest signed value contained in the @@ -202,18 +197,13 @@ APInt ConstantRange::getSignedMin() const { if (!isWrappedSet()) { if (getLower().sle(getUpper() - 1)) return getLower(); - else + return SignedMin; + } + if ((getUpper() - 1).slt(getLower())) { + if (getUpper() != SignedMin) return SignedMin; - } else { - if ((getUpper() - 1).slt(getLower())) { - if (getUpper() != SignedMin) - return SignedMin; - else - return getLower(); - } else { - return getLower(); - } } + return getLower(); } /// contains - Return true if the specified value is in the set. @@ -224,8 +214,7 @@ bool ConstantRange::contains(const APInt &V) const { if (!isWrappedSet()) return Lower.ule(V) && V.ult(Upper); - else - 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. @@ -260,6 +249,12 @@ ConstantRange ConstantRange::subtract(const APInt &Val) const { 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()); +} + /// 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 @@ -285,15 +280,14 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { return ConstantRange(CR.Lower, Upper); return CR; - } else { - if (Upper.ult(CR.Upper)) - return *this; + } + if (Upper.ult(CR.Upper)) + return *this; - if (Lower.ult(CR.Upper)) - return ConstantRange(Lower, CR.Upper); + if (Lower.ult(CR.Upper)) + return ConstantRange(Lower, CR.Upper); - return ConstantRange(getBitWidth(), false); - } + return ConstantRange(getBitWidth(), false); } if (isWrappedSet() && !CR.isWrappedSet()) { @@ -301,14 +295,14 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { if (CR.Upper.ult(Upper)) return CR; - if (CR.Upper.ult(Lower)) + if (CR.Upper.ule(Lower)) return ConstantRange(CR.Lower, Upper); if (getSetSize().ult(CR.getSetSize())) return *this; - else - return CR; - } else if (CR.Lower.ult(Lower)) { + return CR; + } + if (CR.Lower.ult(Lower)) { if (CR.Upper.ule(Lower)) return ConstantRange(getBitWidth(), false); @@ -321,15 +315,15 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { if (CR.Lower.ult(Upper)) { if (getSetSize().ult(CR.getSetSize())) return *this; - else - return CR; + return CR; } if (CR.Lower.ult(Lower)) return ConstantRange(Lower, CR.Upper); return CR; - } else if (CR.Upper.ult(Lower)) { + } + if (CR.Upper.ule(Lower)) { if (CR.Lower.ult(Lower)) return *this; @@ -337,8 +331,7 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { } if (getSetSize().ult(CR.getSetSize())) return *this; - else - return CR; + return CR; } @@ -363,8 +356,7 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; if (d1.ult(d2)) return ConstantRange(Lower, CR.Upper); - else - return ConstantRange(CR.Lower, Upper); + return ConstantRange(CR.Lower, Upper); } APInt L = Lower, U = Upper; @@ -397,8 +389,7 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; if (d1.ult(d2)) return ConstantRange(Lower, CR.Upper); - else - return ConstantRange(CR.Lower, Upper); + return ConstantRange(CR.Lower, Upper); } // ----U L----- : this @@ -408,13 +399,11 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { // ------U L---- : this // L-----U : CR - if (CR.Lower.ult(Upper) && CR.Upper.ult(Lower)) - return ConstantRange(Lower, CR.Upper); + assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && + "ConstantRange::unionWith missed a case with one range wrapped"); + 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)) @@ -438,9 +427,13 @@ ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { unsigned SrcTySize = getBitWidth(); assert(SrcTySize < DstTySize && "Not a value extension"); - if (isFullSet() || isWrappedSet()) + if (isFullSet() || isWrappedSet()) { // Change into [0, 1 << src bit width) - return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize)); + 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)); + } return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); } @@ -467,13 +460,54 @@ ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { /// correspond to the possible range of values as if the source range had been /// truncated to the specified type. 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)) + assert(getBitWidth() > DstTySize && "Not a value truncation"); + if (isEmptySet()) + return ConstantRange(DstTySize, /*isFullSet=*/false); + if (isFullSet()) return ConstantRange(DstTySize, /*isFullSet=*/true); - return ConstantRange(Lower.trunc(DstTySize), Upper.trunc(DstTySize)); + 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 @@ -482,10 +516,9 @@ ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { unsigned SrcTySize = getBitWidth(); if (SrcTySize > DstTySize) return truncate(DstTySize); - else if (SrcTySize < DstTySize) + if (SrcTySize < DstTySize) return zeroExtend(DstTySize); - else - return *this; + return *this; } /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The @@ -494,10 +527,9 @@ ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { unsigned SrcTySize = getBitWidth(); if (SrcTySize > DstTySize) return truncate(DstTySize); - else if (SrcTySize < DstTySize) + if (SrcTySize < DstTySize) return signExtend(DstTySize); - else - return *this; + return *this; } ConstantRange @@ -529,8 +561,8 @@ ConstantRange::sub(const ConstantRange &Other) const { return ConstantRange(getBitWidth(), /*isFullSet=*/true); APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); - APInt NewLower = getLower() - Other.getLower(); - APInt NewUpper = getUpper() - Other.getUpper() + 1; + APInt NewLower = getLower() - Other.getUpper() + 1; + APInt NewUpper = getUpper() - Other.getLower(); if (NewLower == NewUpper) return ConstantRange(getBitWidth(), /*isFullSet=*/true); @@ -551,8 +583,6 @@ 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); @@ -676,11 +706,10 @@ ConstantRange::lshr(const ConstantRange &Other) const { } ConstantRange ConstantRange::inverse() const { - if (isFullSet()) { + if (isFullSet()) return ConstantRange(getBitWidth(), /*isFullSet=*/false); - } else if (isEmptySet()) { + if (isEmptySet()) return ConstantRange(getBitWidth(), /*isFullSet=*/true); - } return ConstantRange(Upper, Lower); }