From bea2753da897ede723e70bcd17023d050b0603d0 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Sat, 6 Aug 2011 00:29:57 +0000 Subject: [PATCH] [analyzer] Change SymbolReaper to store region roots implied by the Environment, allowing it be queried when determining if symbols derived from regions are still live. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@137005 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Core/PathSensitive/Environment.h | 3 +-- .../StaticAnalyzer/Core/PathSensitive/Store.h | 3 +-- .../Core/PathSensitive/SymbolManager.h | 22 ++++++++++++++----- lib/StaticAnalyzer/Core/Environment.cpp | 7 +++--- lib/StaticAnalyzer/Core/GRState.cpp | 6 ++--- lib/StaticAnalyzer/Core/RegionStore.cpp | 15 ++++++------- lib/StaticAnalyzer/Core/SymbolManager.cpp | 17 +++++++++----- 7 files changed, 43 insertions(+), 30 deletions(-) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h index 40efcc43eb..2a3960236c 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Environment.h @@ -96,8 +96,7 @@ public: SVal V); Environment removeDeadBindings(Environment Env, - SymbolReaper &SymReaper, const GRState *ST, - SmallVectorImpl& RegionRoots); + SymbolReaper &SymReaper, const GRState *ST); }; } // end GR namespace diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h index 708918bbed..66022faf91 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h @@ -146,8 +146,7 @@ public: const MemRegion *castRegion(const MemRegion *region, QualType CastToTy); virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, - SymbolReaper& SymReaper, - SmallVectorImpl& RegionRoots) = 0; + SymbolReaper& SymReaper) = 0; virtual StoreRef BindDecl(Store store, const VarRegion *VR, SVal initVal) = 0; diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h index 42113167a1..a610c02f2b 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -416,11 +416,15 @@ public: }; class SymbolReaper { - typedef llvm::DenseSet SetTy; + typedef llvm::DenseSet SymbolSetTy; + typedef llvm::DenseSet RegionSetTy; - SetTy TheLiving; - SetTy MetadataInUse; - SetTy TheDead; + SymbolSetTy TheLiving; + SymbolSetTy MetadataInUse; + SymbolSetTy TheDead; + + RegionSetTy RegionRoots; + const LocationContext *LCtx; const Stmt *Loc; SymbolManager& SymMgr; @@ -438,6 +442,7 @@ public: const Stmt *getCurrentStatement() const { return Loc; } bool isLive(SymbolRef sym); + bool isLiveRegion(const MemRegion *region); bool isLive(const Stmt *ExprVal) const; bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; @@ -458,13 +463,17 @@ public: // Returns true if the symbol is dead, false if live. bool maybeDead(SymbolRef sym); - typedef SetTy::const_iterator dead_iterator; + typedef SymbolSetTy::const_iterator dead_iterator; dead_iterator dead_begin() const { return TheDead.begin(); } dead_iterator dead_end() const { return TheDead.end(); } bool hasDeadSymbols() const { return !TheDead.empty(); } + + typedef RegionSetTy::const_iterator region_iterator; + region_iterator region_begin() const { return RegionRoots.begin(); } + region_iterator region_end() const { return RegionRoots.end(); } /// isDead - Returns whether or not a symbol has been confirmed dead. This /// should only be called once all marking of dead symbols has completed. @@ -473,6 +482,8 @@ public: return TheDead.count(sym); } + void markLive(const MemRegion *region); + /// Set to the value of the symbolic store after /// StoreManager::removeDeadBindings has been called. void setReapedStore(StoreRef st) { reapedStore = st; } @@ -484,6 +495,7 @@ public: // GRStateManager::scanReachableSymbols. The method returns \c true if // symbols should continue be scanned and \c false otherwise. virtual bool VisitSymbol(SymbolRef sym) = 0; + virtual bool VisitMemRegion(const MemRegion *region) { return true; }; virtual ~SymbolVisitor(); }; diff --git a/lib/StaticAnalyzer/Core/Environment.cpp b/lib/StaticAnalyzer/Core/Environment.cpp index b34a481e32..a695437f26 100644 --- a/lib/StaticAnalyzer/Core/Environment.cpp +++ b/lib/StaticAnalyzer/Core/Environment.cpp @@ -143,8 +143,7 @@ static inline bool IsLocation(const Stmt *S) { Environment EnvironmentManager::removeDeadBindings(Environment Env, SymbolReaper &SymReaper, - const GRState *ST, - SmallVectorImpl &DRoots) { + const GRState *ST) { // We construct a new Environment object entirely, as this is cheaper than // individually removing all the subexpression bindings (which will greatly @@ -175,8 +174,8 @@ EnvironmentManager::removeDeadBindings(Environment Env, // If the block expr's value is a memory region, then mark that region. if (isa(X)) { - const MemRegion* R = cast(X).getRegion(); - DRoots.push_back(R); + const MemRegion *R = cast(X).getRegion(); + SymReaper.markLive(R); } // Mark all symbols in the block expr's value live. diff --git a/lib/StaticAnalyzer/Core/GRState.cpp b/lib/StaticAnalyzer/Core/GRState.cpp index 370f98ac56..c904ed2882 100644 --- a/lib/StaticAnalyzer/Core/GRState.cpp +++ b/lib/StaticAnalyzer/Core/GRState.cpp @@ -71,15 +71,13 @@ GRStateManager::removeDeadBindings(const GRState* state, // 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. - SmallVector RegionRoots; GRState NewState = *state; - NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, - state, RegionRoots); + NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); // Clean up the store. StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, - SymReaper, RegionRoots); + SymReaper); NewState.setStore(newStore); SymReaper.setReapedStore(newStore); diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp index 852af29d81..6a039c55f5 100644 --- a/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -373,10 +373,10 @@ public: // Part of public interface to class. /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. /// It returns a new Store with these values removed. StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, - SymbolReaper& SymReaper, - SmallVectorImpl& RegionRoots); + SymbolReaper& SymReaper); - StoreRef enterStackFrame(const GRState *state, const StackFrameContext *frame); + StoreRef enterStackFrame(const GRState *state, + const StackFrameContext *frame); //===------------------------------------------------------------------===// // Region "extents". @@ -1774,17 +1774,16 @@ bool removeDeadBindingsWorker::UpdatePostponed() { StoreRef RegionStoreManager::removeDeadBindings(Store store, const StackFrameContext *LCtx, - SymbolReaper& SymReaper, - SmallVectorImpl& RegionRoots) -{ + SymbolReaper& SymReaper) { RegionBindings B = GetRegionBindings(store); removeDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); W.GenerateClusters(); // Enqueue the region roots onto the worklist. - for (SmallVectorImpl::iterator I=RegionRoots.begin(), - E=RegionRoots.end(); I!=E; ++I) + for (SymbolReaper::region_iterator I = SymReaper.region_begin(), + E = SymReaper.region_end(); I != E; ++I) { W.AddToWorkList(*I); + } do W.RunWorkList(); while (W.UpdatePostponed()); diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp index 7ae338e8d8..6d90d19f9e 100644 --- a/lib/StaticAnalyzer/Core/SymbolManager.cpp +++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp @@ -253,6 +253,10 @@ void SymbolReaper::markLive(SymbolRef sym) { TheDead.erase(sym); } +void SymbolReaper::markLive(const MemRegion *region) { + RegionRoots.insert(region); +} + void SymbolReaper::markInUse(SymbolRef sym) { if (isa(sym)) MetadataInUse.insert(sym); @@ -266,14 +270,17 @@ bool SymbolReaper::maybeDead(SymbolRef sym) { return true; } -static bool IsLiveRegion(SymbolReaper &Reaper, const MemRegion *MR) { +bool SymbolReaper::isLiveRegion(const MemRegion *MR) { + if (RegionRoots.count(MR)) + return true; + MR = MR->getBaseRegion(); if (const SymbolicRegion *SR = dyn_cast(MR)) - return Reaper.isLive(SR->getSymbol()); + return isLive(SR->getSymbol()); if (const VarRegion *VR = dyn_cast(MR)) - return Reaper.isLive(VR, true); + return isLive(VR, true); // FIXME: This is a gross over-approximation. What we really need is a way to // tell if anything still refers to this region. Unlike SymbolicRegions, @@ -304,7 +311,7 @@ bool SymbolReaper::isLive(SymbolRef sym) { } if (const SymbolExtent *extent = dyn_cast(sym)) { - if (IsLiveRegion(*this, extent->getRegion())) { + if (isLiveRegion(extent->getRegion())) { markLive(sym); return true; } @@ -313,7 +320,7 @@ bool SymbolReaper::isLive(SymbolRef sym) { if (const SymbolMetadata *metadata = dyn_cast(sym)) { if (MetadataInUse.count(sym)) { - if (IsLiveRegion(*this, metadata->getRegion())) { + if (isLiveRegion(metadata->getRegion())) { markLive(sym); MetadataInUse.erase(sym); return true; -- 2.40.0