[cfe-dev] Proposed: change tracking for RegionStore
Ted Kremenek
kremenek at apple.com
Mon Aug 9 13:45:50 PDT 2010
On Aug 7, 2010, at 6:42 PM, Jordy Rose wrote:
> Second pass. This mainly addresses the fact that InvalidateRegions doesn't
> just invalidate the regions it's given -- thanks, Ted -- by recording all
> the touched regions in a SmallVector.
Thanks Jordy. I'm still really leery about the cost of this, but I'm willing to see how CStringChecker makes use of the information so we can see how we can possibly do this better. Recording the entire set of invalidated regions seems really expensive. Comments inline:
Index: include/clang/Checker/PathSensitive/Store.h
===================================================================
--- include/clang/Checker/PathSensitive/Store.h (revision 110519)
+++ include/clang/Checker/PathSensitive/Store.h (working copy)
@@ -159,13 +159,15 @@
virtual Store BindDeclWithNoInit(Store store, const VarRegion *VR) = 0;
typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
+ typedef llvm::SmallVector<const MemRegion *, 8> InvalidatedRegions;
virtual Store InvalidateRegions(Store store,
const MemRegion * const *Begin,
const MemRegion * const *End,
const Expr *E, unsigned Count,
InvalidatedSymbols *IS,
- bool invalidateGlobals) = 0;
+ bool invalidateGlobals,
+ InvalidatedRegions &Regions) = 0;
Does it make sense to pass in a pointer instead of a reference? The problem with passing in a reference is that it means we always have to do the work of recording the invalidated MemRegions.
/// EnterStackFrame - Let the StoreManager to do something when execution
/// engine is about to execute into a callee.
Index: include/clang/Checker/PathSensitive/GRExprEngine.h
===================================================================
--- include/clang/Checker/PathSensitive/GRExprEngine.h (revision 110519)
+++ include/clang/Checker/PathSensitive/GRExprEngine.h (working copy)
@@ -78,7 +78,8 @@
enum CallbackKind {
PreVisitStmtCallback,
PostVisitStmtCallback,
- ProcessAssumeCallback
+ ProcessAssumeCallback,
+ EvalRegionChangesCallback
};
typedef uint32_t CallbackTag;
@@ -228,6 +229,12 @@
/// making assumptions about state values.
const GRState *ProcessAssume(const GRState *state, SVal cond,bool assumption);
+ /// ProcessRegionChanges - Called by GRStateManager whenever a change is made
+ /// to the store. Used to update checkers that track region values.
+ const GRState* ProcessRegionChanges(const GRState *state,
+ const MemRegion * const *Begin,
+ const MemRegion * const *End);
+
Looks good.
virtual GRStateManager& getStateManager() { return StateMgr; }
StoreManager& getStoreManager() { return StateMgr.getStoreManager(); }
Index: include/clang/Checker/PathSensitive/Checker.h
===================================================================
--- include/clang/Checker/PathSensitive/Checker.h (revision 110519)
+++ include/clang/Checker/PathSensitive/Checker.h (working copy)
@@ -284,6 +284,14 @@
return state;
}
+ virtual const GRState *EvalRegionChanges(const GRState *state,
+ const MemRegion * const *Begin,
+ const MemRegion * const *End,
+ bool *respondsToCallback) {
+ *respondsToCallback = false;
+ return state;
+ }
+
Looks good, although we should probably just move this out-of-line at this point.
virtual void VisitEndAnalysis(ExplodedGraph &G, BugReporter &B,
GRExprEngine &Eng) {}
};
Index: include/clang/Checker/PathSensitive/GRSubEngine.h
===================================================================
--- include/clang/Checker/PathSensitive/GRSubEngine.h (revision 110519)
+++ include/clang/Checker/PathSensitive/GRSubEngine.h (working copy)
@@ -17,7 +17,7 @@
namespace clang {
-class Stmt;
+class AnalysisManager;
class CFGBlock;
class CFGElement;
class ExplodedNode;
@@ -32,6 +32,8 @@
class GRCallEnterNodeBuilder;
class GRCallExitNodeBuilder;
class LocationContext;
+class MemRegion;
+class Stmt;
class GRSubEngine {
public:
@@ -75,12 +77,23 @@
// Generate the first post callsite node.
virtual void ProcessCallExit(GRCallExitNodeBuilder &builder) = 0;
-
+
/// Called by ConstraintManager. Used to call checker-specific
/// logic for handling assumptions on symbolic values.
virtual const GRState* ProcessAssume(const GRState *state,
SVal cond, bool assumption) = 0;
-
+
+ /// ProcessRegionChanges - Called by GRStateManager whenever a change is made
+ /// to the store. Used to update checkers that track region values.
+ virtual const GRState* ProcessRegionChanges(const GRState* state,
+ const MemRegion* const *Begin,
+ const MemRegion* const *End) = 0;
+
+ inline const GRState* ProcessRegionChange(const GRState* state,
+ const MemRegion* MR) {
+ return ProcessRegionChanges(state, &MR, &MR+1);
+ }
+
/// Called by GRCoreEngine when the analysis worklist is either empty or the
// maximum number of analysis steps have been reached.
virtual void ProcessEndWorklist(bool hasWorkRemaining) = 0;
Index: include/clang/Checker/PathSensitive/GRState.h
===================================================================
--- include/clang/Checker/PathSensitive/GRState.h (revision 110519)
+++ include/clang/Checker/PathSensitive/GRState.h (working copy)
@@ -16,6 +16,7 @@
#include "clang/Checker/PathSensitive/ConstraintManager.h"
#include "clang/Checker/PathSensitive/Environment.h"
+#include "clang/Checker/PathSensitive/GRSubEngine.h"
#include "clang/Checker/PathSensitive/Store.h"
#include "clang/Checker/PathSensitive/ValueManager.h"
#include "llvm/ADT/FoldingSet.h"
@@ -397,6 +398,9 @@
friend class GRState;
friend class GRExprEngine; // FIXME: Remove.
private:
+ /// Eng - The GRSubEngine that owns this state manager.
+ GRSubEngine &Eng;
+
EnvironmentManager EnvMgr;
llvm::OwningPtr<StoreManager> StoreMgr;
llvm::OwningPtr<ConstraintManager> ConstraintMgr;
@@ -426,7 +430,8 @@
ConstraintManagerCreator CreateConstraintManager,
llvm::BumpPtrAllocator& alloc,
GRSubEngine &subeng)
- : EnvMgr(alloc),
+ : Eng(subeng),
+ EnvMgr(alloc),
GDMFactory(alloc),
ValueMgr(alloc, Ctx, *this),
Alloc(alloc) {
@@ -469,6 +474,7 @@
StoreManager& getStoreManager() { return *StoreMgr; }
ConstraintManager& getConstraintManager() { return *ConstraintMgr; }
+ GRSubEngine& getOwningEngine() { return Eng; }
const GRState* RemoveDeadBindings(const GRState* St,
const StackFrameContext *LCtx,
@@ -618,58 +624,10 @@
cast<DefinedSVal>(UpperBound), Assumption);
}
-inline const GRState *
-GRState::bindCompoundLiteral(const CompoundLiteralExpr* CL,
- const LocationContext *LC, SVal V) const {
- Store new_store =
- getStateManager().StoreMgr->BindCompoundLiteral(St, CL, LC, V);
- return makeWithStore(new_store);
-}
-
-inline const GRState *GRState::bindDecl(const VarRegion* VR, SVal IVal) const {
- Store new_store = getStateManager().StoreMgr->BindDecl(St, VR, IVal);
- return makeWithStore(new_store);
-}
-
-inline const GRState *GRState::bindDeclWithNoInit(const VarRegion* VR) const {
- Store new_store = getStateManager().StoreMgr->BindDeclWithNoInit(St, VR);
- return makeWithStore(new_store);
-}
-
-inline const GRState *GRState::bindLoc(Loc LV, SVal V) const {
- Store new_store = getStateManager().StoreMgr->Bind(St, LV, V);
- return makeWithStore(new_store);
-}
-
inline const GRState *GRState::bindLoc(SVal LV, SVal V) const {
return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V);
}
When moving these methods out-of-line, please commit that change in another patch. It separates out the functional change being done by your patch from the "cosmetic" one by moving these methods out-of-line. Keeping it all together makes this patch a little harder to follow.
-inline const GRState *GRState::bindDefault(SVal loc, SVal V) const {
- const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion();
- Store new_store = getStateManager().StoreMgr->BindDefault(St, R, V);
- return makeWithStore(new_store);
-}
-
-inline const GRState *
-GRState::InvalidateRegions(const MemRegion * const *Begin,
- const MemRegion * const *End,
- const Expr *E, unsigned Count,
- StoreManager::InvalidatedSymbols *IS,
- bool invalidateGlobals) const {
- Store new_store
- = getStateManager().StoreMgr->InvalidateRegions(St, Begin, End,
- E, Count, IS,
- invalidateGlobals);
- return makeWithStore(new_store);
-}
-
-inline const GRState *
-GRState::EnterStackFrame(const StackFrameContext *frame) const {
- Store new_store = getStateManager().StoreMgr->EnterStackFrame(this, frame);
- return makeWithStore(new_store);
-}
-
inline Loc GRState::getLValue(const VarDecl* VD,
const LocationContext *LC) const {
return getStateManager().StoreMgr->getLValueVar(VD, LC);
Index: lib/Checker/FlatStore.cpp
===================================================================
--- lib/Checker/FlatStore.cpp (revision 110519)
+++ lib/Checker/FlatStore.cpp (working copy)
@@ -60,7 +60,7 @@
Store InvalidateRegions(Store store, const MemRegion * const *I,
const MemRegion * const *E, const Expr *Ex,
unsigned Count, InvalidatedSymbols *IS,
- bool invalidateGlobals);
+ bool invalidateGlobals, InvalidatedRegions &Regions);
void print(Store store, llvm::raw_ostream& Out, const char* nl,
const char *sep);
@@ -155,11 +155,12 @@
}
Store FlatStoreManager::InvalidateRegions(Store store,
- const MemRegion * const *I,
- const MemRegion * const *E,
- const Expr *Ex, unsigned Count,
- InvalidatedSymbols *IS,
- bool invalidateGlobals) {
+ const MemRegion * const *I,
+ const MemRegion * const *E,
+ const Expr *Ex, unsigned Count,
+ InvalidatedSymbols *IS,
+ bool invalidateGlobals,
+ InvalidatedRegions &Regions) {
assert(false && "Not implemented");
return store;
}
Index: lib/Checker/GRState.cpp
===================================================================
--- lib/Checker/GRState.cpp (revision 110519)
+++ lib/Checker/GRState.cpp (working copy)
@@ -68,6 +68,29 @@
return getPersistentState(State);
}
+const GRState * GRState::bindCompoundLiteral(const CompoundLiteralExpr* CL,
+ const LocationContext *LC,
+ SVal V) const {
+ Store new_store =
+ getStateManager().StoreMgr->BindCompoundLiteral(St, CL, LC, V);
+ return makeWithStore(new_store);
+}
+
+const GRState *GRState::bindDecl(const VarRegion* VR, SVal IVal) const {
+ Store new_store = getStateManager().StoreMgr->BindDecl(St, VR, IVal);
+ return makeWithStore(new_store);
+}
+
+const GRState *GRState::bindDeclWithNoInit(const VarRegion* VR) const {
+ Store new_store = getStateManager().StoreMgr->BindDeclWithNoInit(St, VR);
+ return makeWithStore(new_store);
+}
+
+const GRState *GRState::EnterStackFrame(const StackFrameContext *frame) const {
+ Store new_store = getStateManager().StoreMgr->EnterStackFrame(this, frame);
+ return makeWithStore(new_store);
+}
+
const GRState *GRState::unbindLoc(Loc LV) const {
assert(!isa<loc::MemRegionVal>(LV) && "Use InvalidateRegion instead.");
@@ -80,6 +103,46 @@
return makeWithStore(NewStore);
}
+const GRState *GRState::bindLoc(Loc LV, SVal V) const {
+ GRStateManager &Mgr = getStateManager();
+ Store new_store = Mgr.StoreMgr->Bind(St, LV, V);
+ const GRState *new_state = makeWithStore(new_store);
+
+ const MemRegion *MR = LV.getAsRegion();
+ if (MR)
+ return Mgr.getOwningEngine().ProcessRegionChange(new_state, MR);
+
+ return new_state;
+}
+
+const GRState *GRState::bindDefault(SVal loc, SVal V) const {
+ GRStateManager &Mgr = getStateManager();
+ const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion();
+ Store new_store = Mgr.StoreMgr->BindDefault(St, R, V);
+ const GRState *new_state = makeWithStore(new_store);
+ return Mgr.getOwningEngine().ProcessRegionChange(new_state, R);
+}
+
+const GRState *GRState::InvalidateRegions(const MemRegion * const *Begin,
+ const MemRegion * const *End,
+ const Expr *E, unsigned Count,
+ StoreManager::InvalidatedSymbols *IS,
+ bool invalidateGlobals) const {
+ StoreManager::InvalidatedRegions Regions;
+
+ GRStateManager &Mgr = getStateManager();
+ Store new_store = Mgr.StoreMgr->InvalidateRegions(St, Begin, End,
+ E, Count, IS,
+ invalidateGlobals,
+ Regions);
+ const GRState *new_state = makeWithStore(new_store);
+
+ GRSubEngine &Eng = Mgr.getOwningEngine();
+ return Eng.ProcessRegionChanges(new_state,
+ &Regions.front(),
+ &Regions.back()+1);
+}
+
SVal GRState::getSValAsScalarOrLoc(const MemRegion *R) const {
// We only want to do fetches from regions that we can actually bind
// values. For example, SymbolicRegions of type 'id<...>' cannot
Index: lib/Checker/BasicStore.cpp
===================================================================
--- lib/Checker/BasicStore.cpp (revision 110519)
+++ lib/Checker/BasicStore.cpp (working copy)
@@ -52,7 +52,7 @@
Store InvalidateRegions(Store store, const MemRegion * const *Begin,
const MemRegion * const *End, const Expr *E,
unsigned Count, InvalidatedSymbols *IS,
- bool invalidateGlobals);
+ bool invalidateGlobals, InvalidatedRegions &Regions);
Store scanForIvars(Stmt *B, const Decl* SelfDecl,
const MemRegion *SelfRegion, Store St);
@@ -521,11 +521,12 @@
Store BasicStoreManager::InvalidateRegions(Store store,
- const MemRegion * const *I,
- const MemRegion * const *End,
- const Expr *E, unsigned Count,
- InvalidatedSymbols *IS,
- bool invalidateGlobals) {
+ const MemRegion * const *I,
+ const MemRegion * const *End,
+ const Expr *E, unsigned Count,
+ InvalidatedSymbols *IS,
+ bool invalidateGlobals,
+ InvalidatedRegions &Regions) {
if (invalidateGlobals) {
BindingsTy B = GetBindings(store);
for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
@@ -543,6 +544,7 @@
continue;
}
store = InvalidateRegion(store, *I, E, Count, IS);
+ Regions.push_back(R);
}
Note that if 'Regions' was a pointer instead of a reference, we could conditionally do this work instead of always paying the cost.
// FIXME: This is copy-and-paste from RegionStore.cpp.
@@ -556,6 +558,7 @@
Count);
store = Bind(store, loc::MemRegionVal(GS), V);
+ Regions.push_back(GS);
}
Same comment.
return store;
Index: lib/Checker/RegionStore.cpp
===================================================================
--- lib/Checker/RegionStore.cpp (revision 110519)
+++ lib/Checker/RegionStore.cpp (working copy)
@@ -231,7 +231,8 @@
const MemRegion * const *End,
const Expr *E, unsigned Count,
InvalidatedSymbols *IS,
- bool invalidateGlobals);
+ bool invalidateGlobals,
+ InvalidatedRegions &Regions);
public: // Made public for helper classes.
@@ -572,14 +573,16 @@
const Expr *Ex;
unsigned Count;
StoreManager::InvalidatedSymbols *IS;
+ StoreManager::InvalidatedRegions &Regions;
public:
InvalidateRegionsWorker(RegionStoreManager &rm,
GRStateManager &stateMgr,
RegionBindings b,
const Expr *ex, unsigned count,
- StoreManager::InvalidatedSymbols *is)
+ StoreManager::InvalidatedSymbols *is,
+ StoreManager::InvalidatedRegions &r)
: ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b),
- Ex(ex), Count(count), IS(is) {}
+ Ex(ex), Count(count), IS(is), Regions(r) {}
void VisitCluster(const MemRegion *baseR, BindingKey *I, BindingKey *E);
void VisitBaseRegion(const MemRegion *baseR);
@@ -650,6 +653,9 @@
return;
}
+ // Otherwise, we have a normal data region. Record that we touched the region.
+ Regions.push_back(baseR);
+
if (isa<AllocaRegion>(baseR) || isa<SymbolicRegion>(baseR)) {
// Invalidate the region by setting its default value to
// conjured symbol. The type of the symbol is irrelavant.
@@ -700,10 +706,11 @@
const MemRegion * const *E,
const Expr *Ex, unsigned Count,
InvalidatedSymbols *IS,
- bool invalidateGlobals) {
+ bool invalidateGlobals,
+ InvalidatedRegions &Regions) {
InvalidateRegionsWorker W(*this, StateMgr,
RegionStoreManager::GetRegionBindings(store),
- Ex, Count, IS);
+ Ex, Count, IS, Regions);
// Scan the bindings and generate the clusters.
W.GenerateClusters(invalidateGlobals);
@@ -726,6 +733,10 @@
/* symbol type, doesn't matter */ Ctx.IntTy,
Count);
B = Add(B, BindingKey::Make(GS, BindingKey::Default), V);
+
+ // Even if there are no bindings in the global scope, we still need to
+ // record that we touched it.
+ Regions.push_back(GS);
}
Same comment. Make 'Region's a pointer that can be null.
return B.getRoot();
Index: lib/Checker/GRExprEngine.cpp
===================================================================
--- lib/Checker/GRExprEngine.cpp (revision 110519)
+++ lib/Checker/GRExprEngine.cpp (working copy)
@@ -558,6 +558,59 @@
return TF->EvalAssume(state, cond, assumption);
}
+const GRState *
+GRExprEngine::ProcessRegionChanges(const GRState *state,
+ const MemRegion * const *Begin,
+ const MemRegion * const *End) {
+ // Determine if we already have a cached 'CheckersOrdered' vector
+ // specifically tailored for processing assumptions. This
+ // can reduce the number of checkers actually called.
+ CheckersOrdered *CO = &Checkers;
+ llvm::OwningPtr<CheckersOrdered> NewCO;
+
+ CallbackTag K = GetCallbackTag(EvalRegionChangesCallback);
+ CheckersOrdered *& CO_Ref = COCache[K];
+
+ if (!CO_Ref) {
+ // If we have no previously cached CheckersOrdered vector for this
+ // statement kind, then create one.
+ NewCO.reset(new CheckersOrdered);
+ }
+ else {
+ // Use the already cached set.
+ CO = CO_Ref;
+ }
+
+ // If there are no checkers, just return the state as is.
+ if (CO->empty())
+ return state;
+
+ for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
+ I != E; ++I) {
+
+ // If any checker declares the state infeasible (or if it starts that way),
+ // bail out.
+ if (!state)
+ return NULL;
+
+ Checker *C = I->second;
+ bool respondsToCallback = true;
+
+ state = C->EvalRegionChanges(state, Begin, End, &respondsToCallback);
+
+ // See if we're building a cache of checkers that care about region changes.
+ if (NewCO.get() && respondsToCallback)
+ NewCO->push_back(*I);
+ }
+
+ // If we got through all the checkers, and we built a list of those that
+ // care about region changes, save it.
+ if (NewCO.get())
+ CO_Ref = NewCO.take();
+
+ return state;
+}
+
This is more copy-paste. We should be able to refactor this (in a later patch).
void GRExprEngine::ProcessEndWorklist(bool hasWorkRemaining) {
for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
I != E; ++I) {
More information about the cfe-dev
mailing list