[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

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<const MemRegion*>& 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<const MemRegion*>& 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<SymbolRef> SetTy;
+  typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
+  typedef llvm::DenseSet<const MemRegion *> 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<const MemRegion*> &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<loc::MemRegionVal>(X)) {
-        const MemRegion* R = cast<loc::MemRegionVal>(X).getRegion();
-        DRoots.push_back(R);
+        const MemRegion *R = cast<loc::MemRegionVal>(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<const MemRegion*, 10> 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<const MemRegion*>& 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<const MemRegion*>& 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<const MemRegion*>::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<SymbolMetadata>(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<SymbolicRegion>(MR))
-    return Reaper.isLive(SR->getSymbol());
+    return isLive(SR->getSymbol());
 
   if (const VarRegion *VR = dyn_cast<VarRegion>(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<SymbolExtent>(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<SymbolMetadata>(sym)) {
     if (MetadataInUse.count(sym)) {
-      if (IsLiveRegion(*this, metadata->getRegion())) {
+      if (isLiveRegion(metadata->getRegion())) {
         markLive(sym);
         MetadataInUse.erase(sym);
         return true;