diff options
Diffstat (limited to 'include/clang/Analysis/PathSensitive')
20 files changed, 5980 insertions, 0 deletions
diff --git a/include/clang/Analysis/PathSensitive/BasicValueFactory.h b/include/clang/Analysis/PathSensitive/BasicValueFactory.h new file mode 100644 index 0000000..b694e9b2 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/BasicValueFactory.h @@ -0,0 +1,163 @@ +//=== BasicValueFactory.h - Basic values for Path Sens analysis --*- 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 BasicValueFactory, a class that manages the lifetime +// of APSInt objects and symbolic constraints used by GRExprEngine +// and related classes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_BASICVALUEFACTORY_H +#define LLVM_CLANG_ANALYSIS_BASICVALUEFACTORY_H + +#include "clang/Analysis/PathSensitive/SymbolManager.h" +#include "clang/Analysis/PathSensitive/SVals.h" +#include "clang/AST/ASTContext.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/ADT/ImmutableList.h" + +namespace clang { + +class CompoundValData : public llvm::FoldingSetNode { + QualType T; + llvm::ImmutableList<SVal> L; + +public: + CompoundValData(QualType t, llvm::ImmutableList<SVal> l) + : T(t), L(l) {} + + typedef llvm::ImmutableList<SVal>::iterator iterator; + iterator begin() const { return L.begin(); } + iterator end() const { return L.end(); } + + static void Profile(llvm::FoldingSetNodeID& ID, QualType T, + llvm::ImmutableList<SVal> L); + + void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); } +}; + +class BasicValueFactory { + typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt> > + APSIntSetTy; + + ASTContext& Ctx; + llvm::BumpPtrAllocator& BPAlloc; + + APSIntSetTy APSIntSet; + void* PersistentSVals; + void* PersistentSValPairs; + + llvm::ImmutableList<SVal>::Factory SValListFactory; + llvm::FoldingSet<CompoundValData> CompoundValDataSet; + +public: + BasicValueFactory(ASTContext& ctx, llvm::BumpPtrAllocator& Alloc) + : Ctx(ctx), BPAlloc(Alloc), PersistentSVals(0), PersistentSValPairs(0), + SValListFactory(Alloc) {} + + ~BasicValueFactory(); + + ASTContext& getContext() const { return Ctx; } + + const llvm::APSInt& getValue(const llvm::APSInt& X); + const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned); + const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned); + const llvm::APSInt& getValue(uint64_t X, QualType T); + + /// Convert - Create a new persistent APSInt with the same value as 'From' + /// but with the bitwidth and signedness of 'To'. + const llvm::APSInt& Convert(const llvm::APSInt& To, + const llvm::APSInt& From) { + + if (To.isUnsigned() == From.isUnsigned() && + To.getBitWidth() == From.getBitWidth()) + return From; + + return getValue(From.getSExtValue(), + To.getBitWidth(), + To.isUnsigned()); + } + + const llvm::APSInt& getIntValue(uint64_t X, bool isUnsigned) { + QualType T = isUnsigned ? Ctx.UnsignedIntTy : Ctx.IntTy; + return getValue(X, T); + } + + inline const llvm::APSInt& getMaxValue(const llvm::APSInt &v) { + return getValue(llvm::APSInt::getMaxValue(v.getBitWidth(), v.isUnsigned())); + } + + inline const llvm::APSInt& getMinValue(const llvm::APSInt &v) { + return getValue(llvm::APSInt::getMinValue(v.getBitWidth(), v.isUnsigned())); + } + + inline const llvm::APSInt& getMaxValue(QualType T) { + assert(T->isIntegerType() || Loc::IsLocType(T)); + bool isUnsigned = T->isUnsignedIntegerType() || Loc::IsLocType(T); + return getValue(llvm::APSInt::getMaxValue(Ctx.getTypeSize(T), isUnsigned)); + } + + inline const llvm::APSInt& getMinValue(QualType T) { + assert(T->isIntegerType() || Loc::IsLocType(T)); + bool isUnsigned = T->isUnsignedIntegerType() || Loc::IsLocType(T); + return getValue(llvm::APSInt::getMinValue(Ctx.getTypeSize(T), isUnsigned)); + } + + inline const llvm::APSInt& Add1(const llvm::APSInt& V) { + llvm::APSInt X = V; + ++X; + return getValue(X); + } + + inline const llvm::APSInt& Sub1(const llvm::APSInt& V) { + llvm::APSInt X = V; + --X; + return getValue(X); + } + + inline const llvm::APSInt& getZeroWithPtrWidth(bool isUnsigned = true) { + return getValue(0, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned); + } + + inline const llvm::APSInt& getTruthValue(bool b, QualType T) { + return getValue(b ? 1 : 0, Ctx.getTypeSize(T), false); + } + + inline const llvm::APSInt& getTruthValue(bool b) { + return getTruthValue(b, Ctx.IntTy); + } + + const CompoundValData* getCompoundValData(QualType T, + llvm::ImmutableList<SVal> Vals); + + llvm::ImmutableList<SVal> getEmptySValList() { + return SValListFactory.GetEmptyList(); + } + + llvm::ImmutableList<SVal> consVals(SVal X, llvm::ImmutableList<SVal> L) { + return SValListFactory.Add(X, L); + } + + const llvm::APSInt* EvaluateAPSInt(BinaryOperator::Opcode Op, + const llvm::APSInt& V1, + const llvm::APSInt& V2); + + const std::pair<SVal, uintptr_t>& + getPersistentSValWithData(const SVal& V, uintptr_t Data); + + const std::pair<SVal, SVal>& + getPersistentSValPair(const SVal& V1, const SVal& V2); + + const SVal* getPersistentSVal(SVal X); +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/BugReporter.h b/include/clang/Analysis/PathSensitive/BugReporter.h new file mode 100644 index 0000000..90fd9d8 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/BugReporter.h @@ -0,0 +1,466 @@ +//===--- BugReporter.h - Generate PathDiagnostics --------------*- 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 BugReporter, a utility class for generating +// PathDiagnostics for analyses based on GRState. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_BUGREPORTER +#define LLVM_CLANG_ANALYSIS_BUGREPORTER + +#include "clang/Basic/Diagnostic.h" +#include "clang/Basic/SourceLocation.h" +#include "clang/Analysis/PathSensitive/GRState.h" +#include "clang/Analysis/PathSensitive/ExplodedGraph.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/ImmutableSet.h" +#include <list> + +namespace clang { + +class PathDiagnostic; +class PathDiagnosticPiece; +class PathDiagnosticClient; +class ASTContext; +class Diagnostic; +class BugReporter; +class BugReporterContext; +class GRExprEngine; +class GRState; +class Stmt; +class BugType; +class ParentMap; + +//===----------------------------------------------------------------------===// +// Interface for individual bug reports. +//===----------------------------------------------------------------------===// + +class BugReporterVisitor { +public: + virtual ~BugReporterVisitor(); + virtual PathDiagnosticPiece* VisitNode(const ExplodedNode<GRState>* N, + const ExplodedNode<GRState>* PrevN, + BugReporterContext& BRC) = 0; + + virtual bool isOwnedByReporterContext() { return true; } +}; + +// FIXME: Combine this with RangedBugReport and remove RangedBugReport. +class BugReport : public BugReporterVisitor { +protected: + BugType& BT; + std::string ShortDescription; + std::string Description; + const ExplodedNode<GRState> *EndNode; + SourceRange R; + +protected: + friend class BugReporter; + friend class BugReportEquivClass; + + virtual void Profile(llvm::FoldingSetNodeID& hash) const { + hash.AddInteger(getLocation().getRawEncoding()); + } + +public: + class NodeResolver { + public: + virtual ~NodeResolver() {} + virtual const ExplodedNode<GRState>* + getOriginalNode(const ExplodedNode<GRState>* N) = 0; + }; + + BugReport(BugType& bt, const char* desc, const ExplodedNode<GRState> *n) + : BT(bt), Description(desc), EndNode(n) {} + + BugReport(BugType& bt, const char* shortDesc, const char* desc, + const ExplodedNode<GRState> *n) + : BT(bt), ShortDescription(shortDesc), Description(desc), EndNode(n) {} + + virtual ~BugReport(); + + virtual bool isOwnedByReporterContext() { return false; } + + const BugType& getBugType() const { return BT; } + BugType& getBugType() { return BT; } + + // FIXME: Perhaps this should be moved into a subclass? + const ExplodedNode<GRState>* getEndNode() const { return EndNode; } + + // FIXME: Do we need this? Maybe getLocation() should return a ProgramPoint + // object. + // FIXME: If we do need it, we can probably just make it private to + // BugReporter. + Stmt* getStmt(BugReporter& BR) const; + + const std::string& getDescription() const { return Description; } + + const std::string& getShortDescription() const { + return ShortDescription.empty() ? Description : ShortDescription; + } + + // FIXME: Is this needed? + virtual std::pair<const char**,const char**> getExtraDescriptiveText() { + return std::make_pair((const char**)0,(const char**)0); + } + + // FIXME: Perhaps move this into a subclass. + virtual PathDiagnosticPiece* getEndPath(BugReporterContext& BRC, + const ExplodedNode<GRState>* N); + + /// getLocation - Return the "definitive" location of the reported bug. + /// While a bug can span an entire path, usually there is a specific + /// location that can be used to identify where the key issue occured. + /// This location is used by clients rendering diagnostics. + virtual SourceLocation getLocation() const; + + /// getRanges - Returns the source ranges associated with this bug. + virtual void getRanges(BugReporter& BR,const SourceRange*& beg, + const SourceRange*& end); + + virtual PathDiagnosticPiece* VisitNode(const ExplodedNode<GRState>* N, + const ExplodedNode<GRState>* PrevN, + BugReporterContext& BR); + + virtual void registerInitialVisitors(BugReporterContext& BRC, + const ExplodedNode<GRState>* N) {} +}; + +//===----------------------------------------------------------------------===// +// BugTypes (collections of related reports). +//===----------------------------------------------------------------------===// + +class BugReportEquivClass : public llvm::FoldingSetNode { + // List of *owned* BugReport objects. + std::list<BugReport*> Reports; + + friend class BugReporter; + void AddReport(BugReport* R) { Reports.push_back(R); } +public: + BugReportEquivClass(BugReport* R) { Reports.push_back(R); } + ~BugReportEquivClass(); + + void Profile(llvm::FoldingSetNodeID& ID) const { + assert(!Reports.empty()); + (*Reports.begin())->Profile(ID); + } + + class iterator { + std::list<BugReport*>::iterator impl; + public: + iterator(std::list<BugReport*>::iterator i) : impl(i) {} + iterator& operator++() { ++impl; return *this; } + bool operator==(const iterator& I) const { return I.impl == impl; } + bool operator!=(const iterator& I) const { return I.impl != impl; } + BugReport* operator*() const { return *impl; } + BugReport* operator->() const { return *impl; } + }; + + class const_iterator { + std::list<BugReport*>::const_iterator impl; + public: + const_iterator(std::list<BugReport*>::const_iterator i) : impl(i) {} + const_iterator& operator++() { ++impl; return *this; } + bool operator==(const const_iterator& I) const { return I.impl == impl; } + bool operator!=(const const_iterator& I) const { return I.impl != impl; } + const BugReport* operator*() const { return *impl; } + const BugReport* operator->() const { return *impl; } + }; + + iterator begin() { return iterator(Reports.begin()); } + iterator end() { return iterator(Reports.end()); } + + const_iterator begin() const { return const_iterator(Reports.begin()); } + const_iterator end() const { return const_iterator(Reports.end()); } +}; + +class BugType { +private: + const std::string Name; + const std::string Category; + llvm::FoldingSet<BugReportEquivClass> EQClasses; + friend class BugReporter; +public: + BugType(const char *name, const char* cat) : Name(name), Category(cat) {} + virtual ~BugType(); + + // FIXME: Should these be made strings as well? + const std::string& getName() const { return Name; } + const std::string& getCategory() const { return Category; } + + virtual void FlushReports(BugReporter& BR); + void AddReport(BugReport* BR); + + typedef llvm::FoldingSet<BugReportEquivClass>::iterator iterator; + iterator begin() { return EQClasses.begin(); } + iterator end() { return EQClasses.end(); } + + typedef llvm::FoldingSet<BugReportEquivClass>::const_iterator const_iterator; + const_iterator begin() const { return EQClasses.begin(); } + const_iterator end() const { return EQClasses.end(); } +}; + +//===----------------------------------------------------------------------===// +// Specialized subclasses of BugReport. +//===----------------------------------------------------------------------===// + +// FIXME: Collapse this with the default BugReport class. +class RangedBugReport : public BugReport { + std::vector<SourceRange> Ranges; +public: + RangedBugReport(BugType& D, const char* description, ExplodedNode<GRState> *n) + : BugReport(D, description, n) {} + + RangedBugReport(BugType& D, const char *shortDescription, + const char *description, ExplodedNode<GRState> *n) + : BugReport(D, shortDescription, description, n) {} + + ~RangedBugReport(); + + // FIXME: Move this out of line. + void addRange(SourceRange R) { Ranges.push_back(R); } + + // FIXME: Move this out of line. + void getRanges(BugReporter& BR,const SourceRange*& beg, + const SourceRange*& end) { + + if (Ranges.empty()) { + beg = NULL; + end = NULL; + } + else { + beg = &Ranges[0]; + end = beg + Ranges.size(); + } + } +}; + +//===----------------------------------------------------------------------===// +// BugReporter and friends. +//===----------------------------------------------------------------------===// + +class BugReporterData { +public: + virtual ~BugReporterData(); + virtual Diagnostic& getDiagnostic() = 0; + virtual PathDiagnosticClient* getPathDiagnosticClient() = 0; + virtual ASTContext& getContext() = 0; + virtual SourceManager& getSourceManager() = 0; + virtual CFG* getCFG() = 0; + virtual ParentMap& getParentMap() = 0; + virtual LiveVariables* getLiveVariables() = 0; +}; + +class BugReporter { +public: + enum Kind { BaseBRKind, GRBugReporterKind }; + +private: + typedef llvm::ImmutableSet<BugType*> BugTypesTy; + BugTypesTy::Factory F; + BugTypesTy BugTypes; + + const Kind kind; + BugReporterData& D; + + void FlushReport(BugReportEquivClass& EQ); + +protected: + BugReporter(BugReporterData& d, Kind k) : BugTypes(F.GetEmptySet()), kind(k), D(d) {} + +public: + BugReporter(BugReporterData& d) : BugTypes(F.GetEmptySet()), kind(BaseBRKind), D(d) {} + virtual ~BugReporter(); + + void FlushReports(); + + Kind getKind() const { return kind; } + + Diagnostic& getDiagnostic() { + return D.getDiagnostic(); + } + + PathDiagnosticClient* getPathDiagnosticClient() { + return D.getPathDiagnosticClient(); + } + + typedef BugTypesTy::iterator iterator; + iterator begin() { return BugTypes.begin(); } + iterator end() { return BugTypes.end(); } + + ASTContext& getContext() { return D.getContext(); } + + SourceManager& getSourceManager() { return D.getSourceManager(); } + + CFG* getCFG() { return D.getCFG(); } + + ParentMap& getParentMap() { return D.getParentMap(); } + + LiveVariables* getLiveVariables() { return D.getLiveVariables(); } + + virtual void GeneratePathDiagnostic(PathDiagnostic& PD, + BugReportEquivClass& EQ) {} + + void Register(BugType *BT); + + void EmitReport(BugReport *R); + + void EmitBasicReport(const char* BugName, const char* BugStr, + SourceLocation Loc, + SourceRange* RangeBeg, unsigned NumRanges); + + void EmitBasicReport(const char* BugName, const char* BugCategory, + const char* BugStr, SourceLocation Loc, + SourceRange* RangeBeg, unsigned NumRanges); + + + void EmitBasicReport(const char* BugName, const char* BugStr, + SourceLocation Loc) { + EmitBasicReport(BugName, BugStr, Loc, 0, 0); + } + + void EmitBasicReport(const char* BugName, const char* BugCategory, + const char* BugStr, SourceLocation Loc) { + EmitBasicReport(BugName, BugCategory, BugStr, Loc, 0, 0); + } + + void EmitBasicReport(const char* BugName, const char* BugStr, + SourceLocation Loc, SourceRange R) { + EmitBasicReport(BugName, BugStr, Loc, &R, 1); + } + + void EmitBasicReport(const char* BugName, const char* Category, + const char* BugStr, SourceLocation Loc, SourceRange R) { + EmitBasicReport(BugName, Category, BugStr, Loc, &R, 1); + } + + static bool classof(const BugReporter* R) { return true; } +}; + +// FIXME: Get rid of GRBugReporter. It's the wrong abstraction. +class GRBugReporter : public BugReporter { + GRExprEngine& Eng; + llvm::SmallSet<SymbolRef, 10> NotableSymbols; +public: + GRBugReporter(BugReporterData& d, GRExprEngine& eng) + : BugReporter(d, GRBugReporterKind), Eng(eng) {} + + virtual ~GRBugReporter(); + + /// getEngine - Return the analysis engine used to analyze a given + /// function or method. + GRExprEngine& getEngine() { return Eng; } + + /// getGraph - Get the exploded graph created by the analysis engine + /// for the analyzed method or function. + ExplodedGraph<GRState>& getGraph(); + + /// getStateManager - Return the state manager used by the analysis + /// engine. + GRStateManager& getStateManager(); + + virtual void GeneratePathDiagnostic(PathDiagnostic& PD, + BugReportEquivClass& R); + + void addNotableSymbol(SymbolRef Sym) { + NotableSymbols.insert(Sym); + } + + bool isNotable(SymbolRef Sym) const { + return (bool) NotableSymbols.count(Sym); + } + + /// classof - Used by isa<>, cast<>, and dyn_cast<>. + static bool classof(const BugReporter* R) { + return R->getKind() == GRBugReporterKind; + } +}; + +class BugReporterContext { + GRBugReporter &BR; + std::vector<BugReporterVisitor*> Callbacks; +public: + BugReporterContext(GRBugReporter& br) : BR(br) {} + virtual ~BugReporterContext(); + + void addVisitor(BugReporterVisitor* visitor) { + if (visitor) Callbacks.push_back(visitor); + } + + typedef std::vector<BugReporterVisitor*>::iterator visitor_iterator; + visitor_iterator visitor_begin() { return Callbacks.begin(); } + visitor_iterator visitor_end() { return Callbacks.end(); } + + GRBugReporter& getBugReporter() { return BR; } + + ExplodedGraph<GRState>& getGraph() { return BR.getGraph(); } + + void addNotableSymbol(SymbolRef Sym) { + // FIXME: For now forward to GRBugReporter. + BR.addNotableSymbol(Sym); + } + + bool isNotable(SymbolRef Sym) const { + // FIXME: For now forward to GRBugReporter. + return BR.isNotable(Sym); + } + + GRStateManager& getStateManager() { + return BR.getStateManager(); + } + + ValueManager& getValueManager() { + return getStateManager().getValueManager(); + } + + ASTContext& getASTContext() { + return BR.getContext(); + } + + SourceManager& getSourceManager() { + return BR.getSourceManager(); + } + + const Decl& getCodeDecl() { + return getStateManager().getCodeDecl(); + } + + const CFG& getCFG() { + return *BR.getCFG(); + } + + virtual BugReport::NodeResolver& getNodeResolver() = 0; +}; + +class DiagBugReport : public RangedBugReport { + std::list<std::string> Strs; + FullSourceLoc L; +public: + DiagBugReport(BugType& D, const char* desc, FullSourceLoc l) : + RangedBugReport(D, desc, 0), L(l) {} + + virtual ~DiagBugReport() {} + + // FIXME: Move out-of-line (virtual function). + SourceLocation getLocation() const { return L; } + + void addString(const std::string& s) { Strs.push_back(s); } + + typedef std::list<std::string>::const_iterator str_iterator; + str_iterator str_begin() const { return Strs.begin(); } + str_iterator str_end() const { return Strs.end(); } +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/ConstraintManager.h b/include/clang/Analysis/PathSensitive/ConstraintManager.h new file mode 100644 index 0000000..c8e5e85 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/ConstraintManager.h @@ -0,0 +1,67 @@ +//== ConstraintManager.h - Constraints on symbolic values.-------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the interface to manage constraints on symbolic values. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CONSTRAINT_MANAGER_H +#define LLVM_CLANG_ANALYSIS_CONSTRAINT_MANAGER_H + +// FIXME: Typedef LiveSymbolsTy/DeadSymbolsTy at a more appropriate place. +#include "clang/Analysis/PathSensitive/Store.h" + +namespace llvm { +class APSInt; +} + +namespace clang { + +class GRState; +class GRStateManager; +class SVal; + +class ConstraintManager { +public: + virtual ~ConstraintManager(); + virtual const GRState* Assume(const GRState* St, SVal Cond, + bool Assumption, bool& isFeasible) = 0; + + virtual const GRState* AssumeInBound(const GRState* St, SVal Idx, + SVal UpperBound, bool Assumption, + bool& isFeasible) = 0; + + virtual const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) + const = 0; + + virtual bool isEqual(const GRState* St, SymbolRef sym, + const llvm::APSInt& V) const = 0; + + virtual const GRState* RemoveDeadBindings(const GRState* St, + SymbolReaper& SymReaper) = 0; + + virtual void print(const GRState* St, std::ostream& Out, + const char* nl, const char *sep) = 0; + + virtual void EndPath(const GRState* St) {} + + /// canReasonAbout - Not all ConstraintManagers can accurately reason about + /// all SVal values. This method returns true if the ConstraintManager can + /// reasonably handle a given SVal value. This is typically queried by + /// GRExprEngine to determine if the value should be replaced with a + /// conjured symbolic value in order to recover some precision. + virtual bool canReasonAbout(SVal X) const = 0; +}; + +ConstraintManager* CreateBasicConstraintManager(GRStateManager& statemgr); +ConstraintManager* CreateRangeConstraintManager(GRStateManager& statemgr); + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/Environment.h b/include/clang/Analysis/PathSensitive/Environment.h new file mode 100644 index 0000000..fde8b16 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/Environment.h @@ -0,0 +1,151 @@ +//== Environment.h - Map from Stmt* to Locations/Values ---------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the Environment and EnvironmentManager classes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ENVIRONMENT_H +#define LLVM_CLANG_ANALYSIS_ENVIRONMENT_H + +// For using typedefs in StoreManager. Should find a better place for these +// typedefs. +#include "clang/Analysis/PathSensitive/Store.h" + +#include "llvm/ADT/ImmutableMap.h" +#include "llvm/ADT/SmallVector.h" +#include "clang/Analysis/PathSensitive/SVals.h" +#include "llvm/Support/Allocator.h" +#include "llvm/ADT/FoldingSet.h" + +namespace clang { + +class EnvironmentManager; +class BasicValueFactory; +class LiveVariables; + +class Environment : public llvm::FoldingSetNode { +private: + + friend class EnvironmentManager; + + // Type definitions. + typedef llvm::ImmutableMap<Stmt*,SVal> BindingsTy; + + // Data. + BindingsTy SubExprBindings; + BindingsTy BlkExprBindings; + + Environment(BindingsTy seb, BindingsTy beb) + : SubExprBindings(seb), BlkExprBindings(beb) {} + +public: + + typedef BindingsTy::iterator seb_iterator; + seb_iterator seb_begin() const { return SubExprBindings.begin(); } + seb_iterator seb_end() const { return SubExprBindings.end(); } + + typedef BindingsTy::iterator beb_iterator; + beb_iterator beb_begin() const { return BlkExprBindings.begin(); } + beb_iterator beb_end() const { return BlkExprBindings.end(); } + + SVal LookupSubExpr(Stmt* E) const { + const SVal* X = SubExprBindings.lookup(cast<Expr>(E)); + return X ? *X : UnknownVal(); + } + + SVal LookupBlkExpr(Stmt* E) const { + const SVal* X = BlkExprBindings.lookup(E); + return X ? *X : UnknownVal(); + } + + SVal LookupExpr(Stmt* E) const { + const SVal* X = SubExprBindings.lookup(E); + if (X) return *X; + X = BlkExprBindings.lookup(E); + return X ? *X : UnknownVal(); + } + + SVal GetSVal(Stmt* Ex, BasicValueFactory& BasicVals) const; + SVal GetBlkExprSVal(Stmt* Ex, BasicValueFactory& BasicVals) const; + + /// Profile - Profile the contents of an Environment object for use + /// in a FoldingSet. + static void Profile(llvm::FoldingSetNodeID& ID, const Environment* E) { + E->SubExprBindings.Profile(ID); + E->BlkExprBindings.Profile(ID); + } + + /// Profile - Used to profile the contents of this object for inclusion + /// in a FoldingSet. + void Profile(llvm::FoldingSetNodeID& ID) const { + Profile(ID, this); + } + + bool operator==(const Environment& RHS) const { + return SubExprBindings == RHS.SubExprBindings && + BlkExprBindings == RHS.BlkExprBindings; + } +}; + +class EnvironmentManager { +private: + typedef Environment::BindingsTy::Factory FactoryTy; + FactoryTy F; + +public: + + EnvironmentManager(llvm::BumpPtrAllocator& Allocator) : F(Allocator) {} + ~EnvironmentManager() {} + + /// RemoveBlkExpr - Return a new environment object with the same bindings as + /// the provided environment except with any bindings for the provided Stmt* + /// removed. This method only removes bindings for block-level expressions. + /// Using this method on a non-block level expression will return the + /// same environment object. + Environment RemoveBlkExpr(const Environment& Env, Stmt* E) { + return Environment(Env.SubExprBindings, F.Remove(Env.BlkExprBindings, E)); + } + + Environment RemoveSubExpr(const Environment& Env, Stmt* E) { + return Environment(F.Remove(Env.SubExprBindings, E), Env.BlkExprBindings); + } + + Environment AddBlkExpr(const Environment& Env, Stmt* E, SVal V) { + return Environment(Env.SubExprBindings, F.Add(Env.BlkExprBindings, E, V)); + } + + Environment AddSubExpr(const Environment& Env, Stmt* E, SVal V) { + return Environment(F.Add(Env.SubExprBindings, E, V), Env.BlkExprBindings); + } + + /// RemoveSubExprBindings - Return a new environment object with + /// the same bindings as the provided environment except with all the + /// subexpression bindings removed. + Environment RemoveSubExprBindings(const Environment& Env) { + return Environment(F.GetEmptyMap(), Env.BlkExprBindings); + } + + Environment getInitialEnvironment() { + return Environment(F.GetEmptyMap(), F.GetEmptyMap()); + } + + Environment BindExpr(const Environment& Env, Stmt* E, SVal V, + bool isBlkExpr, bool Invalidate); + + Environment + RemoveDeadBindings(Environment Env, Stmt* Loc, SymbolReaper& SymReaper, + GRStateManager& StateMgr, const GRState *state, + llvm::SmallVectorImpl<const MemRegion*>& DRoots); + +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h new file mode 100644 index 0000000..8494d93 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h @@ -0,0 +1,582 @@ +//=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- 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 the template classes ExplodedNode and ExplodedGraph, +// which represent a path-sensitive, intra-procedural "exploded graph." +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH +#define LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH + +#include "clang/Analysis/ProgramPoint.h" +#include "clang/AST/Decl.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Support/Allocator.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/Support/Casting.h" + +namespace clang { + +class GRCoreEngineImpl; +class ExplodedNodeImpl; +class CFG; +class ASTContext; + +class GRStmtNodeBuilderImpl; +class GRBranchNodeBuilderImpl; +class GRIndirectGotoNodeBuilderImpl; +class GRSwitchNodeBuilderImpl; +class GREndPathNodebuilderImpl; + +//===----------------------------------------------------------------------===// +// ExplodedGraph "implementation" classes. These classes are not typed to +// contain a specific kind of state. Typed-specialized versions are defined +// on top of these classes. +//===----------------------------------------------------------------------===// + +class ExplodedNodeImpl : public llvm::FoldingSetNode { +protected: + friend class ExplodedGraphImpl; + friend class GRCoreEngineImpl; + friend class GRStmtNodeBuilderImpl; + friend class GRBranchNodeBuilderImpl; + friend class GRIndirectGotoNodeBuilderImpl; + friend class GRSwitchNodeBuilderImpl; + friend class GREndPathNodeBuilderImpl; + + class NodeGroup { + enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 }; + uintptr_t P; + + unsigned getKind() const { + return P & 0x1; + } + + void* getPtr() const { + assert (!getFlag()); + return reinterpret_cast<void*>(P & ~Mask); + } + + ExplodedNodeImpl* getNode() const { + return reinterpret_cast<ExplodedNodeImpl*>(getPtr()); + } + + public: + NodeGroup() : P(0) {} + + ~NodeGroup(); + + ExplodedNodeImpl** begin() const; + + ExplodedNodeImpl** end() const; + + unsigned size() const; + + bool empty() const { return size() == 0; } + + void addNode(ExplodedNodeImpl* N); + + void setFlag() { + assert (P == 0); + P = AuxFlag; + } + + bool getFlag() const { + return P & AuxFlag ? true : false; + } + }; + + /// Location - The program location (within a function body) associated + /// with this node. + const ProgramPoint Location; + + /// State - The state associated with this node. + const void* State; + + /// Preds - The predecessors of this node. + NodeGroup Preds; + + /// Succs - The successors of this node. + NodeGroup Succs; + + /// Construct a ExplodedNodeImpl with the provided location and state. + explicit ExplodedNodeImpl(const ProgramPoint& loc, const void* state) + : Location(loc), State(state) {} + + /// addPredeccessor - Adds a predecessor to the current node, and + /// in tandem add this node as a successor of the other node. + void addPredecessor(ExplodedNodeImpl* V); + +public: + + /// getLocation - Returns the edge associated with the given node. + ProgramPoint getLocation() const { return Location; } + + template <typename T> + const T* getLocationAs() const { return llvm::dyn_cast<T>(&Location); } + + unsigned succ_size() const { return Succs.size(); } + unsigned pred_size() const { return Preds.size(); } + bool succ_empty() const { return Succs.empty(); } + bool pred_empty() const { return Preds.empty(); } + + bool isSink() const { return Succs.getFlag(); } + void markAsSink() { Succs.setFlag(); } + + // For debugging. + +public: + + class Auditor { + public: + virtual ~Auditor(); + virtual void AddEdge(ExplodedNodeImpl* Src, ExplodedNodeImpl* Dst) = 0; + }; + + static void SetAuditor(Auditor* A); +}; + + +template <typename StateTy> +struct GRTrait { + static inline void Profile(llvm::FoldingSetNodeID& ID, const StateTy* St) { + St->Profile(ID); + } +}; + + +template <typename StateTy> +class ExplodedNode : public ExplodedNodeImpl { +public: + /// Construct a ExplodedNodeImpl with the given node ID, program edge, + /// and state. + explicit ExplodedNode(const ProgramPoint& loc, const StateTy* St) + : ExplodedNodeImpl(loc, St) {} + + /// getState - Returns the state associated with the node. + inline const StateTy* getState() const { + return static_cast<const StateTy*>(State); + } + + // Profiling (for FoldingSet). + + static inline void Profile(llvm::FoldingSetNodeID& ID, + const ProgramPoint& Loc, + const StateTy* state) { + ID.Add(Loc); + GRTrait<StateTy>::Profile(ID, state); + } + + inline void Profile(llvm::FoldingSetNodeID& ID) const { + Profile(ID, getLocation(), getState()); + } + + void addPredecessor(ExplodedNode* V) { + ExplodedNodeImpl::addPredecessor(V); + } + + ExplodedNode* getFirstPred() { + return pred_empty() ? NULL : *(pred_begin()); + } + + const ExplodedNode* getFirstPred() const { + return const_cast<ExplodedNode*>(this)->getFirstPred(); + } + + // Iterators over successor and predecessor vertices. + typedef ExplodedNode** succ_iterator; + typedef const ExplodedNode* const * const_succ_iterator; + typedef ExplodedNode** pred_iterator; + typedef const ExplodedNode* const * const_pred_iterator; + + pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); } + pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); } + + const_pred_iterator pred_begin() const { + return const_cast<ExplodedNode*>(this)->pred_begin(); + } + const_pred_iterator pred_end() const { + return const_cast<ExplodedNode*>(this)->pred_end(); + } + + succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); } + succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); } + + const_succ_iterator succ_begin() const { + return const_cast<ExplodedNode*>(this)->succ_begin(); + } + const_succ_iterator succ_end() const { + return const_cast<ExplodedNode*>(this)->succ_end(); + } +}; + +class InterExplodedGraphMapImpl; + +class ExplodedGraphImpl { +protected: + friend class GRCoreEngineImpl; + friend class GRStmtNodeBuilderImpl; + friend class GRBranchNodeBuilderImpl; + friend class GRIndirectGotoNodeBuilderImpl; + friend class GRSwitchNodeBuilderImpl; + friend class GREndPathNodeBuilderImpl; + + // Type definitions. + typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; + typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; + + /// Roots - The roots of the simulation graph. Usually there will be only + /// one, but clients are free to establish multiple subgraphs within a single + /// SimulGraph. Moreover, these subgraphs can often merge when paths from + /// different roots reach the same state at the same program location. + RootsTy Roots; + + /// EndNodes - The nodes in the simulation graph which have been + /// specially marked as the endpoint of an abstract simulation path. + EndNodesTy EndNodes; + + /// Allocator - BumpPtrAllocator to create nodes. + llvm::BumpPtrAllocator Allocator; + + /// cfg - The CFG associated with this analysis graph. + CFG& cfg; + + /// CodeDecl - The declaration containing the code being analyzed. This + /// can be a FunctionDecl or and ObjCMethodDecl. + Decl& CodeDecl; + + /// Ctx - The ASTContext used to "interpret" CodeDecl. + ASTContext& Ctx; + + /// NumNodes - The number of nodes in the graph. + unsigned NumNodes; + + /// getNodeImpl - Retrieve the node associated with a (Location,State) + /// pair, where 'State' is represented as an opaque void*. This method + /// is intended to be used only by GRCoreEngineImpl. + virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, + const void* State, + bool* IsNew) = 0; + + virtual ExplodedGraphImpl* MakeEmptyGraph() const = 0; + + /// addRoot - Add an untyped node to the set of roots. + ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { + Roots.push_back(V); + return V; + } + + /// addEndOfPath - Add an untyped node to the set of EOP nodes. + ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { + EndNodes.push_back(V); + return V; + } + + // ctor. + ExplodedGraphImpl(CFG& c, Decl& cd, ASTContext& ctx) + : cfg(c), CodeDecl(cd), Ctx(ctx), NumNodes(0) {} + +public: + virtual ~ExplodedGraphImpl() {} + + unsigned num_roots() const { return Roots.size(); } + unsigned num_eops() const { return EndNodes.size(); } + + bool empty() const { return NumNodes == 0; } + unsigned size() const { return NumNodes; } + + llvm::BumpPtrAllocator& getAllocator() { return Allocator; } + CFG& getCFG() { return cfg; } + ASTContext& getContext() { return Ctx; } + + Decl& getCodeDecl() { return CodeDecl; } + const Decl& getCodeDecl() const { return CodeDecl; } + + const FunctionDecl* getFunctionDecl() const { + return llvm::dyn_cast<FunctionDecl>(&CodeDecl); + } + + typedef llvm::DenseMap<const ExplodedNodeImpl*, ExplodedNodeImpl*> NodeMap; + + ExplodedGraphImpl* Trim(const ExplodedNodeImpl* const * NBeg, + const ExplodedNodeImpl* const * NEnd, + InterExplodedGraphMapImpl *M, + llvm::DenseMap<const void*, const void*> *InverseMap) + const; +}; + +class InterExplodedGraphMapImpl { + llvm::DenseMap<const ExplodedNodeImpl*, ExplodedNodeImpl*> M; + friend class ExplodedGraphImpl; + void add(const ExplodedNodeImpl* From, ExplodedNodeImpl* To); + +protected: + ExplodedNodeImpl* getMappedImplNode(const ExplodedNodeImpl* N) const; + + InterExplodedGraphMapImpl(); +public: + virtual ~InterExplodedGraphMapImpl() {} +}; + +//===----------------------------------------------------------------------===// +// Type-specialized ExplodedGraph classes. +//===----------------------------------------------------------------------===// + +template <typename STATE> +class InterExplodedGraphMap : public InterExplodedGraphMapImpl { +public: + InterExplodedGraphMap() {}; + ~InterExplodedGraphMap() {}; + + ExplodedNode<STATE>* getMappedNode(const ExplodedNode<STATE>* N) const { + return static_cast<ExplodedNode<STATE>*>(getMappedImplNode(N)); + } +}; + +template <typename STATE> +class ExplodedGraph : public ExplodedGraphImpl { +public: + typedef STATE StateTy; + typedef ExplodedNode<StateTy> NodeTy; + typedef llvm::FoldingSet<NodeTy> AllNodesTy; + +protected: + /// Nodes - The nodes in the graph. + AllNodesTy Nodes; + +protected: + virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, + const void* State, + bool* IsNew) { + + return getNode(L, static_cast<const StateTy*>(State), IsNew); + } + + virtual ExplodedGraphImpl* MakeEmptyGraph() const { + return new ExplodedGraph(cfg, CodeDecl, Ctx); + } + +public: + ExplodedGraph(CFG& c, Decl& cd, ASTContext& ctx) + : ExplodedGraphImpl(c, cd, ctx) {} + + /// getNode - Retrieve the node associated with a (Location,State) pair, + /// where the 'Location' is a ProgramPoint in the CFG. If no node for + /// this pair exists, it is created. IsNew is set to true if + /// the node was freshly created. + NodeTy* getNode(const ProgramPoint& L, const StateTy* State, + bool* IsNew = NULL) { + + // Profile 'State' to determine if we already have an existing node. + llvm::FoldingSetNodeID profile; + void* InsertPos = 0; + + NodeTy::Profile(profile, L, State); + NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos); + + if (!V) { + // Allocate a new node. + V = (NodeTy*) Allocator.Allocate<NodeTy>(); + new (V) NodeTy(L, State); + + // Insert the node into the node set and return it. + Nodes.InsertNode(V, InsertPos); + + ++NumNodes; + + if (IsNew) *IsNew = true; + } + else + if (IsNew) *IsNew = false; + + return V; + } + + // Iterators. + typedef NodeTy** roots_iterator; + typedef const NodeTy** const_roots_iterator; + typedef NodeTy** eop_iterator; + typedef const NodeTy** const_eop_iterator; + typedef typename AllNodesTy::iterator node_iterator; + typedef typename AllNodesTy::const_iterator const_node_iterator; + + node_iterator nodes_begin() { + return Nodes.begin(); + } + + node_iterator nodes_end() { + return Nodes.end(); + } + + const_node_iterator nodes_begin() const { + return Nodes.begin(); + } + + const_node_iterator nodes_end() const { + return Nodes.end(); + } + + roots_iterator roots_begin() { + return reinterpret_cast<roots_iterator>(Roots.begin()); + } + + roots_iterator roots_end() { + return reinterpret_cast<roots_iterator>(Roots.end()); + } + + const_roots_iterator roots_begin() const { + return const_cast<ExplodedGraph>(this)->roots_begin(); + } + + const_roots_iterator roots_end() const { + return const_cast<ExplodedGraph>(this)->roots_end(); + } + + eop_iterator eop_begin() { + return reinterpret_cast<eop_iterator>(EndNodes.begin()); + } + + eop_iterator eop_end() { + return reinterpret_cast<eop_iterator>(EndNodes.end()); + } + + const_eop_iterator eop_begin() const { + return const_cast<ExplodedGraph>(this)->eop_begin(); + } + + const_eop_iterator eop_end() const { + return const_cast<ExplodedGraph>(this)->eop_end(); + } + + std::pair<ExplodedGraph*, InterExplodedGraphMap<STATE>*> + Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd, + llvm::DenseMap<const void*, const void*> *InverseMap = 0) const { + + if (NBeg == NEnd) + return std::make_pair((ExplodedGraph*) 0, + (InterExplodedGraphMap<STATE>*) 0); + + assert (NBeg < NEnd); + + const ExplodedNodeImpl* const* NBegImpl = + (const ExplodedNodeImpl* const*) NBeg; + const ExplodedNodeImpl* const* NEndImpl = + (const ExplodedNodeImpl* const*) NEnd; + + llvm::OwningPtr<InterExplodedGraphMap<STATE> > + M(new InterExplodedGraphMap<STATE>()); + + ExplodedGraphImpl* G = ExplodedGraphImpl::Trim(NBegImpl, NEndImpl, M.get(), + InverseMap); + + return std::make_pair(static_cast<ExplodedGraph*>(G), M.take()); + } +}; + +template <typename StateTy> +class ExplodedNodeSet { + + typedef ExplodedNode<StateTy> NodeTy; + typedef llvm::SmallPtrSet<NodeTy*,5> ImplTy; + ImplTy Impl; + +public: + ExplodedNodeSet(NodeTy* N) { + assert (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()); + Impl.insert(N); + } + + ExplodedNodeSet() {} + + inline void Add(NodeTy* N) { + if (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()) Impl.insert(N); + } + + typedef typename ImplTy::iterator iterator; + typedef typename ImplTy::const_iterator const_iterator; + + inline unsigned size() const { return Impl.size(); } + inline bool empty() const { return Impl.empty(); } + + inline void clear() { Impl.clear(); } + + inline iterator begin() { return Impl.begin(); } + inline iterator end() { return Impl.end(); } + + inline const_iterator begin() const { return Impl.begin(); } + inline const_iterator end() const { return Impl.end(); } +}; + +} // end clang namespace + +// GraphTraits + +namespace llvm { + template<typename StateTy> + struct GraphTraits<clang::ExplodedNode<StateTy>*> { + typedef clang::ExplodedNode<StateTy> NodeType; + typedef typename NodeType::succ_iterator ChildIteratorType; + typedef llvm::df_iterator<NodeType*> nodes_iterator; + + static inline NodeType* getEntryNode(NodeType* N) { + return N; + } + + static inline ChildIteratorType child_begin(NodeType* N) { + return N->succ_begin(); + } + + static inline ChildIteratorType child_end(NodeType* N) { + return N->succ_end(); + } + + static inline nodes_iterator nodes_begin(NodeType* N) { + return df_begin(N); + } + + static inline nodes_iterator nodes_end(NodeType* N) { + return df_end(N); + } + }; + + template<typename StateTy> + struct GraphTraits<const clang::ExplodedNode<StateTy>*> { + typedef const clang::ExplodedNode<StateTy> NodeType; + typedef typename NodeType::succ_iterator ChildIteratorType; + typedef llvm::df_iterator<NodeType*> nodes_iterator; + + static inline NodeType* getEntryNode(NodeType* N) { + return N; + } + + static inline ChildIteratorType child_begin(NodeType* N) { + return N->succ_begin(); + } + + static inline ChildIteratorType child_end(NodeType* N) { + return N->succ_end(); + } + + static inline nodes_iterator nodes_begin(NodeType* N) { + return df_begin(N); + } + + static inline nodes_iterator nodes_end(NodeType* N) { + return df_end(N); + } + }; + +} // end llvm namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRAuditor.h b/include/clang/Analysis/PathSensitive/GRAuditor.h new file mode 100644 index 0000000..eca591d --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRAuditor.h @@ -0,0 +1,39 @@ +//==- GRAuditor.h - Observers of the creation of ExplodedNodes------*- 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 GRAuditor and its primary subclasses, an interface +// to audit the creation of ExplodedNodes. This interface can be used +// to implement simple checkers that do not mutate analysis state but +// instead operate by perfoming simple logical checks at key monitoring +// locations (e.g., function calls). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_GRAUDITOR +#define LLVM_CLANG_ANALYSIS_GRAUDITOR + +#include "clang/AST/Expr.h" +#include "clang/Analysis/PathSensitive/ExplodedGraph.h" + +namespace clang { + +template <typename STATE> +class GRAuditor { +public: + typedef ExplodedNode<STATE> NodeTy; + typedef typename STATE::ManagerTy ManagerTy; + + virtual ~GRAuditor() {} + virtual bool Audit(NodeTy* N, ManagerTy& M) = 0; +}; + + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRBlockCounter.h b/include/clang/Analysis/PathSensitive/GRBlockCounter.h new file mode 100644 index 0000000..b4fd270 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRBlockCounter.h @@ -0,0 +1,50 @@ +//==- GRBlockCounter.h - ADT for counting block visits -------------*- 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 GRBlockCounter, an abstract data type used to count +// the number of times a given block has been visited along a path +// analyzed by GRCoreEngine. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_GRBLOCKCOUNTER +#define LLVM_CLANG_ANALYSIS_GRBLOCKCOUNTER + +namespace llvm { + class BumpPtrAllocator; +} + +namespace clang { + +class GRBlockCounter { + void* Data; + + GRBlockCounter(void* D) : Data(D) {} + +public: + GRBlockCounter() : Data(0) {} + + unsigned getNumVisited(unsigned BlockID) const; + + class Factory { + void* F; + public: + Factory(llvm::BumpPtrAllocator& Alloc); + ~Factory(); + + GRBlockCounter GetEmptyCounter(); + GRBlockCounter IncrementCount(GRBlockCounter BC, unsigned BlockID); + }; + + friend class Factory; +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h new file mode 100644 index 0000000..0fbdbde --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h @@ -0,0 +1,668 @@ +//==- GRCoreEngine.h - Path-Sensitive Dataflow Engine ------------------*- 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 a generic engine for intraprocedural, path-sensitive, +// dataflow analysis via graph reachability. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_GRENGINE +#define LLVM_CLANG_ANALYSIS_GRENGINE + +#include "clang/AST/Expr.h" +#include "clang/Analysis/PathSensitive/ExplodedGraph.h" +#include "clang/Analysis/PathSensitive/GRWorkList.h" +#include "clang/Analysis/PathSensitive/GRBlockCounter.h" +#include "clang/Analysis/PathSensitive/GRAuditor.h" +#include "llvm/ADT/OwningPtr.h" + +namespace clang { + +class GRStmtNodeBuilderImpl; +class GRBranchNodeBuilderImpl; +class GRIndirectGotoNodeBuilderImpl; +class GRSwitchNodeBuilderImpl; +class GREndPathNodeBuilderImpl; +class GRWorkList; + +//===----------------------------------------------------------------------===// +/// GRCoreEngineImpl - Implements the core logic of the graph-reachability +/// analysis. It traverses the CFG and generates the ExplodedGraph. +/// Program "states" are treated as opaque void pointers. +/// The template class GRCoreEngine (which subclasses GRCoreEngineImpl) +/// provides the matching component to the engine that knows the actual types +/// for states. Note that this engine only dispatches to transfer functions +/// at the statement and block-level. The analyses themselves must implement +/// any transfer function logic and the sub-expression level (if any). +class GRCoreEngineImpl { +protected: + friend class GRStmtNodeBuilderImpl; + friend class GRBranchNodeBuilderImpl; + friend class GRIndirectGotoNodeBuilderImpl; + friend class GRSwitchNodeBuilderImpl; + friend class GREndPathNodeBuilderImpl; + + /// G - The simulation graph. Each node is a (location,state) pair. + llvm::OwningPtr<ExplodedGraphImpl> G; + + /// WList - A set of queued nodes that need to be processed by the + /// worklist algorithm. It is up to the implementation of WList to decide + /// the order that nodes are processed. + GRWorkList* WList; + + /// BCounterFactory - A factory object for created GRBlockCounter objects. + /// These are used to record for key nodes in the ExplodedGraph the + /// number of times different CFGBlocks have been visited along a path. + GRBlockCounter::Factory BCounterFactory; + + void GenerateNode(const ProgramPoint& Loc, const void* State, + ExplodedNodeImpl* Pred); + + /// getInitialState - Gets the void* representing the initial 'state' + /// of the analysis. This is simply a wrapper (implemented + /// in GRCoreEngine) that performs type erasure on the initial + /// state returned by the checker object. + virtual const void* getInitialState() = 0; + + void HandleBlockEdge(const BlockEdge& E, ExplodedNodeImpl* Pred); + void HandleBlockEntrance(const BlockEntrance& E, ExplodedNodeImpl* Pred); + void HandleBlockExit(CFGBlock* B, ExplodedNodeImpl* Pred); + void HandlePostStmt(const PostStmt& S, CFGBlock* B, + unsigned StmtIdx, ExplodedNodeImpl *Pred); + + void HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock* B, + ExplodedNodeImpl* Pred); + + virtual void ProcessEndPath(GREndPathNodeBuilderImpl& Builder) = 0; + + virtual bool ProcessBlockEntrance(CFGBlock* Blk, const void* State, + GRBlockCounter BC) = 0; + + virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilderImpl& Builder) = 0; + + virtual void ProcessBranch(Stmt* Condition, Stmt* Terminator, + GRBranchNodeBuilderImpl& Builder) = 0; + + virtual void ProcessIndirectGoto(GRIndirectGotoNodeBuilderImpl& Builder) = 0; + + virtual void ProcessSwitch(GRSwitchNodeBuilderImpl& Builder) = 0; + +private: + GRCoreEngineImpl(const GRCoreEngineImpl&); // Do not implement. + GRCoreEngineImpl& operator=(const GRCoreEngineImpl&); + +protected: + GRCoreEngineImpl(ExplodedGraphImpl* g, GRWorkList* wl) + : G(g), WList(wl), BCounterFactory(g->getAllocator()) {} + +public: + /// ExecuteWorkList - Run the worklist algorithm for a maximum number of + /// steps. Returns true if there is still simulation state on the worklist. + bool ExecuteWorkList(unsigned Steps); + + virtual ~GRCoreEngineImpl(); + + CFG& getCFG() { return G->getCFG(); } +}; + +class GRStmtNodeBuilderImpl { + GRCoreEngineImpl& Eng; + CFGBlock& B; + const unsigned Idx; + ExplodedNodeImpl* Pred; + ExplodedNodeImpl* LastNode; + + typedef llvm::SmallPtrSet<ExplodedNodeImpl*,5> DeferredTy; + DeferredTy Deferred; + + void GenerateAutoTransition(ExplodedNodeImpl* N); + +public: + GRStmtNodeBuilderImpl(CFGBlock* b, unsigned idx, + ExplodedNodeImpl* N, GRCoreEngineImpl* e); + + ~GRStmtNodeBuilderImpl(); + + ExplodedNodeImpl* getBasePredecessor() const { return Pred; } + + ExplodedNodeImpl* getLastNode() const { + return LastNode ? (LastNode->isSink() ? NULL : LastNode) : NULL; + } + + GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} + + unsigned getCurrentBlockCount() const { + return getBlockCounter().getNumVisited(B.getBlockID()); + } + + ExplodedNodeImpl* + generateNodeImpl(PostStmt PP, const void* State, ExplodedNodeImpl* Pred); + + ExplodedNodeImpl* + generateNodeImpl(Stmt* S, const void* State, ExplodedNodeImpl* Pred, + ProgramPoint::Kind K = ProgramPoint::PostStmtKind, + const void *tag = 0); + + ExplodedNodeImpl* + generateNodeImpl(Stmt* S, const void* State, + ProgramPoint::Kind K = ProgramPoint::PostStmtKind, + const void *tag = 0) { + ExplodedNodeImpl* N = getLastNode(); + assert (N && "Predecessor of new node is infeasible."); + return generateNodeImpl(S, State, N, K, tag); + } + + ExplodedNodeImpl* + generateNodeImpl(Stmt* S, const void* State, const void *tag = 0) { + ExplodedNodeImpl* N = getLastNode(); + assert (N && "Predecessor of new node is infeasible."); + return generateNodeImpl(S, State, N, ProgramPoint::PostStmtKind, tag); + } + + /// getStmt - Return the current block-level expression associated with + /// this builder. + Stmt* getStmt() const { return B[Idx]; } + + /// getBlock - Return the CFGBlock associated with the block-level expression + /// of this builder. + CFGBlock* getBlock() const { return &B; } +}; + + +template<typename STATE> +class GRStmtNodeBuilder { +public: + typedef STATE StateTy; + typedef typename StateTy::ManagerTy StateManagerTy; + typedef ExplodedNode<StateTy> NodeTy; + +private: + GRStmtNodeBuilderImpl& NB; + StateManagerTy& Mgr; + const StateTy* CleanedState; + GRAuditor<StateTy>* Auditor; + +public: + GRStmtNodeBuilder(GRStmtNodeBuilderImpl& nb, StateManagerTy& mgr) : + NB(nb), Mgr(mgr), Auditor(0), PurgingDeadSymbols(false), + BuildSinks(false), HasGeneratedNode(false), + PointKind(ProgramPoint::PostStmtKind), Tag(0) { + + CleanedState = getLastNode()->getState(); + } + + void setAuditor(GRAuditor<StateTy>* A) { + Auditor = A; + } + + NodeTy* getLastNode() const { + return static_cast<NodeTy*>(NB.getLastNode()); + } + + NodeTy* generateNode(PostStmt PP, const StateTy* St, NodeTy* Pred) { + HasGeneratedNode = true; + return static_cast<NodeTy*>(NB.generateNodeImpl(PP, St, Pred)); + } + + NodeTy* generateNode(Stmt* S, const StateTy* St, NodeTy* Pred, + ProgramPoint::Kind K) { + HasGeneratedNode = true; + if (PurgingDeadSymbols) K = ProgramPoint::PostPurgeDeadSymbolsKind; + return static_cast<NodeTy*>(NB.generateNodeImpl(S, St, Pred, K, Tag)); + } + + NodeTy* generateNode(Stmt* S, const StateTy* St, NodeTy* Pred) { + return generateNode(S, St, Pred, PointKind); + } + + NodeTy* generateNode(Stmt* S, const StateTy* St, ProgramPoint::Kind K) { + HasGeneratedNode = true; + if (PurgingDeadSymbols) K = ProgramPoint::PostPurgeDeadSymbolsKind; + return static_cast<NodeTy*>(NB.generateNodeImpl(S, St, K, Tag)); + } + + NodeTy* generateNode(Stmt* S, const StateTy* St) { + return generateNode(S, St, PointKind); + } + + + GRBlockCounter getBlockCounter() const { + return NB.getBlockCounter(); + } + + unsigned getCurrentBlockCount() const { + return NB.getCurrentBlockCount(); + } + + const StateTy* GetState(NodeTy* Pred) const { + if ((ExplodedNodeImpl*) Pred == NB.getBasePredecessor()) + return CleanedState; + else + return Pred->getState(); + } + + void SetCleanedState(const StateTy* St) { + CleanedState = St; + } + + NodeTy* MakeNode(ExplodedNodeSet<StateTy>& Dst, Stmt* S, + NodeTy* Pred, const StateTy* St) { + return MakeNode(Dst, S, Pred, St, PointKind); + } + + NodeTy* MakeNode(ExplodedNodeSet<StateTy>& Dst, Stmt* S, + NodeTy* Pred, const StateTy* St, ProgramPoint::Kind K) { + + const StateTy* PredState = GetState(Pred); + + // If the state hasn't changed, don't generate a new node. + if (!BuildSinks && St == PredState && Auditor == 0) { + Dst.Add(Pred); + return NULL; + } + + NodeTy* N = generateNode(S, St, Pred, K); + + if (N) { + if (BuildSinks) + N->markAsSink(); + else { + if (Auditor && Auditor->Audit(N, Mgr)) + N->markAsSink(); + + Dst.Add(N); + } + } + + return N; + } + + NodeTy* MakeSinkNode(ExplodedNodeSet<StateTy>& Dst, Stmt* S, + NodeTy* Pred, const StateTy* St) { + bool Tmp = BuildSinks; + BuildSinks = true; + NodeTy* N = MakeNode(Dst, S, Pred, St); + BuildSinks = Tmp; + return N; + } + + bool PurgingDeadSymbols; + bool BuildSinks; + bool HasGeneratedNode; + ProgramPoint::Kind PointKind; + const void *Tag; +}; + +class GRBranchNodeBuilderImpl { + GRCoreEngineImpl& Eng; + CFGBlock* Src; + CFGBlock* DstT; + CFGBlock* DstF; + ExplodedNodeImpl* Pred; + + typedef llvm::SmallVector<ExplodedNodeImpl*,3> DeferredTy; + DeferredTy Deferred; + + bool GeneratedTrue; + bool GeneratedFalse; + +public: + GRBranchNodeBuilderImpl(CFGBlock* src, CFGBlock* dstT, CFGBlock* dstF, + ExplodedNodeImpl* pred, GRCoreEngineImpl* e) + : Eng(*e), Src(src), DstT(dstT), DstF(dstF), Pred(pred), + GeneratedTrue(false), GeneratedFalse(false) {} + + ~GRBranchNodeBuilderImpl(); + + ExplodedNodeImpl* getPredecessor() const { return Pred; } + const ExplodedGraphImpl& getGraph() const { return *Eng.G; } + GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} + + ExplodedNodeImpl* generateNodeImpl(const void* State, bool branch); + + CFGBlock* getTargetBlock(bool branch) const { + return branch ? DstT : DstF; + } + + void markInfeasible(bool branch) { + if (branch) GeneratedTrue = true; + else GeneratedFalse = true; + } +}; + +template<typename STATE> +class GRBranchNodeBuilder { + typedef STATE StateTy; + typedef ExplodedGraph<StateTy> GraphTy; + typedef typename GraphTy::NodeTy NodeTy; + + GRBranchNodeBuilderImpl& NB; + +public: + GRBranchNodeBuilder(GRBranchNodeBuilderImpl& nb) : NB(nb) {} + + const GraphTy& getGraph() const { + return static_cast<const GraphTy&>(NB.getGraph()); + } + + NodeTy* getPredecessor() const { + return static_cast<NodeTy*>(NB.getPredecessor()); + } + + const StateTy* getState() const { + return getPredecessor()->getState(); + } + + NodeTy* generateNode(const StateTy* St, bool branch) { + return static_cast<NodeTy*>(NB.generateNodeImpl(St, branch)); + } + + GRBlockCounter getBlockCounter() const { + return NB.getBlockCounter(); + } + + CFGBlock* getTargetBlock(bool branch) const { + return NB.getTargetBlock(branch); + } + + void markInfeasible(bool branch) { + NB.markInfeasible(branch); + } +}; + +class GRIndirectGotoNodeBuilderImpl { + GRCoreEngineImpl& Eng; + CFGBlock* Src; + CFGBlock& DispatchBlock; + Expr* E; + ExplodedNodeImpl* Pred; +public: + GRIndirectGotoNodeBuilderImpl(ExplodedNodeImpl* pred, CFGBlock* src, + Expr* e, CFGBlock* dispatch, + GRCoreEngineImpl* eng) + : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} + + + class Iterator { + CFGBlock::succ_iterator I; + + friend class GRIndirectGotoNodeBuilderImpl; + Iterator(CFGBlock::succ_iterator i) : I(i) {} + public: + + Iterator& operator++() { ++I; return *this; } + bool operator!=(const Iterator& X) const { return I != X.I; } + + LabelStmt* getLabel() const { + return llvm::cast<LabelStmt>((*I)->getLabel()); + } + + CFGBlock* getBlock() const { + return *I; + } + }; + + Iterator begin() { return Iterator(DispatchBlock.succ_begin()); } + Iterator end() { return Iterator(DispatchBlock.succ_end()); } + + ExplodedNodeImpl* generateNodeImpl(const Iterator& I, const void* State, + bool isSink); + + Expr* getTarget() const { return E; } + const void* getState() const { return Pred->State; } +}; + +template<typename STATE> +class GRIndirectGotoNodeBuilder { + typedef STATE StateTy; + typedef ExplodedGraph<StateTy> GraphTy; + typedef typename GraphTy::NodeTy NodeTy; + + GRIndirectGotoNodeBuilderImpl& NB; + +public: + GRIndirectGotoNodeBuilder(GRIndirectGotoNodeBuilderImpl& nb) : NB(nb) {} + + typedef GRIndirectGotoNodeBuilderImpl::Iterator iterator; + + iterator begin() { return NB.begin(); } + iterator end() { return NB.end(); } + + Expr* getTarget() const { return NB.getTarget(); } + + NodeTy* generateNode(const iterator& I, const StateTy* St, bool isSink=false){ + return static_cast<NodeTy*>(NB.generateNodeImpl(I, St, isSink)); + } + + const StateTy* getState() const { + return static_cast<const StateTy*>(NB.getState()); + } +}; + +class GRSwitchNodeBuilderImpl { + GRCoreEngineImpl& Eng; + CFGBlock* Src; + Expr* Condition; + ExplodedNodeImpl* Pred; +public: + GRSwitchNodeBuilderImpl(ExplodedNodeImpl* pred, CFGBlock* src, + Expr* condition, GRCoreEngineImpl* eng) + : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} + + class Iterator { + CFGBlock::succ_reverse_iterator I; + + friend class GRSwitchNodeBuilderImpl; + Iterator(CFGBlock::succ_reverse_iterator i) : I(i) {} + public: + + Iterator& operator++() { ++I; return *this; } + bool operator!=(const Iterator& X) const { return I != X.I; } + + CaseStmt* getCase() const { + return llvm::cast<CaseStmt>((*I)->getLabel()); + } + + CFGBlock* getBlock() const { + return *I; + } + }; + + Iterator begin() { return Iterator(Src->succ_rbegin()+1); } + Iterator end() { return Iterator(Src->succ_rend()); } + + ExplodedNodeImpl* generateCaseStmtNodeImpl(const Iterator& I, + const void* State); + + ExplodedNodeImpl* generateDefaultCaseNodeImpl(const void* State, + bool isSink); + + Expr* getCondition() const { return Condition; } + const void* getState() const { return Pred->State; } +}; + +template<typename STATE> +class GRSwitchNodeBuilder { + typedef STATE StateTy; + typedef ExplodedGraph<StateTy> GraphTy; + typedef typename GraphTy::NodeTy NodeTy; + + GRSwitchNodeBuilderImpl& NB; + +public: + GRSwitchNodeBuilder(GRSwitchNodeBuilderImpl& nb) : NB(nb) {} + + typedef GRSwitchNodeBuilderImpl::Iterator iterator; + + iterator begin() { return NB.begin(); } + iterator end() { return NB.end(); } + + Expr* getCondition() const { return NB.getCondition(); } + + NodeTy* generateCaseStmtNode(const iterator& I, const StateTy* St) { + return static_cast<NodeTy*>(NB.generateCaseStmtNodeImpl(I, St)); + } + + NodeTy* generateDefaultCaseNode(const StateTy* St, bool isSink = false) { + return static_cast<NodeTy*>(NB.generateDefaultCaseNodeImpl(St, isSink)); + } + + const StateTy* getState() const { + return static_cast<const StateTy*>(NB.getState()); + } +}; + + +class GREndPathNodeBuilderImpl { + GRCoreEngineImpl& Eng; + CFGBlock& B; + ExplodedNodeImpl* Pred; + bool HasGeneratedNode; + +public: + GREndPathNodeBuilderImpl(CFGBlock* b, ExplodedNodeImpl* N, + GRCoreEngineImpl* e) + : Eng(*e), B(*b), Pred(N), HasGeneratedNode(false) {} + + ~GREndPathNodeBuilderImpl(); + + ExplodedNodeImpl* getPredecessor() const { return Pred; } + + GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} + + unsigned getCurrentBlockCount() const { + return getBlockCounter().getNumVisited(B.getBlockID()); + } + + ExplodedNodeImpl* generateNodeImpl(const void* State, + const void *tag = 0, + ExplodedNodeImpl *P = 0); + + CFGBlock* getBlock() const { return &B; } +}; + + +template<typename STATE> +class GREndPathNodeBuilder { + typedef STATE StateTy; + typedef ExplodedNode<StateTy> NodeTy; + + GREndPathNodeBuilderImpl& NB; + +public: + GREndPathNodeBuilder(GREndPathNodeBuilderImpl& nb) : NB(nb) {} + + NodeTy* getPredecessor() const { + return static_cast<NodeTy*>(NB.getPredecessor()); + } + + GRBlockCounter getBlockCounter() const { + return NB.getBlockCounter(); + } + + unsigned getCurrentBlockCount() const { + return NB.getCurrentBlockCount(); + } + + const StateTy* getState() const { + return getPredecessor()->getState(); + } + + NodeTy* MakeNode(const StateTy* St, const void *tag = 0) { + return static_cast<NodeTy*>(NB.generateNodeImpl(St, tag)); + } + + NodeTy *generateNode(const StateTy *St, NodeTy *Pred, const void *tag = 0) { + return static_cast<NodeTy*>(NB.generateNodeImpl(St, tag, Pred)); + } +}; + + +template<typename SUBENGINE> +class GRCoreEngine : public GRCoreEngineImpl { +public: + typedef SUBENGINE SubEngineTy; + typedef typename SubEngineTy::StateTy StateTy; + typedef typename StateTy::ManagerTy StateManagerTy; + typedef ExplodedGraph<StateTy> GraphTy; + typedef typename GraphTy::NodeTy NodeTy; + +protected: + SubEngineTy& SubEngine; + + virtual const void* getInitialState() { + return SubEngine.getInitialState(); + } + + virtual void ProcessEndPath(GREndPathNodeBuilderImpl& BuilderImpl) { + GREndPathNodeBuilder<StateTy> Builder(BuilderImpl); + SubEngine.ProcessEndPath(Builder); + } + + virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilderImpl& BuilderImpl) { + GRStmtNodeBuilder<StateTy> Builder(BuilderImpl,SubEngine.getStateManager()); + SubEngine.ProcessStmt(S, Builder); + } + + virtual bool ProcessBlockEntrance(CFGBlock* Blk, const void* State, + GRBlockCounter BC) { + return SubEngine.ProcessBlockEntrance(Blk, + static_cast<const StateTy*>(State), + BC); + } + + virtual void ProcessBranch(Stmt* Condition, Stmt* Terminator, + GRBranchNodeBuilderImpl& BuilderImpl) { + GRBranchNodeBuilder<StateTy> Builder(BuilderImpl); + SubEngine.ProcessBranch(Condition, Terminator, Builder); + } + + virtual void ProcessIndirectGoto(GRIndirectGotoNodeBuilderImpl& BuilderImpl) { + GRIndirectGotoNodeBuilder<StateTy> Builder(BuilderImpl); + SubEngine.ProcessIndirectGoto(Builder); + } + + virtual void ProcessSwitch(GRSwitchNodeBuilderImpl& BuilderImpl) { + GRSwitchNodeBuilder<StateTy> Builder(BuilderImpl); + SubEngine.ProcessSwitch(Builder); + } + +public: + /// Construct a GRCoreEngine object to analyze the provided CFG using + /// a DFS exploration of the exploded graph. + GRCoreEngine(CFG& cfg, Decl& cd, ASTContext& ctx, SubEngineTy& subengine) + : GRCoreEngineImpl(new GraphTy(cfg, cd, ctx), + GRWorkList::MakeBFS()), + SubEngine(subengine) {} + + /// Construct a GRCoreEngine object to analyze the provided CFG and to + /// use the provided worklist object to execute the worklist algorithm. + /// The GRCoreEngine object assumes ownership of 'wlist'. + GRCoreEngine(CFG& cfg, Decl& cd, ASTContext& ctx, GRWorkList* wlist, + SubEngineTy& subengine) + : GRCoreEngineImpl(new GraphTy(cfg, cd, ctx), wlist), + SubEngine(subengine) {} + + virtual ~GRCoreEngine() {} + + /// getGraph - Returns the exploded graph. + GraphTy& getGraph() { + return *static_cast<GraphTy*>(G.get()); + } + + /// takeGraph - Returns the exploded graph. Ownership of the graph is + /// transfered to the caller. + GraphTy* takeGraph() { + return static_cast<GraphTy*>(G.take()); + } +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h new file mode 100644 index 0000000..2068b1b --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -0,0 +1,738 @@ +//===-- GRExprEngine.h - Path-Sensitive Expression-Level Dataflow ---*- 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 a meta-engine for path-sensitive dataflow analysis that +// is built on GRCoreEngine, but provides the boilerplate to execute transfer +// functions and build the ExplodedGraph at the expression level. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_GREXPRENGINE +#define LLVM_CLANG_ANALYSIS_GREXPRENGINE + +#include "clang/Analysis/PathSensitive/GRCoreEngine.h" +#include "clang/Analysis/PathSensitive/GRState.h" +#include "clang/Analysis/PathSensitive/GRSimpleAPICheck.h" +#include "clang/Analysis/PathSensitive/GRTransferFuncs.h" +#include "clang/Analysis/PathSensitive/BugReporter.h" +#include "clang/AST/Type.h" +#include "clang/AST/ExprObjC.h" + +namespace clang { + + class PathDiagnosticClient; + class Diagnostic; + class ObjCForCollectionStmt; + +class GRExprEngine { +public: + typedef GRState StateTy; + typedef ExplodedGraph<StateTy> GraphTy; + typedef GraphTy::NodeTy NodeTy; + + // Builders. + typedef GRStmtNodeBuilder<StateTy> StmtNodeBuilder; + typedef GRBranchNodeBuilder<StateTy> BranchNodeBuilder; + typedef GRIndirectGotoNodeBuilder<StateTy> IndirectGotoNodeBuilder; + typedef GRSwitchNodeBuilder<StateTy> SwitchNodeBuilder; + typedef GREndPathNodeBuilder<StateTy> EndPathNodeBuilder; + typedef ExplodedNodeSet<StateTy> NodeSet; + +protected: + GRCoreEngine<GRExprEngine> CoreEngine; + + /// G - the simulation graph. + GraphTy& G; + + /// Liveness - live-variables information the ValueDecl* and block-level + /// Expr* in the CFG. Used to prune out dead state. + LiveVariables& Liveness; + + /// Builder - The current GRStmtNodeBuilder which is used when building the + /// nodes for a given statement. + StmtNodeBuilder* Builder; + + /// StateMgr - Object that manages the data for all created states. + GRStateManager StateMgr; + + /// SymMgr - Object that manages the symbol information. + SymbolManager& SymMgr; + + /// ValMgr - Object that manages/creates SVals. + ValueManager &ValMgr; + + /// EntryNode - The immediate predecessor node. + NodeTy* EntryNode; + + /// CleanedState - The state for EntryNode "cleaned" of all dead + /// variables and symbols (as determined by a liveness analysis). + const GRState* CleanedState; + + /// CurrentStmt - The current block-level statement. + Stmt* CurrentStmt; + + // Obj-C Class Identifiers. + IdentifierInfo* NSExceptionII; + + // Obj-C Selectors. + Selector* NSExceptionInstanceRaiseSelectors; + Selector RaiseSel; + + llvm::OwningPtr<GRSimpleAPICheck> BatchAuditor; + + /// PurgeDead - Remove dead bindings before processing a statement. + bool PurgeDead; + + /// BR - The BugReporter associated with this engine. It is important that + // this object be placed at the very end of member variables so that its + // destructor is called before the rest of the GRExprEngine is destroyed. + GRBugReporter BR; + + /// EargerlyAssume - A flag indicating how the engine should handle + // expressions such as: 'x = (y != 0)'. When this flag is true then + // the subexpression 'y != 0' will be eagerly assumed to be true or false, + // thus evaluating it to the integers 0 or 1 respectively. The upside + // is that this can increase analysis precision until we have a better way + // to lazily evaluate such logic. The downside is that it eagerly + // bifurcates paths. + const bool EagerlyAssume; + +public: + typedef llvm::SmallPtrSet<NodeTy*,2> ErrorNodes; + typedef llvm::DenseMap<NodeTy*, Expr*> UndefArgsTy; + + /// NilReceiverStructRetExplicit - Nodes in the ExplodedGraph that resulted + /// from [x ...] with 'x' definitely being nil and the result was a 'struct' + // (an undefined value). + ErrorNodes NilReceiverStructRetExplicit; + + /// NilReceiverStructRetImplicit - Nodes in the ExplodedGraph that resulted + /// from [x ...] with 'x' possibly being nil and the result was a 'struct' + // (an undefined value). + ErrorNodes NilReceiverStructRetImplicit; + + /// NilReceiverLargerThanVoidPtrRetExplicit - Nodes in the ExplodedGraph that + /// resulted from [x ...] with 'x' definitely being nil and the result's size + // was larger than sizeof(void *) (an undefined value). + ErrorNodes NilReceiverLargerThanVoidPtrRetExplicit; + + /// NilReceiverLargerThanVoidPtrRetImplicit - Nodes in the ExplodedGraph that + /// resulted from [x ...] with 'x' possibly being nil and the result's size + // was larger than sizeof(void *) (an undefined value). + ErrorNodes NilReceiverLargerThanVoidPtrRetImplicit; + + /// RetsStackAddr - Nodes in the ExplodedGraph that result from returning + /// the address of a stack variable. + ErrorNodes RetsStackAddr; + + /// RetsUndef - Nodes in the ExplodedGraph that result from returning + /// an undefined value. + ErrorNodes RetsUndef; + + /// UndefBranches - Nodes in the ExplodedGraph that result from + /// taking a branch based on an undefined value. + ErrorNodes UndefBranches; + + /// UndefStores - Sinks in the ExplodedGraph that result from + /// making a store to an undefined lvalue. + ErrorNodes UndefStores; + + /// NoReturnCalls - Sinks in the ExplodedGraph that result from + // calling a function with the attribute "noreturn". + ErrorNodes NoReturnCalls; + + /// ImplicitNullDeref - Nodes in the ExplodedGraph that result from + /// taking a dereference on a symbolic pointer that MAY be NULL. + ErrorNodes ImplicitNullDeref; + + /// ExplicitNullDeref - Nodes in the ExplodedGraph that result from + /// taking a dereference on a symbolic pointer that MUST be NULL. + ErrorNodes ExplicitNullDeref; + + /// UnitDeref - Nodes in the ExplodedGraph that result from + /// taking a dereference on an undefined value. + ErrorNodes UndefDeref; + + /// ImplicitBadDivides - Nodes in the ExplodedGraph that result from + /// evaluating a divide or modulo operation where the denominator + /// MAY be zero. + ErrorNodes ImplicitBadDivides; + + /// ExplicitBadDivides - Nodes in the ExplodedGraph that result from + /// evaluating a divide or modulo operation where the denominator + /// MUST be zero or undefined. + ErrorNodes ExplicitBadDivides; + + /// ImplicitBadSizedVLA - Nodes in the ExplodedGraph that result from + /// constructing a zero-sized VLA where the size may be zero. + ErrorNodes ImplicitBadSizedVLA; + + /// ExplicitBadSizedVLA - Nodes in the ExplodedGraph that result from + /// constructing a zero-sized VLA where the size must be zero. + ErrorNodes ExplicitBadSizedVLA; + + /// UndefResults - Nodes in the ExplodedGraph where the operands are defined + /// by the result is not. Excludes divide-by-zero errors. + ErrorNodes UndefResults; + + /// BadCalls - Nodes in the ExplodedGraph resulting from calls to function + /// pointers that are NULL (or other constants) or Undefined. + ErrorNodes BadCalls; + + /// UndefReceiver - Nodes in the ExplodedGraph resulting from message + /// ObjC message expressions where the receiver is undefined (uninitialized). + ErrorNodes UndefReceivers; + + /// UndefArg - Nodes in the ExplodedGraph resulting from calls to functions + /// where a pass-by-value argument has an undefined value. + UndefArgsTy UndefArgs; + + /// MsgExprUndefArgs - Nodes in the ExplodedGraph resulting from + /// message expressions where a pass-by-value argument has an undefined + /// value. + UndefArgsTy MsgExprUndefArgs; + + /// OutOfBoundMemAccesses - Nodes in the ExplodedGraph resulting from + /// out-of-bound memory accesses where the index MAY be out-of-bound. + ErrorNodes ImplicitOOBMemAccesses; + + /// OutOfBoundMemAccesses - Nodes in the ExplodedGraph resulting from + /// out-of-bound memory accesses where the index MUST be out-of-bound. + ErrorNodes ExplicitOOBMemAccesses; + +public: + GRExprEngine(CFG& cfg, Decl& CD, ASTContext& Ctx, LiveVariables& L, + BugReporterData& BRD, + bool purgeDead, bool eagerlyAssume = true, + StoreManagerCreator SMC = CreateBasicStoreManager, + ConstraintManagerCreator CMC = CreateBasicConstraintManager); + + ~GRExprEngine(); + + void ExecuteWorkList(unsigned Steps = 150000) { + CoreEngine.ExecuteWorkList(Steps); + } + + /// getContext - Return the ASTContext associated with this analysis. + ASTContext& getContext() const { return G.getContext(); } + + /// getCFG - Returns the CFG associated with this analysis. + CFG& getCFG() { return G.getCFG(); } + + GRTransferFuncs& getTF() { return *StateMgr.TF; } + + BugReporter& getBugReporter() { return BR; } + + /// setTransferFunctions + void setTransferFunctions(GRTransferFuncs* tf); + + void setTransferFunctions(GRTransferFuncs& tf) { + setTransferFunctions(&tf); + } + + /// ViewGraph - Visualize the ExplodedGraph created by executing the + /// simulation. + void ViewGraph(bool trim = false); + + void ViewGraph(NodeTy** Beg, NodeTy** End); + + /// getLiveness - Returned computed live-variables information for the + /// analyzed function. + const LiveVariables& getLiveness() const { return Liveness; } + LiveVariables& getLiveness() { return Liveness; } + + /// getInitialState - Return the initial state used for the root vertex + /// in the ExplodedGraph. + const GRState* getInitialState(); + + GraphTy& getGraph() { return G; } + const GraphTy& getGraph() const { return G; } + + void RegisterInternalChecks(); + + bool isRetStackAddr(const NodeTy* N) const { + return N->isSink() && RetsStackAddr.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isUndefControlFlow(const NodeTy* N) const { + return N->isSink() && UndefBranches.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isUndefStore(const NodeTy* N) const { + return N->isSink() && UndefStores.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isImplicitNullDeref(const NodeTy* N) const { + return N->isSink() && ImplicitNullDeref.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isExplicitNullDeref(const NodeTy* N) const { + return N->isSink() && ExplicitNullDeref.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isUndefDeref(const NodeTy* N) const { + return N->isSink() && UndefDeref.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isImplicitBadDivide(const NodeTy* N) const { + return N->isSink() && ImplicitBadDivides.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isExplicitBadDivide(const NodeTy* N) const { + return N->isSink() && ExplicitBadDivides.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isNoReturnCall(const NodeTy* N) const { + return N->isSink() && NoReturnCalls.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isUndefResult(const NodeTy* N) const { + return N->isSink() && UndefResults.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isBadCall(const NodeTy* N) const { + return N->isSink() && BadCalls.count(const_cast<NodeTy*>(N)) != 0; + } + + bool isUndefArg(const NodeTy* N) const { + return N->isSink() && + (UndefArgs.find(const_cast<NodeTy*>(N)) != UndefArgs.end() || + MsgExprUndefArgs.find(const_cast<NodeTy*>(N)) != MsgExprUndefArgs.end()); + } + + bool isUndefReceiver(const NodeTy* N) const { + return N->isSink() && UndefReceivers.count(const_cast<NodeTy*>(N)) != 0; + } + + typedef ErrorNodes::iterator ret_stackaddr_iterator; + ret_stackaddr_iterator ret_stackaddr_begin() { return RetsStackAddr.begin(); } + ret_stackaddr_iterator ret_stackaddr_end() { return RetsStackAddr.end(); } + + typedef ErrorNodes::iterator ret_undef_iterator; + ret_undef_iterator ret_undef_begin() { return RetsUndef.begin(); } + ret_undef_iterator ret_undef_end() { return RetsUndef.end(); } + + typedef ErrorNodes::iterator undef_branch_iterator; + undef_branch_iterator undef_branches_begin() { return UndefBranches.begin(); } + undef_branch_iterator undef_branches_end() { return UndefBranches.end(); } + + typedef ErrorNodes::iterator null_deref_iterator; + null_deref_iterator null_derefs_begin() { return ExplicitNullDeref.begin(); } + null_deref_iterator null_derefs_end() { return ExplicitNullDeref.end(); } + + null_deref_iterator implicit_null_derefs_begin() { + return ImplicitNullDeref.begin(); + } + null_deref_iterator implicit_null_derefs_end() { + return ImplicitNullDeref.end(); + } + + typedef ErrorNodes::iterator nil_receiver_struct_ret_iterator; + + nil_receiver_struct_ret_iterator nil_receiver_struct_ret_begin() { + return NilReceiverStructRetExplicit.begin(); + } + + nil_receiver_struct_ret_iterator nil_receiver_struct_ret_end() { + return NilReceiverStructRetExplicit.end(); + } + + typedef ErrorNodes::iterator nil_receiver_larger_than_voidptr_ret_iterator; + + nil_receiver_larger_than_voidptr_ret_iterator + nil_receiver_larger_than_voidptr_ret_begin() { + return NilReceiverLargerThanVoidPtrRetExplicit.begin(); + } + + nil_receiver_larger_than_voidptr_ret_iterator + nil_receiver_larger_than_voidptr_ret_end() { + return NilReceiverLargerThanVoidPtrRetExplicit.end(); + } + + typedef ErrorNodes::iterator undef_deref_iterator; + undef_deref_iterator undef_derefs_begin() { return UndefDeref.begin(); } + undef_deref_iterator undef_derefs_end() { return UndefDeref.end(); } + + typedef ErrorNodes::iterator bad_divide_iterator; + + bad_divide_iterator explicit_bad_divides_begin() { + return ExplicitBadDivides.begin(); + } + + bad_divide_iterator explicit_bad_divides_end() { + return ExplicitBadDivides.end(); + } + + bad_divide_iterator implicit_bad_divides_begin() { + return ImplicitBadDivides.begin(); + } + + bad_divide_iterator implicit_bad_divides_end() { + return ImplicitBadDivides.end(); + } + + typedef ErrorNodes::iterator undef_result_iterator; + undef_result_iterator undef_results_begin() { return UndefResults.begin(); } + undef_result_iterator undef_results_end() { return UndefResults.end(); } + + typedef ErrorNodes::iterator bad_calls_iterator; + bad_calls_iterator bad_calls_begin() { return BadCalls.begin(); } + bad_calls_iterator bad_calls_end() { return BadCalls.end(); } + + typedef UndefArgsTy::iterator undef_arg_iterator; + undef_arg_iterator undef_arg_begin() { return UndefArgs.begin(); } + undef_arg_iterator undef_arg_end() { return UndefArgs.end(); } + + undef_arg_iterator msg_expr_undef_arg_begin() { + return MsgExprUndefArgs.begin(); + } + undef_arg_iterator msg_expr_undef_arg_end() { + return MsgExprUndefArgs.end(); + } + + typedef ErrorNodes::iterator undef_receivers_iterator; + + undef_receivers_iterator undef_receivers_begin() { + return UndefReceivers.begin(); + } + + undef_receivers_iterator undef_receivers_end() { + return UndefReceivers.end(); + } + + typedef ErrorNodes::iterator oob_memacc_iterator; + oob_memacc_iterator implicit_oob_memacc_begin() { + return ImplicitOOBMemAccesses.begin(); + } + oob_memacc_iterator implicit_oob_memacc_end() { + return ImplicitOOBMemAccesses.end(); + } + oob_memacc_iterator explicit_oob_memacc_begin() { + return ExplicitOOBMemAccesses.begin(); + } + oob_memacc_iterator explicit_oob_memacc_end() { + return ExplicitOOBMemAccesses.end(); + } + + void AddCheck(GRSimpleAPICheck* A, Stmt::StmtClass C); + void AddCheck(GRSimpleAPICheck* A); + + /// ProcessStmt - Called by GRCoreEngine. Used to generate new successor + /// nodes by processing the 'effects' of a block-level statement. + void ProcessStmt(Stmt* S, StmtNodeBuilder& builder); + + /// ProcessBlockEntrance - Called by GRCoreEngine when start processing + /// a CFGBlock. This method returns true if the analysis should continue + /// exploring the given path, and false otherwise. + bool ProcessBlockEntrance(CFGBlock* B, const GRState* St, + GRBlockCounter BC); + + /// ProcessBranch - Called by GRCoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a branch condition. + void ProcessBranch(Stmt* Condition, Stmt* Term, BranchNodeBuilder& builder); + + /// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a computed goto jump. + void ProcessIndirectGoto(IndirectGotoNodeBuilder& builder); + + /// ProcessSwitch - Called by GRCoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a switch statement. + void ProcessSwitch(SwitchNodeBuilder& builder); + + /// ProcessEndPath - Called by GRCoreEngine. Used to generate end-of-path + /// nodes when the control reaches the end of a function. + void ProcessEndPath(EndPathNodeBuilder& builder) { + getTF().EvalEndPath(*this, builder); + StateMgr.EndPath(builder.getState()); + } + + GRStateManager& getStateManager() { return StateMgr; } + const GRStateManager& getStateManager() const { return StateMgr; } + + StoreManager& getStoreManager() { return StateMgr.getStoreManager(); } + + ConstraintManager& getConstraintManager() { + return StateMgr.getConstraintManager(); + } + + // FIXME: Remove when we migrate over to just using ValueManager. + BasicValueFactory& getBasicVals() { + return StateMgr.getBasicVals(); + } + const BasicValueFactory& getBasicVals() const { + return StateMgr.getBasicVals(); + } + + ValueManager &getValueManager() { return ValMgr; } + const ValueManager &getValueManager() const { return ValMgr; } + + // FIXME: Remove when we migrate over to just using ValueManager. + SymbolManager& getSymbolManager() { return SymMgr; } + const SymbolManager& getSymbolManager() const { return SymMgr; } + +protected: + + const GRState* GetState(NodeTy* N) { + return N == EntryNode ? CleanedState : N->getState(); + } + +public: + + const GRState* BindExpr(const GRState* St, Expr* Ex, SVal V) { + return StateMgr.BindExpr(St, Ex, V); + } + + const GRState* BindExpr(const GRState* St, const Expr* Ex, SVal V) { + return BindExpr(St, const_cast<Expr*>(Ex), V); + } + +protected: + + const GRState* BindBlkExpr(const GRState* St, Expr* Ex, SVal V) { + return StateMgr.BindExpr(St, Ex, V, true, false); + } + + const GRState* BindLoc(const GRState* St, Loc LV, SVal V) { + return StateMgr.BindLoc(St, LV, V); + } + + SVal GetSVal(const GRState* St, Stmt* Ex) { + return StateMgr.GetSVal(St, Ex); + } + + SVal GetSVal(const GRState* St, const Stmt* Ex) { + return GetSVal(St, const_cast<Stmt*>(Ex)); + } + + SVal GetBlkExprSVal(const GRState* St, Stmt* Ex) { + return StateMgr.GetBlkExprSVal(St, Ex); + } + + SVal GetSVal(const GRState* St, Loc LV, QualType T = QualType()) { + return StateMgr.GetSVal(St, LV, T); + } + + inline NonLoc MakeConstantVal(uint64_t X, Expr* Ex) { + return NonLoc::MakeVal(getBasicVals(), X, Ex->getType()); + } + + /// Assume - Create new state by assuming that a given expression + /// is true or false. + const GRState* Assume(const GRState* St, SVal Cond, bool Assumption, + bool& isFeasible) { + return StateMgr.Assume(St, Cond, Assumption, isFeasible); + } + + const GRState* Assume(const GRState* St, Loc Cond, bool Assumption, + bool& isFeasible) { + return StateMgr.Assume(St, Cond, Assumption, isFeasible); + } + + const GRState* AssumeInBound(const GRState* St, SVal Idx, SVal UpperBound, + bool Assumption, bool& isFeasible) { + return StateMgr.AssumeInBound(St, Idx, UpperBound, Assumption, isFeasible); + } + +public: + NodeTy* MakeNode(NodeSet& Dst, Stmt* S, NodeTy* Pred, const GRState* St, + ProgramPoint::Kind K = ProgramPoint::PostStmtKind, + const void *tag = 0); +protected: + + /// Visit - Transfer function logic for all statements. Dispatches to + /// other functions that handle specific kinds of statements. + void Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst); + + /// VisitLValue - Evaluate the lvalue of the expression. For example, if Ex is + /// a DeclRefExpr, it evaluates to the MemRegionVal which represents its + /// storage location. Note that not all kinds of expressions has lvalue. + void VisitLValue(Expr* Ex, NodeTy* Pred, NodeSet& Dst); + + /// VisitArraySubscriptExpr - Transfer function for array accesses. + void VisitArraySubscriptExpr(ArraySubscriptExpr* Ex, NodeTy* Pred, + NodeSet& Dst, bool asLValue); + + /// VisitAsmStmt - Transfer function logic for inline asm. + void VisitAsmStmt(AsmStmt* A, NodeTy* Pred, NodeSet& Dst); + + void VisitAsmStmtHelperOutputs(AsmStmt* A, + AsmStmt::outputs_iterator I, + AsmStmt::outputs_iterator E, + NodeTy* Pred, NodeSet& Dst); + + void VisitAsmStmtHelperInputs(AsmStmt* A, + AsmStmt::inputs_iterator I, + AsmStmt::inputs_iterator E, + NodeTy* Pred, NodeSet& Dst); + + /// VisitBinaryOperator - Transfer function logic for binary operators. + void VisitBinaryOperator(BinaryOperator* B, NodeTy* Pred, NodeSet& Dst); + + + /// VisitCall - Transfer function for function calls. + void VisitCall(CallExpr* CE, NodeTy* Pred, + CallExpr::arg_iterator AI, CallExpr::arg_iterator AE, + NodeSet& Dst); + void VisitCallRec(CallExpr* CE, NodeTy* Pred, + CallExpr::arg_iterator AI, CallExpr::arg_iterator AE, + NodeSet& Dst, const FunctionProtoType *, + unsigned ParamIdx = 0); + + /// VisitCast - Transfer function logic for all casts (implicit and explicit). + void VisitCast(Expr* CastE, Expr* Ex, NodeTy* Pred, NodeSet& Dst); + + /// VisitCastPointerToInteger - Transfer function (called by VisitCast) that + /// handles pointer to integer casts and array to integer casts. + void VisitCastPointerToInteger(SVal V, const GRState* state, QualType PtrTy, + Expr* CastE, NodeTy* Pred, NodeSet& Dst); + + /// VisitCompoundLiteralExpr - Transfer function logic for compound literals. + void VisitCompoundLiteralExpr(CompoundLiteralExpr* CL, NodeTy* Pred, + NodeSet& Dst, bool asLValue); + + /// VisitDeclRefExpr - Transfer function logic for DeclRefExprs. + void VisitDeclRefExpr(DeclRefExpr* DR, NodeTy* Pred, NodeSet& Dst, + bool asLValue); + + /// VisitDeclStmt - Transfer function logic for DeclStmts. + void VisitDeclStmt(DeclStmt* DS, NodeTy* Pred, NodeSet& Dst); + + /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose + void VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R, NodeTy* Pred, NodeSet& Dst); + + void VisitInitListExpr(InitListExpr* E, NodeTy* Pred, NodeSet& Dst); + + /// VisitLogicalExpr - Transfer function logic for '&&', '||' + void VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred, NodeSet& Dst); + + /// VisitMemberExpr - Transfer function for member expressions. + void VisitMemberExpr(MemberExpr* M, NodeTy* Pred, NodeSet& Dst,bool asLValue); + + /// VisitObjCIvarRefExpr - Transfer function logic for ObjCIvarRefExprs. + void VisitObjCIvarRefExpr(ObjCIvarRefExpr* DR, NodeTy* Pred, NodeSet& Dst, + bool asLValue); + + /// VisitObjCForCollectionStmt - Transfer function logic for + /// ObjCForCollectionStmt. + void VisitObjCForCollectionStmt(ObjCForCollectionStmt* S, NodeTy* Pred, + NodeSet& Dst); + + void VisitObjCForCollectionStmtAux(ObjCForCollectionStmt* S, NodeTy* Pred, + NodeSet& Dst, SVal ElementV); + + /// VisitObjCMessageExpr - Transfer function for ObjC message expressions. + void VisitObjCMessageExpr(ObjCMessageExpr* ME, NodeTy* Pred, NodeSet& Dst); + + void VisitObjCMessageExprArgHelper(ObjCMessageExpr* ME, + ObjCMessageExpr::arg_iterator I, + ObjCMessageExpr::arg_iterator E, + NodeTy* Pred, NodeSet& Dst); + + void VisitObjCMessageExprDispatchHelper(ObjCMessageExpr* ME, NodeTy* Pred, + NodeSet& Dst); + + /// VisitReturnStmt - Transfer function logic for return statements. + void VisitReturnStmt(ReturnStmt* R, NodeTy* Pred, NodeSet& Dst); + + /// VisitSizeOfAlignOfExpr - Transfer function for sizeof. + void VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr* Ex, NodeTy* Pred, + NodeSet& Dst); + + /// VisitUnaryOperator - Transfer function logic for unary operators. + void VisitUnaryOperator(UnaryOperator* B, NodeTy* Pred, NodeSet& Dst, + bool asLValue); + + const GRState* CheckDivideZero(Expr* Ex, const GRState* St, NodeTy* Pred, + SVal Denom); + + /// EvalEagerlyAssume - Given the nodes in 'Src', eagerly assume symbolic + /// expressions of the form 'x != 0' and generate new nodes (stored in Dst) + /// with those assumptions. + void EvalEagerlyAssume(NodeSet& Dst, NodeSet& Src, Expr *Ex); + + SVal EvalCast(SVal X, QualType CastT) { + if (X.isUnknownOrUndef()) + return X; + + if (isa<Loc>(X)) + return getTF().EvalCast(*this, cast<Loc>(X), CastT); + else + return getTF().EvalCast(*this, cast<NonLoc>(X), CastT); + } + + SVal EvalMinus(UnaryOperator* U, SVal X) { + return X.isValid() ? getTF().EvalMinus(*this, U, cast<NonLoc>(X)) : X; + } + + SVal EvalComplement(SVal X) { + return X.isValid() ? getTF().EvalComplement(*this, cast<NonLoc>(X)) : X; + } + +public: + + SVal EvalBinOp(BinaryOperator::Opcode Op, NonLoc L, NonLoc R, QualType T) { + return R.isValid() ? getTF().DetermEvalBinOpNN(*this, Op, L, R, T) + : R; + } + + SVal EvalBinOp(BinaryOperator::Opcode Op, NonLoc L, SVal R, QualType T) { + return R.isValid() ? getTF().DetermEvalBinOpNN(*this, Op, L, + cast<NonLoc>(R), T) : R; + } + + void EvalBinOp(ExplodedNodeSet<GRState>& Dst, Expr* Ex, + BinaryOperator::Opcode Op, NonLoc L, NonLoc R, + ExplodedNode<GRState>* Pred, QualType T); + + void EvalBinOp(GRStateSet& OStates, const GRState* St, Expr* Ex, + BinaryOperator::Opcode Op, NonLoc L, NonLoc R, QualType T); + + SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op, SVal L,SVal R, + QualType T); + +protected: + + void EvalCall(NodeSet& Dst, CallExpr* CE, SVal L, NodeTy* Pred); + + void EvalObjCMessageExpr(NodeSet& Dst, ObjCMessageExpr* ME, NodeTy* Pred) { + assert (Builder && "GRStmtNodeBuilder must be defined."); + getTF().EvalObjCMessageExpr(Dst, *this, *Builder, ME, Pred); + } + + void EvalReturn(NodeSet& Dst, ReturnStmt* s, NodeTy* Pred); + + const GRState* MarkBranch(const GRState* St, Stmt* Terminator, + bool branchTaken); + + /// EvalBind - Handle the semantics of binding a value to a specific location. + /// This method is used by EvalStore, VisitDeclStmt, and others. + void EvalBind(NodeSet& Dst, Expr* Ex, NodeTy* Pred, + const GRState* St, SVal location, SVal Val); + +public: + void EvalLoad(NodeSet& Dst, Expr* Ex, NodeTy* Pred, + const GRState* St, SVal location, const void *tag = 0); + + NodeTy* EvalLocation(Stmt* Ex, NodeTy* Pred, + const GRState* St, SVal location, + const void *tag = 0); + + + void EvalStore(NodeSet& Dst, Expr* E, NodeTy* Pred, const GRState* St, + SVal TargetLV, SVal Val, const void *tag = 0); + + void EvalStore(NodeSet& Dst, Expr* E, Expr* StoreE, NodeTy* Pred, + const GRState* St, SVal TargetLV, SVal Val, + const void *tag = 0); + +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRExprEngineBuilders.h b/include/clang/Analysis/PathSensitive/GRExprEngineBuilders.h new file mode 100644 index 0000000..6c23745 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRExprEngineBuilders.h @@ -0,0 +1,101 @@ +//===-- GRExprEngineBuilders.h - "Builder" classes for GRExprEngine -*- 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 smart builder "references" which are used to marshal +// builders between GRExprEngine objects and their related components. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_GREXPRENGINE_BUILDERS +#define LLVM_CLANG_ANALYSIS_GREXPRENGINE_BUILDERS +#include "clang/Analysis/PathSensitive/GRExprEngine.h" + +namespace clang { + + +// SaveAndRestore - A utility class that uses RAII to save and restore +// the value of a variable. +template<typename T> +struct SaveAndRestore { + SaveAndRestore(T& x) : X(x), old_value(x) {} + ~SaveAndRestore() { X = old_value; } + T get() { return old_value; } +private: + T& X; + T old_value; +}; + +// SaveOr - Similar to SaveAndRestore. Operates only on bools; the old +// value of a variable is saved, and during the dstor the old value is +// or'ed with the new value. +struct SaveOr { + SaveOr(bool& x) : X(x), old_value(x) { x = false; } + ~SaveOr() { X |= old_value; } +private: + bool& X; + const bool old_value; +}; + +class GRStmtNodeBuilderRef { + GRExprEngine::NodeSet &Dst; + GRExprEngine::StmtNodeBuilder &B; + GRExprEngine& Eng; + GRExprEngine::NodeTy* Pred; + const GRState* state; + const Stmt* stmt; + const unsigned OldSize; + const bool AutoCreateNode; + SaveAndRestore<bool> OldSink; + SaveAndRestore<const void*> OldTag; + SaveOr OldHasGen; + +private: + friend class GRExprEngine; + + GRStmtNodeBuilderRef(); // do not implement + void operator=(const GRStmtNodeBuilderRef&); // do not implement + + GRStmtNodeBuilderRef(GRExprEngine::NodeSet &dst, + GRExprEngine::StmtNodeBuilder &builder, + GRExprEngine& eng, + GRExprEngine::NodeTy* pred, + const GRState *st, + const Stmt* s, bool auto_create_node) + : Dst(dst), B(builder), Eng(eng), Pred(pred), + state(st), stmt(s), OldSize(Dst.size()), AutoCreateNode(auto_create_node), + OldSink(B.BuildSinks), OldTag(B.Tag), OldHasGen(B.HasGeneratedNode) {} + +public: + + ~GRStmtNodeBuilderRef() { + // Handle the case where no nodes where generated. Auto-generate that + // contains the updated state if we aren't generating sinks. + if (!B.BuildSinks && Dst.size() == OldSize && !B.HasGeneratedNode) { + if (AutoCreateNode) + B.MakeNode(Dst, const_cast<Stmt*>(stmt), Pred, state); + else + Dst.Add(Pred); + } + } + + GRStateRef getState() { + return GRStateRef(state, Eng.getStateManager()); + } + + GRStateManager& getStateManager() { + return Eng.getStateManager(); + } + + GRExprEngine::NodeTy* MakeNode(const GRState* state) { + return B.MakeNode(Dst, const_cast<Stmt*>(stmt), Pred, state); + } +}; + +} // end clang namespace +#endif diff --git a/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h b/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h new file mode 100644 index 0000000..e54b31d --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h @@ -0,0 +1,40 @@ +// GRCheckAPI.h - Simple API checks based on GRAuditor ------------*- 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 the interface for building simple, path-sensitive checks +// that are stateless and only emit warnings at errors that occur at +// CallExpr or ObjCMessageExpr. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_GRAPICHECKS +#define LLVM_CLANG_ANALYSIS_GRAPICHECKS + +#include "clang/Analysis/PathSensitive/GRAuditor.h" +#include "clang/Analysis/PathSensitive/GRState.h" + +namespace clang { + +class Diagnostic; +class BugReporter; +class ASTContext; +class GRExprEngine; +class PathDiagnosticClient; +template <typename T> class ExplodedGraph; + + +class GRSimpleAPICheck : public GRAuditor<GRState> { +public: + GRSimpleAPICheck() {} + virtual ~GRSimpleAPICheck() {} +}; + +} // end namespace clang + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRState.h b/include/clang/Analysis/PathSensitive/GRState.h new file mode 100644 index 0000000..d61feea --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRState.h @@ -0,0 +1,820 @@ +//== GRState*h - Path-Sens. "State" for tracking valuues -----*- 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 SymbolRef, ExprBindKey, and GRState* +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_VALUESTATE_H +#define LLVM_CLANG_ANALYSIS_VALUESTATE_H + +// FIXME: Reduce the number of includes. + +#include "clang/Analysis/PathSensitive/Environment.h" +#include "clang/Analysis/PathSensitive/Store.h" +#include "clang/Analysis/PathSensitive/ConstraintManager.h" +#include "clang/Analysis/PathSensitive/ValueManager.h" +#include "clang/Analysis/PathSensitive/GRCoreEngine.h" +#include "clang/AST/Expr.h" +#include "clang/AST/Decl.h" +#include "clang/AST/ASTContext.h" +#include "clang/Analysis/Analyses/LiveVariables.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/ImmutableMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Streams.h" + +#include <functional> + +namespace clang { + +class GRStateManager; +class GRTransferFuncs; + +typedef ConstraintManager* (*ConstraintManagerCreator)(GRStateManager&); +typedef StoreManager* (*StoreManagerCreator)(GRStateManager&); + +//===----------------------------------------------------------------------===// +// GRStateTrait - Traits used by the Generic Data Map of a GRState. +//===----------------------------------------------------------------------===// + +template <typename T> struct GRStatePartialTrait; + +template <typename T> struct GRStateTrait { + typedef typename T::data_type data_type; + static inline void* GDMIndex() { return &T::TagInt; } + static inline void* MakeVoidPtr(data_type D) { return (void*) D; } + static inline data_type MakeData(void* const* P) { + return P ? (data_type) *P : (data_type) 0; + } +}; + +//===----------------------------------------------------------------------===// +// GRState- An ImmutableMap type Stmt*/Decl*/Symbols to SVals. +//===----------------------------------------------------------------------===// + +/// GRState - This class encapsulates the actual data values for +/// for a "state" in our symbolic value tracking. It is intended to be +/// used as a functional object; that is once it is created and made +/// "persistent" in a FoldingSet its values will never change. +class GRState : public llvm::FoldingSetNode { +public: + // Typedefs. + typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; + typedef llvm::ImmutableMap<void*, void*> GenericDataMap; + + typedef GRStateManager ManagerTy; + +private: + void operator=(const GRState& R) const; + + friend class GRStateManager; + + Environment Env; + Store St; + + // FIXME: Make these private. +public: + GenericDataMap GDM; + +public: + + /// This ctor is used when creating the first GRState object. + GRState(const Environment& env, Store st, GenericDataMap gdm) + : Env(env), + St(st), + GDM(gdm) {} + + /// Copy ctor - We must explicitly define this or else the "Next" ptr + /// in FoldingSetNode will also get copied. + GRState(const GRState& RHS) + : llvm::FoldingSetNode(), + Env(RHS.Env), + St(RHS.St), + GDM(RHS.GDM) {} + + /// getEnvironment - Return the environment associated with this state. + /// The environment is the mapping from expressions to values. + const Environment& getEnvironment() const { return Env; } + + /// getStore - Return the store associated with this state. The store + /// is a mapping from locations to values. + Store getStore() const { return St; } + + /// getGDM - Return the generic data map associated with this state. + GenericDataMap getGDM() const { return GDM; } + + /// Profile - Profile the contents of a GRState object for use + /// in a FoldingSet. + static void Profile(llvm::FoldingSetNodeID& ID, const GRState* V) { + V->Env.Profile(ID); + ID.AddPointer(V->St); + V->GDM.Profile(ID); + } + + /// Profile - Used to profile the contents of this object for inclusion + /// in a FoldingSet. + void Profile(llvm::FoldingSetNodeID& ID) const { + Profile(ID, this); + } + + SVal LookupExpr(Expr* E) const { + return Env.LookupExpr(E); + } + + // Iterators. + typedef Environment::seb_iterator seb_iterator; + seb_iterator seb_begin() const { return Env.seb_begin(); } + seb_iterator seb_end() const { return Env.beb_end(); } + + typedef Environment::beb_iterator beb_iterator; + beb_iterator beb_begin() const { return Env.beb_begin(); } + beb_iterator beb_end() const { return Env.beb_end(); } + + // Trait based GDM dispatch. + void* const* FindGDM(void* K) const; + + template <typename T> + typename GRStateTrait<T>::data_type + get() const { + return GRStateTrait<T>::MakeData(FindGDM(GRStateTrait<T>::GDMIndex())); + } + + template<typename T> + typename GRStateTrait<T>::lookup_type + get(typename GRStateTrait<T>::key_type key) const { + void* const* d = FindGDM(GRStateTrait<T>::GDMIndex()); + return GRStateTrait<T>::Lookup(GRStateTrait<T>::MakeData(d), key); + } + + template<typename T> + bool contains(typename GRStateTrait<T>::key_type key) const { + void* const* d = FindGDM(GRStateTrait<T>::GDMIndex()); + return GRStateTrait<T>::Contains(GRStateTrait<T>::MakeData(d), key); + } + + // State pretty-printing. + class Printer { + public: + virtual ~Printer() {} + virtual void Print(std::ostream& Out, const GRState* state, + const char* nl, const char* sep) = 0; + }; + + void print(std::ostream& Out, StoreManager& StoreMgr, + ConstraintManager& ConstraintMgr, + Printer **Beg = 0, Printer **End = 0, + const char* nl = "\n", const char *sep = "") const; + + // Tags used for the Generic Data Map. + struct NullDerefTag { + static int TagInt; + typedef const SVal* data_type; + }; +}; + +template<> struct GRTrait<GRState*> { + static inline void* toPtr(GRState* St) { return (void*) St; } + static inline GRState* toState(void* P) { return (GRState*) P; } + static inline void Profile(llvm::FoldingSetNodeID& profile, GRState* St) { + // At this point states have already been uniqued. Just + // add the pointer. + profile.AddPointer(St); + } +}; + + +class GRStateSet { + typedef llvm::SmallPtrSet<const GRState*,5> ImplTy; + ImplTy Impl; +public: + GRStateSet() {} + + inline void Add(const GRState* St) { + Impl.insert(St); + } + + typedef ImplTy::const_iterator iterator; + + inline unsigned size() const { return Impl.size(); } + inline bool empty() const { return Impl.empty(); } + + inline iterator begin() const { return Impl.begin(); } + inline iterator end() const { return Impl.end(); } + + class AutoPopulate { + GRStateSet& S; + unsigned StartSize; + const GRState* St; + public: + AutoPopulate(GRStateSet& s, const GRState* st) + : S(s), StartSize(S.size()), St(st) {} + + ~AutoPopulate() { + if (StartSize == S.size()) + S.Add(St); + } + }; +}; + +//===----------------------------------------------------------------------===// +// GRStateManager - Factory object for GRStates. +//===----------------------------------------------------------------------===// + +class GRStateRef; + +class GRStateManager { + friend class GRExprEngine; + friend class GRStateRef; + +private: + EnvironmentManager EnvMgr; + llvm::OwningPtr<StoreManager> StoreMgr; + llvm::OwningPtr<ConstraintManager> ConstraintMgr; + GRState::IntSetTy::Factory ISetFactory; + + GRState::GenericDataMap::Factory GDMFactory; + + typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy; + GDMContextsTy GDMContexts; + + /// Printers - A set of printer objects used for pretty-printing a GRState. + /// GRStateManager owns these objects. + std::vector<GRState::Printer*> Printers; + + /// StateSet - FoldingSet containing all the states created for analyzing + /// a particular function. This is used to unique states. + llvm::FoldingSet<GRState> StateSet; + + /// ValueMgr - Object that manages the data for all created SVals. + ValueManager ValueMgr; + + /// Alloc - A BumpPtrAllocator to allocate states. + llvm::BumpPtrAllocator& Alloc; + + /// CurrentStmt - The block-level statement currently being visited. This + /// is set by GRExprEngine. + Stmt* CurrentStmt; + + /// cfg - The CFG for the analyzed function/method. + CFG& cfg; + + /// codedecl - The Decl representing the function/method being analyzed. + const Decl& codedecl; + + /// TF - Object that represents a bundle of transfer functions + /// for manipulating and creating SVals. + GRTransferFuncs* TF; + + /// Liveness - live-variables information of the ValueDecl* and block-level + /// Expr* in the CFG. Used to get initial store and prune out dead state. + LiveVariables& Liveness; + +private: + + Environment RemoveBlkExpr(const Environment& Env, Expr* E) { + return EnvMgr.RemoveBlkExpr(Env, E); + } + + // FIXME: Remove when we do lazy initializaton of variable bindings. +// const GRState* BindVar(const GRState* St, VarDecl* D, SVal V) { +// return SetSVal(St, getLoc(D), V); +// } + +public: + + GRStateManager(ASTContext& Ctx, + StoreManagerCreator CreateStoreManager, + ConstraintManagerCreator CreateConstraintManager, + llvm::BumpPtrAllocator& alloc, CFG& c, + const Decl& cd, LiveVariables& L) + : EnvMgr(alloc), + ISetFactory(alloc), + GDMFactory(alloc), + ValueMgr(alloc, Ctx), + Alloc(alloc), + cfg(c), + codedecl(cd), + Liveness(L) { + StoreMgr.reset((*CreateStoreManager)(*this)); + ConstraintMgr.reset((*CreateConstraintManager)(*this)); + } + + ~GRStateManager(); + + const GRState* getInitialState(); + + ASTContext &getContext() { return ValueMgr.getContext(); } + const ASTContext &getContext() const { return ValueMgr.getContext(); } + + const Decl &getCodeDecl() { return codedecl; } + GRTransferFuncs& getTransferFuncs() { return *TF; } + + BasicValueFactory &getBasicVals() { + return ValueMgr.getBasicValueFactory(); + } + const BasicValueFactory& getBasicVals() const { + return ValueMgr.getBasicValueFactory(); + } + + SymbolManager &getSymbolManager() { + return ValueMgr.getSymbolManager(); + } + const SymbolManager &getSymbolManager() const { + return ValueMgr.getSymbolManager(); + } + + ValueManager &getValueManager() { return ValueMgr; } + const ValueManager &getValueManager() const { return ValueMgr; } + + LiveVariables& getLiveVariables() { return Liveness; } + llvm::BumpPtrAllocator& getAllocator() { return Alloc; } + + MemRegionManager& getRegionManager() { + return ValueMgr.getRegionManager(); + } + const MemRegionManager& getRegionManager() const { + return ValueMgr.getRegionManager(); + } + + StoreManager& getStoreManager() { return *StoreMgr; } + ConstraintManager& getConstraintManager() { return *ConstraintMgr; } + + const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal IVal) { + // Store manager should return a persistent state. + return StoreMgr->BindDecl(St, VD, IVal); + } + + const GRState* BindDeclWithNoInit(const GRState* St, const VarDecl* VD) { + // Store manager should return a persistent state. + return StoreMgr->BindDeclWithNoInit(St, VD); + } + + /// BindCompoundLiteral - Return the state that has the bindings currently + /// in 'state' plus the bindings for the CompoundLiteral. 'R' is the region + /// for the compound literal and 'BegInit' and 'EndInit' represent an + /// array of initializer values. + const GRState* BindCompoundLiteral(const GRState* St, + const CompoundLiteralExpr* CL, SVal V) { + return StoreMgr->BindCompoundLiteral(St, CL, V); + } + + const GRState* RemoveDeadBindings(const GRState* St, Stmt* Loc, + SymbolReaper& SymReaper); + + const GRState* RemoveSubExprBindings(const GRState* St) { + GRState NewSt = *St; + NewSt.Env = EnvMgr.RemoveSubExprBindings(NewSt.Env); + return getPersistentState(NewSt); + } + + + // Utility methods for getting regions. + + VarRegion* getRegion(const VarDecl* D) { + return getRegionManager().getVarRegion(D); + } + + const MemRegion* getSelfRegion(const GRState* state) { + return StoreMgr->getSelfRegion(state->getStore()); + } + + // Get the lvalue for a variable reference. + SVal GetLValue(const GRState* St, const VarDecl* D) { + return StoreMgr->getLValueVar(St, D); + } + + // Get the lvalue for a StringLiteral. + SVal GetLValue(const GRState* St, const StringLiteral* E) { + return StoreMgr->getLValueString(St, E); + } + + SVal GetLValue(const GRState* St, const CompoundLiteralExpr* CL) { + return StoreMgr->getLValueCompoundLiteral(St, CL); + } + + // Get the lvalue for an ivar reference. + SVal GetLValue(const GRState* St, const ObjCIvarDecl* D, SVal Base) { + return StoreMgr->getLValueIvar(St, D, Base); + } + + // Get the lvalue for a field reference. + SVal GetLValue(const GRState* St, SVal Base, const FieldDecl* D) { + return StoreMgr->getLValueField(St, Base, D); + } + + // Get the lvalue for an array index. + SVal GetLValue(const GRState* St, QualType ElementType, SVal Base, SVal Idx) { + return StoreMgr->getLValueElement(St, ElementType, Base, Idx); + } + + // Methods that query & manipulate the Environment. + + SVal GetSVal(const GRState* St, Stmt* Ex) { + return St->getEnvironment().GetSVal(Ex, getBasicVals()); + } + + SVal GetSValAsScalarOrLoc(const GRState* state, const Stmt *S) { + if (const Expr *Ex = dyn_cast<Expr>(S)) { + QualType T = Ex->getType(); + if (Loc::IsLocType(T) || T->isIntegerType()) + return GetSVal(state, S); + } + + return UnknownVal(); + } + + + SVal GetSVal(const GRState* St, const Stmt* Ex) { + return St->getEnvironment().GetSVal(const_cast<Stmt*>(Ex), getBasicVals()); + } + + SVal GetBlkExprSVal(const GRState* St, Stmt* Ex) { + return St->getEnvironment().GetBlkExprSVal(Ex, getBasicVals()); + } + + + + const GRState* BindExpr(const GRState* St, Stmt* Ex, SVal V, + bool isBlkExpr, bool Invalidate) { + + const Environment& OldEnv = St->getEnvironment(); + Environment NewEnv = EnvMgr.BindExpr(OldEnv, Ex, V, isBlkExpr, Invalidate); + + if (NewEnv == OldEnv) + return St; + + GRState NewSt = *St; + NewSt.Env = NewEnv; + return getPersistentState(NewSt); + } + + const GRState* BindExpr(const GRState* St, Stmt* Ex, SVal V, + bool Invalidate = true) { + + bool isBlkExpr = false; + + if (Ex == CurrentStmt) { + // FIXME: Should this just be an assertion? When would we want to set + // the value of a block-level expression if it wasn't CurrentStmt? + isBlkExpr = cfg.isBlkExpr(Ex); + + if (!isBlkExpr) + return St; + } + + return BindExpr(St, Ex, V, isBlkExpr, Invalidate); + } + + SVal ArrayToPointer(Loc Array) { + return StoreMgr->ArrayToPointer(Array); + } + + // Methods that manipulate the GDM. + const GRState* addGDM(const GRState* St, void* Key, void* Data); + + // Methods that query or create regions. + bool hasStackStorage(const MemRegion* R) { + return getRegionManager().hasStackStorage(R); + } + + // Methods that query & manipulate the Store. + + void iterBindings(const GRState* state, StoreManager::BindingsHandler& F) { + StoreMgr->iterBindings(state->getStore(), F); + } + + + SVal GetSVal(const GRState* state, Loc LV, QualType T = QualType()) { + return StoreMgr->Retrieve(state, LV, T); + } + + SVal GetSVal(const GRState* state, const MemRegion* R) { + return StoreMgr->Retrieve(state, loc::MemRegionVal(R)); + } + + SVal GetSValAsScalarOrLoc(const GRState* state, const MemRegion *R) { + // We only want to do fetches from regions that we can actually bind + // values. For example, SymbolicRegions of type 'id<...>' cannot + // have direct bindings (but their can be bindings on their subregions). + if (!R->isBoundable(getContext())) + return UnknownVal(); + + if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) { + QualType T = TR->getValueType(getContext()); + if (Loc::IsLocType(T) || T->isIntegerType()) + return GetSVal(state, R); + } + + return UnknownVal(); + } + + const GRState* BindLoc(const GRState* St, Loc LV, SVal V) { + return StoreMgr->Bind(St, LV, V); + } + + void Unbind(GRState& St, Loc LV) { + St.St = StoreMgr->Remove(St.St, LV); + } + + const GRState* Unbind(const GRState* St, Loc LV); + + const GRState* getPersistentState(GRState& Impl); + + // MakeStateWithStore - get a persistent state with the new store. + const GRState* MakeStateWithStore(const GRState* St, Store store); + + bool isEqual(const GRState* state, Expr* Ex, const llvm::APSInt& V); + bool isEqual(const GRState* state, Expr* Ex, uint64_t); + + + //==---------------------------------------------------------------------==// + // Generic Data Map methods. + //==---------------------------------------------------------------------==// + // + // GRStateManager and GRState support a "generic data map" that allows + // different clients of GRState objects to embed arbitrary data within a + // GRState object. The generic data map is essentially an immutable map + // from a "tag" (that acts as the "key" for a client) and opaque values. + // Tags/keys and values are simply void* values. The typical way that clients + // generate unique tags are by taking the address of a static variable. + // Clients are responsible for ensuring that data values referred to by a + // the data pointer are immutable (and thus are essentially purely functional + // data). + // + // The templated methods below use the GRStateTrait<T> class + // to resolve keys into the GDM and to return data values to clients. + // + + // Trait based GDM dispatch. + template <typename T> + const GRState* set(const GRState* st, typename GRStateTrait<T>::data_type D) { + return addGDM(st, GRStateTrait<T>::GDMIndex(), + GRStateTrait<T>::MakeVoidPtr(D)); + } + + template<typename T> + const GRState* set(const GRState* st, + typename GRStateTrait<T>::key_type K, + typename GRStateTrait<T>::value_type V, + typename GRStateTrait<T>::context_type C) { + + return addGDM(st, GRStateTrait<T>::GDMIndex(), + GRStateTrait<T>::MakeVoidPtr(GRStateTrait<T>::Set(st->get<T>(), K, V, C))); + } + + template <typename T> + const GRState* add(const GRState* st, + typename GRStateTrait<T>::key_type K, + typename GRStateTrait<T>::context_type C) { + return addGDM(st, GRStateTrait<T>::GDMIndex(), + GRStateTrait<T>::MakeVoidPtr(GRStateTrait<T>::Add(st->get<T>(), K, C))); + } + + template <typename T> + const GRState* remove(const GRState* st, + typename GRStateTrait<T>::key_type K, + typename GRStateTrait<T>::context_type C) { + + return addGDM(st, GRStateTrait<T>::GDMIndex(), + GRStateTrait<T>::MakeVoidPtr(GRStateTrait<T>::Remove(st->get<T>(), K, C))); + } + + + void* FindGDMContext(void* index, + void* (*CreateContext)(llvm::BumpPtrAllocator&), + void (*DeleteContext)(void*)); + + template <typename T> + typename GRStateTrait<T>::context_type get_context() { + void* p = FindGDMContext(GRStateTrait<T>::GDMIndex(), + GRStateTrait<T>::CreateContext, + GRStateTrait<T>::DeleteContext); + + return GRStateTrait<T>::MakeContext(p); + } + + //==---------------------------------------------------------------------==// + // Constraints on values. + //==---------------------------------------------------------------------==// + // + // Each GRState records constraints on symbolic values. These constraints + // are managed using the ConstraintManager associated with a GRStateManager. + // As constraints gradually accrue on symbolic values, added constraints + // may conflict and indicate that a state is infeasible (as no real values + // could satisfy all the constraints). This is the principal mechanism + // for modeling path-sensitivity in GRExprEngine/GRState. + // + // Various "Assume" methods form the interface for adding constraints to + // symbolic values. A call to "Assume" indicates an assumption being placed + // on one or symbolic values. Assume methods take the following inputs: + // + // (1) A GRState object representing the current state. + // + // (2) The assumed constraint (which is specific to a given "Assume" method). + // + // (3) A binary value "Assumption" that indicates whether the constraint is + // assumed to be true or false. + // + // The output of "Assume" are two values: + // + // (a) "isFeasible" is set to true or false to indicate whether or not + // the assumption is feasible. + // + // (b) A new GRState object with the added constraints. + // + // FIXME: (a) should probably disappear since it is redundant with (b). + // (i.e., (b) could just be set to NULL). + // + + const GRState* Assume(const GRState* St, SVal Cond, bool Assumption, + bool& isFeasible) { + const GRState *state = + ConstraintMgr->Assume(St, Cond, Assumption, isFeasible); + assert(!isFeasible || state); + return isFeasible ? state : NULL; + } + + const GRState* AssumeInBound(const GRState* St, SVal Idx, SVal UpperBound, + bool Assumption, bool& isFeasible) { + const GRState *state = + ConstraintMgr->AssumeInBound(St, Idx, UpperBound, Assumption, + isFeasible); + assert(!isFeasible || state); + return isFeasible ? state : NULL; + } + + const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) { + return ConstraintMgr->getSymVal(St, sym); + } + + void EndPath(const GRState* St) { + ConstraintMgr->EndPath(St); + } + + bool scanReachableSymbols(SVal val, const GRState* state, + SymbolVisitor& visitor); +}; + +//===----------------------------------------------------------------------===// +// GRStateRef - A "fat" reference to GRState that also bundles GRStateManager. +//===----------------------------------------------------------------------===// + +class GRStateRef { + const GRState* St; + GRStateManager* Mgr; +public: + GRStateRef(const GRState* st, GRStateManager& mgr) : St(st), Mgr(&mgr) {} + + const GRState* getState() const { return St; } + operator const GRState*() const { return St; } + GRStateManager& getManager() const { return *Mgr; } + + SVal GetSVal(Expr* Ex) { + return Mgr->GetSVal(St, Ex); + } + + SVal GetBlkExprSVal(Expr* Ex) { + return Mgr->GetBlkExprSVal(St, Ex); + } + + SVal GetSValAsScalarOrLoc(const Expr *Ex) { + return Mgr->GetSValAsScalarOrLoc(St, Ex); + } + + SVal GetSVal(Loc LV, QualType T = QualType()) { + return Mgr->GetSVal(St, LV, T); + } + + SVal GetSVal(const MemRegion* R) { + return Mgr->GetSVal(St, R); + } + + SVal GetSValAsScalarOrLoc(const MemRegion *R) { + return Mgr->GetSValAsScalarOrLoc(St, R); + } + + GRStateRef BindExpr(Stmt* Ex, SVal V, bool isBlkExpr, bool Invalidate) { + return GRStateRef(Mgr->BindExpr(St, Ex, V, isBlkExpr, Invalidate), *Mgr); + } + + GRStateRef BindExpr(Stmt* Ex, SVal V, bool Invalidate = true) { + return GRStateRef(Mgr->BindExpr(St, Ex, V, Invalidate), *Mgr); + } + + GRStateRef BindDecl(const VarDecl* VD, SVal InitVal) { + return GRStateRef(Mgr->BindDecl(St, VD, InitVal), *Mgr); + } + + GRStateRef BindLoc(Loc LV, SVal V) { + return GRStateRef(Mgr->BindLoc(St, LV, V), *Mgr); + } + + GRStateRef BindLoc(SVal LV, SVal V) { + if (!isa<Loc>(LV)) return *this; + return BindLoc(cast<Loc>(LV), V); + } + + GRStateRef Unbind(Loc LV) { + return GRStateRef(Mgr->Unbind(St, LV), *Mgr); + } + + // Trait based GDM dispatch. + template<typename T> + typename GRStateTrait<T>::data_type get() const { + return St->get<T>(); + } + + template<typename T> + typename GRStateTrait<T>::lookup_type + get(typename GRStateTrait<T>::key_type key) const { + return St->get<T>(key); + } + + template<typename T> + GRStateRef set(typename GRStateTrait<T>::data_type D) { + return GRStateRef(Mgr->set<T>(St, D), *Mgr); + } + + template <typename T> + typename GRStateTrait<T>::context_type get_context() { + return Mgr->get_context<T>(); + } + + template<typename T> + GRStateRef set(typename GRStateTrait<T>::key_type K, + typename GRStateTrait<T>::value_type E, + typename GRStateTrait<T>::context_type C) { + return GRStateRef(Mgr->set<T>(St, K, E, C), *Mgr); + } + + template<typename T> + GRStateRef set(typename GRStateTrait<T>::key_type K, + typename GRStateTrait<T>::value_type E) { + return GRStateRef(Mgr->set<T>(St, K, E, get_context<T>()), *Mgr); + } + + template<typename T> + GRStateRef add(typename GRStateTrait<T>::key_type K) { + return GRStateRef(Mgr->add<T>(St, K, get_context<T>()), *Mgr); + } + + template<typename T> + GRStateRef remove(typename GRStateTrait<T>::key_type K, + typename GRStateTrait<T>::context_type C) { + return GRStateRef(Mgr->remove<T>(St, K, C), *Mgr); + } + + template<typename T> + GRStateRef remove(typename GRStateTrait<T>::key_type K) { + return GRStateRef(Mgr->remove<T>(St, K, get_context<T>()), *Mgr); + } + + template<typename T> + bool contains(typename GRStateTrait<T>::key_type key) const { + return St->contains<T>(key); + } + + // Lvalue methods. + SVal GetLValue(const VarDecl* VD) { + return Mgr->GetLValue(St, VD); + } + + GRStateRef Assume(SVal Cond, bool Assumption, bool& isFeasible) { + return GRStateRef(Mgr->Assume(St, Cond, Assumption, isFeasible), *Mgr); + } + + template <typename CB> + CB scanReachableSymbols(SVal val) { + CB cb(*this); + Mgr->scanReachableSymbols(val, St, cb); + return cb; + } + + SymbolManager& getSymbolManager() { return Mgr->getSymbolManager(); } + BasicValueFactory& getBasicVals() { return Mgr->getBasicVals(); } + + // Pretty-printing. + void print(std::ostream& Out, const char* nl = "\n", + const char *sep = "") const; + + void printStdErr() const; + + void printDOT(std::ostream& Out) const; +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRStateTrait.h b/include/clang/Analysis/PathSensitive/GRStateTrait.h new file mode 100644 index 0000000..ce43cda --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRStateTrait.h @@ -0,0 +1,148 @@ +//==- GRStateTrait.h - Partial implementations of GRStateTrait -----*- 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 partial implementations of template specializations of +// the class GRStateTrait<>. GRStateTrait<> is used by GRState to implement +// set/get methods for mapulating a GRState's generic data map. +// +//===----------------------------------------------------------------------===// + + +#ifndef LLVM_CLANG_ANALYSIS_GRSTATETRAIT_H +#define LLVM_CLANG_ANALYSIS_GRSTATETRAIT_H + +namespace llvm { + class BumpPtrAllocator; + template <typename K, typename D, typename I> class ImmutableMap; + template <typename K, typename I> class ImmutableSet; + template <typename T> class ImmutableList; + template <typename T> class ImmutableListImpl; +} + +namespace clang { + template <typename T> struct GRStatePartialTrait; + + // Partial-specialization for ImmutableMap. + + template <typename Key, typename Data, typename Info> + struct GRStatePartialTrait< llvm::ImmutableMap<Key,Data,Info> > { + typedef llvm::ImmutableMap<Key,Data,Info> data_type; + typedef typename data_type::Factory& context_type; + typedef Key key_type; + typedef Data value_type; + typedef const value_type* lookup_type; + + static inline data_type MakeData(void* const* p) { + return p ? data_type((typename data_type::TreeTy*) *p) : data_type(0); + } + static inline void* MakeVoidPtr(data_type B) { + return B.getRoot(); + } + static lookup_type Lookup(data_type B, key_type K) { + return B.lookup(K); + } + static data_type Set(data_type B, key_type K, value_type E,context_type F){ + return F.Add(B, K, E); + } + + static data_type Remove(data_type B, key_type K, context_type F) { + return F.Remove(B, K); + } + + static inline context_type MakeContext(void* p) { + return *((typename data_type::Factory*) p); + } + + static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + return new typename data_type::Factory(Alloc); + } + + static void DeleteContext(void* Ctx) { + delete (typename data_type::Factory*) Ctx; + } + }; + + + // Partial-specialization for ImmutableSet. + + template <typename Key, typename Info> + struct GRStatePartialTrait< llvm::ImmutableSet<Key,Info> > { + typedef llvm::ImmutableSet<Key,Info> data_type; + typedef typename data_type::Factory& context_type; + typedef Key key_type; + + static inline data_type MakeData(void* const* p) { + return p ? data_type((typename data_type::TreeTy*) *p) : data_type(0); + } + + static inline void* MakeVoidPtr(data_type B) { + return B.getRoot(); + } + + static data_type Add(data_type B, key_type K, context_type F) { + return F.Add(B, K); + } + + static data_type Remove(data_type B, key_type K, context_type F) { + return F.Remove(B, K); + } + + static bool Contains(data_type B, key_type K) { + return B.contains(K); + } + + static inline context_type MakeContext(void* p) { + return *((typename data_type::Factory*) p); + } + + static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + return new typename data_type::Factory(Alloc); + } + + static void DeleteContext(void* Ctx) { + delete (typename data_type::Factory*) Ctx; + } + }; + + // Partial-specialization for ImmutableList. + + template <typename T> + struct GRStatePartialTrait< llvm::ImmutableList<T> > { + typedef llvm::ImmutableList<T> data_type; + typedef T key_type; + typedef typename data_type::Factory& context_type; + + static data_type Add(data_type L, key_type K, context_type F) { + return F.Add(K, L); + } + + static inline data_type MakeData(void* const* p) { + return p ? data_type((const llvm::ImmutableListImpl<T>*) *p) + : data_type(0); + } + + static inline void* MakeVoidPtr(data_type D) { + return (void*) D.getInternalPointer(); + } + + static inline context_type MakeContext(void* p) { + return *((typename data_type::Factory*) p); + } + + static void* CreateContext(llvm::BumpPtrAllocator& Alloc) { + return new typename data_type::Factory(Alloc); + } + + static void DeleteContext(void* Ctx) { + delete (typename data_type::Factory*) Ctx; + } + }; +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h new file mode 100644 index 0000000..0f353d0 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h @@ -0,0 +1,123 @@ +//== GRTransferFuncs.h - Path-Sens. Transfer Functions Interface -*- 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 GRTransferFuncs, which provides a base-class that +// defines an interface for transfer functions used by GRExprEngine. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_GRTF +#define LLVM_CLANG_ANALYSIS_GRTF + +#include "clang/Analysis/PathSensitive/SVals.h" +#include "clang/Analysis/PathSensitive/GRCoreEngine.h" +#include "clang/Analysis/PathSensitive/GRState.h" +#include <vector> + +namespace clang { + + class GRExprEngine; + class BugReporter; + class ObjCMessageExpr; + class GRStmtNodeBuilderRef; + +class GRTransferFuncs { + friend class GRExprEngine; +protected: + virtual SVal DetermEvalBinOpNN(GRExprEngine& Eng, + BinaryOperator::Opcode Op, + NonLoc L, NonLoc R, QualType T) { + return UnknownVal(); + } + +public: + GRTransferFuncs() {} + virtual ~GRTransferFuncs() {} + + virtual void RegisterPrinters(std::vector<GRState::Printer*>& Printers) {} + virtual void RegisterChecks(BugReporter& BR) {} + + // Casts. + + virtual SVal EvalCast(GRExprEngine& Engine, NonLoc V, QualType CastT) =0; + virtual SVal EvalCast(GRExprEngine& Engine, Loc V, QualType CastT) = 0; + + // Unary Operators. + + virtual SVal EvalMinus(GRExprEngine& Engine, UnaryOperator* U, NonLoc X) = 0; + + virtual SVal EvalComplement(GRExprEngine& Engine, NonLoc X) = 0; + + // Binary Operators. + // FIXME: We're moving back towards using GREXprEngine directly. No need + // for OStates + virtual void EvalBinOpNN(GRStateSet& OStates, GRExprEngine& Eng, + const GRState* St, Expr* Ex, + BinaryOperator::Opcode Op, NonLoc L, NonLoc R, + QualType T); + + virtual SVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op, + Loc L, Loc R) = 0; + + // Pointer arithmetic. + + virtual SVal EvalBinOp(GRExprEngine& Engine, const GRState *state, + BinaryOperator::Opcode Op, Loc L, NonLoc R) = 0; + + // Calls. + + virtual void EvalCall(ExplodedNodeSet<GRState>& Dst, + GRExprEngine& Engine, + GRStmtNodeBuilder<GRState>& Builder, + CallExpr* CE, SVal L, + ExplodedNode<GRState>* Pred) {} + + virtual void EvalObjCMessageExpr(ExplodedNodeSet<GRState>& Dst, + GRExprEngine& Engine, + GRStmtNodeBuilder<GRState>& Builder, + ObjCMessageExpr* ME, + ExplodedNode<GRState>* Pred) {} + + // Stores. + + virtual void EvalBind(GRStmtNodeBuilderRef& B, SVal location, SVal val) {} + + // End-of-path and dead symbol notification. + + virtual void EvalEndPath(GRExprEngine& Engine, + GREndPathNodeBuilder<GRState>& Builder) {} + + + virtual void EvalDeadSymbols(ExplodedNodeSet<GRState>& Dst, + GRExprEngine& Engine, + GRStmtNodeBuilder<GRState>& Builder, + ExplodedNode<GRState>* Pred, + Stmt* S, const GRState* state, + SymbolReaper& SymReaper) {} + + // Return statements. + virtual void EvalReturn(ExplodedNodeSet<GRState>& Dst, + GRExprEngine& Engine, + GRStmtNodeBuilder<GRState>& Builder, + ReturnStmt* S, + ExplodedNode<GRState>* Pred) {} + + // Assumptions. + + virtual const GRState* EvalAssume(GRStateManager& VMgr, + const GRState* St, + SVal Cond, bool Assumption, + bool& isFeasible) { + return St; + } +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRWorkList.h b/include/clang/Analysis/PathSensitive/GRWorkList.h new file mode 100644 index 0000000..c765322 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRWorkList.h @@ -0,0 +1,76 @@ +//==- GRWorkList.h - Worklist class used by GRCoreEngine -----------*- 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 GRWorkList, a pure virtual class that represents an opaque +// worklist used by GRCoreEngine to explore the reachability state space. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_GRWORKLIST +#define LLVM_CLANG_ANALYSIS_GRWORKLIST + +#include "clang/Analysis/PathSensitive/GRBlockCounter.h" + +namespace clang { + +class ExplodedNodeImpl; + +class GRWorkListUnit { + ExplodedNodeImpl* Node; + GRBlockCounter Counter; + CFGBlock* Block; + unsigned BlockIdx; + +public: + GRWorkListUnit(ExplodedNodeImpl* N, GRBlockCounter C, + CFGBlock* B, unsigned idx) + : Node(N), + Counter(C), + Block(B), + BlockIdx(idx) {} + + explicit GRWorkListUnit(ExplodedNodeImpl* N, GRBlockCounter C) + : Node(N), + Counter(C), + Block(NULL), + BlockIdx(0) {} + + ExplodedNodeImpl* getNode() const { return Node; } + GRBlockCounter getBlockCounter() const { return Counter; } + CFGBlock* getBlock() const { return Block; } + unsigned getIndex() const { return BlockIdx; } +}; + +class GRWorkList { + GRBlockCounter CurrentCounter; +public: + virtual ~GRWorkList(); + virtual bool hasWork() const = 0; + + virtual void Enqueue(const GRWorkListUnit& U) = 0; + + void Enqueue(ExplodedNodeImpl* N, CFGBlock& B, unsigned idx) { + Enqueue(GRWorkListUnit(N, CurrentCounter, &B, idx)); + } + + void Enqueue(ExplodedNodeImpl* N) { + Enqueue(GRWorkListUnit(N, CurrentCounter)); + } + + virtual GRWorkListUnit Dequeue() = 0; + + void setBlockCounter(GRBlockCounter C) { CurrentCounter = C; } + GRBlockCounter getBlockCounter() const { return CurrentCounter; } + + static GRWorkList *MakeDFS(); + static GRWorkList *MakeBFS(); + static GRWorkList *MakeBFSBlockDFSContents(); +}; +} // end clang namespace +#endif diff --git a/include/clang/Analysis/PathSensitive/MemRegion.h b/include/clang/Analysis/PathSensitive/MemRegion.h new file mode 100644 index 0000000..0e8da2a --- /dev/null +++ b/include/clang/Analysis/PathSensitive/MemRegion.h @@ -0,0 +1,665 @@ +//== MemRegion.h - Abstract memory regions for static analysis --*- 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 MemRegion and its subclasses. MemRegion defines a +// partially-typed abstraction of memory useful for path-sensitive dataflow +// analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_MEMREGION_H +#define LLVM_CLANG_ANALYSIS_MEMREGION_H + +#include "clang/AST/Decl.h" +#include "clang/AST/DeclObjC.h" +#include "clang/Analysis/PathSensitive/SymbolManager.h" +#include "clang/Analysis/PathSensitive/SVals.h" +#include "clang/AST/ASTContext.h" +#include "llvm/Support/Casting.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/ImmutableList.h" +#include "llvm/ADT/ImmutableMap.h" +#include "llvm/Support/Allocator.h" +#include <string> + +namespace llvm { class raw_ostream; } + +namespace clang { + +class MemRegionManager; + + +/// MemRegion - The root abstract class for all memory regions. +class MemRegion : public llvm::FoldingSetNode { +public: + enum Kind { MemSpaceRegionKind, + SymbolicRegionKind, + AllocaRegionKind, + // Typed regions. + BEG_TYPED_REGIONS, + CodeTextRegionKind, + CompoundLiteralRegionKind, + StringRegionKind, ElementRegionKind, + TypedViewRegionKind, + // Decl Regions. + BEG_DECL_REGIONS, + VarRegionKind, FieldRegionKind, + ObjCIvarRegionKind, ObjCObjectRegionKind, + END_DECL_REGIONS, + END_TYPED_REGIONS }; +private: + const Kind kind; + +protected: + MemRegion(Kind k) : kind(k) {} + virtual ~MemRegion(); + +public: + // virtual MemExtent getExtent(MemRegionManager& mrm) const = 0; + virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0; + + std::string getString() const; + + virtual void print(llvm::raw_ostream& os) const; + + Kind getKind() const { return kind; } + + template<typename RegionTy> const RegionTy* getAs() const; + + virtual bool isBoundable(ASTContext&) const { return true; } + + static bool classof(const MemRegion*) { return true; } +}; + +/// MemSpaceRegion - A memory region that represents and "memory space"; +/// for example, the set of global variables, the stack frame, etc. +class MemSpaceRegion : public MemRegion { + friend class MemRegionManager; + MemSpaceRegion() : MemRegion(MemSpaceRegionKind) {} + +public: + //RegionExtent getExtent() const { return UndefinedExtent(); } + + void Profile(llvm::FoldingSetNodeID& ID) const; + + bool isBoundable(ASTContext &) const { return false; } + + static bool classof(const MemRegion* R) { + return R->getKind() == MemSpaceRegionKind; + } +}; + +/// SubRegion - A region that subsets another larger region. Most regions +/// are subclasses of SubRegion. +class SubRegion : public MemRegion { +protected: + const MemRegion* superRegion; + SubRegion(const MemRegion* sReg, Kind k) : MemRegion(k), superRegion(sReg) {} + +public: + const MemRegion* getSuperRegion() const { + return superRegion; + } + + bool isSubRegionOf(const MemRegion* R) const; + + static bool classof(const MemRegion* R) { + return R->getKind() > MemSpaceRegionKind; + } +}; + +/// AllocaRegion - A region that represents an untyped blob of bytes created +/// by a call to 'alloca'. +class AllocaRegion : public SubRegion { + friend class MemRegionManager; +protected: + unsigned Cnt; // Block counter. Used to distinguish different pieces of + // memory allocated by alloca at the same call site. + const Expr* Ex; + + AllocaRegion(const Expr* ex, unsigned cnt, const MemRegion* superRegion) + : SubRegion(superRegion, AllocaRegionKind), Cnt(cnt), Ex(ex) {} + +public: + + const Expr* getExpr() const { return Ex; } + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr* Ex, + unsigned Cnt); + + void print(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == AllocaRegionKind; + } +}; + +/// TypedRegion - An abstract class representing regions that are typed. +class TypedRegion : public SubRegion { +protected: + TypedRegion(const MemRegion* sReg, Kind k) : SubRegion(sReg, k) {} + +public: + virtual QualType getValueType(ASTContext &C) const = 0; + + virtual QualType getLocationType(ASTContext& C) const { + // FIXME: We can possibly optimize this later to cache this value. + return C.getPointerType(getValueType(C)); + } + + QualType getDesugaredValueType(ASTContext& C) const { + QualType T = getValueType(C); + return T.getTypePtr() ? T->getDesugaredType() : T; + } + + QualType getDesugaredLocationType(ASTContext& C) const { + return getLocationType(C)->getDesugaredType(); + } + + bool isBoundable(ASTContext &C) const { + return !getValueType(C).isNull(); + } + + static bool classof(const MemRegion* R) { + unsigned k = R->getKind(); + return k > BEG_TYPED_REGIONS && k < END_TYPED_REGIONS; + } +}; + +/// CodeTextRegion - A region that represents code texts of a function. It wraps +/// two kinds of code texts: real function and symbolic function. Real function +/// is a function declared in the program. Symbolic function is a function +/// pointer that we don't know which function it points to. +class CodeTextRegion : public TypedRegion { +public: + enum CodeKind { Declared, Symbolic }; + +private: + // The function pointer kind that this CodeTextRegion represents. + CodeKind codekind; + + // Data may be a SymbolRef or FunctionDecl*. + const void* Data; + + // Cached function pointer type. + QualType LocationType; + +public: + + CodeTextRegion(const FunctionDecl* fd, QualType t, const MemRegion* sreg) + : TypedRegion(sreg, CodeTextRegionKind), + codekind(Declared), + Data(fd), + LocationType(t) {} + + CodeTextRegion(SymbolRef sym, QualType t, const MemRegion* sreg) + : TypedRegion(sreg, CodeTextRegionKind), + codekind(Symbolic), + Data(sym), + LocationType(t) {} + + QualType getValueType(ASTContext &C) const { + // Do not get the object type of a CodeTextRegion. + assert(0); + return QualType(); + } + + QualType getLocationType(ASTContext &C) const { + return LocationType; + } + + bool isDeclared() const { return codekind == Declared; } + bool isSymbolic() const { return codekind == Symbolic; } + + const FunctionDecl* getDecl() const { + assert(codekind == Declared); + return static_cast<const FunctionDecl*>(Data); + } + + SymbolRef getSymbol() const { + assert(codekind == Symbolic); + return const_cast<SymbolRef>(static_cast<const SymbolRef>(Data)); + } + + bool isBoundable(ASTContext&) const { return false; } + + virtual void print(llvm::raw_ostream& os) const; + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, + const void* data, QualType t); + + static bool classof(const MemRegion* R) { + return R->getKind() == CodeTextRegionKind; + } +}; + +/// SymbolicRegion - A special, "non-concrete" region. Unlike other region +/// clases, SymbolicRegion represents a region that serves as an alias for +/// either a real region, a NULL pointer, etc. It essentially is used to +/// map the concept of symbolic values into the domain of regions. Symbolic +/// regions do not need to be typed. +class SymbolicRegion : public SubRegion { +protected: + const SymbolRef sym; + +public: + SymbolicRegion(const SymbolRef s, const MemRegion* sreg) + : SubRegion(sreg, SymbolicRegionKind), sym(s) {} + + SymbolRef getSymbol() const { + return sym; + } + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym); + + void print(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == SymbolicRegionKind; + } +}; + +/// StringRegion - Region associated with a StringLiteral. +class StringRegion : public TypedRegion { + friend class MemRegionManager; + const StringLiteral* Str; +protected: + + StringRegion(const StringLiteral* str, MemRegion* sreg) + : TypedRegion(sreg, StringRegionKind), Str(str) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, + const StringLiteral* Str, + const MemRegion* superRegion); + +public: + + const StringLiteral* getStringLiteral() const { return Str; } + + QualType getValueType(ASTContext& C) const { + return Str->getType(); + } + + void Profile(llvm::FoldingSetNodeID& ID) const { + ProfileRegion(ID, Str, superRegion); + } + + void print(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == StringRegionKind; + } +}; + +class TypedViewRegion : public TypedRegion { + friend class MemRegionManager; + QualType LValueType; + + TypedViewRegion(QualType lvalueType, const MemRegion* sreg) + : TypedRegion(sreg, TypedViewRegionKind), LValueType(lvalueType) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType T, + const MemRegion* superRegion); + +public: + + void print(llvm::raw_ostream& os) const; + + QualType getLocationType(ASTContext&) const { + return LValueType; + } + + QualType getValueType(ASTContext&) const { + const PointerType* PTy = LValueType->getAsPointerType(); + assert(PTy); + return PTy->getPointeeType(); + } + + bool isBoundable(ASTContext &C) const { + return isa<PointerType>(LValueType); + } + + void Profile(llvm::FoldingSetNodeID& ID) const { + ProfileRegion(ID, LValueType, superRegion); + } + + static bool classof(const MemRegion* R) { + return R->getKind() == TypedViewRegionKind; + } + + const MemRegion *removeViews() const; +}; + + +/// CompoundLiteralRegion - A memory region representing a compound literal. +/// Compound literals are essentially temporaries that are stack allocated +/// or in the global constant pool. +class CompoundLiteralRegion : public TypedRegion { +private: + friend class MemRegionManager; + const CompoundLiteralExpr* CL; + + CompoundLiteralRegion(const CompoundLiteralExpr* cl, const MemRegion* sReg) + : TypedRegion(sReg, CompoundLiteralRegionKind), CL(cl) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, + const CompoundLiteralExpr* CL, + const MemRegion* superRegion); +public: + QualType getValueType(ASTContext& C) const { + return C.getCanonicalType(CL->getType()); + } + + void Profile(llvm::FoldingSetNodeID& ID) const; + + void print(llvm::raw_ostream& os) const; + + const CompoundLiteralExpr* getLiteralExpr() const { return CL; } + + static bool classof(const MemRegion* R) { + return R->getKind() == CompoundLiteralRegionKind; + } +}; + +class DeclRegion : public TypedRegion { +protected: + const Decl* D; + + DeclRegion(const Decl* d, const MemRegion* sReg, Kind k) + : TypedRegion(sReg, k), D(d) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D, + const MemRegion* superRegion, Kind k); + +public: + const Decl* getDecl() const { return D; } + void Profile(llvm::FoldingSetNodeID& ID) const; + + static bool classof(const MemRegion* R) { + unsigned k = R->getKind(); + return k > BEG_DECL_REGIONS && k < END_DECL_REGIONS; + } +}; + +class VarRegion : public DeclRegion { + friend class MemRegionManager; + + VarRegion(const VarDecl* vd, const MemRegion* sReg) + : DeclRegion(vd, sReg, VarRegionKind) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, VarDecl* VD, + const MemRegion* superRegion) { + DeclRegion::ProfileRegion(ID, VD, superRegion, VarRegionKind); + } + +public: + const VarDecl* getDecl() const { return cast<VarDecl>(D); } + + QualType getValueType(ASTContext& C) const { + // FIXME: We can cache this if needed. + return C.getCanonicalType(getDecl()->getType()); + } + + void print(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == VarRegionKind; + } +}; + +class FieldRegion : public DeclRegion { + friend class MemRegionManager; + + FieldRegion(const FieldDecl* fd, const MemRegion* sReg) + : DeclRegion(fd, sReg, FieldRegionKind) {} + +public: + + void print(llvm::raw_ostream& os) const; + + const FieldDecl* getDecl() const { return cast<FieldDecl>(D); } + + QualType getValueType(ASTContext& C) const { + // FIXME: We can cache this if needed. + return C.getCanonicalType(getDecl()->getType()); + } + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, FieldDecl* FD, + const MemRegion* superRegion) { + DeclRegion::ProfileRegion(ID, FD, superRegion, FieldRegionKind); + } + + static bool classof(const MemRegion* R) { + return R->getKind() == FieldRegionKind; + } +}; + +class ObjCObjectRegion : public DeclRegion { + + friend class MemRegionManager; + + ObjCObjectRegion(const ObjCInterfaceDecl* ivd, const MemRegion* sReg) + : DeclRegion(ivd, sReg, ObjCObjectRegionKind) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, ObjCInterfaceDecl* ivd, + const MemRegion* superRegion) { + DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCObjectRegionKind); + } + +public: + const ObjCInterfaceDecl* getInterface() const { + return cast<ObjCInterfaceDecl>(D); + } + + QualType getValueType(ASTContext& C) const { + return C.getObjCInterfaceType(getInterface()); + } + + static bool classof(const MemRegion* R) { + return R->getKind() == ObjCObjectRegionKind; + } +}; + +class ObjCIvarRegion : public DeclRegion { + + friend class MemRegionManager; + + ObjCIvarRegion(const ObjCIvarDecl* ivd, const MemRegion* sReg) + : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, ObjCIvarDecl* ivd, + const MemRegion* superRegion) { + DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind); + } + +public: + const ObjCIvarDecl* getDecl() const { return cast<ObjCIvarDecl>(D); } + QualType getValueType(ASTContext&) const { return getDecl()->getType(); } + + static bool classof(const MemRegion* R) { + return R->getKind() == ObjCIvarRegionKind; + } +}; + +class ElementRegion : public TypedRegion { + friend class MemRegionManager; + + QualType ElementType; + SVal Index; + + ElementRegion(QualType elementType, SVal Idx, const MemRegion* sReg) + : TypedRegion(sReg, ElementRegionKind), + ElementType(elementType), Index(Idx) { + assert((!isa<nonloc::ConcreteInt>(&Idx) || + cast<nonloc::ConcreteInt>(&Idx)->getValue().isSigned()) && + "The index must be signed"); + } + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType elementType, + SVal Idx, const MemRegion* superRegion); + +public: + + SVal getIndex() const { return Index; } + + QualType getValueType(ASTContext&) const { + return ElementType; + } + + QualType getElementType() const { + return ElementType; + } + + void print(llvm::raw_ostream& os) const; + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == ElementRegionKind; + } +}; + +template<typename RegionTy> +const RegionTy* MemRegion::getAs() const { + const MemRegion *R = this; + + do { + if (const RegionTy* RT = dyn_cast<RegionTy>(R)) + return RT; + + if (const TypedViewRegion *TR = dyn_cast<TypedViewRegion>(R)) { + R = TR->getSuperRegion(); + continue; + } + + break; + } + while (R); + + return 0; +} + +//===----------------------------------------------------------------------===// +// MemRegionManager - Factory object for creating regions. +//===----------------------------------------------------------------------===// + +class MemRegionManager { + llvm::BumpPtrAllocator& A; + llvm::FoldingSet<MemRegion> Regions; + + MemSpaceRegion* globals; + MemSpaceRegion* stack; + MemSpaceRegion* heap; + MemSpaceRegion* unknown; + MemSpaceRegion* code; + +public: + MemRegionManager(llvm::BumpPtrAllocator& a) + : A(a), globals(0), stack(0), heap(0), unknown(0), code(0) {} + + ~MemRegionManager() {} + + /// getStackRegion - Retrieve the memory region associated with the + /// current stack frame. + MemSpaceRegion* getStackRegion(); + + /// getGlobalsRegion - Retrieve the memory region associated with + /// all global variables. + MemSpaceRegion* getGlobalsRegion(); + + /// getHeapRegion - Retrieve the memory region associated with the + /// generic "heap". + MemSpaceRegion* getHeapRegion(); + + /// getUnknownRegion - Retrieve the memory region associated with unknown + /// memory space. + MemSpaceRegion* getUnknownRegion(); + + MemSpaceRegion* getCodeRegion(); + + bool isGlobalsRegion(const MemRegion* R) { + assert(R); + return R == globals; + } + + /// onStack - check if the region is allocated on the stack. + bool onStack(const MemRegion* R); + + /// onHeap - check if the region is allocated on the heap, usually by malloc. + bool onHeap(const MemRegion* R); + + /// getAllocaRegion - Retrieve a region associated with a call to alloca(). + AllocaRegion* getAllocaRegion(const Expr* Ex, unsigned Cnt); + + /// getCompoundLiteralRegion - Retrieve the region associated with a + /// given CompoundLiteral. + CompoundLiteralRegion* + getCompoundLiteralRegion(const CompoundLiteralExpr* CL); + + /// getSymbolicRegion - Retrieve or create a "symbolic" memory region. + SymbolicRegion* getSymbolicRegion(SymbolRef sym); + + StringRegion* getStringRegion(const StringLiteral* Str); + + /// getVarRegion - Retrieve or create the memory region associated with + /// a specified VarDecl. + VarRegion* getVarRegion(const VarDecl* vd); + + /// getElementRegion - Retrieve the memory region associated with the + /// associated element type, index, and super region. + ElementRegion* getElementRegion(QualType elementType, SVal Idx, + const MemRegion* superRegion); + + /// getFieldRegion - Retrieve or create the memory region associated with + /// a specified FieldDecl. 'superRegion' corresponds to the containing + /// memory region (which typically represents the memory representing + /// a structure or class). + FieldRegion* getFieldRegion(const FieldDecl* fd, + const MemRegion* superRegion); + + /// getObjCObjectRegion - Retrieve or create the memory region associated with + /// the instance of a specified Objective-C class. + ObjCObjectRegion* getObjCObjectRegion(const ObjCInterfaceDecl* ID, + const MemRegion* superRegion); + + /// getObjCIvarRegion - Retrieve or create the memory region associated with + /// a specified Objective-c instance variable. 'superRegion' corresponds + /// to the containing region (which typically represents the Objective-C + /// object). + ObjCIvarRegion* getObjCIvarRegion(const ObjCIvarDecl* ivd, + const MemRegion* superRegion); + + TypedViewRegion* getTypedViewRegion(QualType LValueType, + const MemRegion* superRegion); + + CodeTextRegion* getCodeTextRegion(SymbolRef sym, QualType t); + CodeTextRegion* getCodeTextRegion(const FunctionDecl* fd, QualType t); + + bool hasStackStorage(const MemRegion* R); + +private: + MemSpaceRegion* LazyAllocate(MemSpaceRegion*& region); +}; +} // end clang namespace + +namespace llvm { +static inline raw_ostream& operator<<(raw_ostream& O, + const clang::MemRegion* R) { + R->print(O); + return O; +} +} // end llvm namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/SVals.h b/include/clang/Analysis/PathSensitive/SVals.h new file mode 100644 index 0000000..ee6d4dc --- /dev/null +++ b/include/clang/Analysis/PathSensitive/SVals.h @@ -0,0 +1,447 @@ +//== SVals.h - Abstract Values for Static Analysis ---------*- 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 SVal, Loc, and NonLoc, classes that represent +// abstract r-values for use with path-sensitive value tracking. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_RVALUE_H +#define LLVM_CLANG_ANALYSIS_RVALUE_H + +#include "clang/Analysis/PathSensitive/SymbolManager.h" +#include "llvm/Support/Casting.h" +#include "llvm/ADT/ImmutableList.h" + +//==------------------------------------------------------------------------==// +// Base SVal types. +//==------------------------------------------------------------------------==// + +namespace clang { + +class CompoundValData; +class BasicValueFactory; +class MemRegion; +class MemRegionManager; +class GRStateManager; + +class SVal { +public: + enum BaseKind { UndefinedKind, UnknownKind, LocKind, NonLocKind }; + enum { BaseBits = 2, BaseMask = 0x3 }; + +protected: + void* Data; + unsigned Kind; + +protected: + SVal(const void* d, bool isLoc, unsigned ValKind) + : Data(const_cast<void*>(d)), + Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} + + explicit SVal(BaseKind k, void* D = NULL) + : Data(D), Kind(k) {} + +public: + SVal() : Data(0), Kind(0) {} + ~SVal() {}; + + /// BufferTy - A temporary buffer to hold a set of SVals. + typedef llvm::SmallVector<SVal,5> BufferTy; + + inline unsigned getRawKind() const { return Kind; } + inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); } + inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; } + + inline void Profile(llvm::FoldingSetNodeID& ID) const { + ID.AddInteger((unsigned) getRawKind()); + ID.AddPointer(reinterpret_cast<void*>(Data)); + } + + inline bool operator==(const SVal& R) const { + return getRawKind() == R.getRawKind() && Data == R.Data; + } + + inline bool operator!=(const SVal& R) const { + return !(*this == R); + } + + inline bool isUnknown() const { + return getRawKind() == UnknownKind; + } + + inline bool isUndef() const { + return getRawKind() == UndefinedKind; + } + + inline bool isUnknownOrUndef() const { + return getRawKind() <= UnknownKind; + } + + inline bool isValid() const { + return getRawKind() > UnknownKind; + } + + bool isZeroConstant() const; + + /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true; + bool hasConjuredSymbol() const; + + /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a + /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. + /// Otherwise return 0. + const FunctionDecl* getAsFunctionDecl() const; + + /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and + /// wraps a symbol, return that SymbolRef. Otherwise return a SymbolData* + SymbolRef getAsLocSymbol() const; + + /// getAsSymbol - If this Sval wraps a symbol return that SymbolRef. + /// Otherwise return a SymbolRef where 'isValid()' returns false. + SymbolRef getAsSymbol() const; + + /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then + /// return that expression. Otherwise return NULL. + const SymExpr *getAsSymbolicExpression() const; + + void print(std::ostream& OS) const; + void print(llvm::raw_ostream& OS) const; + void printStdErr() const; + + // Iterators. + class symbol_iterator { + llvm::SmallVector<const SymExpr*, 5> itr; + void expand(); + public: + symbol_iterator() {} + symbol_iterator(const SymExpr* SE); + + symbol_iterator& operator++(); + SymbolRef operator*(); + + bool operator==(const symbol_iterator& X) const; + bool operator!=(const symbol_iterator& X) const; + }; + + symbol_iterator symbol_begin() const { + const SymExpr *SE = getAsSymbolicExpression(); + if (SE) + return symbol_iterator(SE); + else + return symbol_iterator(); + } + + symbol_iterator symbol_end() const { return symbol_iterator(); } + + // Implement isa<T> support. + static inline bool classof(const SVal*) { return true; } +}; + +class UnknownVal : public SVal { +public: + UnknownVal() : SVal(UnknownKind) {} + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == UnknownKind; + } +}; + +class UndefinedVal : public SVal { +public: + UndefinedVal() : SVal(UndefinedKind) {} + UndefinedVal(void* D) : SVal(UndefinedKind, D) {} + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == UndefinedKind; + } + + void* getData() const { return Data; } +}; + +class NonLoc : public SVal { +protected: + NonLoc(unsigned SubKind, const void* d) : SVal(d, false, SubKind) {} + +public: + void print(llvm::raw_ostream& Out) const; + + // Utility methods to create NonLocs. + + static NonLoc MakeIntVal(BasicValueFactory& BasicVals, uint64_t X, + bool isUnsigned); + + static NonLoc MakeVal(BasicValueFactory& BasicVals, uint64_t X, + unsigned BitWidth, bool isUnsigned); + + static NonLoc MakeVal(BasicValueFactory& BasicVals, uint64_t X, QualType T); + + static NonLoc MakeVal(BasicValueFactory& BasicVals, IntegerLiteral* I); + + static NonLoc MakeVal(BasicValueFactory& BasicVals, const llvm::APInt& I, + bool isUnsigned); + + static NonLoc MakeVal(BasicValueFactory& BasicVals, const llvm::APSInt& I); + + static NonLoc MakeIntTruthVal(BasicValueFactory& BasicVals, bool b); + + static NonLoc MakeCompoundVal(QualType T, llvm::ImmutableList<SVal> Vals, + BasicValueFactory& BasicVals); + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind; + } +}; + +class Loc : public SVal { +protected: + Loc(unsigned SubKind, const void* D) + : SVal(const_cast<void*>(D), true, SubKind) {} + +public: + void print(llvm::raw_ostream& Out) const; + + Loc(const Loc& X) : SVal(X.Data, true, X.getSubKind()) {} + Loc& operator=(const Loc& X) { memcpy(this, &X, sizeof(Loc)); return *this; } + + static Loc MakeVal(const MemRegion* R); + + static Loc MakeVal(AddrLabelExpr* E); + + static Loc MakeNull(BasicValueFactory &BasicVals); + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind; + } + + static inline bool IsLocType(QualType T) { + return T->isPointerType() || T->isObjCQualifiedIdType() + || T->isBlockPointerType(); + } +}; + +//==------------------------------------------------------------------------==// +// Subclasses of NonLoc. +//==------------------------------------------------------------------------==// + +namespace nonloc { + +enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, + LocAsIntegerKind, CompoundValKind }; + +class SymbolVal : public NonLoc { +public: + SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {} + + SymbolRef getSymbol() const { + return (const SymbolData*) Data; + } + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == SymbolValKind; + } + + static inline bool classof(const NonLoc* V) { + return V->getSubKind() == SymbolValKind; + } +}; + +class SymExprVal : public NonLoc { +public: + SymExprVal(const SymExpr *SE) + : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {} + + const SymExpr *getSymbolicExpression() const { + return reinterpret_cast<SymExpr*>(Data); + } + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == SymExprValKind; + } + + static inline bool classof(const NonLoc* V) { + return V->getSubKind() == SymExprValKind; + } +}; + +class ConcreteInt : public NonLoc { +public: + ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} + + const llvm::APSInt& getValue() const { + return *static_cast<llvm::APSInt*>(Data); + } + + // Transfer functions for binary/unary operations on ConcreteInts. + SVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, + const ConcreteInt& R) const; + + ConcreteInt EvalComplement(BasicValueFactory& BasicVals) const; + + ConcreteInt EvalMinus(BasicValueFactory& BasicVals, UnaryOperator* U) const; + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == ConcreteIntKind; + } + + static inline bool classof(const NonLoc* V) { + return V->getSubKind() == ConcreteIntKind; + } +}; + +class LocAsInteger : public NonLoc { + LocAsInteger(const std::pair<SVal, uintptr_t>& data) : + NonLoc(LocAsIntegerKind, &data) { + assert (isa<Loc>(data.first)); + } + +public: + + Loc getLoc() const { + return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first); + } + + const Loc& getPersistentLoc() const { + const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first; + return cast<Loc>(V); + } + + unsigned getNumBits() const { + return ((std::pair<SVal, unsigned>*) Data)->second; + } + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == LocAsIntegerKind; + } + + static inline bool classof(const NonLoc* V) { + return V->getSubKind() == LocAsIntegerKind; + } + + static LocAsInteger Make(BasicValueFactory& Vals, Loc V, unsigned Bits); +}; + +class CompoundVal : public NonLoc { + friend class NonLoc; + + CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} + +public: + const CompoundValData* getValue() const { + return static_cast<CompoundValData*>(Data); + } + + typedef llvm::ImmutableList<SVal>::iterator iterator; + iterator begin() const; + iterator end() const; + + static bool classof(const SVal* V) { + return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind; + } + + static bool classof(const NonLoc* V) { + return V->getSubKind() == CompoundValKind; + } +}; + +} // end namespace clang::nonloc + +//==------------------------------------------------------------------------==// +// Subclasses of Loc. +//==------------------------------------------------------------------------==// + +namespace loc { + +enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind }; + +class GotoLabel : public Loc { +public: + GotoLabel(LabelStmt* Label) : Loc(GotoLabelKind, Label) {} + + LabelStmt* getLabel() const { + return static_cast<LabelStmt*>(Data); + } + + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind && + V->getSubKind() == GotoLabelKind; + } + + static inline bool classof(const Loc* V) { + return V->getSubKind() == GotoLabelKind; + } +}; + + +class MemRegionVal : public Loc { +public: + MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {} + + const MemRegion* getRegion() const { + return static_cast<MemRegion*>(Data); + } + + template <typename REGION> + const REGION* getRegionAs() const { + return llvm::dyn_cast<REGION>(getRegion()); + } + + inline bool operator==(const MemRegionVal& R) const { + return getRegion() == R.getRegion(); + } + + inline bool operator!=(const MemRegionVal& R) const { + return getRegion() != R.getRegion(); + } + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind && + V->getSubKind() == MemRegionKind; + } + + static inline bool classof(const Loc* V) { + return V->getSubKind() == MemRegionKind; + } +}; + +class ConcreteInt : public Loc { +public: + ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} + + const llvm::APSInt& getValue() const { + return *static_cast<llvm::APSInt*>(Data); + } + + // Transfer functions for binary/unary operations on ConcreteInts. + SVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, + const ConcreteInt& R) const; + + // Implement isa<T> support. + static inline bool classof(const SVal* V) { + return V->getBaseKind() == LocKind && + V->getSubKind() == ConcreteIntKind; + } + + static inline bool classof(const Loc* V) { + return V->getSubKind() == ConcreteIntKind; + } +}; + +} // end clang::loc namespace +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/Store.h b/include/clang/Analysis/PathSensitive/Store.h new file mode 100644 index 0000000..1f081f4 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/Store.h @@ -0,0 +1,204 @@ +//== Store.h - Interface for maps from Locations to Values ------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the types Store and StoreManager. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_STORE_H +#define LLVM_CLANG_ANALYSIS_STORE_H + +#include "clang/Analysis/PathSensitive/SVals.h" +#include "clang/Analysis/PathSensitive/MemRegion.h" +#include "clang/Analysis/PathSensitive/ValueManager.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallVector.h" +#include <iosfwd> + +namespace clang { + +typedef const void* Store; + +class GRState; +class GRStateManager; +class Stmt; +class Expr; +class ObjCIvarDecl; +class SubRegionMap; + +class StoreManager { +protected: + ValueManager &ValMgr; + GRStateManager &StateMgr; + + /// MRMgr - Manages region objects associated with this StoreManager. + MemRegionManager &MRMgr; + + StoreManager(GRStateManager &stateMgr); + +protected: + virtual const GRState* AddRegionView(const GRState* St, + const MemRegion* View, + const MemRegion* Base) { + return St; + } + +public: + virtual ~StoreManager() {} + + /// Return the value bound to specified location in a given state. + /// \param[in] state The analysis state. + /// \param[in] loc The symbolic memory location. + /// \param[in] T An optional type that provides a hint indicating the + /// expected type of the returned value. This is used if the value is + /// lazily computed. + /// \return The value bound to the location \c loc. + virtual SVal Retrieve(const GRState* state, Loc loc, + QualType T = QualType()) = 0; + + /// Return a state with the specified value bound to the given location. + /// \param[in] state The analysis state. + /// \param[in] loc The symbolic memory location. + /// \param[in] val The value to bind to location \c loc. + /// \return A pointer to a GRState object that contains the same bindings as + /// \c state with the addition of having the value specified by \c val bound + /// to the location given for \c loc. + virtual const GRState* Bind(const GRState* state, Loc loc, SVal val) = 0; + + virtual Store Remove(Store St, Loc L) = 0; + + /// BindCompoundLiteral - Return the store that has the bindings currently + /// in 'store' plus the bindings for the CompoundLiteral. 'R' is the region + /// for the compound literal and 'BegInit' and 'EndInit' represent an + /// array of initializer values. + virtual const GRState* BindCompoundLiteral(const GRState* St, + const CompoundLiteralExpr* CL, + SVal V) = 0; + + /// getInitialStore - Returns the initial "empty" store representing the + /// value bindings upon entry to an analyzed function. + virtual Store getInitialStore() = 0; + + /// getRegionManager - Returns the internal RegionManager object that is + /// used to query and manipulate MemRegion objects. + MemRegionManager& getRegionManager() { return MRMgr; } + + /// getSubRegionMap - Returns an opaque map object that clients can query + /// to get the subregions of a given MemRegion object. It is the + // caller's responsibility to 'delete' the returned map. + virtual SubRegionMap* getSubRegionMap(const GRState *state) = 0; + + virtual SVal getLValueVar(const GRState* St, const VarDecl* VD) = 0; + + virtual SVal getLValueString(const GRState* St, const StringLiteral* S) = 0; + + virtual SVal getLValueCompoundLiteral(const GRState* St, + const CompoundLiteralExpr* CL) = 0; + + virtual SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, + SVal Base) = 0; + + virtual SVal getLValueField(const GRState* St, SVal Base, + const FieldDecl* D) = 0; + + virtual SVal getLValueElement(const GRState* St, QualType elementType, + SVal Base, SVal Offset) = 0; + + virtual SVal getSizeInElements(const GRState* St, const MemRegion* R) { + return UnknownVal(); + } + + /// ArrayToPointer - Used by GRExprEngine::VistCast to handle implicit + /// conversions between arrays and pointers. + virtual SVal ArrayToPointer(Loc Array) = 0; + + + class CastResult { + const GRState* State; + const MemRegion* R; + public: + const GRState* getState() const { return State; } + const MemRegion* getRegion() const { return R; } + CastResult(const GRState* s, const MemRegion* r = 0) : State(s), R(r) {} + }; + + /// CastRegion - Used by GRExprEngine::VisitCast to handle casts from + /// a MemRegion* to a specific location type. 'R' is the region being + /// casted and 'CastToTy' the result type of the cast. + virtual CastResult CastRegion(const GRState* state, const MemRegion* R, + QualType CastToTy); + + /// EvalBinOp - Perform pointer arithmetic. + virtual SVal EvalBinOp(const GRState *state, + BinaryOperator::Opcode Op, Loc L, NonLoc R) { + return UnknownVal(); + } + + /// getSelfRegion - Returns the region for the 'self' (Objective-C) or + /// 'this' object (C++). When used when analyzing a normal function this + /// method returns NULL. + virtual const MemRegion* getSelfRegion(Store store) = 0; + + virtual Store + RemoveDeadBindings(const GRState* state, Stmt* Loc, SymbolReaper& SymReaper, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) = 0; + + virtual const GRState* BindDecl(const GRState* St, const VarDecl* VD, + SVal InitVal) = 0; + + virtual const GRState* BindDeclWithNoInit(const GRState* St, + const VarDecl* VD) = 0; + + virtual const GRState* setExtent(const GRState* St, + const MemRegion* R, SVal Extent) { + return St; + } + + virtual const GRState* setDefaultValue(const GRState* St, + const MemRegion* R, SVal V) { + return St; + } + + virtual void print(Store store, std::ostream& Out, + const char* nl, const char *sep) = 0; + + class BindingsHandler { + public: + virtual ~BindingsHandler(); + virtual bool HandleBinding(StoreManager& SMgr, Store store, + const MemRegion* R, SVal val) = 0; + }; + + /// iterBindings - Iterate over the bindings in the Store. + virtual void iterBindings(Store store, BindingsHandler& f) = 0; +}; + +/// SubRegionMap - An abstract interface that represents a queryable map +/// between MemRegion objects and their subregions. +class SubRegionMap { +public: + virtual ~SubRegionMap() {} + + class Visitor { + public: + virtual ~Visitor() {}; + virtual bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) = 0; + }; + + virtual bool iterSubRegions(const MemRegion* R, Visitor& V) const = 0; +}; + +StoreManager* CreateBasicStoreManager(GRStateManager& StMgr); +StoreManager* CreateRegionStoreManager(GRStateManager& StMgr); + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/SymbolManager.h b/include/clang/Analysis/PathSensitive/SymbolManager.h new file mode 100644 index 0000000..d424526 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/SymbolManager.h @@ -0,0 +1,329 @@ +//== SymbolManager.h - Management of Symbolic Values ------------*- 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 SymbolManager, a class that manages symbolic values +// created for use by GRExprEngine and related classes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_SYMMGR_H +#define LLVM_CLANG_ANALYSIS_SYMMGR_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" +#include "clang/Analysis/Analyses/LiveVariables.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/Allocator.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ImmutableSet.h" + +namespace llvm { + class raw_ostream; +} + +namespace clang { + class MemRegion; + class ASTContext; + class BasicValueFactory; +} + +namespace clang { + +class SymExpr : public llvm::FoldingSetNode { +public: + enum Kind { BEGIN_SYMBOLS, RegionValueKind, ConjuredKind, END_SYMBOLS, + SymIntKind, SymSymKind }; +private: + Kind K; + +protected: + SymExpr(Kind k) : K(k) {} + +public: + virtual ~SymExpr() {} + + Kind getKind() const { return K; } + + virtual QualType getType(ASTContext&) const = 0; + virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; + + // Implement isa<T> support. + static inline bool classof(const SymExpr*) { return true; } +}; + +typedef unsigned SymbolID; + +class SymbolData : public SymExpr { +private: + const SymbolID Sym; + +protected: + SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {} + +public: + virtual ~SymbolData() {} + + SymbolID getSymbolID() const { return Sym; } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + Kind k = SE->getKind(); + return k > BEGIN_SYMBOLS && k < END_SYMBOLS; + } +}; + +typedef const SymbolData* SymbolRef; + +class SymbolRegionValue : public SymbolData { + const MemRegion *R; +public: + SymbolRegionValue(SymbolID sym, const MemRegion *r) + : SymbolData(RegionValueKind, sym), R(r) {} + + const MemRegion* getRegion() const { return R; } + + static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion* R) { + profile.AddInteger((unsigned) RegionValueKind); + profile.AddPointer(R); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, R); + } + + QualType getType(ASTContext&) const; + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == RegionValueKind; + } +}; + +class SymbolConjured : public SymbolData { + const Stmt* S; + QualType T; + unsigned Count; + const void* SymbolTag; + +public: + SymbolConjured(SymbolID sym, const Stmt* s, QualType t, unsigned count, + const void* symbolTag) + : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), + SymbolTag(symbolTag) {} + + const Stmt* getStmt() const { return S; } + unsigned getCount() const { return Count; } + const void* getTag() const { return SymbolTag; } + + QualType getType(ASTContext&) const; + + static void Profile(llvm::FoldingSetNodeID& profile, const Stmt* S, + QualType T, unsigned Count, const void* SymbolTag) { + profile.AddInteger((unsigned) ConjuredKind); + profile.AddPointer(S); + profile.Add(T); + profile.AddInteger(Count); + profile.AddPointer(SymbolTag); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, S, T, Count, SymbolTag); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == ConjuredKind; + } +}; + +// SymIntExpr - Represents symbolic expression like 'x' + 3. +class SymIntExpr : public SymExpr { + const SymExpr *LHS; + BinaryOperator::Opcode Op; + const llvm::APSInt& RHS; + QualType T; + +public: + SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, + const llvm::APSInt& rhs, QualType t) + : SymExpr(SymIntKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} + + // FIXME: We probably need to make this out-of-line to avoid redundant + // generation of virtual functions. + QualType getType(ASTContext& C) const { return T; } + + BinaryOperator::Opcode getOpcode() const { return Op; } + + const SymExpr *getLHS() const { return LHS; } + const llvm::APSInt &getRHS() const { return RHS; } + + static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, + BinaryOperator::Opcode op, const llvm::APSInt& rhs, + QualType t) { + ID.AddInteger((unsigned) SymIntKind); + ID.AddPointer(lhs); + ID.AddInteger(op); + ID.AddPointer(&rhs); + ID.Add(t); + } + + void Profile(llvm::FoldingSetNodeID& ID) { + Profile(ID, LHS, Op, RHS, T); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == SymIntKind; + } +}; + +// SymSymExpr - Represents symbolic expression like 'x' + 'y'. +class SymSymExpr : public SymExpr { + const SymExpr *LHS; + BinaryOperator::Opcode Op; + const SymExpr *RHS; + QualType T; + +public: + SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, + QualType t) + : SymExpr(SymSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} + + const SymExpr *getLHS() const { return LHS; } + const SymExpr *getRHS() const { return RHS; } + + // FIXME: We probably need to make this out-of-line to avoid redundant + // generation of virtual functions. + QualType getType(ASTContext& C) const { return T; } + + static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, + BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { + ID.AddInteger((unsigned) SymSymKind); + ID.AddPointer(lhs); + ID.AddInteger(op); + ID.AddPointer(rhs); + ID.Add(t); + } + + void Profile(llvm::FoldingSetNodeID& ID) { + Profile(ID, LHS, Op, RHS, T); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == SymSymKind; + } +}; + +class SymbolManager { + typedef llvm::FoldingSet<SymExpr> DataSetTy; + DataSetTy DataSet; + unsigned SymbolCounter; + llvm::BumpPtrAllocator& BPAlloc; + BasicValueFactory &BV; + ASTContext& Ctx; + +public: + SymbolManager(ASTContext& ctx, BasicValueFactory &bv, + llvm::BumpPtrAllocator& bpalloc) + : SymbolCounter(0), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} + + ~SymbolManager(); + + static bool canSymbolicate(QualType T); + + /// Make a unique symbol for MemRegion R according to its kind. + const SymbolRegionValue* getRegionValueSymbol(const MemRegion* R); + const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T, + unsigned VisitCount, + const void* SymbolTag = 0); + + const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount, + const void* SymbolTag = 0) { + return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag); + } + + const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, + const llvm::APSInt& rhs, QualType t); + + const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, + const llvm::APSInt& rhs, QualType t) { + return getSymIntExpr(&lhs, op, rhs, t); + } + + const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, + const SymExpr *rhs, QualType t); + + QualType getType(const SymExpr *SE) const { + return SE->getType(Ctx); + } + + ASTContext &getContext() { return Ctx; } + BasicValueFactory &getBasicVals() { return BV; } +}; + +class SymbolReaper { + typedef llvm::ImmutableSet<SymbolRef> SetTy; + typedef SetTy::Factory FactoryTy; + + FactoryTy F; + SetTy TheLiving; + SetTy TheDead; + LiveVariables& Liveness; + SymbolManager& SymMgr; + +public: + SymbolReaper(LiveVariables& liveness, SymbolManager& symmgr) + : TheLiving(F.GetEmptySet()), TheDead(F.GetEmptySet()), + Liveness(liveness), SymMgr(symmgr) {} + + bool isLive(SymbolRef sym); + + bool isLive(const Stmt* Loc, const Stmt* ExprVal) const { + return Liveness.isLive(Loc, ExprVal); + } + + bool isLive(const Stmt* Loc, const VarDecl* VD) const { + return Liveness.isLive(Loc, VD); + } + + void markLive(SymbolRef sym); + bool maybeDead(SymbolRef sym); + + typedef SetTy::iterator dead_iterator; + dead_iterator dead_begin() const { return TheDead.begin(); } + dead_iterator dead_end() const { return TheDead.end(); } + + bool hasDeadSymbols() const { + return !TheDead.isEmpty(); + } +}; + +class SymbolVisitor { +public: + // VisitSymbol - A visitor method invoked by + // GRStateManager::scanReachableSymbols. The method returns \c true if + // symbols should continue be scanned and \c false otherwise. + virtual bool VisitSymbol(SymbolRef sym) = 0; + virtual ~SymbolVisitor(); +}; + +} // end clang namespace + +namespace llvm { + llvm::raw_ostream& operator<<(llvm::raw_ostream& Out, + const clang::SymExpr *SE); +} +namespace std { + std::ostream& operator<<(std::ostream& Out, + const clang::SymExpr *SE); +} + +#endif diff --git a/include/clang/Analysis/PathSensitive/ValueManager.h b/include/clang/Analysis/PathSensitive/ValueManager.h new file mode 100644 index 0000000..89af975 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/ValueManager.h @@ -0,0 +1,103 @@ +//== ValueManager.h - Aggregate manager of symbols and SVals ----*- 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 ValueManager, a class that manages symbolic values +// and SVals created for use by GRExprEngine and related classes. It +// wraps SymbolManager, MemRegionManager, and BasicValueFactory. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_AGGREGATE_VALUE_MANAGER_H +#define LLVM_CLANG_ANALYSIS_AGGREGATE_VALUE_MANAGER_H + +#include "clang/Analysis/PathSensitive/MemRegion.h" +#include "clang/Analysis/PathSensitive/SVals.h" +#include "clang/Analysis/PathSensitive/BasicValueFactory.h" +#include "clang/Analysis/PathSensitive/SymbolManager.h" + +namespace llvm { class BumpPtrAllocator; } + +namespace clang { +class ValueManager { + + ASTContext &Context; + BasicValueFactory BasicVals; + + /// SymMgr - Object that manages the symbol information. + SymbolManager SymMgr; + + + MemRegionManager MemMgr; + +public: + ValueManager(llvm::BumpPtrAllocator &alloc, ASTContext &context) + : Context(context), BasicVals(Context, alloc), + SymMgr(Context, BasicVals, alloc), + MemMgr(alloc) {} + + // Accessors to submanagers. + + ASTContext &getContext() { return Context; } + const ASTContext &getContext() const { return Context; } + + BasicValueFactory &getBasicValueFactory() { return BasicVals; } + const BasicValueFactory &getBasicValueFactory() const { return BasicVals; } + + SymbolManager &getSymbolManager() { return SymMgr; } + const SymbolManager &getSymbolManager() const { return SymMgr; } + + MemRegionManager &getRegionManager() { return MemMgr; } + const MemRegionManager &getRegionManager() const { return MemMgr; } + + // Forwarding methods to SymbolManager. + + const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T, + unsigned VisitCount, + const void* SymbolTag = 0) { + return SymMgr.getConjuredSymbol(E, T, VisitCount, SymbolTag); + } + + const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount, + const void* SymbolTag = 0) { + return SymMgr.getConjuredSymbol(E, VisitCount, SymbolTag); + } + + // Aggregation methods that use multiple submanagers. + + Loc makeRegionVal(SymbolRef Sym) { + return Loc::MakeVal(MemMgr.getSymbolicRegion(Sym)); + } + + /// makeZeroVal - Construct an SVal representing '0' for the specified type. + SVal makeZeroVal(QualType T); + /// makeZeroArrayIndex - Construct an SVal representing '0' index for array + /// elements. + SVal makeZeroArrayIndex(); + + /// GetRegionValueSymbolVal - make a unique symbol for value of R. + SVal getRegionValueSymbolVal(const MemRegion* R); + + SVal getConjuredSymbolVal(const Expr *E, unsigned Count); + SVal getConjuredSymbolVal(const Expr* E, QualType T, unsigned Count); + + SVal getFunctionPointer(const FunctionDecl* FD); + + NonLoc makeNonLoc(SymbolRef sym); + + NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, + const llvm::APSInt& rhs, QualType T); + + NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, + const SymExpr *rhs, QualType T); + + NonLoc makeTruthVal(bool b, QualType T); +}; +} // end clang namespace +#endif + |
