Index: include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h @@ -29,6 +29,7 @@ class ConditionTruthVal { Optional Val; + public: /// Construct a ConditionTruthVal indicating the constraint is constrained /// to either true or false, depending on the boolean value provided. @@ -36,40 +37,32 @@ /// Construct a ConstraintVal indicating the constraint is underconstrained. ConditionTruthVal() {} - + /// Return true if the constraint is perfectly constrained to 'true'. - bool isConstrainedTrue() const { - return Val.hasValue() && Val.getValue(); - } + bool isConstrainedTrue() const { return Val.hasValue() && Val.getValue(); } /// Return true if the constraint is perfectly constrained to 'false'. - bool isConstrainedFalse() const { - return Val.hasValue() && !Val.getValue(); - } + bool isConstrainedFalse() const { return Val.hasValue() && !Val.getValue(); } /// Return true if the constrained is perfectly constrained. - bool isConstrained() const { - return Val.hasValue(); - } + bool isConstrained() const { return Val.hasValue(); } /// Return true if the constrained is underconstrained and we do not know /// if the constraint is true of value. - bool isUnderconstrained() const { - return !Val.hasValue(); - } + bool isUnderconstrained() const { return !Val.hasValue(); } }; - + class ConstraintManager { public: ConstraintManager() : NotifyAssumeClients(true) {} - + virtual ~ConstraintManager(); - virtual ProgramStateRef assume(ProgramStateRef state, - DefinedSVal Cond, - bool Assumption) = 0; typedef std::pair ProgramStatePair; + virtual ProgramStateRef assume(ProgramStateRef state, DefinedSVal Cond, + bool Assumption) = 0; + /// Returns a pair of states (StTrue, StFalse) where the given condition is /// assumed to be true or false, respectively. ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond) { @@ -85,7 +78,7 @@ // does not. Is there a good equivalent there? assert(assume(State, Cond, false) && "System is over constrained."); #endif - return ProgramStatePair((ProgramStateRef)nullptr, State); + return ProgramStatePair((ProgramStateRef) nullptr, State); } ProgramStateRef StFalse = assume(State, Cond, false); @@ -93,36 +86,37 @@ // We are careful to return the original state, /not/ StTrue, // because we want to avoid having callers generate a new node // in the ExplodedGraph. - return ProgramStatePair(State, (ProgramStateRef)nullptr); + return ProgramStatePair(State, (ProgramStateRef) nullptr); } return ProgramStatePair(StTrue, StFalse); } - virtual ProgramStateRef assumeWithinInclusiveRange(ProgramStateRef State, - NonLoc Value, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool InBound) = 0; + virtual ProgramStateRef assumeInclusiveRange(ProgramStateRef State, + NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InBound) = 0; - virtual ProgramStatePair assumeWithinInclusiveRangeDual( - ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, - const llvm::APSInt &To) { - ProgramStateRef StInRange = assumeWithinInclusiveRange(State, Value, From, - To, true); + virtual ProgramStatePair assumeInclusiveRangeDual(ProgramStateRef State, + NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To) { + ProgramStateRef StInRange = + assumeInclusiveRange(State, Value, From, To, true); // If StTrue is infeasible, asserting the falseness of Cond is unnecessary // because the existing constraints already establish this. if (!StInRange) - return ProgramStatePair((ProgramStateRef)nullptr, State); + return ProgramStatePair((ProgramStateRef) nullptr, State); - ProgramStateRef StOutOfRange = assumeWithinInclusiveRange(State, Value, - From, To, false); + ProgramStateRef StOutOfRange = + assumeInclusiveRange(State, Value, From, To, false); if (!StOutOfRange) { // We are careful to return the original state, /not/ StTrue, // because we want to avoid having callers generate a new node // in the ExplodedGraph. - return ProgramStatePair(State, (ProgramStateRef)nullptr); + return ProgramStatePair(State, (ProgramStateRef) nullptr); } return ProgramStatePair(StInRange, StOutOfRange); @@ -133,21 +127,21 @@ /// /// Note that a ConstraintManager is not obligated to return a concretized /// value for a symbol, even if it is perfectly constrained. - virtual const llvm::APSInt* getSymVal(ProgramStateRef state, - SymbolRef sym) const { + virtual const llvm::APSInt *getSymVal(ProgramStateRef State, + SymbolRef Sym) const { return nullptr; } + /// Scan all symbols referenced by the constraints. If the symbol is not + /// alive, remove it. virtual ProgramStateRef removeDeadBindings(ProgramStateRef state, - SymbolReaper& SymReaper) = 0; + SymbolReaper &SymReaper) = 0; - virtual void print(ProgramStateRef state, - raw_ostream &Out, - const char* nl, + virtual void print(ProgramStateRef state, raw_ostream &Out, const char *nl, const char *sep) = 0; virtual void EndPath(ProgramStateRef state) {} - + /// Convenience method to query the state to see if a symbol is null or /// not null, or if neither assumption can be made. ConditionTruthVal isNull(ProgramStateRef State, SymbolRef Sym) { @@ -173,7 +167,7 @@ virtual bool canReasonAbout(SVal X) const = 0; /// Returns whether or not a symbol is known to be null ("true"), known to be - /// non-null ("false"), or may be either ("underconstrained"). + /// non-null ("false"), or may be either ("underconstrained"). virtual ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym); }; Index: include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -197,10 +197,10 @@ /// /// This returns a new state with the added constraint on \p cond. /// If no new state is feasible, NULL is returned. - ProgramStateRef assumeWithinInclusiveRange(DefinedOrUnknownSVal Val, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool assumption) const; + ProgramStateRef assumeInclusiveRange(DefinedOrUnknownSVal Val, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool assumption) const; /// Assumes given range both "true" and "false" for \p Val, and returns both /// corresponding states (respectively). @@ -208,8 +208,8 @@ /// This is more efficient than calling assume() twice. Note that one (but not /// both) of the returned states may be NULL. std::pair - assumeWithinInclusiveRange(DefinedOrUnknownSVal Val, const llvm::APSInt &From, - const llvm::APSInt &To) const; + assumeInclusiveRange(DefinedOrUnknownSVal Val, const llvm::APSInt &From, + const llvm::APSInt &To) const; /// \brief Check if the given SVal is constrained to zero or is a zero @@ -658,30 +658,30 @@ } inline ProgramStateRef -ProgramState::assumeWithinInclusiveRange(DefinedOrUnknownSVal Val, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool Assumption) const { +ProgramState::assumeInclusiveRange(DefinedOrUnknownSVal Val, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool Assumption) const { if (Val.isUnknown()) return this; assert(Val.getAs() && "Only NonLocs are supported!"); - return getStateManager().ConstraintMgr->assumeWithinInclusiveRange( + return getStateManager().ConstraintMgr->assumeInclusiveRange( this, Val.castAs(), From, To, Assumption); } inline std::pair -ProgramState::assumeWithinInclusiveRange(DefinedOrUnknownSVal Val, - const llvm::APSInt &From, - const llvm::APSInt &To) const { +ProgramState::assumeInclusiveRange(DefinedOrUnknownSVal Val, + const llvm::APSInt &From, + const llvm::APSInt &To) const { if (Val.isUnknown()) return std::make_pair(this, this); assert(Val.getAs() && "Only NonLocs are supported!"); return getStateManager().ConstraintMgr - ->assumeWithinInclusiveRangeDual(this, Val.castAs(), From, To); + ->assumeInclusiveRangeDual(this, Val.castAs(), From, To); } inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V) const { Index: include/clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h =================================================================== --- /dev/null +++ include/clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h @@ -0,0 +1,100 @@ +//== SimpleConstraintManager.h ----------------------------------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Simplified constraint manager backend. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SIMPLECONSTRAINTMANAGER_H +#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SIMPLECONSTRAINTMANAGER_H + +#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" + +namespace clang { + +namespace ento { + +class SimpleConstraintManager : public ConstraintManager { + SubEngine *SU; + SValBuilder &SVB; + +public: + SimpleConstraintManager(SubEngine *subengine, SValBuilder &SB) + : SU(subengine), SVB(SB) {} + + ~SimpleConstraintManager() override; + + //===------------------------------------------------------------------===// + // Implementation for interface from ConstraintManager. + //===------------------------------------------------------------------===// + + /// Ensures that the DefinedSVal conditional is expressed as a NonLoc by + /// creating boolean casts to handle Loc's. + ProgramStateRef assume(ProgramStateRef State, DefinedSVal Cond, + bool Assumption) override; + + ProgramStateRef assumeInclusiveRange(ProgramStateRef State, NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InRange) override; + +protected: + /// Given a symbolic expression that cannot be reasoned about, assume that + /// it is zero/nonzero and add it directly to the solver state. + virtual ProgramStateRef assumeSymUnsupported(ProgramStateRef State, + SymbolRef Sym, bool Assumption); + + //===------------------------------------------------------------------===// + // Interface that subclasses must implement. + //===------------------------------------------------------------------===// + + /// Given a symbolic expression that can be reasoned about, assume that it is + /// true/false and generate the new program state. + virtual ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, + bool Assumption) = 0; + + /// Assume a constraint between a symbolic expression and a concrete integer. + /// Used to directly add unsupported constraints to the solver state. + virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, + BinaryOperator::Opcode op, + const llvm::APSInt &Int) = 0; + + /// Given a symbolic expression within the range [From, To], assume that it is + /// true/false and generate the new program state. + /// This function is used to handle case ranges produced by a language + /// extension + /// for switch case statements. + virtual ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, + SymbolRef Sym, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InRange) = 0; + + //===------------------------------------------------------------------===// + // Internal implementation. + //===------------------------------------------------------------------===// + + BasicValueFactory &getBasicVals() const { return SVB.getBasicValueFactory(); } + SymbolManager &getSymbolManager() const { return SVB.getSymbolManager(); } + +private: + ProgramStateRef assume(ProgramStateRef State, NonLoc Cond, + bool Assumption); + + ProgramStateRef assumeAux(ProgramStateRef State, NonLoc Cond, + bool Assumption); + +}; + +} // end GR namespace + +} // end clang namespace + +#endif Index: lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp +++ lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp @@ -243,7 +243,7 @@ const llvm::APSInt &Min = BVF.getValue(R[I].first, T); const llvm::APSInt &Max = BVF.getValue(R[I].second, T); assert(Min <= Max); - State = CM.assumeWithinInclusiveRange(State, *N, Min, Max, false); + State = CM.assumeInclusiveRange(State, *N, Min, Max, false); if (!State) break; } @@ -277,7 +277,7 @@ const llvm::APSInt &Left = BVF.getValue(R[0].first - 1ULL, T); if (Left != PlusInf) { assert(MinusInf <= Left); - State = CM.assumeWithinInclusiveRange(State, *N, MinusInf, Left, false); + State = CM.assumeInclusiveRange(State, *N, MinusInf, Left, false); if (!State) return nullptr; } @@ -285,7 +285,7 @@ const llvm::APSInt &Right = BVF.getValue(R[E - 1].second + 1ULL, T); if (Right != MinusInf) { assert(Right <= PlusInf); - State = CM.assumeWithinInclusiveRange(State, *N, Right, PlusInf, false); + State = CM.assumeInclusiveRange(State, *N, Right, PlusInf, false); if (!State) return nullptr; } @@ -294,7 +294,7 @@ const llvm::APSInt &Min = BVF.getValue(R[I - 1].second + 1ULL, T); const llvm::APSInt &Max = BVF.getValue(R[I].first - 1ULL, T); assert(Min <= Max); - State = CM.assumeWithinInclusiveRange(State, *N, Min, Max, false); + State = CM.assumeInclusiveRange(State, *N, Min, Max, false); if (!State) return nullptr; } Index: lib/StaticAnalyzer/Core/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Core/CMakeLists.txt +++ lib/StaticAnalyzer/Core/CMakeLists.txt @@ -34,6 +34,7 @@ PlistDiagnostics.cpp ProgramState.cpp RangeConstraintManager.cpp + RangedConstraintManager.cpp RegionStore.cpp SValBuilder.cpp SVals.cpp Index: lib/StaticAnalyzer/Core/ConstraintManager.cpp =================================================================== --- lib/StaticAnalyzer/Core/ConstraintManager.cpp +++ lib/StaticAnalyzer/Core/ConstraintManager.cpp @@ -20,8 +20,8 @@ static DefinedSVal getLocFromSymbol(const ProgramStateRef &State, SymbolRef Sym) { - const MemRegion *R = State->getStateManager().getRegionManager() - .getSymbolicRegion(Sym); + const MemRegion *R = + State->getStateManager().getRegionManager().getSymbolicRegion(Sym); return loc::MemRegionVal(R); } Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1836,7 +1836,7 @@ ProgramStateRef StateCase; if (Optional NL = CondV.getAs()) std::tie(StateCase, DefaultSt) = - DefaultSt->assumeWithinInclusiveRange(*NL, V1, V2); + DefaultSt->assumeInclusiveRange(*NL, V1, V2); else // UnknownVal StateCase = DefaultSt; Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp =================================================================== --- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -12,7 +12,7 @@ // //===----------------------------------------------------------------------===// -#include "SimpleConstraintManager.h" +#include "RangedConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" @@ -27,22 +27,17 @@ /// guarantee that from <= to. Note that Range is immutable, so as not /// to subvert RangeSet's immutability. namespace { -class Range : public std::pair { +class Range : public std::pair { public: Range(const llvm::APSInt &from, const llvm::APSInt &to) - : std::pair(&from, &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 &From() const { return *first; } + const llvm::APSInt &To() const { return *second; } const llvm::APSInt *getConcreteValue() const { return &From() == &To() ? &From() : nullptr; } @@ -53,7 +48,6 @@ } }; - class RangeTrait : public llvm::ImutContainerInfo { public: // When comparing if one Range is less than another, we should compare @@ -61,8 +55,8 @@ // 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); + return *lhs.first < *rhs.first || + (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second); } }; @@ -96,7 +90,7 @@ /// 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))) {} + : ranges(F.add(F.getEmptySet(), Range(from, to))) {} /// Profile - Generates a hash profile of this RangeSet for use /// by FoldingSet. @@ -105,16 +99,14 @@ /// 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 { + 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, + 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. @@ -134,8 +126,8 @@ if (i->Includes(Lower)) { if (i->Includes(Upper)) { - newRanges = F.add(newRanges, Range(BV.getValue(Lower), - BV.getValue(Upper))); + newRanges = + F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); break; } else newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To())); @@ -243,8 +235,8 @@ // 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 { + RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, + llvm::APSInt Upper) const { if (!pin(Lower, Upper)) return F.getEmptySet(); @@ -290,56 +282,69 @@ RangeSet)) namespace { -class RangeConstraintManager : public SimpleConstraintManager{ - RangeSet GetRange(ProgramStateRef state, SymbolRef sym); +class RangeConstraintManager : public RangedConstraintManager { public: - RangeConstraintManager(SubEngine *subengine, SValBuilder &SVB) - : SimpleConstraintManager(subengine, SVB) {} + RangeConstraintManager(SubEngine *SE, SValBuilder &SVB) + : RangedConstraintManager(SE, SVB) {} - ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& Int, - const llvm::APSInt& Adjustment) override; + //===------------------------------------------------------------------===// + // Implementation for interface from ConstraintManager. + //===------------------------------------------------------------------===// - ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& Int, - const llvm::APSInt& Adjustment) override; + bool canReasonAbout(SVal X) const override; - ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& Int, - const llvm::APSInt& Adjustment) override; + ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; - ProgramStateRef assumeSymGT(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& Int, - const llvm::APSInt& Adjustment) override; + const llvm::APSInt *getSymVal(ProgramStateRef State, + SymbolRef Sym) const override; - ProgramStateRef assumeSymGE(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& Int, - const llvm::APSInt& Adjustment) override; + ProgramStateRef removeDeadBindings(ProgramStateRef State, + SymbolReaper &SymReaper) override; - ProgramStateRef assumeSymLE(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& Int, - const llvm::APSInt& Adjustment) override; + void print(ProgramStateRef State, raw_ostream &Out, const char *nl, + const char *sep) override; - ProgramStateRef assumeSymbolWithinInclusiveRange( - ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, - const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; + //===------------------------------------------------------------------===// + // Implementation for interface from RangedConstraintManager. + //===------------------------------------------------------------------===// - ProgramStateRef assumeSymbolOutOfInclusiveRange( - ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, - const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; + ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; - const llvm::APSInt* getSymVal(ProgramStateRef St, - SymbolRef sym) const override; - ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; + ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; - ProgramStateRef removeDeadBindings(ProgramStateRef St, - SymbolReaper& SymReaper) override; + ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; - void print(ProgramStateRef St, raw_ostream &Out, - const char* nl, const char *sep) 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; + + ProgramStateRef assumeSymWithinInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymOutsideInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; private: RangeSet::Factory F; + + RangeSet getRange(ProgramStateRef state, SymbolRef sym); + RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); @@ -363,10 +368,46 @@ return llvm::make_unique(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; +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; } ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, @@ -393,27 +434,35 @@ return ConditionTruthVal(); } +const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, + SymbolRef Sym) const { + const ConstraintRangeTy::data_type *T = St->get(Sym); + return T ? T->getConcreteValue() : nullptr; +} + /// 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) { - + SymbolReaper &SymReaper) { + bool Changed = false; ConstraintRangeTy CR = state->get(); - ConstraintRangeTy::Factory& CRFactory = state->get_context(); + 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)) + if (SymReaper.maybeDead(sym)) { + Changed = true; CR = CRFactory.remove(CR, sym); + } } - return state->set(CR); + return Changed ? state->set(CR) : state; } -RangeSet -RangeConstraintManager::GetRange(ProgramStateRef state, SymbolRef sym) { - if (ConstraintRangeTy::data_type* V = state->get(sym)) +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 @@ -427,14 +476,14 @@ if (T->isReferenceType()) { APSIntType IntType = BV.getAPSIntType(T); Result = Result.Intersect(BV, F, ++IntType.getZeroValue(), - --IntType.getZeroValue()); + --IntType.getZeroValue()); } return Result; } //===------------------------------------------------------------------------=== -// assumeSymX methods: public interface for RangeConstraintManager. +// assumeSymX methods: protected interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ // The syntax for ranges below is mathematical, using [x, y] for closed ranges @@ -461,7 +510,7 @@ // [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); + RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); return New.isEmpty() ? nullptr : St->set(Sym, New); } @@ -476,7 +525,7 @@ // [Int-Adjustment, Int-Adjustment] llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; - RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); + RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); return New.isEmpty() ? nullptr : St->set(Sym, New); } @@ -492,7 +541,7 @@ case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: - return GetRange(St, Sym); + return getRange(St, Sym); } // Special case for Int == Min. This is always false. @@ -505,7 +554,7 @@ llvm::APSInt Upper = ComparisonVal - Adjustment; --Upper; - return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); + return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } ProgramStateRef @@ -516,15 +565,15 @@ return New.isEmpty() ? nullptr : St->set(Sym, New); } -RangeSet -RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment) { +RangeSet RangeConstraintManager::getSymGTRange(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 GetRange(St, Sym); + return getRange(St, Sym); case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: @@ -541,7 +590,7 @@ llvm::APSInt Upper = Max - Adjustment; ++Lower; - return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); + return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } ProgramStateRef @@ -552,15 +601,15 @@ return New.isEmpty() ? nullptr : St->set(Sym, New); } -RangeSet -RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment) { +RangeSet RangeConstraintManager::getSymGERange(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 GetRange(St, Sym); + return getRange(St, Sym); case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: @@ -571,13 +620,13 @@ llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) - return GetRange(St, Sym); + return getRange(St, Sym); llvm::APSInt Max = AdjustmentType.getMaxValue(); llvm::APSInt Lower = ComparisonVal - Adjustment; llvm::APSInt Upper = Max - Adjustment; - return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); + return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } ProgramStateRef @@ -588,10 +637,9 @@ return New.isEmpty() ? nullptr : St->set(Sym, New); } -RangeSet -RangeConstraintManager::getSymLERange(const RangeSet &RS, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment) { +RangeSet RangeConstraintManager::getSymLERange(const RangeSet &RS, + 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)) { @@ -616,10 +664,10 @@ return RS.Intersect(getBasicVals(), F, Lower, Upper); } -RangeSet -RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment) { +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)) { @@ -628,20 +676,20 @@ case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: - return GetRange(St, Sym); + 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); + return getRange(St, Sym); llvm::APSInt Min = AdjustmentType.getMinValue(); llvm::APSInt Lower = Min - Adjustment; llvm::APSInt Upper = ComparisonVal - Adjustment; - return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); + return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } ProgramStateRef @@ -652,8 +700,7 @@ return New.isEmpty() ? nullptr : St->set(Sym, New); } -ProgramStateRef -RangeConstraintManager::assumeSymbolWithinInclusiveRange( +ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange( ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) { RangeSet New = getSymGERange(State, Sym, From, Adjustment); @@ -663,8 +710,7 @@ return New.isEmpty() ? nullptr : State->set(Sym, New); } -ProgramStateRef -RangeConstraintManager::assumeSymbolOutOfInclusiveRange( +ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange( ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment) { RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment); @@ -678,7 +724,7 @@ //===------------------------------------------------------------------------===/ void RangeConstraintManager::print(ProgramStateRef St, raw_ostream &Out, - const char* nl, const char *sep) { + const char *nl, const char *sep) { ConstraintRangeTy Ranges = St->get(); @@ -688,7 +734,8 @@ } Out << nl << sep << "Ranges of symbol values:"; - for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){ + for (ConstraintRangeTy::iterator I = Ranges.begin(), E = Ranges.end(); I != E; + ++I) { Out << nl << ' ' << I.getKey() << " : "; I.getData().print(Out); } Index: lib/StaticAnalyzer/Core/RangedConstraintManager.h =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Core/RangedConstraintManager.h @@ -0,0 +1,98 @@ +//== RangedConstraintManager.h ----------------------------------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Ranged constraint manager, built on SimpleConstraintManager. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H +#define LLVM_CLANG_LIB_STATICANALYZER_CORE_RANGEDCONSTRAINTMANAGER_H + +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" + +namespace clang { + +namespace ento { + +class RangedConstraintManager : public SimpleConstraintManager { +public: + RangedConstraintManager(SubEngine *SE, SValBuilder &SB) + : SimpleConstraintManager(SE, SB) {} + + ~RangedConstraintManager() override; + + //===------------------------------------------------------------------===// + // Implementation for interface from SimpleConstraintManager. + //===------------------------------------------------------------------===// + + ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, + bool Assumption) override; + + ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, + BinaryOperator::Opcode op, + const llvm::APSInt &Int) override; + + ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InRange) override; + +protected: + //===------------------------------------------------------------------===// + // Interface that subclasses must implement. + //===------------------------------------------------------------------===// + + // Each of these is of the form "$Sym+Adj <> V", where "<>" is the comparison + // operation for the method being invoked. + + virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) = 0; + + virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) = 0; + + virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) = 0; + + virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) = 0; + + virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) = 0; + + virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) = 0; + + virtual ProgramStateRef assumeSymWithinInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; + + virtual ProgramStateRef assumeSymOutsideInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; + + //===------------------------------------------------------------------===// + // Internal implementation. + //===------------------------------------------------------------------===// +private: + static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); +}; + +} // end GR namespace + +} // end clang namespace + +#endif Index: lib/StaticAnalyzer/Core/RangedConstraintManager.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Core/RangedConstraintManager.cpp @@ -0,0 +1,176 @@ +//== RangedConstraintManager.cpp --------------------------------*- 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 RangedConstraintManager, a class that provides a +// range-based constraint manager interface. +// +//===----------------------------------------------------------------------===// + +#include "RangedConstraintManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" + +namespace clang { + +namespace ento { + +RangedConstraintManager::~RangedConstraintManager() {} + +ProgramStateRef RangedConstraintManager::assumeSym(ProgramStateRef State, + SymbolRef Sym, + bool Assumption) { + // Handle SymbolData. + if (isa(Sym)) { + return assumeSymUnsupported(State, Sym, Assumption); + + // Handle symbolic expression. + } else if (const SymIntExpr *SIE = dyn_cast(Sym)) { + // We can only simplify expressions whose RHS is an integer. + + BinaryOperator::Opcode op = SIE->getOpcode(); + if (BinaryOperator::isComparisonOp(op)) { + if (!Assumption) + op = BinaryOperator::negateComparisonOp(op); + + return assumeSymRel(State, SIE->getLHS(), op, SIE->getRHS()); + } + + } else if (const SymSymExpr *SSE = dyn_cast(Sym)) { + // Translate "a != b" to "(b - a) != 0". + // We invert the order of the operands as a heuristic for how loop + // conditions are usually written ("begin != end") as compared to length + // calculations ("end - begin"). The more correct thing to do would be to + // canonicalize "a - b" and "b - a", which would allow us to treat + // "a != b" and "b != a" the same. + SymbolManager &SymMgr = getSymbolManager(); + BinaryOperator::Opcode Op = SSE->getOpcode(); + assert(BinaryOperator::isComparisonOp(Op)); + + // For now, we only support comparing pointers. + assert(Loc::isLocType(SSE->getLHS()->getType())); + assert(Loc::isLocType(SSE->getRHS()->getType())); + QualType DiffTy = SymMgr.getContext().getPointerDiffType(); + SymbolRef Subtraction = + SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), DiffTy); + + const llvm::APSInt &Zero = getBasicVals().getValue(0, DiffTy); + Op = BinaryOperator::reverseComparisonOp(Op); + if (!Assumption) + Op = BinaryOperator::negateComparisonOp(Op); + return assumeSymRel(State, Subtraction, Op, Zero); + } + + // If we get here, there's nothing else we can do but treat the symbol as + // opaque. + return assumeSymUnsupported(State, Sym, Assumption); +} + +ProgramStateRef RangedConstraintManager::assumeSymRel(ProgramStateRef State, + SymbolRef LHS, + BinaryOperator::Opcode op, + const llvm::APSInt &Int) { + assert(BinaryOperator::isComparisonOp(op) && + "Non-comparison ops should be rewritten as comparisons to zero."); + + // Get the type used for calculating wraparound. + BasicValueFactory &BVF = getBasicVals(); + APSIntType WraparoundType = BVF.getAPSIntType(LHS->getType()); + + // We only handle simple comparisons of the form "$sym == constant" + // or "($sym+constant1) == constant2". + // The adjustment is "constant1" in the above expression. It's used to + // "slide" the solution range around for modular arithmetic. For example, + // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which + // in modular arithmetic is [0, 1] U [UINT_MAX-1, UINT_MAX]. It's up to + // the subclasses of SimpleConstraintManager to handle the adjustment. + SymbolRef Sym = LHS; + llvm::APSInt Adjustment = WraparoundType.getZeroValue(); + computeAdjustment(Sym, Adjustment); + + // Convert the right-hand side integer as necessary. + APSIntType ComparisonType = std::max(WraparoundType, APSIntType(Int)); + llvm::APSInt ConvertedInt = ComparisonType.convert(Int); + + // Prefer unsigned comparisons. + if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() && + ComparisonType.isUnsigned() && !WraparoundType.isUnsigned()) + Adjustment.setIsSigned(false); + + switch (op) { + default: + llvm_unreachable("invalid operation not caught by assertion above"); + + case BO_EQ: + return assumeSymEQ(State, Sym, ConvertedInt, Adjustment); + + case BO_NE: + return assumeSymNE(State, Sym, ConvertedInt, Adjustment); + + case BO_GT: + return assumeSymGT(State, Sym, ConvertedInt, Adjustment); + + case BO_GE: + return assumeSymGE(State, Sym, ConvertedInt, Adjustment); + + case BO_LT: + return assumeSymLT(State, Sym, ConvertedInt, Adjustment); + + case BO_LE: + return assumeSymLE(State, Sym, ConvertedInt, Adjustment); + } // end switch +} + +ProgramStateRef RangedConstraintManager::assumeSymInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, bool InRange) { + // Get the type used for calculating wraparound. + BasicValueFactory &BVF = getBasicVals(); + APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType()); + + llvm::APSInt Adjustment = WraparoundType.getZeroValue(); + SymbolRef AdjustedSym = Sym; + computeAdjustment(AdjustedSym, Adjustment); + + // Convert the right-hand side integer as necessary. + APSIntType ComparisonType = std::max(WraparoundType, APSIntType(From)); + llvm::APSInt ConvertedFrom = ComparisonType.convert(From); + llvm::APSInt ConvertedTo = ComparisonType.convert(To); + + // Prefer unsigned comparisons. + if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() && + ComparisonType.isUnsigned() && !WraparoundType.isUnsigned()) + Adjustment.setIsSigned(false); + + if (InRange) + return assumeSymWithinInclusiveRange(State, AdjustedSym, ConvertedFrom, + ConvertedTo, Adjustment); + return assumeSymOutsideInclusiveRange(State, AdjustedSym, ConvertedFrom, + ConvertedTo, Adjustment); +} + +void RangedConstraintManager::computeAdjustment(SymbolRef &Sym, + llvm::APSInt &Adjustment) { + // Is it a "($sym+constant1)" expression? + if (const SymIntExpr *SE = dyn_cast(Sym)) { + BinaryOperator::Opcode Op = SE->getOpcode(); + if (Op == BO_Add || Op == BO_Sub) { + Sym = SE->getLHS(); + Adjustment = APSIntType(Adjustment).convert(SE->getRHS()); + + // Don't forget to negate the adjustment if it's being subtracted. + // This should happen /after/ promotion, in case the value being + // subtracted is, say, CHAR_MIN, and the promoted type is 'int'. + if (Op == BO_Sub) + Adjustment = -Adjustment; + } + } +} + +} // end of namespace ento + +} // end of namespace clang Index: lib/StaticAnalyzer/Core/SimpleConstraintManager.h =================================================================== --- lib/StaticAnalyzer/Core/SimpleConstraintManager.h +++ /dev/null @@ -1,121 +0,0 @@ -//== SimpleConstraintManager.h ----------------------------------*- C++ -*--==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Code shared between BasicConstraintManager and RangeConstraintManager. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_LIB_STATICANALYZER_CORE_SIMPLECONSTRAINTMANAGER_H -#define LLVM_CLANG_LIB_STATICANALYZER_CORE_SIMPLECONSTRAINTMANAGER_H - -#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" - -namespace clang { - -namespace ento { - -class SimpleConstraintManager : public ConstraintManager { - SubEngine *SU; - SValBuilder &SVB; -public: - SimpleConstraintManager(SubEngine *subengine, SValBuilder &SB) - : SU(subengine), SVB(SB) {} - ~SimpleConstraintManager() override; - - //===------------------------------------------------------------------===// - // Common implementation for the interface provided by ConstraintManager. - //===------------------------------------------------------------------===// - - ProgramStateRef assume(ProgramStateRef state, DefinedSVal Cond, - bool Assumption) override; - - ProgramStateRef assume(ProgramStateRef state, NonLoc Cond, bool Assumption); - - ProgramStateRef assumeWithinInclusiveRange(ProgramStateRef State, - NonLoc Value, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool InRange) override; - - ProgramStateRef assumeSymRel(ProgramStateRef state, - const SymExpr *LHS, - BinaryOperator::Opcode op, - const llvm::APSInt& Int); - - ProgramStateRef assumeSymWithinInclusiveRange(ProgramStateRef State, - SymbolRef Sym, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool InRange); - - -protected: - - //===------------------------------------------------------------------===// - // Interface that subclasses must implement. - //===------------------------------------------------------------------===// - - // Each of these is of the form "$sym+Adj <> V", where "<>" is the comparison - // operation for the method being invoked. - virtual ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment) = 0; - - virtual ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment) = 0; - - virtual ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment) = 0; - - virtual ProgramStateRef assumeSymGT(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment) = 0; - - virtual ProgramStateRef assumeSymLE(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment) = 0; - - virtual ProgramStateRef assumeSymGE(ProgramStateRef state, SymbolRef sym, - const llvm::APSInt& V, - const llvm::APSInt& Adjustment) = 0; - - - virtual ProgramStateRef assumeSymbolWithinInclusiveRange( - ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, - const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; - - virtual ProgramStateRef assumeSymbolOutOfInclusiveRange( - ProgramStateRef state, SymbolRef Sym, const llvm::APSInt &From, - const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; - //===------------------------------------------------------------------===// - // Internal implementation. - //===------------------------------------------------------------------===// - - BasicValueFactory &getBasicVals() const { return SVB.getBasicValueFactory(); } - SymbolManager &getSymbolManager() const { return SVB.getSymbolManager(); } - - bool canReasonAbout(SVal X) const override; - - ProgramStateRef assumeAux(ProgramStateRef state, - NonLoc Cond, - bool Assumption); - - ProgramStateRef assumeAuxForSymbol(ProgramStateRef State, - SymbolRef Sym, - bool Assumption); -}; - -} // end GR namespace - -} // end clang namespace - -#endif Index: lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp =================================================================== --- lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp +++ lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp @@ -7,12 +7,12 @@ // //===----------------------------------------------------------------------===// // -// This file defines SimpleConstraintManager, a class that holds code shared -// between BasicConstraintManager and RangeConstraintManager. +// This file defines SimpleConstraintManager, a class that provides a +// simplified constraint manager interface, compared to ConstraintManager. // //===----------------------------------------------------------------------===// -#include "SimpleConstraintManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" @@ -23,54 +23,12 @@ SimpleConstraintManager::~SimpleConstraintManager() {} -bool SimpleConstraintManager::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; -} - -ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, - DefinedSVal Cond, - bool Assumption) { +ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef State, + DefinedSVal Cond, + bool Assumption) { // If we have a Loc value, cast it to a bool NonLoc first. if (Optional LV = Cond.getAs()) { - SValBuilder &SVB = state->getStateManager().getSValBuilder(); + SValBuilder &SVB = State->getStateManager().getSValBuilder(); QualType T; const MemRegion *MR = LV->getAsRegion(); if (const TypedRegion *TR = dyn_cast_or_null(MR)) @@ -81,46 +39,28 @@ Cond = SVB.evalCast(*LV, SVB.getContext().BoolTy, T).castAs(); } - return assume(state, Cond.castAs(), Assumption); + return assume(State, Cond.castAs(), Assumption); } -ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, - NonLoc cond, - bool assumption) { - state = assumeAux(state, cond, assumption); +ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef State, + NonLoc Cond, bool Assumption) { + State = assumeAux(State, Cond, Assumption); if (NotifyAssumeClients && SU) - return SU->processAssume(state, cond, assumption); - return state; + return SU->processAssume(State, Cond, Assumption); + return State; } - -ProgramStateRef -SimpleConstraintManager::assumeAuxForSymbol(ProgramStateRef State, - SymbolRef Sym, bool Assumption) { - BasicValueFactory &BVF = getBasicVals(); - QualType T = Sym->getType(); - - // None of the constraint solvers currently support non-integer types. - if (!T->isIntegralOrEnumerationType()) - return State; - - const llvm::APSInt &zero = BVF.getValue(0, T); - if (Assumption) - return assumeSymNE(State, Sym, zero, zero); - else - return assumeSymEQ(State, Sym, zero, zero); -} - -ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef state, - NonLoc Cond, - bool Assumption) { +ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef State, + NonLoc Cond, + bool Assumption) { // We cannot reason about SymSymExprs, and can only reason about some // SymIntExprs. if (!canReasonAbout(Cond)) { // Just add the constraint to the expression without trying to simplify. - SymbolRef sym = Cond.getAsSymExpr(); - return assumeAuxForSymbol(state, sym, Assumption); + SymbolRef Sym = Cond.getAsSymExpr(); + assert(Sym); + return assumeSymUnsupported(State, Sym, Assumption); } switch (Cond.getSubKind()) { @@ -129,68 +69,40 @@ case nonloc::SymbolValKind: { nonloc::SymbolVal SV = Cond.castAs(); - SymbolRef sym = SV.getSymbol(); - assert(sym); - - // Handle SymbolData. - if (!SV.isExpression()) { - return assumeAuxForSymbol(state, sym, Assumption); - - // Handle symbolic expression. - } else if (const SymIntExpr *SE = dyn_cast(sym)) { - // We can only simplify expressions whose RHS is an integer. - - BinaryOperator::Opcode op = SE->getOpcode(); - if (BinaryOperator::isComparisonOp(op)) { - if (!Assumption) - op = BinaryOperator::negateComparisonOp(op); - - return assumeSymRel(state, SE->getLHS(), op, SE->getRHS()); - } - - } else if (const SymSymExpr *SSE = dyn_cast(sym)) { - // Translate "a != b" to "(b - a) != 0". - // We invert the order of the operands as a heuristic for how loop - // conditions are usually written ("begin != end") as compared to length - // calculations ("end - begin"). The more correct thing to do would be to - // canonicalize "a - b" and "b - a", which would allow us to treat - // "a != b" and "b != a" the same. - SymbolManager &SymMgr = getSymbolManager(); - BinaryOperator::Opcode Op = SSE->getOpcode(); - assert(BinaryOperator::isComparisonOp(Op)); - - // For now, we only support comparing pointers. - assert(Loc::isLocType(SSE->getLHS()->getType())); - assert(Loc::isLocType(SSE->getRHS()->getType())); - QualType DiffTy = SymMgr.getContext().getPointerDiffType(); - SymbolRef Subtraction = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, - SSE->getLHS(), DiffTy); - - const llvm::APSInt &Zero = getBasicVals().getValue(0, DiffTy); - Op = BinaryOperator::reverseComparisonOp(Op); - if (!Assumption) - Op = BinaryOperator::negateComparisonOp(Op); - return assumeSymRel(state, Subtraction, Op, Zero); - } + SymbolRef Sym = SV.getSymbol(); + assert(Sym); - // If we get here, there's nothing else we can do but treat the symbol as - // opaque. - return assumeAuxForSymbol(state, sym, Assumption); + return assumeSym(State, Sym, Assumption); } case nonloc::ConcreteIntKind: { bool b = Cond.castAs().getValue() != 0; bool isFeasible = b ? Assumption : !Assumption; - return isFeasible ? state : nullptr; + return isFeasible ? State : nullptr; } case nonloc::LocAsIntegerKind: - return assume(state, Cond.castAs().getLoc(), + return assume(State, Cond.castAs().getLoc(), Assumption); } // end switch } -ProgramStateRef SimpleConstraintManager::assumeWithinInclusiveRange( +ProgramStateRef +SimpleConstraintManager::assumeSymUnsupported(ProgramStateRef State, + SymbolRef Sym, bool Assumption) { + BasicValueFactory &BVF = getBasicVals(); + QualType T = Sym->getType(); + + // None of the constraint solvers currently support non-integer types. + if (!T->isIntegralOrEnumerationType()) + return State; + + // Reverse the operation. + const llvm::APSInt &Zero = BVF.getValue(0, T); + return assumeSymRel(State, Sym, Assumption ? BO_NE : BO_EQ, Zero); +} + +ProgramStateRef SimpleConstraintManager::assumeInclusiveRange( ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, const llvm::APSInt &To, bool InRange) { @@ -202,18 +114,18 @@ // Just add the constraint to the expression without trying to simplify. SymbolRef Sym = Value.getAsSymExpr(); assert(Sym); - return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange); + return assumeSymInclusiveRange(State, Sym, From, To, InRange); } switch (Value.getSubKind()) { default: - llvm_unreachable("'assumeWithinInclusiveRange' is not implemented" + llvm_unreachable("'assumeWithInclusiveRange' is not implemented" "for this NonLoc"); case nonloc::LocAsIntegerKind: case nonloc::SymbolValKind: { if (SymbolRef Sym = Value.getAsSymbol()) - return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange); + return assumeSymInclusiveRange(State, Sym, From, To, InRange); return State; } // end switch @@ -226,109 +138,6 @@ } // end switch } -static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment) { - // Is it a "($sym+constant1)" expression? - if (const SymIntExpr *SE = dyn_cast(Sym)) { - BinaryOperator::Opcode Op = SE->getOpcode(); - if (Op == BO_Add || Op == BO_Sub) { - Sym = SE->getLHS(); - Adjustment = APSIntType(Adjustment).convert(SE->getRHS()); - - // Don't forget to negate the adjustment if it's being subtracted. - // This should happen /after/ promotion, in case the value being - // subtracted is, say, CHAR_MIN, and the promoted type is 'int'. - if (Op == BO_Sub) - Adjustment = -Adjustment; - } - } -} - -ProgramStateRef SimpleConstraintManager::assumeSymRel(ProgramStateRef state, - const SymExpr *LHS, - BinaryOperator::Opcode op, - const llvm::APSInt& Int) { - assert(BinaryOperator::isComparisonOp(op) && - "Non-comparison ops should be rewritten as comparisons to zero."); - - // Get the type used for calculating wraparound. - BasicValueFactory &BVF = getBasicVals(); - APSIntType WraparoundType = BVF.getAPSIntType(LHS->getType()); - - // We only handle simple comparisons of the form "$sym == constant" - // or "($sym+constant1) == constant2". - // The adjustment is "constant1" in the above expression. It's used to - // "slide" the solution range around for modular arithmetic. For example, - // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which - // in modular arithmetic is [0, 1] U [UINT_MAX-1, UINT_MAX]. It's up to - // the subclasses of SimpleConstraintManager to handle the adjustment. - SymbolRef Sym = LHS; - llvm::APSInt Adjustment = WraparoundType.getZeroValue(); - computeAdjustment(Sym, Adjustment); - - // Convert the right-hand side integer as necessary. - APSIntType ComparisonType = std::max(WraparoundType, APSIntType(Int)); - llvm::APSInt ConvertedInt = ComparisonType.convert(Int); - - // Prefer unsigned comparisons. - if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() && - ComparisonType.isUnsigned() && !WraparoundType.isUnsigned()) - Adjustment.setIsSigned(false); - - switch (op) { - default: - llvm_unreachable("invalid operation not caught by assertion above"); - - case BO_EQ: - return assumeSymEQ(state, Sym, ConvertedInt, Adjustment); - - case BO_NE: - return assumeSymNE(state, Sym, ConvertedInt, Adjustment); - - case BO_GT: - return assumeSymGT(state, Sym, ConvertedInt, Adjustment); - - case BO_GE: - return assumeSymGE(state, Sym, ConvertedInt, Adjustment); - - case BO_LT: - return assumeSymLT(state, Sym, ConvertedInt, Adjustment); - - case BO_LE: - return assumeSymLE(state, Sym, ConvertedInt, Adjustment); - } // end switch -} - -ProgramStateRef -SimpleConstraintManager::assumeSymWithinInclusiveRange(ProgramStateRef State, - SymbolRef Sym, - const llvm::APSInt &From, - const llvm::APSInt &To, - bool InRange) { - // Get the type used for calculating wraparound. - BasicValueFactory &BVF = getBasicVals(); - APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType()); - - llvm::APSInt Adjustment = WraparoundType.getZeroValue(); - SymbolRef AdjustedSym = Sym; - computeAdjustment(AdjustedSym, Adjustment); - - // Convert the right-hand side integer as necessary. - APSIntType ComparisonType = std::max(WraparoundType, APSIntType(From)); - llvm::APSInt ConvertedFrom = ComparisonType.convert(From); - llvm::APSInt ConvertedTo = ComparisonType.convert(To); - - // Prefer unsigned comparisons. - if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() && - ComparisonType.isUnsigned() && !WraparoundType.isUnsigned()) - Adjustment.setIsSigned(false); - - if (InRange) - return assumeSymbolWithinInclusiveRange(State, AdjustedSym, ConvertedFrom, - ConvertedTo, Adjustment); - return assumeSymbolOutOfInclusiveRange(State, AdjustedSym, ConvertedFrom, - ConvertedTo, Adjustment); -} - } // end of namespace ento } // end of namespace clang