From 9ab6b9cfb76ee56a61829e2bdb08e5cdc288726e Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 22 Jan 2009 18:23:34 +0000 Subject: [PATCH] Static analyzer: Remove a bunch of outdated SymbolData objects and their associated APIs. We no longer need separate SymbolData objects for fields, variables, etc. Instead, we now associated symbols with the "rvalue" of a MemRegion (i.e., the value stored at that region). Now we only have two kinds of SymbolData objects: SymbolRegionRValue and SymbolConjured. This cleanup also makes the distinction between a SymbolicRegion and a symbolic value that is a location much clearer. A SymbolicRegion represents a chunk of symbolic memory, while a symbolic location is just a "pointer" with different possible values. Without any specific knowledge, a symbolic location resolves (i.e., via a dereference) to a SymbolicRegion. In the future, when we do better alias reasoning, a symbolic location can become an alias for another location, thus merging the constraints on the referred SymbolicRegion with the other region. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@62769 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../clang/Analysis/PathSensitive/GRState.h | 2 +- include/clang/Analysis/PathSensitive/SVals.h | 14 +-- .../Analysis/PathSensitive/SymbolManager.h | 117 ++++-------------- lib/Analysis/BasicConstraintManager.cpp | 9 +- lib/Analysis/BasicStore.cpp | 7 +- lib/Analysis/RegionStore.cpp | 9 +- lib/Analysis/SVals.cpp | 38 ++---- lib/Analysis/SymbolManager.cpp | 117 +++--------------- 8 files changed, 64 insertions(+), 249 deletions(-) diff --git a/include/clang/Analysis/PathSensitive/GRState.h b/include/clang/Analysis/PathSensitive/GRState.h index 7cf3a43bfa..74cd01f515 100644 --- a/include/clang/Analysis/PathSensitive/GRState.h +++ b/include/clang/Analysis/PathSensitive/GRState.h @@ -310,7 +310,7 @@ public: ISetFactory(alloc), GDMFactory(alloc), BasicVals(Ctx, alloc), - SymMgr(alloc), + SymMgr(Ctx, alloc), Alloc(alloc), cfg(c), codedecl(cd), diff --git a/include/clang/Analysis/PathSensitive/SVals.h b/include/clang/Analysis/PathSensitive/SVals.h index ca36187530..dbeba45c83 100644 --- a/include/clang/Analysis/PathSensitive/SVals.h +++ b/include/clang/Analysis/PathSensitive/SVals.h @@ -72,17 +72,9 @@ public: return !(*this == R); } - /// MakeSymbolValue - make a unique symbol value for the region R according to - /// its kind. R should be a scalar region. The symbol value T has the same - /// type as R's rvalue type. - static SVal MakeSymbolValue(SymbolManager& SymMgr, const MemRegion* R, - QualType T); - - static SVal GetSymbolValue(SymbolManager& SymMgr, VarDecl *D); - static SVal getSymbolValue(SymbolManager& SymMgr, const MemRegion* R, - const llvm::APSInt* Idx, QualType T); - static SVal getSymbolValue(SymbolManager& SymMgr, const MemRegion* R, - const FieldDecl* FD, QualType T); + /// GetRValueSymbolVal - make a unique symbol for value of R. + static SVal GetRValueSymbolVal(SymbolManager& SymMgr, const MemRegion* R); + inline bool isUnknown() const { return getRawKind() == UnknownKind; diff --git a/include/clang/Analysis/PathSensitive/SymbolManager.h b/include/clang/Analysis/PathSensitive/SymbolManager.h index e326166dfc..6b777be0c5 100644 --- a/include/clang/Analysis/PathSensitive/SymbolManager.h +++ b/include/clang/Analysis/PathSensitive/SymbolManager.h @@ -32,6 +32,7 @@ namespace clang { class MemRegion; class SymbolManager; +class ASTContext; class SymbolRef { unsigned Data; @@ -80,8 +81,7 @@ namespace clang { class SymbolData : public llvm::FoldingSetNode { public: - enum Kind { UndefKind, ParmKind, GlobalKind, ElementKind, FieldKind, - ConjuredKind }; + enum Kind { RegionRValue, ConjuredKind }; private: Kind K; @@ -97,105 +97,36 @@ public: SymbolRef getSymbol() const { return Sym; } - QualType getType(const SymbolManager& SymMgr) const; + virtual QualType getType(ASTContext&) const = 0; virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; // Implement isa support. static inline bool classof(const SymbolData*) { return true; } }; - -class SymbolDataParmVar : public SymbolData { - const ParmVarDecl *VD; - -public: - SymbolDataParmVar(SymbolRef MySym, const ParmVarDecl* vd) - : SymbolData(ParmKind, MySym), VD(vd) {} - - const ParmVarDecl* getDecl() const { return VD; } - - static void Profile(llvm::FoldingSetNodeID& profile, const ParmVarDecl* VD) { - profile.AddInteger((unsigned) ParmKind); - profile.AddPointer(VD); - } - virtual void Profile(llvm::FoldingSetNodeID& profile) { - Profile(profile, VD); - } - - // Implement isa support. - static inline bool classof(const SymbolData* D) { - return D->getKind() == ParmKind; - } -}; - -class SymbolDataGlobalVar : public SymbolData { - const VarDecl *VD; - +class SymbolRegionRValue : public SymbolData { + const MemRegion *R; public: - SymbolDataGlobalVar(SymbolRef MySym, const VarDecl* vd) : - SymbolData(GlobalKind, MySym), VD(vd) {} - - const VarDecl* getDecl() const { return VD; } + SymbolRegionRValue(SymbolRef MySym, const MemRegion *r) + : SymbolData(RegionRValue, MySym), R(r) {} - static void Profile(llvm::FoldingSetNodeID& profile, const VarDecl* VD) { - profile.AddInteger((unsigned) GlobalKind); - profile.AddPointer(VD); + const MemRegion* getRegion() const { return R; } + + static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion* R) { + profile.AddInteger((unsigned) RegionRValue); + profile.AddPointer(R); } virtual void Profile(llvm::FoldingSetNodeID& profile) { - Profile(profile, VD); + Profile(profile, R); } + QualType getType(ASTContext&) const; + // Implement isa support. static inline bool classof(const SymbolData* D) { - return D->getKind() == GlobalKind; - } -}; - -class SymbolDataElement : public SymbolData { - const MemRegion* R; - const llvm::APSInt* Idx; - -public: - SymbolDataElement(SymbolRef MySym, const MemRegion* r, const llvm::APSInt* idx) - : SymbolData(ElementKind, MySym), R(r), Idx(idx) {} - - static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion* R, - const llvm::APSInt* Idx) { - profile.AddPointer(R); - profile.AddPointer(Idx); - } - - void Profile(llvm::FoldingSetNodeID& profile) { - Profile(profile, R, Idx); - } - - static bool classof(const SymbolData* D) { - return D->getKind() == ElementKind; - } -}; - -class SymbolDataField : public SymbolData { - const MemRegion* R; - const FieldDecl* D; - -public: - SymbolDataField(SymbolRef MySym, const MemRegion* r, const FieldDecl* d) - : SymbolData(FieldKind, MySym), R(r), D(d) {} - - static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion* R, - const FieldDecl* D) { - profile.AddPointer(R); - profile.AddPointer(D); - } - - void Profile(llvm::FoldingSetNodeID& profile) { - Profile(profile, R, D); - } - - static bool classof(const SymbolData* D) { - return D->getKind() == FieldKind; + return D->getKind() == RegionRValue; } }; @@ -210,7 +141,7 @@ public: Stmt* getStmt() const { return S; } unsigned getCount() const { return Count; } - QualType getType() const { return T; } + QualType getType(ASTContext&) const; static void Profile(llvm::FoldingSetNodeID& profile, Stmt* S, QualType T, unsigned Count) { @@ -271,18 +202,16 @@ class SymbolManager { unsigned SymbolCounter; llvm::BumpPtrAllocator& BPAlloc; + ASTContext& Ctx; public: - SymbolManager(llvm::BumpPtrAllocator& bpalloc) - : SymbolCounter(0), BPAlloc(bpalloc) {} + SymbolManager(ASTContext& ctx, llvm::BumpPtrAllocator& bpalloc) + : SymbolCounter(0), BPAlloc(bpalloc), Ctx(ctx) {} ~SymbolManager(); /// Make a unique symbol for MemRegion R according to its kind. - SymbolRef getSymbol(const MemRegion* R); - SymbolRef getSymbol(const VarDecl* D); - SymbolRef getElementSymbol(const MemRegion* R, const llvm::APSInt* Idx); - SymbolRef getFieldSymbol(const MemRegion* R, const FieldDecl* D); + SymbolRef getRegionRValueSymbol(const MemRegion* R); SymbolRef getConjuredSymbol(Stmt* E, QualType T, unsigned VisitCount); SymbolRef getConjuredSymbol(Expr* E, unsigned VisitCount) { return getConjuredSymbol(E, E->getType(), VisitCount); @@ -291,8 +220,10 @@ public: const SymbolData& getSymbolData(SymbolRef ID) const; QualType getType(SymbolRef ID) const { - return getSymbolData(ID).getType(*this); + return getSymbolData(ID).getType(Ctx); } + + ASTContext& getContext() { return Ctx; } }; class SymbolReaper { diff --git a/lib/Analysis/BasicConstraintManager.cpp b/lib/Analysis/BasicConstraintManager.cpp index 450c38f20b..c875691167 100644 --- a/lib/Analysis/BasicConstraintManager.cpp +++ b/lib/Analysis/BasicConstraintManager.cpp @@ -204,13 +204,12 @@ BasicConstraintManager::AssumeAux(const GRState* St,NonLoc Cond, case nonloc::SymbolValKind: { nonloc::SymbolVal& SV = cast(Cond); SymbolRef sym = SV.getSymbol(); - + QualType T = SymMgr.getType(sym); + if (Assumption) - return AssumeSymNE(St, sym, BasicVals.getValue(0, SymMgr.getType(sym)), - isFeasible); + return AssumeSymNE(St, sym, BasicVals.getValue(0, T), isFeasible); else - return AssumeSymEQ(St, sym, BasicVals.getValue(0, SymMgr.getType(sym)), - isFeasible); + return AssumeSymEQ(St, sym, BasicVals.getValue(0, T), isFeasible); } case nonloc::SymIntConstraintValKind: diff --git a/lib/Analysis/BasicStore.cpp b/lib/Analysis/BasicStore.cpp index 7315ec71ac..a36a239e0d 100644 --- a/lib/Analysis/BasicStore.cpp +++ b/lib/Analysis/BasicStore.cpp @@ -454,12 +454,13 @@ Store BasicStoreManager::getInitialStore() { if (Loc::IsLocType(T) || T->isIntegerType()) { // Initialize globals and parameters to symbolic values. // Initialize local variables to undefined. + const MemRegion *R = StateMgr.getRegion(VD); SVal X = (VD->hasGlobalStorage() || isa(VD) || isa(VD)) - ? SVal::GetSymbolValue(StateMgr.getSymbolManager(), VD) - : UndefinedVal(); + ? SVal::GetRValueSymbolVal(StateMgr.getSymbolManager(), R) + : UndefinedVal(); - St = BindInternal(St, Loc::MakeVal(MRMgr.getVarRegion(VD)), X); + St = BindInternal(St, Loc::MakeVal(R), X); } } } diff --git a/lib/Analysis/RegionStore.cpp b/lib/Analysis/RegionStore.cpp index 3faae70885..5a13a1dbc2 100644 --- a/lib/Analysis/RegionStore.cpp +++ b/lib/Analysis/RegionStore.cpp @@ -552,8 +552,7 @@ SVal RegionStoreManager::Retrieve(const GRState* St, Loc L, QualType T) { // We treat function parameters as symbolic values. if (const VarRegion* VR = dyn_cast(R)) if (isa(VR->getDecl())) - return SVal::MakeSymbolValue(getSymbolManager(), VR, - VR->getRValueType(getContext())); + return SVal::GetRValueSymbolVal(getSymbolManager(), VR); if (MRMgr.onStack(R) || MRMgr.onHeap(R)) { // All stack variables are considered to have undefined values @@ -564,8 +563,7 @@ SVal RegionStoreManager::Retrieve(const GRState* St, Loc L, QualType T) { } // All other values are symbolic. - return SVal::MakeSymbolValue(getSymbolManager(), R, - cast(R)->getRValueType(getContext())); + return SVal::GetRValueSymbolVal(getSymbolManager(), R); // FIXME: consider default values for elements and fields. } @@ -603,8 +601,7 @@ SVal RegionStoreManager::RetrieveStruct(const GRState* St,const TypedRegion* R){ if (MRMgr.onStack(FR) || MRMgr.onHeap(FR)) FieldValue = UndefinedVal(); else - FieldValue = SVal::MakeSymbolValue(getSymbolManager(), FR, - FR->getRValueType(getContext())); + FieldValue = SVal::GetRValueSymbolVal(getSymbolManager(), FR); } StructVal = getBasicVals().consVals(FieldValue, StructVal); diff --git a/lib/Analysis/SVals.cpp b/lib/Analysis/SVals.cpp index 6cc5e914f4..6847764871 100644 --- a/lib/Analysis/SVals.cpp +++ b/lib/Analysis/SVals.cpp @@ -286,38 +286,14 @@ NonLoc NonLoc::MakeCompoundVal(QualType T, llvm::ImmutableList Vals, return nonloc::CompoundVal(BasicVals.getCompoundValData(T, Vals)); } -SVal SVal::MakeSymbolValue(SymbolManager& SymMgr, const MemRegion* R, - QualType T) { - if (Loc::IsLocType(T)) - return Loc::MakeVal(SymMgr.getSymbol(R)); - else - return NonLoc::MakeVal(SymMgr.getSymbol(R)); -} - -SVal SVal::GetSymbolValue(SymbolManager& SymMgr, VarDecl* D) { - - QualType T = D->getType(); - - if (Loc::IsLocType(T)) - return loc::SymbolVal(SymMgr.getSymbol(D)); +SVal SVal::GetRValueSymbolVal(SymbolManager& SymMgr, const MemRegion* R) { + SymbolRef sym = SymMgr.getRegionRValueSymbol(R); + + if (const TypedRegion* TR = cast(R)) + if (Loc::IsLocType(TR->getRValueType(SymMgr.getContext()))) + return Loc::MakeVal(sym); - return nonloc::SymbolVal(SymMgr.getSymbol(D)); -} - -SVal SVal::getSymbolValue(SymbolManager& SymMgr, const MemRegion* R, - const llvm::APSInt* Idx, QualType T) { - if (Loc::IsLocType(T)) - return loc::SymbolVal(SymMgr.getElementSymbol(R, Idx)); - else - return nonloc::SymbolVal(SymMgr.getElementSymbol(R, Idx)); -} - -SVal SVal::getSymbolValue(SymbolManager& SymMgr, const MemRegion* R, - const FieldDecl* FD, QualType T) { - if (Loc::IsLocType(T)) - return loc::SymbolVal(SymMgr.getFieldSymbol(R, FD)); - else - return nonloc::SymbolVal(SymMgr.getFieldSymbol(R, FD)); + return NonLoc::MakeVal(sym); } nonloc::LocAsInteger nonloc::LocAsInteger::Make(BasicValueFactory& Vals, Loc V, diff --git a/lib/Analysis/SymbolManager.cpp b/lib/Analysis/SymbolManager.cpp index d0099e15fa..54ba7b1d93 100644 --- a/lib/Analysis/SymbolManager.cpp +++ b/lib/Analysis/SymbolManager.cpp @@ -22,99 +22,23 @@ void SymbolRef::print(llvm::raw_ostream& os) const { os << getNumber(); } -SymbolRef SymbolManager::getSymbol(const MemRegion* R) { - switch (R->getKind()) { - default: - assert(0 && "unprocessed region"); - case MemRegion::VarRegionKind: - return getSymbol(cast(R)->getDecl()); - - case MemRegion::ElementRegionKind: { - const ElementRegion* ER = cast(R); - const llvm::APSInt& Idx = - cast(ER->getIndex()).getValue(); - return getElementSymbol(ER->getSuperRegion(), &Idx); - } - - case MemRegion::FieldRegionKind: { - const FieldRegion* FR = cast(R); - return getFieldSymbol(FR->getSuperRegion(), FR->getDecl()); - } - } -} - -SymbolRef SymbolManager::getSymbol(const VarDecl* D) { - - assert (isa(D) || isa(D) || - D->hasGlobalStorage()); - +SymbolRef SymbolManager::getRegionRValueSymbol(const MemRegion* R) { llvm::FoldingSetNodeID profile; - - const ParmVarDecl* PD = dyn_cast(D); - - if (PD) - SymbolDataParmVar::Profile(profile, PD); - else - SymbolDataGlobalVar::Profile(profile, D); - - void* InsertPos; - - SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); - if (SD) - return SD->getSymbol(); - - if (PD) { - SD = (SymbolData*) BPAlloc.Allocate(); - new (SD) SymbolDataParmVar(SymbolCounter, PD); - } - else { - SD = (SymbolData*) BPAlloc.Allocate(); - new (SD) SymbolDataGlobalVar(SymbolCounter, D); - } + SymbolRegionRValue::Profile(profile, R); + void* InsertPos; + SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); + if (SD) return SD->getSymbol(); + SD = (SymbolData*) BPAlloc.Allocate(); + new (SD) SymbolRegionRValue(SymbolCounter, R); DataSet.InsertNode(SD, InsertPos); - - DataMap[SymbolCounter] = SD; - return SymbolCounter++; -} - -SymbolRef SymbolManager::getElementSymbol(const MemRegion* R, - const llvm::APSInt* Idx){ - llvm::FoldingSetNodeID ID; - SymbolDataElement::Profile(ID, R, Idx); - void* InsertPos; - SymbolData* SD = DataSet.FindNodeOrInsertPos(ID, InsertPos); - - if (SD) - return SD->getSymbol(); - - SD = (SymbolData*) BPAlloc.Allocate(); - new (SD) SymbolDataElement(SymbolCounter, R, Idx); - - DataSet.InsertNode(SD, InsertPos); - DataMap[SymbolCounter] = SD; + DataMap[SymbolCounter] = SD; return SymbolCounter++; -} - -SymbolRef SymbolManager::getFieldSymbol(const MemRegion* R, const FieldDecl* D) { - llvm::FoldingSetNodeID ID; - SymbolDataField::Profile(ID, R, D); - void* InsertPos; - SymbolData* SD = DataSet.FindNodeOrInsertPos(ID, InsertPos); - if (SD) - return SD->getSymbol(); - - SD = (SymbolData*) BPAlloc.Allocate(); - new (SD) SymbolDataField(SymbolCounter, R, D); - - DataSet.InsertNode(SD, InsertPos); - DataMap[SymbolCounter] = SD; - return SymbolCounter++; } -SymbolRef SymbolManager::getConjuredSymbol(Stmt* E, QualType T, unsigned Count) { +SymbolRef SymbolManager::getConjuredSymbol(Stmt* E, QualType T, unsigned Count){ llvm::FoldingSetNodeID profile; SymbolConjured::Profile(profile, E, T, Count); @@ -141,20 +65,15 @@ const SymbolData& SymbolManager::getSymbolData(SymbolRef Sym) const { } -QualType SymbolData::getType(const SymbolManager& SymMgr) const { - switch (getKind()) { - default: - assert (false && "getType() not implemented for this symbol."); - - case ParmKind: - return cast(this)->getDecl()->getType(); - - case GlobalKind: - return cast(this)->getDecl()->getType(); +QualType SymbolConjured::getType(ASTContext&) const { + return T; +} - case ConjuredKind: - return cast(this)->getType(); - } +QualType SymbolRegionRValue::getType(ASTContext& C) const { + if (const TypedRegion* TR = dyn_cast(R)) + return TR->getRValueType(C); + + return QualType(); } SymbolManager::~SymbolManager() {} @@ -172,7 +91,7 @@ bool SymbolReaper::maybeDead(SymbolRef sym) { return true; } -bool SymbolReaper::isLive(SymbolRef sym) { +bool SymbolReaper::isLive(SymbolRef sym) { return TheLiving.contains(sym); } -- 2.40.0