This is a big patch, but the functionality change is small and the rest of the patch consists of deltas due to API changes.
This patch overhauls the "memory region" abstraction that was prototyped (but never really used) as part of the Store.h. This patch adds MemRegion.h and MemRegion.cpp, which defines the class MemRegion and its subclasses. This classes serve to define an abstract representation of memory, with regions being layered on other regions to to capture the relationships between fields and variables, variables and the address space they are allocated in, and so on.
The main motivation of this patch is that key parts of the analyzer assumed that all value bindings were to VarDecls. In the future this won't be the case, and this patch removes lval::DeclVal and replaces it with lval::MemRegionVal. Now all pieces of the analyzer must reason about abstract memory blocks instead of just variables.
There should be no functionality change from this patch, but it opens the door for significant improvements to the analyzer such as field-sensitivity and object-sensitivity, both which were on hold until the memory abstraction got generalized.
The memory region abstraction also allows type-information to literally be affixed to a memory region. This will allow the some now redundant logic to be removed from the retain/release checker.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@57042 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/BasicConstraintManager.cpp b/lib/Analysis/BasicConstraintManager.cpp
index 0576eaf..66bf082 100644
--- a/lib/Analysis/BasicConstraintManager.cpp
+++ b/lib/Analysis/BasicConstraintManager.cpp
@@ -129,7 +129,7 @@
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/lib/Analysis/BasicObjCFoundationChecks.cpp b/lib/Analysis/BasicObjCFoundationChecks.cpp
index 521f317..b3f534d 100644
--- a/lib/Analysis/BasicObjCFoundationChecks.cpp
+++ b/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 @@
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 @@
// 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 @@
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/lib/Analysis/BasicStore.cpp b/lib/Analysis/BasicStore.cpp
index 9756679..4616143 100644
--- a/lib/Analysis/BasicStore.cpp
+++ b/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 @@
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 @@
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 @@
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 @@
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 @@
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::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::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 @@
// 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 @@
}
// 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 @@
? RVal::GetSymbolValue(StateMgr.getSymbolManager(), VD)
: UndefinedVal();
- St = SetRVal(St, lval::DeclVal(VD), X);
+ St = SetRVal(St, StMgr.getLVal(VD), X);
}
}
}
@@ -310,16 +280,16 @@
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 @@
: cast<RVal>(nonlval::SymbolVal(Sym));
}
- store = SetRVal(store, lval::DeclVal(VD), V);
+ store = SetRVal(store, StMgr.getLVal(VD), V);
}
}
@@ -366,57 +336,9 @@
VarBindingsTy B = GetVarBindings(store);
for (VarBindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
- VarBinding binding(&(*I));
- f.HandleBinding(*this, store, binding);
+
+ f.HandleBinding(*this, store, StMgr.getRegion(I.getKey()),I.getData());
}
}
-
-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;
- }
-};
-} // 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/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp
index 6a1478a..e56da7b 100644
--- a/lib/Analysis/BugReporter.cpp
+++ b/lib/Analysis/BugReporter.cpp
@@ -322,6 +322,90 @@
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) {
+
+ 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;
+
+ if (ScanSym != Sym)
+ return true;
+
+ // Check if the previous state has this binding.
+ RVal X = VMgr.GetRVal(PrevSt, lval::MemRegionVal(R));
+
+ if (X == V) // Same binding?
+ 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.
+
+ VarDecl *VD = 0;
+
+ if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
+ if (!B->isAssignmentOp())
+ return true;
+
+ // What variable did we assign to?
+ DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
+
+ if (!DR)
+ return true;
+
+ VD = dyn_cast<VarDecl>(DR->getDecl());
+ }
+ else if (DeclStmt* DS = dyn_cast<DeclStmt>(S))
+ VD = dyn_cast<VarDecl>(DS->getDecl());
+
+ if (!VD)
+ return true;
+
+ // What is the most recently referenced variable with this binding?
+ VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
+
+ if (!MostRecent)
+ 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() + "'";
+
+ PD.push_front(new PathDiagnosticPiece(L, msg));
+ }
+
+ return true;
+ }
+};
+}
static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S,
SymbolID Sym, BugReporter& BR,
@@ -333,82 +417,53 @@
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();
+ // 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();
-
- // FIXME: Later generalize for a broader memory model.
+ NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
+ cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
+}
- // 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.
+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) {}
- for (GRState::vb_iterator I=St->vb_begin(), E=St->vb_end(); I!=E; ++I){
-
- RVal V = I.getData();
+ 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
- continue;
-
- if (ScanSym != Sym)
- continue;
-
- // Check if the previous state has this binding.
-
- RVal X = VMgr.GetRVal(PrevSt, lval::DeclVal(I.getKey()));
-
- if (X == V) // Same binding?
- continue;
-
- // Different binding. Only handle assignments for now. We don't pull
- // this check out of the loop because we will eventually handle other
- // cases.
-
- VarDecl *VD = 0;
-
- if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
- if (!B->isAssignmentOp())
- continue;
-
- // What variable did we assign to?
- DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
-
- if (!DR)
- continue;
-
- VD = dyn_cast<VarDecl>(DR->getDecl());
- }
- else if (DeclStmt* DS = dyn_cast<DeclStmt>(S))
- VD = dyn_cast<VarDecl>(DS->getDecl());
-
- if (!VD)
- continue;
-
- // What is the most recently referenced variable with this binding?
- VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
-
- if (!MostRecent)
- continue;
-
- // Create the diagnostic.
-
- FullSourceLoc L(S->getLocStart(), BR.getSourceManager());
-
- if (VD->getType()->isPointerLikeType()) {
- std::string msg = "'" + std::string(VD->getName()) +
- "' now aliases '" + MostRecent->getName() + "'";
-
- PD.push_front(new PathDiagnosticPiece(L, msg));
- }
+ 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 @@
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/lib/Analysis/CFRefCount.cpp b/lib/Analysis/CFRefCount.cpp
index 733cad1..c63529a 100644
--- a/lib/Analysis/CFRefCount.cpp
+++ b/lib/Analysis/CFRefCount.cpp
@@ -1489,7 +1489,7 @@
// 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 @@
// 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 @@
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 @@
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 @@
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 @@
// 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 @@
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/lib/Analysis/CheckNSError.cpp b/lib/Analysis/CheckNSError.cpp
index 5a1e7cb..03c9af3 100644
--- a/lib/Analysis/CheckNSError.cpp
+++ b/lib/Analysis/CheckNSError.cpp
@@ -216,7 +216,7 @@
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/lib/Analysis/Environment.cpp b/lib/Analysis/Environment.cpp
index 15a1d36..f86c4fe 100644
--- a/lib/Analysis/Environment.cpp
+++ b/lib/Analysis/Environment.cpp
@@ -107,11 +107,11 @@
}
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 @@
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/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp
index 41bf989..115d265 100644
--- a/lib/Analysis/GRExprEngine.cpp
+++ b/lib/Analysis/GRExprEngine.cpp
@@ -792,12 +792,12 @@
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 @@
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/lib/Analysis/GRExprEngineInternalChecks.cpp b/lib/Analysis/GRExprEngineInternalChecks.cpp
index e7e5f45..d61998c 100644
--- a/lib/Analysis/GRExprEngineInternalChecks.cpp
+++ b/lib/Analysis/GRExprEngineInternalChecks.cpp
@@ -194,13 +194,14 @@
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/lib/Analysis/GRSimpleVals.cpp b/lib/Analysis/GRSimpleVals.cpp
index b33d512..4470316 100644
--- a/lib/Analysis/GRSimpleVals.cpp
+++ b/lib/Analysis/GRSimpleVals.cpp
@@ -287,7 +287,7 @@
case lval::FieldOffsetKind:
// Fall-through.
- case lval::DeclValKind:
+ case lval::MemRegionKind:
case lval::FuncValKind:
case lval::GotoLabelKind:
case lval::StringLiteralValKind:
@@ -351,7 +351,7 @@
case lval::FieldOffsetKind:
// Fall-through.
- case lval::DeclValKind:
+ case lval::MemRegionKind:
case lval::FuncValKind:
case lval::GotoLabelKind:
case lval::StringLiteralValKind:
diff --git a/lib/Analysis/GRState.cpp b/lib/Analysis/GRState.cpp
index 67bff39..2f829e6 100644
--- a/lib/Analysis/GRState.cpp
+++ b/lib/Analysis/GRState.cpp
@@ -42,19 +42,18 @@
// 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/lib/Analysis/MemRegion.cpp b/lib/Analysis/MemRegion.cpp
new file mode 100644
index 0000000..7c2af42
--- /dev/null
+++ b/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/lib/Analysis/RValues.cpp b/lib/Analysis/RValues.cpp
index 5dc9cd5..337d479 100644
--- a/lib/Analysis/RValues.cpp
+++ b/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 @@
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 @@
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 @@
// 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 @@
// 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 @@
<< 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: