head 1.1; branch 1.1.1; access; symbols netbsd-11-0-RC4:1.1.1.8 netbsd-11-0-RC3:1.1.1.8 netbsd-11-0-RC2:1.1.1.8 netbsd-11-0-RC1:1.1.1.8 perseant-exfatfs-base-20250801:1.1.1.8 netbsd-11:1.1.1.8.0.10 netbsd-11-base:1.1.1.8 netbsd-10-1-RELEASE:1.1.1.8 perseant-exfatfs-base-20240630:1.1.1.8 perseant-exfatfs:1.1.1.8.0.8 perseant-exfatfs-base:1.1.1.8 netbsd-8-3-RELEASE:1.1.1.5 netbsd-9-4-RELEASE:1.1.1.7 netbsd-10-0-RELEASE:1.1.1.8 netbsd-10-0-RC6:1.1.1.8 netbsd-10-0-RC5:1.1.1.8 netbsd-10-0-RC4:1.1.1.8 netbsd-10-0-RC3:1.1.1.8 netbsd-10-0-RC2:1.1.1.8 netbsd-10-0-RC1:1.1.1.8 netbsd-10:1.1.1.8.0.6 netbsd-10-base:1.1.1.8 netbsd-9-3-RELEASE:1.1.1.7 cjep_sun2x:1.1.1.8.0.4 cjep_sun2x-base:1.1.1.8 cjep_staticlib_x-base1:1.1.1.8 netbsd-9-2-RELEASE:1.1.1.7 cjep_staticlib_x:1.1.1.8.0.2 cjep_staticlib_x-base:1.1.1.8 netbsd-9-1-RELEASE:1.1.1.7 phil-wifi-20200421:1.1.1.8 phil-wifi-20200411:1.1.1.8 phil-wifi-20200406:1.1.1.8 netbsd-8-2-RELEASE:1.1.1.5 netbsd-9-0-RELEASE:1.1.1.7 netbsd-9-0-RC2:1.1.1.7 netbsd-9-0-RC1:1.1.1.7 netbsd-9:1.1.1.7.0.2 netbsd-9-base:1.1.1.7 phil-wifi-20190609:1.1.1.7 netbsd-8-1-RELEASE:1.1.1.5 netbsd-8-1-RC1:1.1.1.5 pgoyette-compat-merge-20190127:1.1.1.6.2.1 pgoyette-compat-20190127:1.1.1.7 pgoyette-compat-20190118:1.1.1.7 pgoyette-compat-1226:1.1.1.7 pgoyette-compat-1126:1.1.1.7 pgoyette-compat-1020:1.1.1.7 pgoyette-compat-0930:1.1.1.7 pgoyette-compat-0906:1.1.1.7 netbsd-7-2-RELEASE:1.1.1.2.2.1 pgoyette-compat-0728:1.1.1.7 clang-337282:1.1.1.7 netbsd-8-0-RELEASE:1.1.1.5 phil-wifi:1.1.1.6.0.4 phil-wifi-base:1.1.1.6 pgoyette-compat-0625:1.1.1.6 netbsd-8-0-RC2:1.1.1.5 pgoyette-compat-0521:1.1.1.6 pgoyette-compat-0502:1.1.1.6 pgoyette-compat-0422:1.1.1.6 netbsd-8-0-RC1:1.1.1.5 pgoyette-compat-0415:1.1.1.6 pgoyette-compat-0407:1.1.1.6 pgoyette-compat-0330:1.1.1.6 pgoyette-compat-0322:1.1.1.6 pgoyette-compat-0315:1.1.1.6 netbsd-7-1-2-RELEASE:1.1.1.2.2.1 pgoyette-compat:1.1.1.6.0.2 pgoyette-compat-base:1.1.1.6 netbsd-7-1-1-RELEASE:1.1.1.2.2.1 clang-319952:1.1.1.6 matt-nb8-mediatek:1.1.1.5.0.10 matt-nb8-mediatek-base:1.1.1.5 clang-309604:1.1.1.6 perseant-stdc-iso10646:1.1.1.5.0.8 perseant-stdc-iso10646-base:1.1.1.5 netbsd-8:1.1.1.5.0.6 netbsd-8-base:1.1.1.5 prg-localcount2-base3:1.1.1.5 prg-localcount2-base2:1.1.1.5 prg-localcount2-base1:1.1.1.5 prg-localcount2:1.1.1.5.0.4 prg-localcount2-base:1.1.1.5 pgoyette-localcount-20170426:1.1.1.5 bouyer-socketcan-base1:1.1.1.5 pgoyette-localcount-20170320:1.1.1.5 netbsd-7-1:1.1.1.2.2.1.0.6 netbsd-7-1-RELEASE:1.1.1.2.2.1 netbsd-7-1-RC2:1.1.1.2.2.1 clang-294123:1.1.1.5 netbsd-7-nhusb-base-20170116:1.1.1.2.2.1 bouyer-socketcan:1.1.1.5.0.2 bouyer-socketcan-base:1.1.1.5 clang-291444:1.1.1.5 pgoyette-localcount-20170107:1.1.1.4 netbsd-7-1-RC1:1.1.1.2.2.1 pgoyette-localcount-20161104:1.1.1.4 netbsd-7-0-2-RELEASE:1.1.1.2.2.1 localcount-20160914:1.1.1.4 netbsd-7-nhusb:1.1.1.2.2.1.0.4 netbsd-7-nhusb-base:1.1.1.2.2.1 clang-280599:1.1.1.4 pgoyette-localcount-20160806:1.1.1.4 pgoyette-localcount-20160726:1.1.1.4 pgoyette-localcount:1.1.1.4.0.2 pgoyette-localcount-base:1.1.1.4 netbsd-7-0-1-RELEASE:1.1.1.2.2.1 clang-261930:1.1.1.4 netbsd-7-0:1.1.1.2.2.1.0.2 netbsd-7-0-RELEASE:1.1.1.2.2.1 netbsd-7-0-RC3:1.1.1.2.2.1 netbsd-7-0-RC2:1.1.1.2.2.1 netbsd-7-0-RC1:1.1.1.2.2.1 clang-237755:1.1.1.3 clang-232565:1.1.1.3 clang-227398:1.1.1.3 tls-maxphys-base:1.1.1.2 tls-maxphys:1.1.1.2.0.4 netbsd-7:1.1.1.2.0.2 netbsd-7-base:1.1.1.2 clang-215315:1.1.1.2 clang-209886:1.1.1.2 yamt-pagecache:1.1.1.1.0.4 yamt-pagecache-base9:1.1.1.1 tls-earlyentropy:1.1.1.1.0.2 tls-earlyentropy-base:1.1.1.2 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.1.1.1 riastradh-drm2-base3:1.1.1.1 clang-202566:1.1.1.1 clang-201163:1.1.1.1 clang-199312:1.1.1.1 clang-198450:1.1.1.1 clang-196603:1.1.1.1 clang-195771:1.1.1.1 LLVM:1.1.1; locks; strict; comment @// @; 1.1 date 2013.11.28.14.14.53; author joerg; state Exp; branches 1.1.1.1; next ; commitid ow8OybrawrB1f3fx; 1.1.1.1 date 2013.11.28.14.14.53; author joerg; state Exp; branches 1.1.1.1.2.1 1.1.1.1.4.1; next 1.1.1.2; commitid ow8OybrawrB1f3fx; 1.1.1.2 date 2014.05.30.18.14.44; author joerg; state Exp; branches 1.1.1.2.2.1 1.1.1.2.4.1; next 1.1.1.3; commitid 8q0kdlBlCn09GACx; 1.1.1.3 date 2015.01.29.19.57.30; author joerg; state Exp; branches; next 1.1.1.4; commitid mlISSizlPKvepX7y; 1.1.1.4 date 2016.02.27.22.12.06; author joerg; state Exp; branches 1.1.1.4.2.1; next 1.1.1.5; commitid tIimz3oDlh1NpBWy; 1.1.1.5 date 2017.01.11.10.35.32; author joerg; state Exp; branches; next 1.1.1.6; commitid CNnUNfII1jgNmxBz; 1.1.1.6 date 2017.08.01.19.35.14; author joerg; state Exp; branches 1.1.1.6.2.1 1.1.1.6.4.1; next 1.1.1.7; commitid pMuDy65V0VicSx1A; 1.1.1.7 date 2018.07.17.18.31.06; author joerg; state Exp; branches; next 1.1.1.8; commitid wDzL46ALjrCZgwKA; 1.1.1.8 date 2019.11.13.22.19.29; author joerg; state dead; branches; next ; commitid QD8YATxuNG34YJKB; 1.1.1.1.2.1 date 2014.08.10.07.08.10; author tls; state Exp; branches; next ; commitid t01A1TLTYxkpGMLx; 1.1.1.1.4.1 date 2013.11.28.14.14.53; author yamt; state dead; branches; next 1.1.1.1.4.2; commitid WSrDtL5nYAUyiyBx; 1.1.1.1.4.2 date 2014.05.22.16.18.31; author yamt; state Exp; branches; next ; commitid WSrDtL5nYAUyiyBx; 1.1.1.2.2.1 date 2015.06.04.20.04.30; author snj; state Exp; branches; next ; commitid yRnjq9fueSo6n9oy; 1.1.1.2.4.1 date 2014.05.30.18.14.44; author tls; state dead; branches; next 1.1.1.2.4.2; commitid jTnpym9Qu0o4R1Nx; 1.1.1.2.4.2 date 2014.08.19.23.47.32; author tls; state Exp; branches; next ; commitid jTnpym9Qu0o4R1Nx; 1.1.1.4.2.1 date 2017.03.20.06.52.42; author pgoyette; state Exp; branches; next ; commitid jjw7cAwgyKq7RfKz; 1.1.1.6.2.1 date 2018.07.28.04.33.24; author pgoyette; state Exp; branches; next ; commitid 1UP1xAIUxv1ZgRLA; 1.1.1.6.4.1 date 2019.06.10.21.45.29; author christos; state Exp; branches; next 1.1.1.6.4.2; commitid jtc8rnCzWiEEHGqB; 1.1.1.6.4.2 date 2020.04.13.07.46.39; author martin; state dead; branches; next ; commitid X01YhRUPVUDaec4C; desc @@ 1.1 log @Initial revision @ text @//== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file defines RangeConstraintManager, a class that tracks simple // equality and inequality constraints on symbolic values of ProgramState. // //===----------------------------------------------------------------------===// #include "SimpleConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableSet.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" 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 { public: Range(const llvm::APSInt &from, const llvm::APSInt &to) : std::pair(&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() : NULL; } void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddPointer(&From()); ID.AddPointer(&To()); } }; class RangeTrait : public llvm::ImutContainerInfo { 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 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) {} 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() : 0; } 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) { 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); } } } const llvm::APSInt &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) { 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; } 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; // However, if the range wraps around, it spans all possible values. Lower = Type.getMinValue(); Upper = Type.getMaxValue(); break; } break; } return true; } 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 newRanges; } 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) << ']'; } os << " }"; } bool operator==(const RangeSet &other) const { return ranges == other.ranges; } }; } // end anonymous namespace REGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintRange, CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, RangeSet)) namespace { class RangeConstraintManager : public SimpleConstraintManager{ RangeSet GetRange(ProgramStateRef state, SymbolRef sym); public: RangeConstraintManager(SubEngine *subengine, SValBuilder &SVB) : SimpleConstraintManager(subengine, SVB) {} ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymGT(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymGE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymLE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); const llvm::APSInt* getSymVal(ProgramStateRef St, SymbolRef sym) const; ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym); ProgramStateRef removeDeadBindings(ProgramStateRef St, SymbolReaper& SymReaper); void print(ProgramStateRef St, raw_ostream &Out, const char* nl, const char *sep); private: RangeSet::Factory F; }; } // end anonymous namespace ConstraintManager * ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) { return new RangeConstraintManager(Eng, StMgr.getSValBuilder()); } const llvm::APSInt* RangeConstraintManager::getSymVal(ProgramStateRef St, SymbolRef sym) const { const ConstraintRangeTy::data_type *T = St->get(sym); return T ? T->getConcreteValue() : NULL; } ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, SymbolRef Sym) { const RangeSet *Ranges = State->get(Sym); // If we don't have any information about this symbol, it's underconstrained. if (!Ranges) return ConditionTruthVal(); // If we have a concrete value, see if it's zero. if (const llvm::APSInt *Value = Ranges->getConcreteValue()) return *Value == 0; BasicValueFactory &BV = getBasicVals(); APSIntType IntType = BV.getAPSIntType(Sym->getType()); llvm::APSInt Zero = IntType.getZeroValue(); // Check if zero is in the set of possible values. if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty()) return false; // Zero is a possible value, but it is not the /only/ possible value. return ConditionTruthVal(); } /// Scan all symbols referenced by the constraints. If the symbol is not alive /// as marked in LSymbols, mark it as dead in DSymbols. ProgramStateRef RangeConstraintManager::removeDeadBindings(ProgramStateRef state, SymbolReaper& SymReaper) { ConstraintRangeTy CR = state->get(); ConstraintRangeTy::Factory& CRFactory = state->get_context(); for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) { SymbolRef sym = I.getKey(); if (SymReaper.maybeDead(sym)) CR = CRFactory.remove(CR, sym); } return state->set(CR); } RangeSet RangeConstraintManager::GetRange(ProgramStateRef state, SymbolRef sym) { if (ConstraintRangeTy::data_type* V = state->get(sym)) return *V; // 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)); // Special case: references are known to be non-zero. if (T->isReferenceType()) { APSIntType IntType = BV.getAPSIntType(T); Result = Result.Intersect(BV, F, ++IntType.getZeroValue(), --IntType.getZeroValue()); } return Result; } //===------------------------------------------------------------------------=== // assumeSymX methods: public interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ // The syntax for ranges below is mathematical, using [x, y] for closed ranges // and (x, y) for open ranges. These ranges are modular, corresponding with // a common treatment of C integer overflow. This means that these methods // do not have to worry about overflow; RangeSet::Intersect can handle such a // "wraparound" range. // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, // UINT_MAX, 0, 1, and 2. ProgramStateRef RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return St; llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment; llvm::APSInt Upper = Lower; --Lower; ++Upper; // [Int-Adjustment+1, Int-Adjustment-1] // Notice that the lower bound is greater than the upper bound. RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return NULL; // [Int-Adjustment, Int-Adjustment] llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return NULL; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return St; } // Special case for Int == Min. This is always false. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) return NULL; llvm::APSInt Lower = Min-Adjustment; llvm::APSInt Upper = ComparisonVal-Adjustment; --Upper; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return St; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return NULL; } // Special case for Int == Max. This is always false. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) return NULL; llvm::APSInt Lower = ComparisonVal-Adjustment; llvm::APSInt Upper = Max-Adjustment; ++Lower; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return St; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return NULL; } // Special case for Int == Min. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) return St; llvm::APSInt Max = AdjustmentType.getMaxValue(); llvm::APSInt Lower = ComparisonVal-Adjustment; llvm::APSInt Upper = Max-Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return NULL; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return St; } // Special case for Int == Max. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) return St; llvm::APSInt Min = AdjustmentType.getMinValue(); llvm::APSInt Lower = Min-Adjustment; llvm::APSInt Upper = ComparisonVal-Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? NULL : St->set(Sym, New); } //===------------------------------------------------------------------------=== // Pretty-printing. //===------------------------------------------------------------------------===/ void RangeConstraintManager::print(ProgramStateRef St, raw_ostream &Out, const char* nl, const char *sep) { ConstraintRangeTy Ranges = St->get(); if (Ranges.isEmpty()) { Out << nl << sep << "Ranges are empty." << nl; return; } Out << nl << sep << "Ranges of symbol values:"; for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){ Out << nl << ' ' << I.getKey() << " : "; I.getData().print(Out); } Out << nl; } @ 1.1.1.1 log @Import Clang 3.4rc1 r195771. @ text @@ 1.1.1.1.2.1 log @Rebase. @ text @d48 1 a48 1 return &From() == &To() ? &From() : nullptr; d101 1 a101 1 return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; d293 1 a293 1 const llvm::APSInt& Adjustment) override; d297 1 a297 1 const llvm::APSInt& Adjustment) override; d301 1 a301 1 const llvm::APSInt& Adjustment) override; d305 1 a305 1 const llvm::APSInt& Adjustment) override; d309 1 a309 1 const llvm::APSInt& Adjustment) override; d313 1 a313 1 const llvm::APSInt& Adjustment) override; d315 2 a316 3 const llvm::APSInt* getSymVal(ProgramStateRef St, SymbolRef sym) const override; ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; d318 1 a318 2 ProgramStateRef removeDeadBindings(ProgramStateRef St, SymbolReaper& SymReaper) override; d321 1 a321 1 const char* nl, const char *sep) override; d337 1 a337 1 return T ? T->getConcreteValue() : nullptr; d433 1 a433 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d443 1 a443 1 return nullptr; d448 1 a448 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d459 1 a459 1 return nullptr; d470 1 a470 1 return nullptr; d477 1 a477 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d492 1 a492 1 return nullptr; d499 1 a499 1 return nullptr; d506 1 a506 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d521 1 a521 1 return nullptr; d535 1 a535 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d546 1 a546 1 return nullptr; d564 1 a564 1 return New.isEmpty() ? nullptr : St->set(Sym, New); @ 1.1.1.2 log @Import Clang 3.5svn r209886. @ text @d48 1 a48 1 return &From() == &To() ? &From() : nullptr; d101 1 a101 1 return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; d293 1 a293 1 const llvm::APSInt& Adjustment) override; d297 1 a297 1 const llvm::APSInt& Adjustment) override; d301 1 a301 1 const llvm::APSInt& Adjustment) override; d305 1 a305 1 const llvm::APSInt& Adjustment) override; d309 1 a309 1 const llvm::APSInt& Adjustment) override; d313 1 a313 1 const llvm::APSInt& Adjustment) override; d315 2 a316 3 const llvm::APSInt* getSymVal(ProgramStateRef St, SymbolRef sym) const override; ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; d318 1 a318 2 ProgramStateRef removeDeadBindings(ProgramStateRef St, SymbolReaper& SymReaper) override; d321 1 a321 1 const char* nl, const char *sep) override; d337 1 a337 1 return T ? T->getConcreteValue() : nullptr; d433 1 a433 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d443 1 a443 1 return nullptr; d448 1 a448 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d459 1 a459 1 return nullptr; d470 1 a470 1 return nullptr; d477 1 a477 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d492 1 a492 1 return nullptr; d499 1 a499 1 return nullptr; d506 1 a506 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d521 1 a521 1 return nullptr; d535 1 a535 1 return New.isEmpty() ? nullptr : St->set(Sym, New); d546 1 a546 1 return nullptr; d564 1 a564 1 return New.isEmpty() ? nullptr : St->set(Sym, New); @ 1.1.1.2.2.1 log @Update LLVM to 3.6.1, requested by joerg in ticket 824. @ text @d331 1 a331 1 std::unique_ptr d333 1 a333 1 return llvm::make_unique(Eng, StMgr.getSValBuilder()); @ 1.1.1.3 log @Import Clang 3.6RC1 r227398. @ text @d331 1 a331 1 std::unique_ptr d333 1 a333 1 return llvm::make_unique(Eng, StMgr.getSValBuilder()); @ 1.1.1.4 log @Import Clang 3.8.0rc3 r261930. @ text @a83 9 /// 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); } d165 1 a165 1 if (Lower <= Upper) d216 1 a216 1 if (Lower <= Upper) a314 8 ProgramStateRef assumeSymbolWithinInclusiveRange( ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymbolOutOfInclusiveRange( ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; a326 14 RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); RangeSet getSymLERange(const RangeSet &RS, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); d368 1 a368 1 ProgramStateRef d418 1 a418 1 ProgramStateRef d438 1 a438 1 ProgramStateRef d453 4 a456 4 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d461 1 a461 1 return F.getEmptySet(); d465 1 a465 1 return GetRange(St, Sym); d472 1 a472 1 return F.getEmptySet(); d474 2 a475 2 llvm::APSInt Lower = Min - Adjustment; llvm::APSInt Upper = ComparisonVal - Adjustment; d478 2 a479 1 return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d482 2 a483 2 ProgramStateRef RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, a485 8 RangeSet New = getSymLTRange(St, Sym, Int, Adjustment); return New.isEmpty() ? nullptr : St->set(Sym, New); } RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d490 1 a490 1 return GetRange(St, Sym); d494 1 a494 1 return F.getEmptySet(); d501 1 a501 1 return F.getEmptySet(); d503 2 a504 2 llvm::APSInt Lower = ComparisonVal - Adjustment; llvm::APSInt Upper = Max - Adjustment; d507 2 a508 1 return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d511 2 a512 2 ProgramStateRef RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, a514 8 RangeSet New = getSymGTRange(St, Sym, Int, Adjustment); return New.isEmpty() ? nullptr : St->set(Sym, New); } RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d519 1 a519 1 return GetRange(St, Sym); d523 1 a523 1 return F.getEmptySet(); d530 1 a530 1 return GetRange(St, Sym); d533 2 a534 2 llvm::APSInt Lower = ComparisonVal - Adjustment; llvm::APSInt Upper = Max - Adjustment; d536 2 a537 1 return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d540 2 a541 2 ProgramStateRef RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, a543 8 RangeSet New = getSymGERange(St, Sym, Int, Adjustment); return New.isEmpty() ? nullptr : St->set(Sym, New); } RangeSet RangeConstraintManager::getSymLERange(const RangeSet &RS, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d548 1 a548 1 return F.getEmptySet(); d552 1 a552 1 return RS; d559 1 a559 29 return RS; llvm::APSInt Min = AdjustmentType.getMinValue(); llvm::APSInt Lower = Min - Adjustment; llvm::APSInt Upper = ComparisonVal - Adjustment; return RS.Intersect(getBasicVals(), F, Lower, Upper); } RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return F.getEmptySet(); case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return GetRange(St, Sym); } // Special case for Int == Max. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) return GetRange(St, Sym); d562 2 a563 5 llvm::APSInt Lower = Min - Adjustment; llvm::APSInt Upper = ComparisonVal - Adjustment; return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } d565 1 a565 5 ProgramStateRef RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { RangeSet New = getSymLERange(St, Sym, Int, Adjustment); a568 21 ProgramStateRef RangeConstraintManager::assumeSymbolWithinInclusiveRange( ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) { RangeSet New = getSymGERange(State, Sym, From, Adjustment); if (New.isEmpty()) return nullptr; New = getSymLERange(New, To, Adjustment); return New.isEmpty() ? nullptr : State->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymbolOutOfInclusiveRange( ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) { RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment); RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment); RangeSet New(RangeLT.addRange(F, RangeGT)); return New.isEmpty() ? nullptr : State->set(Sym, New); } @ 1.1.1.4.2.1 log @Sync with HEAD @ text @d21 1 d31 2 a32 1 class Range : public std::pair { d35 1 a35 1 : std::pair(&from, &to) { d41 6 a46 2 const llvm::APSInt &From() const { return *first; } const llvm::APSInt &To() const { return *second; } d57 1 d65 2 a66 2 return *lhs.first < *rhs.first || (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); d100 1 a100 1 : ranges(F.add(F.getEmptySet(), Range(from, to))) {} d109 1 a109 1 const llvm::APSInt *getConcreteValue() const { d115 4 a118 2 const llvm::APSInt &Lower, const llvm::APSInt &Upper, PrimRangeSet &newRanges, PrimRangeSet::iterator &i, d138 2 a139 2 newRanges = F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); d247 2 a248 2 RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, llvm::APSInt Upper) const { d294 2 a295 3 class RangeConstraintManager : public SimpleConstraintManager { RangeSet getRange(ProgramStateRef State, SymbolRef Sym); d297 2 a298 2 RangeConstraintManager(SubEngine *SE, SValBuilder &SVB) : SimpleConstraintManager(SE, SVB) {} d300 23 a322 23 ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; d325 2 a326 2 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; d329 2 a330 2 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; d332 2 a333 2 const llvm::APSInt *getSymVal(ProgramStateRef St, SymbolRef Sym) const override; d337 1 a337 1 SymbolReaper &SymReaper) override; d339 2 a340 2 void print(ProgramStateRef St, raw_ostream &Out, const char *nl, const char *sep) override; d367 3 a369 3 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, SymbolRef Sym) const { const ConstraintRangeTy::data_type *T = St->get(Sym); d400 5 a404 5 RangeConstraintManager::removeDeadBindings(ProgramStateRef State, SymbolReaper &SymReaper) { bool Changed = false; ConstraintRangeTy CR = State->get(); ConstraintRangeTy::Factory &CRFactory = State->get_context(); d407 3 a409 5 SymbolRef Sym = I.getKey(); if (SymReaper.maybeDead(Sym)) { Changed = true; CR = CRFactory.remove(CR, Sym); } d412 1 a412 1 return Changed ? State->set(CR) : State; d415 3 a417 3 RangeSet RangeConstraintManager::getRange(ProgramStateRef State, SymbolRef Sym) { if (ConstraintRangeTy::data_type *V = State->get(Sym)) d423 1 a423 1 QualType T = Sym->getType(); d431 1 a431 1 --IntType.getZeroValue()); d465 1 a465 1 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); d480 1 a480 1 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); d496 1 a496 1 return getRange(St, Sym); d509 1 a509 1 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d520 4 a523 4 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d528 1 a528 1 return getRange(St, Sym); d545 1 a545 1 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d556 4 a559 4 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d564 1 a564 1 return getRange(St, Sym); d575 1 a575 1 return getRange(St, Sym); d581 1 a581 1 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d592 4 a595 3 RangeSet RangeConstraintManager::getSymLERange(const RangeSet &RS, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d620 4 a623 4 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d632 1 a632 1 return getRange(St, Sym); d639 1 a639 1 return getRange(St, Sym); d645 1 a645 1 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d656 2 a657 1 ProgramStateRef RangeConstraintManager::assumeSymbolWithinInclusiveRange( d667 2 a668 1 ProgramStateRef RangeConstraintManager::assumeSymbolOutOfInclusiveRange( d682 1 a682 1 const char *nl, const char *sep) { d692 1 a692 2 for (ConstraintRangeTy::iterator I = Ranges.begin(), E = Ranges.end(); I != E; ++I) { @ 1.1.1.5 log @Import Clang pre-4.0.0 r291444. @ text @d21 1 d31 2 a32 1 class Range : public std::pair { d35 1 a35 1 : std::pair(&from, &to) { d41 6 a46 2 const llvm::APSInt &From() const { return *first; } const llvm::APSInt &To() const { return *second; } d57 1 d65 2 a66 2 return *lhs.first < *rhs.first || (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); d100 1 a100 1 : ranges(F.add(F.getEmptySet(), Range(from, to))) {} d109 1 a109 1 const llvm::APSInt *getConcreteValue() const { d115 4 a118 2 const llvm::APSInt &Lower, const llvm::APSInt &Upper, PrimRangeSet &newRanges, PrimRangeSet::iterator &i, d138 2 a139 2 newRanges = F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); d247 2 a248 2 RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, llvm::APSInt Upper) const { d294 2 a295 3 class RangeConstraintManager : public SimpleConstraintManager { RangeSet getRange(ProgramStateRef State, SymbolRef Sym); d297 2 a298 2 RangeConstraintManager(SubEngine *SE, SValBuilder &SVB) : SimpleConstraintManager(SE, SVB) {} d300 23 a322 23 ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment) override; d325 2 a326 2 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; d329 2 a330 2 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; d332 2 a333 2 const llvm::APSInt *getSymVal(ProgramStateRef St, SymbolRef Sym) const override; d337 1 a337 1 SymbolReaper &SymReaper) override; d339 2 a340 2 void print(ProgramStateRef St, raw_ostream &Out, const char *nl, const char *sep) override; d367 3 a369 3 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, SymbolRef Sym) const { const ConstraintRangeTy::data_type *T = St->get(Sym); d400 5 a404 5 RangeConstraintManager::removeDeadBindings(ProgramStateRef State, SymbolReaper &SymReaper) { bool Changed = false; ConstraintRangeTy CR = State->get(); ConstraintRangeTy::Factory &CRFactory = State->get_context(); d407 3 a409 5 SymbolRef Sym = I.getKey(); if (SymReaper.maybeDead(Sym)) { Changed = true; CR = CRFactory.remove(CR, Sym); } d412 1 a412 1 return Changed ? State->set(CR) : State; d415 3 a417 3 RangeSet RangeConstraintManager::getRange(ProgramStateRef State, SymbolRef Sym) { if (ConstraintRangeTy::data_type *V = State->get(Sym)) d423 1 a423 1 QualType T = Sym->getType(); d431 1 a431 1 --IntType.getZeroValue()); d465 1 a465 1 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); d480 1 a480 1 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); d496 1 a496 1 return getRange(St, Sym); d509 1 a509 1 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d520 4 a523 4 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d528 1 a528 1 return getRange(St, Sym); d545 1 a545 1 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d556 4 a559 4 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d564 1 a564 1 return getRange(St, Sym); d575 1 a575 1 return getRange(St, Sym); d581 1 a581 1 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d592 4 a595 3 RangeSet RangeConstraintManager::getSymLERange(const RangeSet &RS, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d620 4 a623 4 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d632 1 a632 1 return getRange(St, Sym); d639 1 a639 1 return getRange(St, Sym); d645 1 a645 1 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); d656 2 a657 1 ProgramStateRef RangeConstraintManager::assumeSymbolWithinInclusiveRange( d667 2 a668 1 ProgramStateRef RangeConstraintManager::assumeSymbolOutOfInclusiveRange( d682 1 a682 1 const char *nl, const char *sep) { d692 1 a692 2 for (ConstraintRangeTy::iterator I = Ranges.begin(), E = Ranges.end(); I != E; ++I) { @ 1.1.1.6 log @Import clang r309604 from branches/release_50 @ text @d15 1 a15 1 #include "RangedConstraintManager.h" d285 3 a287 1 class RangeConstraintManager : public RangedConstraintManager { d290 1 a290 22 : RangedConstraintManager(SE, SVB) {} //===------------------------------------------------------------------===// // Implementation for interface from ConstraintManager. //===------------------------------------------------------------------===// bool canReasonAbout(SVal X) const override; ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; const llvm::APSInt *getSymVal(ProgramStateRef State, SymbolRef Sym) const override; ProgramStateRef removeDeadBindings(ProgramStateRef State, SymbolReaper &SymReaper) override; void print(ProgramStateRef State, raw_ostream &Out, const char *nl, const char *sep) override; //===------------------------------------------------------------------===// // Implementation for interface from RangedConstraintManager. //===------------------------------------------------------------------===// d316 1 a316 1 ProgramStateRef assumeSymWithinInclusiveRange( d320 1 a320 1 ProgramStateRef assumeSymOutsideInclusiveRange( d324 10 a335 3 RangeSet getRange(ProgramStateRef State, SymbolRef Sym); d359 4 a362 40 bool RangeConstraintManager::canReasonAbout(SVal X) const { Optional SymVal = X.getAs(); if (SymVal && SymVal->isExpression()) { const SymExpr *SE = SymVal->getSymbol(); if (const SymIntExpr *SIE = dyn_cast(SE)) { switch (SIE->getOpcode()) { // We don't reason yet about bitwise-constraints on symbolic values. case BO_And: case BO_Or: case BO_Xor: return false; // We don't reason yet about these arithmetic constraints on // symbolic values. case BO_Mul: case BO_Div: case BO_Rem: case BO_Shl: case BO_Shr: return false; // All other cases. default: return true; } } if (const SymSymExpr *SSE = dyn_cast(SE)) { if (BinaryOperator::isComparisonOp(SSE->getOpcode())) { // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc. if (Loc::isLocType(SSE->getLHS()->getType())) { assert(Loc::isLocType(SSE->getRHS()->getType())); return true; } } } return false; } return true; a388 6 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, SymbolRef Sym) const { const ConstraintRangeTy::data_type *T = St->get(Sym); return T ? T->getConcreteValue() : nullptr; } d432 1 a432 1 // assumeSymX methods: protected interface for RangeConstraintManager. d649 1 a649 1 ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange( d659 1 a659 1 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange( @ 1.1.1.6.4.1 log @Sync with HEAD @ text @d15 1 a18 1 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" d26 79 a104 19 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; } d106 18 a123 4 if (i->Includes(Lower)) { if (i->Includes(Upper)) { newRanges = F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); d125 16 a140 8 } 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); a142 1 } d144 14 a157 14 const llvm::APSInt &RangeSet::getMinValue() const { assert(!isEmpty()); return ranges.begin()->From(); } 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); d159 1 a159 3 switch (LowerTest) { case APSIntType::RTR_Below: switch (UpperTest) { d161 22 a182 8 // 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(); d185 17 a201 3 // The range starts below what's possible but ends within it. Pin. Lower = Type.getMinValue(); Type.apply(Upper); d204 20 a223 22 // 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(); a225 16 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; d227 1 a227 6 // However, if the range wraps around, it spans all possible values. Lower = Type.getMinValue(); Upper = Type.getMaxValue(); break; } break; d230 37 a266 16 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(); PrimRangeSet newRanges = F.getEmptySet(); d268 2 a269 40 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 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))); d271 1 d274 5 a278 2 return newRanges; } d280 3 a282 14 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 << " }"; } a346 2 const RangeSet* getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym); d357 1 a357 2 RangeSet getSymLERange(llvm::function_ref RS, const llvm::APSInt &Int, a361 1 d398 1 a398 3 // FIXME: Handle <=> here. if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || BinaryOperator::isRelationalOp(SSE->getOpcode())) { a462 47 /// Return a range set subtracting zero from \p Domain. static RangeSet assumeNonZero( BasicValueFactory &BV, RangeSet::Factory &F, SymbolRef Sym, RangeSet Domain) { APSIntType IntType = BV.getAPSIntType(Sym->getType()); return Domain.Intersect(BV, F, ++IntType.getZeroValue(), --IntType.getZeroValue()); } /// 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. /// /// Pattern matches the expression \p Sym against those rule, /// and applies the required constraints. /// \p Input Previously established expression range set static RangeSet applyBitwiseConstraints( BasicValueFactory &BV, RangeSet::Factory &F, RangeSet Input, const SymIntExpr* SIE) { QualType T = SIE->getType(); bool IsUnsigned = T->isUnsignedIntegerType(); const llvm::APSInt &RHS = SIE->getRHS(); const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue(); BinaryOperator::Opcode Operator = SIE->getOpcode(); // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS. if (Operator == BO_Or && IsUnsigned) return Input.Intersect(BV, F, RHS, BV.getMaxValue(T)); // Bitwise-or with a non-zero constant is always non-zero. if (Operator == BO_Or && RHS != Zero) return assumeNonZero(BV, F, SIE, Input); // For unsigned types, or positive RHS, // bitwise-and output is always smaller-or-equal than RHS (assuming two's // complement representation of signed types). if (Operator == BO_And && (IsUnsigned || RHS >= Zero)) return Input.Intersect(BV, F, BV.getMinValue(T), RHS); return Input; } a467 7 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); d470 1 d475 6 a480 7 // References are known to be non-zero. if (T->isReferenceType()) return assumeNonZero(BV, F, Sym, Result); // Known constraints on ranges of bitwise expressions. if (const SymIntExpr* SIE = dyn_cast(Sym)) return applyBitwiseConstraints(BV, F, Result, SIE); a484 26 // 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(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(negSym)) { // Unsigned range set cannot be negated, unless it is [0, 0]. if ((negV->getConcreteValue() && (*negV->getConcreteValue() == 0)) || T->isSignedIntegerOrEnumerationType()) return negV; } } } return nullptr; } d640 3 a642 4 RangeSet RangeConstraintManager::getSymLERange( llvm::function_ref RS, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d651 1 a651 1 return RS(); d658 1 a658 1 return RS(); d664 1 a664 1 return RS().Intersect(getBasicVals(), F, Lower, Upper); d671 22 a692 1 return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment); d709 2 a710 2 RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment); return Out.isEmpty() ? nullptr : State->set(Sym, Out); @ 1.1.1.6.4.2 log @Mostly merge changes from HEAD upto 20200411 @ text @@ 1.1.1.6.2.1 log @Sync with HEAD @ text @d15 1 a18 1 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" d26 79 a104 19 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; } d106 18 a123 4 if (i->Includes(Lower)) { if (i->Includes(Upper)) { newRanges = F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); d125 16 a140 8 } 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); a142 1 } d144 14 a157 14 const llvm::APSInt &RangeSet::getMinValue() const { assert(!isEmpty()); return ranges.begin()->From(); } 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); d159 1 a159 3 switch (LowerTest) { case APSIntType::RTR_Below: switch (UpperTest) { d161 22 a182 8 // 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(); d185 17 a201 3 // The range starts below what's possible but ends within it. Pin. Lower = Type.getMinValue(); Type.apply(Upper); d204 20 a223 22 // 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(); a225 16 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; d227 1 a227 6 // However, if the range wraps around, it spans all possible values. Lower = Type.getMinValue(); Upper = Type.getMaxValue(); break; } break; d230 37 a266 16 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(); PrimRangeSet newRanges = F.getEmptySet(); d268 2 a269 40 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 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))); d271 1 d274 5 a278 2 return newRanges; } d280 3 a282 14 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 << " }"; } a346 2 const RangeSet* getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym); d357 1 a357 2 RangeSet getSymLERange(llvm::function_ref RS, const llvm::APSInt &Int, a361 1 d398 1 a398 3 // FIXME: Handle <=> here. if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || BinaryOperator::isRelationalOp(SSE->getOpcode())) { a462 47 /// Return a range set subtracting zero from \p Domain. static RangeSet assumeNonZero( BasicValueFactory &BV, RangeSet::Factory &F, SymbolRef Sym, RangeSet Domain) { APSIntType IntType = BV.getAPSIntType(Sym->getType()); return Domain.Intersect(BV, F, ++IntType.getZeroValue(), --IntType.getZeroValue()); } /// 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. /// /// Pattern matches the expression \p Sym against those rule, /// and applies the required constraints. /// \p Input Previously established expression range set static RangeSet applyBitwiseConstraints( BasicValueFactory &BV, RangeSet::Factory &F, RangeSet Input, const SymIntExpr* SIE) { QualType T = SIE->getType(); bool IsUnsigned = T->isUnsignedIntegerType(); const llvm::APSInt &RHS = SIE->getRHS(); const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue(); BinaryOperator::Opcode Operator = SIE->getOpcode(); // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS. if (Operator == BO_Or && IsUnsigned) return Input.Intersect(BV, F, RHS, BV.getMaxValue(T)); // Bitwise-or with a non-zero constant is always non-zero. if (Operator == BO_Or && RHS != Zero) return assumeNonZero(BV, F, SIE, Input); // For unsigned types, or positive RHS, // bitwise-and output is always smaller-or-equal than RHS (assuming two's // complement representation of signed types). if (Operator == BO_And && (IsUnsigned || RHS >= Zero)) return Input.Intersect(BV, F, BV.getMinValue(T), RHS); return Input; } a467 7 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); d470 1 d475 6 a480 7 // References are known to be non-zero. if (T->isReferenceType()) return assumeNonZero(BV, F, Sym, Result); // Known constraints on ranges of bitwise expressions. if (const SymIntExpr* SIE = dyn_cast(Sym)) return applyBitwiseConstraints(BV, F, Result, SIE); a484 26 // 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(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(negSym)) { // Unsigned range set cannot be negated, unless it is [0, 0]. if ((negV->getConcreteValue() && (*negV->getConcreteValue() == 0)) || T->isSignedIntegerOrEnumerationType()) return negV; } } } return nullptr; } d640 3 a642 4 RangeSet RangeConstraintManager::getSymLERange( llvm::function_ref RS, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d651 1 a651 1 return RS(); d658 1 a658 1 return RS(); d664 1 a664 1 return RS().Intersect(getBasicVals(), F, Lower, Upper); d671 22 a692 1 return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment); d709 2 a710 2 RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment); return Out.isEmpty() ? nullptr : State->set(Sym, Out); @ 1.1.1.7 log @Import clang r337282 from trunk @ text @d15 1 a18 1 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" d26 79 a104 19 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; } d106 18 a123 4 if (i->Includes(Lower)) { if (i->Includes(Upper)) { newRanges = F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); d125 16 a140 8 } 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); a142 1 } d144 14 a157 14 const llvm::APSInt &RangeSet::getMinValue() const { assert(!isEmpty()); return ranges.begin()->From(); } 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); d159 1 a159 3 switch (LowerTest) { case APSIntType::RTR_Below: switch (UpperTest) { d161 22 a182 8 // 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(); d185 17 a201 3 // The range starts below what's possible but ends within it. Pin. Lower = Type.getMinValue(); Type.apply(Upper); d204 20 a223 22 // 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(); a225 16 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; d227 1 a227 6 // However, if the range wraps around, it spans all possible values. Lower = Type.getMinValue(); Upper = Type.getMaxValue(); break; } break; d230 37 a266 16 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(); PrimRangeSet newRanges = F.getEmptySet(); d268 2 a269 40 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 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))); d271 1 d274 5 a278 2 return newRanges; } d280 3 a282 14 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 << " }"; } a346 2 const RangeSet* getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym); d357 1 a357 2 RangeSet getSymLERange(llvm::function_ref RS, const llvm::APSInt &Int, a361 1 d398 1 a398 3 // FIXME: Handle <=> here. if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || BinaryOperator::isRelationalOp(SSE->getOpcode())) { a462 47 /// Return a range set subtracting zero from \p Domain. static RangeSet assumeNonZero( BasicValueFactory &BV, RangeSet::Factory &F, SymbolRef Sym, RangeSet Domain) { APSIntType IntType = BV.getAPSIntType(Sym->getType()); return Domain.Intersect(BV, F, ++IntType.getZeroValue(), --IntType.getZeroValue()); } /// 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. /// /// Pattern matches the expression \p Sym against those rule, /// and applies the required constraints. /// \p Input Previously established expression range set static RangeSet applyBitwiseConstraints( BasicValueFactory &BV, RangeSet::Factory &F, RangeSet Input, const SymIntExpr* SIE) { QualType T = SIE->getType(); bool IsUnsigned = T->isUnsignedIntegerType(); const llvm::APSInt &RHS = SIE->getRHS(); const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue(); BinaryOperator::Opcode Operator = SIE->getOpcode(); // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS. if (Operator == BO_Or && IsUnsigned) return Input.Intersect(BV, F, RHS, BV.getMaxValue(T)); // Bitwise-or with a non-zero constant is always non-zero. if (Operator == BO_Or && RHS != Zero) return assumeNonZero(BV, F, SIE, Input); // For unsigned types, or positive RHS, // bitwise-and output is always smaller-or-equal than RHS (assuming two's // complement representation of signed types). if (Operator == BO_And && (IsUnsigned || RHS >= Zero)) return Input.Intersect(BV, F, BV.getMinValue(T), RHS); return Input; } a467 7 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); d470 1 d475 6 a480 7 // References are known to be non-zero. if (T->isReferenceType()) return assumeNonZero(BV, F, Sym, Result); // Known constraints on ranges of bitwise expressions. if (const SymIntExpr* SIE = dyn_cast(Sym)) return applyBitwiseConstraints(BV, F, Result, SIE); a484 26 // 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(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(negSym)) { // Unsigned range set cannot be negated, unless it is [0, 0]. if ((negV->getConcreteValue() && (*negV->getConcreteValue() == 0)) || T->isSignedIntegerOrEnumerationType()) return negV; } } } return nullptr; } d640 3 a642 4 RangeSet RangeConstraintManager::getSymLERange( llvm::function_ref RS, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { d651 1 a651 1 return RS(); d658 1 a658 1 return RS(); d664 1 a664 1 return RS().Intersect(getBasicVals(), F, Lower, Upper); d671 22 a692 1 return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment); d709 2 a710 2 RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment); return Out.isEmpty() ? nullptr : State->set(Sym, Out); @ 1.1.1.8 log @Mark old LLVM instance as dead. @ text @@ 1.1.1.2.4.1 log @file RangeConstraintManager.cpp was added on branch tls-maxphys on 2014-08-19 23:47:32 +0000 @ text @d1 589 @ 1.1.1.2.4.2 log @Rebase to HEAD as of a few days ago. @ text @a0 589 //== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file defines RangeConstraintManager, a class that tracks simple // equality and inequality constraints on symbolic values of ProgramState. // //===----------------------------------------------------------------------===// #include "SimpleConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableSet.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" 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 { public: Range(const llvm::APSInt &from, const llvm::APSInt &to) : std::pair(&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 { 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 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) {} 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; } 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) { 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); } } } const llvm::APSInt &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) { 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; } 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; // However, if the range wraps around, it spans all possible values. Lower = Type.getMinValue(); Upper = Type.getMaxValue(); break; } break; } return true; } 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 newRanges; } 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) << ']'; } os << " }"; } bool operator==(const RangeSet &other) const { return ranges == other.ranges; } }; } // end anonymous namespace REGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintRange, CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, RangeSet)) namespace { class RangeConstraintManager : public SimpleConstraintManager{ RangeSet GetRange(ProgramStateRef state, SymbolRef sym); public: RangeConstraintManager(SubEngine *subengine, SValBuilder &SVB) : SimpleConstraintManager(subengine, SVB) {} ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment) override; ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment) override; ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment) override; ProgramStateRef assumeSymGT(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment) override; ProgramStateRef assumeSymGE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment) override; ProgramStateRef assumeSymLE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment) override; const llvm::APSInt* getSymVal(ProgramStateRef St, SymbolRef sym) const override; ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; ProgramStateRef removeDeadBindings(ProgramStateRef St, SymbolReaper& SymReaper) override; void print(ProgramStateRef St, raw_ostream &Out, const char* nl, const char *sep) override; private: RangeSet::Factory F; }; } // end anonymous namespace ConstraintManager * ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) { return new RangeConstraintManager(Eng, StMgr.getSValBuilder()); } const llvm::APSInt* RangeConstraintManager::getSymVal(ProgramStateRef St, SymbolRef sym) const { const ConstraintRangeTy::data_type *T = St->get(sym); return T ? T->getConcreteValue() : nullptr; } ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, SymbolRef Sym) { const RangeSet *Ranges = State->get(Sym); // If we don't have any information about this symbol, it's underconstrained. if (!Ranges) return ConditionTruthVal(); // If we have a concrete value, see if it's zero. if (const llvm::APSInt *Value = Ranges->getConcreteValue()) return *Value == 0; BasicValueFactory &BV = getBasicVals(); APSIntType IntType = BV.getAPSIntType(Sym->getType()); llvm::APSInt Zero = IntType.getZeroValue(); // Check if zero is in the set of possible values. if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty()) return false; // Zero is a possible value, but it is not the /only/ possible value. return ConditionTruthVal(); } /// Scan all symbols referenced by the constraints. If the symbol is not alive /// as marked in LSymbols, mark it as dead in DSymbols. ProgramStateRef RangeConstraintManager::removeDeadBindings(ProgramStateRef state, SymbolReaper& SymReaper) { ConstraintRangeTy CR = state->get(); ConstraintRangeTy::Factory& CRFactory = state->get_context(); for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) { SymbolRef sym = I.getKey(); if (SymReaper.maybeDead(sym)) CR = CRFactory.remove(CR, sym); } return state->set(CR); } RangeSet RangeConstraintManager::GetRange(ProgramStateRef state, SymbolRef sym) { if (ConstraintRangeTy::data_type* V = state->get(sym)) return *V; // 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)); // Special case: references are known to be non-zero. if (T->isReferenceType()) { APSIntType IntType = BV.getAPSIntType(T); Result = Result.Intersect(BV, F, ++IntType.getZeroValue(), --IntType.getZeroValue()); } return Result; } //===------------------------------------------------------------------------=== // assumeSymX methods: public interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ // The syntax for ranges below is mathematical, using [x, y] for closed ranges // and (x, y) for open ranges. These ranges are modular, corresponding with // a common treatment of C integer overflow. This means that these methods // do not have to worry about overflow; RangeSet::Intersect can handle such a // "wraparound" range. // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, // UINT_MAX, 0, 1, and 2. ProgramStateRef RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return St; llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment; llvm::APSInt Upper = Lower; --Lower; ++Upper; // [Int-Adjustment+1, Int-Adjustment-1] // Notice that the lower bound is greater than the upper bound. RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); return New.isEmpty() ? nullptr : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return nullptr; // [Int-Adjustment, Int-Adjustment] llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); return New.isEmpty() ? nullptr : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return nullptr; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return St; } // Special case for Int == Min. This is always false. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) return nullptr; llvm::APSInt Lower = Min-Adjustment; llvm::APSInt Upper = ComparisonVal-Adjustment; --Upper; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? nullptr : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return St; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return nullptr; } // Special case for Int == Max. This is always false. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) return nullptr; llvm::APSInt Lower = ComparisonVal-Adjustment; llvm::APSInt Upper = Max-Adjustment; ++Lower; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? nullptr : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return St; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return nullptr; } // Special case for Int == Min. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) return St; llvm::APSInt Max = AdjustmentType.getMaxValue(); llvm::APSInt Lower = ComparisonVal-Adjustment; llvm::APSInt Upper = Max-Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? nullptr : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return nullptr; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return St; } // Special case for Int == Max. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) return St; llvm::APSInt Min = AdjustmentType.getMinValue(); llvm::APSInt Lower = Min-Adjustment; llvm::APSInt Upper = ComparisonVal-Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? nullptr : St->set(Sym, New); } //===------------------------------------------------------------------------=== // Pretty-printing. //===------------------------------------------------------------------------===/ void RangeConstraintManager::print(ProgramStateRef St, raw_ostream &Out, const char* nl, const char *sep) { ConstraintRangeTy Ranges = St->get(); if (Ranges.isEmpty()) { Out << nl << sep << "Ranges are empty." << nl; return; } Out << nl << sep << "Ranges of symbol values:"; for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){ Out << nl << ' ' << I.getKey() << " : "; I.getData().print(Out); } Out << nl; } @ 1.1.1.1.4.1 log @file RangeConstraintManager.cpp was added on branch yamt-pagecache on 2014-05-22 16:18:31 +0000 @ text @d1 587 @ 1.1.1.1.4.2 log @sync with head. for a reference, the tree before this commit was tagged as yamt-pagecache-tag8. this commit was splitted into small chunks to avoid a limitation of cvs. ("Protocol error: too many arguments") @ text @a0 587 //== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file defines RangeConstraintManager, a class that tracks simple // equality and inequality constraints on symbolic values of ProgramState. // //===----------------------------------------------------------------------===// #include "SimpleConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableSet.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" 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 { public: Range(const llvm::APSInt &from, const llvm::APSInt &to) : std::pair(&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() : NULL; } void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddPointer(&From()); ID.AddPointer(&To()); } }; class RangeTrait : public llvm::ImutContainerInfo { 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 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) {} 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() : 0; } 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) { 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); } } } const llvm::APSInt &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) { 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; } 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; // However, if the range wraps around, it spans all possible values. Lower = Type.getMinValue(); Upper = Type.getMaxValue(); break; } break; } return true; } 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 newRanges; } 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) << ']'; } os << " }"; } bool operator==(const RangeSet &other) const { return ranges == other.ranges; } }; } // end anonymous namespace REGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintRange, CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, RangeSet)) namespace { class RangeConstraintManager : public SimpleConstraintManager{ RangeSet GetRange(ProgramStateRef state, SymbolRef sym); public: RangeConstraintManager(SubEngine *subengine, SValBuilder &SVB) : SimpleConstraintManager(subengine, SVB) {} ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymGT(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymGE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); ProgramStateRef assumeSymLE(ProgramStateRef state, SymbolRef sym, const llvm::APSInt& Int, const llvm::APSInt& Adjustment); const llvm::APSInt* getSymVal(ProgramStateRef St, SymbolRef sym) const; ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym); ProgramStateRef removeDeadBindings(ProgramStateRef St, SymbolReaper& SymReaper); void print(ProgramStateRef St, raw_ostream &Out, const char* nl, const char *sep); private: RangeSet::Factory F; }; } // end anonymous namespace ConstraintManager * ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) { return new RangeConstraintManager(Eng, StMgr.getSValBuilder()); } const llvm::APSInt* RangeConstraintManager::getSymVal(ProgramStateRef St, SymbolRef sym) const { const ConstraintRangeTy::data_type *T = St->get(sym); return T ? T->getConcreteValue() : NULL; } ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, SymbolRef Sym) { const RangeSet *Ranges = State->get(Sym); // If we don't have any information about this symbol, it's underconstrained. if (!Ranges) return ConditionTruthVal(); // If we have a concrete value, see if it's zero. if (const llvm::APSInt *Value = Ranges->getConcreteValue()) return *Value == 0; BasicValueFactory &BV = getBasicVals(); APSIntType IntType = BV.getAPSIntType(Sym->getType()); llvm::APSInt Zero = IntType.getZeroValue(); // Check if zero is in the set of possible values. if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty()) return false; // Zero is a possible value, but it is not the /only/ possible value. return ConditionTruthVal(); } /// Scan all symbols referenced by the constraints. If the symbol is not alive /// as marked in LSymbols, mark it as dead in DSymbols. ProgramStateRef RangeConstraintManager::removeDeadBindings(ProgramStateRef state, SymbolReaper& SymReaper) { ConstraintRangeTy CR = state->get(); ConstraintRangeTy::Factory& CRFactory = state->get_context(); for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) { SymbolRef sym = I.getKey(); if (SymReaper.maybeDead(sym)) CR = CRFactory.remove(CR, sym); } return state->set(CR); } RangeSet RangeConstraintManager::GetRange(ProgramStateRef state, SymbolRef sym) { if (ConstraintRangeTy::data_type* V = state->get(sym)) return *V; // 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)); // Special case: references are known to be non-zero. if (T->isReferenceType()) { APSIntType IntType = BV.getAPSIntType(T); Result = Result.Intersect(BV, F, ++IntType.getZeroValue(), --IntType.getZeroValue()); } return Result; } //===------------------------------------------------------------------------=== // assumeSymX methods: public interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ // The syntax for ranges below is mathematical, using [x, y] for closed ranges // and (x, y) for open ranges. These ranges are modular, corresponding with // a common treatment of C integer overflow. This means that these methods // do not have to worry about overflow; RangeSet::Intersect can handle such a // "wraparound" range. // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, // UINT_MAX, 0, 1, and 2. ProgramStateRef RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return St; llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment; llvm::APSInt Upper = Lower; --Lower; ++Upper; // [Int-Adjustment+1, Int-Adjustment-1] // Notice that the lower bound is greater than the upper bound. RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return NULL; // [Int-Adjustment, Int-Adjustment] llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return NULL; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return St; } // Special case for Int == Min. This is always false. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) return NULL; llvm::APSInt Lower = Min-Adjustment; llvm::APSInt Upper = ComparisonVal-Adjustment; --Upper; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return St; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return NULL; } // Special case for Int == Max. This is always false. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) return NULL; llvm::APSInt Lower = ComparisonVal-Adjustment; llvm::APSInt Upper = Max-Adjustment; ++Lower; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return St; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return NULL; } // Special case for Int == Min. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) return St; llvm::APSInt Max = AdjustmentType.getMaxValue(); llvm::APSInt Lower = ComparisonVal-Adjustment; llvm::APSInt Upper = Max-Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? NULL : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: return NULL; case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: return St; } // Special case for Int == Max. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) return St; llvm::APSInt Min = AdjustmentType.getMinValue(); llvm::APSInt Lower = Min-Adjustment; llvm::APSInt Upper = ComparisonVal-Adjustment; RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); return New.isEmpty() ? NULL : St->set(Sym, New); } //===------------------------------------------------------------------------=== // Pretty-printing. //===------------------------------------------------------------------------===/ void RangeConstraintManager::print(ProgramStateRef St, raw_ostream &Out, const char* nl, const char *sep) { ConstraintRangeTy Ranges = St->get(); if (Ranges.isEmpty()) { Out << nl << sep << "Ranges are empty." << nl; return; } Out << nl << sep << "Ranges of symbol values:"; for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){ Out << nl << ' ' << I.getKey() << " : "; I.getData().print(Out); } Out << nl; } @