diff options
Diffstat (limited to 'lib/StaticAnalyzer/Core/RangeConstraintManager.cpp')
-rw-r--r-- | lib/StaticAnalyzer/Core/RangeConstraintManager.cpp | 455 |
1 files changed, 216 insertions, 239 deletions
diff --git a/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp index 5a4031c0b4a5..e8c7bdbde385 100644 --- a/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -12,10 +12,10 @@ // //===----------------------------------------------------------------------===// -#include "RangedConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableSet.h" #include "llvm/Support/raw_ostream.h" @@ -23,263 +23,203 @@ using namespace clang; using namespace ento; -/// A Range represents the closed range [from, to]. The caller must -/// guarantee that from <= to. Note that Range is immutable, so as not -/// to subvert RangeSet's immutability. -namespace { -class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> { -public: - Range(const llvm::APSInt &from, const llvm::APSInt &to) - : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) { - assert(from <= to); - } - bool Includes(const llvm::APSInt &v) const { - return *first <= v && v <= *second; - } - const llvm::APSInt &From() const { return *first; } - const llvm::APSInt &To() const { return *second; } - const llvm::APSInt *getConcreteValue() const { - return &From() == &To() ? &From() : nullptr; - } - - void Profile(llvm::FoldingSetNodeID &ID) const { - ID.AddPointer(&From()); - ID.AddPointer(&To()); - } -}; - -class RangeTrait : public llvm::ImutContainerInfo<Range> { -public: - // When comparing if one Range is less than another, we should compare - // the actual APSInt values instead of their pointers. This keeps the order - // consistent (instead of comparing by pointer values) and can potentially - // be used to speed up some of the operations in RangeSet. - static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { - return *lhs.first < *rhs.first || - (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); - } -}; - -/// RangeSet contains a set of ranges. If the set is empty, then -/// there the value of a symbol is overly constrained and there are no -/// possible values for that symbol. -class RangeSet { - typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet; - PrimRangeSet ranges; // no need to make const, since it is an - // ImmutableSet - this allows default operator= - // to work. -public: - typedef PrimRangeSet::Factory Factory; - typedef PrimRangeSet::iterator iterator; - - RangeSet(PrimRangeSet RS) : ranges(RS) {} - - /// Create a new set with all ranges of this set and RS. - /// Possible intersections are not checked here. - RangeSet addRange(Factory &F, const RangeSet &RS) { - PrimRangeSet Ranges(RS.ranges); - for (const auto &range : ranges) - Ranges = F.add(Ranges, range); - return RangeSet(Ranges); - } - - iterator begin() const { return ranges.begin(); } - iterator end() const { return ranges.end(); } - - bool isEmpty() const { return ranges.isEmpty(); } - - /// Construct a new RangeSet representing '{ [from, to] }'. - RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to) - : ranges(F.add(F.getEmptySet(), Range(from, to))) {} - - /// Profile - Generates a hash profile of this RangeSet for use - /// by FoldingSet. - void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); } - - /// getConcreteValue - If a symbol is contrained to equal a specific integer - /// constant then this method returns that value. Otherwise, it returns - /// NULL. - const llvm::APSInt *getConcreteValue() const { - return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; - } +void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F, + const llvm::APSInt &Lower, const llvm::APSInt &Upper, + PrimRangeSet &newRanges, PrimRangeSet::iterator &i, + PrimRangeSet::iterator &e) const { + // There are six cases for each range R in the set: + // 1. R is entirely before the intersection range. + // 2. R is entirely after the intersection range. + // 3. R contains the entire intersection range. + // 4. R starts before the intersection range and ends in the middle. + // 5. R starts in the middle of the intersection range and ends after it. + // 6. R is entirely contained in the intersection range. + // These correspond to each of the conditions below. + for (/* i = begin(), e = end() */; i != e; ++i) { + if (i->To() < Lower) { + continue; + } + if (i->From() > Upper) { + break; + } -private: - void IntersectInRange(BasicValueFactory &BV, Factory &F, - const llvm::APSInt &Lower, const llvm::APSInt &Upper, - PrimRangeSet &newRanges, PrimRangeSet::iterator &i, - PrimRangeSet::iterator &e) const { - // There are six cases for each range R in the set: - // 1. R is entirely before the intersection range. - // 2. R is entirely after the intersection range. - // 3. R contains the entire intersection range. - // 4. R starts before the intersection range and ends in the middle. - // 5. R starts in the middle of the intersection range and ends after it. - // 6. R is entirely contained in the intersection range. - // These correspond to each of the conditions below. - for (/* i = begin(), e = end() */; i != e; ++i) { - if (i->To() < Lower) { - continue; - } - if (i->From() > Upper) { + if (i->Includes(Lower)) { + if (i->Includes(Upper)) { + newRanges = + F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); break; - } - - if (i->Includes(Lower)) { - if (i->Includes(Upper)) { - newRanges = - F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); - break; - } else - newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To())); - } else { - if (i->Includes(Upper)) { - newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper))); - break; - } else - newRanges = F.add(newRanges, *i); - } + } else + newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To())); + } else { + if (i->Includes(Upper)) { + newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper))); + break; + } else + newRanges = F.add(newRanges, *i); } } +} - const llvm::APSInt &getMinValue() const { - assert(!isEmpty()); - return ranges.begin()->From(); - } +const llvm::APSInt &RangeSet::getMinValue() const { + assert(!isEmpty()); + return ranges.begin()->From(); +} - bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const { - // This function has nine cases, the cartesian product of range-testing - // both the upper and lower bounds against the symbol's type. - // Each case requires a different pinning operation. - // The function returns false if the described range is entirely outside - // the range of values for the associated symbol. - APSIntType Type(getMinValue()); - APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true); - APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true); - - switch (LowerTest) { +bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const { + // This function has nine cases, the cartesian product of range-testing + // both the upper and lower bounds against the symbol's type. + // Each case requires a different pinning operation. + // The function returns false if the described range is entirely outside + // the range of values for the associated symbol. + APSIntType Type(getMinValue()); + APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true); + APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true); + + switch (LowerTest) { + case APSIntType::RTR_Below: + switch (UpperTest) { case APSIntType::RTR_Below: - switch (UpperTest) { - case APSIntType::RTR_Below: - // The entire range is outside the symbol's set of possible values. - // If this is a conventionally-ordered range, the state is infeasible. - if (Lower <= Upper) - return false; - - // However, if the range wraps around, it spans all possible values. - Lower = Type.getMinValue(); - Upper = Type.getMaxValue(); - break; - case APSIntType::RTR_Within: - // The range starts below what's possible but ends within it. Pin. - Lower = Type.getMinValue(); - Type.apply(Upper); - break; - case APSIntType::RTR_Above: - // The range spans all possible values for the symbol. Pin. - Lower = Type.getMinValue(); - Upper = Type.getMaxValue(); - break; - } + // The entire range is outside the symbol's set of possible values. + // If this is a conventionally-ordered range, the state is infeasible. + if (Lower <= Upper) + return false; + + // However, if the range wraps around, it spans all possible values. + Lower = Type.getMinValue(); + Upper = Type.getMaxValue(); break; case APSIntType::RTR_Within: - switch (UpperTest) { - case APSIntType::RTR_Below: - // The range wraps around, but all lower values are not possible. - Type.apply(Lower); - Upper = Type.getMaxValue(); - break; - case APSIntType::RTR_Within: - // The range may or may not wrap around, but both limits are valid. - Type.apply(Lower); - Type.apply(Upper); - break; - case APSIntType::RTR_Above: - // The range starts within what's possible but ends above it. Pin. - Type.apply(Lower); - Upper = Type.getMaxValue(); - break; - } + // The range starts below what's possible but ends within it. Pin. + Lower = Type.getMinValue(); + Type.apply(Upper); break; case APSIntType::RTR_Above: - switch (UpperTest) { - case APSIntType::RTR_Below: - // The range wraps but is outside the symbol's set of possible values. - return false; - case APSIntType::RTR_Within: - // The range starts above what's possible but ends within it (wrap). - Lower = Type.getMinValue(); - Type.apply(Upper); - break; - case APSIntType::RTR_Above: - // The entire range is outside the symbol's set of possible values. - // If this is a conventionally-ordered range, the state is infeasible. - if (Lower <= Upper) - return false; - - // However, if the range wraps around, it spans all possible values. - Lower = Type.getMinValue(); - Upper = Type.getMaxValue(); - break; - } + // The range spans all possible values for the symbol. Pin. + Lower = Type.getMinValue(); + Upper = Type.getMaxValue(); + break; + } + break; + case APSIntType::RTR_Within: + switch (UpperTest) { + case APSIntType::RTR_Below: + // The range wraps around, but all lower values are not possible. + Type.apply(Lower); + Upper = Type.getMaxValue(); + break; + case APSIntType::RTR_Within: + // The range may or may not wrap around, but both limits are valid. + Type.apply(Lower); + Type.apply(Upper); + break; + case APSIntType::RTR_Above: + // The range starts within what's possible but ends above it. Pin. + Type.apply(Lower); + Upper = Type.getMaxValue(); break; } + break; + case APSIntType::RTR_Above: + switch (UpperTest) { + case APSIntType::RTR_Below: + // The range wraps but is outside the symbol's set of possible values. + return false; + case APSIntType::RTR_Within: + // The range starts above what's possible but ends within it (wrap). + Lower = Type.getMinValue(); + Type.apply(Upper); + break; + case APSIntType::RTR_Above: + // The entire range is outside the symbol's set of possible values. + // If this is a conventionally-ordered range, the state is infeasible. + if (Lower <= Upper) + return false; - return true; + // However, if the range wraps around, it spans all possible values. + Lower = Type.getMinValue(); + Upper = Type.getMaxValue(); + break; + } + break; } -public: - // Returns a set containing the values in the receiving set, intersected with - // the closed range [Lower, Upper]. Unlike the Range type, this range uses - // modular arithmetic, corresponding to the common treatment of C integer - // overflow. Thus, if the Lower bound is greater than the Upper bound, the - // range is taken to wrap around. This is equivalent to taking the - // intersection with the two ranges [Min, Upper] and [Lower, Max], - // or, alternatively, /removing/ all integers between Upper and Lower. - RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, - llvm::APSInt Upper) const { - if (!pin(Lower, Upper)) - return F.getEmptySet(); - - PrimRangeSet newRanges = F.getEmptySet(); - - PrimRangeSet::iterator i = begin(), e = end(); - if (Lower <= Upper) - IntersectInRange(BV, F, Lower, Upper, newRanges, i, e); - else { - // The order of the next two statements is important! - // IntersectInRange() does not reset the iteration state for i and e. - // Therefore, the lower range most be handled first. - IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e); - IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e); - } + return true; +} + +// Returns a set containing the values in the receiving set, intersected with +// the closed range [Lower, Upper]. Unlike the Range type, this range uses +// modular arithmetic, corresponding to the common treatment of C integer +// overflow. Thus, if the Lower bound is greater than the Upper bound, the +// range is taken to wrap around. This is equivalent to taking the +// intersection with the two ranges [Min, Upper] and [Lower, Max], +// or, alternatively, /removing/ all integers between Upper and Lower. +RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F, + llvm::APSInt Lower, llvm::APSInt Upper) const { + if (!pin(Lower, Upper)) + return F.getEmptySet(); - return newRanges; + PrimRangeSet newRanges = F.getEmptySet(); + + PrimRangeSet::iterator i = begin(), e = end(); + if (Lower <= Upper) + IntersectInRange(BV, F, Lower, Upper, newRanges, i, e); + else { + // The order of the next two statements is important! + // IntersectInRange() does not reset the iteration state for i and e. + // Therefore, the lower range most be handled first. + IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e); + IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e); } - void print(raw_ostream &os) const { - bool isFirst = true; - os << "{ "; - for (iterator i = begin(), e = end(); i != e; ++i) { - if (isFirst) - isFirst = false; - else - os << ", "; - - os << '[' << i->From().toString(10) << ", " << i->To().toString(10) - << ']'; + return newRanges; +} + +// Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set +// [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal +// signed values of the type. +RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const { + PrimRangeSet newRanges = F.getEmptySet(); + + for (iterator i = begin(), e = end(); i != e; ++i) { + const llvm::APSInt &from = i->From(), &to = i->To(); + const llvm::APSInt &newTo = (from.isMinSignedValue() ? + BV.getMaxValue(from) : + BV.getValue(- from)); + if (to.isMaxSignedValue() && !newRanges.isEmpty() && + newRanges.begin()->From().isMinSignedValue()) { + assert(newRanges.begin()->To().isMinSignedValue() && + "Ranges should not overlap"); + assert(!from.isMinSignedValue() && "Ranges should not overlap"); + const llvm::APSInt &newFrom = newRanges.begin()->From(); + newRanges = + F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo)); + } else if (!to.isMinSignedValue()) { + const llvm::APSInt &newFrom = BV.getValue(- to); + newRanges = F.add(newRanges, Range(newFrom, newTo)); + } + if (from.isMinSignedValue()) { + newRanges = F.add(newRanges, Range(BV.getMinValue(from), + BV.getMinValue(from))); } - os << " }"; } - bool operator==(const RangeSet &other) const { - return ranges == other.ranges; - } -}; -} // end anonymous namespace + return newRanges; +} -REGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintRange, - CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, - RangeSet)) +void RangeSet::print(raw_ostream &os) const { + bool isFirst = true; + os << "{ "; + for (iterator i = begin(), e = end(); i != e; ++i) { + if (isFirst) + isFirst = false; + else + os << ", "; + + os << '[' << i->From().toString(10) << ", " << i->To().toString(10) + << ']'; + } + os << " }"; +} namespace { class RangeConstraintManager : public RangedConstraintManager { @@ -344,6 +284,8 @@ private: RangeSet::Factory F; RangeSet getRange(ProgramStateRef State, SymbolRef Sym); + const RangeSet* getRangeForMinusSymbol(ProgramStateRef State, + SymbolRef Sym); RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, @@ -360,6 +302,7 @@ private: RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); + }; } // end anonymous namespace @@ -400,9 +343,11 @@ bool RangeConstraintManager::canReasonAbout(SVal X) const { if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || BinaryOperator::isRelationalOp(SSE->getOpcode())) { // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc. + // We've recently started producing Loc <> NonLoc comparisons (that + // result from casts of one of the operands between eg. intptr_t and + // void *), but we can't reason about them yet. if (Loc::isLocType(SSE->getLHS()->getType())) { - assert(Loc::isLocType(SSE->getRHS()->getType())); - return true; + return Loc::isLocType(SSE->getRHS()->getType()); } } } @@ -474,7 +419,7 @@ static RangeSet assumeNonZero( --IntType.getZeroValue()); } -/// \brief Apply implicit constraints for bitwise OR- and AND-. +/// Apply implicit constraints for bitwise OR- and AND-. /// For unsigned types, bitwise OR with a constant always returns /// a value greater-or-equal than the constant, and bitwise AND /// returns a value less-or-equal then the constant. @@ -515,9 +460,15 @@ RangeSet RangeConstraintManager::getRange(ProgramStateRef State, if (ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym)) return *V; + BasicValueFactory &BV = getBasicVals(); + + // If Sym is a difference of symbols A - B, then maybe we have range set + // stored for B - A. + if (const RangeSet *R = getRangeForMinusSymbol(State, Sym)) + return R->Negate(BV, F); + // Lazily generate a new RangeSet representing all possible values for the // given symbol type. - BasicValueFactory &BV = getBasicVals(); QualType T = Sym->getType(); RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T)); @@ -533,6 +484,32 @@ RangeSet RangeConstraintManager::getRange(ProgramStateRef State, return Result; } +// FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to +// obtain the negated symbolic expression instead of constructing the +// symbol manually. This will allow us to support finding ranges of not +// only negated SymSymExpr-type expressions, but also of other, simpler +// expressions which we currently do not know how to negate. +const RangeSet* +RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State, + SymbolRef Sym) { + if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) { + if (SSE->getOpcode() == BO_Sub) { + QualType T = Sym->getType(); + SymbolManager &SymMgr = State->getSymbolManager(); + SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, + SSE->getLHS(), T); + if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) { + // Unsigned range set cannot be negated, unless it is [0, 0]. + if ((negV->getConcreteValue() && + (*negV->getConcreteValue() == 0)) || + T->isSignedIntegerOrEnumerationType()) + return negV; + } + } + } + return nullptr; +} + //===------------------------------------------------------------------------=== // assumeSymX methods: protected interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ |