Index: llvm/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/include/llvm/IR/ConstantRange.h +++ llvm/include/llvm/IR/ConstantRange.h @@ -32,6 +32,7 @@ #define LLVM_IR_CONSTANTRANGE_H #include "llvm/ADT/APInt.h" +#include "llvm/ADT/APFloat.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/Support/Compiler.h" @@ -46,14 +47,25 @@ /// This class represents a range of values. class LLVM_NODISCARD ConstantRange { APInt Lower, Upper; + APFloat LowerFP = APFloat(0.0), UpperFP = APFloat(0.0); + bool isFloat = false; + bool canBeNaN = false; + + /// Create full constant FP range with the same semantics + ConstantRange getFullFP(bool CanBeNan=true) const { + assert(isFloat); + return getFull(LowerFP.getSemantics(), CanBeNan); + } - /// Create empty constant range with same bitwidth. + /// Create empty constant range with same bitwidth/semantics. ConstantRange getEmpty() const { + if (isFloat) return getEmpty(LowerFP.getSemantics()); return ConstantRange(getBitWidth(), false); } /// Create full constant range with same bitwidth. ConstantRange getFull() const { + if (isFloat) return getFull(LowerFP.getSemantics(), true); return ConstantRange(getBitWidth(), true); } @@ -63,22 +75,35 @@ /// Initialize a range to hold the single specified value. ConstantRange(APInt Value); + ConstantRange(const APFloat &Value); /// Initialize a range of values explicitly. This will assert out if /// Lower==Upper and Lower != Min or Max value for its type. It will also /// assert out if the two APInt's are not the same bit width. ConstantRange(APInt Lower, APInt Upper); + ConstantRange(APFloat Lower, APFloat Upper, bool canBeNaN = false); /// Create empty constant range with the given bit width. static ConstantRange getEmpty(uint32_t BitWidth) { return ConstantRange(BitWidth, false); } + /// Create empty float constant range with the given semantics. + static ConstantRange getEmpty(const fltSemantics &Sem) { + return ConstantRange(APFloat::getNaN(Sem), APFloat::getNaN(Sem), false); + } + /// Create full constant range with the given bit width. static ConstantRange getFull(uint32_t BitWidth) { return ConstantRange(BitWidth, true); } + /// Create full constant range with the given bit width. + static ConstantRange getFull(const fltSemantics &Sem, bool CanBeNan=true) { + return ConstantRange(APFloat::getInf(Sem, true), + APFloat::getInf(Sem, false), CanBeNan); + } + /// Create non-empty constant range with the given bounds. If Lower and /// Upper are the same, a full range is returned. static ConstantRange getNonEmpty(APInt Lower, APInt Upper) { @@ -103,6 +128,15 @@ static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other); + /// Produce the smallest range such that all values that may satisfy the given + /// predicate with any value contained within Other is contained in the + /// returned range. Formally, this returns a superset of + /// 'union over all y in Other . { x : icmp op x y is true }'. If the exact + /// answer is not representable as a ConstantRange, the return value will be a + /// proper superset of the above. + static ConstantRange makeAllowedFCmpRegion(CmpInst::Predicate Pred, + const ConstantRange &Other); + /// Produce the largest range such that all values in the returned range /// satisfy the given predicate with all values contained within Other. /// Formally, this returns a subset of @@ -114,6 +148,15 @@ static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other); + /// Produce the largest range such that all values in the returned range + /// satisfy the given predicate with all values contained within Other. + /// Formally, this returns a subset of + /// 'intersection over all y in Other . { x : fcmp op x y is true }'. If the + /// exact answer is not representable as a ConstantRange, the return value + /// will be a proper subset of the above. + static ConstantRange makeSatisfyingFCmpRegion(CmpInst::Predicate Pred, + const ConstantRange &Other); + /// Produce the exact range such that all values in the returned range satisfy /// the given predicate with any value contained within Other. Formally, this /// returns the exact answer when the superset of 'union over all y in Other @@ -124,6 +167,14 @@ static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other); + /// Produce the exact range such that all values in the returned range satisfy + /// the given predicate with any value contained within Other. Formally, this + /// returns the exact answer when the superset of 'union over all y in Other + /// is exactly same as the subset of intersection over all y in Other. + /// { x : fcmp op x y is true}'. + static ConstantRange makeExactFCmpRegion(CmpInst::Predicate Pred, + const APFloat &Other); + /// Produce the largest range containing all X such that "X BinOp Y" is /// guaranteed not to wrap (overflow) for *all* Y in Other. However, there may /// be *some* Y in Other for which additional X not contained in the result @@ -156,13 +207,25 @@ bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const; /// Return the lower value for this range. - const APInt &getLower() const { return Lower; } + const APInt &getLower() const { assert(!isFloat); return Lower; } /// Return the upper value for this range. - const APInt &getUpper() const { return Upper; } + const APInt &getUpper() const { assert(!isFloat); return Upper; } + + /// Return the lower value for this range. + const APFloat &getLowerFP() const { assert(isFloat); return LowerFP; } + + /// Return the upper value for this range. + const APFloat &getUpperFP() const { assert(isFloat); return UpperFP; } + + bool getIsFloat() const { return isFloat; } + bool getCanBeNaN() const { return isFloat && canBeNaN; } /// Get the bit width of this ConstantRange. - uint32_t getBitWidth() const { return Lower.getBitWidth(); } + uint32_t getBitWidth() const { + if (isFloat) return APFloat::getSizeInBits(LowerFP.getSemantics()); + else return Lower.getBitWidth(); + } /// Return true if this set contains all of the elements possible /// for this data-type. @@ -200,27 +263,42 @@ /// Return true if the specified value is in the set. bool contains(const APInt &Val) const; + /// Return true if the specified value is in the set. + bool contains(const APFloat &Val) const; + /// Return true if the other range is a subset of this one. bool contains(const ConstantRange &CR) const; /// If this set contains a single element, return it, otherwise return null. const APInt *getSingleElement() const { - if (Upper == Lower + 1) + if (!isFloat && (Upper == Lower + 1)) return &Lower; return nullptr; } + /// If this set contains a single FP element, return it, otherwise return null. + const APFloat *getSingleElementFP() const { + if (isFloat && !isEmptySet() && UpperFP.bitwiseIsEqual(LowerFP) && + (canBeNaN == LowerFP.isNaN())) + return &LowerFP; + return nullptr; + } + /// If this set contains all but a single element, return it, otherwise return /// null. const APInt *getSingleMissingElement() const { + assert(!isFloat); if (Lower == Upper + 1) return &Upper; return nullptr; } - /// Return true if this set contains exactly one member. + /// Return true if this set contains exactly one integer member. bool isSingleElement() const { return getSingleElement() != nullptr; } + /// Return true if this set contains exactly one floating point member. + bool isSingleElementFP() const { return getSingleElementFP() != nullptr; } + /// Compare set size of this range with the range CR. bool isSizeStrictlySmallerThan(const ConstantRange &CR) const; @@ -247,7 +325,12 @@ /// Return true if this range is equal to another range. bool operator==(const ConstantRange &CR) const { - return Lower == CR.Lower && Upper == CR.Upper; + if (isFloat) + return isFloat == CR.isFloat && canBeNaN == CR.canBeNaN && + (LowerFP.bitwiseIsEqual(CR.LowerFP) || (LowerFP.isNaN() && CR.LowerFP.isNaN())) && + (UpperFP.bitwiseIsEqual(CR.UpperFP) || (UpperFP.isNaN() && CR.UpperFP.isNaN())); + else + return isFloat == CR.isFloat && Lower == CR.Lower && Upper == CR.Upper; } bool operator!=(const ConstantRange &CR) const { return !operator==(CR); @@ -287,12 +370,18 @@ /// Return a new range representing the possible values resulting /// from an application of the specified cast operator to this range. \p - /// BitWidth is the target bitwidth of the cast. For casts which don't - /// change bitwidth, it must be the same as the source bitwidth. For casts + /// BitWidth is the target bitwidth of the cast. For casts which don't + /// change bitwidth, it must be the same as the source bitwidth. For casts /// which do change bitwidth, the bitwidth must be consistent with the - /// requested cast and source bitwidth. + /// requested cast and source bitwidth. Casts to floating point type are not + /// handled by this function. ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const; + /// Return a new range representing the possible values resulting + /// from an application of the specified cast operator to this range. \p + /// Sem is target floating point semantics. + ConstantRange castOp(Instruction::CastOps CastOp, + const llvm::fltSemantics &Sem) const; /// Return a new range in the specified integer type, which must /// be strictly larger than the current type. The returned range will @@ -338,6 +427,10 @@ /// from an addition of a value in this range and a value in \p Other. ConstantRange add(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting + /// from an addition of a value in this range and a value in \p Other. + ConstantRange fadd(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting /// from an addition with wrap type \p NoWrapKind of a value in this /// range and a value in \p Other. @@ -358,11 +451,31 @@ ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType = Smallest) const; + /// Return a new range representing the possible values resulting + /// from a subtraction of a value in this range and a value in \p Other. + ConstantRange fsub(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting /// from a multiplication of a value in this range and a value in \p Other, /// treating both this and \p Other as unsigned ranges. ConstantRange multiply(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting + /// from a multiplication of a value in this range and a value in \p Other. + ConstantRange fmultiply(const ConstantRange &Other) const; + + /// Return a new range representing the possible values resulting + /// from a division of a value in this range and a value in \p Other. + ConstantRange fdivide(const ConstantRange &Other) const; + + /// Return a new range representing the possible values resulting + /// from a maximum of a value in this range and a value in \p Other. + ConstantRange fmax(const ConstantRange &Other) const; + + /// Return a new range representing the possible values resulting + /// from a minimum of a value in this range and a value in \p Other. + ConstantRange fmin(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting /// from a signed maximum of a value in this range and a value in \p Other. ConstantRange smax(const ConstantRange &Other) const; Index: llvm/lib/IR/ConstantRange.cpp =================================================================== --- llvm/lib/IR/ConstantRange.cpp +++ llvm/lib/IR/ConstantRange.cpp @@ -39,6 +39,14 @@ using namespace llvm; +static APFloat ZeroNext(APFloat X, bool Neg) { + if (X.isZero() && X.isNegative() != Neg) + X.changeSign(); + else + X.next(Neg); + return X; +} + ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)), Upper(Lower) {} @@ -54,6 +62,23 @@ "Lower == Upper, but they aren't min or max value!"); } +ConstantRange::ConstantRange(const APFloat &Const) + : LowerFP(Const), UpperFP(Const), isFloat(true), canBeNaN(Const.isNaN()) {} + +ConstantRange::ConstantRange(APFloat Lower, APFloat Upper, bool canBeNaN) + : LowerFP(std::move(Lower)), UpperFP(std::move(Upper)), isFloat(true), + canBeNaN(canBeNaN) { + assert(&Lower.getSemantics() == &Upper.getSemantics() && + "ConstantRange with mismatched FP semantics"); + assert(LowerFP.isNaN() == UpperFP.isNaN()); + // Check if we are wrapped range with no values outside + APFloat Tmp = ZeroNext(LowerFP, true); + if (!LowerFP.bitwiseIsEqual(UpperFP) && Tmp.bitwiseIsEqual(UpperFP) && !Tmp.isNaN()) { + LowerFP = APFloat::getInf(LowerFP.getSemantics(), true); // NegInf + UpperFP = APFloat::getInf(LowerFP.getSemantics(), false); // PosInf + } +} + ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known, bool IsSigned) { assert(!Known.hasConflict() && "Expected valid KnownBits"); @@ -74,6 +99,117 @@ return ConstantRange(Lower, Upper + 1); } +ConstantRange ConstantRange::makeAllowedFCmpRegion(CmpInst::Predicate Pred, + const ConstantRange &CR) { + assert(CR.isFloat); + if (CR.isEmptySet()) + return CR; + + // Nothing is ordered wrt NaN + if (CR.LowerFP.isNaN() && CmpInst::isOrdered(Pred)) + return CR.getEmpty(); + // Everything is unordered wrt NaN + if (CR.canBeNaN && CmpInst::isUnordered(Pred)) + return CR.getFull(); + + // Useful constants + APFloat PosInf = APFloat::getInf(CR.LowerFP.getSemantics(), false); + APFloat NegInf = APFloat::getInf(CR.LowerFP.getSemantics(), true); + APFloat NaN = APFloat::getNaN(CR.LowerFP.getSemantics()); + + switch (Pred) { + default: + llvm_unreachable("Invalid FCmp predicate to makeAllowedFCmpRegion()"); + case CmpInst::FCMP_UNO: + // CR.canBeNaN is handled above, so only NaN compares UNO to CR. + return ConstantRange(NaN); + case CmpInst::FCMP_ORD: + // isnan(CR) is handled above, return no-nan range + return ConstantRange(std::move(NegInf), std::move(PosInf), false); + case CmpInst::FCMP_UEQ: + case CmpInst::FCMP_OEQ: { + // Return the sames ordered part as CR, extend boundaries if zero. + APFloat LowerFP = CR.LowerFP.isZero() ? APFloat::getZero(CR.LowerFP.getSemantics(), true) : CR.LowerFP; + APFloat UpperFP = CR.UpperFP.isZero() ? APFloat::getZero(CR.UpperFP.getSemantics(), false) : CR.UpperFP; + return ConstantRange(std::move(LowerFP), std::move(UpperFP), CmpInst::isUnordered(Pred)); + } + case CmpInst::FCMP_UNE: + case CmpInst::FCMP_ONE: + // bitwiseIsEqual covers singleElement + canBeNaN + // [-0,0] should be trated as single value wrt != operator + if (CR.LowerFP.bitwiseIsEqual(CR.UpperFP) || + (CR.LowerFP.isNegZero() && CR.UpperFP.isPosZero())) { + ConstantRange Inv = CR.inverse(); + Inv.canBeNaN = CmpInst::isUnordered(Pred); + // Handle +/- 0 + if (Inv.LowerFP.isPosZero()) // The original included -0.0 + Inv.LowerFP.next(false); + if (Inv.UpperFP.isNegZero()) // The original included 0.0 + Inv.UpperFP.next(true); + return Inv; + } + return ConstantRange(std::move(NegInf), std::move(PosInf), CmpInst::isUnordered(Pred)); + case CmpInst::FCMP_OLT: + case CmpInst::FCMP_ULT: { + // Nothing is LT -Inf, but NaN is unordered + if (CR.UpperFP.bitwiseIsEqual(CR.LowerFP) && + CR.UpperFP.isNegative() && CR.UpperFP.isInfinity()) + return ConstantRange(NaN, NaN, CmpInst::isUnordered(Pred)); + // Almost everything is LT +Inf + APFloat Upper = CR.contains(PosInf) ? PosInf : CR.UpperFP; + Upper.next(true); + return ConstantRange(std::move(NegInf), std::move(Upper), CmpInst::isUnordered(Pred)); + } + case CmpInst::FCMP_OGT: + case CmpInst::FCMP_UGT: { + // Nothing is GT +Inf, but NaN unordered + if (CR.UpperFP.bitwiseIsEqual(CR.LowerFP) && + !CR.UpperFP.isNegative() && CR.UpperFP.isInfinity()) + return ConstantRange(NaN, NaN, CmpInst::isUnordered(Pred)); + // Almost everything is LT -Inf + APFloat Lower = CR.contains(NegInf) ? NegInf : CR.LowerFP; + Lower.next(false); + return ConstantRange(std::move(Lower), std::move(PosInf), CmpInst::isUnordered(Pred)); + } + case CmpInst::FCMP_OLE: + case CmpInst::FCMP_ULE: { + // Everything is LE than +Inf, and NaN is unordered + if (CR.contains(PosInf)) + return ConstantRange(std::move(NegInf), std::move(PosInf), CmpInst::isUnordered(Pred)); + APFloat Upper = CR.UpperFP.isZero() ? APFloat::getZero(CR.UpperFP.getSemantics()) : CR.UpperFP; + return ConstantRange(std::move(NegInf), std::move(Upper), CmpInst::isUnordered(Pred)); + } + case CmpInst::FCMP_OGE: + case CmpInst::FCMP_UGE: { + // Everything is GE than -Inf, and NaN is unordered + if (CR.contains(NegInf)) + return ConstantRange(std::move(NegInf), std::move(PosInf), CmpInst::isUnordered(Pred)); + APFloat Lower = CR.LowerFP.isZero() ? APFloat::getZero(CR.LowerFP.getSemantics(), true) : CR.LowerFP; + return ConstantRange(std::move(Lower), std::move(PosInf), CmpInst::isUnordered(Pred)); + } + } +} + +ConstantRange ConstantRange::makeSatisfyingFCmpRegion(CmpInst::Predicate Pred, + const ConstantRange &CR) { + // Follows from De-Morgan's laws: + // + // ~(~A union ~B) == A intersect B. + // + return makeAllowedFCmpRegion(CmpInst::getInversePredicate(Pred), CR) + .inverse(); +} + +ConstantRange ConstantRange::makeExactFCmpRegion(CmpInst::Predicate Pred, + const APFloat &C) { + // Computes the exact range that is equal to both the constant ranges returned + // by makeAllowedFCmpRegion and makeSatisfyingICmpRegion. This is always true + // when RHS is a singleton such as an APFloat and so the assert is valid. + // + assert(makeAllowedFCmpRegion(Pred, C) == makeSatisfyingFCmpRegion(Pred, C)); + return makeAllowedFCmpRegion(Pred, C); +} + ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &CR) { if (CR.isEmptySet()) @@ -149,6 +285,7 @@ bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const { bool Success = false; + assert(!isFloat); if (isFullSet() || isEmptySet()) { Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE; @@ -302,32 +439,45 @@ } bool ConstantRange::isFullSet() const { - return Lower == Upper && Lower.isMaxValue(); + if (isFloat) + return LowerFP.isInfinity() && LowerFP.isNegative() && + UpperFP.isInfinity() && !UpperFP.isNegative() && canBeNaN; + else + return Lower == Upper && Lower.isMaxValue(); } bool ConstantRange::isEmptySet() const { + if (isFloat) + return LowerFP.isNaN() && UpperFP.isNaN() && !canBeNaN; return Lower == Upper && Lower.isMinValue(); } bool ConstantRange::isWrappedSet() const { + if (isFloat) // Float version is the same as isUpperWrapped + return isUpperWrapped(); return Lower.ugt(Upper) && !Upper.isNullValue(); } bool ConstantRange::isUpperWrapped() const { + if (isFloat) + return LowerFP.compare(UpperFP) == APFloat::cmpGreaterThan; return Lower.ugt(Upper); } bool ConstantRange::isSignWrappedSet() const { + assert(!isFloat); return Lower.sgt(Upper) && !Upper.isMinSignedValue(); } bool ConstantRange::isUpperSignWrapped() const { + assert(!isFloat); return Lower.sgt(Upper); } bool ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const { assert(getBitWidth() == Other.getBitWidth()); + assert(!isFloat); if (isFullSet()) return false; if (Other.isFullSet()) @@ -338,6 +488,7 @@ bool ConstantRange::isSizeLargerThan(uint64_t MaxSize) const { assert(MaxSize && "MaxSize can't be 0."); + assert(!isFloat); // If this a full set, we need special handling to avoid needing an extra bit // to represent the size. if (isFullSet()) @@ -353,6 +504,7 @@ if (isFullSet()) return false; + assert(!isFloat); return !isUpperSignWrapped() && !Upper.isStrictlyPositive(); } @@ -362,30 +514,35 @@ } APInt ConstantRange::getUnsignedMax() const { + assert(!isFloat); if (isFullSet() || isUpperWrapped()) return APInt::getMaxValue(getBitWidth()); return getUpper() - 1; } APInt ConstantRange::getUnsignedMin() const { + assert(!isFloat); if (isFullSet() || isWrappedSet()) return APInt::getMinValue(getBitWidth()); return getLower(); } APInt ConstantRange::getSignedMax() const { + assert(!isFloat); if (isFullSet() || isUpperSignWrapped()) return APInt::getSignedMaxValue(getBitWidth()); return getUpper() - 1; } APInt ConstantRange::getSignedMin() const { + assert(!isFloat); if (isFullSet() || isSignWrappedSet()) return APInt::getSignedMinValue(getBitWidth()); return getLower(); } bool ConstantRange::contains(const APInt &V) const { + assert(!isFloat); if (Lower == Upper) return isFullSet(); @@ -394,21 +551,64 @@ return Lower.ule(V) || V.ult(Upper); } +bool ConstantRange::contains(const APFloat &V) const { + assert(isFloat); + if (V.isNaN()) + return canBeNaN; + + if (V.bitwiseIsEqual(LowerFP) || V.bitwiseIsEqual(UpperFP)) + return true; + + // Special handling for signed zeros + if (V.isPosZero() && LowerFP.isNegZero() && !UpperFP.isNegZero()) + return true; + if (V.isNegZero() && UpperFP.isPosZero() && !LowerFP.isPosZero()) + return true; + + if (!isUpperWrapped()) + return LowerFP < V && V < UpperFP; + return UpperFP > V || V > LowerFP; +} + bool ConstantRange::contains(const ConstantRange &Other) const { + assert(isFloat == Other.isFloat); if (isFullSet() || Other.isEmptySet()) return true; if (isEmptySet() || Other.isFullSet()) return false; + if (isFloat && canBeNaN && Other.UpperFP.isNaN()) return true; if (!isUpperWrapped()) { if (Other.isUpperWrapped()) return false; + if (isFloat) { + auto Lo = LowerFP.compare(Other.LowerFP); + auto Hi = UpperFP.compare(Other.UpperFP); + return (Lo == APFloat::cmpLessThan || + LowerFP.bitwiseIsEqual(Other.LowerFP) || + (LowerFP.isNegZero() && Other.LowerFP.isPosZero())) && + (Hi == APFloat::cmpGreaterThan || + UpperFP.bitwiseIsEqual(Other.UpperFP) || + (UpperFP.isPosZero() && Other.UpperFP.isNegZero())) && + (canBeNaN || !Other.canBeNaN); + } return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); } - if (!Other.isUpperWrapped()) - return Other.getUpper().ule(Upper) || - Lower.ule(Other.getLower()); + if (!Other.isUpperWrapped()) { + if (isFloat) { + // LHS is UpperWrapped, RHS is not. We can split into two subregions. + ConstantRange UpperHalf = ConstantRange(LowerFP, + APFloat::getInf(LowerFP.getSemantics()), + canBeNaN); + ConstantRange LowerHalf = ConstantRange( + APFloat::getInf(LowerFP.getSemantics(), true), + UpperFP, canBeNaN); + return LowerHalf.contains(Other) || UpperHalf.contains(Other); + } + return Other.getUpper().ule(Upper) || Lower.ule(Other.getLower()); + } + assert(!isFloat); return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); } @@ -446,6 +646,8 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR, PreferredRangeType Type) const { + assert(isFloat == CR.isFloat && + "ConstantRange type don't agree!"); assert(getBitWidth() == CR.getBitWidth() && "ConstantRange types don't agree!"); @@ -457,6 +659,24 @@ return CR.intersectWith(*this, Type); if (!isUpperWrapped() && !CR.isUpperWrapped()) { + if (isFloat) { + assert(Type == Smallest); + // There are several situations handled in this block, + // none of which can result in a wrapped or disjoint result: + // this: L--U | L--U | L--U | L---U | L--U | L--U + // CR: L--U | L--U | L----U | L-U | L--U | L--U + APFloat Upper = llvm::minimum(UpperFP, CR.UpperFP); + APFloat Lower = llvm::maximum(LowerFP, CR.LowerFP); + auto Res = Lower.compare(Upper); + // Explicitly allow [-0, 0] + if (Res != APFloat::cmpLessThan && !Lower.bitwiseIsEqual(Upper) && + !(Lower.isNegZero() && Upper.isPosZero())) + return ConstantRange(APFloat::getNaN(Lower.getSemantics()), + APFloat::getNaN(Upper.getSemantics()), + canBeNaN && CR.canBeNaN); + return ConstantRange(::std::move(Lower), ::std::move(Upper), + canBeNaN && CR.canBeNaN); + } if (Lower.ult(CR.Lower)) { // L---U : this // L---U : CR @@ -488,37 +708,65 @@ } if (isUpperWrapped() && !CR.isUpperWrapped()) { - if (CR.Lower.ult(Upper)) { + // FP range is inclusive so include it here + if ((!isFloat && CR.Lower.ult(Upper)) || + (isFloat && CR.LowerFP <= UpperFP)) { // ------U L--- : this // L--U : CR - if (CR.Upper.ult(Upper)) + if (!isFloat && CR.Upper.ult(Upper)) return CR; + if (isFloat && CR.UpperFP < UpperFP) + return ConstantRange(CR.LowerFP, CR.UpperFP, canBeNaN && CR.canBeNaN); // ------U L--- : this // L------U : CR - if (CR.Upper.ule(Lower)) + if (!isFloat && CR.Upper.ule(Lower)) return ConstantRange(CR.Lower, Upper); + // FP range is inclusive so don't include it here + if (isFloat && CR.UpperFP < LowerFP) + return ConstantRange(CR.LowerFP, UpperFP, canBeNaN && CR.canBeNaN); // ------U L--- : this // L----------U : CR + if (isFloat) + return ConstantRange(CR.LowerFP, CR.UpperFP, canBeNaN && CR.canBeNaN); return getPreferredRange(*this, CR, Type); } - if (CR.Lower.ult(Lower)) { + if ((!isFloat && CR.Lower.ult(Lower)) || + (isFloat && CR.LowerFP < LowerFP)) { // --U L---- : this // L--U : CR - if (CR.Upper.ule(Lower)) + if (!isFloat && CR.Upper.ule(Lower)) return getEmpty(); + if (isFloat && CR.UpperFP < LowerFP) + return ConstantRange(APFloat::getNaN(LowerFP.getSemantics()), + APFloat::getNaN(UpperFP.getSemantics()), + canBeNaN && CR.canBeNaN); // --U L---- : this // L------U : CR + if (isFloat) + return ConstantRange(LowerFP, CR.UpperFP, canBeNaN && CR.canBeNaN); return ConstantRange(Lower, CR.Upper); } // --U L------ : this // L--U : CR + if (isFloat) + return ConstantRange(CR.LowerFP, CR.UpperFP, canBeNaN && CR.canBeNaN); return CR; } + // Both are upperWrapped + if (isFloat) { + assert(Type == Smallest); + // Handle disjoint cases + if (CR.LowerFP <= UpperFP || LowerFP <= CR.UpperFP) + return (CR.LowerFP - CR.UpperFP) > (LowerFP - UpperFP) ? CR : *this; + APFloat Upper = llvm::minimum(UpperFP, CR.UpperFP); + APFloat Lower = llvm::maximum(LowerFP, CR.LowerFP); + return ConstantRange(::std::move(Lower), ::std::move(Upper), canBeNaN && CR.canBeNaN); + } if (CR.Upper.ult(Upper)) { // ------U L-- : this // --U L------ : CR @@ -552,16 +800,25 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR, PreferredRangeType Type) const { - assert(getBitWidth() == CR.getBitWidth() && - "ConstantRange types don't agree!"); + assert(isFloat == CR.isFloat); if ( isFullSet() || CR.isEmptySet()) return *this; if (CR.isFullSet() || isEmptySet()) return CR; + // Handle union with NaN that is not empty + if (CR.UpperFP.isNaN()) return ConstantRange(LowerFP, UpperFP, true); + if (UpperFP.isNaN()) return ConstantRange(CR.LowerFP, CR.UpperFP, true); + + assert(getBitWidth() == CR.getBitWidth() && + "ConstantRange types don't agree!"); if (!isUpperWrapped() && CR.isUpperWrapped()) return CR.unionWith(*this, Type); if (!isUpperWrapped() && !CR.isUpperWrapped()) { + if (isFloat) { + return ConstantRange(minimum(LowerFP, CR.LowerFP), + maximum(UpperFP, CR.UpperFP), canBeNaN || CR.canBeNaN); + } // L---U and L---U : this // L---U L---U : CR // result in one of @@ -583,30 +840,47 @@ if (!CR.isUpperWrapped()) { // ------U L----- and ------U L----- : this // L--U L--U : CR - if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) + if (!isFloat && (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))) return *this; + // Call maximum/minimum to properly handle +/-0 situations. + if (isFloat && CR.UpperFP <= UpperFP) + return ConstantRange(LowerFP, maximum(UpperFP, CR.UpperFP), canBeNaN || CR.canBeNaN); + if (isFloat && CR.LowerFP >= LowerFP) + return ConstantRange(minimum(LowerFP, CR.LowerFP), UpperFP, canBeNaN || CR.canBeNaN); // ------U L----- : this // L---------U : CR - if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) + if (!isFloat && (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))) return getFull(); + if (isFloat && (CR.LowerFP <= UpperFP && LowerFP <= CR.UpperFP)) + return getFullFP(canBeNaN || CR.canBeNaN); // ----U L---- : this // L---U : CR // results in one of // ----------U L---- // ----U L---------- - if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) + if (!isFloat && Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) return getPreferredRange( ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type); + if (isFloat && UpperFP < CR.LowerFP && CR.UpperFP < LowerFP) { + assert(Type == Smallest); + return CR.LowerFP - UpperFP > LowerFP - CR.UpperFP ? + ConstantRange(CR.LowerFP, UpperFP, canBeNaN || CR.canBeNaN): + ConstantRange(LowerFP, CR.UpperFP, canBeNaN || CR.canBeNaN); + } // ----U L----- : this // L----U : CR - if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper)) + if (!isFloat && Upper.ult(CR.Lower) && Lower.ule(CR.Upper)) return ConstantRange(CR.Lower, Upper); + if (isFloat && UpperFP < CR.LowerFP && LowerFP <= CR.UpperFP) + return ConstantRange(CR.LowerFP, UpperFP, canBeNaN || CR.canBeNaN); // ------U L---- : this // L-----U : CR + if (isFloat) + return ConstantRange(LowerFP, CR.UpperFP, canBeNaN || CR.canBeNaN); assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) && "ConstantRange::unionWith missed a case with one range wrapped"); return ConstantRange(Lower, CR.Upper); @@ -614,9 +888,14 @@ // ------U L---- and ------U L---- : this // -U L----------- and ------------U L : CR - if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) + if (!isFloat && (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))) return getFull(); + if (isFloat && (CR.LowerFP <= UpperFP || LowerFP <= CR.UpperFP)) + return getFullFP(canBeNaN || CR.canBeNaN); + if (isFloat) + return ConstantRange(minimum(LowerFP, CR.LowerFP), + maximum(UpperFP, CR.UpperFP), canBeNaN || CR.canBeNaN); APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower; APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper; @@ -635,29 +914,14 @@ case Instruction::ZExt: return zeroExtend(ResultBitWidth); case Instruction::BitCast: - return *this; + // Bitcast bitwidth needs to match. ppc_fp128 needs special handling + assert((getBitWidth() == ResultBitWidth) || + (ResultBitWidth == 128 && (isFloat && &LowerFP.getSemantics() == &APFloat::PPCDoubleDouble()))); + return isFloat ? getFull(ResultBitWidth) : *this; case Instruction::FPToUI: case Instruction::FPToSI: - if (getBitWidth() == ResultBitWidth) - return *this; - else - return getFull(ResultBitWidth); - case Instruction::UIToFP: { // TODO: use input range if available - auto BW = getBitWidth(); - APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth); - APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth); - return ConstantRange(std::move(Min), std::move(Max)); - } - case Instruction::SIToFP: { - // TODO: use input range if available - auto BW = getBitWidth(); - APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth); - APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth); - return ConstantRange(std::move(SMin), std::move(SMax)); - } - case Instruction::FPTrunc: - case Instruction::FPExt: + return getFull(ResultBitWidth); case Instruction::IntToPtr: case Instruction::PtrToInt: case Instruction::AddrSpaceCast: @@ -666,7 +930,38 @@ }; } +ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp, + const llvm::fltSemantics &Sem) const { + switch (CastOp) { + default: + llvm_unreachable("unsupported cast type"); + case Instruction::FPTrunc: + case Instruction::FPExt: { + bool losesInfo1 = false, losesInfo2 = false; + APFloat ValL = LowerFP, ValU = UpperFP; + if (isUpperWrapped()) { + ValL.convert(Sem, APFloat::rmTowardPositive, &losesInfo1); + ValU.convert(Sem, APFloat::rmTowardNegative, &losesInfo2); + } else { + ValL.convert(Sem, APFloat::rmTowardNegative, &losesInfo1); + ValU.convert(Sem, APFloat::rmTowardPositive, &losesInfo2); + } + return ConstantRange(ValL, ValU, canBeNaN); + } + case Instruction::BitCast: + // Bitcast bitwidth needs to match. ppc_fp128 needs special handling + assert((getBitWidth() == APFloat::getSizeInBits(Sem)) || + (getBitWidth() == 128 && &Sem == &APFloat::PPCDoubleDouble())); + return isFloat ? *this : getFull(Sem); + case Instruction::UIToFP: + case Instruction::SIToFP: + // TODO: use input range if available + return getFull(Sem); + }; +} + ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { + assert(!isFloat); if (isEmptySet()) return getEmpty(DstTySize); unsigned SrcTySize = getBitWidth(); @@ -684,6 +979,7 @@ } ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { + assert(!isFloat); if (isEmptySet()) return getEmpty(DstTySize); unsigned SrcTySize = getBitWidth(); @@ -702,6 +998,7 @@ } ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { + assert(!isFloat); assert(getBitWidth() > DstTySize && "Not a value truncation"); if (isEmptySet()) return getEmpty(DstTySize); @@ -756,6 +1053,7 @@ } ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { + assert(!isFloat); unsigned SrcTySize = getBitWidth(); if (SrcTySize > DstTySize) return truncate(DstTySize); @@ -765,6 +1063,7 @@ } ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { + assert(!isFloat); unsigned SrcTySize = getBitWidth(); if (SrcTySize > DstTySize) return truncate(DstTySize); @@ -804,14 +1103,22 @@ return binaryOr(Other); case Instruction::Xor: return binaryXor(Other); - // Note: floating point operations applied to abstract ranges are just - // ideal integer operations with a lossy representation case Instruction::FAdd: - return add(Other); + if (isFloat) // We don't support vector types + return fadd(Other); + // Fallthrough case Instruction::FSub: - return sub(Other); + if (isFloat) // We don't support vector types + return fsub(Other); + // Fallthrough case Instruction::FMul: - return multiply(Other); + if (isFloat) // We don't support vector types + return fmultiply(Other); + // Fallthrough + case Instruction::FDiv: + if (isFloat) // We don't support vector types + return fdivide(Other); + // Fallthrough default: // Conservatively return getFull set. return getFull(); @@ -835,8 +1142,46 @@ } } +ConstantRange +ConstantRange::fadd(const ConstantRange &Other) const { + assert(isFloat && Other.isFloat); + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + + // If one of the operands can only be NaN, it propagates. + // Even if the other operand is full set. + if (isSingleElementFP() && getSingleElementFP()->isNaN()) + return *this; + if (Other.isSingleElementFP() && Other.getSingleElementFP()->isNaN()) + return Other; + + if (isFullSet() || Other.isFullSet()) + return getFull(); + + // Adding infinities of oposing signs generates NaN + APFloat PosInf = APFloat::getInf(LowerFP.getSemantics(), false); + APFloat NegInf = APFloat::getInf(LowerFP.getSemantics(), true); + bool ResNaN = (contains(PosInf) && Other.contains(NegInf)) || + (contains(NegInf) && Other.contains(PosInf)) || + canBeNaN || Other.canBeNaN; + + if (isUpperWrapped() || Other.isUpperWrapped()) + return ConstantRange(std::move(NegInf), std::move(PosInf), ResNaN); + + APFloat NewLower = LowerFP; + APFloat NewUpper = UpperFP; + NewLower.add(Other.LowerFP, APFloat::rmTowardNegative); + NewUpper.add(Other.UpperFP, APFloat::rmTowardPositive); + // Give up if any boundaries generate NaN + if (NewUpper.isNaN() || NewLower.isNaN()) + return getFull(); + + return ConstantRange(std::move(NewLower), std::move(NewUpper), ResNaN); +} + ConstantRange ConstantRange::add(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); if (isFullSet() || Other.isFullSet()) @@ -860,6 +1205,7 @@ PreferredRangeType RangeType) const { // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow). // (X is from this, and Y is from Other) + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); if (isFullSet() && Other.isFullSet()) @@ -882,8 +1228,46 @@ return Result; } +ConstantRange +ConstantRange::fsub(const ConstantRange &Other) const { + assert(isFloat && Other.isFloat); + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + + // If one of the operands can only be NaN, it propagates. + // Even if the other operand is full set. + if (isSingleElementFP() && getSingleElementFP()->isNaN()) + return *this; + if (Other.isSingleElementFP() && Other.getSingleElementFP()->isNaN()) + return Other; + + if (isFullSet() || Other.isFullSet()) + return getFull(); + + // Subtracting infinities of the same sign generates NaN + APFloat PosInf = APFloat::getInf(LowerFP.getSemantics(), false); + APFloat NegInf = APFloat::getInf(LowerFP.getSemantics(), true); + bool ResNaN = (contains(PosInf) && Other.contains(PosInf)) || + (contains(NegInf) && Other.contains(NegInf)) || + canBeNaN || Other.canBeNaN; + + if (isUpperWrapped() || Other.isUpperWrapped()) + return ConstantRange(std::move(NegInf), std::move(PosInf), ResNaN); + + APFloat NewLower = LowerFP; + APFloat NewUpper = UpperFP; + NewLower.subtract(Other.UpperFP, APFloat::rmTowardNegative); + NewUpper.subtract(Other.LowerFP, APFloat::rmTowardPositive); + // Give up if any boundaries generate NaN + if (NewUpper.isNaN() || NewLower.isNaN()) + return getFull(); + + return ConstantRange(std::move(NewLower), std::move(NewUpper), ResNaN); +} + ConstantRange ConstantRange::sub(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); if (isFullSet() || Other.isFullSet()) @@ -907,6 +1291,7 @@ PreferredRangeType RangeType) const { // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow). // (X is from this, and Y is from Other) + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); if (isFullSet() && Other.isFullSet()) @@ -932,6 +1317,176 @@ return Result; } +ConstantRange +ConstantRange::fdivide(const ConstantRange &Other) const { + assert(isFloat && Other.isFloat); + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + + // If one of the operands can only be NaN, it propagates. + // Even if the other operand is full set. + if (isSingleElementFP() && getSingleElementFP()->isNaN()) + return *this; + if (Other.isSingleElementFP() && Other.getSingleElementFP()->isNaN()) + return Other; + + if (isFullSet() || Other.isFullSet()) + return getFull(); + + // Useful constants + APFloat PosInf = APFloat::getInf(LowerFP.getSemantics(), false); + APFloat NegInf = APFloat::getInf(LowerFP.getSemantics(), true); + APFloat PosZero = APFloat::getZero(LowerFP.getSemantics(), false); + APFloat NegZero = APFloat::getZero(LowerFP.getSemantics(), true); + + // Dividing Inf/Inf is NaN, as is 0/0 + auto ContainsInf = [=](const ConstantRange &CR) { + return CR.contains(PosInf) || CR.contains(NegInf); + }; + auto ContainsZero = [=](const ConstantRange &CR) { + return CR.contains(PosZero) || CR.contains(NegZero); + }; + bool ResNaN = (ContainsInf(*this) && ContainsInf(Other)) || + (ContainsZero(Other) && ContainsZero(*this)) || + canBeNaN || Other.canBeNaN; + + // Division by +/-Zero: + // X / 0 == Inf for X > 0, X / -0 == -Inf for X < -0 + // X / 0 == -Inf for X < -0, X / -0 == Inf for X > 0 + bool ResPosInf = (Other.contains(PosZero) && (!LowerFP.isNegative() || !UpperFP.isNegative())) || + (Other.contains(NegZero) && (LowerFP.isNegative() || UpperFP.isNegative())); + bool ResNegInf = (Other.contains(PosZero) && (LowerFP.isNegative() || UpperFP.isNegative())) || + (Other.contains(NegZero) && (!LowerFP.isNegative() || !UpperFP.isNegative())); + if (ResPosInf && ResNegInf) + return ConstantRange(std::move(NegInf), std::move(PosInf), ResNaN); + + // Division by Inf. Both bounds are Inf except for [-Inf, Inf] + if (Other.LowerFP.isInfinity() && Other.UpperFP.isInfinity() && + !(!Other.UpperFP.isNegative() && Other.LowerFP.isNegative())) { + // +/-Inf / +/- Inf can only be NaN + if (LowerFP.isInfinity() && UpperFP.isInfinity() && + !(!UpperFP.isNegative() && LowerFP.isNegative())) + return ConstantRange(APFloat::getNaN(LowerFP.getSemantics())); + // 'this' contains other numbers than +/-Inf + return ConstantRange(std::move(NegZero), std::move(PosZero), ResNaN); + } + + // If upperWrapped ranges have not been handled by now, give up. + if (isUpperWrapped() || Other.isUpperWrapped()) + return ConstantRange(std::move(NegInf), std::move(PosInf), ResNaN); + + APFloat MyBounds[] = {LowerFP, UpperFP}; + APFloat OtherBounds[] = {Other.LowerFP, Other.UpperFP}; + APFloat::roundingMode RoundingModes[] = {APFloat::rmTowardNegative, APFloat::rmTowardPositive}; + + SmallVector Bounds; + for (const auto &MyBound:MyBounds) + for (const auto &OtherBound:OtherBounds) + for (auto RM:RoundingModes) { + APFloat Res = MyBound; + Res.divide(OtherBound, RM); + if (!Res.isNaN()) + Bounds.push_back(std::move(Res)); + } + if (ResPosInf) + Bounds.push_back(std::move(PosInf)); + if (ResNegInf) + Bounds.push_back(std::move(PosInf)); + assert(!Bounds.empty()); + auto CompareMin = [](const APFloat &A, const APFloat &B) { + return llvm::minimum(A, B).bitwiseIsEqual(A); }; + auto CompareMax = [](const APFloat &A, const APFloat &B) { + return llvm::maximum(A, B).bitwiseIsEqual(B); }; + return ConstantRange(*std::min_element(Bounds.begin(), Bounds.end(), CompareMin), + *std::max_element(Bounds.begin(), Bounds.end(), CompareMax), ResNaN); +} + +ConstantRange +ConstantRange::fmultiply(const ConstantRange &Other) const { + assert(isFloat && Other.isFloat); + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + + // If one of the operands can only be NaN, it propagates. + // Even if the other operand is full set. + if (isSingleElementFP() && getSingleElementFP()->isNaN()) + return *this; + if (Other.isSingleElementFP() && Other.getSingleElementFP()->isNaN()) + return Other; + + // Full set includes infinities. Multiplying inf results in +/-inf so just + // return another full set + if (isFullSet() || Other.isFullSet()) + return getFull(); + + // Useful constants + APFloat PosInf = APFloat::getInf(LowerFP.getSemantics(), false); + APFloat NegInf = APFloat::getInf(LowerFP.getSemantics(), true); + APFloat PosZero = APFloat::getZero(LowerFP.getSemantics(), false); + APFloat NegZero = APFloat::getZero(LowerFP.getSemantics(), true); + + // Handle special cases, where multiplying boudnaries doesn't work: + // [-Inf, 0] * [-Inf, 0] -- produces [0, Inf] instead of [-0, Inf] + // [-Inf, 0] * [-0, Inf] -- produces [-Inf, -0] instead of [-Inf, 0] + // [-0, Inf] * [-Inf, 0] -- produces [-Inf, -0] instead of [-Inf, 0] + // [-0, Inf] * [-0, Inf] -- produces [0, Inf] instead of [-0, Inf] + auto IsNegZeroPosInf = [](const ConstantRange &CR) { + return CR.LowerFP.isNegZero() && CR.UpperFP.isInfinity() && !CR.UpperFP.isNegative(); + }; + auto IsNegInfPosZero = [](const ConstantRange &CR) { + return CR.UpperFP.isPosZero() && CR.LowerFP.isInfinity() && CR.LowerFP.isNegative(); + }; + if ((IsNegInfPosZero(*this) && IsNegZeroPosInf(Other)) || + (IsNegZeroPosInf(*this) && IsNegInfPosZero(Other))) + return ConstantRange(std::move(NegInf), std::move(PosZero), true); + if ((IsNegZeroPosInf(*this) && IsNegZeroPosInf(Other)) || + (IsNegInfPosZero(*this) && IsNegInfPosZero(Other))) + return ConstantRange(std::move(NegZero), std::move(PosInf), true); + + // Multiplying any zero by any inf produces NaN + auto ContainsInf = [=](const ConstantRange &CR) { + return CR.contains(PosInf) || CR.contains(NegInf); + }; + auto ContainsZero = [=](const ConstantRange &CR) { + return CR.contains(PosZero) || CR.contains(NegZero); + }; + bool ResNaN = (ContainsZero(*this) && ContainsInf(Other)) || + (ContainsZero(Other) && ContainsInf(*this)) || + canBeNaN || Other.canBeNaN; + + // Multiplication by +/-Zero: Inf * 0 is NaN, any other value * 0 is +/-0 + // This conservatively includes both zeros. + if ((LowerFP.isZero() && UpperFP.isZero()) || + (Other.LowerFP.isZero() && Other.UpperFP.isZero())) + return ConstantRange(std::move(NegZero), std::move(PosZero), ResNaN); + + // If upperWrapped ranges have not been handled by now, give up. + if (isUpperWrapped() || Other.isUpperWrapped()) + return ConstantRange(std::move(NegInf), std::move(PosInf), ResNaN); + + APFloat MyBounds[] = {LowerFP, UpperFP}; + APFloat OtherBounds[] = {Other.LowerFP, Other.UpperFP}; + APFloat::roundingMode RoundingModes[] = {APFloat::rmTowardNegative, APFloat::rmTowardPositive}; + + SmallVector Bounds; + for (const auto &MyBound:MyBounds) + for (const auto &OtherBound:OtherBounds) + for (auto RM:RoundingModes) { + APFloat Res = MyBound; + Res.multiply(OtherBound, RM); + if (!Res.isNaN()) + Bounds.push_back(std::move(Res)); + } + assert(!Bounds.empty()); + + auto CompareMin = [](const APFloat &A, const APFloat &B) { + return llvm::minimum(A, B).bitwiseIsEqual(A); }; + auto CompareMax = [](const APFloat &A, const APFloat &B) { + return llvm::maximum(A, B).bitwiseIsEqual(B); }; + return ConstantRange(*std::min_element(Bounds.begin(), Bounds.end(), CompareMin), + *std::max_element(Bounds.begin(), Bounds.end(), CompareMax), ResNaN); +} + ConstantRange ConstantRange::multiply(const ConstantRange &Other) const { // TODO: If either operand is a single element and the multiply is known to @@ -939,6 +1494,7 @@ // 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. + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -986,10 +1542,60 @@ return UR.isSizeStrictlySmallerThan(SR) ? UR : SR; } +ConstantRange +ConstantRange::fmax(const ConstantRange &Other) const { + assert(isFloat); + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + // X fmax Y is: range(fmax(X_smin, Y_smin), fmax(X_smax, Y_smax)) + if (!isUpperWrapped() && !Other.isUpperWrapped()) + return ConstantRange(maximum(LowerFP, Other.LowerFP), + maximum(UpperFP, Other.UpperFP), + canBeNaN || Other.canBeNaN); + + if (!isUpperWrapped() && Other.isUpperWrapped()) + return Other.fmax(*this); + + // Handle NaN explicitly + if (Other.LowerFP.isNaN()) + return ConstantRange(LowerFP, UpperFP, true); + // If a range is upper wrapped it includes -Inf. + // This results in all numbers from the other range to appear in the results. + if (isUpperWrapped() && !Other.isUpperWrapped()) + return ConstantRange(Other.LowerFP, APFloat::getInf(UpperFP.getSemantics()), + canBeNaN || Other.canBeNaN); + return unionWith(Other); +} + +ConstantRange +ConstantRange::fmin(const ConstantRange &Other) const { + assert(isFloat && Other.isFloat); + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + // X fmin Y is: range(fmin(X_smin, Y_smin), fmin(X_smax, Y_smax)) + if (!isUpperWrapped() && !Other.isUpperWrapped()) + return ConstantRange(minimum(LowerFP, Other.LowerFP), + minimum(UpperFP, Other.UpperFP), + canBeNaN || Other.canBeNaN); + if (!isUpperWrapped() && Other.isUpperWrapped()) + return Other.fmin(*this); + + // Handle NaN explicitly + if (Other.LowerFP.isNaN()) + return ConstantRange(LowerFP, UpperFP, true); + // If a range is upper wrapped it includes Inf. + // This results in all numbers from the other range to appear in the results. + if (isUpperWrapped() && !Other.isUpperWrapped()) + return ConstantRange(APFloat::getInf(UpperFP.getSemantics(), true), + Other.UpperFP, canBeNaN || Other.canBeNaN); + return unionWith(Other); +} + ConstantRange ConstantRange::smax(const ConstantRange &Other) const { // X smax Y is: range(smax(X_smin, Y_smin), // smax(X_smax, Y_smax)) + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); @@ -1001,6 +1607,7 @@ ConstantRange::umax(const ConstantRange &Other) const { // X umax Y is: range(umax(X_umin, Y_umin), // umax(X_umax, Y_umax)) + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); @@ -1012,6 +1619,7 @@ ConstantRange::smin(const ConstantRange &Other) const { // X smin Y is: range(smin(X_smin, Y_smin), // smin(X_smax, Y_smax)) + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin()); @@ -1023,6 +1631,7 @@ ConstantRange::umin(const ConstantRange &Other) const { // X umin Y is: range(umin(X_umin, Y_umin), // umin(X_umax, Y_umax)) + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin()); @@ -1032,6 +1641,7 @@ ConstantRange ConstantRange::udiv(const ConstantRange &RHS) const { + assert(!isFloat); if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue()) return getEmpty(); @@ -1055,6 +1665,7 @@ // We split up the LHS and RHS into positive and negative components // and then also compute the positive and negative components of the result // separately by combining division results with the appropriate signs. + assert(!isFloat); APInt Zero = APInt::getNullValue(getBitWidth()); APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); ConstantRange PosFilter(APInt(getBitWidth(), 1), SignedMin); @@ -1137,6 +1748,7 @@ } ConstantRange ConstantRange::urem(const ConstantRange &RHS) const { + assert(!isFloat); if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue()) return getEmpty(); @@ -1150,6 +1762,7 @@ } ConstantRange ConstantRange::srem(const ConstantRange &RHS) const { + assert(!isFloat); if (isEmptySet() || RHS.isEmptySet()) return getEmpty(); @@ -1193,6 +1806,7 @@ ConstantRange ConstantRange::binaryAnd(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1208,6 +1822,7 @@ ConstantRange ConstantRange::binaryOr(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1235,6 +1850,7 @@ ConstantRange ConstantRange::shl(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1260,6 +1876,7 @@ ConstantRange ConstantRange::lshr(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1270,6 +1887,7 @@ ConstantRange ConstantRange::ashr(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1320,6 +1938,7 @@ } ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1329,6 +1948,7 @@ } ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1338,6 +1958,7 @@ } ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1347,6 +1968,7 @@ } ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1356,6 +1978,7 @@ } ConstantRange ConstantRange::umul_sat(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1365,6 +1988,7 @@ } ConstantRange ConstantRange::smul_sat(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1391,6 +2015,7 @@ } ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1400,6 +2025,7 @@ } ConstantRange ConstantRange::sshl_sat(const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return getEmpty(); @@ -1415,10 +2041,31 @@ return getEmpty(); if (isEmptySet()) return getFull(); - return ConstantRange(Upper, Lower); + + if (!isFloat) + return ConstantRange(Upper, Lower); + + // Handle 'almost full' range + if (LowerFP.isNegative() && LowerFP.isInfinity() && !UpperFP.isNegative() && UpperFP.isInfinity()) + return APFloat::getNaN(LowerFP.getSemantics()); + + APFloat NewLower = UpperFP; + if ((NewLower.isInfinity() && !NewLower.isNegative()) || NewLower.isNaN()) + NewLower = APFloat::getInf(LowerFP.getSemantics(), true); + else + NewLower = ZeroNext(NewLower, false); + + APFloat NewUpper = LowerFP; + if ((NewUpper.isInfinity() && NewUpper.isNegative()) || NewUpper.isNaN()) + NewUpper = APFloat::getInf(UpperFP.getSemantics(), false); + else + NewUpper = ZeroNext(NewUpper, true); + + return ConstantRange(::std::move(NewLower), ::std::move(NewUpper), !canBeNaN); } ConstantRange ConstantRange::abs() const { + assert(!isFloat); if (isEmptySet()) return getEmpty(); @@ -1451,6 +2098,7 @@ ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow( const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return OverflowResult::MayOverflow; @@ -1467,6 +2115,7 @@ ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow( const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return OverflowResult::MayOverflow; @@ -1497,6 +2146,7 @@ ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow( const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return OverflowResult::MayOverflow; @@ -1513,6 +2163,7 @@ ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow( const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return OverflowResult::MayOverflow; @@ -1543,6 +2194,7 @@ ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow( const ConstantRange &Other) const { + assert(!isFloat); if (isEmptySet() || Other.isEmptySet()) return OverflowResult::MayOverflow; @@ -1563,11 +2215,21 @@ void ConstantRange::print(raw_ostream &OS) const { if (isFullSet()) - OS << "full-set"; + OS << (isFloat ? "full-set-fp" : "full-set"); else if (isEmptySet()) - OS << "empty-set"; + OS << (isFloat ? "empty-set-fp" : "empty-set"); else - OS << "[" << Lower << "," << Upper << ")"; + if (isFloat) { + SmallVector Lo, Up; + LowerFP.toString(Lo); + UpperFP.toString(Up); + OS << "[" << Lo << ", " << Up << "]"; + if (LowerFP.bitwiseIsEqual(UpperFP)) + OS << "*"; + if (canBeNaN) + OS << " or NaN"; + } else + OS << "[" << Lower << "," << Upper << ")"; } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) Index: llvm/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/unittests/IR/ConstantRangeTest.cpp +++ llvm/unittests/IR/ConstantRangeTest.cpp @@ -5,6 +5,7 @@ // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// +#include #include "llvm/ADT/BitVector.h" #include "llvm/IR/ConstantRange.h" @@ -24,6 +25,15 @@ static ConstantRange One; static ConstantRange Some; static ConstantRange Wrap; + static ConstantRange NaNFP; + static ConstantRange FullFP; + static ConstantRange EmptyFP; + static ConstantRange OneFP; + static ConstantRange SomeFP; + static ConstantRange ZeroFP; + static ConstantRange NegZeroFP; + static ConstantRange WrapFP; + static ConstantRange InfFP; }; template @@ -133,12 +143,108 @@ }); } +static APFloat advanceFP(const APFloat &F, unsigned ExpDiff) { + // Check special cases first + if (F.isNegZero()) + return APFloat::getZero(F.getSemantics(), false); + if (F.isPosZero()) + return APFloat::getSmallest(F.getSemantics(), false); + if (F.isNegative() && F.isInfinity()) + return APFloat::getLargest(F.getSemantics(), true); + if (!F.isNegative() && F.isInfinity()) + return APFloat::getInf(F.getSemantics(), true); + + assert(&F.getSemantics() == &APFloat::IEEEsingle()); + APFloat Coef(std::exp2f((127 - ExpDiff))); + if (F.isNegative()) + return F / Coef; + else + return F * Coef; +} + +template +static void EnumerateConstantRangesFP(unsigned ExpDiff, Fn TestFn) { + APFloat PosInf = APFloat::getInf(APFloat::IEEEsingle(), false); + APFloat NegInf = APFloat::getInf(APFloat::IEEEsingle(), true); + for (APFloat Lo = NegInf; Lo < PosInf; Lo = advanceFP(Lo, ExpDiff)) { + for (APFloat Hi = NegInf; Hi < PosInf; Hi = advanceFP(Hi, ExpDiff)) { + // Test with NaN + ConstantRange CR1(Lo, Hi, true); + TestFn(CR1); + // Test without NaN + ConstantRange CR2(Lo, Hi, false); + TestFn(CR2); + } + // Test PosInf with NaN + ConstantRange CR1(Lo, PosInf, true); + TestFn(CR1); + // Test PosInf without NaN + ConstantRange CR2(Lo, PosInf, false); + TestFn(CR2); + } + // Lo == PosInf is not enumerated above + for (APFloat Hi = NegInf; Hi < PosInf; Hi = advanceFP(Hi, ExpDiff)) { + // Test with NaN + ConstantRange CR1(PosInf, Hi, true); + TestFn(CR1); + // Test without NaN + ConstantRange CR2(PosInf, Hi, false); + TestFn(CR2); + } + // Lo == PosInf, Hi == PosInf + // Test with NaN + ConstantRange CR1(PosInf, PosInf, true); + TestFn(CR1); + // Test without NaN + ConstantRange CR2(PosInf, PosInf, false); + TestFn(CR2); + + // Test only NaN + APFloat NaN = APFloat::getNaN(APFloat::IEEEsingle()); + ConstantRange CR3(NaN, NaN, true); + TestFn(CR3); +} + +template +static void EnumerateTwoConstantRangesFP(unsigned ExpDiff, Fn TestFn) { + EnumerateConstantRangesFP(ExpDiff, [&](const ConstantRange &CR1) { + EnumerateConstantRangesFP(ExpDiff, [&](const ConstantRange &CR2) { + TestFn(CR1, CR2); + }); + }); +} + +template +static void ForeachNumInConstantRangeFP(const ConstantRange &CR, unsigned ExpDiff, Fn TestFn) { + if (!CR.isEmptySet()) { + APFloat N = CR.getLowerFP(); + for (;!N.bitwiseIsEqual(CR.getUpperFP()); N = advanceFP(N, ExpDiff)) { + TestFn(N); + } + // Test the upper bound + TestFn(CR.getUpperFP()); + // Test NaN if it's allowed in the range + if (CR.getCanBeNaN()) + TestFn(APFloat::getNaN(N.getSemantics())); + } +} + ConstantRange ConstantRangeTest::Full(16, true); ConstantRange ConstantRangeTest::Empty(16, false); ConstantRange ConstantRangeTest::One(APInt(16, 0xa)); ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa)); ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa)); +ConstantRange ConstantRangeTest::NaNFP(APFloat::getNaN(APFloat::IEEEsingle()), APFloat::getNaN(APFloat::IEEEsingle()), true); +ConstantRange ConstantRangeTest::EmptyFP(APFloat::getNaN(APFloat::IEEEsingle()), APFloat::getNaN(APFloat::IEEEsingle()), false); +ConstantRange ConstantRangeTest::FullFP(APFloat::getInf(APFloat::IEEEsingle(), true), APFloat::getInf(APFloat::IEEEsingle(), false), true); +ConstantRange ConstantRangeTest::OneFP(APFloat(10.0f)); +ConstantRange ConstantRangeTest::ZeroFP(APFloat(0.0f)); +ConstantRange ConstantRangeTest::NegZeroFP(APFloat(-0.0f)); +ConstantRange ConstantRangeTest::SomeFP(APFloat(10.0f), APFloat(100.0f), false); +ConstantRange ConstantRangeTest::WrapFP(APFloat(100.0f), APFloat(10.0f), false); +ConstantRange ConstantRangeTest::InfFP(APFloat::getInf(APFloat::IEEEsingle(), true), APFloat::getInf(APFloat::IEEEsingle(), false), false); + TEST_F(ConstantRangeTest, Basics) { EXPECT_TRUE(Full.isFullSet()); EXPECT_FALSE(Full.isEmptySet()); @@ -189,6 +295,107 @@ EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa))); } +TEST_F(ConstantRangeTest, BasicsFP) { + EXPECT_TRUE(FullFP.isFullSet()); + EXPECT_FALSE(FullFP.isEmptySet()); + EXPECT_TRUE(FullFP.getIsFloat()); + EXPECT_TRUE(FullFP.getCanBeNaN()); + EXPECT_FALSE(FullFP.isWrappedSet()); + EXPECT_TRUE(FullFP.inverse().isEmptySet()); + EXPECT_TRUE(FullFP.contains(APFloat(0.0f))); + EXPECT_TRUE(FullFP.contains(APFloat(0.9f))); + EXPECT_TRUE(FullFP.contains(APFloat(10.0f))); + EXPECT_TRUE(FullFP.contains(APFloat(1000.0f))); + EXPECT_TRUE(FullFP.contains(APFloat(-1000.0f))); + EXPECT_TRUE(FullFP.contains(APFloat::getNaN(APFloat::IEEEsingle()))); + EXPECT_TRUE(FullFP.contains(APFloat::getInf(APFloat::IEEEsingle(), true))); + EXPECT_TRUE(FullFP.contains(APFloat::getInf(APFloat::IEEEsingle(), false))); + + EXPECT_FALSE(EmptyFP.isFullSet()); + EXPECT_TRUE(EmptyFP.isEmptySet()); + EXPECT_TRUE(EmptyFP.getIsFloat()); + EXPECT_TRUE(EmptyFP.inverse().isFullSet()); + EXPECT_FALSE(EmptyFP.getCanBeNaN()); + EXPECT_FALSE(Empty.isWrappedSet()); + EXPECT_FALSE(EmptyFP.contains(APFloat(0.0f))); + EXPECT_FALSE(EmptyFP.contains(APFloat(9.0f))); + EXPECT_FALSE(EmptyFP.contains(APFloat(10.0f))); + EXPECT_FALSE(EmptyFP.contains(APFloat(1000.0f))); + EXPECT_FALSE(EmptyFP.contains(APFloat(-1000.0f))); + EXPECT_FALSE(EmptyFP.contains(NaNFP)); + EXPECT_FALSE(EmptyFP.contains(APFloat::getInf(APFloat::IEEEsingle(), true))); + EXPECT_FALSE(EmptyFP.contains(APFloat::getInf(APFloat::IEEEsingle(), false))); + + EXPECT_FALSE(OneFP.isFullSet()); + EXPECT_FALSE(OneFP.isEmptySet()); + EXPECT_TRUE(OneFP.getIsFloat()); + EXPECT_TRUE(OneFP.isSingleElementFP()); + EXPECT_FALSE(OneFP.getCanBeNaN()); + EXPECT_FALSE(OneFP.isWrappedSet()); + EXPECT_FALSE(OneFP.contains(APFloat(0.0f))); + EXPECT_FALSE(OneFP.contains(APFloat(0.0f))); + EXPECT_TRUE(OneFP.contains(APFloat(10.0f))); + EXPECT_FALSE(OneFP.inverse().contains(APFloat(10.0f))); + EXPECT_FALSE(OneFP.contains(APFloat(1000.0f))); + EXPECT_FALSE(OneFP.contains(APFloat(-1000.0f))); + EXPECT_FALSE(OneFP.contains(NaNFP)); + EXPECT_FALSE(OneFP.contains(APFloat::getInf(APFloat::IEEEsingle(), true))); + EXPECT_FALSE(OneFP.contains(APFloat::getInf(APFloat::IEEEsingle(), false))); + + EXPECT_FALSE(ZeroFP.contains(APFloat(-0.0f))); + EXPECT_FALSE(NegZeroFP.contains(APFloat(0.0f))); + EXPECT_TRUE(ZeroFP.contains(APFloat(0.0f))); + EXPECT_TRUE(NegZeroFP.contains(APFloat(-0.0f))); + + EXPECT_FALSE(SomeFP.isFullSet()); + EXPECT_FALSE(SomeFP.isEmptySet()); + EXPECT_TRUE(SomeFP.getIsFloat()); + EXPECT_FALSE(SomeFP.getCanBeNaN()); + EXPECT_FALSE(SomeFP.isWrappedSet()); + EXPECT_FALSE(SomeFP.contains(APFloat(0.0f))); + EXPECT_FALSE(SomeFP.contains(APFloat(9.0f))); + EXPECT_TRUE(SomeFP.contains(APFloat(10.0f))); + EXPECT_TRUE(SomeFP.contains(APFloat(100.0f))); + EXPECT_FALSE(SomeFP.contains(APFloat(10000.0f))); + EXPECT_FALSE(SomeFP.contains(NaNFP)); + EXPECT_FALSE(SomeFP.contains(APFloat::getInf(APFloat::IEEEsingle(), true))); + EXPECT_FALSE(SomeFP.contains(APFloat::getInf(APFloat::IEEEsingle(), false))); + + EXPECT_FALSE(WrapFP.isFullSet()); + EXPECT_FALSE(WrapFP.isEmptySet()); + EXPECT_TRUE(WrapFP.getIsFloat()); + EXPECT_FALSE(WrapFP.getCanBeNaN()); + EXPECT_TRUE(WrapFP.isWrappedSet()); + EXPECT_TRUE(WrapFP.contains(APFloat(0.0f))); + EXPECT_TRUE(WrapFP.contains(APFloat(9.0f))); + EXPECT_FALSE(WrapFP.contains(APFloat(10.1f))); + EXPECT_FALSE(WrapFP.contains(APFloat(99.9f))); + EXPECT_TRUE(WrapFP.contains(APFloat(1000.0f))); + EXPECT_FALSE(WrapFP.contains(NaNFP)); + EXPECT_TRUE(WrapFP.contains(APFloat::getInf(APFloat::IEEEsingle(), true))); + EXPECT_TRUE(WrapFP.contains(APFloat::getInf(APFloat::IEEEsingle(), false))); + + EXPECT_FALSE(NaNFP.isFullSet()); + EXPECT_FALSE(NaNFP.isEmptySet()); + EXPECT_TRUE(NaNFP.getCanBeNaN()); + EXPECT_TRUE(NaNFP.getIsFloat()); + EXPECT_TRUE(NaNFP.isSingleElementFP()); + EXPECT_TRUE(NaNFP.getSingleElementFP()->isNaN()); + EXPECT_FALSE(NaNFP.inverse().getCanBeNaN()); + EXPECT_TRUE(NaNFP.inverse().contains(APFloat::getInf(APFloat::IEEEsingle(), false))); + EXPECT_TRUE(NaNFP.inverse().contains(APFloat::getInf(APFloat::IEEEsingle(), true))); + EXPECT_TRUE(NaNFP.inverse().contains(APFloat(0.0f))); + EXPECT_FALSE(NaNFP.isWrappedSet()); + EXPECT_FALSE(NaNFP.contains(APFloat(0.0f))); + EXPECT_FALSE(NaNFP.contains(APFloat(9.0f))); + EXPECT_FALSE(NaNFP.contains(APFloat(10.0f))); + EXPECT_FALSE(NaNFP.contains(APFloat(100.0f))); + EXPECT_FALSE(NaNFP.contains(APFloat(1000.0f))); + EXPECT_TRUE(NaNFP.contains(APFloat::getNaN(APFloat::IEEEsingle()))); + EXPECT_FALSE(NaNFP.contains(APFloat::getInf(APFloat::IEEEsingle(), true))); + EXPECT_FALSE(NaNFP.contains(APFloat::getInf(APFloat::IEEEsingle(), false))); +} + TEST_F(ConstantRangeTest, Equality) { EXPECT_EQ(Full, Full); EXPECT_EQ(Empty, Empty); @@ -207,6 +414,29 @@ EXPECT_NE(Some, Wrap); } +TEST_F(ConstantRangeTest, EqualityFP) { + EXPECT_EQ(FullFP, FullFP); + EXPECT_EQ(EmptyFP, EmptyFP); + EXPECT_EQ(OneFP, OneFP); + EXPECT_EQ(SomeFP, SomeFP); + EXPECT_EQ(WrapFP, WrapFP); + EXPECT_EQ(NaNFP, NaNFP); + EXPECT_NE(FullFP, EmptyFP); + EXPECT_NE(FullFP, OneFP); + EXPECT_NE(FullFP, SomeFP); + EXPECT_NE(FullFP, WrapFP); + EXPECT_NE(FullFP, NaNFP); + EXPECT_NE(EmptyFP, OneFP); + EXPECT_NE(EmptyFP, SomeFP); + EXPECT_NE(EmptyFP, WrapFP); + EXPECT_NE(EmptyFP, NaNFP); + EXPECT_NE(OneFP, SomeFP); + EXPECT_NE(OneFP, WrapFP); + EXPECT_NE(OneFP, NaNFP); + EXPECT_NE(SomeFP, WrapFP); + EXPECT_NE(SomeFP, NaNFP); +} + TEST_F(ConstantRangeTest, SingleElement) { EXPECT_EQ(Full.getSingleElement(), static_cast(nullptr)); EXPECT_EQ(Empty.getSingleElement(), static_cast(nullptr)); @@ -230,6 +460,15 @@ EXPECT_FALSE(Wrap.isSingleElement()); } +TEST_F(ConstantRangeTest, SingleElementFP) { + EXPECT_EQ(FullFP.getSingleElementFP(), static_cast(nullptr)); + EXPECT_EQ(EmptyFP.getSingleElementFP(), static_cast(nullptr)); + + EXPECT_EQ(*OneFP.getSingleElementFP(), APFloat(10.0f)); + EXPECT_EQ(SomeFP.getSingleElementFP(), static_cast(nullptr)); + EXPECT_EQ(WrapFP.getSingleElementFP(), static_cast(nullptr)); +} + TEST_F(ConstantRangeTest, GetMinsAndMaxes) { EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX)); EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa)); @@ -295,6 +534,16 @@ EXPECT_TRUE(CR2.isUpperSignWrapped()); } +TEST_F(ConstantRangeTest, UpperWrappedFP) { + // The behavior here is the same as for isWrappedSet() / isSignWrappedSet(). + EXPECT_FALSE(FullFP.isUpperWrapped()); + EXPECT_FALSE(EmptyFP.isUpperWrapped()); + EXPECT_FALSE(OneFP.isUpperWrapped()); + EXPECT_FALSE(SomeFP.isUpperWrapped()); + EXPECT_TRUE(WrapFP.isUpperWrapped()); + EXPECT_FALSE(NaNFP.isUpperWrapped()); +} + TEST_F(ConstantRangeTest, Trunc) { ConstantRange TFull = Full.truncate(10); ConstantRange TEmpty = Empty.truncate(10); @@ -425,6 +674,74 @@ EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0))); } +TEST_F(ConstantRangeTest, IntersectWithFP) { + EXPECT_EQ(EmptyFP.intersectWith(FullFP), EmptyFP); + EXPECT_EQ(EmptyFP.intersectWith(EmptyFP), EmptyFP); + EXPECT_EQ(EmptyFP.intersectWith(OneFP), EmptyFP); + EXPECT_EQ(EmptyFP.intersectWith(SomeFP), EmptyFP); + EXPECT_EQ(EmptyFP.intersectWith(WrapFP), EmptyFP); + EXPECT_EQ(EmptyFP.intersectWith(NaNFP), EmptyFP); + EXPECT_EQ(FullFP.intersectWith(FullFP), FullFP); + EXPECT_EQ(FullFP.intersectWith(OneFP), OneFP); + EXPECT_EQ(FullFP.intersectWith(SomeFP), SomeFP); + EXPECT_EQ(FullFP.intersectWith(NaNFP), NaNFP); + EXPECT_EQ(SomeFP.intersectWith(SomeFP), SomeFP); + EXPECT_EQ(SomeFP.intersectWith(OneFP), OneFP); + EXPECT_EQ(SomeFP.intersectWith(WrapFP), SomeFP); + EXPECT_EQ(SomeFP.intersectWith(NaNFP), EmptyFP); + EXPECT_EQ(OneFP.intersectWith(WrapFP), OneFP); + EXPECT_EQ(OneFP.intersectWith(WrapFP), WrapFP.intersectWith(OneFP)); + EXPECT_EQ(OneFP.intersectWith(NaNFP), EmptyFP); + EXPECT_EQ(NaNFP.intersectWith(NaNFP), NaNFP); + + // Klee generated testcase from PR4545, float version. + // The intersection of [4, 2] and [6, 5] is disjoint, looking like + // [-Inf, 2] \/ [4, 5] \/ [6, Inf]. + ConstantRange LHS(APFloat(4.0f), APFloat(2.0f)); + ConstantRange RHS(APFloat(6.0f), APFloat(5.0f)); + EXPECT_TRUE(LHS.intersectWith(RHS) == LHS); + + // Intersection of [-Inf, 3] and [2, Inf] should be [2, 3] + LHS = ConstantRange(APFloat::getInf(APFloat::IEEEsingle(), true), APFloat(3.0f)); + RHS = ConstantRange(APFloat(2.0f), APFloat::getInf(APFloat::IEEEsingle())); + EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APFloat(2.0f), APFloat(3.0f))); + + // Intersection of [-Inf, -0.0] and [0.0, Inf] should be empty + LHS = ConstantRange(APFloat::getInf(APFloat::IEEEsingle(), true), APFloat(-0.0f)); + RHS = ConstantRange(APFloat(0.0f), APFloat::getInf(APFloat::IEEEsingle())); + EXPECT_EQ(LHS.intersectWith(RHS), EmptyFP); + + // [2, 0] /\ [4, 3] = [2, 0] + LHS = ConstantRange(APFloat(2.0f), APFloat(0.0f)); + RHS = ConstantRange(APFloat(4.0f), APFloat(3.0f)); + EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APFloat(2.0f), APFloat(0.0f))); + + // [3, 0] /\ [4, 2] = [4, 0] + LHS = ConstantRange(APFloat(3.0f), APFloat(0.0f)); + RHS = ConstantRange(APFloat(4.0f), APFloat(2.0f)); + EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APFloat(4.0f), APFloat(0.0f))); + + // [4, 2] /\ [5, 1] = [5, 1] + LHS = ConstantRange(APFloat(4.0f), APFloat(2.0f)); + RHS = ConstantRange(APFloat(5.0f), APFloat(1.0f)); + EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APFloat(5.0f), APFloat(1.0f))); + + // [2, 0] /\ [7, 4] = [7, 4] + LHS = ConstantRange(APFloat(2.0f), APFloat(0.0f)); + RHS = ConstantRange(APFloat(7.0f), APFloat(4.0f)); + EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APFloat(7.0f), APFloat(4.0f))); + + // [4, 2] /\ [1, 0] = [1, 0] + LHS = ConstantRange(APFloat(4.0f), APFloat(2.0f)); + RHS = ConstantRange(APFloat(1.0f), APFloat(0.0f)); + EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APFloat(4.0f), APFloat(2.0f))); + + // [15, 0] /\ [7, 6] = [15, 0] + LHS = ConstantRange(APFloat(15.0f), APFloat(0.0f)); + RHS = ConstantRange(APFloat(7.0f), APFloat(6.0f)); + EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APFloat(15.0f), APFloat(0.0f))); +} + template void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 InResultFn) { unsigned Bits = 4; @@ -564,6 +881,28 @@ }); } +TEST_F(ConstantRangeTest, IntersectWithExhaustiveFP) { + unsigned ExpDiff = 2; + ConstantRange Full(APFloat::getInf(APFloat::IEEEsingle(), true), + APFloat::getInf(APFloat::IEEEsingle(), false), true); + EnumerateTwoConstantRangesFP(ExpDiff, + [=](const ConstantRange &CR1, const ConstantRange &CR2) { + ConstantRange Res = CR1.intersectWith(CR2); + + ForeachNumInConstantRangeFP(Full, ExpDiff, [&](const APFloat &N) { + // UpperWrapped operands lead to disjoint ranges check that result + // is a super-set. + if (CR1.isUpperWrapped() || CR2.isUpperWrapped()) { + if (CR1.contains(N) && CR2.contains(N) && !Res.contains(N)) + ADD_FAILURE() << "FAILURE AT: " << N.convertToFloat() << "\n"; + } else { + if (Res.contains(N) != (CR1.contains(N) && CR2.contains(N))) + ADD_FAILURE() << "FAILURE AT: " << N.convertToFloat() << "\n"; + } + }); + }); +} + TEST_F(ConstantRangeTest, UnionWithExhaustive) { testBinarySetOperationExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2, @@ -575,6 +914,30 @@ }); } +TEST_F(ConstantRangeTest, UnionWithExhaustiveFP) { + unsigned ExpDiff = 2; + ConstantRange Full(APFloat::getInf(APFloat::IEEEsingle(), true), + APFloat::getInf(APFloat::IEEEsingle(), false), true); + EnumerateTwoConstantRangesFP(ExpDiff, + [=](const ConstantRange &CR1, const ConstantRange &CR2) { + ConstantRange Res = CR1.unionWith(CR2); + + ForeachNumInConstantRangeFP(Full, ExpDiff, [&](const APFloat &N) { + // Non-upperWrapped operands lead to disjoint ranges check that + // result is a super-set. + bool InSources = CR1.contains(N) || CR2.contains(N); + bool InResult = Res.contains(N); + if (!CR1.isUpperWrapped() || !CR2.isUpperWrapped()) { + if (InSources && !InResult) + ADD_FAILURE() << "FAILURE AT: " << N.convertToFloat() << "\n"; + } else { + if (InResult != InSources) + ADD_FAILURE() << "FAILURE AT: " << N.convertToFloat() << "\n"; + } + }); + }); +} + TEST_F(ConstantRangeTest, UnionWith) { EXPECT_EQ(Wrap.unionWith(One), ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb))); @@ -595,6 +958,47 @@ ConstantRange::getFull(16)); } +TEST_F(ConstantRangeTest, UnionWithFP) { + EXPECT_EQ(WrapFP.unionWith(OneFP), WrapFP); + EXPECT_EQ(OneFP.unionWith(WrapFP), WrapFP.unionWith(OneFP)); + EXPECT_EQ(EmptyFP.unionWith(EmptyFP), EmptyFP); + EXPECT_EQ(FullFP.unionWith(FullFP), FullFP); + EXPECT_EQ(SomeFP.unionWith(WrapFP), ConstantRange::getFull(APFloat::IEEEsingle(), false)); + EXPECT_EQ(OneFP.unionWith(NaNFP), NaNFP.unionWith(OneFP)); + EXPECT_EQ(SomeFP.unionWith(NaNFP), NaNFP.unionWith(SomeFP)); + EXPECT_EQ(WrapFP.unionWith(NaNFP), NaNFP.unionWith(WrapFP)); + EXPECT_TRUE(OneFP.unionWith(NaNFP).getCanBeNaN()); + EXPECT_FALSE(OneFP.unionWith(NaNFP).isSingleElementFP()); + EXPECT_TRUE(SomeFP.unionWith(NaNFP).getCanBeNaN()); + EXPECT_TRUE(WrapFP.unionWith(NaNFP).getCanBeNaN()); + EXPECT_TRUE(OneFP.unionWith(NaNFP).contains(APFloat::getNaN(APFloat::IEEEsingle()))); + EXPECT_TRUE(SomeFP.unionWith(NaNFP).contains(APFloat::getNaN(APFloat::IEEEsingle()))); + EXPECT_TRUE(WrapFP.unionWith(NaNFP).contains(APFloat::getNaN(APFloat::IEEEsingle()))); + + EXPECT_EQ(ConstantRange(APFloat(14.0f), APFloat(1.0f)).unionWith( + ConstantRange(APFloat(1.0f), APFloat(8.0f))), + ConstantRange(APFloat(14.0f), APFloat(8.0f))); + EXPECT_EQ(ConstantRange(APFloat(6.0f), APFloat(4.0f)).unionWith( + ConstantRange(APFloat(4.0f), APFloat(0.0f))), + ConstantRange::getFull(APFloat::IEEEsingle(), false)); + EXPECT_EQ(ConstantRange(APFloat(1.0f), APFloat(0.0f)).unionWith( + ConstantRange(APFloat(2.0f), APFloat(1.0f))), + ConstantRange::getFull(APFloat::IEEEsingle(), false)); +} + +TEST_F(ConstantRangeTest, InverseExhaustiveFP) { + unsigned ExpDiff = 2; + ConstantRange Full(APFloat::getInf(APFloat::IEEEsingle(), true), + APFloat::getInf(APFloat::IEEEsingle(), false), true); + EnumerateConstantRangesFP(ExpDiff, [&](const ConstantRange &CR) { + ConstantRange Res = CR.inverse(); + ForeachNumInConstantRangeFP(Full, ExpDiff, [&](const APFloat &N) { + if (CR.contains(N) == Res.contains(N)) + ADD_FAILURE() << "FAILURE AT: " << N.convertToFloat() << "\n"; + }); + }); +} + TEST_F(ConstantRangeTest, SetDifference) { EXPECT_EQ(Full.difference(Empty), Full); EXPECT_EQ(Full.difference(Full), Empty); @@ -612,6 +1016,26 @@ EXPECT_EQ(E.difference(A), F); } +TEST_F(ConstantRangeTest, SetDifferenceFP) { + EXPECT_EQ(FullFP.difference(EmptyFP), FullFP); + EXPECT_EQ(FullFP.difference(FullFP), EmptyFP); + EXPECT_EQ(EmptyFP.difference(EmptyFP), EmptyFP); + EXPECT_EQ(EmptyFP.difference(FullFP), EmptyFP); + + auto N7U = APFloat(7.0f); N7U.next(false); + auto N3D = APFloat(3.0f); N3D.next(true); + auto N5D = APFloat(5.0f); N5D.next(true); + ConstantRange A(APFloat(3.0f), APFloat(7.0f)); + ConstantRange B(APFloat(5.0f), APFloat(9.0f)); + ConstantRange C(APFloat(3.0f), N5D); + ConstantRange D(N7U, APFloat(9.0f)); + ConstantRange E(APFloat(5.0f), APFloat(4.0f)); + ConstantRange F(N7U, N3D); + EXPECT_EQ(A.difference(B), C); + EXPECT_EQ(B.difference(A), D); + EXPECT_EQ(E.difference(A), F); +} + TEST_F(ConstantRangeTest, SubtractAPInt) { EXPECT_EQ(Full.subtract(APInt(16, 4)), Full); EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty); @@ -643,6 +1067,146 @@ ConstantRange(APInt(16, 0xe))); } +TEST_F(ConstantRangeTest, AddFP) { + EXPECT_EQ(FullFP.fadd(APFloat(4.0f)), FullFP); + EXPECT_EQ(FullFP.fadd(FullFP), FullFP); + EXPECT_EQ(FullFP.fadd(EmptyFP), EmptyFP); + EXPECT_EQ(FullFP.fadd(OneFP), FullFP); + EXPECT_EQ(FullFP.fadd(SomeFP), FullFP); + EXPECT_EQ(FullFP.fadd(WrapFP), FullFP); + EXPECT_EQ(EmptyFP.fadd(EmptyFP), EmptyFP); + EXPECT_EQ(EmptyFP.fadd(OneFP), EmptyFP); + EXPECT_EQ(EmptyFP.fadd(SomeFP), EmptyFP); + EXPECT_EQ(EmptyFP.fadd(WrapFP), EmptyFP); + EXPECT_EQ(EmptyFP.fadd(APFloat(4.0f)), EmptyFP); + EXPECT_EQ(SomeFP.fadd(APFloat(4.0f)), + ConstantRange(APFloat(14.0f), APFloat(104.0f))); + EXPECT_EQ(WrapFP.fadd(APFloat(4.0f)), InfFP); + EXPECT_EQ(OneFP.fadd(APFloat(4.0f)), + ConstantRange(APFloat(14.0f))); +} + +template +static void TestFPBinOpExhaustive( + Fn1 RangeFn, Fn2 FloatFn, bool CorrectnessOnly = false) { + unsigned ExpDiff = 1; + APFloat NaN = APFloat::getNaN(APFloat::IEEEsingle()); + APFloat PosInf = APFloat::getInf(APFloat::IEEEsingle()); + APFloat NegInf = APFloat::getInf(APFloat::IEEEsingle(), true); + + EnumerateTwoConstantRangesFP(ExpDiff, [&](const ConstantRange &CR1, + const ConstantRange &CR2) { + SmallVector Ranges1; + SmallVector Ranges2; + SmallVector ExactRanges; + + // Split upperWrapped ranges into pos and neg part and test separately + if (CR1.isUpperWrapped()) { + Ranges1.push_back({CR1.getLowerFP(), PosInf, CR1.getCanBeNaN()}); + Ranges1.push_back({NegInf, CR1.getUpperFP(), CR1.getCanBeNaN()}); + } else { + Ranges1.push_back(CR1); + } + if (CR2.isUpperWrapped()) { + Ranges2.push_back({CR2.getLowerFP(), PosInf, CR2.getCanBeNaN()}); + Ranges2.push_back({NegInf, CR2.getUpperFP(), CR2.getCanBeNaN()}); + } else { + Ranges2.push_back(CR2); + } + + + for (const auto &R1:Ranges1) + for (const auto &R2:Ranges2) { + APFloat Min = NaN; + APFloat Max = NaN; + bool canBeNaN = R1.getCanBeNaN() || R2.getCanBeNaN(); + ForeachNumInConstantRangeFP(R1, ExpDiff, [&](const APFloat &N1) { + ForeachNumInConstantRangeFP(R2, ExpDiff, [&](const APFloat &N2) { + APFloat N = FloatFn(N1, N2); + Min = minnum(Min, N); + Max = maxnum(Max, N); + if (N.isNaN()) + canBeNaN = true; + }); + }); + ExactRanges.push_back({Min, Max, canBeNaN}); + } + + ConstantRange CR = RangeFn(CR1, CR2); + + bool ExactNaN = false; + for (const auto &Exact: ExactRanges) { + if (Exact.getCanBeNaN()) + ExactNaN = true; + if (!CR.contains(Exact)) + ADD_FAILURE() << "FAILED: \n"; + } + // Check that we don't unnecesarilly include NaN + EXPECT_EQ(CR.getCanBeNaN(), ExactNaN); + }); +} + + +TEST_F(ConstantRangeTest, AddFPExhaustive) { + TestFPBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.fadd(CR2); + }, + [](const APFloat &X, const APFloat &Y) { + return X + Y; + }); +} + +TEST_F(ConstantRangeTest, SubFPExhaustive) { + TestFPBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.fsub(CR2); + }, + [](const APFloat &X, const APFloat &Y) { + return X - Y; + }); +} + +TEST_F(ConstantRangeTest, MulFPExhaustive) { + TestFPBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.fmultiply(CR2); + }, + [](const APFloat &X, const APFloat &Y) { + return X * Y; + }); +} + +TEST_F(ConstantRangeTest, DivFPExhaustive) { + TestFPBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.fdivide(CR2); + }, + [](const APFloat &X, const APFloat &Y) { + return X / Y; + }); +} + +TEST_F(ConstantRangeTest, MaximumFPExhaustive) { + TestFPBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.fmax(CR2); + }, + [](const APFloat &X, const APFloat &Y) { + return maximum(X, Y); + }); +} + +TEST_F(ConstantRangeTest, MinimumFPExhaustive) { + TestFPBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.fmin(CR2); + }, + [](const APFloat &X, const APFloat &Y) { + return minimum(X, Y); + }); +} + template static void TestAddWithNoSignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) { unsigned Bits = 4; @@ -1355,6 +1919,287 @@ APInt(16, 0xfffe, true))); } +template +static void TestFPCompExhaustive(Fn1 RangeFn, Fn2 FloatFn, Fn3 CombFn, bool Init) { + unsigned ExpDiff = 105; + ConstantRange FullCR = ConstantRange::getFull(APFloat::IEEEsingle()); + EnumerateConstantRangesFP(ExpDiff, [&](const ConstantRange &CR) { + ConstantRange ResCR = RangeFn(CR); + ForeachNumInConstantRangeFP(FullCR, ExpDiff, [&](const APFloat &LHS) { + bool ResVal = Init; + // Compare against all values in the original ConstantRange + ForeachNumInConstantRangeFP(CR, ExpDiff, [&](const APFloat &RHS) { + ResVal = CombFn(ResVal, FloatFn(LHS, RHS)); + }); + EXPECT_EQ(ResVal, ResCR.contains(LHS)); + }); + }); +} + +template +static void TestFPCompExhaustiveAllowed(Fn1 RangeFn, Fn2 FloatFn) { + TestFPCompExhaustive( + RangeFn, FloatFn, [](bool a, bool b){ return a || b; }, false); +} + +TEST(ConstantRange, MakeAllowedFCmpOrdRegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_ORD, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN(); } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpUnoRegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_UNO, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN(); } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpOEQRegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_OEQ, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS == RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpUEQRegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_UEQ, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS == RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpONERegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_ONE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS != RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpUNERegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_UNE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS != RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpOGTRegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_OGT, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS > RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpUGTRegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_UGT, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS > RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpOLTRegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_OLT, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS < RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpULTRegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_ULT, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS < RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpOGERegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_OGE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS >= RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpUGERegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_UGE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS >= RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpOLERegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_OLE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS <= RHS; } + ); +} + +TEST(ConstantRange, MakeAllowedFCmpULERegion) { + TestFPCompExhaustiveAllowed( + [](const ConstantRange &CR) { + return ConstantRange::makeAllowedFCmpRegion(CmpInst::FCMP_ULE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS <= RHS; } + ); +} + +template +static void TestFPCompExhaustiveSatisfying(Fn1 RangeFn, Fn2 FloatFn) { + TestFPCompExhaustive( + RangeFn, FloatFn, [](bool a, bool b){ return a && b; }, true); +} + +TEST(ConstantRange, MakeSatisfyingFCmpOrdRegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_ORD, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN(); } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpUnoRegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_UNO, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN(); } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpOEQRegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_OEQ, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS == RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpUEQRegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_UEQ, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS == RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpONERegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_ONE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS != RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpUNERegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_UNE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS != RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpOGTRegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_OGT, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS > RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpUGTRegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_UGT, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS > RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpOLTRegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_OLT, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS < RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpULTRegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_ULT, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS < RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpOGERegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_OGE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS >= RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpUGERegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_UGE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS >= RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpOLERegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_OLE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return !LHS.isNaN() && !RHS.isNaN() && LHS <= RHS; } + ); +} + +TEST(ConstantRange, MakeSatisfyingFCmpULERegion) { + TestFPCompExhaustiveSatisfying( + [](const ConstantRange &CR) { + return ConstantRange::makeSatisfyingFCmpRegion(CmpInst::FCMP_ULE, CR); }, + [](const APFloat &LHS, const APFloat &RHS) { + return LHS.isNaN() || RHS.isNaN() || LHS <= RHS; } + ); +} + TEST(ConstantRange, MakeAllowedICmpRegion) { // PR8250 ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32)); @@ -2297,17 +3142,46 @@ TEST_F(ConstantRangeTest, castOps) { ConstantRange A(APInt(16, 66), APInt(16, 128)); - ConstantRange FpToI8 = A.castOp(Instruction::FPToSI, 8); + ConstantRange A32(APInt(32, 66), APInt(32, 128)); + ConstantRange AF(APFloat(66.0f), APFloat(128.0f)); + EXPECT_EQ(32u, AF.getBitWidth()); + + EXPECT_TRUE(A.castOp(Instruction::BitCast, APFloat::IEEEhalf()).getIsFloat()); + EXPECT_TRUE(A32.castOp(Instruction::BitCast, APFloat::IEEEsingle()).getIsFloat()); + EXPECT_TRUE(A32.castOp(Instruction::BitCast, APFloat::IEEEsingle()).isFullSet()); + EXPECT_TRUE(AF.castOp(Instruction::BitCast, APFloat::IEEEsingle()).getIsFloat()); + EXPECT_EQ(AF.castOp(Instruction::BitCast, APFloat::IEEEsingle()), AF); + + EXPECT_FALSE(A32.castOp(Instruction::BitCast, 32).getIsFloat()); + EXPECT_FALSE(AF.castOp(Instruction::BitCast, 32).getIsFloat()); + EXPECT_EQ(A32.castOp(Instruction::BitCast, 32), A32); + EXPECT_TRUE(AF.castOp(Instruction::BitCast, 32).isFullSet()); + + ConstantRange FpToI8 = AF.castOp(Instruction::FPToSI, 8); EXPECT_EQ(8u, FpToI8.getBitWidth()); EXPECT_TRUE(FpToI8.isFullSet()); - ConstantRange FpToI16 = A.castOp(Instruction::FPToSI, 16); + ConstantRange FpToI16 = AF.castOp(Instruction::FPToSI, 16); EXPECT_EQ(16u, FpToI16.getBitWidth()); - EXPECT_EQ(A, FpToI16); + EXPECT_TRUE(FpToI16.isFullSet()); + + ConstantRange UI32ToFP32 = A.castOp(Instruction::UIToFP, APFloat::IEEEsingle()); + EXPECT_EQ(32u, UI32ToFP32.getBitWidth()); + EXPECT_TRUE(UI32ToFP32.isFullSet()); - ConstantRange FPExtToDouble = A.castOp(Instruction::FPExt, 64); + ConstantRange SI32ToFP32 = A.castOp(Instruction::SIToFP, APFloat::IEEEsingle()); + EXPECT_EQ(32u, SI32ToFP32.getBitWidth()); + EXPECT_TRUE(SI32ToFP32.isFullSet()); + + ConstantRange FPExtToDouble = AF.castOp(Instruction::FPExt, APFloat::IEEEdouble()); EXPECT_EQ(64u, FPExtToDouble.getBitWidth()); - EXPECT_TRUE(FPExtToDouble.isFullSet()); + EXPECT_EQ(66.0, FPExtToDouble.getLowerFP().convertToDouble()); + EXPECT_EQ(128.0, FPExtToDouble.getUpperFP().convertToDouble()); + + ConstantRange FPTruncToHalf = AF.castOp(Instruction::FPTrunc, APFloat::IEEEhalf()); + EXPECT_EQ(16u, FPTruncToHalf.getBitWidth()); + EXPECT_TRUE(FPTruncToHalf.getLowerFP().isExactlyValue(66.0)); + EXPECT_TRUE(FPTruncToHalf.getUpperFP().isExactlyValue(128.0)); ConstantRange PtrToInt = A.castOp(Instruction::PtrToInt, 64); EXPECT_EQ(64u, PtrToInt.getBitWidth()); @@ -2316,6 +3190,19 @@ ConstantRange IntToPtr = A.castOp(Instruction::IntToPtr, 64); EXPECT_EQ(64u, IntToPtr.getBitWidth()); EXPECT_TRUE(IntToPtr.isFullSet()); + + ConstantRange A128(APInt(128, 66), APInt(128, 128)); + EXPECT_TRUE(A128.castOp(Instruction::BitCast, APFloat::PPCDoubleDouble()).getIsFloat()); + EXPECT_TRUE(A128.castOp(Instruction::BitCast, APFloat::PPCDoubleDouble()).isFullSet()); + EXPECT_EQ(A128.castOp(Instruction::BitCast, 128), A128); + EXPECT_FALSE(A128.castOp(Instruction::BitCast, 128).getIsFloat()); + + ConstantRange AFPPC(APFloat::getZero(APFloat::PPCDoubleDouble()), + APFloat::getInf(APFloat::PPCDoubleDouble())); + EXPECT_EQ(AFPPC.castOp(Instruction::BitCast, APFloat::PPCDoubleDouble()), AFPPC); + EXPECT_TRUE(AFPPC.castOp(Instruction::BitCast, APFloat::PPCDoubleDouble()).getIsFloat()); + EXPECT_FALSE(AFPPC.castOp(Instruction::BitCast, 128).getIsFloat()); + EXPECT_TRUE(AFPPC.castOp(Instruction::BitCast, 128).isFullSet()); } TEST_F(ConstantRangeTest, binaryXor) {