1 files changed, 71 insertions, 0 deletions
diff --git a/Analysis/ValueState.cpp b/Analysis/ValueState.cpp
index d191623dd8..55451a959e 100644
--- a/Analysis/ValueState.cpp
+++ b/Analysis/ValueState.cpp
@@ -31,6 +31,77 @@ const llvm::APSInt* ValueState::getSymVal(SymbolID sym) const {
   return T ? T->getValue().second : NULL;  
 }
 
+ValueState
+ValueStateManager::RemoveDeadBindings(ValueState St, Stmt* Loc,
+                                      const LiveVariables& Liveness) {  
+  
+  // 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
+  // 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.
+  
+  llvm::SmallVector<ValueDecl*, 10> WList;
+  
+  for (StateTy::vb_iterator I = St.begin(), E = St.end(); I!=E ; ++I) {
+    
+    // Remove old bindings for subexpressions.
+    if (I.getKey().isSubExpr()) {
+      St = Remove(St, I.getKey());
+      continue;
+    }
+    
+    if (I.getKey().isBlkExpr()) {
+      if (Liveness.isLive(Loc, cast<Stmt>(I.getKey()))) {
+        if (isa<lval::DeclVal>(I.getData())) {
+          lval::DeclVal LV = cast<lval::DeclVal>(I.getData());
+          WList.push_back(LV.getDecl());
+        }
+      }
+      else
+        St = Remove(St, I.getKey());
+      
+      continue;
+    }
+    
+    assert (I.getKey().isDecl());
+    
+    if (VarDecl* V = dyn_cast<VarDecl>(cast<ValueDecl>(I.getKey())))
+      if (Liveness.isLive(Loc, V))
+        WList.push_back(V);
+  }
+  
+  llvm::SmallPtrSet<ValueDecl*, 10> Marked;
+  
+  while (!WList.empty()) {
+    ValueDecl* V = WList.back();
+    WList.pop_back();
+    
+    if (Marked.count(V))
+      continue;
+    
+    Marked.insert(V);
+    
+    if (V->getType()->isPointerType()) {
+      const LValue& LV = cast<LValue>(GetValue(St, lval::DeclVal(V)));
+      
+      if (!isa<lval::DeclVal>(LV))
+        continue;
+      
+      const lval::DeclVal& LVD = cast<lval::DeclVal>(LV);
+      WList.push_back(LVD.getDecl());
+    }    
+  }
+  
+  for (StateTy::vb_iterator I = St.begin(), E = St.end(); I!=E ; ++I)
+    if (I.getKey().isDecl())
+      if (VarDecl* V = dyn_cast<VarDecl>(cast<ValueDecl>(I.getKey())))
+        if (!Marked.count(V))
+          St = Remove(St, V);
+  
+  return St;
+}
 
 
 RValue ValueStateManager::GetValue(const StateTy& St, const LValue& LV,