| //===- ConstantRange.cpp - ConstantRange implementation -------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Represent a range of possible values that may occur when the program is run |
| // for an integral value. This keeps track of a lower and upper bound for the |
| // constant, which MAY wrap around the end of the numeric range. To do this, it |
| // keeps track of a [lower, upper) bound, which specifies an interval just like |
| // STL iterators. When used with boolean values, the following are important |
| // ranges (other integral ranges use min/max values for special range values): |
| // |
| // [F, F) = {} = Empty set |
| // [T, F) = {T} |
| // [F, T) = {F} |
| // [T, T) = {F, T} = Full set |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/ADT/APInt.h" |
| #include "llvm/Config/llvm-config.h" |
| #include "llvm/IR/ConstantRange.h" |
| #include "llvm/IR/Constants.h" |
| #include "llvm/IR/InstrTypes.h" |
| #include "llvm/IR/Instruction.h" |
| #include "llvm/IR/Metadata.h" |
| #include "llvm/IR/Operator.h" |
| #include "llvm/Support/Compiler.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/ErrorHandling.h" |
| #include "llvm/Support/KnownBits.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <algorithm> |
| #include <cassert> |
| #include <cstdint> |
| |
| using namespace llvm; |
| |
| ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) |
| : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)), |
| Upper(Lower) {} |
| |
| ConstantRange::ConstantRange(APInt V) |
| : Lower(std::move(V)), Upper(Lower + 1) {} |
| |
| ConstantRange::ConstantRange(APInt L, APInt U) |
| : Lower(std::move(L)), Upper(std::move(U)) { |
| assert(Lower.getBitWidth() == Upper.getBitWidth() && |
| "ConstantRange with unequal bit widths"); |
| assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && |
| "Lower == Upper, but they aren't min or max value!"); |
| } |
| |
| ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known, |
| bool IsSigned) { |
| assert(!Known.hasConflict() && "Expected valid KnownBits"); |
| |
| if (Known.isUnknown()) |
| return getFull(Known.getBitWidth()); |
| |
| // For unsigned ranges, or signed ranges with known sign bit, create a simple |
| // range between the smallest and largest possible value. |
| if (!IsSigned || Known.isNegative() || Known.isNonNegative()) |
| return ConstantRange(Known.One, ~Known.Zero + 1); |
| |
| // If we don't know the sign bit, pick the lower bound as a negative number |
| // and the upper bound as a non-negative one. |
| APInt Lower = Known.One, Upper = ~Known.Zero; |
| Lower.setSignBit(); |
| Upper.clearSignBit(); |
| return ConstantRange(Lower, Upper + 1); |
| } |
| |
| ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, |
| const ConstantRange &CR) { |
| if (CR.isEmptySet()) |
| return CR; |
| |
| uint32_t W = CR.getBitWidth(); |
| switch (Pred) { |
| default: |
| llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()"); |
| case CmpInst::ICMP_EQ: |
| return CR; |
| case CmpInst::ICMP_NE: |
| if (CR.isSingleElement()) |
| return ConstantRange(CR.getUpper(), CR.getLower()); |
| return getFull(W); |
| case CmpInst::ICMP_ULT: { |
| APInt UMax(CR.getUnsignedMax()); |
| if (UMax.isMinValue()) |
| return getEmpty(W); |
| return ConstantRange(APInt::getMinValue(W), std::move(UMax)); |
| } |
| case CmpInst::ICMP_SLT: { |
| APInt SMax(CR.getSignedMax()); |
| if (SMax.isMinSignedValue()) |
| return getEmpty(W); |
| return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax)); |
| } |
| case CmpInst::ICMP_ULE: |
| return getNonEmpty(APInt::getMinValue(W), CR.getUnsignedMax() + 1); |
| case CmpInst::ICMP_SLE: |
| return getNonEmpty(APInt::getSignedMinValue(W), CR.getSignedMax() + 1); |
| case CmpInst::ICMP_UGT: { |
| APInt UMin(CR.getUnsignedMin()); |
| if (UMin.isMaxValue()) |
| return getEmpty(W); |
| return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W)); |
| } |
| case CmpInst::ICMP_SGT: { |
| APInt SMin(CR.getSignedMin()); |
| if (SMin.isMaxSignedValue()) |
| return getEmpty(W); |
| return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W)); |
| } |
| case CmpInst::ICMP_UGE: |
| return getNonEmpty(CR.getUnsignedMin(), APInt::getNullValue(W)); |
| case CmpInst::ICMP_SGE: |
| return getNonEmpty(CR.getSignedMin(), APInt::getSignedMinValue(W)); |
| } |
| } |
| |
| ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred, |
| const ConstantRange &CR) { |
| // Follows from De-Morgan's laws: |
| // |
| // ~(~A union ~B) == A intersect B. |
| // |
| return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR) |
| .inverse(); |
| } |
| |
| ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred, |
| const APInt &C) { |
| // Computes the exact range that is equal to both the constant ranges returned |
| // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true |
| // when RHS is a singleton such as an APInt and so the assert is valid. |
| // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion |
| // returns [0,4) but makeSatisfyICmpRegion returns [0,2). |
| // |
| assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C)); |
| return makeAllowedICmpRegion(Pred, C); |
| } |
| |
| bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred, |
| APInt &RHS) const { |
| bool Success = false; |
| |
| if (isFullSet() || isEmptySet()) { |
| Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE; |
| RHS = APInt(getBitWidth(), 0); |
| Success = true; |
| } else if (auto *OnlyElt = getSingleElement()) { |
| Pred = CmpInst::ICMP_EQ; |
| RHS = *OnlyElt; |
| Success = true; |
| } else if (auto *OnlyMissingElt = getSingleMissingElement()) { |
| Pred = CmpInst::ICMP_NE; |
| RHS = *OnlyMissingElt; |
| Success = true; |
| } else if (getLower().isMinSignedValue() || getLower().isMinValue()) { |
| Pred = |
| getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT; |
| RHS = getUpper(); |
| Success = true; |
| } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) { |
| Pred = |
| getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE; |
| RHS = getLower(); |
| Success = true; |
| } |
| |
| assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) && |
| "Bad result!"); |
| |
| return Success; |
| } |
| |
| /// Exact mul nuw region for single element RHS. |
| static ConstantRange makeExactMulNUWRegion(const APInt &V) { |
| unsigned BitWidth = V.getBitWidth(); |
| if (V == 0) |
| return ConstantRange::getFull(V.getBitWidth()); |
| |
| return ConstantRange::getNonEmpty( |
| APIntOps::RoundingUDiv(APInt::getMinValue(BitWidth), V, |
| APInt::Rounding::UP), |
| APIntOps::RoundingUDiv(APInt::getMaxValue(BitWidth), V, |
| APInt::Rounding::DOWN) + 1); |
| } |
| |
| /// Exact mul nsw region for single element RHS. |
| static ConstantRange makeExactMulNSWRegion(const APInt &V) { |
| // Handle special case for 0, -1 and 1. See the last for reason why we |
| // specialize -1 and 1. |
| unsigned BitWidth = V.getBitWidth(); |
| if (V == 0 || V.isOneValue()) |
| return ConstantRange::getFull(BitWidth); |
| |
| APInt MinValue = APInt::getSignedMinValue(BitWidth); |
| APInt MaxValue = APInt::getSignedMaxValue(BitWidth); |
| // e.g. Returning [-127, 127], represented as [-127, -128). |
| if (V.isAllOnesValue()) |
| return ConstantRange(-MaxValue, MinValue); |
| |
| APInt Lower, Upper; |
| if (V.isNegative()) { |
| Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP); |
| Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN); |
| } else { |
| Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP); |
| Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN); |
| } |
| // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1). |
| // Upper + 1 is guaranteed not to overflow, because |divisor| > 1. 0, -1, |
| // and 1 are already handled as special cases. |
| return ConstantRange(Lower, Upper + 1); |
| } |
| |
| ConstantRange |
| ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, |
| const ConstantRange &Other, |
| unsigned NoWrapKind) { |
| using OBO = OverflowingBinaryOperator; |
| |
| assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!"); |
| |
| assert((NoWrapKind == OBO::NoSignedWrap || |
| NoWrapKind == OBO::NoUnsignedWrap) && |
| "NoWrapKind invalid!"); |
| |
| bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap; |
| unsigned BitWidth = Other.getBitWidth(); |
| |
| switch (BinOp) { |
| default: |
| llvm_unreachable("Unsupported binary op"); |
| |
| case Instruction::Add: { |
| if (Unsigned) |
| return getNonEmpty(APInt::getNullValue(BitWidth), |
| -Other.getUnsignedMax()); |
| |
| APInt SignedMinVal = APInt::getSignedMinValue(BitWidth); |
| APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax(); |
| return getNonEmpty( |
| SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal, |
| SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal); |
| } |
| |
| case Instruction::Sub: { |
| if (Unsigned) |
| return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth)); |
| |
| APInt SignedMinVal = APInt::getSignedMinValue(BitWidth); |
| APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax(); |
| return getNonEmpty( |
| SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal, |
| SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal); |
| } |
| |
| case Instruction::Mul: |
| if (Unsigned) |
| return makeExactMulNUWRegion(Other.getUnsignedMax()); |
| |
| return makeExactMulNSWRegion(Other.getSignedMin()) |
| .intersectWith(makeExactMulNSWRegion(Other.getSignedMax())); |
| |
| case Instruction::Shl: { |
| // For given range of shift amounts, if we ignore all illegal shift amounts |
| // (that always produce poison), what shift amount range is left? |
| ConstantRange ShAmt = Other.intersectWith( |
| ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, (BitWidth - 1) + 1))); |
| if (ShAmt.isEmptySet()) { |
| // If the entire range of shift amounts is already poison-producing, |
| // then we can freely add more poison-producing flags ontop of that. |
| return getFull(BitWidth); |
| } |
| // There are some legal shift amounts, we can compute conservatively-correct |
| // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax |
| // to be at most bitwidth-1, which results in most conservative range. |
| APInt ShAmtUMax = ShAmt.getUnsignedMax(); |
| if (Unsigned) |
| return getNonEmpty(APInt::getNullValue(BitWidth), |
| APInt::getMaxValue(BitWidth).lshr(ShAmtUMax) + 1); |
| return getNonEmpty(APInt::getSignedMinValue(BitWidth).ashr(ShAmtUMax), |
| APInt::getSignedMaxValue(BitWidth).ashr(ShAmtUMax) + 1); |
| } |
| } |
| } |
| |
| ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp, |
| const APInt &Other, |
| unsigned NoWrapKind) { |
| // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as |
| // "for all" and "for any" coincide in this case. |
| return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind); |
| } |
| |
| bool ConstantRange::isFullSet() const { |
| return Lower == Upper && Lower.isMaxValue(); |
| } |
| |
| bool ConstantRange::isEmptySet() const { |
| return Lower == Upper && Lower.isMinValue(); |
| } |
| |
| bool ConstantRange::isWrappedSet() const { |
| return Lower.ugt(Upper) && !Upper.isNullValue(); |
| } |
| |
| bool ConstantRange::isUpperWrapped() const { |
| return Lower.ugt(Upper); |
| } |
| |
| bool ConstantRange::isSignWrappedSet() const { |
| return Lower.sgt(Upper) && !Upper.isMinSignedValue(); |
| } |
| |
| bool ConstantRange::isUpperSignWrapped() const { |
| return Lower.sgt(Upper); |
| } |
| |
| bool |
| ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const { |
| assert(getBitWidth() == Other.getBitWidth()); |
| if (isFullSet()) |
| return false; |
| if (Other.isFullSet()) |
| return true; |
| return (Upper - Lower).ult(Other.Upper - Other.Lower); |
| } |
| |
| bool |
| ConstantRange::isSizeLargerThan(uint64_t MaxSize) const { |
| assert(MaxSize && "MaxSize can't be 0."); |
| // If this a full set, we need special handling to avoid needing an extra bit |
| // to represent the size. |
| if (isFullSet()) |
| return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1); |
| |
| return (Upper - Lower).ugt(MaxSize); |
| } |
| |
| bool ConstantRange::isAllNegative() const { |
| // Empty set is all negative, full set is not. |
| if (isEmptySet()) |
| return true; |
| if (isFullSet()) |
| return false; |
| |
| return !isUpperSignWrapped() && !Upper.isStrictlyPositive(); |
| } |
| |
| bool ConstantRange::isAllNonNegative() const { |
| // Empty and full set are automatically treated correctly. |
| return !isSignWrappedSet() && Lower.isNonNegative(); |
| } |
| |
| APInt ConstantRange::getUnsignedMax() const { |
| if (isFullSet() || isUpperWrapped()) |
| return APInt::getMaxValue(getBitWidth()); |
| return getUpper() - 1; |
| } |
| |
| APInt ConstantRange::getUnsignedMin() const { |
| if (isFullSet() || isWrappedSet()) |
| return APInt::getMinValue(getBitWidth()); |
| return getLower(); |
| } |
| |
| APInt ConstantRange::getSignedMax() const { |
| if (isFullSet() || isUpperSignWrapped()) |
| return APInt::getSignedMaxValue(getBitWidth()); |
| return getUpper() - 1; |
| } |
| |
| APInt ConstantRange::getSignedMin() const { |
| if (isFullSet() || isSignWrappedSet()) |
| return APInt::getSignedMinValue(getBitWidth()); |
| return getLower(); |
| } |
| |
| bool ConstantRange::contains(const APInt &V) const { |
| if (Lower == Upper) |
| return isFullSet(); |
| |
| if (!isUpperWrapped()) |
| return Lower.ule(V) && V.ult(Upper); |
| return Lower.ule(V) || V.ult(Upper); |
| } |
| |
| bool ConstantRange::contains(const ConstantRange &Other) const { |
| if (isFullSet() || Other.isEmptySet()) return true; |
| if (isEmptySet() || Other.isFullSet()) return false; |
| |
| if (!isUpperWrapped()) { |
| if (Other.isUpperWrapped()) |
| return false; |
| |
| return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); |
| } |
| |
| if (!Other.isUpperWrapped()) |
| return Other.getUpper().ule(Upper) || |
| Lower.ule(Other.getLower()); |
| |
| return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); |
| } |
| |
| ConstantRange ConstantRange::subtract(const APInt &Val) const { |
| assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); |
| // If the set is empty or full, don't modify the endpoints. |
| if (Lower == Upper) |
| return *this; |
| return ConstantRange(Lower - Val, Upper - Val); |
| } |
| |
| ConstantRange ConstantRange::difference(const ConstantRange &CR) const { |
| return intersectWith(CR.inverse()); |
| } |
| |
| static ConstantRange getPreferredRange( |
| const ConstantRange &CR1, const ConstantRange &CR2, |
| ConstantRange::PreferredRangeType Type) { |
| if (Type == ConstantRange::Unsigned) { |
| if (!CR1.isWrappedSet() && CR2.isWrappedSet()) |
| return CR1; |
| if (CR1.isWrappedSet() && !CR2.isWrappedSet()) |
| return CR2; |
| } else if (Type == ConstantRange::Signed) { |
| if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet()) |
| return CR1; |
| if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) |
| return CR2; |
| } |
| |
| if (CR1.isSizeStrictlySmallerThan(CR2)) |
| return CR1; |
| return CR2; |
| } |
| |
| ConstantRange ConstantRange::intersectWith(const ConstantRange &CR, |
| PreferredRangeType Type) const { |
| assert(getBitWidth() == CR.getBitWidth() && |
| "ConstantRange types don't agree!"); |
| |
| // Handle common cases. |
| if ( isEmptySet() || CR.isFullSet()) return *this; |
| if (CR.isEmptySet() || isFullSet()) return CR; |
| |
| if (!isUpperWrapped() && CR.isUpperWrapped()) |
| return CR.intersectWith(*this, Type); |
| |
| if (!isUpperWrapped() && !CR.isUpperWrapped()) { |
| if (Lower.ult(CR.Lower)) { |
| // L---U : this |
| // L---U : CR |
| if (Upper.ule(CR.Lower)) |
| return getEmpty(); |
| |
| // L---U : this |
| // L---U : CR |
| if (Upper.ult(CR.Upper)) |
| return ConstantRange(CR.Lower, Upper); |
| |
| // L-------U : this |
| // L---U : CR |
| return CR; |
| } |
| // L---U : this |
| // L-------U : CR |
| if (Upper.ult(CR.Upper)) |
| return *this; |
| |
| // L-----U : this |
| // L-----U : CR |
| if (Lower.ult(CR.Upper)) |
| return ConstantRange(Lower, CR.Upper); |
| |
| // L---U : this |
| // L---U : CR |
| return getEmpty(); |
| } |
| |
| if (isUpperWrapped() && !CR.isUpperWrapped()) { |
| if (CR.Lower.ult(Upper)) { |
| // ------U L--- : this |
| // L--U : CR |
| if (CR.Upper.ult(Upper)) |
| return CR; |
| |
| // ------U L--- : this |
| // L------U : CR |
| if (CR.Upper.ule(Lower)) |
| return ConstantRange(CR.Lower, Upper); |
| |
| // ------U L--- : this |
| // L----------U : CR |
| return getPreferredRange(*this, CR, Type); |
| } |
| if (CR.Lower.ult(Lower)) { |
| // --U L---- : this |
| // L--U : CR |
| if (CR.Upper.ule(Lower)) |
| return getEmpty(); |
| |
| // --U L---- : this |
| // L------U : CR |
| return ConstantRange(Lower, CR.Upper); |
| } |
| |
| // --U L------ : this |
| // L--U : CR |
| return CR; |
| } |
| |
| if (CR.Upper.ult(Upper)) { |
| // ------U L-- : this |
| // --U L------ : CR |
| if (CR.Lower.ult(Upper)) |
| return getPreferredRange(*this, CR, Type); |
| |
| // ----U L-- : this |
| // --U L---- : CR |
| if (CR.Lower.ult(Lower)) |
| return ConstantRange(Lower, CR.Upper); |
| |
| // ----U L---- : this |
| // --U L-- : CR |
| return CR; |
| } |
| if (CR.Upper.ule(Lower)) { |
| // --U L-- : this |
| // ----U L---- : CR |
| if (CR.Lower.ult(Lower)) |
| return *this; |
| |
| // --U L---- : this |
| // ----U L-- : CR |
| return ConstantRange(CR.Lower, Upper); |
| } |
| |
| // --U L------ : this |
| // ------U L-- : CR |
| return getPreferredRange(*this, CR, Type); |
| } |
| |
| ConstantRange ConstantRange::unionWith(const ConstantRange &CR, |
| PreferredRangeType Type) const { |
| assert(getBitWidth() == CR.getBitWidth() && |
| "ConstantRange types don't agree!"); |
| |
| if ( isFullSet() || CR.isEmptySet()) return *this; |
| if (CR.isFullSet() || isEmptySet()) return CR; |
| |
| if (!isUpperWrapped() && CR.isUpperWrapped()) |
| return CR.unionWith(*this, Type); |
| |
| if (!isUpperWrapped() && !CR.isUpperWrapped()) { |
| // L---U and L---U : this |
| // L---U L---U : CR |
| // result in one of |
| // L---------U |
| // -----U L----- |
| if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) |
| return getPreferredRange( |
| ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type); |
| |
| APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower; |
| APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper; |
| |
| if (L.isNullValue() && U.isNullValue()) |
| return getFull(); |
| |
| return ConstantRange(std::move(L), std::move(U)); |
| } |
| |
| if (!CR.isUpperWrapped()) { |
| // ------U L----- and ------U L----- : this |
| // L--U L--U : CR |
| if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) |
| return *this; |
| |
| // ------U L----- : this |
| // L---------U : CR |
| if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) |
| return getFull(); |
| |
| // ----U L---- : this |
| // L---U : CR |
| // results in one of |
| // ----------U L---- |
| // ----U L---------- |
| if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) |
| return getPreferredRange( |
| ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type); |
| |
| // ----U L----- : this |
| // L----U : CR |
| if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper)) |
| return ConstantRange(CR.Lower, Upper); |
| |
| // ------U L---- : this |
| // L-----U : CR |
| assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) && |
| "ConstantRange::unionWith missed a case with one range wrapped"); |
| return ConstantRange(Lower, CR.Upper); |
| } |
| |
| // ------U L---- and ------U L---- : this |
| // -U L----------- and ------------U L : CR |
| if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) |
| return getFull(); |
| |
| APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower; |
| APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper; |
| |
| return ConstantRange(std::move(L), std::move(U)); |
| } |
| |
| ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp, |
| uint32_t ResultBitWidth) const { |
| switch (CastOp) { |
| default: |
| llvm_unreachable("unsupported cast type"); |
| case Instruction::Trunc: |
| return truncate(ResultBitWidth); |
| case Instruction::SExt: |
| return signExtend(ResultBitWidth); |
| case Instruction::ZExt: |
| return zeroExtend(ResultBitWidth); |
| case Instruction::BitCast: |
| return *this; |
| case Instruction::FPToUI: |
| case Instruction::FPToSI: |
| if (getBitWidth() == ResultBitWidth) |
| return *this; |
| else |
| return getFull(); |
| 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: |
| case Instruction::IntToPtr: |
| case Instruction::PtrToInt: |
| case Instruction::AddrSpaceCast: |
| // Conservatively return getFull set. |
| return getFull(); |
| }; |
| } |
| |
| ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { |
| if (isEmptySet()) return getEmpty(DstTySize); |
| |
| unsigned SrcTySize = getBitWidth(); |
| assert(SrcTySize < DstTySize && "Not a value extension"); |
| if (isFullSet() || isUpperWrapped()) { |
| // Change into [0, 1 << src bit width) |
| APInt LowerExt(DstTySize, 0); |
| if (!Upper) // special case: [X, 0) -- not really wrapping around |
| LowerExt = Lower.zext(DstTySize); |
| return ConstantRange(std::move(LowerExt), |
| APInt::getOneBitSet(DstTySize, SrcTySize)); |
| } |
| |
| return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); |
| } |
| |
| ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { |
| if (isEmptySet()) return getEmpty(DstTySize); |
| |
| unsigned SrcTySize = getBitWidth(); |
| assert(SrcTySize < DstTySize && "Not a value extension"); |
| |
| // special case: [X, INT_MIN) -- not really wrapping around |
| if (Upper.isMinSignedValue()) |
| return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize)); |
| |
| if (isFullSet() || isSignWrappedSet()) { |
| return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), |
| APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); |
| } |
| |
| return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); |
| } |
| |
| ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { |
| assert(getBitWidth() > DstTySize && "Not a value truncation"); |
| if (isEmptySet()) |
| return getEmpty(DstTySize); |
| if (isFullSet()) |
| return getFull(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 (isUpperWrapped()) { |
| // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole |
| // truncated range. |
| if (Upper.getActiveBits() > DstTySize || |
| Upper.countTrailingOnes() == DstTySize) |
| return getFull(DstTySize); |
| |
| Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); |
| UpperDiv.setAllBits(); |
| |
| // Union covers the MaxValue case, so return if the remaining range is just |
| // MaxValue(DstTy). |
| if (LowerDiv == UpperDiv) |
| return Union; |
| } |
| |
| // Chop off the most significant bits that are past the destination bitwidth. |
| if (LowerDiv.getActiveBits() > DstTySize) { |
| // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv. |
| APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize); |
| LowerDiv -= Adjust; |
| UpperDiv -= Adjust; |
| } |
| |
| unsigned UpperDivWidth = UpperDiv.getActiveBits(); |
| if (UpperDivWidth <= DstTySize) |
| return ConstantRange(LowerDiv.trunc(DstTySize), |
| UpperDiv.trunc(DstTySize)).unionWith(Union); |
| |
| // The truncated value wraps around. Check if we can do better than fullset. |
| if (UpperDivWidth == DstTySize + 1) { |
| // Clear the MSB so that UpperDiv wraps around. |
| UpperDiv.clearBit(DstTySize); |
| if (UpperDiv.ult(LowerDiv)) |
| return ConstantRange(LowerDiv.trunc(DstTySize), |
| UpperDiv.trunc(DstTySize)).unionWith(Union); |
| } |
| |
| return getFull(DstTySize); |
| } |
| |
| ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { |
| unsigned SrcTySize = getBitWidth(); |
| if (SrcTySize > DstTySize) |
| return truncate(DstTySize); |
| if (SrcTySize < DstTySize) |
| return zeroExtend(DstTySize); |
| return *this; |
| } |
| |
| ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { |
| unsigned SrcTySize = getBitWidth(); |
| if (SrcTySize > DstTySize) |
| return truncate(DstTySize); |
| if (SrcTySize < DstTySize) |
| return signExtend(DstTySize); |
| return *this; |
| } |
| |
| ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp, |
| const ConstantRange &Other) const { |
| assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!"); |
| |
| switch (BinOp) { |
| case Instruction::Add: |
| return add(Other); |
| case Instruction::Sub: |
| return sub(Other); |
| case Instruction::Mul: |
| return multiply(Other); |
| case Instruction::UDiv: |
| return udiv(Other); |
| case Instruction::SDiv: |
| return sdiv(Other); |
| case Instruction::URem: |
| return urem(Other); |
| case Instruction::SRem: |
| return srem(Other); |
| case Instruction::Shl: |
| return shl(Other); |
| case Instruction::LShr: |
| return lshr(Other); |
| case Instruction::AShr: |
| return ashr(Other); |
| case Instruction::And: |
| return binaryAnd(Other); |
| case Instruction::Or: |
| return binaryOr(Other); |
| // Note: floating point operations applied to abstract ranges are just |
| // ideal integer operations with a lossy representation |
| case Instruction::FAdd: |
| return add(Other); |
| case Instruction::FSub: |
| return sub(Other); |
| case Instruction::FMul: |
| return multiply(Other); |
| default: |
| // Conservatively return getFull set. |
| return getFull(); |
| } |
| } |
| |
| ConstantRange |
| ConstantRange::add(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| if (isFullSet() || Other.isFullSet()) |
| return getFull(); |
| |
| APInt NewLower = getLower() + Other.getLower(); |
| APInt NewUpper = getUpper() + Other.getUpper() - 1; |
| if (NewLower == NewUpper) |
| return getFull(); |
| |
| ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper)); |
| if (X.isSizeStrictlySmallerThan(*this) || |
| X.isSizeStrictlySmallerThan(Other)) |
| // We've wrapped, therefore, full set. |
| return getFull(); |
| return X; |
| } |
| |
| ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other, |
| unsigned NoWrapKind, |
| 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) |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| if (isFullSet() && Other.isFullSet()) |
| return getFull(); |
| |
| using OBO = OverflowingBinaryOperator; |
| ConstantRange Result = add(Other); |
| |
| auto addWithNoUnsignedWrap = [this](const ConstantRange &Other) { |
| APInt LMin = getUnsignedMin(), LMax = getUnsignedMax(); |
| APInt RMin = Other.getUnsignedMin(), RMax = Other.getUnsignedMax(); |
| bool Overflow; |
| APInt NewMin = LMin.uadd_ov(RMin, Overflow); |
| if (Overflow) |
| return getEmpty(); |
| APInt NewMax = LMax.uadd_sat(RMax); |
| return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1); |
| }; |
| |
| auto addWithNoSignedWrap = [this](const ConstantRange &Other) { |
| APInt LMin = getSignedMin(), LMax = getSignedMax(); |
| APInt RMin = Other.getSignedMin(), RMax = Other.getSignedMax(); |
| if (LMin.isNonNegative()) { |
| bool Overflow; |
| APInt Temp = LMin.sadd_ov(RMin, Overflow); |
| if (Overflow) |
| return getEmpty(); |
| } |
| if (LMax.isNegative()) { |
| bool Overflow; |
| APInt Temp = LMax.sadd_ov(RMax, Overflow); |
| if (Overflow) |
| return getEmpty(); |
| } |
| APInt NewMin = LMin.sadd_sat(RMin); |
| APInt NewMax = LMax.sadd_sat(RMax); |
| return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1); |
| }; |
| |
| if (NoWrapKind & OBO::NoSignedWrap) |
| Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType); |
| if (NoWrapKind & OBO::NoUnsignedWrap) |
| Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType); |
| return Result; |
| } |
| |
| ConstantRange |
| ConstantRange::sub(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| if (isFullSet() || Other.isFullSet()) |
| return getFull(); |
| |
| APInt NewLower = getLower() - Other.getUpper() + 1; |
| APInt NewUpper = getUpper() - Other.getLower(); |
| if (NewLower == NewUpper) |
| return getFull(); |
| |
| ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper)); |
| if (X.isSizeStrictlySmallerThan(*this) || |
| X.isSizeStrictlySmallerThan(Other)) |
| // We've wrapped, therefore, full set. |
| return getFull(); |
| return X; |
| } |
| |
| ConstantRange |
| ConstantRange::multiply(const ConstantRange &Other) const { |
| // TODO: If either operand is a single element and the multiply is known to |
| // be non-wrapping, round the result min and max value to the appropriate |
| // multiple of that element. If wrapping is possible, at least adjust the |
| // range according to the greatest power-of-two factor of the single element. |
| |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| // Multiplication is signedness-independent. However different ranges can be |
| // obtained depending on how the input ranges are treated. These different |
| // ranges are all conservatively correct, but one might be better than the |
| // other. We calculate two ranges; one treating the inputs as unsigned |
| // and the other signed, then return the smallest of these ranges. |
| |
| // Unsigned range first. |
| APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); |
| APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); |
| APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); |
| APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); |
| |
| ConstantRange Result_zext = ConstantRange(this_min * Other_min, |
| this_max * Other_max + 1); |
| ConstantRange UR = Result_zext.truncate(getBitWidth()); |
| |
| // If the unsigned range doesn't wrap, and isn't negative then it's a range |
| // from one positive number to another which is as good as we can generate. |
| // In this case, skip the extra work of generating signed ranges which aren't |
| // going to be better than this range. |
| if (!UR.isUpperWrapped() && |
| (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue())) |
| return UR; |
| |
| // Now the signed range. Because we could be dealing with negative numbers |
| // here, the lower bound is the smallest of the cartesian product of the |
| // lower and upper ranges; for example: |
| // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6. |
| // Similarly for the upper bound, swapping min for max. |
| |
| this_min = getSignedMin().sext(getBitWidth() * 2); |
| this_max = getSignedMax().sext(getBitWidth() * 2); |
| Other_min = Other.getSignedMin().sext(getBitWidth() * 2); |
| Other_max = Other.getSignedMax().sext(getBitWidth() * 2); |
| |
| auto L = {this_min * Other_min, this_min * Other_max, |
| this_max * Other_min, this_max * Other_max}; |
| auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); }; |
| ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1); |
| ConstantRange SR = Result_sext.truncate(getBitWidth()); |
| |
| return UR.isSizeStrictlySmallerThan(SR) ? UR : SR; |
| } |
| |
| ConstantRange |
| ConstantRange::smax(const ConstantRange &Other) const { |
| // X smax Y is: range(smax(X_smin, Y_smin), |
| // smax(X_smax, Y_smax)) |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); |
| APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; |
| return getNonEmpty(std::move(NewL), std::move(NewU)); |
| } |
| |
| ConstantRange |
| ConstantRange::umax(const ConstantRange &Other) const { |
| // X umax Y is: range(umax(X_umin, Y_umin), |
| // umax(X_umax, Y_umax)) |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); |
| APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; |
| return getNonEmpty(std::move(NewL), std::move(NewU)); |
| } |
| |
| ConstantRange |
| ConstantRange::smin(const ConstantRange &Other) const { |
| // X smin Y is: range(smin(X_smin, Y_smin), |
| // smin(X_smax, Y_smax)) |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin()); |
| APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1; |
| return getNonEmpty(std::move(NewL), std::move(NewU)); |
| } |
| |
| ConstantRange |
| ConstantRange::umin(const ConstantRange &Other) const { |
| // X umin Y is: range(umin(X_umin, Y_umin), |
| // umin(X_umax, Y_umax)) |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin()); |
| APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1; |
| return getNonEmpty(std::move(NewL), std::move(NewU)); |
| } |
| |
| ConstantRange |
| ConstantRange::udiv(const ConstantRange &RHS) const { |
| if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue()) |
| return getEmpty(); |
| |
| APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); |
| |
| APInt RHS_umin = RHS.getUnsignedMin(); |
| if (RHS_umin.isNullValue()) { |
| // We want the lowest value in RHS excluding zero. Usually that would be 1 |
| // except for a range in the form of [X, 1) in which case it would be X. |
| if (RHS.getUpper() == 1) |
| RHS_umin = RHS.getLower(); |
| else |
| RHS_umin = 1; |
| } |
| |
| APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; |
| return getNonEmpty(std::move(Lower), std::move(Upper)); |
| } |
| |
| ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const { |
| // 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. |
| APInt Zero = APInt::getNullValue(getBitWidth()); |
| APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); |
| ConstantRange PosFilter(APInt(getBitWidth(), 1), SignedMin); |
| ConstantRange NegFilter(SignedMin, Zero); |
| ConstantRange PosL = intersectWith(PosFilter); |
| ConstantRange NegL = intersectWith(NegFilter); |
| ConstantRange PosR = RHS.intersectWith(PosFilter); |
| ConstantRange NegR = RHS.intersectWith(NegFilter); |
| |
| ConstantRange PosRes = getEmpty(); |
| if (!PosL.isEmptySet() && !PosR.isEmptySet()) |
| // pos / pos = pos. |
| PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1), |
| (PosL.Upper - 1).sdiv(PosR.Lower) + 1); |
| |
| if (!NegL.isEmptySet() && !NegR.isEmptySet()) { |
| // neg / neg = pos. |
| // |
| // We need to deal with one tricky case here: SignedMin / -1 is UB on the |
| // IR level, so we'll want to exclude this case when calculating bounds. |
| // (For APInts the operation is well-defined and yields SignedMin.) We |
| // handle this by dropping either SignedMin from the LHS or -1 from the RHS. |
| APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower); |
| if (NegL.Lower.isMinSignedValue() && NegR.Upper.isNullValue()) { |
| // Remove -1 from the LHS. Skip if it's the only element, as this would |
| // leave us with an empty set. |
| if (!NegR.Lower.isAllOnesValue()) { |
| APInt AdjNegRUpper; |
| if (RHS.Lower.isAllOnesValue()) |
| // Negative part of [-1, X] without -1 is [SignedMin, X]. |
| AdjNegRUpper = RHS.Upper; |
| else |
| // [X, -1] without -1 is [X, -2]. |
| AdjNegRUpper = NegR.Upper - 1; |
| |
| PosRes = PosRes.unionWith( |
| ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1)); |
| } |
| |
| // Remove SignedMin from the RHS. Skip if it's the only element, as this |
| // would leave us with an empty set. |
| if (NegL.Upper != SignedMin + 1) { |
| APInt AdjNegLLower; |
| if (Upper == SignedMin + 1) |
| // Negative part of [X, SignedMin] without SignedMin is [X, -1]. |
| AdjNegLLower = Lower; |
| else |
| // [SignedMin, X] without SignedMin is [SignedMin + 1, X]. |
| AdjNegLLower = NegL.Lower + 1; |
| |
| PosRes = PosRes.unionWith( |
| ConstantRange(std::move(Lo), |
| AdjNegLLower.sdiv(NegR.Upper - 1) + 1)); |
| } |
| } else { |
| PosRes = PosRes.unionWith( |
| ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1)); |
| } |
| } |
| |
| ConstantRange NegRes = getEmpty(); |
| if (!PosL.isEmptySet() && !NegR.isEmptySet()) |
| // pos / neg = neg. |
| NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1), |
| PosL.Lower.sdiv(NegR.Lower) + 1); |
| |
| if (!NegL.isEmptySet() && !PosR.isEmptySet()) |
| // neg / pos = neg. |
| NegRes = NegRes.unionWith( |
| ConstantRange(NegL.Lower.sdiv(PosR.Lower), |
| (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1)); |
| |
| // Prefer a non-wrapping signed range here. |
| ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed); |
| |
| // Preserve the zero that we dropped when splitting the LHS by sign. |
| if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet())) |
| Res = Res.unionWith(ConstantRange(Zero)); |
| return Res; |
| } |
| |
| ConstantRange ConstantRange::urem(const ConstantRange &RHS) const { |
| if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue()) |
| return getEmpty(); |
| |
| // L % R for L < R is L. |
| if (getUnsignedMax().ult(RHS.getUnsignedMin())) |
| return *this; |
| |
| // L % R is <= L and < R. |
| APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1; |
| return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper)); |
| } |
| |
| ConstantRange ConstantRange::srem(const ConstantRange &RHS) const { |
| if (isEmptySet() || RHS.isEmptySet()) |
| return getEmpty(); |
| |
| ConstantRange AbsRHS = RHS.abs(); |
| APInt MinAbsRHS = AbsRHS.getUnsignedMin(); |
| APInt MaxAbsRHS = AbsRHS.getUnsignedMax(); |
| |
| // Modulus by zero is UB. |
| if (MaxAbsRHS.isNullValue()) |
| return getEmpty(); |
| |
| if (MinAbsRHS.isNullValue()) |
| ++MinAbsRHS; |
| |
| APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax(); |
| |
| if (MinLHS.isNonNegative()) { |
| // L % R for L < R is L. |
| if (MaxLHS.ult(MinAbsRHS)) |
| return *this; |
| |
| // L % R is <= L and < R. |
| APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1; |
| return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(Upper)); |
| } |
| |
| // Same basic logic as above, but the result is negative. |
| if (MaxLHS.isNegative()) { |
| if (MinLHS.ugt(-MinAbsRHS)) |
| return *this; |
| |
| APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1); |
| return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1)); |
| } |
| |
| // LHS range crosses zero. |
| APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1); |
| APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1; |
| return ConstantRange(std::move(Lower), std::move(Upper)); |
| } |
| |
| ConstantRange |
| ConstantRange::binaryAnd(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| // TODO: replace this with something less conservative |
| |
| APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); |
| return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(umin) + 1); |
| } |
| |
| ConstantRange |
| ConstantRange::binaryOr(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| // TODO: replace this with something less conservative |
| |
| APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); |
| return getNonEmpty(std::move(umax), APInt::getNullValue(getBitWidth())); |
| } |
| |
| ConstantRange |
| ConstantRange::shl(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| APInt max = getUnsignedMax(); |
| APInt Other_umax = Other.getUnsignedMax(); |
| |
| // If we are shifting by maximum amount of |
| // zero return return the original range. |
| if (Other_umax.isNullValue()) |
| return *this; |
| // there's overflow! |
| if (Other_umax.ugt(max.countLeadingZeros())) |
| return getFull(); |
| |
| // FIXME: implement the other tricky cases |
| |
| APInt min = getUnsignedMin(); |
| min <<= Other.getUnsignedMin(); |
| max <<= Other_umax; |
| |
| return ConstantRange(std::move(min), std::move(max) + 1); |
| } |
| |
| ConstantRange |
| ConstantRange::lshr(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1; |
| APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); |
| return getNonEmpty(std::move(min), std::move(max)); |
| } |
| |
| ConstantRange |
| ConstantRange::ashr(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| // May straddle zero, so handle both positive and negative cases. |
| // 'PosMax' is the upper bound of the result of the ashr |
| // operation, when Upper of the LHS of ashr is a non-negative. |
| // number. Since ashr of a non-negative number will result in a |
| // smaller number, the Upper value of LHS is shifted right with |
| // the minimum value of 'Other' instead of the maximum value. |
| APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1; |
| |
| // 'PosMin' is the lower bound of the result of the ashr |
| // operation, when Lower of the LHS is a non-negative number. |
| // Since ashr of a non-negative number will result in a smaller |
| // number, the Lower value of LHS is shifted right with the |
| // maximum value of 'Other'. |
| APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax()); |
| |
| // 'NegMax' is the upper bound of the result of the ashr |
| // operation, when Upper of the LHS of ashr is a negative number. |
| // Since 'ashr' of a negative number will result in a bigger |
| // number, the Upper value of LHS is shifted right with the |
| // maximum value of 'Other'. |
| APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1; |
| |
| // 'NegMin' is the lower bound of the result of the ashr |
| // operation, when Lower of the LHS of ashr is a negative number. |
| // Since 'ashr' of a negative number will result in a bigger |
| // number, the Lower value of LHS is shifted right with the |
| // minimum value of 'Other'. |
| APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin()); |
| |
| APInt max, min; |
| if (getSignedMin().isNonNegative()) { |
| // Upper and Lower of LHS are non-negative. |
| min = PosMin; |
| max = PosMax; |
| } else if (getSignedMax().isNegative()) { |
| // Upper and Lower of LHS are negative. |
| min = NegMin; |
| max = NegMax; |
| } else { |
| // Upper is non-negative and Lower is negative. |
| min = NegMin; |
| max = PosMax; |
| } |
| return getNonEmpty(std::move(min), std::move(max)); |
| } |
| |
| ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin()); |
| APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1; |
| return getNonEmpty(std::move(NewL), std::move(NewU)); |
| } |
| |
| ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin()); |
| APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1; |
| return getNonEmpty(std::move(NewL), std::move(NewU)); |
| } |
| |
| ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax()); |
| APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1; |
| return getNonEmpty(std::move(NewL), std::move(NewU)); |
| } |
| |
| ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return getEmpty(); |
| |
| APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax()); |
| APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1; |
| return getNonEmpty(std::move(NewL), std::move(NewU)); |
| } |
| |
| ConstantRange ConstantRange::inverse() const { |
| if (isFullSet()) |
| return getEmpty(); |
| if (isEmptySet()) |
| return getFull(); |
| return ConstantRange(Upper, Lower); |
| } |
| |
| ConstantRange ConstantRange::abs() const { |
| if (isEmptySet()) |
| return getEmpty(); |
| |
| if (isSignWrappedSet()) { |
| APInt Lo; |
| // Check whether the range crosses zero. |
| if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive()) |
| Lo = APInt::getNullValue(getBitWidth()); |
| else |
| Lo = APIntOps::umin(Lower, -Upper + 1); |
| |
| // SignedMin is included in the result range. |
| return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth()) + 1); |
| } |
| |
| APInt SMin = getSignedMin(), SMax = getSignedMax(); |
| |
| // All non-negative. |
| if (SMin.isNonNegative()) |
| return *this; |
| |
| // All negative. |
| if (SMax.isNegative()) |
| return ConstantRange(-SMax, -SMin + 1); |
| |
| // Range crosses zero. |
| return ConstantRange(APInt::getNullValue(getBitWidth()), |
| APIntOps::umax(-SMin, SMax) + 1); |
| } |
| |
| ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow( |
| const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return OverflowResult::MayOverflow; |
| |
| APInt Min = getUnsignedMin(), Max = getUnsignedMax(); |
| APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax(); |
| |
| // a u+ b overflows high iff a u> ~b. |
| if (Min.ugt(~OtherMin)) |
| return OverflowResult::AlwaysOverflowsHigh; |
| if (Max.ugt(~OtherMax)) |
| return OverflowResult::MayOverflow; |
| return OverflowResult::NeverOverflows; |
| } |
| |
| ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow( |
| const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return OverflowResult::MayOverflow; |
| |
| APInt Min = getSignedMin(), Max = getSignedMax(); |
| APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax(); |
| |
| APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); |
| APInt SignedMax = APInt::getSignedMaxValue(getBitWidth()); |
| |
| // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b. |
| // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b. |
| if (Min.isNonNegative() && OtherMin.isNonNegative() && |
| Min.sgt(SignedMax - OtherMin)) |
| return OverflowResult::AlwaysOverflowsHigh; |
| if (Max.isNegative() && OtherMax.isNegative() && |
| Max.slt(SignedMin - OtherMax)) |
| return OverflowResult::AlwaysOverflowsLow; |
| |
| if (Max.isNonNegative() && OtherMax.isNonNegative() && |
| Max.sgt(SignedMax - OtherMax)) |
| return OverflowResult::MayOverflow; |
| if (Min.isNegative() && OtherMin.isNegative() && |
| Min.slt(SignedMin - OtherMin)) |
| return OverflowResult::MayOverflow; |
| |
| return OverflowResult::NeverOverflows; |
| } |
| |
| ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow( |
| const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return OverflowResult::MayOverflow; |
| |
| APInt Min = getUnsignedMin(), Max = getUnsignedMax(); |
| APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax(); |
| |
| // a u- b overflows low iff a u< b. |
| if (Max.ult(OtherMin)) |
| return OverflowResult::AlwaysOverflowsLow; |
| if (Min.ult(OtherMax)) |
| return OverflowResult::MayOverflow; |
| return OverflowResult::NeverOverflows; |
| } |
| |
| ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow( |
| const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return OverflowResult::MayOverflow; |
| |
| APInt Min = getSignedMin(), Max = getSignedMax(); |
| APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax(); |
| |
| APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); |
| APInt SignedMax = APInt::getSignedMaxValue(getBitWidth()); |
| |
| // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b. |
| // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b. |
| if (Min.isNonNegative() && OtherMax.isNegative() && |
| Min.sgt(SignedMax + OtherMax)) |
| return OverflowResult::AlwaysOverflowsHigh; |
| if (Max.isNegative() && OtherMin.isNonNegative() && |
| Max.slt(SignedMin + OtherMin)) |
| return OverflowResult::AlwaysOverflowsLow; |
| |
| if (Max.isNonNegative() && OtherMin.isNegative() && |
| Max.sgt(SignedMax + OtherMin)) |
| return OverflowResult::MayOverflow; |
| if (Min.isNegative() && OtherMax.isNonNegative() && |
| Min.slt(SignedMin + OtherMax)) |
| return OverflowResult::MayOverflow; |
| |
| return OverflowResult::NeverOverflows; |
| } |
| |
| ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow( |
| const ConstantRange &Other) const { |
| if (isEmptySet() || Other.isEmptySet()) |
| return OverflowResult::MayOverflow; |
| |
| APInt Min = getUnsignedMin(), Max = getUnsignedMax(); |
| APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax(); |
| bool Overflow; |
| |
| (void) Min.umul_ov(OtherMin, Overflow); |
| if (Overflow) |
| return OverflowResult::AlwaysOverflowsHigh; |
| |
| (void) Max.umul_ov(OtherMax, Overflow); |
| if (Overflow) |
| return OverflowResult::MayOverflow; |
| |
| return OverflowResult::NeverOverflows; |
| } |
| |
| void ConstantRange::print(raw_ostream &OS) const { |
| if (isFullSet()) |
| OS << "full-set"; |
| else if (isEmptySet()) |
| OS << "empty-set"; |
| else |
| OS << "[" << Lower << "," << Upper << ")"; |
| } |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| LLVM_DUMP_METHOD void ConstantRange::dump() const { |
| print(dbgs()); |
| } |
| #endif |
| |
| ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) { |
| const unsigned NumRanges = Ranges.getNumOperands() / 2; |
| assert(NumRanges >= 1 && "Must have at least one range!"); |
| assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs"); |
| |
| auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0)); |
| auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1)); |
| |
| ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue()); |
| |
| for (unsigned i = 1; i < NumRanges; ++i) { |
| auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0)); |
| auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1)); |
| |
| // Note: unionWith will potentially create a range that contains values not |
| // contained in any of the original N ranges. |
| CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue())); |
| } |
| |
| return CR; |
| } |