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
diff --git a/lib/Analysis/BasicConstraintManager.cpp b/lib/Analysis/BasicConstraintManager.cpp
index d9d97c6..450c38f 100644
--- a/lib/Analysis/BasicConstraintManager.cpp
+++ b/lib/Analysis/BasicConstraintManager.cpp
@@ -82,9 +82,8 @@
   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 @@
 
 /// 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 @@
 
   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 b223114..7315ec7 100644
--- a/lib/Analysis/BasicStore.cpp
+++ b/lib/Analysis/BasicStore.cpp
@@ -88,10 +88,10 @@
   /// 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::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 @@
   
   // 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 @@
     
     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 @@
         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 @@
       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 c72d2a3..4731921 100644
--- a/lib/Analysis/CFRefCount.cpp
+++ b/lib/Analysis/CFRefCount.cpp
@@ -1367,9 +1367,9 @@
                                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 @@
                                  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 5f9e97e..c4ed349 100644
--- a/lib/Analysis/Environment.cpp
+++ b/lib/Analysis/Environment.cpp
@@ -108,9 +108,8 @@
 
 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 @@
        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 80215f3..6a7f86b 100644
--- a/lib/Analysis/GRExprEngine.cpp
+++ b/lib/Analysis/GRExprEngine.cpp
@@ -211,18 +211,17 @@
   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 @@
     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 8e49ebb..ea6f7a0 100644
--- a/lib/Analysis/GRState.cpp
+++ b/lib/Analysis/GRState.cpp
@@ -34,9 +34,8 @@
 
 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 @@
   // 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 0c6fb80..7c42fec 100644
--- a/lib/Analysis/RegionStore.cpp
+++ b/lib/Analysis/RegionStore.cpp
@@ -195,11 +195,8 @@
   ///  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 @@
 }
 
 
-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 @@
   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 @@
       // 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 @@
     // 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 = 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 f8f8555..d0099e1 100644
--- a/lib/Analysis/SymbolManager.cpp
+++ b/lib/Analysis/SymbolManager.cpp
@@ -158,3 +158,21 @@
 }
 
 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);
+}
+