diff options
Diffstat (limited to 'clang')
19 files changed, 768 insertions, 468 deletions
diff --git a/clang/include/clang/Analysis/PathSensitive/Environment.h b/clang/include/clang/Analysis/PathSensitive/Environment.h index 9c9dc54886a..8e1b97a3bec 100644 --- a/clang/include/clang/Analysis/PathSensitive/Environment.h +++ b/clang/include/clang/Analysis/PathSensitive/Environment.h @@ -19,6 +19,7 @@ #include "clang/Analysis/PathSensitive/Store.h" #include "llvm/ADT/ImmutableMap.h" +#include "llvm/ADT/SmallVector.h" #include "clang/Analysis/PathSensitive/RValues.h" #include "llvm/Support/Allocator.h" #include "llvm/ADT/FoldingSet.h" @@ -138,11 +139,10 @@ public: Environment SetRVal(const Environment& Env, Expr* E, RVal V, bool isBlkExpr, bool Invalidate); - Environment RemoveDeadBindings(Environment Env, - Stmt* Loc, - const LiveVariables& Liveness, - StoreManager::DeclRootsTy& DRoots, - StoreManager::LiveSymbolsTy& LSymbols); + Environment RemoveDeadBindings(Environment Env, Stmt* Loc, + const LiveVariables& Liveness, + llvm::SmallVectorImpl<const MemRegion*>& DRoots, + StoreManager::LiveSymbolsTy& LSymbols); }; } // end clang namespace diff --git a/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h b/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h index 5b713d9c18a..0bcc13781f8 100644 --- a/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -410,6 +410,10 @@ public: return SetRVal(St, const_cast<Expr*>(Ex), V); } + LVal getLVal(VarDecl* V) { + return getStateManager().getLVal(V); + } + protected: const GRState* SetBlkExprRVal(const GRState* St, Expr* Ex, RVal V) { diff --git a/clang/include/clang/Analysis/PathSensitive/GRState.h b/clang/include/clang/Analysis/PathSensitive/GRState.h index fd81a86946f..992174c2a33 100644 --- a/clang/include/clang/Analysis/PathSensitive/GRState.h +++ b/clang/include/clang/Analysis/PathSensitive/GRState.h @@ -19,6 +19,7 @@ #include "clang/Analysis/PathSensitive/Environment.h" #include "clang/Analysis/PathSensitive/Store.h" #include "clang/Analysis/PathSensitive/ConstraintManager.h" +#include "clang/Analysis/PathSensitive/MemRegion.h" #include "clang/Analysis/PathSensitive/RValues.h" #include "clang/Analysis/PathSensitive/GRCoreEngine.h" #include "clang/AST/Expr.h" @@ -133,20 +134,6 @@ public: } // Iterators. - - // FIXME: We'll be removing the VarBindings iterator very soon. Right now - // it assumes that Store is a VarBindingsTy. - typedef llvm::ImmutableMap<VarDecl*,RVal> VarBindingsTy; - typedef VarBindingsTy::iterator vb_iterator; - vb_iterator vb_begin() const { - VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St)); - return B.begin(); - } - vb_iterator vb_end() const { - VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St)); - return B.end(); - } - typedef Environment::seb_iterator seb_iterator; seb_iterator seb_begin() const { return Env.seb_begin(); } seb_iterator seb_end() const { return Env.beb_end(); } @@ -249,6 +236,7 @@ private: EnvironmentManager EnvMgr; llvm::OwningPtr<StoreManager> StMgr; llvm::OwningPtr<ConstraintManager> ConstraintMgr; + MemRegionManager MRMgr; GRState::IntSetTy::Factory ISetFactory; GRState::GenericDataMap::Factory GDMFactory; @@ -273,10 +261,6 @@ private: /// Alloc - A BumpPtrAllocator to allocate states. llvm::BumpPtrAllocator& Alloc; - /// DRoots - A vector to hold of worklist used by RemoveDeadSymbols. - /// This vector is persistent because it is reused over and over. - StoreManager::DeclRootsTy DRoots; - /// CurrentStmt - The block-level statement currently being visited. This /// is set by GRExprEngine. Stmt* CurrentStmt; @@ -297,10 +281,10 @@ private: Environment RemoveBlkExpr(const Environment& Env, Expr* E) { return EnvMgr.RemoveBlkExpr(Env, E); } - + // FIXME: Remove when we do lazy initializaton of variable bindings. const GRState* BindVar(const GRState* St, VarDecl* D, RVal V) { - return SetRVal(St, lval::DeclVal(D), V); + return SetRVal(St, getLVal(D), V); } public: @@ -313,7 +297,8 @@ public: ConstraintManagerCreator CreateConstraintManager, llvm::BumpPtrAllocator& alloc, CFG& c, LiveVariables& L) : EnvMgr(alloc), - ISetFactory(alloc), + MRMgr(alloc), + ISetFactory(alloc), GDMFactory(alloc), BasicVals(Ctx, alloc), SymMgr(alloc), @@ -334,6 +319,7 @@ public: SymbolManager& getSymbolManager() { return SymMgr; } LiveVariables& getLiveVariables() { return Liveness; } llvm::BumpPtrAllocator& getAllocator() { return Alloc; } + MemRegionManager& getRegionManager() { return MRMgr; } typedef StoreManager::DeadSymbolsTy DeadSymbolsTy; @@ -350,6 +336,17 @@ public: return getPersistentState(NewSt); } + + // Utility methods for getting regions. + + VarRegion* getRegion(const VarDecl* D) { + return MRMgr.getVarRegion(D); + } + + lval::MemRegionVal getLVal(const VarDecl* D) { + return lval::MemRegionVal(getRegion(D)); + } + // Methods that query & manipulate the Environment. RVal GetRVal(const GRState* St, Expr* Ex) { @@ -394,19 +391,17 @@ public: // Methods that manipulate the GDM. const GRState* addGDM(const GRState* St, void* Key, void* Data); - // Methods that query & manipulate the Store. - - /// getBindings - Returns all store bindings in the specified state that bind - /// to the specified symbolic value. - void getBindings(llvm::SmallVectorImpl<store::Binding>& bindings, - const GRState* St, SymbolID Sym) { - StMgr->getBindings(bindings, St->getStore(), Sym); + // Methods that query or create regions. + bool hasStackStorage(const MemRegion* R) { + return getRegionManager().hasStackStorage(R); } - /// BindingAsString - Returns a string representing the given store binding. - std::string BindingAsString(store::Binding binding) { - return StMgr->BindingAsString(binding); + // Methods that query & manipulate the Store. + + void iterBindings(const GRState* state, StoreManager::BindingsHandler& F) { + StMgr->iterBindings(state->getStore(), F); } + RVal GetRVal(const GRState* St, LVal LV, QualType T = QualType()) { return StMgr->GetRVal(St->getStore(), LV, T); diff --git a/clang/include/clang/Analysis/PathSensitive/MemRegion.h b/clang/include/clang/Analysis/PathSensitive/MemRegion.h new file mode 100644 index 00000000000..79705613ab9 --- /dev/null +++ b/clang/include/clang/Analysis/PathSensitive/MemRegion.h @@ -0,0 +1,267 @@ +//== MemRegion.h - Abstract memory regions for static analysis --*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines MemRegion and its subclasses. MemRegion defines a +// partially-typed abstraction of memory useful for path-sensitive dataflow +// analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_MEMREGION_H +#define LLVM_CLANG_ANALYSIS_MEMREGION_H + +#include "llvm/Support/Casting.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/Support/Allocator.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclObjC.h" +#include <string> + +namespace llvm { class raw_ostream; } + +namespace clang { + +class MemRegionManager; + + +/// MemRegion - The root abstract class for all memory regions. +class MemRegion : public llvm::FoldingSetNode { +public: + enum Kind { MemSpaceRegionKind, + // Typed regions. + BEG_TYPED_REGIONS, + VarRegionKind, FieldRegionKind, ObjCIvarRegionKind, + AnonTypedRegionKind, + END_TYPED_REGIONS }; +private: + const Kind kind; + +protected: + MemRegion(Kind k) : kind(k) {} + virtual ~MemRegion(); + +public: + // virtual MemExtent getExtent(MemRegionManager& mrm) const = 0; + virtual const MemRegion* getSuperRegion() const = 0; + virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0; + + std::string getString() const; + virtual void print(llvm::raw_ostream& os) const; + + Kind getKind() const { return kind; } + static bool classof(const MemRegion*) { return true; } +}; + +/// MemSpaceRegion - A memory region that represents and "memory space"; +/// for example, the set of global variables, the stack frame, etc. +class MemSpaceRegion : public MemRegion { + friend class MemRegionManager; + MemSpaceRegion() : MemRegion(MemSpaceRegionKind) {} + +public: + //RegionExtent getExtent() const { return UndefinedExtent(); } + + const MemRegion* getSuperRegion() const { + return 0; + } + + //static void ProfileRegion(llvm::FoldingSetNodeID& ID); + void Profile(llvm::FoldingSetNodeID& ID) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == MemSpaceRegionKind; + } +}; + +/// TypedRegion - An abstract class representing regions that are typed. +class TypedRegion : public MemRegion { +protected: + const MemRegion* superRegion; + + TypedRegion(const MemRegion* sReg, Kind k) + : MemRegion(k), superRegion(sReg) {}; + +public: + virtual QualType getType() const = 0; + + // MemExtent getExtent(MemRegionManager& mrm) const; + const MemRegion* getSuperRegion() const { + return superRegion; + } + + static bool classof(const MemRegion* R) { + unsigned k = R->getKind(); + return k > BEG_TYPED_REGIONS && k < END_TYPED_REGIONS; + } +}; + +/// AnonTypedRegion - An "anonymous" region that simply types a chunk +/// of memory. +class AnonTypedRegion : public TypedRegion { + QualType T; + + friend class MemRegionManager; + + AnonTypedRegion(QualType t, MemRegion* sreg) + : TypedRegion(sreg, AnonTypedRegionKind), T(t) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType T, + const MemRegion* superRegion); + +public: + QualType getType() const { return T; } + + + void Profile(llvm::FoldingSetNodeID& ID) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == AnonTypedRegionKind; + } +}; + +class DeclRegion : public TypedRegion { +protected: + const Decl* D; + + DeclRegion(const Decl* d, MemRegion* sReg, Kind k) + : TypedRegion(sReg, k), D(d) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D, + const MemRegion* superRegion, Kind k); + +public: + void Profile(llvm::FoldingSetNodeID& ID) const; +}; + +class VarRegion : public DeclRegion { + friend class MemRegionManager; + + VarRegion(const VarDecl* vd, MemRegion* sReg) + : DeclRegion(vd, sReg, VarRegionKind) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, VarDecl* VD, + const MemRegion* superRegion) { + DeclRegion::ProfileRegion(ID, VD, superRegion, VarRegionKind); + } + +public: + const VarDecl* getDecl() const { return cast<VarDecl>(D); } + QualType getType() const { return getDecl()->getType(); } + + void print(llvm::raw_ostream& os) const; + + static bool classof(const MemRegion* R) { + return R->getKind() == VarRegionKind; + } +}; + +class FieldRegion : public DeclRegion { + friend class MemRegionManager; + + FieldRegion(const FieldDecl* fd, MemRegion* sReg) + : DeclRegion(fd, sReg, FieldRegionKind) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, FieldDecl* FD, + const MemRegion* superRegion) { + DeclRegion::ProfileRegion(ID, FD, superRegion, FieldRegionKind); + } + +public: + const FieldDecl* getDecl() const { return cast<FieldDecl>(D); } + QualType getType() const { return getDecl()->getType(); } + + static bool classof(const MemRegion* R) { + return R->getKind() == FieldRegionKind; + } +}; + +class ObjCIvarRegion : public DeclRegion { + + friend class MemRegionManager; + + ObjCIvarRegion(const ObjCIvarDecl* ivd, MemRegion* sReg) + : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {} + + static void ProfileRegion(llvm::FoldingSetNodeID& ID, ObjCIvarDecl* ivd, + const MemRegion* superRegion) { + DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind); + } + +public: + const ObjCIvarDecl* getDecl() const { return cast<ObjCIvarDecl>(D); } + QualType getType() const { return getDecl()->getType(); } + + static bool classof(const MemRegion* R) { + return R->getKind() == ObjCIvarRegionKind; + } +}; + +//===----------------------------------------------------------------------===// +// MemRegionManager - Factory object for creating regions. +//===----------------------------------------------------------------------===// + +class MemRegionManager { + llvm::BumpPtrAllocator& A; + llvm::FoldingSet<MemRegion> Regions; + + MemSpaceRegion* globals; + MemSpaceRegion* stack; + MemSpaceRegion* heap; + +public: + MemRegionManager(llvm::BumpPtrAllocator& a) + : A(a), globals(0), stack(0), heap(0) {} + + ~MemRegionManager() {} + + /// getStackRegion - Retrieve the memory region associated with the + /// current stack frame. + MemSpaceRegion* getStackRegion(); + + /// getGlobalsRegion - Retrieve the memory region associated with + /// all global variables. + MemSpaceRegion* getGlobalsRegion(); + + /// getHeapRegion - Retrieve the memory region associated with the + /// generic "heap". + MemSpaceRegion* getHeapRegion(); + + /// getVarRegion - Retrieve or create the memory region associated with + /// a specified VarDecl. 'superRegion' corresponds to the containing + /// memory region, and 'off' is the offset within the containing region. + VarRegion* getVarRegion(const VarDecl* vd, MemRegion* superRegion); + + VarRegion* getVarRegion(const VarDecl* vd) { + return getVarRegion(vd, vd->hasLocalStorage() ? getStackRegion() + : getGlobalsRegion()); + } + + /// 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, 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, + MemRegion* superRegion); + + bool hasStackStorage(const MemRegion* R); + +private: + MemSpaceRegion* LazyAllocate(MemSpaceRegion*& region); +}; + + + +} // end clang namespace +#endif diff --git a/clang/include/clang/Analysis/PathSensitive/RValues.h b/clang/include/clang/Analysis/PathSensitive/RValues.h index 9034c0d4ae2..82e51193739 100644 --- a/clang/include/clang/Analysis/PathSensitive/RValues.h +++ b/clang/include/clang/Analysis/PathSensitive/RValues.h @@ -24,6 +24,9 @@ namespace clang { +class MemRegion; +class GRStateManager; + class RVal { public: enum BaseKind { UndefinedKind, UnknownKind, LValKind, NonLValKind }; @@ -92,7 +95,7 @@ public: symbol_iterator symbol_begin() const; symbol_iterator symbol_end() const; - static RVal MakeVal(BasicValueFactory& BasicVals, DeclRefExpr* E); + static RVal MakeVal(GRStateManager& SMgr, DeclRefExpr* E); // Implement isa<T> support. static inline bool classof(const RVal*) { return true; } @@ -285,7 +288,7 @@ public: namespace lval { -enum Kind { SymbolValKind, GotoLabelKind, DeclValKind, FuncValKind, +enum Kind { SymbolValKind, GotoLabelKind, MemRegionKind, FuncValKind, ConcreteIntKind, StringLiteralValKind, FieldOffsetKind, ArrayOffsetKind }; @@ -327,30 +330,30 @@ public: }; -class DeclVal : public LVal { +class MemRegionVal : public LVal { public: - DeclVal(const VarDecl* vd) : LVal(DeclValKind, vd) {} - - VarDecl* getDecl() const { - return static_cast<VarDecl*>(Data); + MemRegionVal(const MemRegion* r) : LVal(MemRegionKind, r) {} + + MemRegion* getRegion() const { + return static_cast<MemRegion*>(Data); } - inline bool operator==(const DeclVal& R) const { - return getDecl() == R.getDecl(); + inline bool operator==(const MemRegionVal& R) const { + return getRegion() == R.getRegion(); } - inline bool operator!=(const DeclVal& R) const { - return getDecl() != R.getDecl(); + inline bool operator!=(const MemRegionVal& R) const { + return getRegion() != R.getRegion(); } // Implement isa<T> support. static inline bool classof(const RVal* V) { return V->getBaseKind() == LValKind && - V->getSubKind() == DeclValKind; + V->getSubKind() == MemRegionKind; } static inline bool classof(const LVal* V) { - return V->getSubKind() == DeclValKind; + return V->getSubKind() == MemRegionKind; } }; diff --git a/clang/include/clang/Analysis/PathSensitive/Store.h b/clang/include/clang/Analysis/PathSensitive/Store.h index fc9b7f3d078..4300954eac2 100644 --- a/clang/include/clang/Analysis/PathSensitive/Store.h +++ b/clang/include/clang/Analysis/PathSensitive/Store.h @@ -19,127 +19,21 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallVector.h" -#include <vector> #include <iosfwd> namespace clang { typedef const void* Store; -namespace store { - /// Region - A region represents an abstract chunk of memory. Subclasses - /// of StoreManager are responsible for defining the particular semantics - /// of Region for the store they represent. - class Region { - protected: - const void* Data; - Region(const void* data) : Data(data) {} - public: - Region() : Data(0) {} - }; - - /// Binding - A "binding" represents a binding of a value to an abstract - /// chunk of memory (which is represented by a region). Subclasses of - /// StoreManager are responsible for defining the particular semantics - /// of a Binding. - class Binding { - protected: - const void* first; - const void* second; - Binding(const void* f, const void* s = 0) : first(f), second(s) {} - public: - Binding() : first(0), second(0) {} - operator bool() const { return first || second; } - }; - - /// RegionExtent - Represents the size, or extent, or an abstract memory - /// chunk (a region). Sizes are in bits. RegionExtent is essentially a - /// variant with three subclasses: UnknownExtent, FixedExtent, - /// and SymbolicExtent. - class RegionExtent { - public: - enum Kind { Unknown = 0, Fixed = 0, Sym = 1 }; - - protected: - const uintptr_t Raw; - RegionExtent(uintptr_t raw, Kind k) : Raw(raw | k) {} - uintptr_t getData() const { return Raw & ~0x1; } - - public: - // Folding-set profiling. - void Profile(llvm::FoldingSetNodeID& ID) const { - ID.AddPointer((void*) Raw); - } - // Comparing extents. - bool operator==(const RegionExtent& R) const { - return Raw == R.Raw; - } - bool operator!=(const RegionExtent& R) const { - return Raw != R.Raw; - } - // Implement isa<T> support. - Kind getKind() const { return Kind(Raw & 0x1); } - uintptr_t getRaw() const { return Raw; } - - static inline bool classof(const RegionExtent*) { - return true; - } - }; - - /// UnknownExtent - Represents a region extent with no available information - /// about the size of the region. - class UnknownExtent : public RegionExtent { - public: - UnknownExtent() : RegionExtent(0,Unknown) {} - - // Implement isa<T> support. - static inline bool classof(const RegionExtent* E) { - return E->getRaw() == 0; - } - }; - - /// FixedExtent - Represents a region extent with a known fixed size. - /// Typically FixedExtents are used to represent the size of variables, but - /// they can also be used to represent the size of a constant-sized array. - class FixedExtent : public RegionExtent { - public: - FixedExtent(const llvm::APSInt& X) : RegionExtent((uintptr_t) &X, Fixed) {} - - const llvm::APSInt& getInt() const { - return *((llvm::APSInt*) getData()); - } - - // Implement isa<T> support. - static inline bool classof(const RegionExtent* E) { - return E->getKind() == Fixed && E->getRaw() != 0; - } - }; - - /// SymbolicExtent - Represents the extent of a region where the extent - /// itself is a symbolic value. These extents can be used to represent - /// the sizes of dynamically allocated chunks of memory with variable size. - class SymbolicExtent : public RegionExtent { - public: - SymbolicExtent(SymbolID S) : RegionExtent(S.getNumber() << 1, Sym) {} - - SymbolID getSymbol() const { return SymbolID(getData() >> 1); } - - // Implement isa<T> support. - static inline bool classof(const RegionExtent* E) { - return E->getKind() == Sym; - } - }; -} // end store namespace - class GRStateManager; class LiveVariables; class Stmt; +class MemRegion; class StoreManager { public: typedef llvm::SmallSet<SymbolID, 20> LiveSymbolsTy; typedef llvm::DenseSet<SymbolID> DeadSymbolsTy; - typedef std::vector<ValueDecl*> DeclRootsTy; virtual ~StoreManager() {} virtual RVal GetRVal(Store St, LVal LV, QualType T = QualType()) = 0; @@ -147,10 +41,10 @@ public: virtual Store Remove(Store St, LVal LV) = 0; virtual Store getInitialStore(GRStateManager& StateMgr) = 0; - virtual Store RemoveDeadBindings(Store store, Stmt* Loc, - const LiveVariables& Live, - DeclRootsTy& DRoots, LiveSymbolsTy& LSymbols, - DeadSymbolsTy& DSymbols) = 0; + virtual Store + RemoveDeadBindings(Store store, Stmt* Loc, const LiveVariables& Live, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots, + LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols) = 0; virtual Store AddDecl(Store store, GRStateManager& StMgr, const VarDecl* VD, Expr* Ex, @@ -163,29 +57,14 @@ public: public: virtual ~BindingsHandler(); virtual bool HandleBinding(StoreManager& SMgr, Store store, - store::Binding binding) = 0; + MemRegion* R, RVal val) = 0; }; /// iterBindings - Iterate over the bindings in the Store. - virtual void iterBindings(Store store, BindingsHandler& f) = 0; - - /// getBindings - Returns all bindings in the specified store that bind - /// to the specified symbolic value. - void getBindings(llvm::SmallVectorImpl<store::Binding>& bindings, - Store store, SymbolID Sym); - - /// BindingAsString - Returns a string representing the given binding. - virtual std::string BindingAsString(store::Binding binding) = 0; - - /// getExtent - Returns the size of the region in bits. - virtual store::RegionExtent getExtent(store::Region R) = 0; - - /// getRVal - Returns the bound RVal for a given binding. - virtual RVal getRVal(Store store, store::Binding binding) = 0; + virtual void iterBindings(Store store, BindingsHandler& f) = 0; }; StoreManager* CreateBasicStoreManager(GRStateManager& StMgr); - } // end clang namespace diff --git a/clang/lib/Analysis/BasicConstraintManager.cpp b/clang/lib/Analysis/BasicConstraintManager.cpp index 0576eaf2a14..66bf082b136 100644 --- a/clang/lib/Analysis/BasicConstraintManager.cpp +++ b/clang/lib/Analysis/BasicConstraintManager.cpp @@ -129,7 +129,7 @@ const GRState* BasicConstraintManager::AssumeAux(const GRState* St, LVal Cond, return AssumeSymEQ(St, cast<lval::SymbolVal>(Cond).getSymbol(), BasicVals.getZeroWithPtrWidth(), isFeasible); - case lval::DeclValKind: + case lval::MemRegionKind: case lval::FuncValKind: case lval::GotoLabelKind: case lval::StringLiteralValKind: diff --git a/clang/lib/Analysis/BasicObjCFoundationChecks.cpp b/clang/lib/Analysis/BasicObjCFoundationChecks.cpp index 521f317d631..b3f534d1af0 100644 --- a/clang/lib/Analysis/BasicObjCFoundationChecks.cpp +++ b/clang/lib/Analysis/BasicObjCFoundationChecks.cpp @@ -20,6 +20,7 @@ #include "clang/Analysis/PathSensitive/GRExprEngine.h" #include "clang/Analysis/PathSensitive/GRState.h" #include "clang/Analysis/PathSensitive/BugReporter.h" +#include "clang/Analysis/PathSensitive/MemRegion.h" #include "clang/Analysis/PathDiagnostic.h" #include "clang/Analysis/LocalCheckers.h" @@ -366,7 +367,7 @@ public: private: - void AddError(VarDecl* V, Expr* Ex, ExplodedNode<GRState> *N, + void AddError(TypedRegion* R, Expr* Ex, ExplodedNode<GRState> *N, uint64_t SourceSize, uint64_t TargetSize, uint64_t NumberKind); }; } // end anonymous namespace @@ -497,12 +498,17 @@ bool AuditCFNumberCreate::Audit(ExplodedNode<GRState>* N,GRStateManager&){ // FIXME: Eventually we should handle arbitrary locations. We can do this // by having an enhanced memory model that does low-level typing. - lval::DeclVal* LV = dyn_cast<lval::DeclVal>(&TheValueExpr); + lval::MemRegionVal* LV = dyn_cast<lval::MemRegionVal>(&TheValueExpr); if (!LV) return false; - QualType T = Ctx.getCanonicalType(LV->getDecl()->getType()); + TypedRegion* R = dyn_cast<TypedRegion>(LV->getRegion()); + if (!R) + return false; + + + QualType T = Ctx.getCanonicalType(R->getType()); // FIXME: If the pointee isn't an integer type, should we flag a warning? // People can do weird stuff with pointers. @@ -517,14 +523,14 @@ bool AuditCFNumberCreate::Audit(ExplodedNode<GRState>* N,GRStateManager&){ if (SourceSize == TargetSize) return false; - AddError(LV->getDecl(), CE->getArg(2), N, SourceSize, TargetSize, NumberKind); + AddError(R, CE->getArg(2), N, SourceSize, TargetSize, NumberKind); // FIXME: We can actually create an abstract "CFNumber" object that has // the bits initialized to the provided values. return SourceSize < TargetSize; } -void AuditCFNumberCreate::AddError(VarDecl* V, Expr* Ex, +void AuditCFNumberCreate::AddError(TypedRegion* R, Expr* Ex, ExplodedNode<GRState> *N, uint64_t SourceSize, uint64_t TargetSize, uint64_t NumberKind) { diff --git a/clang/lib/Analysis/BasicStore.cpp b/clang/lib/Analysis/BasicStore.cpp index 97566798c0b..4616143d136 100644 --- a/clang/lib/Analysis/BasicStore.cpp +++ b/clang/lib/Analysis/BasicStore.cpp @@ -18,10 +18,8 @@ #include "llvm/Support/Streams.h" using namespace clang; -using store::Region; -using store::RegionExtent; -typedef llvm::ImmutableMap<VarDecl*,RVal> VarBindingsTy; +typedef llvm::ImmutableMap<const VarDecl*,RVal> VarBindingsTy; namespace { @@ -40,10 +38,10 @@ public: virtual Store getInitialStore(GRStateManager& StateMgr); - virtual Store RemoveDeadBindings(Store store, Stmt* Loc, - const LiveVariables& Live, - DeclRootsTy& DRoots, LiveSymbolsTy& LSymbols, - DeadSymbolsTy& DSymbols); + virtual Store + RemoveDeadBindings(Store store, Stmt* Loc, const LiveVariables& Live, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots, + LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols); virtual void iterBindings(Store store, BindingsHandler& f); @@ -57,42 +55,9 @@ public: virtual void print(Store store, std::ostream& Out, const char* nl, const char *sep); - - virtual RegionExtent getExtent(Region R); - - /// BindingAsString - Returns a string representing the given binding. - virtual std::string BindingAsString(store::Binding binding); - - /// getRVal - Returns the bound RVal for a given binding. - virtual RVal getRVal(Store store, store::Binding binding); -}; - -class VISIBILITY_HIDDEN VarRegion : public store::Region { -public: - VarRegion(VarDecl* VD) : Region(VD) {} - VarDecl* getDecl() const { return (VarDecl*) Data; } - static bool classof(const store::Region*) { return true; } -}; - -class VISIBILITY_HIDDEN VarBinding : public store::Binding { -public: - VarBinding(VarBindingsTy::value_type* T) : store::Binding(T) {} - - const VarBindingsTy::value_type_ref getValue() const { - return *static_cast<const VarBindingsTy::value_type*>(first); - } - std::string getName() const { - return getValue().first->getName(); - } - - RVal getRVal() const { - return getValue().second; - } - - static inline bool classof(const store::Binding*) { return true; } }; - + } // end anonymous namespace @@ -100,22 +65,6 @@ StoreManager* clang::CreateBasicStoreManager(GRStateManager& StMgr) { return new BasicStoreManager(StMgr); } -RegionExtent BasicStoreManager::getExtent(Region R) { - QualType T = cast<VarRegion>(&R)->getDecl()->getType(); - - // FIXME: Add support for VLAs. This may require passing in additional - // information, or tracking a different region type. - if (!T.getTypePtr()->isConstantSizeType()) - return store::UnknownExtent(); - - ASTContext& C = StMgr.getContext(); - assert (!T->isObjCInterfaceType()); // @interface not a possible VarDecl type. - assert (T != C.VoidTy); // void not a possible VarDecl type. - return store::FixedExtent(StMgr.getBasicVals().getValue(C.getTypeSize(T), - C.VoidPtrTy)); -} - - RVal BasicStoreManager::GetRVal(Store St, LVal LV, QualType T) { if (isa<UnknownVal>(LV)) @@ -125,9 +74,15 @@ RVal BasicStoreManager::GetRVal(Store St, LVal LV, QualType T) { switch (LV.getSubKind()) { - case lval::DeclValKind: { + case lval::MemRegionKind: { + VarRegion* R = + dyn_cast<VarRegion>(cast<lval::MemRegionVal>(LV).getRegion()); + + if (!R) + return UnknownVal(); + VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St)); - VarBindingsTy::data_type* T = B.lookup(cast<lval::DeclVal>(LV).getDecl()); + VarBindingsTy::data_type* T = B.lookup(R->getDecl()); return T ? *T : UnknownVal(); } @@ -161,11 +116,17 @@ RVal BasicStoreManager::GetRVal(Store St, LVal LV, QualType T) { Store BasicStoreManager::SetRVal(Store store, LVal LV, RVal V) { switch (LV.getSubKind()) { - case lval::DeclValKind: { + case lval::MemRegionKind: { + VarRegion* R = + dyn_cast<VarRegion>(cast<lval::MemRegionVal>(LV).getRegion()); + + if (!R) + return store; + VarBindingsTy B = GetVarBindings(store); return V.isUnknown() - ? VBFactory.Remove(B,cast<lval::DeclVal>(LV).getDecl()).getRoot() - : VBFactory.Add(B, cast<lval::DeclVal>(LV).getDecl(), V).getRoot(); + ? VBFactory.Remove(B, R->getDecl()).getRoot() + : VBFactory.Add(B, R->getDecl(), V).getRoot(); } default: assert ("SetRVal for given LVal type not yet implemented."); @@ -175,9 +136,15 @@ Store BasicStoreManager::SetRVal(Store store, LVal LV, RVal V) { Store BasicStoreManager::Remove(Store store, LVal LV) { switch (LV.getSubKind()) { - case lval::DeclValKind: { + case lval::MemRegionKind: { + VarRegion* R = + dyn_cast<VarRegion>(cast<lval::MemRegionVal>(LV).getRegion()); + + if (!R) + return store; + VarBindingsTy B = GetVarBindings(store); - return VBFactory.Remove(B,cast<lval::DeclVal>(LV).getDecl()).getRoot(); + return VBFactory.Remove(B,R->getDecl()).getRoot(); } default: assert ("Remove for given LVal type not yet implemented."); @@ -185,12 +152,11 @@ Store BasicStoreManager::Remove(Store store, LVal LV) { } } -Store BasicStoreManager::RemoveDeadBindings(Store store, - Stmt* Loc, - const LiveVariables& Liveness, - DeclRootsTy& DRoots, - LiveSymbolsTy& LSymbols, - DeadSymbolsTy& DSymbols) { +Store +BasicStoreManager::RemoveDeadBindings(Store store, Stmt* Loc, + const LiveVariables& Liveness, + llvm::SmallVectorImpl<const MemRegion*>& RegionRoots, + LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols) { VarBindingsTy B = GetVarBindings(store); typedef RVal::symbol_iterator symbol_iterator; @@ -198,7 +164,7 @@ Store BasicStoreManager::RemoveDeadBindings(Store store, // Iterate over the variable bindings. for (VarBindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) if (Liveness.isLive(Loc, I.getKey())) { - DRoots.push_back(I.getKey()); + RegionRoots.push_back(StMgr.getRegion(I.getKey())); RVal X = I.getData(); for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI) @@ -206,39 +172,43 @@ Store BasicStoreManager::RemoveDeadBindings(Store store, } // Scan for live variables and live symbols. - llvm::SmallPtrSet<ValueDecl*, 10> Marked; + llvm::SmallPtrSet<const VarRegion*, 10> Marked; - while (!DRoots.empty()) { - ValueDecl* V = DRoots.back(); - DRoots.pop_back(); + while (!RegionRoots.empty()) { + const VarRegion* R = cast<VarRegion>(RegionRoots.back()); + RegionRoots.pop_back(); - if (Marked.count(V)) + if (Marked.count(R)) continue; - Marked.insert(V); - - RVal X = GetRVal(store, lval::DeclVal(cast<VarDecl>(V)), QualType()); + Marked.insert(R); + // FIXME: Do we need the QualType here, since regions are partially + // typed? + RVal X = GetRVal(store, lval::MemRegionVal(R), QualType()); for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI) LSymbols.insert(*SI); - if (!isa<lval::DeclVal>(X)) + if (!isa<lval::MemRegionVal>(X)) continue; - const lval::DeclVal& LVD = cast<lval::DeclVal>(X); - DRoots.push_back(LVD.getDecl()); + const lval::MemRegionVal& LVD = cast<lval::MemRegionVal>(X); + RegionRoots.push_back(cast<VarRegion>(LVD.getRegion())); } // Remove dead variable bindings. - for (VarBindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) - if (!Marked.count(I.getKey())) { - store = Remove(store, lval::DeclVal(I.getKey())); + for (VarBindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) { + const VarRegion* R = cast<VarRegion>(StMgr.getRegion(I.getKey())); + + if (!Marked.count(R)) { + store = Remove(store, lval::MemRegionVal(R)); RVal X = I.getData(); for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI) if (!LSymbols.count(*SI)) DSymbols.insert(*SI); } - + } + return store; } @@ -270,7 +240,7 @@ Store BasicStoreManager::getInitialStore(GRStateManager& StateMgr) { ? RVal::GetSymbolValue(StateMgr.getSymbolManager(), VD) : UndefinedVal(); - St = SetRVal(St, lval::DeclVal(VD), X); + St = SetRVal(St, StMgr.getLVal(VD), X); } } } @@ -310,16 +280,16 @@ Store BasicStoreManager::AddDecl(Store store, GRStateManager& StateMgr, if (!Ex) { QualType T = VD->getType(); if (LVal::IsLValType(T)) - store = SetRVal(store, lval::DeclVal(VD), + store = SetRVal(store, StMgr.getLVal(VD), lval::ConcreteInt(BasicVals.getValue(0, T))); else if (T->isIntegerType()) - store = SetRVal(store, lval::DeclVal(VD), + store = SetRVal(store, StMgr.getLVal(VD), nonlval::ConcreteInt(BasicVals.getValue(0, T))); else { // assert(0 && "ignore other types of variables"); } } else { - store = SetRVal(store, lval::DeclVal(VD), InitVal); + store = SetRVal(store, StMgr.getLVal(VD), InitVal); } } } else { @@ -337,7 +307,7 @@ Store BasicStoreManager::AddDecl(Store store, GRStateManager& StateMgr, : cast<RVal>(nonlval::SymbolVal(Sym)); } - store = SetRVal(store, lval::DeclVal(VD), V); + store = SetRVal(store, StMgr.getLVal(VD), V); } } @@ -366,57 +336,9 @@ void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) { VarBindingsTy B = GetVarBindings(store); for (VarBindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) { - VarBinding binding(&(*I)); - f.HandleBinding(*this, store, binding); - } -} - - -std::string BasicStoreManager::BindingAsString(store::Binding binding) { - return cast<VarBinding>(binding).getName(); -} - -RVal BasicStoreManager::getRVal(Store store, store::Binding binding) { - return cast<VarBinding>(binding).getRVal(); -} - -//==------------------------------------------------------------------------==// -// Generic store operations. -//==------------------------------------------------------------------------==// -namespace { -class VISIBILITY_HIDDEN GetBindingsIterator : public StoreManager::BindingsHandler { - SymbolID Sym; - llvm::SmallVectorImpl<store::Binding>& bindings; -public: - GetBindingsIterator(SymbolID s, llvm::SmallVectorImpl<store::Binding>& b) - : Sym(s), bindings(b) {} - - virtual bool HandleBinding(StoreManager& SMgr, Store store, - store::Binding binding) { - - RVal V = SMgr.getRVal(store, binding); - - if (const lval::SymbolVal* SV=dyn_cast<lval::SymbolVal>(&V)) { - if (SV->getSymbol() == Sym) - bindings.push_back(binding); - } - else if (const nonlval::SymbolVal* SV=dyn_cast<nonlval::SymbolVal>(&V)){ - if (SV->getSymbol() == Sym) - bindings.push_back(binding); - } - - return true; + f.HandleBinding(*this, store, StMgr.getRegion(I.getKey()),I.getData()); } -}; -} // end anonymous namespace - -void StoreManager::getBindings(llvm::SmallVectorImpl<store::Binding>& bindings, - Store store, SymbolID Sym) { - - GetBindingsIterator BI(Sym, bindings); - iterBindings(store, BI); } StoreManager::BindingsHandler::~BindingsHandler() {} - diff --git a/clang/lib/Analysis/BugReporter.cpp b/clang/lib/Analysis/BugReporter.cpp index 6a1478a9cbb..e56da7b872d 100644 --- a/clang/lib/Analysis/BugReporter.cpp +++ b/clang/lib/Analysis/BugReporter.cpp @@ -322,32 +322,27 @@ static VarDecl* GetMostRecentVarDeclBinding(ExplodedNode<GRState>* N, return 0; } +namespace { +class VISIBILITY_HIDDEN NotableSymbolHandler + : public StoreManager::BindingsHandler { + + SymbolID Sym; + const GRState* PrevSt; + Stmt* S; + GRStateManager& VMgr; + ExplodedNode<GRState>* Pred; + PathDiagnostic& PD; + BugReporter& BR; + +public: + + NotableSymbolHandler(SymbolID sym, const GRState* prevst, Stmt* s, + GRStateManager& vmgr, ExplodedNode<GRState>* pred, + PathDiagnostic& pd, BugReporter& br) + : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {} + + bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, RVal V) { -static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S, - SymbolID Sym, BugReporter& BR, - PathDiagnostic& PD) { - - ExplodedNode<GRState>* Pred = N->pred_empty() ? 0 : *N->pred_begin(); - const GRState* PrevSt = Pred ? Pred->getState() : 0; - - if (!PrevSt) - return; - - // Look at the variable bindings of the current state that map to the - // specified symbol. Are any of them not in the previous state. - - const GRState* St = N->getState(); - GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager(); - - // FIXME: Later generalize for a broader memory model. - - // FIXME: This is quadratic, since its nested in another loop. Probably - // doesn't matter, but keep an eye out for performance issues. It's - // also a bunch of copy-paste. Bad. Cleanup later. - - for (GRState::vb_iterator I=St->vb_begin(), E=St->vb_end(); I!=E; ++I){ - - RVal V = I.getData(); SymbolID ScanSym; if (lval::SymbolVal* SV = dyn_cast<lval::SymbolVal>(&V)) @@ -355,18 +350,17 @@ static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S, else if (nonlval::SymbolVal* SV = dyn_cast<nonlval::SymbolVal>(&V)) ScanSym = SV->getSymbol(); else - continue; + return true; if (ScanSym != Sym) - continue; - - // Check if the previous state has this binding. + return true; - RVal X = VMgr.GetRVal(PrevSt, lval::DeclVal(I.getKey())); + // Check if the previous state has this binding. + RVal X = VMgr.GetRVal(PrevSt, lval::MemRegionVal(R)); if (X == V) // Same binding? - continue; - + return true; + // Different binding. Only handle assignments for now. We don't pull // this check out of the loop because we will eventually handle other // cases. @@ -375,41 +369,102 @@ static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S, if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { if (!B->isAssignmentOp()) - continue; + return true; // What variable did we assign to? DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts()); if (!DR) - continue; + return true; VD = dyn_cast<VarDecl>(DR->getDecl()); } else if (DeclStmt* DS = dyn_cast<DeclStmt>(S)) VD = dyn_cast<VarDecl>(DS->getDecl()); - + if (!VD) - continue; - + return true; + // What is the most recently referenced variable with this binding? VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V); - + if (!MostRecent) - continue; - + return true; + // Create the diagnostic. FullSourceLoc L(S->getLocStart(), BR.getSourceManager()); - + if (VD->getType()->isPointerLikeType()) { std::string msg = "'" + std::string(VD->getName()) + - "' now aliases '" + MostRecent->getName() + "'"; + "' now aliases '" + MostRecent->getName() + "'"; PD.push_front(new PathDiagnosticPiece(L, msg)); } - } + + return true; + } +}; } +static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S, + SymbolID Sym, BugReporter& BR, + PathDiagnostic& PD) { + + ExplodedNode<GRState>* Pred = N->pred_empty() ? 0 : *N->pred_begin(); + const GRState* PrevSt = Pred ? Pred->getState() : 0; + + if (!PrevSt) + return; + + // Look at the region bindings of the current state that map to the + // specified symbol. Are any of them not in the previous state? + GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager(); + NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR); + cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H); +} + +namespace { +class VISIBILITY_HIDDEN ScanNotableSymbols + : public StoreManager::BindingsHandler { + + llvm::SmallSet<SymbolID, 10> AlreadyProcessed; + ExplodedNode<GRState>* N; + Stmt* S; + GRBugReporter& BR; + PathDiagnostic& PD; + +public: + ScanNotableSymbols(ExplodedNode<GRState>* n, Stmt* s, GRBugReporter& br, + PathDiagnostic& pd) + : N(n), S(s), BR(br), PD(pd) {} + + bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, RVal V) { + SymbolID ScanSym; + + if (lval::SymbolVal* SV = dyn_cast<lval::SymbolVal>(&V)) + ScanSym = SV->getSymbol(); + else if (nonlval::SymbolVal* SV = dyn_cast<nonlval::SymbolVal>(&V)) + ScanSym = SV->getSymbol(); + else + return true; + + assert (ScanSym.isInitialized()); + + if (!BR.isNotable(ScanSym)) + return true; + + if (AlreadyProcessed.count(ScanSym)) + return true; + + AlreadyProcessed.insert(ScanSym); + + HandleNotableSymbol(N, S, ScanSym, BR, PD); + return true; + } +}; +} // end anonymous namespace + void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, BugReport& R) { @@ -633,42 +688,11 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, if (PathDiagnosticPiece* p = R.VisitNode(N, NextNode, *ReportGraph, *this)) PD.push_front(p); - if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) { - - const GRState* St = N->getState(); - - // Scan the lval bindings, and see if a "notable" symbol has a new + if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) { + // Scan the region bindings, and see if a "notable" symbol has a new // lval binding. - - // FIXME: In the future, when we generalize the memory model, we'll - // need a way to iterate over binded locations. - - llvm::SmallSet<SymbolID, 10> AlreadyProcessed; - - for (GRState::vb_iterator I=St->vb_begin(), E=St->vb_end(); I!=E; ++I){ - - RVal V = I.getData(); - SymbolID ScanSym; - - if (lval::SymbolVal* SV = dyn_cast<lval::SymbolVal>(&V)) - ScanSym = SV->getSymbol(); - else if (nonlval::SymbolVal* SV = dyn_cast<nonlval::SymbolVal>(&V)) - ScanSym = SV->getSymbol(); - else - continue; - - assert (ScanSym.isInitialized()); - - if (!isNotable(ScanSym)) - continue; - - if (AlreadyProcessed.count(ScanSym)) - continue; - - AlreadyProcessed.insert(ScanSym); - - HandleNotableSymbol(N, PS->getStmt(), ScanSym, *this, PD); - } + ScanNotableSymbols SNS(N, PS->getStmt(), *this, PD); + getStateManager().iterBindings(N->getState(), SNS); } } } diff --git a/clang/lib/Analysis/CFRefCount.cpp b/clang/lib/Analysis/CFRefCount.cpp index 733cad18acf..c63529aa055 100644 --- a/clang/lib/Analysis/CFRefCount.cpp +++ b/clang/lib/Analysis/CFRefCount.cpp @@ -1489,7 +1489,7 @@ void CFRefCount::EvalSummary(ExplodedNodeSet<GRState>& Dst, // Nuke all arguments passed by reference. StateMgr.Unbind(StVals, cast<LVal>(V)); #else - if (lval::DeclVal* DV = dyn_cast<lval::DeclVal>(&V)) { + if (lval::MemRegionVal* MR = dyn_cast<lval::MemRegionVal>(&V)) { if (GetArgE(Summ, idx) == DoNothingByRef) continue; @@ -1506,23 +1506,28 @@ void CFRefCount::EvalSummary(ExplodedNodeSet<GRState>& Dst, // disambiguate conjured symbols. // Is the invalidated variable something that we were tracking? - RVal X = state.GetRVal(*DV); + RVal X = state.GetRVal(*MR); if (isa<lval::SymbolVal>(X)) { SymbolID Sym = cast<lval::SymbolVal>(X).getSymbol(); state = state.remove<RefBindings>(Sym); } - - // Set the value of the variable to be a conjured symbol. - unsigned Count = Builder.getCurrentBlockCount(); - SymbolID NewSym = - Eng.getSymbolManager().getConjuredSymbol(*I, DV->getDecl()->getType(), - Count); - - state = state.SetRVal(*DV, - LVal::IsLValType(DV->getDecl()->getType()) - ? cast<RVal>(lval::SymbolVal(NewSym)) - : cast<RVal>(nonlval::SymbolVal(NewSym))); + + TypedRegion* R = dyn_cast<TypedRegion>(MR->getRegion()); + if (R) { + // Set the value of the variable to be a conjured symbol. + unsigned Count = Builder.getCurrentBlockCount(); + QualType T = R->getType(); + SymbolID NewSym = + Eng.getSymbolManager().getConjuredSymbol(*I, T, Count); + + state = state.SetRVal(*MR, + LVal::IsLValType(T) + ? cast<RVal>(lval::SymbolVal(NewSym)) + : cast<RVal>(nonlval::SymbolVal(NewSym))); + } + else + state = state.SetRVal(*MR, UnknownVal()); } else { // Nuke all other arguments passed by reference. @@ -1709,10 +1714,12 @@ void CFRefCount::EvalStore(ExplodedNodeSet<GRState>& Dst, bool escapes = false; - if (!isa<lval::DeclVal>(TargetLV)) + if (!isa<lval::MemRegionVal>(TargetLV)) escapes = true; - else - escapes = cast<lval::DeclVal>(TargetLV).getDecl()->hasGlobalStorage(); + else { + MemRegion* R = cast<lval::MemRegionVal>(TargetLV).getRegion(); + escapes = !Eng.getStateManager().hasStackStorage(R); + } if (!escapes) return; @@ -2307,14 +2314,51 @@ PathDiagnosticPiece* CFRefReport::VisitNode(ExplodedNode<GRState>* N, return P; } -static std::pair<ExplodedNode<GRState>*,store::Binding> +namespace { +class VISIBILITY_HIDDEN FindUniqueBinding : + public StoreManager::BindingsHandler { + SymbolID Sym; + MemRegion* Binding; + bool First; + + public: + FindUniqueBinding(SymbolID sym) : Sym(sym), Binding(0), First(true) {} + + bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, RVal val) { + if (const lval::SymbolVal* SV = dyn_cast<lval::SymbolVal>(&val)) { + if (SV->getSymbol() != Sym) + return true; + } + else if (const nonlval::SymbolVal* SV=dyn_cast<nonlval::SymbolVal>(&val)) { + if (SV->getSymbol() != Sym) + return true; + } + else + return true; + + if (Binding) { + First = false; + return false; + } + else + Binding = R; + + return true; + } + + operator bool() { return First && Binding; } + MemRegion* getRegion() { return Binding; } +}; +} + +static std::pair<ExplodedNode<GRState>*,MemRegion*> GetAllocationSite(GRStateManager* StateMgr, ExplodedNode<GRState>* N, SymbolID Sym) { // Find both first node that referred to the tracked symbol and the // memory location that value was store to. ExplodedNode<GRState>* Last = N; - store::Binding FirstBinding; + MemRegion* FirstBinding = 0; while (N) { const GRState* St = N->getState(); @@ -2324,11 +2368,9 @@ GetAllocationSite(GRStateManager* StateMgr, ExplodedNode<GRState>* N, break; if (StateMgr) { - llvm::SmallVector<store::Binding, 5> Bindings; - StateMgr->getBindings(Bindings, St, Sym); - - if (Bindings.size() == 1) - FirstBinding = Bindings[0]; + FindUniqueBinding FB(Sym); + StateMgr->iterBindings(St, FB); + if (FB) FirstBinding = FB.getRegion(); } Last = N; @@ -2357,7 +2399,7 @@ PathDiagnosticPiece* CFRefReport::getEndPath(BugReporter& br, // symbol appeared, and also get the first VarDecl that tracked object // is stored to. ExplodedNode<GRState>* AllocNode = 0; - store::Binding FirstBinding; + MemRegion* FirstBinding = 0; llvm::tie(AllocNode, FirstBinding) = GetAllocationSite(&BR.getStateManager(), EndN, Sym); @@ -2413,8 +2455,8 @@ PathDiagnosticPiece* CFRefReport::getEndPath(BugReporter& br, os << "Object allocated on line " << AllocLine; if (FirstBinding) - os << " and stored into '" - << BR.getStateManager().BindingAsString(FirstBinding) << '\''; + os << " and stored into '" << FirstBinding->getString() << '\''; + os << " is no longer referenced after this point and has a retain count of +" << RetCount << " (object leaked)."; diff --git a/clang/lib/Analysis/CheckNSError.cpp b/clang/lib/Analysis/CheckNSError.cpp index 5a1e7cb8f14..03c9af3a729 100644 --- a/clang/lib/Analysis/CheckNSError.cpp +++ b/clang/lib/Analysis/CheckNSError.cpp @@ -216,7 +216,7 @@ void NSErrorCheck::CheckParamDeref(VarDecl* Param, GRStateRef rootState, GRExprEngine& Eng, GRBugReporter& BR, bool isNSErrorWarning) { - RVal ParamRVal = rootState.GetRVal(lval::DeclVal(Param)); + RVal ParamRVal = rootState.GetRVal(Eng.getLVal(Param)); // FIXME: For now assume that ParamRVal is symbolic. We need to generalize // this later. diff --git a/clang/lib/Analysis/Environment.cpp b/clang/lib/Analysis/Environment.cpp index 15a1d3659f8..f86c4fea716 100644 --- a/clang/lib/Analysis/Environment.cpp +++ b/clang/lib/Analysis/Environment.cpp @@ -107,11 +107,11 @@ Environment EnvironmentManager::SetRVal(const Environment& Env, Expr* E, RVal V, } Environment -EnvironmentManager::RemoveDeadBindings(Environment Env, - Stmt* Loc, - const LiveVariables& Liveness, - StoreManager::DeclRootsTy& DRoots, - StoreManager::LiveSymbolsTy& LSymbols) { +EnvironmentManager::RemoveDeadBindings(Environment Env, Stmt* Loc, + const LiveVariables& Liveness, + llvm::SmallVectorImpl<const MemRegion*>& DRoots, + StoreManager::LiveSymbolsTy& LSymbols) { + // Drop bindings for subexpressions. Env = RemoveSubExprBindings(Env); @@ -123,12 +123,10 @@ EnvironmentManager::RemoveDeadBindings(Environment Env, if (Liveness.isLive(Loc, BlkExpr)) { RVal X = I.getData(); - // If the block expr's value is the address of some Decl, then mark that - // Decl. - if (isa<lval::DeclVal>(X)) { - lval::DeclVal LV = cast<lval::DeclVal>(X); - DRoots.push_back(LV.getDecl()); - } + // If the block expr's value is a memory region, then mark that region. + if (isa<lval::MemRegionVal>(X)) + DRoots.push_back(cast<lval::MemRegionVal>(X).getRegion()); + // Mark all symbols in the block expr's value. for (RVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end(); diff --git a/clang/lib/Analysis/GRExprEngine.cpp b/clang/lib/Analysis/GRExprEngine.cpp index 41bf98933ef..115d265dde4 100644 --- a/clang/lib/Analysis/GRExprEngine.cpp +++ b/clang/lib/Analysis/GRExprEngine.cpp @@ -792,12 +792,12 @@ void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst, bool asLVal) { const GRState* St = GetState(Pred); - RVal X = RVal::MakeVal(getBasicVals(), D); + RVal X = RVal::MakeVal(getStateManager(), D); if (asLVal) MakeNode(Dst, D, Pred, SetRVal(St, D, cast<LVal>(X))); else { - RVal V = isa<lval::DeclVal>(X) ? GetRVal(St, cast<LVal>(X)) : X; + RVal V = isa<lval::MemRegionVal>(X) ? GetRVal(St, cast<LVal>(X)) : X; MakeNode(Dst, D, Pred, SetRVal(St, D, V)); } } @@ -1900,9 +1900,12 @@ void GRExprEngine::VisitReturnStmt(ReturnStmt* S, NodeTy* Pred, NodeSet& Dst) { for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { RVal X = GetRVal((*I)->getState(), R); - if (isa<lval::DeclVal>(X)) { + if (isa<lval::MemRegionVal>(X)) { - if (cast<lval::DeclVal>(X).getDecl()->hasLocalStorage()) { + // Determine if the value is on the stack. + const MemRegion* R = cast<lval::MemRegionVal>(&X)->getRegion(); + + if (R && getStateManager().hasStackStorage(R)) { // Create a special node representing the v diff --git a/clang/lib/Analysis/GRExprEngineInternalChecks.cpp b/clang/lib/Analysis/GRExprEngineInternalChecks.cpp index e7e5f45d8a6..d61998c5a41 100644 --- a/clang/lib/Analysis/GRExprEngineInternalChecks.cpp +++ b/clang/lib/Analysis/GRExprEngineInternalChecks.cpp @@ -194,13 +194,14 @@ public: assert (E && "Return expression cannot be NULL"); // Get the value associated with E. - lval::DeclVal V = - cast<lval::DeclVal>(Eng.getStateManager().GetRVal(N->getState(), E)); + lval::MemRegionVal V = + cast<lval::MemRegionVal>(Eng.getStateManager().GetRVal(N->getState(), + E)); // Generate a report for this bug. std::ostringstream os; os << "Address of stack memory associated with local variable '" - << V.getDecl()->getName() << "' returned."; + << V.getRegion()->getString() << "' returned."; std::string s = os.str(); diff --git a/clang/lib/Analysis/GRSimpleVals.cpp b/clang/lib/Analysis/GRSimpleVals.cpp index b33d5122b19..44703163e06 100644 --- a/clang/lib/Analysis/GRSimpleVals.cpp +++ b/clang/lib/Analysis/GRSimpleVals.cpp @@ -287,7 +287,7 @@ RVal GRSimpleVals::EvalEQ(GRExprEngine& Eng, LVal L, LVal R) { case lval::FieldOffsetKind: // Fall-through. - case lval::DeclValKind: + case lval::MemRegionKind: case lval::FuncValKind: case lval::GotoLabelKind: case lval::StringLiteralValKind: @@ -351,7 +351,7 @@ RVal GRSimpleVals::EvalNE(GRExprEngine& Eng, LVal L, LVal R) { case lval::FieldOffsetKind: // Fall-through. - case lval::DeclValKind: + case lval::MemRegionKind: case lval::FuncValKind: case lval::GotoLabelKind: case lval::StringLiteralValKind: diff --git a/clang/lib/Analysis/GRState.cpp b/clang/lib/Analysis/GRState.cpp index 67bff39fc8c..2f829e65da8 100644 --- a/clang/lib/Analysis/GRState.cpp +++ b/clang/lib/Analysis/GRState.cpp @@ -42,19 +42,18 @@ GRStateManager::RemoveDeadBindings(const GRState* St, Stmt* Loc, // tells us are live. We then see what Decls they may reference, and keep // those around. This code more than likely can be made faster, and the // frequency of which this method is called should be experimented with - // for optimum performance. - DRoots.clear(); + // for optimum performance. + llvm::SmallVector<const MemRegion*, 10> RegionRoots; StoreManager::LiveSymbolsTy LSymbols; - GRState NewSt = *St; - NewSt.Env = EnvMgr.RemoveDeadBindings(NewSt.Env, Loc, Liveness, - DRoots, LSymbols); + NewSt.Env = + EnvMgr.RemoveDeadBindings(NewSt.Env, Loc, Liveness, RegionRoots, LSymbols); // Clean up the store. DSymbols.clear(); - NewSt.St = StMgr->RemoveDeadBindings(St->getStore(), Loc, Liveness, DRoots, - LSymbols, DSymbols); + NewSt.St = StMgr->RemoveDeadBindings(St->getStore(), Loc, Liveness, + RegionRoots, LSymbols, DSymbols); return ConstraintMgr->RemoveDeadBindings(getPersistentState(NewSt), LSymbols, DSymbols); diff --git a/clang/lib/Analysis/MemRegion.cpp b/clang/lib/Analysis/MemRegion.cpp new file mode 100644 index 00000000000..7c2af428d36 --- /dev/null +++ b/clang/lib/Analysis/MemRegion.cpp @@ -0,0 +1,158 @@ +//== MemRegion.cpp - Abstract memory regions for static analysis --*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines MemRegion and its subclasses. MemRegion defines a +// partially-typed abstraction of memory useful for path-sensitive dataflow +// analyses. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Support/raw_ostream.h" +#include "clang/Analysis/PathSensitive/MemRegion.h" + +using namespace clang; + + +MemRegion::~MemRegion() {} + +void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const { + ID.AddInteger((unsigned)getKind()); +} + +void AnonTypedRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, QualType T, + const MemRegion* superRegion) { + ID.AddInteger((unsigned) AnonTypedRegionKind); + ID.Add(T); + ID.AddPointer(superRegion); +} + +void AnonTypedRegion::Profile(llvm::FoldingSetNodeID& ID) const { + AnonTypedRegion::ProfileRegion(ID, T, superRegion); +} + +void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D, + const MemRegion* superRegion, Kind k) { + ID.AddInteger((unsigned) k); + ID.AddPointer(D); + ID.AddPointer(superRegion); +} + +void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const { + DeclRegion::ProfileRegion(ID, D, superRegion, getKind()); +} + +//===----------------------------------------------------------------------===// +// Region pretty-printing. +//===----------------------------------------------------------------------===// + +std::string MemRegion::getString() const { + std::string s; + llvm::raw_string_ostream os(s); + print(os); + return os.str(); +} + +void MemRegion::print(llvm::raw_ostream& os) const { + os << "<Unknown Region>"; +} + +void VarRegion::print(llvm::raw_ostream& os) const { + os << cast<VarDecl>(D)->getName(); +} + +//===----------------------------------------------------------------------===// +// MemRegionManager methods. +//===----------------------------------------------------------------------===// + +MemSpaceRegion* MemRegionManager::LazyAllocate(MemSpaceRegion*& region) { + + if (!region) { + region = (MemSpaceRegion*) A.Allocate<MemSpaceRegion>(); + new (region) MemSpaceRegion(); + } + + return region; +} + +MemSpaceRegion* MemRegionManager::getStackRegion() { + return LazyAllocate(stack); +} + +MemSpaceRegion* MemRegionManager::getGlobalsRegion() { + return LazyAllocate(globals); +} + +MemSpaceRegion* MemRegionManager::getHeapRegion() { + return LazyAllocate(heap); +} + +VarRegion* MemRegionManager::getVarRegion(const VarDecl* d, + MemRegion* superRegion) { + llvm::FoldingSetNodeID ID; + DeclRegion::ProfileRegion(ID, d, superRegion, MemRegion::VarRegionKind); + + void* InsertPos; + MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); + VarRegion* R = cast_or_null<VarRegion>(data); + + if (!R) { + R = (VarRegion*) A.Allocate<VarRegion>(); + new (R) VarRegion(d, superRegion); + Regions.InsertNode(R, InsertPos); + } + + return R; +} + +FieldRegion* MemRegionManager::getFieldRegion(const FieldDecl* d, + MemRegion* superRegion) { + llvm::FoldingSetNodeID ID; + DeclRegion::ProfileRegion(ID, d, superRegion, MemRegion::FieldRegionKind); + + void* InsertPos; + MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); + FieldRegion* R = cast_or_null<FieldRegion>(data); + + if (!R) { + R = (FieldRegion*) A.Allocate<FieldRegion>(); + new (R) FieldRegion(d, superRegion); + Regions.InsertNode(R, InsertPos); + } + + return R; +} + +ObjCIvarRegion* MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl* d, + MemRegion* superRegion) { + llvm::FoldingSetNodeID ID; + DeclRegion::ProfileRegion(ID, d, superRegion, MemRegion::ObjCIvarRegionKind); + + void* InsertPos; + MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); + ObjCIvarRegion* R = cast_or_null<ObjCIvarRegion>(data); + + if (!R) { + R = (ObjCIvarRegion*) A.Allocate<FieldRegion>(); + new (R) FieldRegion(d, superRegion); + Regions.InsertNode(R, InsertPos); + } + + return R; +} + +bool MemRegionManager::hasStackStorage(const MemRegion* R) { + MemSpaceRegion* S = getStackRegion(); + + while (R) { + if (R == S) return true; + R = R->getSuperRegion(); + } + + return false; +} diff --git a/clang/lib/Analysis/RValues.cpp b/clang/lib/Analysis/RValues.cpp index 5dc9cd5fbe0..337d4792555 100644 --- a/clang/lib/Analysis/RValues.cpp +++ b/clang/lib/Analysis/RValues.cpp @@ -12,7 +12,7 @@ // //===----------------------------------------------------------------------===// -#include "clang/Analysis/PathSensitive/RValues.h" +#include "clang/Analysis/PathSensitive/GRState.h" #include "clang/Basic/IdentifierTable.h" #include "llvm/Support/Streams.h" @@ -163,9 +163,9 @@ NonLVal LVal::EQ(BasicValueFactory& BasicVals, const LVal& R) const { break; } - case lval::DeclValKind: - if (isa<lval::DeclVal>(R)) { - bool b = cast<lval::DeclVal>(*this) == cast<lval::DeclVal>(R); + case lval::MemRegionKind: + if (isa<lval::MemRegionVal>(R)) { + bool b = cast<lval::MemRegionVal>(*this) == cast<lval::MemRegionVal>(R); return NonLVal::MakeIntTruthVal(BasicVals, b); } @@ -216,9 +216,9 @@ NonLVal LVal::NE(BasicValueFactory& BasicVals, const LVal& R) const { break; } - case lval::DeclValKind: - if (isa<lval::DeclVal>(R)) { - bool b = cast<lval::DeclVal>(*this) == cast<lval::DeclVal>(R); + case lval::MemRegionKind: + if (isa<lval::MemRegionVal>(R)) { + bool b = cast<lval::MemRegionVal>(*this)==cast<lval::MemRegionVal>(R); return NonLVal::MakeIntTruthVal(BasicVals, b); } @@ -270,12 +270,12 @@ LVal LVal::MakeVal(StringLiteral* S) { // Utility methods for constructing RVals (both NonLVals and LVals). //===----------------------------------------------------------------------===// -RVal RVal::MakeVal(BasicValueFactory& BasicVals, DeclRefExpr* E) { +RVal RVal::MakeVal(GRStateManager& SMgr, DeclRefExpr* E) { ValueDecl* D = cast<DeclRefExpr>(E)->getDecl(); if (VarDecl* VD = dyn_cast<VarDecl>(D)) { - return lval::DeclVal(VD); + return SMgr.getLVal(VD); } else if (EnumConstantDecl* ED = dyn_cast<EnumConstantDecl>(D)) { @@ -283,7 +283,7 @@ RVal RVal::MakeVal(BasicValueFactory& BasicVals, DeclRefExpr* E) { // already has persistent storage? We do this because we // are comparing states using pointer equality. Perhaps there is // a better way, since APInts are fairly lightweight. - + BasicValueFactory& BasicVals = SMgr.getBasicVals(); return nonlval::ConcreteInt(BasicVals.getValue(ED->getInitVal())); } else if (FunctionDecl* FD = dyn_cast<FunctionDecl>(D)) { @@ -408,9 +408,8 @@ void LVal::print(std::ostream& Out) const { << cast<lval::GotoLabel>(this)->getLabel()->getID()->getName(); break; - case lval::DeclValKind: - Out << '&' - << cast<lval::DeclVal>(this)->getDecl()->getIdentifier()->getName(); + case lval::MemRegionKind: + Out << '&' << cast<lval::MemRegionVal>(this)->getRegion()->getString(); break; case lval::FuncValKind: |
