Static Analyzer: Replace LiveSymbols/DeadSymbols sets with a new object called "SymbolReaper". Right now it just consolidates the two and cleans up some client code, but shortly it will be used to enable "lazy computation" of live symbols for use with RegionStore.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@62722 91177308-0d34-0410-b5e6-96231b3b80d8

8 files changed, 83 insertions, 84 deletions

diff --git a/lib/Analysis/BasicConstraintManager.cpp b/lib/Analysis/BasicConstraintManager.cpp
index d9d97c601a..450c38f20b 100644
--- a/lib/Analysis/BasicConstraintManager.cpp
+++ b/lib/Analysis/BasicConstraintManager.cpp
@@ -82,9 +82,8 @@ public:
   bool isNotEqual(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
   bool isEqual(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
 
-  const GRState* RemoveDeadBindings(const GRState* St,
-                                    StoreManager::LiveSymbolsTy& LSymbols,
-                                    StoreManager::DeadSymbolsTy& DSymbols);
+  const GRState* RemoveDeadBindings(const GRState* St, SymbolReaper& SymReaper);
+
 
   void print(const GRState* St, std::ostream& Out, 
              const char* nl, const char *sep);
@@ -504,19 +503,17 @@ bool BasicConstraintManager::isEqual(const GRState* St, SymbolRef sym,
 
 /// Scan all symbols referenced by the constraints. If the symbol is not alive
 /// as marked in LSymbols, mark it as dead in DSymbols.
-const GRState* BasicConstraintManager::RemoveDeadBindings(const GRState* St,
-                                        StoreManager::LiveSymbolsTy& LSymbols,
-                                        StoreManager::DeadSymbolsTy& DSymbols) {
+const GRState*
+BasicConstraintManager::RemoveDeadBindings(const GRState* St,
+                                           SymbolReaper& SymReaper) {
+
   GRStateRef state(St, StateMgr);
   ConstEqTy CE = state.get<ConstEqTy>();
   ConstEqTy::Factory& CEFactory = state.get_context<ConstEqTy>();
 
   for (ConstEqTy::iterator I = CE.begin(), E = CE.end(); I!=E; ++I) {
-    SymbolRef sym = I.getKey();        
-    if (!LSymbols.count(sym)) {
-      DSymbols.insert(sym);
-      CE = CEFactory.Remove(CE, sym);
-    }
+    SymbolRef sym = I.getKey();
+    if (SymReaper.maybeDead(sym)) CE = CEFactory.Remove(CE, sym);
   }
   state = state.set<ConstEqTy>(CE);
 
@@ -525,10 +522,7 @@ const GRState* BasicConstraintManager::RemoveDeadBindings(const GRState* St,
 
   for (ConstNotEqTy::iterator I = CNE.begin(), E = CNE.end(); I != E; ++I) {
     SymbolRef sym = I.getKey();    
-    if (!LSymbols.count(sym)) {
-      DSymbols.insert(sym);
-      CNE = CNEFactory.Remove(CNE, sym);
-    }
+    if (SymReaper.maybeDead(sym)) CNE = CNEFactory.Remove(CNE, sym);
   }
   
   return state.set<ConstNotEqTy>(CNE);
diff --git a/lib/Analysis/BasicStore.cpp b/lib/Analysis/BasicStore.cpp
index b223114a51..7315ec71ac 100644
--- a/lib/Analysis/BasicStore.cpp
+++ b/lib/Analysis/BasicStore.cpp
@@ -88,10 +88,10 @@ public:
   /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
   ///  It returns a new Store with these values removed, and populates LSymbols
   ///  and DSymbols with the known set of live and dead symbols respectively.
-  Store RemoveDeadBindings(const GRState* state, Stmt* Loc,
-                           const LiveVariables& Live,
-                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
-                           LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols);
+  Store
+  RemoveDeadBindings(const GRState* state, Stmt* Loc,
+                     SymbolReaper& SymReaper,
+                     llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
 
   void iterBindings(Store store, BindingsHandler& f);
 
@@ -344,9 +344,9 @@ Store BasicStoreManager::Remove(Store store, Loc loc) {
 
 Store
 BasicStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
-                          const LiveVariables& Liveness,
-                          llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
-                          LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols) {
+                                      SymbolReaper& SymReaper,
+                          llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
+{
   
   Store store = state->getStore();
   VarBindingsTy B = GetVarBindings(store);
@@ -354,12 +354,12 @@ BasicStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
   
   // Iterate over the variable bindings.
   for (VarBindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I)
-    if (Liveness.isLive(Loc, I.getKey())) {
+    if (SymReaper.isLive(Loc, I.getKey())) {
       RegionRoots.push_back(MRMgr.getVarRegion(I.getKey()));      
       SVal X = I.getData();
       
       for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
-        LSymbols.insert(*SI);
+        SymReaper.markLive(*SI);
     }
   
   // Scan for live variables and live symbols.
@@ -371,7 +371,7 @@ BasicStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
     
     while (MR) {
       if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
-        LSymbols.insert(SymR->getSymbol());
+        SymReaper.markLive(SymR->getSymbol());
         break;
       }
       else if (const VarRegion* R = dyn_cast<VarRegion>(MR)) {
@@ -382,8 +382,8 @@ BasicStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
         SVal X = Retrieve(state, loc::MemRegionVal(R));
     
         // FIXME: We need to handle symbols nested in region definitions.
-        for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
-          LSymbols.insert(*SI);
+        for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
+          SymReaper.markLive(*SI);
     
         if (!isa<loc::MemRegionVal>(X))
           break;
@@ -408,7 +408,7 @@ BasicStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
       SVal X = I.getData();
       
       for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
-        if (!LSymbols.count(*SI)) DSymbols.insert(*SI);
+        SymReaper.maybeDead(*SI);
     }
   }
   
diff --git a/lib/Analysis/CFRefCount.cpp b/lib/Analysis/CFRefCount.cpp
index c72d2a3070..4731921731 100644
--- a/lib/Analysis/CFRefCount.cpp
+++ b/lib/Analysis/CFRefCount.cpp
@@ -1367,9 +1367,9 @@ public:
                                GRExprEngine& Engine,
                                GRStmtNodeBuilder<GRState>& Builder,
                                ExplodedNode<GRState>* Pred,
-                               Stmt* S,
-                               const GRState* St,
-                               const GRStateManager::DeadSymbolsTy& Dead);
+                               Stmt* S, const GRState* state,
+                               SymbolReaper& SymReaper);
+
   // Return statements.
   
   virtual void EvalReturn(ExplodedNodeSet<GRState>& Dst,
@@ -1915,20 +1915,18 @@ void CFRefCount::EvalDeadSymbols(ExplodedNodeSet<GRState>& Dst,
                                  ExplodedNode<GRState>* Pred,
                                  Stmt* S,
                                  const GRState* St,
-                                 const GRStateManager::DeadSymbolsTy& Dead) {
+                                 SymbolReaper& SymReaper) {
     
   // FIXME: a lot of copy-and-paste from EvalEndPath.  Refactor.
   
   RefBindings B = St->get<RefBindings>();
   llvm::SmallVector<std::pair<SymbolRef,bool>, 10> Leaked;
   
-  for (GRStateManager::DeadSymbolsTy::const_iterator
-       I=Dead.begin(), E=Dead.end(); I!=E; ++I) {
+  for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
+        E = SymReaper.dead_end(); I != E; ++I) {
     
     const RefVal* T = B.lookup(*I);
-
-    if (!T)
-      continue;
+    if (!T) continue;
     
     bool hasLeak = false;
     
diff --git a/lib/Analysis/Environment.cpp b/lib/Analysis/Environment.cpp
index 5f9e97eb0a..c4ed349906 100644
--- a/lib/Analysis/Environment.cpp
+++ b/lib/Analysis/Environment.cpp
@@ -108,9 +108,8 @@ Environment EnvironmentManager::BindExpr(const Environment& Env, Stmt* E,SVal V,
 
 Environment 
 EnvironmentManager::RemoveDeadBindings(Environment Env, Stmt* Loc,
-                                const LiveVariables& Liveness,
-                                llvm::SmallVectorImpl<const MemRegion*>& DRoots,
-                                StoreManager::LiveSymbolsTy& LSymbols) {
+                                       SymbolReaper& SymReaper,
+                              llvm::SmallVectorImpl<const MemRegion*>& DRoots) {
   
   // Drop bindings for subexpressions.
   Env = RemoveSubExprBindings(Env);
@@ -120,19 +119,18 @@ EnvironmentManager::RemoveDeadBindings(Environment Env, Stmt* Loc,
        I != E; ++I) {
     Stmt* BlkExpr = I.getKey();
 
-    if (Liveness.isLive(Loc, BlkExpr)) {
+    if (SymReaper.isLive(Loc, BlkExpr)) {
       SVal X = I.getData();
 
       // If the block expr's value is a memory region, then mark that region.
       if (isa<loc::MemRegionVal>(X))
         DRoots.push_back(cast<loc::MemRegionVal>(X).getRegion());
 
-
       // Mark all symbols in the block expr's value.
       for (SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
-           SI != SE; ++SI) {
-        LSymbols.insert(*SI);
-      }
+           SI != SE; ++SI)
+        SymReaper.markLive(*SI);
+
     } else {
       // The block expr is dead.
       SVal X = I.getData();
diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp
index 80215f34e8..6a7f86b14b 100644
--- a/lib/Analysis/GRExprEngine.cpp
+++ b/lib/Analysis/GRExprEngine.cpp
@@ -211,18 +211,17 @@ void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
   if (BatchAuditor)
     Builder->setAuditor(BatchAuditor.get());
   
+    
   // Create the cleaned state.  
-  if (PurgeDead)
-    CleanedState = StateMgr.RemoveDeadBindings(EntryNode->getState(), 
-                                               CurrentStmt,
-                                               Liveness, DeadSymbols);
-  else
-    CleanedState = EntryNode->getState();
-  
+  SymbolReaper SymReaper(Liveness, SymMgr);  
+  CleanedState = PurgeDead ? StateMgr.RemoveDeadBindings(EntryNode->getState(), 
+                                                         CurrentStmt, SymReaper)
+                           : EntryNode->getState();
+
   // Process any special transfer function for dead symbols.
   NodeSet Tmp;
   
-  if (DeadSymbols.empty())
+  if (!SymReaper.hasDeadSymbols())
     Tmp.Add(EntryNode);
   else {
     SaveAndRestore<bool> OldSink(Builder->BuildSinks);
@@ -232,7 +231,7 @@ void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
     Builder->PurgingDeadSymbols = true;
     
     getTF().EvalDeadSymbols(Tmp, *this, *Builder, EntryNode, S, 
-                        CleanedState, DeadSymbols);
+                            CleanedState, SymReaper);
 
     if (!Builder->BuildSinks && !Builder->HasGeneratedNode)
       Tmp.Add(EntryNode);
diff --git a/lib/Analysis/GRState.cpp b/lib/Analysis/GRState.cpp
index 8e49ebb63d..ea6f7a03d6 100644
--- a/lib/Analysis/GRState.cpp
+++ b/lib/Analysis/GRState.cpp
@@ -34,9 +34,8 @@ GRStateManager::~GRStateManager() {
 
 const GRState*
 GRStateManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
-                                   const LiveVariables& Liveness,
-                                   DeadSymbolsTy& DSymbols) {  
-  
+                                   SymbolReaper& SymReaper) {
+
   // This code essentially performs a "mark-and-sweep" of the VariableBindings.
   // The roots are any Block-level exprs and Decls that our liveness algorithm
   // tells us are live.  We then see what Decls they may reference, and keep
@@ -44,19 +43,17 @@ GRStateManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
   // frequency of which this method is called should be experimented with
   // for optimum performance.
   llvm::SmallVector<const MemRegion*, 10> RegionRoots;
-  StoreManager::LiveSymbolsTy LSymbols;
   GRState NewState = *state;
 
-  NewState.Env = EnvMgr.RemoveDeadBindings(NewState.Env, Loc, Liveness,
-                                           RegionRoots, LSymbols);
+  NewState.Env = EnvMgr.RemoveDeadBindings(NewState.Env, Loc, SymReaper,
+                                           RegionRoots);
 
   // Clean up the store.
-  DSymbols.clear();
-  NewState.St = StoreMgr->RemoveDeadBindings(&NewState, Loc, Liveness,
-                                             RegionRoots, LSymbols, DSymbols);
+  NewState.St = StoreMgr->RemoveDeadBindings(&NewState, Loc, SymReaper,
+                                             RegionRoots);
 
   return ConstraintMgr->RemoveDeadBindings(getPersistentState(NewState),
-                                           LSymbols, DSymbols);
+                                           SymReaper);
 }
 
 const GRState* GRStateManager::Unbind(const GRState* St, Loc LV) {
diff --git a/lib/Analysis/RegionStore.cpp b/lib/Analysis/RegionStore.cpp
index 0c6fb8098b..7c42fec6ff 100644
--- a/lib/Analysis/RegionStore.cpp
+++ b/lib/Analysis/RegionStore.cpp
@@ -195,11 +195,8 @@ public:
   ///  It returns a new Store with these values removed, and populates LSymbols
   //   and DSymbols with the known set of live and dead symbols respectively.
   Store RemoveDeadBindings(const GRState* state, Stmt* Loc,
-                           const LiveVariables& Live,
-                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
-                           LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols);
-
-  void UpdateLiveSymbols(SVal X, LiveSymbolsTy& LSymbols);
+                           SymbolReaper& SymReaper,
+                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
 
   const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal InitVal);
 
@@ -696,15 +693,15 @@ const GRState* RegionStoreManager::setExtent(const GRState* St,
 }
 
 
-void RegionStoreManager::UpdateLiveSymbols(SVal X, LiveSymbolsTy& LSymbols) {
-  for (SVal::symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
-    LSymbols.insert(*SI);
+static void UpdateLiveSymbols(SVal X, SymbolReaper& SymReaper) {
+  for (SVal::symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end();SI!=SE;++SI)
+    SymReaper.markLive(*SI);
 }
 
 Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc, 
-                                             const LiveVariables& Live,
-                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
-                           LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols) {
+                                             SymbolReaper& SymReaper,
+                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
+{
 
   Store store = state->getStore();
   RegionBindingsTy B = GetRegionBindings(store);
@@ -732,7 +729,7 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
   for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
     const MemRegion* R = I.getKey();
     if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
-      if (Live.isLive(Loc, VR->getDecl()))
+      if (SymReaper.isLive(Loc, VR->getDecl()))
         RegionRoots.push_back(VR); // This is a live "root".
     }
     else {
@@ -748,7 +745,7 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
       // to also mark SuperR as a root (as it may not have a value directly
       // bound to it in the store).
       if (const VarRegion* VR = dyn_cast<VarRegion>(SuperR)) {
-        if (Live.isLive(Loc, VR->getDecl()))
+        if (SymReaper.isLive(Loc, VR->getDecl()))
           RegionRoots.push_back(VR); // This is a live "root".
       }
     } 
@@ -773,13 +770,13 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
     // Mark the symbol for any live SymbolicRegion as "live".  This means we
     // should continue to track that symbol.
     if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
-      LSymbols.insert(SymR->getSymbol());
+      SymReaper.markLive(SymR->getSymbol());
 
     // Get the data binding for R (if any).
     RegionBindingsTy::data_type* Xptr = B.lookup(R);
     if (Xptr) {
       SVal X = *Xptr;
-      UpdateLiveSymbols(X, LSymbols); // Update the set of live symbols.
+      UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols.
     
       // If X is a region, then add it the RegionRoots.
       if (loc::MemRegionVal* RegionX = dyn_cast<loc::MemRegionVal>(&X))
@@ -811,14 +808,12 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
     store = Remove(store, Loc::MakeVal(R));
 
     // Mark all non-live symbols that this region references as dead.
-    if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R)) {
-      SymbolRef Sym = SymR->getSymbol();
-      if (!LSymbols.count(Sym)) DSymbols.insert(Sym);
-    }
+    if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
+      SymReaper.maybeDead(SymR->getSymbol());
 
     SVal X = I.getData();
     SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
-    for (; SI != SE; ++SI) { if (!LSymbols.count(*SI)) DSymbols.insert(*SI); }
+    for (; SI != SE; ++SI) SymReaper.maybeDead(*SI);
   }
   
   return store;
diff --git a/lib/Analysis/SymbolManager.cpp b/lib/Analysis/SymbolManager.cpp
index f8f8555949..d0099e15fa 100644
--- a/lib/Analysis/SymbolManager.cpp
+++ b/lib/Analysis/SymbolManager.cpp
@@ -158,3 +158,21 @@ QualType SymbolData::getType(const SymbolManager& SymMgr) const {
 }
 
 SymbolManager::~SymbolManager() {}
+
+void SymbolReaper::markLive(SymbolRef sym) {
+  TheLiving = F.Add(TheLiving, sym);
+  TheDead = F.Remove(TheDead, sym);
+}
+
+bool SymbolReaper::maybeDead(SymbolRef sym) {
+  if (isLive(sym))
+    return false;
+  
+  TheDead = F.Add(TheDead, sym);
+  return true;
+}
+
+bool SymbolReaper::isLive(SymbolRef sym) {  
+  return TheLiving.contains(sym);
+}
+