diff options
Diffstat (limited to 'include/clang/Analysis/PathSensitive')
27 files changed, 2620 insertions, 2339 deletions
diff --git a/include/clang/Analysis/PathSensitive/AnalysisContext.h b/include/clang/Analysis/PathSensitive/AnalysisContext.h new file mode 100644 index 0000000000000..ffe282d3caa39 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/AnalysisContext.h @@ -0,0 +1,167 @@ +//=== AnalysisContext.h - Analysis context 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 AnalysisContext, a class that manages the analysis context +// data for path sensitive analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ANALYSISCONTEXT_H +#define LLVM_CLANG_ANALYSIS_ANALYSISCONTEXT_H + +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/DenseMap.h" + +namespace clang { + +class Decl; +class Stmt; +class CFG; +class LiveVariables; +class ParentMap; +class ImplicitParamDecl; + +/// AnalysisContext contains the context data for the function or method under +/// analysis. +class AnalysisContext { + const Decl *D; + + // AnalysisContext owns the following data. + CFG *cfg; + LiveVariables *liveness; + ParentMap *PM; + +public: + AnalysisContext(const Decl *d) : D(d), cfg(0), liveness(0), PM(0) {} + ~AnalysisContext(); + + const Decl *getDecl() { return D; } + Stmt *getBody(); + CFG *getCFG(); + ParentMap &getParentMap(); + LiveVariables *getLiveVariables(); + + /// Return the ImplicitParamDecl* associated with 'self' if this + /// AnalysisContext wraps an ObjCMethodDecl. Returns NULL otherwise. + const ImplicitParamDecl *getSelfDecl() const; +}; + +class AnalysisContextManager { + typedef llvm::DenseMap<const Decl*, AnalysisContext*> ContextMap; + ContextMap Contexts; +public: + ~AnalysisContextManager(); + + AnalysisContext *getContext(const Decl *D); +}; + +class LocationContext : public llvm::FoldingSetNode { +public: + enum ContextKind { StackFrame, Scope }; + +private: + ContextKind Kind; + AnalysisContext *Ctx; + const LocationContext *Parent; + +protected: + LocationContext(ContextKind k, AnalysisContext *ctx, + const LocationContext *parent) + : Kind(k), Ctx(ctx), Parent(parent) {} + +public: + ContextKind getKind() const { return Kind; } + + AnalysisContext *getAnalysisContext() const { return Ctx; } + + const LocationContext *getParent() const { return Parent; } + + const Decl *getDecl() const { return getAnalysisContext()->getDecl(); } + + CFG *getCFG() const { return getAnalysisContext()->getCFG(); } + + LiveVariables *getLiveVariables() const { + return getAnalysisContext()->getLiveVariables(); + } + + ParentMap &getParentMap() const { + return getAnalysisContext()->getParentMap(); + } + + const ImplicitParamDecl *getSelfDecl() const { + return Ctx->getSelfDecl(); + } + + void Profile(llvm::FoldingSetNodeID &ID) { + Profile(ID, Kind, Ctx, Parent); + } + + static void Profile(llvm::FoldingSetNodeID &ID, ContextKind k, + AnalysisContext *ctx, const LocationContext *parent); + + static bool classof(const LocationContext*) { return true; } +}; + +class StackFrameContext : public LocationContext { + const Stmt *CallSite; + +public: + StackFrameContext(AnalysisContext *ctx, const LocationContext *parent, + const Stmt *s) + : LocationContext(StackFrame, ctx, parent), CallSite(s) {} + + Stmt const *getCallSite() const { return CallSite; } + + void Profile(llvm::FoldingSetNodeID &ID) { + Profile(ID, getAnalysisContext(), getParent(), CallSite); + } + + static void Profile(llvm::FoldingSetNodeID &ID, AnalysisContext *ctx, + const LocationContext *parent, const Stmt *s); + + static bool classof(const LocationContext* Ctx) { + return Ctx->getKind() == StackFrame; + } +}; + +class ScopeContext : public LocationContext { + const Stmt *Enter; + +public: + ScopeContext(AnalysisContext *ctx, const LocationContext *parent, + const Stmt *s) + : LocationContext(Scope, ctx, parent), Enter(s) {} + + void Profile(llvm::FoldingSetNodeID &ID) { + Profile(ID, getAnalysisContext(), getParent(), Enter); + } + + static void Profile(llvm::FoldingSetNodeID &ID, AnalysisContext *ctx, + const LocationContext *parent, const Stmt *s); + + static bool classof(const LocationContext* Ctx) { + return Ctx->getKind() == Scope; + } +}; + +class LocationContextManager { + llvm::FoldingSet<LocationContext> Contexts; + +public: + StackFrameContext *getStackFrame(AnalysisContext *ctx, + const LocationContext *parent, + const Stmt *s); + + ScopeContext *getScope(AnalysisContext *ctx, const LocationContext *parent, + const Stmt *s); +}; + +} // end clang namespace +#endif diff --git a/include/clang/Analysis/PathSensitive/AnalysisManager.h b/include/clang/Analysis/PathSensitive/AnalysisManager.h new file mode 100644 index 0000000000000..e97f80576a8bd --- /dev/null +++ b/include/clang/Analysis/PathSensitive/AnalysisManager.h @@ -0,0 +1,140 @@ +//== AnalysisManager.h - Path sensitive analysis data manager ------*- 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 AnalysisManager class that manages the data and policy +// for path sensitive analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ANALYSISMANAGER_H +#define LLVM_CLANG_ANALYSIS_ANALYSISMANAGER_H + +#include "clang/Analysis/PathSensitive/BugReporter.h" +#include "clang/Analysis/PathSensitive/AnalysisContext.h" +#include "clang/Analysis/PathDiagnostic.h" + +namespace clang { + +class AnalysisManager : public BugReporterData { + AnalysisContextManager AnaCtxMgr; + LocationContextManager LocCtxMgr; + + ASTContext &Ctx; + Diagnostic &Diags; + const LangOptions &LangInfo; + + llvm::OwningPtr<PathDiagnosticClient> PD; + + // Configurable components creators. + StoreManagerCreator CreateStoreMgr; + ConstraintManagerCreator CreateConstraintMgr; + + enum AnalysisScope { ScopeTU, ScopeDecl } AScope; + + bool DisplayedFunction; + bool VisualizeEGDot; + bool VisualizeEGUbi; + bool PurgeDead; + + /// 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. + bool EagerlyAssume; + bool TrimGraph; + +public: + AnalysisManager(ASTContext &ctx, Diagnostic &diags, + const LangOptions &lang, PathDiagnosticClient *pd, + StoreManagerCreator storemgr, + ConstraintManagerCreator constraintmgr, + bool displayProgress, bool vizdot, bool vizubi, + bool purge, bool eager, bool trim) + + : Ctx(ctx), Diags(diags), LangInfo(lang), PD(pd), + CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr), + AScope(ScopeDecl), DisplayedFunction(!displayProgress), + VisualizeEGDot(vizdot), VisualizeEGUbi(vizubi), PurgeDead(purge), + EagerlyAssume(eager), TrimGraph(trim) {} + + StoreManagerCreator getStoreManagerCreator() { + return CreateStoreMgr; + }; + + ConstraintManagerCreator getConstraintManagerCreator() { + return CreateConstraintMgr; + } + + virtual ASTContext &getASTContext() { + return Ctx; + } + + virtual SourceManager &getSourceManager() { + return getASTContext().getSourceManager(); + } + + virtual Diagnostic &getDiagnostic() { + return Diags; + } + + const LangOptions &getLangOptions() const { + return LangInfo; + } + + virtual PathDiagnosticClient *getPathDiagnosticClient() { + return PD.get(); + } + + bool shouldVisualizeGraphviz() const { return VisualizeEGDot; } + + bool shouldVisualizeUbigraph() const { return VisualizeEGUbi; } + + bool shouldVisualize() const { + return VisualizeEGDot || VisualizeEGUbi; + } + + bool shouldTrimGraph() const { return TrimGraph; } + + bool shouldPurgeDead() const { return PurgeDead; } + + bool shouldEagerlyAssume() const { return EagerlyAssume; } + + void DisplayFunction(Decl *D); + + CFG *getCFG(Decl const *D) { + return AnaCtxMgr.getContext(D)->getCFG(); + } + + LiveVariables *getLiveVariables(Decl const *D) { + return AnaCtxMgr.getContext(D)->getLiveVariables(); + } + + ParentMap &getParentMap(Decl const *D) { + return AnaCtxMgr.getContext(D)->getParentMap(); + } + + // Get the top level stack frame. + StackFrameContext *getStackFrame(Decl const *D) { + return LocCtxMgr.getStackFrame(AnaCtxMgr.getContext(D), 0, 0); + } + + // Get a stack frame with parent. + StackFrameContext const *getStackFrame(Decl const *D, + LocationContext const *Parent, + Stmt const *S) { + return LocCtxMgr.getStackFrame(AnaCtxMgr.getContext(D), Parent, S); + } +}; + +} + +#endif diff --git a/include/clang/Analysis/PathSensitive/BasicValueFactory.h b/include/clang/Analysis/PathSensitive/BasicValueFactory.h index b694e9b299408..12f0ce2d50b7c 100644 --- a/include/clang/Analysis/PathSensitive/BasicValueFactory.h +++ b/include/clang/Analysis/PathSensitive/BasicValueFactory.h @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// // // This file defines BasicValueFactory, a class that manages the lifetime -// of APSInt objects and symbolic constraints used by GRExprEngine +// of APSInt objects and symbolic constraints used by GRExprEngine // and related classes. // //===----------------------------------------------------------------------===// @@ -24,25 +24,43 @@ #include "llvm/ADT/ImmutableList.h" namespace clang { - + + class GRState; + class CompoundValData : public llvm::FoldingSetNode { QualType T; llvm::ImmutableList<SVal> L; public: - CompoundValData(QualType t, llvm::ImmutableList<SVal> l) + 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(); } - + 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 LazyCompoundValData : public llvm::FoldingSetNode { + const GRState *state; + const TypedRegion *region; +public: + LazyCompoundValData(const GRState *st, const TypedRegion *r) + : state(st), region(r) {} + + const GRState *getState() const { return state; } + const TypedRegion *getRegion() const { return region; } + + static void Profile(llvm::FoldingSetNodeID& ID, const GRState *state, + const TypedRegion *region); + + void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, state, region); } +}; + class BasicValueFactory { typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt> > APSIntSetTy; @@ -56,44 +74,54 @@ class BasicValueFactory { llvm::ImmutableList<SVal>::Factory SValListFactory; llvm::FoldingSet<CompoundValData> CompoundValDataSet; + llvm::FoldingSet<LazyCompoundValData> LazyCompoundValDataSet; public: - BasicValueFactory(ASTContext& ctx, llvm::BumpPtrAllocator& Alloc) + BasicValueFactory(ASTContext& ctx, llvm::BumpPtrAllocator& Alloc) : Ctx(ctx), BPAlloc(Alloc), PersistentSVals(0), PersistentSValPairs(0), SValListFactory(Alloc) {} ~BasicValueFactory(); - ASTContext& getContext() const { return Ctx; } + 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 &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 &Convert(QualType T, const llvm::APSInt &From) { + assert(T->isIntegerType() || Loc::IsLocType(T)); + unsigned bitwidth = Ctx.getTypeSize(T); + bool isUnsigned = T->isUnsignedIntegerType() || Loc::IsLocType(T); - return getValue(From.getSExtValue(), - To.getBitWidth(), - To.isUnsigned()); + if (isUnsigned == From.isUnsigned() && bitwidth == From.getBitWidth()) + return From; + + return getValue(From.getSExtValue(), bitwidth, 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())); } @@ -103,44 +131,51 @@ public: 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 &getIntWithPtrWidth(uint64_t X, bool isUnsigned) { + return getValue(X, 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, + + const CompoundValData *getCompoundValData(QualType T, llvm::ImmutableList<SVal> Vals); - + + const LazyCompoundValData *getLazyCompoundValData(const GRState *state, + const TypedRegion *region); + llvm::ImmutableList<SVal> getEmptySValList() { return SValListFactory.GetEmptyList(); } - + llvm::ImmutableList<SVal> consVals(SVal X, llvm::ImmutableList<SVal> L) { return SValListFactory.Add(X, L); } @@ -148,13 +183,13 @@ public: 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); - + getPersistentSValPair(const SVal& V1, const SVal& V2); + const SVal* getPersistentSVal(SVal X); }; diff --git a/include/clang/Analysis/PathSensitive/BugReporter.h b/include/clang/Analysis/PathSensitive/BugReporter.h index 90fd9d8ebf45e..1434fce811d15 100644 --- a/include/clang/Analysis/PathSensitive/BugReporter.h +++ b/include/clang/Analysis/PathSensitive/BugReporter.h @@ -27,7 +27,7 @@ #include <list> namespace clang { - + class PathDiagnostic; class PathDiagnosticPiece; class PathDiagnosticClient; @@ -40,7 +40,7 @@ class GRState; class Stmt; class BugType; class ParentMap; - + //===----------------------------------------------------------------------===// // Interface for individual bug reports. //===----------------------------------------------------------------------===// @@ -48,22 +48,22 @@ class ParentMap; class BugReporterVisitor { public: virtual ~BugReporterVisitor(); - virtual PathDiagnosticPiece* VisitNode(const ExplodedNode<GRState>* N, - const ExplodedNode<GRState>* PrevN, + virtual PathDiagnosticPiece* VisitNode(const ExplodedNode* N, + const ExplodedNode* 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; + const ExplodedNode *EndNode; SourceRange R; - + protected: friend class BugReporter; friend class BugReportEquivClass; @@ -71,79 +71,78 @@ protected: 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; + virtual const ExplodedNode* + getOriginalNode(const ExplodedNode* N) = 0; }; - - BugReport(BugType& bt, const char* desc, const ExplodedNode<GRState> *n) + + BugReport(BugType& bt, const char* desc, const ExplodedNode *n) : BT(bt), Description(desc), EndNode(n) {} - + BugReport(BugType& bt, const char* shortDesc, const char* desc, - const ExplodedNode<GRState> *n) + const ExplodedNode *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; } - + const ExplodedNode* 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 Stmt* getStmt() 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); - + const ExplodedNode* 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 void getRanges(const SourceRange*& beg, const SourceRange*& end); - virtual PathDiagnosticPiece* VisitNode(const ExplodedNode<GRState>* N, - const ExplodedNode<GRState>* PrevN, + virtual PathDiagnosticPiece* VisitNode(const ExplodedNode* N, + const ExplodedNode* PrevN, BugReporterContext& BR); - + virtual void registerInitialVisitors(BugReporterContext& BRC, - const ExplodedNode<GRState>* N) {} + const ExplodedNode* 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: @@ -165,7 +164,7 @@ public: BugReport* operator*() const { return *impl; } BugReport* operator->() const { return *impl; } }; - + class const_iterator { std::list<BugReport*>::const_iterator impl; public: @@ -176,64 +175,70 @@ public: 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; + bool SuppressonSink; public: - BugType(const char *name, const char* cat) : Name(name), Category(cat) {} + BugType(const char *name, const char* cat) + : Name(name), Category(cat), SuppressonSink(false) {} 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); + /// isSuppressOnSink - Returns true if bug reports associated with this bug + /// type should be suppressed if the end node of the report is post-dominated + /// by a sink node. + bool isSuppressOnSink() const { return SuppressonSink; } + void setSuppressOnSink(bool x) { SuppressonSink = x; } + + virtual void FlushReports(BugReporter& 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) + RangedBugReport(BugType& D, const char* description, ExplodedNode *n) : BugReport(D, description, n) {} - + RangedBugReport(BugType& D, const char *shortDescription, - const char *description, ExplodedNode<GRState> *n) + const char *description, ExplodedNode *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) { - + void getRanges(const SourceRange*& beg, const SourceRange*& end) { + if (Ranges.empty()) { beg = NULL; end = NULL; @@ -244,7 +249,36 @@ public: } } }; - + +class EnhancedBugReport : public RangedBugReport { +public: + typedef void (*VisitorCreator)(BugReporterContext &BRcC, const void *data, + const ExplodedNode *N); + +private: + typedef std::vector<std::pair<VisitorCreator, const void*> > Creators; + Creators creators; + +public: + EnhancedBugReport(BugType& D, const char* description, ExplodedNode *n) + : RangedBugReport(D, description, n) {} + + EnhancedBugReport(BugType& D, const char *shortDescription, + const char *description, ExplodedNode *n) + : RangedBugReport(D, shortDescription, description, n) {} + + ~EnhancedBugReport() {} + + void registerInitialVisitors(BugReporterContext& BRC, const ExplodedNode* N) { + for (Creators::iterator I = creators.begin(), E = creators.end(); I!=E; ++I) + I->first(BRC, I->second, N); + } + + void addVisitorCreator(VisitorCreator creator, const void *data) { + creators.push_back(std::make_pair(creator, data)); + } +}; + //===----------------------------------------------------------------------===// // BugReporter and friends. //===----------------------------------------------------------------------===// @@ -252,15 +286,12 @@ public: class BugReporterData { public: virtual ~BugReporterData(); - virtual Diagnostic& getDiagnostic() = 0; - virtual PathDiagnosticClient* getPathDiagnosticClient() = 0; - virtual ASTContext& getContext() = 0; + virtual Diagnostic& getDiagnostic() = 0; + virtual PathDiagnosticClient* getPathDiagnosticClient() = 0; + virtual ASTContext& getASTContext() = 0; virtual SourceManager& getSourceManager() = 0; - virtual CFG* getCFG() = 0; - virtual ParentMap& getParentMap() = 0; - virtual LiveVariables* getLiveVariables() = 0; }; - + class BugReporter { public: enum Kind { BaseBRKind, GRBugReporterKind }; @@ -270,9 +301,9 @@ private: BugTypesTy::Factory F; BugTypesTy BugTypes; - const Kind kind; + const Kind kind; BugReporterData& D; - + void FlushReport(BugReportEquivClass& EQ); protected: @@ -281,40 +312,34 @@ protected: 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(); } - + + ASTContext& getContext() { return D.getASTContext(); } + 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); @@ -322,28 +347,28 @@ public: 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; } }; @@ -351,95 +376,87 @@ public: class GRBugReporter : public BugReporter { GRExprEngine& Eng; llvm::SmallSet<SymbolRef, 10> NotableSymbols; -public: +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; } + GRExprEngine &getEngine() { return Eng; } /// getGraph - Get the exploded graph created by the analysis engine /// for the analyzed method or function. - ExplodedGraph<GRState>& getGraph(); - + ExplodedGraph &getGraph(); + /// getStateManager - Return the state manager used by the analysis /// engine. - GRStateManager& getStateManager(); - + 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(); } - + visitor_iterator visitor_end() { return Callbacks.end(); } + + GRBugReporter& getBugReporter() { return BR; } + + ExplodedGraph &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; + + virtual BugReport::NodeResolver& getNodeResolver() = 0; }; class DiagBugReport : public RangedBugReport { @@ -448,19 +465,37 @@ class DiagBugReport : public RangedBugReport { 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); } - + + 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(); } }; +//===----------------------------------------------------------------------===// +//===----------------------------------------------------------------------===// + +namespace bugreporter { + +const Stmt *GetDerefExpr(const ExplodedNode *N); +const Stmt *GetReceiverExpr(const ExplodedNode *N); +const Stmt *GetDenomExpr(const ExplodedNode *N); +const Stmt *GetCalleeExpr(const ExplodedNode *N); +const Stmt *GetRetValExpr(const ExplodedNode *N); + +void registerTrackNullOrUndefValue(BugReporterContext& BRC, const void *stmt, + const ExplodedNode* N); + +} // end namespace clang::bugreporter + +//===----------------------------------------------------------------------===// + } // end clang namespace #endif diff --git a/include/clang/Analysis/PathSensitive/Checker.h b/include/clang/Analysis/PathSensitive/Checker.h new file mode 100644 index 0000000000000..4e00d69cdba1c --- /dev/null +++ b/include/clang/Analysis/PathSensitive/Checker.h @@ -0,0 +1,122 @@ +//== Checker.h - Abstract interface for checkers -----------------*- 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 Checker and CheckerVisitor, classes used for creating +// domain-specific checks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CHECKER +#define LLVM_CLANG_ANALYSIS_CHECKER +#include "clang/Analysis/Support/SaveAndRestore.h" +#include "clang/Analysis/PathSensitive/GRCoreEngine.h" +#include "clang/Analysis/PathSensitive/GRState.h" +#include "clang/Analysis/PathSensitive/GRExprEngine.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/ExprObjC.h" +#include "clang/AST/StmtCXX.h" +#include "clang/AST/StmtObjC.h" + +//===----------------------------------------------------------------------===// +// Checker interface. +//===----------------------------------------------------------------------===// + +namespace clang { + class GRExprEngine; + +class CheckerContext { + ExplodedNodeSet &Dst; + GRStmtNodeBuilder &B; + GRExprEngine &Eng; + ExplodedNode *Pred; + SaveAndRestore<bool> OldSink; + SaveAndRestore<const void*> OldTag; + SaveAndRestore<ProgramPoint::Kind> OldPointKind; + SaveOr OldHasGen; + +public: + CheckerContext(ExplodedNodeSet &dst, + GRStmtNodeBuilder &builder, + GRExprEngine &eng, + ExplodedNode *pred, + const void *tag, bool preVisit) + : Dst(dst), B(builder), Eng(eng), Pred(pred), + OldSink(B.BuildSinks), OldTag(B.Tag), + OldPointKind(B.PointKind), OldHasGen(B.HasGeneratedNode) { + //assert(Dst.empty()); // This is a fake assertion. + // See GRExprEngine::CheckerVisit(), CurrSet is repeatedly used. + B.Tag = tag; + if (preVisit) + B.PointKind = ProgramPoint::PreStmtKind; + } + + ~CheckerContext() { + if (!B.BuildSinks && !B.HasGeneratedNode) + Dst.Add(Pred); + } + + ConstraintManager &getConstraintManager() { + return Eng.getConstraintManager(); + } + ExplodedNodeSet &getNodeSet() { return Dst; } + GRStmtNodeBuilder &getNodeBuilder() { return B; } + ExplodedNode *&getPredecessor() { return Pred; } + const GRState *getState() { return B.GetState(Pred); } + + ASTContext &getASTContext() { + return Eng.getContext(); + } + + ExplodedNode *GenerateNode(const Stmt *S, bool markAsSink = false) { + return GenerateNode(S, getState(), markAsSink); + } + + ExplodedNode *GenerateNode(const Stmt* S, const GRState *state, + bool markAsSink = false) { + ExplodedNode *node = B.generateNode(S, state, Pred); + + if (markAsSink && node) + node->markAsSink(); + + return node; + } + + void addTransition(ExplodedNode *node) { + Dst.Add(node); + } + + void EmitReport(BugReport *R) { + Eng.getBugReporter().EmitReport(R); + } +}; + +class Checker { +private: + friend class GRExprEngine; + + void GR_Visit(ExplodedNodeSet &Dst, + GRStmtNodeBuilder &Builder, + GRExprEngine &Eng, + const Stmt *stmt, + ExplodedNode *Pred, bool isPrevisit) { + CheckerContext C(Dst, Builder, Eng, Pred, getTag(), isPrevisit); + assert(isPrevisit && "Only previsit supported for now."); + _PreVisit(C, stmt); + } + +public: + virtual ~Checker() {} + virtual void _PreVisit(CheckerContext &C, const Stmt *stmt) = 0; + virtual const void *getTag() = 0; +}; + +} // end clang namespace + +#endif + diff --git a/include/clang/Analysis/PathSensitive/CheckerVisitor.def b/include/clang/Analysis/PathSensitive/CheckerVisitor.def new file mode 100644 index 0000000000000..ff6528dae8f56 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/CheckerVisitor.def @@ -0,0 +1,18 @@ +//===-- CheckerVisitor.def - Metadata for CheckerVisitor ----------------*-===// +// +// 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 AST nodes accepted by the CheckerVisitor class. +// +//===---------------------------------------------------------------------===// + +PREVISIT(CallExpr) +PREVISIT(ObjCMessageExpr) +PREVISIT(BinaryOperator) + +#undef PREVISIT diff --git a/include/clang/Analysis/PathSensitive/CheckerVisitor.h b/include/clang/Analysis/PathSensitive/CheckerVisitor.h new file mode 100644 index 0000000000000..e74f49c9a761f --- /dev/null +++ b/include/clang/Analysis/PathSensitive/CheckerVisitor.h @@ -0,0 +1,59 @@ +//== CheckerVisitor.h - Abstract visitor for checkers ------------*- 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 CheckerVisitor. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CHECKERVISITOR +#define LLVM_CLANG_ANALYSIS_CHECKERVISITOR +#include "clang/Analysis/PathSensitive/Checker.h" + +namespace clang { + +//===----------------------------------------------------------------------===// +// Checker visitor interface. Used by subclasses of Checker to specify their +// own checker visitor logic. +//===----------------------------------------------------------------------===// + +/// CheckerVisitor - This class implements a simple visitor for Stmt subclasses. +/// Since Expr derives from Stmt, this also includes support for visiting Exprs. +template<typename ImplClass> +class CheckerVisitor : public Checker { +public: + virtual void _PreVisit(CheckerContext &C, const Stmt *stmt) { + PreVisit(C, stmt); + } + + void PreVisit(CheckerContext &C, const Stmt *S) { + switch (S->getStmtClass()) { + default: + assert(false && "Unsupport statement."); + return; + case Stmt::CompoundAssignOperatorClass: + static_cast<ImplClass*>(this)->PreVisitBinaryOperator(C, + static_cast<const BinaryOperator*>(S)); + break; +#define PREVISIT(NAME) \ +case Stmt::NAME ## Class:\ +static_cast<ImplClass*>(this)->PreVisit ## NAME(C,static_cast<const NAME*>(S));\ +break; +#include "clang/Analysis/PathSensitive/CheckerVisitor.def" + } + } + +#define PREVISIT(NAME) \ +void PreVisit ## NAME(CheckerContext &C, const NAME* S) {} +#include "clang/Analysis/PathSensitive/CheckerVisitor.def" +}; + +} // end clang namespace + +#endif + diff --git a/include/clang/Analysis/PathSensitive/ConstraintManager.h b/include/clang/Analysis/PathSensitive/ConstraintManager.h index 689bebb450f44..37a14083ac558 100644 --- a/include/clang/Analysis/PathSensitive/ConstraintManager.h +++ b/include/clang/Analysis/PathSensitive/ConstraintManager.h @@ -30,26 +30,32 @@ class SVal; class ConstraintManager { public: virtual ~ConstraintManager(); - virtual const GRState *Assume(const GRState *state, SVal Cond, + virtual const GRState *Assume(const GRState *state, DefinedSVal Cond, bool Assumption) = 0; - virtual const GRState *AssumeInBound(const GRState *state, SVal Idx, - SVal UpperBound, bool Assumption) = 0; + virtual const GRState *AssumeInBound(const GRState *state, DefinedSVal Idx, + DefinedSVal UpperBound, bool Assumption) = 0; + + std::pair<const GRState*, const GRState*> AssumeDual(const GRState *state, + DefinedSVal Cond) { + return std::make_pair(Assume(state, Cond, true), + Assume(state, Cond, false)); + } virtual const llvm::APSInt* getSymVal(const GRState *state, SymbolRef sym) const = 0; - virtual bool isEqual(const GRState *state, SymbolRef sym, + virtual bool isEqual(const GRState *state, SymbolRef sym, const llvm::APSInt& V) const = 0; virtual const GRState *RemoveDeadBindings(const GRState *state, SymbolReaper& SymReaper) = 0; - virtual void print(const GRState *state, llvm::raw_ostream& Out, + virtual void print(const GRState *state, llvm::raw_ostream& Out, const char* nl, const char *sep) = 0; virtual void EndPath(const GRState *state) {} - + /// 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 diff --git a/include/clang/Analysis/PathSensitive/Environment.h b/include/clang/Analysis/PathSensitive/Environment.h index 6f8a126427699..6d5c5678e59b1 100644 --- a/include/clang/Analysis/PathSensitive/Environment.h +++ b/include/clang/Analysis/PathSensitive/Environment.h @@ -26,125 +26,78 @@ namespace clang { +class AnalysisContext; class EnvironmentManager; class ValueManager; class LiveVariables; + class Environment { private: friend class EnvironmentManager; - + // Type definitions. typedef llvm::ImmutableMap<const Stmt*,SVal> BindingsTy; // Data. - BindingsTy SubExprBindings; - BindingsTy BlkExprBindings; - - Environment(BindingsTy seb, BindingsTy beb) - : SubExprBindings(seb), BlkExprBindings(beb) {} - + BindingsTy ExprBindings; + AnalysisContext *ACtx; + + Environment(BindingsTy eb, AnalysisContext *aCtx) + : ExprBindings(eb), ACtx(aCtx) {} + 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(const Stmt* E) const { - const SVal* X = SubExprBindings.lookup(cast<Expr>(E)); - return X ? *X : UnknownVal(); - } - - SVal LookupBlkExpr(const Stmt* E) const { - const SVal* X = BlkExprBindings.lookup(E); - return X ? *X : UnknownVal(); - } - + typedef BindingsTy::iterator iterator; + iterator begin() const { return ExprBindings.begin(); } + iterator end() const { return ExprBindings.end(); } + SVal LookupExpr(const Stmt* E) const { - const SVal* X = SubExprBindings.lookup(E); - if (X) return *X; - X = BlkExprBindings.lookup(E); + const SVal* X = ExprBindings.lookup(E); return X ? *X : UnknownVal(); } - + SVal GetSVal(const Stmt* Ex, ValueManager& ValMgr) const; - SVal GetBlkExprSVal(const Stmt* Ex, ValueManager& ValMgr) const; - + + AnalysisContext &getAnalysisContext() const { return *ACtx; } + /// 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); + E->ExprBindings.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; + return ExprBindings == RHS.ExprBindings; } }; - + 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, const Stmt* E) { - return Environment(Env.SubExprBindings, F.Remove(Env.BlkExprBindings, E)); - } - - Environment RemoveSubExpr(const Environment& Env, const Stmt* E) { - return Environment(F.Remove(Env.SubExprBindings, E), Env.BlkExprBindings); + Environment getInitialEnvironment(AnalysisContext *ACtx) { + return Environment(F.GetEmptyMap(), ACtx); } - - Environment AddBlkExpr(const Environment& Env, const Stmt *E, SVal V) { - return Environment(Env.SubExprBindings, F.Add(Env.BlkExprBindings, E, V)); - } - - Environment AddSubExpr(const Environment& Env, const 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, const 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); + Environment BindExpr(Environment Env, const Stmt *S, SVal V, + bool Invalidate); + Environment RemoveDeadBindings(Environment Env, const Stmt *S, + SymbolReaper &SymReaper, const GRState *ST, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots); }; - + } // end clang namespace #endif diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h index 8494d935650d0..a7bbdf939f877 100644 --- a/include/clang/Analysis/PathSensitive/ExplodedGraph.h +++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h @@ -16,6 +16,7 @@ #define LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH #include "clang/Analysis/ProgramPoint.h" +#include "clang/Analysis/PathSensitive/AnalysisContext.h" #include "clang/AST/Decl.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/FoldingSet.h" @@ -25,193 +26,158 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/Support/Casting.h" +#include "clang/Analysis/Support/BumpVector.h" namespace clang { -class GRCoreEngineImpl; -class ExplodedNodeImpl; +class GRState; class CFG; class ASTContext; - -class GRStmtNodeBuilderImpl; -class GRBranchNodeBuilderImpl; -class GRIndirectGotoNodeBuilderImpl; -class GRSwitchNodeBuilderImpl; -class GREndPathNodebuilderImpl; +class ExplodedGraph; //===----------------------------------------------------------------------===// // 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 ExplodedNode : public llvm::FoldingSetNode { + friend class ExplodedGraph; + friend class GRCoreEngine; + friend class GRStmtNodeBuilder; + friend class GRBranchNodeBuilder; + friend class GRIndirectGotoNodeBuilder; + friend class GRSwitchNodeBuilder; + friend class GREndPathNodeBuilder; + 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()); + ExplodedNode *getNode() const { + return reinterpret_cast<ExplodedNode*>(getPtr()); } - + public: NodeGroup() : P(0) {} - - ~NodeGroup(); - - ExplodedNodeImpl** begin() const; - - ExplodedNodeImpl** end() const; - + + ExplodedNode **begin() const; + + ExplodedNode **end() const; + unsigned size() const; - - bool empty() const { return size() == 0; } - - void addNode(ExplodedNodeImpl* N); - + + bool empty() const { return (P & ~Mask) == 0; } + + void addNode(ExplodedNode* N, ExplodedGraph &G); + void setFlag() { - assert (P == 0); + 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; - + const GRState* 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: - + + explicit ExplodedNode(const ProgramPoint& loc, const GRState* state) + : Location(loc), State(state) {} + /// 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); + const LocationContext *getLocationContext() const { + return getLocation().getLocationContext(); } -}; + const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } -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); + CFG &getCFG() const { return *getLocationContext()->getCFG(); } + + ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} + + LiveVariables &getLiveVariables() const { + return *getLocationContext()->getLiveVariables(); } - - // Profiling (for FoldingSet). - - static inline void Profile(llvm::FoldingSetNodeID& ID, - const ProgramPoint& Loc, - const StateTy* state) { + + const GRState* getState() const { return State; } + + template <typename T> + const T* getLocationAs() const { return llvm::dyn_cast<T>(&Location); } + + static void Profile(llvm::FoldingSetNodeID &ID, + const ProgramPoint& Loc, const GRState* state) { ID.Add(Loc); - GRTrait<StateTy>::Profile(ID, state); + ID.AddPointer(state); } - - inline void Profile(llvm::FoldingSetNodeID& ID) const { + + void Profile(llvm::FoldingSetNodeID& ID) const { Profile(ID, getLocation(), getState()); } - - void addPredecessor(ExplodedNode* V) { - ExplodedNodeImpl::addPredecessor(V); - } - + + /// addPredeccessor - Adds a predecessor to the current node, and + /// in tandem add this node as a successor of the other node. + void addPredecessor(ExplodedNode* V, ExplodedGraph &G); + + 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(); } + 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(); } + pred_iterator pred_begin() { return Preds.begin(); } + pred_iterator pred_end() { return 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(); } + succ_iterator succ_begin() { return Succs.begin(); } + succ_iterator succ_end() { return Succs.end(); } const_succ_iterator succ_begin() const { return const_cast<ExplodedNode*>(this)->succ_begin(); @@ -219,23 +185,40 @@ public: const_succ_iterator succ_end() const { return const_cast<ExplodedNode*>(this)->succ_end(); } + + // For debugging. + +public: + + class Auditor { + public: + virtual ~Auditor(); + virtual void AddEdge(ExplodedNode* Src, ExplodedNode* Dst) = 0; + }; + + static void SetAuditor(Auditor* A); }; -class InterExplodedGraphMapImpl; +// FIXME: Is this class necessary? +class InterExplodedGraphMap { + llvm::DenseMap<const ExplodedNode*, ExplodedNode*> M; + friend class ExplodedGraph; -class ExplodedGraphImpl { +public: + ExplodedNode* getMappedNode(const ExplodedNode* N) const; + + InterExplodedGraphMap() {}; + virtual ~InterExplodedGraphMap() {} +}; + +class ExplodedGraph { protected: - friend class GRCoreEngineImpl; - friend class GRStmtNodeBuilderImpl; - friend class GRBranchNodeBuilderImpl; - friend class GRIndirectGotoNodeBuilderImpl; - friend class GRSwitchNodeBuilderImpl; - friend class GREndPathNodeBuilderImpl; - + friend class GRCoreEngine; + // Type definitions. - typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; - typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; - + typedef llvm::SmallVector<ExplodedNode*,2> RootsTy; + typedef llvm::SmallVector<ExplodedNode*,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 @@ -245,338 +228,199 @@ protected: /// 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; - + + /// Nodes - The nodes in the graph. + llvm::FoldingSet<ExplodedNode> Nodes; + + /// BVC - Allocator and context for allocating nodes and their predecessor + /// and successor groups. + BumpVectorContext BVC; + /// 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; +public: + /// 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. + + ExplodedNode* getNode(const ProgramPoint& L, const GRState *State, + bool* IsNew = 0); + + ExplodedGraph* MakeEmptyGraph() const { + return new ExplodedGraph(Ctx); + } /// addRoot - Add an untyped node to the set of roots. - ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { + ExplodedNode* addRoot(ExplodedNode* V) { Roots.push_back(V); return V; } /// addEndOfPath - Add an untyped node to the set of EOP nodes. - ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { + ExplodedNode* addEndOfPath(ExplodedNode* 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() {} + ExplodedGraph(ASTContext& ctx) : Ctx(ctx), NumNodes(0) {} + + ~ExplodedGraph() {} 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 ExplodedNode NodeTy; + typedef llvm::FoldingSet<ExplodedNode> AllNodesTy; typedef NodeTy** roots_iterator; - typedef const NodeTy** const_roots_iterator; + typedef NodeTy* const * 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(); - } + typedef NodeTy* const * const_eop_iterator; + typedef AllNodesTy::iterator node_iterator; + typedef AllNodesTy::const_iterator const_node_iterator; - 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(); - } + node_iterator nodes_begin() { return Nodes.begin(); } - 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>*> + 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 Roots.begin(); } + + roots_iterator roots_end() { return Roots.end(); } + + const_roots_iterator roots_begin() const { return Roots.begin(); } + + const_roots_iterator roots_end() const { return Roots.end(); } + + eop_iterator eop_begin() { return EndNodes.begin(); } + + eop_iterator eop_end() { return EndNodes.end(); } + + const_eop_iterator eop_begin() const { return EndNodes.begin(); } + + const_eop_iterator eop_end() const { return EndNodes.end(); } + + llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } + BumpVectorContext &getNodeAllocator() { return BVC; } + + ASTContext& getContext() { return Ctx; } + + typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap; + + std::pair<ExplodedGraph*, InterExplodedGraphMap*> 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()); - } + llvm::DenseMap<const void*, const void*> *InverseMap = 0) const; + + ExplodedGraph* TrimInternal(const ExplodedNode* const * NBeg, + const ExplodedNode* const * NEnd, + InterExplodedGraphMap *M, + llvm::DenseMap<const void*, const void*> *InverseMap) const; }; -template <typename StateTy> class ExplodedNodeSet { - - typedef ExplodedNode<StateTy> NodeTy; - typedef llvm::SmallPtrSet<NodeTy*,5> ImplTy; + typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy; ImplTy Impl; - + public: - ExplodedNodeSet(NodeTy* N) { - assert (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()); + ExplodedNodeSet(ExplodedNode* N) { + assert (N && !static_cast<ExplodedNode*>(N)->isSink()); Impl.insert(N); } - + ExplodedNodeSet() {} - - inline void Add(NodeTy* N) { - if (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()) Impl.insert(N); + + inline void Add(ExplodedNode* N) { + if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); + } + + ExplodedNodeSet& operator=(const ExplodedNodeSet &X) { + Impl = X.Impl; + return *this; } - - typedef typename ImplTy::iterator iterator; - typedef typename ImplTy::const_iterator const_iterator; + + typedef ImplTy::iterator iterator; + typedef 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; + template<> struct GraphTraits<clang::ExplodedNode*> { + typedef clang::ExplodedNode NodeType; + typedef 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; + + template<> struct GraphTraits<const clang::ExplodedNode*> { + typedef const clang::ExplodedNode NodeType; + typedef NodeType::const_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 index eca591d4af0ec..015c82e80bb59 100644 --- a/include/clang/Analysis/PathSensitive/GRAuditor.h +++ b/include/clang/Analysis/PathSensitive/GRAuditor.h @@ -1,5 +1,5 @@ //==- GRAuditor.h - Observers of the creation of ExplodedNodes------*- C++ -*-// -// +// // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source @@ -18,22 +18,18 @@ #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 ExplodedNode; +class GRStateManager; + class GRAuditor { public: - typedef ExplodedNode<STATE> NodeTy; - typedef typename STATE::ManagerTy ManagerTy; - virtual ~GRAuditor() {} - virtual bool Audit(NodeTy* N, ManagerTy& M) = 0; + virtual bool Audit(ExplodedNode* N, GRStateManager& M) = 0; }; - - + + } // end clang namespace #endif diff --git a/include/clang/Analysis/PathSensitive/GRBlockCounter.h b/include/clang/Analysis/PathSensitive/GRBlockCounter.h index b4fd2704b81a6..67ed9532db02b 100644 --- a/include/clang/Analysis/PathSensitive/GRBlockCounter.h +++ b/include/clang/Analysis/PathSensitive/GRBlockCounter.h @@ -1,5 +1,5 @@ //==- GRBlockCounter.h - ADT for counting block visits -------------*- C++ -*-// -// +// // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source @@ -24,27 +24,27 @@ namespace clang { class GRBlockCounter { void* Data; - - GRBlockCounter(void* D) : Data(D) {} + + 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 index 0fbdbde55bd5c..02e0b0275e4e0 100644 --- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h +++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h @@ -1,5 +1,5 @@ -//==- GRCoreEngine.h - Path-Sensitive Dataflow Engine ------------------*- C++ -*-// -// +//==- GRCoreEngine.h - Path-Sensitive Dataflow Engine --------------*- C++ -*-// +// // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source @@ -20,646 +20,416 @@ #include "clang/Analysis/PathSensitive/GRWorkList.h" #include "clang/Analysis/PathSensitive/GRBlockCounter.h" #include "clang/Analysis/PathSensitive/GRAuditor.h" +#include "clang/Analysis/PathSensitive/GRSubEngine.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 +/// GRCoreEngine - 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) +/// The template class GRCoreEngine (which subclasses GRCoreEngine) /// 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; - +class GRCoreEngine { + friend class GRStmtNodeBuilder; + friend class GRBranchNodeBuilder; + friend class GRIndirectGotoNodeBuilder; + friend class GRSwitchNodeBuilder; + friend class GREndPathNodeBuilder; + + GRSubEngine& SubEngine; + /// G - The simulation graph. Each node is a (location,state) pair. - llvm::OwningPtr<ExplodedGraphImpl> G; - + llvm::OwningPtr<ExplodedGraph> 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 GenerateNode(const ProgramPoint& Loc, const GRState* State, + ExplodedNode* Pred); + + void HandleBlockEdge(const BlockEdge& E, ExplodedNode* Pred); + void HandleBlockEntrance(const BlockEntrance& E, ExplodedNode* Pred); + void HandleBlockExit(CFGBlock* B, ExplodedNode* Pred); void HandlePostStmt(const PostStmt& S, CFGBlock* B, - unsigned StmtIdx, ExplodedNodeImpl *Pred); - + unsigned StmtIdx, ExplodedNode *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; + ExplodedNode* Pred); + + /// Get the initial state from the subengine. + const GRState* getInitialState(const LocationContext *InitLoc) { + return SubEngine.getInitialState(InitLoc); + } + + void ProcessEndPath(GREndPathNodeBuilder& Builder); + + void ProcessStmt(Stmt* S, GRStmtNodeBuilder& Builder); + - virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilderImpl& Builder) = 0; + bool ProcessBlockEntrance(CFGBlock* Blk, const GRState* State, + GRBlockCounter BC); - virtual void ProcessBranch(Stmt* Condition, Stmt* Terminator, - GRBranchNodeBuilderImpl& Builder) = 0; - virtual void ProcessIndirectGoto(GRIndirectGotoNodeBuilderImpl& Builder) = 0; - - virtual void ProcessSwitch(GRSwitchNodeBuilderImpl& Builder) = 0; + void ProcessBranch(Stmt* Condition, Stmt* Terminator, + GRBranchNodeBuilder& Builder); + + + void ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder); + + + void ProcessSwitch(GRSwitchNodeBuilder& Builder); private: - GRCoreEngineImpl(const GRCoreEngineImpl&); // Do not implement. - GRCoreEngineImpl& operator=(const GRCoreEngineImpl&); - -protected: - GRCoreEngineImpl(ExplodedGraphImpl* g, GRWorkList* wl) - : G(g), WList(wl), BCounterFactory(g->getAllocator()) {} - + GRCoreEngine(const GRCoreEngine&); // Do not implement. + GRCoreEngine& operator=(const GRCoreEngine&); + public: + /// Construct a GRCoreEngine object to analyze the provided CFG using + /// a DFS exploration of the exploded graph. + GRCoreEngine(ASTContext& ctx, GRSubEngine& subengine) + : SubEngine(subengine), G(new ExplodedGraph(ctx)), + WList(GRWorkList::MakeBFS()), + BCounterFactory(G->getAllocator()) {} + + /// 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(ASTContext& ctx, GRWorkList* wlist, GRSubEngine& subengine) + : SubEngine(subengine), G(new ExplodedGraph(ctx)), WList(wlist), + BCounterFactory(G->getAllocator()) {} + + ~GRCoreEngine() { + delete WList; + } + + /// getGraph - Returns the exploded graph. + ExplodedGraph& getGraph() { return *G.get(); } + + /// takeGraph - Returns the exploded graph. Ownership of the graph is + /// transfered to the caller. + ExplodedGraph* takeGraph() { return G.take(); } + /// 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(); } + bool ExecuteWorkList(const LocationContext *L, unsigned Steps); }; - -class GRStmtNodeBuilderImpl { - GRCoreEngineImpl& Eng; + +class GRStmtNodeBuilder { + GRCoreEngine& Eng; CFGBlock& B; const unsigned Idx; - ExplodedNodeImpl* Pred; - ExplodedNodeImpl* LastNode; - - typedef llvm::SmallPtrSet<ExplodedNodeImpl*,5> DeferredTy; + ExplodedNode* Pred; + ExplodedNode* LastNode; + GRStateManager& Mgr; + GRAuditor* Auditor; + +public: + bool PurgingDeadSymbols; + bool BuildSinks; + bool HasGeneratedNode; + ProgramPoint::Kind PointKind; + const void *Tag; + + const GRState* CleanedState; + + + typedef llvm::SmallPtrSet<ExplodedNode*,5> DeferredTy; DeferredTy Deferred; - - void GenerateAutoTransition(ExplodedNodeImpl* N); - + + void GenerateAutoTransition(ExplodedNode* N); + public: - GRStmtNodeBuilderImpl(CFGBlock* b, unsigned idx, - ExplodedNodeImpl* N, GRCoreEngineImpl* e); - - ~GRStmtNodeBuilderImpl(); - - ExplodedNodeImpl* getBasePredecessor() const { return Pred; } - - ExplodedNodeImpl* getLastNode() const { + GRStmtNodeBuilder(CFGBlock* b, unsigned idx, ExplodedNode* N, + GRCoreEngine* e, GRStateManager &mgr); + + ~GRStmtNodeBuilder(); + + ExplodedNode* getBasePredecessor() const { return Pred; } + + ExplodedNode* getLastNode() const { return LastNode ? (LastNode->isSink() ? NULL : LastNode) : NULL; } - + + // FIXME: This should not be exposed. + GRWorkList *getWorkList() { return Eng.WList; } + + void SetCleanedState(const GRState* St) { + CleanedState = St; + } + 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); + ExplodedNode* generateNode(PostStmt PP,const GRState* St,ExplodedNode* Pred) { + HasGeneratedNode = true; + return generateNodeInternal(PP, St, Pred); } - - 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); + + ExplodedNode* generateNode(const Stmt *S, const GRState *St, + ExplodedNode *Pred, ProgramPoint::Kind K) { + HasGeneratedNode = true; + + if (PurgingDeadSymbols) + K = ProgramPoint::PostPurgeDeadSymbolsKind; + + return generateNodeInternal(S, St, Pred, K, Tag); } - + + ExplodedNode* generateNode(const Stmt *S, const GRState *St, + ExplodedNode *Pred) { + return generateNode(S, St, Pred, PointKind); + } + + ExplodedNode* + generateNodeInternal(const ProgramPoint &PP, const GRState* State, + ExplodedNode* Pred); + + ExplodedNode* + generateNodeInternal(const Stmt* S, const GRState* State, ExplodedNode* Pred, + ProgramPoint::Kind K = ProgramPoint::PostStmtKind, + const void *tag = 0); + /// 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); - } + void setAuditor(GRAuditor* A) { Auditor = A; } - - GRBlockCounter getBlockCounter() const { - return NB.getBlockCounter(); - } - - unsigned getCurrentBlockCount() const { - return NB.getCurrentBlockCount(); - } - - const StateTy* GetState(NodeTy* Pred) const { - if ((ExplodedNodeImpl*) Pred == NB.getBasePredecessor()) + const GRState* GetState(ExplodedNode* Pred) const { + if ((ExplodedNode*) Pred == 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) { + + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, + const GRState* 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); - + + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, + const GRState* St, ProgramPoint::Kind K) { + + const GRState* 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) { + + ExplodedNode* 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) { + + ExplodedNode* MakeSinkNode(ExplodedNodeSet& Dst, Stmt* S, + ExplodedNode* Pred, const GRState* St) { bool Tmp = BuildSinks; BuildSinks = true; - NodeTy* N = MakeNode(Dst, S, Pred, St); + ExplodedNode* 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; + +class GRBranchNodeBuilder { + GRCoreEngine& Eng; CFGBlock* Src; CFGBlock* DstT; CFGBlock* DstF; - ExplodedNodeImpl* Pred; + ExplodedNode* Pred; - typedef llvm::SmallVector<ExplodedNodeImpl*,3> DeferredTy; + typedef llvm::SmallVector<ExplodedNode*,3> DeferredTy; DeferredTy Deferred; - + bool GeneratedTrue; bool GeneratedFalse; - + bool InFeasibleTrue; + bool InFeasibleFalse; + public: - GRBranchNodeBuilderImpl(CFGBlock* src, CFGBlock* dstT, CFGBlock* dstF, - ExplodedNodeImpl* pred, GRCoreEngineImpl* e) + GRBranchNodeBuilder(CFGBlock* src, CFGBlock* dstT, CFGBlock* dstF, + ExplodedNode* pred, GRCoreEngine* 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; } + GeneratedTrue(false), GeneratedFalse(false), + InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {} + + ~GRBranchNodeBuilder(); + + ExplodedNode* getPredecessor() const { return Pred; } + + const ExplodedGraph& getGraph() const { return *Eng.G; } + GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} - - ExplodedNodeImpl* generateNodeImpl(const void* State, bool branch); - + + ExplodedNode* generateNode(const GRState* 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(); + void markInfeasible(bool branch) { + if (branch) + InFeasibleTrue = GeneratedTrue = true; + else + InFeasibleFalse = GeneratedFalse = true; } - NodeTy* generateNode(const StateTy* St, bool branch) { - return static_cast<NodeTy*>(NB.generateNodeImpl(St, branch)); + bool isFeasible(bool branch) { + return branch ? !InFeasibleTrue : !InFeasibleFalse; } - - GRBlockCounter getBlockCounter() const { - return NB.getBlockCounter(); - } - - CFGBlock* getTargetBlock(bool branch) const { - return NB.getTargetBlock(branch); - } - - void markInfeasible(bool branch) { - NB.markInfeasible(branch); + + const GRState* getState() const { + return getPredecessor()->getState(); } }; - -class GRIndirectGotoNodeBuilderImpl { - GRCoreEngineImpl& Eng; + +class GRIndirectGotoNodeBuilder { + GRCoreEngine& Eng; CFGBlock* Src; CFGBlock& DispatchBlock; Expr* E; - ExplodedNodeImpl* Pred; + ExplodedNode* Pred; + public: - GRIndirectGotoNodeBuilderImpl(ExplodedNodeImpl* pred, CFGBlock* src, - Expr* e, CFGBlock* dispatch, - GRCoreEngineImpl* eng) + GRIndirectGotoNodeBuilder(ExplodedNode* pred, CFGBlock* src, Expr* e, + CFGBlock* dispatch, GRCoreEngine* eng) : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} - - class Iterator { + class iterator { CFGBlock::succ_iterator I; - - friend class GRIndirectGotoNodeBuilderImpl; - Iterator(CFGBlock::succ_iterator i) : I(i) {} + + friend class GRIndirectGotoNodeBuilder; + iterator(CFGBlock::succ_iterator i) : I(i) {} public: - - Iterator& operator++() { ++I; return *this; } - bool operator!=(const Iterator& X) const { return I != X.I; } - + + 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; + iterator begin() { return iterator(DispatchBlock.succ_begin()); } + iterator end() { return iterator(DispatchBlock.succ_end()); } -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()); - } + ExplodedNode* generateNode(const iterator& I, const GRState* State, + bool isSink = false); + + Expr* getTarget() const { return E; } + + const GRState* getState() const { return Pred->State; } }; - -class GRSwitchNodeBuilderImpl { - GRCoreEngineImpl& Eng; + +class GRSwitchNodeBuilder { + GRCoreEngine& Eng; CFGBlock* Src; Expr* Condition; - ExplodedNodeImpl* Pred; + ExplodedNode* Pred; + public: - GRSwitchNodeBuilderImpl(ExplodedNodeImpl* pred, CFGBlock* src, - Expr* condition, GRCoreEngineImpl* eng) + GRSwitchNodeBuilder(ExplodedNode* pred, CFGBlock* src, + Expr* condition, GRCoreEngine* eng) : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} - - class Iterator { + + class iterator { CFGBlock::succ_reverse_iterator I; - - friend class GRSwitchNodeBuilderImpl; - Iterator(CFGBlock::succ_reverse_iterator i) : I(i) {} + + friend class GRSwitchNodeBuilder; + iterator(CFGBlock::succ_reverse_iterator i) : I(i) {} + public: - - Iterator& operator++() { ++I; return *this; } - bool operator!=(const Iterator& X) const { return I != X.I; } - + 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); - + + iterator begin() { return iterator(Src->succ_rbegin()+1); } + iterator end() { return iterator(Src->succ_rend()); } + + ExplodedNode* generateCaseStmtNode(const iterator& I, const GRState* State); + + ExplodedNode* generateDefaultCaseNode(const GRState* State, + bool isSink = false); + 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()); - } + const GRState* getState() const { return Pred->State; } }; - -class GREndPathNodeBuilderImpl { - GRCoreEngineImpl& Eng; +class GREndPathNodeBuilder { + GRCoreEngine& Eng; CFGBlock& B; - ExplodedNodeImpl* Pred; + ExplodedNode* 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; } -}; + GREndPathNodeBuilder(CFGBlock* b, ExplodedNode* N, GRCoreEngine* e) + : Eng(*e), B(*b), Pred(N), HasGeneratedNode(false) {} + ~GREndPathNodeBuilder(); + + ExplodedNode* getPredecessor() const { return Pred; } -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)); + return Eng.WList->getBlockCounter(); } - - 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); + unsigned getCurrentBlockCount() const { + return getBlockCounter().getNumVisited(B.getBlockID()); } - 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()); + ExplodedNode* generateNode(const GRState* State, const void *tag = 0, + ExplodedNode *P = 0); + + CFGBlock* getBlock() const { return &B; } + + const GRState* getState() const { + return getPredecessor()->getState(); } }; diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index f05bc680a7e25..e5c61e68c77c1 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -16,111 +16,86 @@ #ifndef LLVM_CLANG_ANALYSIS_GREXPRENGINE #define LLVM_CLANG_ANALYSIS_GREXPRENGINE +#include "clang/Analysis/PathSensitive/AnalysisManager.h" +#include "clang/Analysis/PathSensitive/GRSubEngine.h" #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/SValuator.h" #include "clang/Analysis/PathSensitive/BugReporter.h" #include "clang/AST/Type.h" #include "clang/AST/ExprObjC.h" -namespace clang { - +namespace clang { + class PathDiagnosticClient; class Diagnostic; class ObjCForCollectionStmt; + class Checker; + +class GRExprEngine : public GRSubEngine { + AnalysisManager &AMgr; + + GRCoreEngine CoreEngine; -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; + ExplodedGraph& G; /// Builder - The current GRStmtNodeBuilder which is used when building the /// nodes for a given statement. - StmtNodeBuilder* Builder; - + GRStmtNodeBuilder* 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; - + /// SVator - SValuator object that creates SVals from expressions. - llvm::OwningPtr<SValuator> SVator; - + SValuator &SVator; + /// EntryNode - The immediate predecessor node. - NodeTy* EntryNode; + ExplodedNode* EntryNode; /// CleanedState - The state for EntryNode "cleaned" of all dead /// variables and symbols (as determined by a liveness analysis). - const GRState* CleanedState; - + 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; + std::vector<Checker*> Checkers; - /// 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; - + typedef llvm::SmallPtrSet<ExplodedNode*,2> ErrorNodes; + typedef llvm::DenseMap<ExplodedNode*, 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). @@ -130,7 +105,7 @@ public: /// 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; @@ -138,65 +113,55 @@ public: /// 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 + + /// UndefDeref - 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 + /// 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 + + /// 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. @@ -209,136 +174,124 @@ public: /// 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(AnalysisManager &mgr); ~GRExprEngine(); - - void ExecuteWorkList(unsigned Steps = 150000) { - CoreEngine.ExecuteWorkList(Steps); + + void ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) { + CoreEngine.ExecuteWorkList(L, 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(); } - + + AnalysisManager &getAnalysisManager() const { return AMgr; } + + SValuator &getSValuator() { return SVator; } + 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; } - + + void ViewGraph(ExplodedNode** Beg, ExplodedNode** End); + /// 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; } + const GRState* getInitialState(const LocationContext *InitLoc); + + ExplodedGraph& getGraph() { return G; } + const ExplodedGraph& 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; + + void registerCheck(Checker *check) { + Checkers.push_back(check); } - - bool isUndefStore(const NodeTy* N) const { - return N->isSink() && UndefStores.count(const_cast<NodeTy*>(N)) != 0; + + bool isRetStackAddr(const ExplodedNode* N) const { + return N->isSink() && RetsStackAddr.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isImplicitNullDeref(const NodeTy* N) const { - return N->isSink() && ImplicitNullDeref.count(const_cast<NodeTy*>(N)) != 0; + + bool isUndefControlFlow(const ExplodedNode* N) const { + return N->isSink() && UndefBranches.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isExplicitNullDeref(const NodeTy* N) const { - return N->isSink() && ExplicitNullDeref.count(const_cast<NodeTy*>(N)) != 0; + + bool isUndefStore(const ExplodedNode* N) const { + return N->isSink() && UndefStores.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isUndefDeref(const NodeTy* N) const { - return N->isSink() && UndefDeref.count(const_cast<NodeTy*>(N)) != 0; + + bool isImplicitNullDeref(const ExplodedNode* N) const { + return N->isSink() && ImplicitNullDeref.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isImplicitBadDivide(const NodeTy* N) const { - return N->isSink() && ImplicitBadDivides.count(const_cast<NodeTy*>(N)) != 0; + + bool isExplicitNullDeref(const ExplodedNode* N) const { + return N->isSink() && ExplicitNullDeref.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isExplicitBadDivide(const NodeTy* N) const { - return N->isSink() && ExplicitBadDivides.count(const_cast<NodeTy*>(N)) != 0; + + bool isUndefDeref(const ExplodedNode* N) const { + return N->isSink() && UndefDeref.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isNoReturnCall(const NodeTy* N) const { - return N->isSink() && NoReturnCalls.count(const_cast<NodeTy*>(N)) != 0; + + bool isNoReturnCall(const ExplodedNode* N) const { + return N->isSink() && NoReturnCalls.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isUndefResult(const NodeTy* N) const { - return N->isSink() && UndefResults.count(const_cast<NodeTy*>(N)) != 0; + + bool isUndefResult(const ExplodedNode* N) const { + return N->isSink() && UndefResults.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isBadCall(const NodeTy* N) const { - return N->isSink() && BadCalls.count(const_cast<NodeTy*>(N)) != 0; + + bool isBadCall(const ExplodedNode* N) const { + return N->isSink() && BadCalls.count(const_cast<ExplodedNode*>(N)) != 0; } - - bool isUndefArg(const NodeTy* N) const { + + bool isUndefArg(const ExplodedNode* N) const { return N->isSink() && - (UndefArgs.find(const_cast<NodeTy*>(N)) != UndefArgs.end() || - MsgExprUndefArgs.find(const_cast<NodeTy*>(N)) != MsgExprUndefArgs.end()); + (UndefArgs.find(const_cast<ExplodedNode*>(N)) != UndefArgs.end() || + MsgExprUndefArgs.find(const_cast<ExplodedNode*>(N)) != MsgExprUndefArgs.end()); } - - bool isUndefReceiver(const NodeTy* N) const { - return N->isSink() && UndefReceivers.count(const_cast<NodeTy*>(N)) != 0; + + bool isUndefReceiver(const ExplodedNode* N) const { + return N->isSink() && UndefReceivers.count(const_cast<ExplodedNode*>(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(); } - + 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(); } - + 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(); } @@ -346,9 +299,9 @@ public: 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(); @@ -358,60 +311,42 @@ public: 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(); } - + 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 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() { + oob_memacc_iterator implicit_oob_memacc_begin() { return ImplicitOOBMemAccesses.begin(); } oob_memacc_iterator implicit_oob_memacc_end() { @@ -426,45 +361,45 @@ public: 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); - + /// nodes by processing the 'effects' of a block-level statement. + void ProcessStmt(Stmt* S, GRStmtNodeBuilder& 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); - + void ProcessBranch(Stmt* Condition, Stmt* Term, GRBranchNodeBuilder& builder); + /// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor /// nodes by processing the 'effects' of a computed goto jump. - void ProcessIndirectGoto(IndirectGotoNodeBuilder& builder); - + void ProcessIndirectGoto(GRIndirectGotoNodeBuilder& builder); + /// ProcessSwitch - Called by GRCoreEngine. Used to generate successor /// nodes by processing the 'effects' of a switch statement. - void ProcessSwitch(SwitchNodeBuilder& builder); - + void ProcessSwitch(GRSwitchNodeBuilder& 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) { + void ProcessEndPath(GREndPathNodeBuilder& 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(); @@ -472,204 +407,198 @@ public: const BasicValueFactory& getBasicVals() const { return StateMgr.getBasicVals(); } - - ValueManager &getValueManager() { return ValMgr; } + + 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) { + const GRState* GetState(ExplodedNode* N) { return N == EntryNode ? CleanedState : N->getState(); } - + public: - NodeTy* MakeNode(NodeSet& Dst, Stmt* S, NodeTy* Pred, const GRState* St, + ExplodedNode* MakeNode(ExplodedNodeSet& Dst, Stmt* S, ExplodedNode* Pred, const GRState* St, ProgramPoint::Kind K = ProgramPoint::PostStmtKind, const void *tag = 0); protected: - + /// CheckerVisit - Dispatcher for performing checker-specific logic + /// at specific statements. + void CheckerVisit(Stmt *S, ExplodedNodeSet &Dst, ExplodedNodeSet &Src, bool isPrevisit); + /// 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); - + void Visit(Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& 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); - + void VisitLValue(Expr* Ex, ExplodedNode* Pred, ExplodedNodeSet& Dst); + /// VisitArraySubscriptExpr - Transfer function for array accesses. - void VisitArraySubscriptExpr(ArraySubscriptExpr* Ex, NodeTy* Pred, - NodeSet& Dst, bool asLValue); - + void VisitArraySubscriptExpr(ArraySubscriptExpr* Ex, ExplodedNode* Pred, + ExplodedNodeSet& Dst, bool asLValue); + /// VisitAsmStmt - Transfer function logic for inline asm. - void VisitAsmStmt(AsmStmt* A, NodeTy* Pred, NodeSet& Dst); - + void VisitAsmStmt(AsmStmt* A, ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitAsmStmtHelperOutputs(AsmStmt* A, AsmStmt::outputs_iterator I, AsmStmt::outputs_iterator E, - NodeTy* Pred, NodeSet& Dst); - + ExplodedNode* Pred, ExplodedNodeSet& Dst); + void VisitAsmStmtHelperInputs(AsmStmt* A, AsmStmt::inputs_iterator I, AsmStmt::inputs_iterator E, - NodeTy* Pred, NodeSet& Dst); - + ExplodedNode* Pred, ExplodedNodeSet& Dst); + /// VisitBinaryOperator - Transfer function logic for binary operators. - void VisitBinaryOperator(BinaryOperator* B, NodeTy* Pred, NodeSet& Dst); + void VisitBinaryOperator(BinaryOperator* B, ExplodedNode* Pred, ExplodedNodeSet& Dst); + - /// VisitCall - Transfer function for function calls. - void VisitCall(CallExpr* CE, NodeTy* Pred, + void VisitCall(CallExpr* CE, ExplodedNode* Pred, CallExpr::arg_iterator AI, CallExpr::arg_iterator AE, - NodeSet& Dst); - void VisitCallRec(CallExpr* CE, NodeTy* Pred, + ExplodedNodeSet& Dst); + void VisitCallRec(CallExpr* CE, ExplodedNode* Pred, CallExpr::arg_iterator AI, CallExpr::arg_iterator AE, - NodeSet& Dst, const FunctionProtoType *, + ExplodedNodeSet& 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); + void VisitCast(Expr* CastE, Expr* Ex, ExplodedNode* Pred, ExplodedNodeSet& 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); - + void VisitCompoundLiteralExpr(CompoundLiteralExpr* CL, ExplodedNode* Pred, + ExplodedNodeSet& Dst, bool asLValue); + /// VisitDeclRefExpr - Transfer function logic for DeclRefExprs. - void VisitDeclRefExpr(DeclRefExpr* DR, NodeTy* Pred, NodeSet& Dst, - bool asLValue); - + void VisitDeclRefExpr(DeclRefExpr* DR, ExplodedNode* Pred, ExplodedNodeSet& Dst, + bool asLValue); + /// VisitDeclStmt - Transfer function logic for DeclStmts. - void VisitDeclStmt(DeclStmt* DS, NodeTy* Pred, NodeSet& Dst); - + void VisitDeclStmt(DeclStmt* DS, ExplodedNode* Pred, ExplodedNodeSet& Dst); + /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose - void VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R, NodeTy* Pred, NodeSet& Dst); + void VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R, ExplodedNode* Pred, ExplodedNodeSet& Dst); - void VisitInitListExpr(InitListExpr* E, NodeTy* Pred, NodeSet& Dst); + void VisitInitListExpr(InitListExpr* E, ExplodedNode* Pred, ExplodedNodeSet& Dst); /// VisitLogicalExpr - Transfer function logic for '&&', '||' - void VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred, NodeSet& Dst); - + void VisitLogicalExpr(BinaryOperator* B, ExplodedNode* Pred, ExplodedNodeSet& Dst); + /// VisitMemberExpr - Transfer function for member expressions. - void VisitMemberExpr(MemberExpr* M, NodeTy* Pred, NodeSet& Dst,bool asLValue); - + void VisitMemberExpr(MemberExpr* M, ExplodedNode* Pred, ExplodedNodeSet& Dst,bool asLValue); + /// VisitObjCIvarRefExpr - Transfer function logic for ObjCIvarRefExprs. - void VisitObjCIvarRefExpr(ObjCIvarRefExpr* DR, NodeTy* Pred, NodeSet& Dst, - bool asLValue); + void VisitObjCIvarRefExpr(ObjCIvarRefExpr* DR, ExplodedNode* Pred, ExplodedNodeSet& 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); - + void VisitObjCForCollectionStmt(ObjCForCollectionStmt* S, ExplodedNode* Pred, + ExplodedNodeSet& Dst); + + void VisitObjCForCollectionStmtAux(ObjCForCollectionStmt* S, ExplodedNode* Pred, + ExplodedNodeSet& Dst, SVal ElementV); + /// VisitObjCMessageExpr - Transfer function for ObjC message expressions. - void VisitObjCMessageExpr(ObjCMessageExpr* ME, NodeTy* Pred, NodeSet& Dst); - + void VisitObjCMessageExpr(ObjCMessageExpr* ME, ExplodedNode* Pred, ExplodedNodeSet& 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); - + ExplodedNode* Pred, ExplodedNodeSet& Dst); + + void VisitObjCMessageExprDispatchHelper(ObjCMessageExpr* ME, ExplodedNode* Pred, + ExplodedNodeSet& Dst); + /// VisitReturnStmt - Transfer function logic for return statements. - void VisitReturnStmt(ReturnStmt* R, NodeTy* Pred, NodeSet& Dst); - + void VisitReturnStmt(ReturnStmt* R, ExplodedNode* Pred, ExplodedNodeSet& Dst); + /// VisitSizeOfAlignOfExpr - Transfer function for sizeof. - void VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr* Ex, NodeTy* Pred, - NodeSet& Dst); - + void VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr* Ex, ExplodedNode* Pred, + ExplodedNodeSet& Dst); + /// VisitUnaryOperator - Transfer function logic for unary operators. - void VisitUnaryOperator(UnaryOperator* B, NodeTy* Pred, NodeSet& Dst, + void VisitUnaryOperator(UnaryOperator* B, ExplodedNode* Pred, ExplodedNodeSet& Dst, bool asLValue); - - const GRState* CheckDivideZero(Expr* Ex, const GRState* St, NodeTy* Pred, - SVal Denom); - + + const GRState* CheckDivideZero(Expr* Ex, const GRState* St, ExplodedNode* 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 SVator->EvalCast(cast<Loc>(X), CastT); - else - return SVator->EvalCast(cast<NonLoc>(X), CastT); - } - + void EvalEagerlyAssume(ExplodedNodeSet& Dst, ExplodedNodeSet& Src, Expr *Ex); + SVal EvalMinus(SVal X) { - return X.isValid() ? SVator->EvalMinus(cast<NonLoc>(X)) : X; + return X.isValid() ? SVator.EvalMinus(cast<NonLoc>(X)) : X; } - + SVal EvalComplement(SVal X) { - return X.isValid() ? SVator->EvalComplement(cast<NonLoc>(X)) : X; + return X.isValid() ? SVator.EvalComplement(cast<NonLoc>(X)) : X; } - + + bool EvalBuiltinFunction(const FunctionDecl *FD, CallExpr *CE, + ExplodedNode *Pred, ExplodedNodeSet &Dst); + public: - - SVal EvalBinOp(BinaryOperator::Opcode op, NonLoc L, NonLoc R, QualType T) { - return SVator->EvalBinOpNN(op, L, R, T); - } - SVal EvalBinOp(BinaryOperator::Opcode op, NonLoc L, SVal R, QualType T) { - return R.isValid() ? SVator->EvalBinOpNN(op, L, cast<NonLoc>(R), T) : R; + SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode op, + NonLoc L, NonLoc R, QualType T) { + return SVator.EvalBinOpNN(state, op, L, R, T); } - + SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode op, - SVal lhs, SVal rhs, QualType T); + NonLoc L, SVal R, QualType T) { + return R.isValid() ? SVator.EvalBinOpNN(state, op, L, cast<NonLoc>(R), T) : R; + } -protected: - - void EvalCall(NodeSet& Dst, CallExpr* CE, SVal L, NodeTy* Pred); + SVal EvalBinOp(const GRState *ST, BinaryOperator::Opcode Op, + SVal LHS, SVal RHS, QualType T) { + return SVator.EvalBinOp(ST, Op, LHS, RHS, T); + } - void EvalObjCMessageExpr(NodeSet& Dst, ObjCMessageExpr* ME, NodeTy* Pred) { +protected: + void EvalCall(ExplodedNodeSet& Dst, CallExpr* CE, SVal L, ExplodedNode* Pred); + + void EvalObjCMessageExpr(ExplodedNodeSet& Dst, ObjCMessageExpr* ME, ExplodedNode* 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, + void EvalReturn(ExplodedNodeSet& Dst, ReturnStmt* s, ExplodedNode* 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, + void EvalBind(ExplodedNodeSet& Dst, Expr* Ex, ExplodedNode* Pred, const GRState* St, SVal location, SVal Val); - + public: - void EvalLoad(NodeSet& Dst, Expr* Ex, NodeTy* Pred, + void EvalLoad(ExplodedNodeSet& Dst, Expr* Ex, ExplodedNode* Pred, const GRState* St, SVal location, const void *tag = 0); - - NodeTy* EvalLocation(Stmt* Ex, NodeTy* Pred, + + ExplodedNode* EvalLocation(Stmt* Ex, ExplodedNode* Pred, const GRState* St, SVal location, const void *tag = 0); - - void EvalStore(NodeSet& Dst, Expr* E, NodeTy* Pred, const GRState* St, + + void EvalStore(ExplodedNodeSet& Dst, Expr* E, ExplodedNode* Pred, const GRState* St, SVal TargetLV, SVal Val, const void *tag = 0); - - void EvalStore(NodeSet& Dst, Expr* E, Expr* StoreE, NodeTy* Pred, + + void EvalStore(ExplodedNodeSet& Dst, Expr* E, Expr* StoreE, ExplodedNode* 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 index 0f3a1372a0f04..60db406cd13df 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngineBuilders.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngineBuilders.h @@ -15,38 +15,15 @@ #ifndef LLVM_CLANG_ANALYSIS_GREXPRENGINE_BUILDERS #define LLVM_CLANG_ANALYSIS_GREXPRENGINE_BUILDERS #include "clang/Analysis/PathSensitive/GRExprEngine.h" +#include "clang/Analysis/Support/SaveAndRestore.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; + ExplodedNodeSet &Dst; + GRStmtNodeBuilder &B; GRExprEngine& Eng; - GRExprEngine::NodeTy* Pred; + ExplodedNode* Pred; const GRState* state; const Stmt* stmt; const unsigned OldSize; @@ -57,25 +34,25 @@ class GRStmtNodeBuilderRef { private: friend class GRExprEngine; - + GRStmtNodeBuilderRef(); // do not implement void operator=(const GRStmtNodeBuilderRef&); // do not implement - - GRStmtNodeBuilderRef(GRExprEngine::NodeSet &dst, - GRExprEngine::StmtNodeBuilder &builder, + + GRStmtNodeBuilderRef(ExplodedNodeSet &dst, + GRStmtNodeBuilder &builder, GRExprEngine& eng, - GRExprEngine::NodeTy* pred, + ExplodedNode* 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. + // 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); @@ -85,14 +62,14 @@ public: } const GRState *getState() { return state; } - + GRStateManager& getStateManager() { return Eng.getStateManager(); } - - GRExprEngine::NodeTy* MakeNode(const GRState* state) { - return B.MakeNode(Dst, const_cast<Stmt*>(stmt), Pred, state); - } + + ExplodedNode* MakeNode(const GRState* state) { + return B.MakeNode(Dst, const_cast<Stmt*>(stmt), Pred, state); + } }; } // end clang namespace diff --git a/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h b/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h index e54b31dfe883b..978ff0889e64c 100644 --- a/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h +++ b/include/clang/Analysis/PathSensitive/GRSimpleAPICheck.h @@ -20,16 +20,16 @@ #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> { +class ExplodedGraph; + + +class GRSimpleAPICheck : public GRAuditor { public: GRSimpleAPICheck() {} virtual ~GRSimpleAPICheck() {} diff --git a/include/clang/Analysis/PathSensitive/GRState.h b/include/clang/Analysis/PathSensitive/GRState.h index 0da8f5243e9c3..d8b9d560ccd85 100644 --- a/include/clang/Analysis/PathSensitive/GRState.h +++ b/include/clang/Analysis/PathSensitive/GRState.h @@ -49,12 +49,12 @@ 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* 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; @@ -66,68 +66,78 @@ template <typename T> struct GRStateTrait { //===----------------------------------------------------------------------===// class GRStateManager; - + /// 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. +public: typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; - typedef llvm::ImmutableMap<void*, void*> GenericDataMap; - - typedef GRStateManager ManagerTy; - + typedef llvm::ImmutableMap<void*, void*> GenericDataMap; + private: void operator=(const GRState& R) const; - + friend class GRStateManager; - GRStateManager *Mgr; + GRStateManager *StateMgr; Environment Env; Store St; // FIXME: Make these private. public: GenericDataMap GDM; - + public: - + /// This ctor is used when creating the first GRState object. - GRState(GRStateManager *mgr, const Environment& env, Store st, - GenericDataMap gdm) - : Mgr(mgr), + GRState(GRStateManager *mgr, const Environment& env, + Store st, GenericDataMap gdm) + : StateMgr(mgr), 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(), - Mgr(RHS.Mgr), + StateMgr(RHS.StateMgr), Env(RHS.Env), St(RHS.St), GDM(RHS.GDM) {} - + /// getStateManager - Return the GRStateManager associated with this state. - GRStateManager &getStateManager() const { return *Mgr; } - + GRStateManager &getStateManager() const { + return *StateMgr; + } + + /// getAnalysisContext - Return the AnalysisContext associated with this + /// state. + AnalysisContext &getAnalysisContext() const { + return Env.getAnalysisContext(); + } + /// 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; } - + + void setStore(Store s) { St = s; } + /// getGDM - Return the generic data map associated with this state. GenericDataMap getGDM() const { return GDM; } - + + void setGDM(GenericDataMap gdm) { GDM = gdm; } + /// Profile - Profile the contents of a GRState object for use /// in a FoldingSet. static void Profile(llvm::FoldingSetNodeID& ID, const GRState* V) { + // FIXME: Do we need to include the AnalysisContext in the profile? V->Env.Profile(ID); ID.AddPointer(V->St); V->GDM.Profile(ID); @@ -138,28 +148,19 @@ public: void Profile(llvm::FoldingSetNodeID& ID) const { Profile(ID, this); } - + SVal LookupExpr(Expr* E) const { return Env.LookupExpr(E); } - + /// makeWithStore - Return a GRState with the same values as the current /// state with the exception of using the specified Store. const GRState *makeWithStore(Store store) const; - - // 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(); } - + BasicValueFactory &getBasicVals() const; SymbolManager &getSymbolManager() const; GRTransferFuncs &getTransferFuncs() const; - + //==---------------------------------------------------------------------==// // Constraints on values. //==---------------------------------------------------------------------==// @@ -192,91 +193,85 @@ public: // FIXME: (a) should probably disappear since it is redundant with (b). // (i.e., (b) could just be set to NULL). // - - const GRState *assume(SVal condition, bool assumption) const; - - const GRState *assumeInBound(SVal idx, SVal upperBound, + + const GRState *Assume(DefinedOrUnknownSVal cond, bool assumption) const; + + const GRState *AssumeInBound(DefinedOrUnknownSVal idx, + DefinedOrUnknownSVal upperBound, bool assumption) const; - + //==---------------------------------------------------------------------==// // Utility methods for getting regions. //==---------------------------------------------------------------------==// - const VarRegion* getRegion(const VarDecl* D) const; - - const MemRegion* getSelfRegion() const; + const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; //==---------------------------------------------------------------------==// // Binding and retrieving values to/from the environment and symbolic store. //==---------------------------------------------------------------------==// - + /// 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 CompoundLiteralExpr* CL, SVal V) const; - - const GRState *bindExpr(const Stmt* Ex, SVal V, bool isBlkExpr, - bool Invalidate) const; - - const GRState *bindExpr(const Stmt* Ex, SVal V, bool Invalidate = true) const; - - const GRState *bindBlkExpr(const Stmt *Ex, SVal V) const { - return bindExpr(Ex, V, true, false); - } - - const GRState *bindDecl(const VarDecl* VD, SVal IVal) const; - - const GRState *bindDeclWithNoInit(const VarDecl* VD) const; - + + const GRState *BindExpr(const Stmt *S, SVal V, bool Invalidate = true) const; + + const GRState *bindDecl(const VarDecl *VD, const LocationContext *LC, + SVal V) const; + + const GRState *bindDeclWithNoInit(const VarDecl *VD, + const LocationContext *LC) const; + const GRState *bindLoc(Loc location, SVal V) const; - + const GRState *bindLoc(SVal location, SVal V) const; - + const GRState *unbindLoc(Loc LV) const; /// Get the lvalue for a variable reference. - SVal getLValue(const VarDecl *decl) const; - + SVal getLValue(const VarDecl *D, const LocationContext *LC) const; + /// Get the lvalue for a StringLiteral. SVal getLValue(const StringLiteral *literal) const; - + SVal getLValue(const CompoundLiteralExpr *literal) const; - + /// Get the lvalue for an ivar reference. SVal getLValue(const ObjCIvarDecl *decl, SVal base) const; - + /// Get the lvalue for a field reference. - SVal getLValue(SVal Base, const FieldDecl *decl) const; - + SVal getLValue(const FieldDecl *decl, SVal Base) const; + /// Get the lvalue for an array index. - SVal getLValue(QualType ElementType, SVal Base, SVal Idx) const; - + SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; + const llvm::APSInt *getSymVal(SymbolRef sym) const; SVal getSVal(const Stmt* Ex) const; - - SVal getBlkExprSVal(const Stmt* Ex) const; - + SVal getSValAsScalarOrLoc(const Stmt *Ex) const; - + SVal getSVal(Loc LV, QualType T = QualType()) const; - + SVal getSVal(const MemRegion* R) const; - + SVal getSValAsScalarOrLoc(const MemRegion *R) const; + const llvm::APSInt *getSymVal(SymbolRef sym); + bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; template <typename CB> CB scanReachableSymbols(SVal val) const; - + //==---------------------------------------------------------------------==// // Accessing the Generic Data Map (GDM). //==---------------------------------------------------------------------==// void* const* FindGDM(void* K) const; - + template<typename T> const GRState *add(typename GRStateTrait<T>::key_type K) const; @@ -285,31 +280,31 @@ public: 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> typename GRStateTrait<T>::context_type get_context() const; - - + + template<typename T> const GRState *remove(typename GRStateTrait<T>::key_type K) const; template<typename T> const GRState *remove(typename GRStateTrait<T>::key_type K, typename GRStateTrait<T>::context_type C) const; - + template<typename T> const GRState *set(typename GRStateTrait<T>::data_type D) const; - + template<typename T> const GRState *set(typename GRStateTrait<T>::key_type K, - typename GRStateTrait<T>::value_type E) const; + typename GRStateTrait<T>::value_type E) const; template<typename T> const GRState *set(typename GRStateTrait<T>::key_type K, @@ -321,7 +316,7 @@ public: void* const* d = FindGDM(GRStateTrait<T>::GDMIndex()); return GRStateTrait<T>::Contains(GRStateTrait<T>::MakeData(d), key); } - + // State pretty-printing. class Printer { public: @@ -329,66 +324,55 @@ public: virtual void Print(llvm::raw_ostream& Out, const GRState* state, const char* nl, const char* sep) = 0; }; - + // Pretty-printing. void print(llvm::raw_ostream& Out, const char *nl = "\n", - const char *sep = "") const; + const char *sep = "") const; + + void printStdErr() const; + + void printDOT(llvm::raw_ostream& Out) const; - void printStdErr() const; - - void printDOT(llvm::raw_ostream& Out) 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; + 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) + 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. //===----------------------------------------------------------------------===// @@ -396,22 +380,21 @@ public: class GRStateManager { friend class GRExprEngine; friend class GRState; - + 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; @@ -421,52 +404,36 @@ private: /// 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; - 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)); + llvm::BumpPtrAllocator& alloc) + : EnvMgr(alloc), + GDMFactory(alloc), + ValueMgr(alloc, Ctx, *this), + Alloc(alloc) { + StoreMgr.reset((*CreateStoreManager)(*this)); + ConstraintMgr.reset((*CreateConstraintManager)(*this)); } - + ~GRStateManager(); - const GRState *getInitialState(); - + const GRState *getInitialState(const LocationContext *InitLoc); + ASTContext &getContext() { return ValueMgr.getContext(); } - const ASTContext &getContext() const { return ValueMgr.getContext(); } - - const Decl &getCodeDecl() { return codedecl; } + const ASTContext &getContext() const { return ValueMgr.getContext(); } + GRTransferFuncs& getTransferFuncs() { return *TF; } BasicValueFactory &getBasicVals() { @@ -475,18 +442,17 @@ public: 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() { @@ -495,28 +461,22 @@ public: const MemRegionManager& getRegionManager() const { return ValueMgr.getRegionManager(); } - + StoreManager& getStoreManager() { return *StoreMgr; } ConstraintManager& getConstraintManager() { return *ConstraintMgr; } - const GRState* RemoveDeadBindings(const GRState* St, Stmt* Loc, + 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); - } - public: 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 & manipulate the Store. void iterBindings(const GRState* state, StoreManager::BindingsHandler& F) { @@ -525,9 +485,9 @@ public: const GRState* getPersistentState(GRState& Impl); - bool isEqual(const GRState* state, Expr* Ex, const llvm::APSInt& V); - bool isEqual(const GRState* state, Expr* Ex, uint64_t); - + bool isEqual(const GRState* state, const Expr* Ex, const llvm::APSInt& V); + bool isEqual(const GRState* state, const Expr* Ex, uint64_t); + //==---------------------------------------------------------------------==// // Generic Data Map methods. //==---------------------------------------------------------------------==// @@ -545,21 +505,21 @@ public: // 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. + + // 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(), + + return addGDM(st, GRStateTrait<T>::GDMIndex(), GRStateTrait<T>::MakeVoidPtr(GRStateTrait<T>::Set(st->get<T>(), K, V, C))); } @@ -575,22 +535,22 @@ public: const GRState* remove(const GRState* st, typename GRStateTrait<T>::key_type K, typename GRStateTrait<T>::context_type C) { - - return addGDM(st, GRStateTrait<T>::GDMIndex(), + + 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); } @@ -602,84 +562,96 @@ public: ConstraintMgr->EndPath(St); } }; - + //===----------------------------------------------------------------------===// // Out-of-line method definitions for GRState. //===----------------------------------------------------------------------===// -inline const VarRegion* GRState::getRegion(const VarDecl* D) const { - return Mgr->getRegionManager().getVarRegion(D); +inline const llvm::APSInt *GRState::getSymVal(SymbolRef sym) { + return getStateManager().getSymVal(this, sym); } - -inline const MemRegion* GRState::getSelfRegion() const { - return Mgr->StoreMgr->getSelfRegion(getStore()); + +inline const VarRegion* GRState::getRegion(const VarDecl *D, + const LocationContext *LC) const { + return getStateManager().getRegionManager().getVarRegion(D, LC); } + +inline const GRState *GRState::Assume(DefinedOrUnknownSVal Cond, + bool Assumption) const { + if (Cond.isUnknown()) + return this; -inline const GRState *GRState::assume(SVal Cond, bool Assumption) const { - return Mgr->ConstraintMgr->Assume(this, Cond, Assumption); + return getStateManager().ConstraintMgr->Assume(this, cast<DefinedSVal>(Cond), + Assumption); } -inline const GRState *GRState::assumeInBound(SVal Idx, SVal UpperBound, +inline const GRState *GRState::AssumeInBound(DefinedOrUnknownSVal Idx, + DefinedOrUnknownSVal UpperBound, bool Assumption) const { - return Mgr->ConstraintMgr->AssumeInBound(this, Idx, UpperBound, Assumption); -} + if (Idx.isUnknown() || UpperBound.isUnknown()) + return this; + + ConstraintManager &CM = *getStateManager().ConstraintMgr; + return CM.AssumeInBound(this, cast<DefinedSVal>(Idx), + cast<DefinedSVal>(UpperBound), Assumption); +} inline const GRState *GRState::bindCompoundLiteral(const CompoundLiteralExpr* CL, SVal V) const { - return Mgr->StoreMgr->BindCompoundLiteral(this, CL, V); + return getStateManager().StoreMgr->BindCompoundLiteral(this, CL, V); } - -inline const GRState *GRState::bindDecl(const VarDecl* VD, SVal IVal) const { - return Mgr->StoreMgr->BindDecl(this, VD, IVal); + +inline const GRState *GRState::bindDecl(const VarDecl* VD, + const LocationContext *LC, + SVal IVal) const { + return getStateManager().StoreMgr->BindDecl(this, VD, LC, IVal); } -inline const GRState *GRState::bindDeclWithNoInit(const VarDecl* VD) const { - return Mgr->StoreMgr->BindDeclWithNoInit(this, VD); +inline const GRState *GRState::bindDeclWithNoInit(const VarDecl* VD, + const LocationContext *LC) const { + return getStateManager().StoreMgr->BindDeclWithNoInit(this, VD, LC); } - + inline const GRState *GRState::bindLoc(Loc LV, SVal V) const { - return Mgr->StoreMgr->Bind(this, LV, V); + return getStateManager().StoreMgr->Bind(this, LV, V); } inline const GRState *GRState::bindLoc(SVal LV, SVal V) const { return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V); } - -inline SVal GRState::getLValue(const VarDecl* VD) const { - return Mgr->StoreMgr->getLValueVar(this, VD); + +inline SVal GRState::getLValue(const VarDecl* VD, + const LocationContext *LC) const { + return getStateManager().StoreMgr->getLValueVar(VD, LC); } inline SVal GRState::getLValue(const StringLiteral *literal) const { - return Mgr->StoreMgr->getLValueString(this, literal); + return getStateManager().StoreMgr->getLValueString(literal); } - + inline SVal GRState::getLValue(const CompoundLiteralExpr *literal) const { - return Mgr->StoreMgr->getLValueCompoundLiteral(this, literal); + return getStateManager().StoreMgr->getLValueCompoundLiteral(literal); } inline SVal GRState::getLValue(const ObjCIvarDecl *D, SVal Base) const { - return Mgr->StoreMgr->getLValueIvar(this, D, Base); + return getStateManager().StoreMgr->getLValueIvar(D, Base); } - -inline SVal GRState::getLValue(SVal Base, const FieldDecl* D) const { - return Mgr->StoreMgr->getLValueField(this, Base, D); + +inline SVal GRState::getLValue(const FieldDecl* D, SVal Base) const { + return getStateManager().StoreMgr->getLValueField(D, Base); } - -inline SVal GRState::getLValue(QualType ElementType, SVal Base, SVal Idx) const{ - return Mgr->StoreMgr->getLValueElement(this, ElementType, Base, Idx); + +inline SVal GRState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ + return getStateManager().StoreMgr->getLValueElement(ElementType, Idx, Base); } - + inline const llvm::APSInt *GRState::getSymVal(SymbolRef sym) const { - return Mgr->getSymVal(this, sym); -} - -inline SVal GRState::getSVal(const Stmt* Ex) const { - return Env.GetSVal(Ex, Mgr->ValueMgr); + return getStateManager().getSymVal(this, sym); } -inline SVal GRState::getBlkExprSVal(const Stmt* Ex) const { - return Env.GetBlkExprSVal(Ex, Mgr->ValueMgr); +inline SVal GRState::getSVal(const Stmt* Ex) const { + return Env.GetSVal(Ex, getStateManager().ValueMgr); } inline SVal GRState::getSValAsScalarOrLoc(const Stmt *S) const { @@ -688,69 +660,69 @@ inline SVal GRState::getSValAsScalarOrLoc(const Stmt *S) const { if (Loc::IsLocType(T) || T->isIntegerType()) return getSVal(S); } - + return UnknownVal(); } inline SVal GRState::getSVal(Loc LV, QualType T) const { - return Mgr->StoreMgr->Retrieve(this, LV, T); + return getStateManager().StoreMgr->Retrieve(this, LV, T).getSVal(); } inline SVal GRState::getSVal(const MemRegion* R) const { - return Mgr->StoreMgr->Retrieve(this, loc::MemRegionVal(R)); + return getStateManager().StoreMgr->Retrieve(this, loc::MemRegionVal(R)).getSVal(); } - + inline BasicValueFactory &GRState::getBasicVals() const { - return Mgr->getBasicVals(); + return getStateManager().getBasicVals(); } inline SymbolManager &GRState::getSymbolManager() const { - return Mgr->getSymbolManager(); + return getStateManager().getSymbolManager(); } - + inline GRTransferFuncs &GRState::getTransferFuncs() const { - return Mgr->getTransferFuncs(); + return getStateManager().getTransferFuncs(); } template<typename T> const GRState *GRState::add(typename GRStateTrait<T>::key_type K) const { - return Mgr->add<T>(this, K, get_context<T>()); + return getStateManager().add<T>(this, K, get_context<T>()); } - + template <typename T> typename GRStateTrait<T>::context_type GRState::get_context() const { - return Mgr->get_context<T>(); + return getStateManager().get_context<T>(); } - + template<typename T> const GRState *GRState::remove(typename GRStateTrait<T>::key_type K) const { - return Mgr->remove<T>(this, K, get_context<T>()); + return getStateManager().remove<T>(this, K, get_context<T>()); } template<typename T> const GRState *GRState::remove(typename GRStateTrait<T>::key_type K, typename GRStateTrait<T>::context_type C) const { - return Mgr->remove<T>(this, K, C); + return getStateManager().remove<T>(this, K, C); } - + template<typename T> const GRState *GRState::set(typename GRStateTrait<T>::data_type D) const { - return Mgr->set<T>(this, D); + return getStateManager().set<T>(this, D); } - + template<typename T> const GRState *GRState::set(typename GRStateTrait<T>::key_type K, typename GRStateTrait<T>::value_type E) const { - return Mgr->set<T>(this, K, E, get_context<T>()); + return getStateManager().set<T>(this, K, E, get_context<T>()); } - + template<typename T> const GRState *GRState::set(typename GRStateTrait<T>::key_type K, typename GRStateTrait<T>::value_type E, typename GRStateTrait<T>::context_type C) const { - return Mgr->set<T>(this, K, E, C); + return getStateManager().set<T>(this, K, E, C); } - + template <typename CB> CB GRState::scanReachableSymbols(SVal val) const { CB cb(this); diff --git a/include/clang/Analysis/PathSensitive/GRStateTrait.h b/include/clang/Analysis/PathSensitive/GRStateTrait.h index ce43cda31e9e5..5189a1f5aa7e8 100644 --- a/include/clang/Analysis/PathSensitive/GRStateTrait.h +++ b/include/clang/Analysis/PathSensitive/GRStateTrait.h @@ -1,5 +1,5 @@ //==- GRStateTrait.h - Partial implementations of GRStateTrait -----*- C++ -*-// -// +// // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source @@ -27,59 +27,59 @@ namespace llvm { 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 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); + 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 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(); @@ -88,60 +88,60 @@ namespace clang { 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); + 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; - + 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) + 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); + return new typename data_type::Factory(Alloc); } - + static void DeleteContext(void* Ctx) { delete (typename data_type::Factory*) Ctx; - } + } }; } // end clang namespace diff --git a/include/clang/Analysis/PathSensitive/GRSubEngine.h b/include/clang/Analysis/PathSensitive/GRSubEngine.h new file mode 100644 index 0000000000000..62e36f9e641e4 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/GRSubEngine.h @@ -0,0 +1,68 @@ +//== GRSubEngine.h - Interface of the subengine of 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 the interface of a subengine of the GRCoreEngine. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_CLANG_ANALYSIS_GRSUBENGINE_H +#define LLVM_CLANG_ANALYSIS_GRSUBENGINE_H + +namespace clang { + +class Stmt; +class CFGBlock; +class GRState; +class GRStateManager; +class GRBlockCounter; +class GRStmtNodeBuilder; +class GRBranchNodeBuilder; +class GRIndirectGotoNodeBuilder; +class GRSwitchNodeBuilder; +class GREndPathNodeBuilder; +class LocationContext; + +class GRSubEngine { +public: + virtual ~GRSubEngine() {} + + virtual const GRState* getInitialState(const LocationContext *InitLoc) = 0; + + virtual GRStateManager& getStateManager() = 0; + + /// ProcessStmt - Called by GRCoreEngine. Used to generate new successor + /// nodes by processing the 'effects' of a block-level statement. + virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilder& builder) = 0; + + /// 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. + virtual bool ProcessBlockEntrance(CFGBlock* B, const GRState* St, + GRBlockCounter BC) = 0; + + /// ProcessBranch - Called by GRCoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a branch condition. + virtual void ProcessBranch(Stmt* Condition, Stmt* Term, + GRBranchNodeBuilder& builder) = 0; + + /// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a computed goto jump. + virtual void ProcessIndirectGoto(GRIndirectGotoNodeBuilder& builder) = 0; + + /// ProcessSwitch - Called by GRCoreEngine. Used to generate successor + /// nodes by processing the 'effects' of a switch statement. + virtual void ProcessSwitch(GRSwitchNodeBuilder& builder) = 0; + + /// ProcessEndPath - Called by GRCoreEngine. Used to generate end-of-path + /// nodes when the control reaches the end of a function. + virtual void ProcessEndPath(GREndPathNodeBuilder& builder) = 0; +}; + +} + +#endif diff --git a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h index db23f81e2d670..5f7b2cb0e327e 100644 --- a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h +++ b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h @@ -21,66 +21,68 @@ #include <vector> namespace clang { - + class GRExprEngine; class BugReporter; class ObjCMessageExpr; class GRStmtNodeBuilderRef; - + class GRTransferFuncs { public: GRTransferFuncs() {} virtual ~GRTransferFuncs() {} - + virtual void RegisterPrinters(std::vector<GRState::Printer*>& Printers) {} virtual void RegisterChecks(BugReporter& BR) {} - + // Calls. - - virtual void EvalCall(ExplodedNodeSet<GRState>& Dst, + + virtual void EvalCall(ExplodedNodeSet& Dst, GRExprEngine& Engine, - GRStmtNodeBuilder<GRState>& Builder, + GRStmtNodeBuilder& Builder, CallExpr* CE, SVal L, - ExplodedNode<GRState>* Pred) {} - - virtual void EvalObjCMessageExpr(ExplodedNodeSet<GRState>& Dst, + ExplodedNode* Pred) {} + + virtual void EvalObjCMessageExpr(ExplodedNodeSet& Dst, GRExprEngine& Engine, - GRStmtNodeBuilder<GRState>& Builder, + GRStmtNodeBuilder& Builder, ObjCMessageExpr* ME, - ExplodedNode<GRState>* Pred) {} - + ExplodedNode* 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, + GREndPathNodeBuilder& Builder) {} + + + virtual void EvalDeadSymbols(ExplodedNodeSet& Dst, GRExprEngine& Engine, - GRStmtNodeBuilder<GRState>& Builder, - ExplodedNode<GRState>* Pred, + GRStmtNodeBuilder& Builder, + ExplodedNode* Pred, Stmt* S, const GRState* state, SymbolReaper& SymReaper) {} - - // Return statements. - virtual void EvalReturn(ExplodedNodeSet<GRState>& Dst, + + // Return statements. + virtual void EvalReturn(ExplodedNodeSet& Dst, GRExprEngine& Engine, - GRStmtNodeBuilder<GRState>& Builder, + GRStmtNodeBuilder& Builder, ReturnStmt* S, - ExplodedNode<GRState>* Pred) {} + ExplodedNode* Pred) {} - // Assumptions. + // Assumptions. virtual const GRState* EvalAssume(const GRState *state, SVal Cond, bool Assumption) { return state; } }; - + +GRTransferFuncs *CreateCallInliner(ASTContext &ctx); + } // end clang namespace #endif diff --git a/include/clang/Analysis/PathSensitive/GRWorkList.h b/include/clang/Analysis/PathSensitive/GRWorkList.h index c76532294c1f8..17b83fdf9fdc3 100644 --- a/include/clang/Analysis/PathSensitive/GRWorkList.h +++ b/include/clang/Analysis/PathSensitive/GRWorkList.h @@ -1,5 +1,5 @@ //==- GRWorkList.h - Worklist class used by GRCoreEngine -----------*- C++ -*-// -// +// // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source @@ -17,31 +17,31 @@ #include "clang/Analysis/PathSensitive/GRBlockCounter.h" -namespace clang { +namespace clang { class ExplodedNodeImpl; - + class GRWorkListUnit { - ExplodedNodeImpl* Node; + ExplodedNode* Node; GRBlockCounter Counter; CFGBlock* Block; unsigned BlockIdx; - + public: - GRWorkListUnit(ExplodedNodeImpl* N, GRBlockCounter C, + GRWorkListUnit(ExplodedNode* N, GRBlockCounter C, CFGBlock* B, unsigned idx) : Node(N), Counter(C), Block(B), BlockIdx(idx) {} - - explicit GRWorkListUnit(ExplodedNodeImpl* N, GRBlockCounter C) + + explicit GRWorkListUnit(ExplodedNode* N, GRBlockCounter C) : Node(N), Counter(C), Block(NULL), BlockIdx(0) {} - - ExplodedNodeImpl* getNode() const { return Node; } + + ExplodedNode* getNode() const { return Node; } GRBlockCounter getBlockCounter() const { return Counter; } CFGBlock* getBlock() const { return Block; } unsigned getIndex() const { return BlockIdx; } @@ -52,25 +52,25 @@ class GRWorkList { public: virtual ~GRWorkList(); virtual bool hasWork() const = 0; - + virtual void Enqueue(const GRWorkListUnit& U) = 0; - void Enqueue(ExplodedNodeImpl* N, CFGBlock& B, unsigned idx) { + void Enqueue(ExplodedNode* N, CFGBlock& B, unsigned idx) { Enqueue(GRWorkListUnit(N, CurrentCounter, &B, idx)); } - - void Enqueue(ExplodedNodeImpl* N) { + + void Enqueue(ExplodedNode* 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 +} // end clang namespace #endif diff --git a/include/clang/Analysis/PathSensitive/MemRegion.h b/include/clang/Analysis/PathSensitive/MemRegion.h index 5926229e517c3..0e487691a8912 100644 --- a/include/clang/Analysis/PathSensitive/MemRegion.h +++ b/include/clang/Analysis/PathSensitive/MemRegion.h @@ -31,10 +31,15 @@ namespace llvm { class raw_ostream; } namespace clang { - + class MemRegionManager; -class MemSpaceRegion; - +class MemSpaceRegion; +class LocationContext; + +//===----------------------------------------------------------------------===// +// Base region classes. +//===----------------------------------------------------------------------===// + /// MemRegion - The root abstract class for all memory regions. class MemRegion : public llvm::FoldingSetNode { public: @@ -46,55 +51,57 @@ public: CodeTextRegionKind, CompoundLiteralRegionKind, StringRegionKind, ElementRegionKind, - TypedViewRegionKind, // Decl Regions. BEG_DECL_REGIONS, VarRegionKind, FieldRegionKind, ObjCIvarRegionKind, ObjCObjectRegionKind, END_DECL_REGIONS, - END_TYPED_REGIONS }; + END_TYPED_REGIONS }; private: const Kind kind; - + protected: MemRegion(Kind k) : kind(k) {} virtual ~MemRegion(); - ASTContext &getContext() const; public: + ASTContext &getContext() const; + virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0; virtual MemRegionManager* getMemRegionManager() const = 0; std::string getString() const; - + const MemSpaceRegion *getMemorySpace() const; - + + const MemRegion *getBaseRegion() const; + bool hasStackStorage() const; - + bool hasParametersStorage() const; - + bool hasGlobalsStorage() const; - + bool hasGlobalsOrParametersStorage() const; - + bool hasHeapStorage() const; - + bool hasHeapOrStackStorage() const; - virtual void print(llvm::raw_ostream& os) const; + virtual void dumpToStream(llvm::raw_ostream& os) const; + + void dump() const; + + Kind getKind() const { return kind; } - void printStdErr() const; - - Kind getKind() const { return kind; } - template<typename RegionTy> const RegionTy* getAs() const; - + virtual bool isBoundable() const { return false; } 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 { @@ -105,7 +112,7 @@ protected: MemSpaceRegion(MemRegionManager *mgr) : MemRegion(MemSpaceRegionKind), Mgr(mgr) {} - + MemRegionManager* getMemRegionManager() const { return Mgr; } @@ -124,13 +131,13 @@ public: /// are subclasses of SubRegion. class SubRegion : public MemRegion { protected: - const MemRegion* superRegion; + const MemRegion* superRegion; SubRegion(const MemRegion* sReg, Kind k) : MemRegion(k), superRegion(sReg) {} public: const MemRegion* getSuperRegion() const { return superRegion; } - + MemRegionManager* getMemRegionManager() const; bool isSubRegionOf(const MemRegion* R) const; @@ -140,6 +147,32 @@ public: } }; +//===----------------------------------------------------------------------===// +// Auxillary data classes for use with MemRegions. +//===----------------------------------------------------------------------===// + +class ElementRegion; + +class RegionRawOffset : public std::pair<const MemRegion*, int64_t> { +private: + friend class ElementRegion; + + RegionRawOffset(const MemRegion* reg, int64_t offset = 0) + : std::pair<const MemRegion*, int64_t>(reg, offset) {} + +public: + // FIXME: Eventually support symbolic offsets. + int64_t getByteOffset() const { return second; } + const MemRegion *getRegion() const { return first; } + + void dumpToStream(llvm::raw_ostream& os) const; + void dump() const; +}; + +//===----------------------------------------------------------------------===// +// MemRegion subclasses. +//===----------------------------------------------------------------------===// + /// AllocaRegion - A region that represents an untyped blob of bytes created /// by a call to 'alloca'. class AllocaRegion : public SubRegion { @@ -151,43 +184,45 @@ protected: AllocaRegion(const Expr* ex, unsigned cnt, const MemRegion *superRegion) : SubRegion(superRegion, AllocaRegionKind), Cnt(cnt), Ex(ex) {} - + public: - + const Expr* getExpr() const { return Ex; } - + + bool isBoundable() const { return true; } + void Profile(llvm::FoldingSetNodeID& ID) const; static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr* Ex, unsigned Cnt, const MemRegion *superRegion); - - void print(llvm::raw_ostream& os) const; - + + void dumpToStream(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; + return T.getTypePtr() ? T.getDesugaredType() : T; } - + QualType getDesugaredLocationType(ASTContext& C) const { - return getLocationType(C)->getDesugaredType(); + return getLocationType(C).getDesugaredType(); } bool isBoundable() const { @@ -205,32 +240,12 @@ public: /// 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; + const FunctionDecl *FD; 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) {} + CodeTextRegion(const FunctionDecl* fd, const MemRegion* sreg) + : TypedRegion(sreg, CodeTextRegionKind), FD(fd) {} QualType getValueType(ASTContext &C) const { // Do not get the object type of a CodeTextRegion. @@ -239,30 +254,21 @@ public: } QualType getLocationType(ASTContext &C) const { - return LocationType; + return C.getPointerType(FD->getType()); } - 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); + const FunctionDecl *getDecl() const { + return FD; } - - SymbolRef getSymbol() const { - assert(codekind == Symbolic); - return const_cast<SymbolRef>(static_cast<const SymbolRef>(Data)); - } - + bool isBoundable() const { return false; } - - virtual void print(llvm::raw_ostream& os) const; + + virtual void dumpToStream(llvm::raw_ostream& os) const; void Profile(llvm::FoldingSetNodeID& ID) const; - static void ProfileRegion(llvm::FoldingSetNodeID& ID, - const void* data, QualType t, const MemRegion*); + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const FunctionDecl *FD, + const MemRegion*); static bool classof(const MemRegion* R) { return R->getKind() == CodeTextRegionKind; @@ -279,25 +285,27 @@ protected: const SymbolRef sym; public: - SymbolicRegion(const SymbolRef s, const MemRegion* sreg) + SymbolicRegion(const SymbolRef s, const MemRegion* sreg) : SubRegion(sreg, SymbolicRegionKind), sym(s) {} - + SymbolRef getSymbol() const { return sym; } + bool isBoundable() const { return true; } + void Profile(llvm::FoldingSetNodeID& ID) const; static void ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym, const MemRegion* superRegion); - - void print(llvm::raw_ostream& os) const; - + + void dumpToStream(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 { @@ -315,7 +323,7 @@ protected: public: const StringLiteral* getStringLiteral() const { return Str; } - + QualType getValueType(ASTContext& C) const { return Str->getType(); } @@ -326,53 +334,13 @@ public: ProfileRegion(ID, Str, superRegion); } - void print(llvm::raw_ostream& os) const; + void dumpToStream(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() 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. @@ -383,7 +351,7 @@ private: CompoundLiteralRegion(const CompoundLiteralExpr* cl, const MemRegion* sReg) : TypedRegion(sReg, CompoundLiteralRegionKind), CL(cl) {} - + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const CompoundLiteralExpr* CL, const MemRegion* superRegion); @@ -395,11 +363,11 @@ public: bool isBoundable() const { return !CL->isFileScope(); } void Profile(llvm::FoldingSetNodeID& ID) const; - - void print(llvm::raw_ostream& os) const; + + void dumpToStream(llvm::raw_ostream& os) const; const CompoundLiteralExpr* getLiteralExpr() const { return CL; } - + static bool classof(const MemRegion* R) { return R->getKind() == CompoundLiteralRegionKind; } @@ -414,41 +382,51 @@ protected: 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) {} + + // Data. + const LocationContext *LC; + + // Constructors and private methods. + VarRegion(const VarDecl* vd, const LocationContext *lC, const MemRegion* sReg) + : DeclRegion(vd, sReg, VarRegionKind), LC(lC) {} static void ProfileRegion(llvm::FoldingSetNodeID& ID, const VarDecl* VD, - const MemRegion* superRegion) { + const LocationContext *LC, + const MemRegion *superRegion) { DeclRegion::ProfileRegion(ID, VD, superRegion, VarRegionKind); + ID.AddPointer(LC); } - -public: - const VarDecl* getDecl() const { return cast<VarDecl>(D); } - - QualType getValueType(ASTContext& C) const { + + void Profile(llvm::FoldingSetNodeID& ID) const; + +public: + const VarDecl *getDecl() const { return cast<VarDecl>(D); } + + const LocationContext *getLocationContext() const { return LC; } + + QualType getValueType(ASTContext& C) const { // FIXME: We can cache this if needed. return C.getCanonicalType(getDecl()->getType()); - } - - void print(llvm::raw_ostream& os) const; - + } + + void dumpToStream(llvm::raw_ostream& os) const; + static bool classof(const MemRegion* R) { return R->getKind() == VarRegionKind; - } + } }; class FieldRegion : public DeclRegion { @@ -458,57 +436,57 @@ class FieldRegion : public DeclRegion { : DeclRegion(fd, sReg, FieldRegionKind) {} public: - - void print(llvm::raw_ostream& os) const; - + + void dumpToStream(llvm::raw_ostream& os) const; + const FieldDecl* getDecl() const { return cast<FieldDecl>(D); } - - QualType getValueType(ASTContext& C) const { + + QualType getValueType(ASTContext& C) const { // FIXME: We can cache this if needed. return C.getCanonicalType(getDecl()->getType()); - } + } static void ProfileRegion(llvm::FoldingSetNodeID& ID, const 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, const 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) {} @@ -516,11 +494,13 @@ class ObjCIvarRegion : public DeclRegion { 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(); } - + + void dumpToStream(llvm::raw_ostream& os) const; + static bool classof(const MemRegion* R) { return R->getKind() == ObjCIvarRegionKind; } @@ -539,7 +519,7 @@ class ElementRegion : public TypedRegion { cast<nonloc::ConcreteInt>(&Idx)->getValue().isSigned()) && "The index must be signed"); } - + static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType elementType, SVal Idx, const MemRegion* superRegion); @@ -550,12 +530,14 @@ public: QualType getValueType(ASTContext&) const { return ElementType; } - + QualType getElementType() const { return ElementType; } - - void print(llvm::raw_ostream& os) const; + + RegionRawOffset getAsRawOffset() const; + + void dumpToStream(llvm::raw_ostream& os) const; void Profile(llvm::FoldingSetNodeID& ID) const; @@ -563,25 +545,13 @@ public: 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; + if (const RegionTy* RT = dyn_cast<RegionTy>(this)) + return RT; + + return NULL; } //===----------------------------------------------------------------------===// @@ -592,7 +562,7 @@ class MemRegionManager { ASTContext &C; llvm::BumpPtrAllocator& A; llvm::FoldingSet<MemRegion> Regions; - + MemSpaceRegion *globals; MemSpaceRegion *stack; MemSpaceRegion *stackArguments; @@ -604,11 +574,11 @@ public: MemRegionManager(ASTContext &c, llvm::BumpPtrAllocator& a) : C(c), A(a), globals(0), stack(0), stackArguments(0), heap(0), unknown(0), code(0) {} - + ~MemRegionManager() {} - + ASTContext &getContext() { return C; } - + /// getStackRegion - Retrieve the memory region associated with the /// current stack frame. MemSpaceRegion *getStackRegion(); @@ -616,11 +586,11 @@ public: /// getStackArgumentsRegion - Retrieve the memory region associated with /// function/method arguments of the current stack frame. MemSpaceRegion *getStackArgumentsRegion(); - + /// getGlobalsRegion - Retrieve the memory region associated with /// all global variables. MemSpaceRegion *getGlobalsRegion(); - + /// getHeapRegion - Retrieve the memory region associated with the /// generic "heap". MemSpaceRegion *getHeapRegion(); @@ -633,69 +603,77 @@ public: /// 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); - + 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); - + /// a specified VarDecl and LocationContext. + VarRegion* getVarRegion(const VarDecl *D, const LocationContext *LC); + /// getElementRegion - Retrieve the memory region associated with the /// associated element type, index, and super region. - ElementRegion* getElementRegion(QualType elementType, SVal Idx, - const MemRegion* superRegion,ASTContext &Ctx); + ElementRegion *getElementRegion(QualType elementType, SVal Idx, + const MemRegion *superRegion, + ASTContext &Ctx); + + ElementRegion *getElementRegionWithSuper(const ElementRegion *ER, + const MemRegion *superRegion) { + return getElementRegion(ER->getElementType(), ER->getIndex(), + superRegion, ER->getContext()); + } /// 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, + FieldRegion *getFieldRegion(const FieldDecl* fd, const MemRegion* superRegion); - + + FieldRegion *getFieldRegionWithSuper(const FieldRegion *FR, + const MemRegion *superRegion) { + return getFieldRegion(FR->getDecl(), 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, + ObjCIvarRegion *getObjCIvarRegion(const ObjCIvarDecl* ivd, const MemRegion* superRegion); - TypedViewRegion* getTypedViewRegion(QualType LValueType, - const MemRegion* superRegion); + CodeTextRegion *getCodeTextRegion(const FunctionDecl *FD); - CodeTextRegion* getCodeTextRegion(SymbolRef sym, QualType t); - CodeTextRegion* getCodeTextRegion(const FunctionDecl* fd, QualType t); - template <typename RegionTy, typename A1> RegionTy* getRegion(const A1 a1); - + template <typename RegionTy, typename A1> - RegionTy* getRegion(const A1 a1, const MemRegion* superRegion); - + RegionTy* getSubRegion(const A1 a1, const MemRegion* superRegion); + template <typename RegionTy, typename A1, typename A2> RegionTy* getRegion(const A1 a1, const A2 a2); - bool isGlobalsRegion(const MemRegion* R) { + bool isGlobalsRegion(const MemRegion* R) { assert(R); - return R == globals; + return R == globals; } - + private: MemSpaceRegion* LazyAllocate(MemSpaceRegion*& region); }; - + //===----------------------------------------------------------------------===// // Out-of-line member definitions. //===----------------------------------------------------------------------===// @@ -703,69 +681,69 @@ private: inline ASTContext& MemRegion::getContext() const { return getMemRegionManager()->getContext(); } - + template<typename RegionTy> struct MemRegionManagerTrait; - + template <typename RegionTy, typename A1> RegionTy* MemRegionManager::getRegion(const A1 a1) { const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1); - - llvm::FoldingSetNodeID ID; - RegionTy::ProfileRegion(ID, a1, superRegion); + + llvm::FoldingSetNodeID ID; + RegionTy::ProfileRegion(ID, a1, superRegion); void* InsertPos; RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos)); - + if (!R) { R = (RegionTy*) A.Allocate<RegionTy>(); new (R) RegionTy(a1, superRegion); Regions.InsertNode(R, InsertPos); } - + return R; } template <typename RegionTy, typename A1> -RegionTy* MemRegionManager::getRegion(const A1 a1, const MemRegion *superRegion) -{ - llvm::FoldingSetNodeID ID; - RegionTy::ProfileRegion(ID, a1, superRegion); +RegionTy* MemRegionManager::getSubRegion(const A1 a1, + const MemRegion *superRegion) { + llvm::FoldingSetNodeID ID; + RegionTy::ProfileRegion(ID, a1, superRegion); void* InsertPos; RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos)); - + if (!R) { R = (RegionTy*) A.Allocate<RegionTy>(); new (R) RegionTy(a1, superRegion); Regions.InsertNode(R, InsertPos); } - + return R; } - + template <typename RegionTy, typename A1, typename A2> RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) { - + const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2); - - llvm::FoldingSetNodeID ID; - RegionTy::ProfileRegion(ID, a1, a2, superRegion); + + llvm::FoldingSetNodeID ID; + RegionTy::ProfileRegion(ID, a1, a2, superRegion); void* InsertPos; RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos)); - + if (!R) { R = (RegionTy*) A.Allocate<RegionTy>(); new (R) RegionTy(a1, a2, superRegion); Regions.InsertNode(R, InsertPos); } - + return R; } - + //===----------------------------------------------------------------------===// // Traits for constructing regions. //===----------------------------------------------------------------------===// @@ -776,18 +754,18 @@ template <> struct MemRegionManagerTrait<AllocaRegion> { const Expr *, unsigned) { return MRMgr.getStackRegion(); } -}; - +}; + template <> struct MemRegionManagerTrait<CompoundLiteralRegion> { typedef MemRegion SuperRegionTy; static const SuperRegionTy* getSuperRegion(MemRegionManager& MRMgr, const CompoundLiteralExpr *CL) { - - return CL->isFileScope() ? MRMgr.getGlobalsRegion() + + return CL->isFileScope() ? MRMgr.getGlobalsRegion() : MRMgr.getStackRegion(); } }; - + template <> struct MemRegionManagerTrait<StringRegion> { typedef MemSpaceRegion SuperRegionTy; static const SuperRegionTy* getSuperRegion(MemRegionManager& MRMgr, @@ -795,20 +773,24 @@ template <> struct MemRegionManagerTrait<StringRegion> { return MRMgr.getGlobalsRegion(); } }; - + template <> struct MemRegionManagerTrait<VarRegion> { typedef MemRegion SuperRegionTy; - static const SuperRegionTy* getSuperRegion(MemRegionManager& MRMgr, - const VarDecl *d) { - if (d->hasLocalStorage()) { - return isa<ParmVarDecl>(d) || isa<ImplicitParamDecl>(d) + static const SuperRegionTy* getSuperRegion(MemRegionManager &MRMgr, + const VarDecl *D, + const LocationContext *LC) { + + // FIXME: Make stack regions have a location context? + + if (D->hasLocalStorage()) { + return isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D) ? MRMgr.getStackArgumentsRegion() : MRMgr.getStackRegion(); } - + return MRMgr.getGlobalsRegion(); } }; - + template <> struct MemRegionManagerTrait<SymbolicRegion> { typedef MemRegion SuperRegionTy; static const SuperRegionTy* getSuperRegion(MemRegionManager& MRMgr, @@ -820,7 +802,7 @@ template <> struct MemRegionManagerTrait<SymbolicRegion> { template<> struct MemRegionManagerTrait<CodeTextRegion> { typedef MemSpaceRegion SuperRegionTy; static const SuperRegionTy* getSuperRegion(MemRegionManager& MRMgr, - const FunctionDecl*, QualType) { + const FunctionDecl*) { return MRMgr.getCodeRegion(); } static const SuperRegionTy* getSuperRegion(MemRegionManager& MRMgr, @@ -828,7 +810,7 @@ template<> struct MemRegionManagerTrait<CodeTextRegion> { return MRMgr.getCodeRegion(); } }; - + } // end clang namespace //===----------------------------------------------------------------------===// @@ -836,10 +818,10 @@ template<> struct MemRegionManagerTrait<CodeTextRegion> { //===----------------------------------------------------------------------===// namespace llvm { -static inline raw_ostream& operator<<(raw_ostream& O, - const clang::MemRegion* R) { - R->print(O); - return O; +static inline raw_ostream& operator<<(raw_ostream& os, + const clang::MemRegion* R) { + R->dumpToStream(os); + return os; } } // end llvm namespace diff --git a/include/clang/Analysis/PathSensitive/SVals.h b/include/clang/Analysis/PathSensitive/SVals.h index 4bc5e27aacf05..4ba3c7396822e 100644 --- a/include/clang/Analysis/PathSensitive/SVals.h +++ b/include/clang/Analysis/PathSensitive/SVals.h @@ -18,7 +18,11 @@ #include "clang/Analysis/PathSensitive/SymbolManager.h" #include "llvm/Support/Casting.h" #include "llvm/ADT/ImmutableList.h" - + +namespace llvm { + class raw_ostream; +} + //==------------------------------------------------------------------------==// // Base SVal types. //==------------------------------------------------------------------------==// @@ -26,40 +30,43 @@ namespace clang { class CompoundValData; +class LazyCompoundValData; +class GRState; class BasicValueFactory; class MemRegion; +class TypedRegion; class MemRegionManager; class GRStateManager; class ValueManager; - + 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)); @@ -68,7 +75,7 @@ public: inline bool operator==(const SVal& R) const { return getRawKind() == R.getRawKind() && Data == R.Data; } - + inline bool operator!=(const SVal& R) const { return !(*this == R); } @@ -84,25 +91,25 @@ public: 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. + /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. /// Otherwise return 0. const FunctionDecl* getAsFunctionDecl() const; - - /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and + + /// 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; @@ -112,9 +119,9 @@ public: const SymExpr *getAsSymbolicExpression() const; const MemRegion *getAsRegion() const; - - void print(llvm::raw_ostream& OS) const; - void printStdErr() const; + + void dumpToStream(llvm::raw_ostream& OS) const; + void dump() const; // Iterators. class symbol_iterator { @@ -123,14 +130,14 @@ public: 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) @@ -138,97 +145,135 @@ public: 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; } + + void* getData() const { return Data; } }; -class NonLoc : public SVal { +class DefinedOrUnknownSVal : public SVal { +private: + // Do not implement. We want calling these methods to be a compiler + // error since they are tautologically false. + bool isUndef() const; + bool isValid() const; + protected: - NonLoc(unsigned SubKind, const void* d) : SVal(d, false, SubKind) {} + explicit DefinedOrUnknownSVal(const void* d, bool isLoc, unsigned ValKind) + : SVal(d, isLoc, ValKind) {} + + explicit DefinedOrUnknownSVal(BaseKind k, void *D = NULL) + : SVal(k, D) {} + +public: + // Implement isa<T> support. + static inline bool classof(const SVal *V) { + return !V->isUndef(); + } +}; +class UnknownVal : public DefinedOrUnknownSVal { public: - void print(llvm::raw_ostream& Out) const; + UnknownVal() : DefinedOrUnknownSVal(UnknownKind) {} + + static inline bool classof(const SVal *V) { + return V->getBaseKind() == UnknownKind; + } +}; +class DefinedSVal : public DefinedOrUnknownSVal { +private: + // Do not implement. We want calling these methods to be a compiler + // error since they are tautologically true/false. + bool isUnknown() const; + bool isUnknownOrUndef() const; + bool isValid() const; +protected: + DefinedSVal(const void* d, bool isLoc, unsigned ValKind) + : DefinedOrUnknownSVal(d, isLoc, ValKind) {} +public: + // Implement isa<T> support. + static inline bool classof(const SVal *V) { + return !V->isUnknownOrUndef(); + } +}; + +class NonLoc : public DefinedSVal { +protected: + NonLoc(unsigned SubKind, const void* d) : DefinedSVal(d, false, SubKind) {} + +public: + void dumpToStream(llvm::raw_ostream& Out) const; + // Implement isa<T> support. static inline bool classof(const SVal* V) { return V->getBaseKind() == NonLocKind; } }; -class Loc : public SVal { +class Loc : public DefinedSVal { protected: Loc(unsigned SubKind, const void* D) - : SVal(const_cast<void*>(D), true, SubKind) {} + : DefinedSVal(const_cast<void*>(D), true, SubKind) {} public: - void print(llvm::raw_ostream& Out) const; + void dumpToStream(llvm::raw_ostream& Out) const; - Loc(const Loc& X) : SVal(X.Data, true, X.getSubKind()) {} + Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {} Loc& operator=(const Loc& X) { memcpy(this, &X, sizeof(Loc)); return *this; } - + // 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(); + return T->isAnyPointerType() || T->isBlockPointerType(); } }; - + //==------------------------------------------------------------------------==// // Subclasses of NonLoc. //==------------------------------------------------------------------------==// namespace nonloc { - + enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, - LocAsIntegerKind, CompoundValKind }; + LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; 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 && + return V->getBaseKind() == NonLocKind && V->getSubKind() == SymbolValKind; } - + static inline bool classof(const NonLoc* V) { return V->getSubKind() == SymbolValKind; } }; -class SymExprVal : public NonLoc { +class SymExprVal : public NonLoc { public: SymExprVal(const SymExpr *SE) : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {} @@ -236,12 +281,12 @@ public: 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; } @@ -250,30 +295,30 @@ public: 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(ValueManager &ValMgr, BinaryOperator::Opcode Op, const ConcreteInt& R) const; - + ConcreteInt evalComplement(ValueManager &ValMgr) const; - + ConcreteInt evalMinus(ValueManager &ValMgr) 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 { friend class clang::ValueManager; @@ -281,28 +326,28 @@ class LocAsInteger : public NonLoc { 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; } @@ -317,10 +362,10 @@ public: const CompoundValData* getValue() const { return static_cast<CompoundValData*>(Data); } - + typedef llvm::ImmutableList<SVal>::iterator iterator; iterator begin() const; - iterator end() const; + iterator end() const; static bool classof(const SVal* V) { return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind; @@ -330,7 +375,28 @@ public: return V->getSubKind() == CompoundValKind; } }; - + +class LazyCompoundVal : public NonLoc { + friend class clang::ValueManager; + + LazyCompoundVal(const LazyCompoundValData *D) + : NonLoc(LazyCompoundValKind, D) {} +public: + const LazyCompoundValData *getCVData() const { + return static_cast<const LazyCompoundValData*>(Data); + } + const GRState *getState() const; + const TypedRegion *getRegion() const; + + static bool classof(const SVal *V) { + return V->getBaseKind() == NonLocKind && + V->getSubKind() == LazyCompoundValKind; + } + static bool classof(const NonLoc *V) { + return V->getSubKind() == LazyCompoundValKind; + } +}; + } // end namespace clang::nonloc //==------------------------------------------------------------------------==// @@ -338,27 +404,27 @@ public: //==------------------------------------------------------------------------==// 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: @@ -367,35 +433,37 @@ public: const MemRegion* getRegion() const { return static_cast<MemRegion*>(Data); } - + + const MemRegion* getBaseRegion() const; + 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); } @@ -403,19 +471,26 @@ public: // 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 +} // end clang::loc namespace +} // end clang namespace + +namespace llvm { +static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, + clang::SVal V) { + V.dumpToStream(os); + return os; +} +} // end llvm namespace #endif diff --git a/include/clang/Analysis/PathSensitive/SValuator.h b/include/clang/Analysis/PathSensitive/SValuator.h index 490c04e5978e9..e63eb12cf8ea8 100644 --- a/include/clang/Analysis/PathSensitive/SValuator.h +++ b/include/clang/Analysis/PathSensitive/SValuator.h @@ -9,7 +9,7 @@ // // This file defines SValuator, a class that defines the interface for // "symbolical evaluators" which construct an SVal from an expression. -// +// //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_ANALYSIS_SVALUATOR @@ -24,32 +24,66 @@ class GRState; class ValueManager; class SValuator { + friend class ValueManager; protected: ValueManager &ValMgr; - + + virtual SVal EvalCastNL(NonLoc val, QualType castTy) = 0; + + virtual SVal EvalCastL(Loc val, QualType castTy) = 0; + public: SValuator(ValueManager &valMgr) : ValMgr(valMgr) {} virtual ~SValuator() {} + + template <typename T> + class GenericCastResult : public std::pair<const GRState *, T> { + public: + const GRState *getState() const { return this->first; } + T getSVal() const { return this->second; } + GenericCastResult(const GRState *s, T v) + : std::pair<const GRState*,T>(s, v) {} + }; - virtual SVal EvalCast(NonLoc val, QualType castTy) = 0; + class CastResult : public GenericCastResult<SVal> { + public: + CastResult(const GRState *s, SVal v) : GenericCastResult<SVal>(s, v) {} + }; + + class DefinedOrUnknownCastResult : + public GenericCastResult<DefinedOrUnknownSVal> { + public: + DefinedOrUnknownCastResult(const GRState *s, DefinedOrUnknownSVal v) + : GenericCastResult<DefinedOrUnknownSVal>(s, v) {} + }; - virtual SVal EvalCast(Loc val, QualType castTy) = 0; + CastResult EvalCast(SVal V, const GRState *ST, + QualType castTy, QualType originalType); + DefinedOrUnknownCastResult EvalCast(DefinedOrUnknownSVal V, const GRState *ST, + QualType castTy, QualType originalType); + virtual SVal EvalMinus(NonLoc val) = 0; - + virtual SVal EvalComplement(NonLoc val) = 0; - virtual SVal EvalBinOpNN(BinaryOperator::Opcode Op, NonLoc lhs, - NonLoc rhs, QualType resultTy) = 0; + virtual SVal EvalBinOpNN(const GRState *state, BinaryOperator::Opcode Op, + NonLoc lhs, NonLoc rhs, QualType resultTy) = 0; virtual SVal EvalBinOpLL(BinaryOperator::Opcode Op, Loc lhs, Loc rhs, QualType resultTy) = 0; virtual SVal EvalBinOpLN(const GRState *state, BinaryOperator::Opcode Op, - Loc lhs, NonLoc rhs, QualType resultTy) = 0; -}; + Loc lhs, NonLoc rhs, QualType resultTy) = 0; -SValuator* CreateSimpleSValuator(ValueManager &valMgr); + SVal EvalBinOp(const GRState *ST, BinaryOperator::Opcode Op, + SVal L, SVal R, QualType T); + DefinedOrUnknownSVal EvalEQ(const GRState *ST, DefinedOrUnknownSVal L, + DefinedOrUnknownSVal R); +}; + +SValuator* CreateSimpleSValuator(ValueManager &valMgr); + } // end clang namespace #endif diff --git a/include/clang/Analysis/PathSensitive/Store.h b/include/clang/Analysis/PathSensitive/Store.h index 5aa53507fd141..3ff253d0abf30 100644 --- a/include/clang/Analysis/PathSensitive/Store.h +++ b/include/clang/Analysis/PathSensitive/Store.h @@ -23,16 +23,17 @@ #include "llvm/ADT/SmallVector.h" namespace clang { - + typedef const void* Store; -class GRState; +class GRState; class GRStateManager; class Stmt; class Expr; class ObjCIvarDecl; class SubRegionMap; - +class StackFrameContext; + class StoreManager { protected: ValueManager &ValMgr; @@ -43,37 +44,30 @@ protected: StoreManager(GRStateManager &stateMgr); -protected: - virtual const GRState *AddRegionView(const GRState *state, - const MemRegion *view, - const MemRegion *base) { - return state; - } - -public: +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 + /// \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; + virtual SValuator::CastResult 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 + /// \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 @@ -81,36 +75,31 @@ public: virtual const GRState *BindCompoundLiteral(const GRState *state, 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; - + virtual Store getInitialStore(const LocationContext *InitLoc) = 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 *state, const VarDecl *vd) = 0; + virtual SVal getLValueVar(const VarDecl *VD, const LocationContext *LC) = 0; + + virtual SVal getLValueString(const StringLiteral* sl) = 0; + + virtual SVal getLValueCompoundLiteral(const CompoundLiteralExpr* cl) = 0; - virtual SVal getLValueString(const GRState *state, - const StringLiteral* sl) = 0; + virtual SVal getLValueIvar(const ObjCIvarDecl* decl, SVal base) = 0; - virtual SVal getLValueCompoundLiteral(const GRState *state, - const CompoundLiteralExpr* cl) = 0; - - virtual SVal getLValueIvar(const GRState *state, const ObjCIvarDecl* decl, - SVal base) = 0; - - virtual SVal getLValueField(const GRState *state, SVal base, - const FieldDecl* D) = 0; - - virtual SVal getLValueElement(const GRState *state, QualType elementType, - SVal base, SVal offset) = 0; + virtual SVal getLValueField(const FieldDecl* D, SVal Base) = 0; + + virtual SVal getLValueElement(QualType elementType, SVal offset, SVal Base)=0; // FIXME: Make out-of-line. virtual SVal getSizeInElements(const GRState *state, const MemRegion *region){ @@ -120,7 +109,7 @@ public: /// 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 *region; @@ -129,33 +118,32 @@ public: const MemRegion* getRegion() const { return region; } CastResult(const GRState *s, const MemRegion* r = 0) : state(s), region(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 *region, - QualType CastToTy); + const MemRegion *CastRegion(const MemRegion *region, QualType CastToTy); /// EvalBinOp - Perform pointer arithmetic. virtual SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op, Loc lhs, NonLoc rhs, QualType resultTy) { 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, + + virtual void RemoveDeadBindings(GRState &state, Stmt* Loc, + SymbolReaper& SymReaper, llvm::SmallVectorImpl<const MemRegion*>& RegionRoots) = 0; - virtual const GRState *BindDecl(const GRState *state, const VarDecl *vd, - SVal initVal) = 0; + virtual const GRState *BindDecl(const GRState *ST, const VarDecl *VD, + const LocationContext *LC, SVal initVal) = 0; - virtual const GRState *BindDeclWithNoInit(const GRState *state, - const VarDecl *vd) = 0; + virtual const GRState *BindDeclWithNoInit(const GRState *ST, + const VarDecl *VD, + const LocationContext *LC) = 0; + + virtual const GRState *InvalidateRegion(const GRState *state, + const MemRegion *R, + const Expr *E, unsigned Count) = 0; // FIXME: Make out-of-line. virtual const GRState *setExtent(const GRState *state, @@ -163,25 +151,35 @@ public: return state; } - // FIXME: Make out-of-line. - virtual const GRState *setDefaultValue(const GRState *state, - const MemRegion *region, - SVal val) { + /// EnterStackFrame - Let the StoreManager to do something when execution + /// engine is about to execute into a callee. + virtual const GRState *EnterStackFrame(const GRState *state, + const StackFrameContext *frame) { return state; } virtual void print(Store store, llvm::raw_ostream& Out, const char* nl, const char *sep) = 0; - + class BindingsHandler { - public: + public: virtual ~BindingsHandler(); virtual bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion *region, SVal val) = 0; }; - + /// iterBindings - Iterate over the bindings in the Store. - virtual void iterBindings(Store store, BindingsHandler& f) = 0; + virtual void iterBindings(Store store, BindingsHandler& f) = 0; + +protected: + const MemRegion *MakeElementRegion(const MemRegion *Base, + QualType pointeeTy, uint64_t index = 0); + + /// CastRetrievedVal - Used by subclasses of StoreManager to implement + /// implicit casts that arise from loads from regions that are reinterpreted + /// as another region. + SValuator::CastResult CastRetrievedVal(SVal val, const GRState *state, + const TypedRegion *R, QualType castTy); }; // FIXME: Do we still need this? @@ -190,14 +188,14 @@ public: 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 *region, Visitor& V) const = 0; + + virtual bool iterSubRegions(const MemRegion *region, Visitor& V) const = 0; }; // FIXME: Do we need to pass GRStateManager anymore? diff --git a/include/clang/Analysis/PathSensitive/SymbolManager.h b/include/clang/Analysis/PathSensitive/SymbolManager.h index f32a7e3481dd2..d3996c6330a2a 100644 --- a/include/clang/Analysis/PathSensitive/SymbolManager.h +++ b/include/clang/Analysis/PathSensitive/SymbolManager.h @@ -21,66 +21,72 @@ #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" +#include "llvm/ADT/DenseSet.h" namespace llvm { class raw_ostream; } -namespace clang { +namespace clang { class MemRegion; + class TypedRegion; class ASTContext; class BasicValueFactory; } namespace clang { - + class SymExpr : public llvm::FoldingSetNode { public: - enum Kind { BEGIN_SYMBOLS, RegionValueKind, ConjuredKind, END_SYMBOLS, + enum Kind { BEGIN_SYMBOLS, + RegionValueKind, ConjuredKind, DerivedKind, + END_SYMBOLS, SymIntKind, SymSymKind }; private: Kind K; protected: - SymExpr(Kind k) : K(k) {} - + SymExpr(Kind k) : K(k) {} + public: virtual ~SymExpr() {} - - Kind getKind() const { return K; } - - virtual QualType getType(ASTContext&) const = 0; + + Kind getKind() const { return K; } + + void dump() const; + + virtual void dumpToStream(llvm::raw_ostream &os) const = 0; + + 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) {} + 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) { + 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; // We may cast the region to another type, so the expected type of the symbol @@ -90,7 +96,7 @@ class SymbolRegionValue : public SymbolData { public: SymbolRegionValue(SymbolID sym, const MemRegion *r, QualType t = QualType()) : SymbolData(RegionValueKind, sym), R(r), T(t) {} - + const MemRegion* getRegion() const { return R; } static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion* R, @@ -99,11 +105,13 @@ public: profile.AddPointer(R); T.Profile(profile); } - + virtual void Profile(llvm::FoldingSetNodeID& profile) { Profile(profile, R, T); } - + + void dumpToStream(llvm::raw_ostream &os) const; + QualType getType(ASTContext&) const; // Implement isa<T> support. @@ -123,15 +131,17 @@ public: 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; - + + void dumpToStream(llvm::raw_ostream &os) const; + static void Profile(llvm::FoldingSetNodeID& profile, const Stmt* S, - QualType T, unsigned Count, const void* SymbolTag) { + QualType T, unsigned Count, const void* SymbolTag) { profile.AddInteger((unsigned) ConjuredKind); profile.AddPointer(S); profile.Add(T); @@ -146,7 +156,39 @@ public: // Implement isa<T> support. static inline bool classof(const SymExpr* SE) { return SE->getKind() == ConjuredKind; - } + } +}; + +class SymbolDerived : public SymbolData { + SymbolRef parentSymbol; + const TypedRegion *R; + +public: + SymbolDerived(SymbolID sym, SymbolRef parent, const TypedRegion *r) + : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} + + SymbolRef getParentSymbol() const { return parentSymbol; } + const TypedRegion *getRegion() const { return R; } + + QualType getType(ASTContext&) const; + + void dumpToStream(llvm::raw_ostream &os) const; + + static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, + const TypedRegion *r) { + profile.AddInteger((unsigned) DerivedKind); + profile.AddPointer(r); + profile.AddPointer(parent); + } + + virtual void Profile(llvm::FoldingSetNodeID& profile) { + Profile(profile, parentSymbol, R); + } + + // Implement isa<T> support. + static inline bool classof(const SymExpr* SE) { + return SE->getKind() == DerivedKind; + } }; // SymIntExpr - Represents symbolic expression like 'x' + 3. @@ -163,14 +205,16 @@ public: // FIXME: We probably need to make this out-of-line to avoid redundant // generation of virtual functions. - QualType getType(ASTContext& C) const { return T; } - + QualType getType(ASTContext& C) const { return T; } + BinaryOperator::Opcode getOpcode() const { return Op; } - + + void dumpToStream(llvm::raw_ostream &os) const; + const SymExpr *getLHS() const { return LHS; } const llvm::APSInt &getRHS() const { return RHS; } - static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, + static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, BinaryOperator::Opcode op, const llvm::APSInt& rhs, QualType t) { ID.AddInteger((unsigned) SymIntKind); @@ -183,11 +227,11 @@ public: 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'. @@ -204,11 +248,13 @@ public: 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; } + void dumpToStream(llvm::raw_ostream &os) const; + static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { ID.AddInteger((unsigned) SymSymKind); @@ -221,45 +267,48 @@ public: 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; + DataSetTy DataSet; unsigned SymbolCounter; llvm::BumpPtrAllocator& BPAlloc; BasicValueFactory &BV; ASTContext& Ctx; - + public: - SymbolManager(ASTContext& ctx, BasicValueFactory &bv, + 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 SymbolRegionValue* getRegionValueSymbol(const MemRegion* R, QualType T = QualType()); 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) { + const void* SymbolTag = 0) { return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag); } + const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, + const TypedRegion *R); + 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); @@ -267,29 +316,28 @@ public: 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; + typedef llvm::DenseSet<SymbolRef> SetTy; + SetTy TheLiving; SetTy TheDead; LiveVariables& Liveness; SymbolManager& SymMgr; - + public: SymbolReaper(LiveVariables& liveness, SymbolManager& symmgr) - : TheLiving(F.GetEmptySet()), TheDead(F.GetEmptySet()), - Liveness(liveness), SymMgr(symmgr) {} + : Liveness(liveness), SymMgr(symmgr) {} + + ~SymbolReaper() {} bool isLive(SymbolRef sym); @@ -300,19 +348,19 @@ public: 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; + + typedef SetTy::const_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(); + return !TheDead.empty(); } }; - + class SymbolVisitor { public: // VisitSymbol - A visitor method invoked by @@ -321,11 +369,14 @@ public: 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); +static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, + const clang::SymExpr *SE) { + SE->dumpToStream(os); + return os; } +} // end llvm namespace #endif diff --git a/include/clang/Analysis/PathSensitive/ValueManager.h b/include/clang/Analysis/PathSensitive/ValueManager.h index 36d1df2150df9..8d162a681c446 100644 --- a/include/clang/Analysis/PathSensitive/ValueManager.h +++ b/include/clang/Analysis/PathSensitive/ValueManager.h @@ -16,82 +16,123 @@ #ifndef LLVM_CLANG_ANALYSIS_AGGREGATE_VALUE_MANAGER_H #define LLVM_CLANG_ANALYSIS_AGGREGATE_VALUE_MANAGER_H +#include "llvm/ADT/OwningPtr.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" +#include "clang/Analysis/PathSensitive/SValuator.h" namespace llvm { class BumpPtrAllocator; } -namespace clang { +namespace clang { + +class GRStateManager; + class ValueManager { - ASTContext &Context; + ASTContext &Context; BasicValueFactory BasicVals; - + /// SymMgr - Object that manages the symbol information. SymbolManager SymMgr; + /// SVator - SValuator object that creates SVals from expressions. + llvm::OwningPtr<SValuator> SVator; MemRegionManager MemMgr; - + + GRStateManager &StateMgr; + + const QualType ArrayIndexTy; + const unsigned ArrayIndexWidth; + public: - ValueManager(llvm::BumpPtrAllocator &alloc, ASTContext &context) - : Context(context), BasicVals(Context, alloc), - SymMgr(Context, BasicVals, alloc), - MemMgr(Context, alloc) {} + ValueManager(llvm::BumpPtrAllocator &alloc, ASTContext &context, + GRStateManager &stateMgr) + : Context(context), BasicVals(context, alloc), + SymMgr(context, BasicVals, alloc), + MemMgr(context, alloc), StateMgr(stateMgr), + ArrayIndexTy(context.IntTy), + ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) { + // FIXME: Generalize later. + SVator.reset(clang::CreateSimpleSValuator(*this)); + } // Accessors to submanagers. - + ASTContext &getContext() { return Context; } const ASTContext &getContext() const { return Context; } - + + GRStateManager &getStateManager() { return StateMgr; } + BasicValueFactory &getBasicValueFactory() { return BasicVals; } const BasicValueFactory &getBasicValueFactory() const { return BasicVals; } - + SymbolManager &getSymbolManager() { return SymMgr; } const SymbolManager &getSymbolManager() const { return SymMgr; } + SValuator &getSValuator() { return *SVator.get(); } + 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) { + const void* SymbolTag = 0) { return SymMgr.getConjuredSymbol(E, VisitCount, SymbolTag); } /// makeZeroVal - Construct an SVal representing '0' for the specified type. - SVal makeZeroVal(QualType T); + DefinedOrUnknownSVal makeZeroVal(QualType T); /// getRegionValueSymbolVal - make a unique symbol for value of R. - SVal getRegionValueSymbolVal(const MemRegion *R, QualType T = QualType()); - - SVal getRegionValueSymbolValOrUnknown(const MemRegion *R, QualType T) { - return SymMgr.canSymbolicate(T) ? getRegionValueSymbolVal(R, T) - : UnknownVal(); + DefinedOrUnknownSVal getRegionValueSymbolVal(const MemRegion *R, + QualType T = QualType()); + + DefinedOrUnknownSVal getRegionValueSymbolValOrUnknown(const MemRegion *R, + QualType T) { + if (SymMgr.canSymbolicate(T)) + return getRegionValueSymbolVal(R, T); + return UnknownVal(); } - - SVal getConjuredSymbolVal(const Expr *E, unsigned Count); - SVal getConjuredSymbolVal(const Expr* E, QualType T, unsigned Count); - SVal getFunctionPointer(const FunctionDecl* FD); + DefinedOrUnknownSVal getConjuredSymbolVal(const void *SymbolTag, + const Expr *E, unsigned Count); + DefinedOrUnknownSVal getConjuredSymbolVal(const void *SymbolTag, + const Expr *E, QualType T, + unsigned Count); + + DefinedOrUnknownSVal getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, + const TypedRegion *R); + + DefinedSVal getFunctionPointer(const FunctionDecl *FD); NonLoc makeCompoundVal(QualType T, llvm::ImmutableList<SVal> Vals) { return nonloc::CompoundVal(BasicVals.getCompoundValData(T, Vals)); } + NonLoc makeLazyCompoundVal(const GRState *state, const TypedRegion *R) { + return nonloc::LazyCompoundVal(BasicVals.getLazyCompoundValData(state, R)); + } + NonLoc makeZeroArrayIndex() { - return nonloc::ConcreteInt(BasicVals.getZeroWithPtrWidth(false)); + return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy)); + } + + NonLoc makeArrayIndex(uint64_t idx) { + return nonloc::ConcreteInt(BasicVals.getValue(idx, ArrayIndexTy)); } + SVal convertToArrayIndex(SVal V); + nonloc::ConcreteInt makeIntVal(const IntegerLiteral* I) { return nonloc::ConcreteInt(BasicVals.getValue(I->getValue(), I->getType()->isUnsignedIntegerType())); @@ -100,7 +141,7 @@ public: nonloc::ConcreteInt makeIntVal(const llvm::APSInt& V) { return nonloc::ConcreteInt(BasicVals.getValue(V)); } - + loc::ConcreteInt makeIntLocVal(const llvm::APSInt &v) { return loc::ConcreteInt(BasicVals.getValue(v)); } @@ -109,7 +150,10 @@ public: return nonloc::ConcreteInt(BasicVals.getValue(V, isUnsigned)); } - NonLoc makeIntVal(uint64_t X, QualType T) { + DefinedSVal makeIntVal(uint64_t X, QualType T) { + if (Loc::IsLocType(T)) + return loc::ConcreteInt(BasicVals.getValue(X, T)); + return nonloc::ConcreteInt(BasicVals.getValue(X, T)); } @@ -117,6 +161,10 @@ public: return nonloc::ConcreteInt(BasicVals.getIntValue(X, isUnsigned)); } + NonLoc makeIntValWithPtrWidth(uint64_t X, bool isUnsigned) { + return nonloc::ConcreteInt(BasicVals.getIntWithPtrWidth(X, isUnsigned)); + } + NonLoc makeIntVal(uint64_t X, unsigned BitWidth, bool isUnsigned) { return nonloc::ConcreteInt(BasicVals.getValue(X, BitWidth, isUnsigned)); } @@ -127,10 +175,10 @@ public: 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) { return nonloc::ConcreteInt(BasicVals.getTruthValue(b, T)); } |