diff options
| -rw-r--r-- | include/clang/Checker/PathSensitive/Checker.h | 10 | ||||
| -rw-r--r-- | include/clang/Checker/PathSensitive/GRExprEngine.h | 13 | ||||
| -rw-r--r-- | include/clang/Checker/PathSensitive/GRState.h | 51 | ||||
| -rw-r--r-- | include/clang/Checker/PathSensitive/GRSubEngine.h | 23 | ||||
| -rw-r--r-- | include/clang/Checker/PathSensitive/Store.h | 25 | ||||
| -rw-r--r-- | lib/Checker/BasicStore.cpp | 17 | ||||
| -rw-r--r-- | lib/Checker/FlatStore.cpp | 13 | ||||
| -rw-r--r-- | lib/Checker/GRExprEngine.cpp | 69 | ||||
| -rw-r--r-- | lib/Checker/RegionStore.cpp | 23 |
9 files changed, 212 insertions, 32 deletions
diff --git a/include/clang/Checker/PathSensitive/Checker.h b/include/clang/Checker/PathSensitive/Checker.h index fc31796a4a..af28fc3ca7 100644 --- a/include/clang/Checker/PathSensitive/Checker.h +++ b/include/clang/Checker/PathSensitive/Checker.h @@ -290,6 +290,16 @@ public: return state; } + virtual bool WantsRegionChangeUpdate(const GRState *state) { return false; } + + virtual const GRState *EvalRegionChanges(const GRState *state, + const MemRegion * const *Begin, + const MemRegion * const *End, + bool *respondsToCallback) { + *respondsToCallback = false; + return state; + } + virtual void VisitEndAnalysis(ExplodedGraph &G, BugReporter &B, GRExprEngine &Eng) {} }; diff --git a/include/clang/Checker/PathSensitive/GRExprEngine.h b/include/clang/Checker/PathSensitive/GRExprEngine.h index 691e7f3605..55dab2a8a3 100644 --- a/include/clang/Checker/PathSensitive/GRExprEngine.h +++ b/include/clang/Checker/PathSensitive/GRExprEngine.h @@ -78,7 +78,8 @@ class GRExprEngine : public GRSubEngine { enum CallbackKind { PreVisitStmtCallback, PostVisitStmtCallback, - ProcessAssumeCallback + ProcessAssumeCallback, + EvalRegionChangesCallback }; typedef uint32_t CallbackTag; @@ -228,6 +229,16 @@ public: /// making assumptions about state values. const GRState *ProcessAssume(const GRState *state, SVal cond,bool assumption); + /// WantsRegionChangeUpdate - Called by GRStateManager to determine if a + /// region change should trigger a ProcessRegionChanges update. + bool WantsRegionChangeUpdate(const GRState* state); + + /// 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); + virtual GRStateManager& getStateManager() { return StateMgr; } StoreManager& getStoreManager() { return StateMgr.getStoreManager(); } diff --git a/include/clang/Checker/PathSensitive/GRState.h b/include/clang/Checker/PathSensitive/GRState.h index 3f7442d0fe..dfba597acc 100644 --- a/include/clang/Checker/PathSensitive/GRState.h +++ b/include/clang/Checker/PathSensitive/GRState.h @@ -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 @@ class GRStateManager { 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 @@ public: 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 @@ public: StoreManager& getStoreManager() { return *StoreMgr; } ConstraintManager& getConstraintManager() { return *ConstraintMgr; } + GRSubEngine& getOwningEngine() { return Eng; } const GRState* RemoveDeadBindings(const GRState* St, const StackFrameContext *LCtx, @@ -620,7 +626,8 @@ inline const GRState *GRState::AssumeInBound(DefinedOrUnknownSVal Idx, inline const GRState * GRState::bindCompoundLiteral(const CompoundLiteralExpr* CL, - const LocationContext *LC, SVal V) const { + const LocationContext *LC, + SVal V) const { Store new_store = getStateManager().StoreMgr->BindCompoundLiteral(St, CL, LC, V); return makeWithStore(new_store); @@ -637,8 +644,15 @@ inline const GRState *GRState::bindDeclWithNoInit(const VarRegion* VR) const { } inline const GRState *GRState::bindLoc(Loc LV, SVal V) const { - Store new_store = getStateManager().StoreMgr->Bind(St, LV, V); - return makeWithStore(new_store); + 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; } inline const GRState *GRState::bindLoc(SVal LV, SVal V) const { @@ -646,9 +660,11 @@ inline const GRState *GRState::bindLoc(SVal LV, SVal V) const { } inline const GRState *GRState::bindDefault(SVal loc, SVal V) const { + GRStateManager &Mgr = getStateManager(); const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion(); - Store new_store = getStateManager().StoreMgr->BindDefault(St, R, V); - return makeWithStore(new_store); + Store new_store = Mgr.StoreMgr->BindDefault(St, R, V); + const GRState *new_state = makeWithStore(new_store); + return Mgr.getOwningEngine().ProcessRegionChange(new_state, R); } inline const GRState * @@ -657,10 +673,27 @@ GRState::InvalidateRegions(const MemRegion * const *Begin, const Expr *E, unsigned Count, StoreManager::InvalidatedSymbols *IS, bool invalidateGlobals) const { - Store new_store - = getStateManager().StoreMgr->InvalidateRegions(St, Begin, End, + GRStateManager &Mgr = getStateManager(); + GRSubEngine &Eng = Mgr.getOwningEngine(); + + if (Eng.WantsRegionChangeUpdate(this)) { + StoreManager::InvalidatedRegions Regions; + + Store new_store = Mgr.StoreMgr->InvalidateRegions(St, Begin, End, + E, Count, IS, + invalidateGlobals, + &Regions); + const GRState *new_state = makeWithStore(new_store); + + return Eng.ProcessRegionChanges(new_state, + &Regions.front(), + &Regions.back()+1); + } + + Store new_store = Mgr.StoreMgr->InvalidateRegions(St, Begin, End, E, Count, IS, - invalidateGlobals); + invalidateGlobals, + NULL); return makeWithStore(new_store); } diff --git a/include/clang/Checker/PathSensitive/GRSubEngine.h b/include/clang/Checker/PathSensitive/GRSubEngine.h index 90f4798359..1904835fbc 100644 --- a/include/clang/Checker/PathSensitive/GRSubEngine.h +++ b/include/clang/Checker/PathSensitive/GRSubEngine.h @@ -17,7 +17,7 @@ namespace clang { -class Stmt; +class AnalysisManager; class CFGBlock; class CFGElement; class ExplodedNode; @@ -32,6 +32,8 @@ class GREndPathNodeBuilder; class GRCallEnterNodeBuilder; class GRCallExitNodeBuilder; class LocationContext; +class MemRegion; +class Stmt; class GRSubEngine { public: @@ -75,12 +77,27 @@ public: // 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; - + + /// WantsRegionChangeUpdate - Called by GRStateManager to determine if a + /// region change should trigger a ProcessRegionChanges update. + virtual bool WantsRegionChangeUpdate(const GRState* state) = 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; diff --git a/include/clang/Checker/PathSensitive/Store.h b/include/clang/Checker/PathSensitive/Store.h index 07f02a7e62..dfe1e22f86 100644 --- a/include/clang/Checker/PathSensitive/Store.h +++ b/include/clang/Checker/PathSensitive/Store.h @@ -159,13 +159,34 @@ public: virtual Store BindDeclWithNoInit(Store store, const VarRegion *VR) = 0; typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols; - + typedef llvm::SmallVector<const MemRegion *, 8> InvalidatedRegions; + + /// InvalidateRegions - Clears out the specified regions from the store, + /// marking their values as unknown. Depending on the store, this may also + /// invalidate additional regions that may have changed based on accessing + /// the given regions. Optionally, invalidates non-static globals as well. + /// \param[in] store The initial store + /// \param[in] Begin A pointer to the first region to invalidate. + /// \param[in] End A pointer just past the last region to invalidate. + /// \param[in] E The current statement being evaluated. Used to conjure + /// symbols to mark the values of invalidated regions. + /// \param[in] Count The current block count. Used to conjure + /// symbols to mark the values of invalidated regions. + /// \param[in,out] IS A set to fill with any symbols that are no longer + /// accessible. Pass \c NULL if this information will not be used. + /// \param[in] invalidateGlobals If \c true, any non-static global regions + /// are invalidated as well. + /// \param[in,out] Regions A vector to fill with any regions being + /// invalidated. This should include any regions explicitly invalidated + /// even if they do not currently have bindings. Pass \c NULL if this + /// information will not be used. 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; /// EnterStackFrame - Let the StoreManager to do something when execution /// engine is about to execute into a callee. diff --git a/lib/Checker/BasicStore.cpp b/lib/Checker/BasicStore.cpp index 7d01c9e110..a5e87e4cb1 100644 --- a/lib/Checker/BasicStore.cpp +++ b/lib/Checker/BasicStore.cpp @@ -52,7 +52,7 @@ public: 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 @@ StoreManager::BindingsHandler::~BindingsHandler() {} 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,8 @@ Store BasicStoreManager::InvalidateRegions(Store store, continue; } store = InvalidateRegion(store, *I, E, Count, IS); + if (Regions) + Regions->push_back(R); } // FIXME: This is copy-and-paste from RegionStore.cpp. @@ -556,6 +559,8 @@ Store BasicStoreManager::InvalidateRegions(Store store, Count); store = Bind(store, loc::MemRegionVal(GS), V); + if (Regions) + Regions->push_back(GS); } return store; diff --git a/lib/Checker/FlatStore.cpp b/lib/Checker/FlatStore.cpp index 64c6ed0620..46e24773db 100644 --- a/lib/Checker/FlatStore.cpp +++ b/lib/Checker/FlatStore.cpp @@ -60,7 +60,7 @@ public: 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::BindDeclWithNoInit(Store store, const VarRegion *VR) { } 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; } diff --git a/lib/Checker/GRExprEngine.cpp b/lib/Checker/GRExprEngine.cpp index fe19c05779..e306ac6667 100644 --- a/lib/Checker/GRExprEngine.cpp +++ b/lib/Checker/GRExprEngine.cpp @@ -557,6 +557,75 @@ const GRState *GRExprEngine::ProcessAssume(const GRState *state, SVal cond, return TF->EvalAssume(state, cond, assumption); } +bool GRExprEngine::WantsRegionChangeUpdate(const GRState* state) { + CallbackTag K = GetCallbackTag(EvalRegionChangesCallback); + CheckersOrdered *CO = COCache[K]; + + if (!CO) + CO = &Checkers; + + for (CheckersOrdered::iterator I = CO->begin(), E = CO->end(); I != E; ++I) { + Checker *C = I->second; + if (C->WantsRegionChangeUpdate(state)) + return true; + } + + return false; +} + +const GRState * +GRExprEngine::ProcessRegionChanges(const GRState *state, + const MemRegion * const *Begin, + const MemRegion * const *End) { + // FIXME: Most of this method is copy-pasted from ProcessAssume. + + // Determine if we already have a cached 'CheckersOrdered' vector + // specifically tailored for processing region changes. 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 + // callback, 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 = CO->begin(), E = CO->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; +} + void GRExprEngine::ProcessEndWorklist(bool hasWorkRemaining) { for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end(); I != E; ++I) { diff --git a/lib/Checker/RegionStore.cpp b/lib/Checker/RegionStore.cpp index 221406e1f3..16aefbf7ab 100644 --- a/lib/Checker/RegionStore.cpp +++ b/lib/Checker/RegionStore.cpp @@ -231,7 +231,8 @@ public: 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 @@ class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker> 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,10 @@ void InvalidateRegionsWorker::VisitBaseRegion(const MemRegion *baseR) { return; } + // Otherwise, we have a normal data region. Record that we touched the region. + if (Regions) + 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 +707,11 @@ Store RegionStoreManager::InvalidateRegions(Store store, 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 +734,11 @@ Store RegionStoreManager::InvalidateRegions(Store store, /* 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. + if (Regions) + Regions->push_back(GS); } return B.getRoot(); |