1 files changed, 110 insertions, 2 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index 4c4612fab5e..9e8566056f4 100644
--- a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
@@ -41,6 +41,94 @@ void ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) {
 }
 
 //===----------------------------------------------------------------------===//
+// Cleanup.
+//===----------------------------------------------------------------------===//
+
+typedef std::vector<ExplodedNode*> NodeList;
+static inline NodeList*& getNodeList(void *&p) { return (NodeList*&) p; }
+
+ExplodedGraph::~ExplodedGraph() {
+  if (reclaimNodes) {
+    delete getNodeList(recentlyAllocatedNodes);
+    delete getNodeList(freeNodes);
+  }
+}
+
+//===----------------------------------------------------------------------===//
+// Node reclamation.
+//===----------------------------------------------------------------------===//
+
+void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
+  if (!recentlyAllocatedNodes)
+    return;
+  NodeList &nl = *getNodeList(recentlyAllocatedNodes);
+ 
+  // Reclaimn all nodes that match *all* the following criteria:
+  //
+  // (1) 1 predecessor (that has one successor)
+  // (2) 1 successor (that has one predecessor)
+  // (3) The ProgramPoint is for a PostStmt.
+  // (4) There is no 'tag' for the ProgramPoint.
+  // (5) The 'store' is the same as the predecessor.
+  // (6) The 'GDM' is the same as the predecessor.
+  // (7) The LocationContext is the same as the predecessor.
+  // (8) The PostStmt is for a non-CFGElement expression.
+  
+  for (NodeList::iterator i = nl.begin(), e = nl.end() ; i != e; ++i) {
+    ExplodedNode *node = *i;
+    
+    // Conditions 1 and 2.
+    if (node->pred_size() != 1 || node->succ_size() != 1)
+      continue;
+
+    ExplodedNode *pred = *(node->pred_begin());
+    if (pred->succ_size() != 1)
+      continue;
+
+    ExplodedNode *succ = *(node->succ_begin());
+    if (succ->pred_size() != 1)
+      continue;
+
+    // Condition 3.
+    ProgramPoint progPoint = node->getLocation();
+    if (!isa<PostStmt>(progPoint))
+      continue;
+
+    // Condition 4.
+    PostStmt ps = cast<PostStmt>(progPoint);
+    if (ps.getTag() || isa<PostStmtCustom>(ps))
+      continue;
+
+    if (isa<BinaryOperator>(ps.getStmt()))
+      continue;
+
+    // Conditions 5, 6, and 7.
+    const GRState *state = node->getState();
+    const GRState *pred_state = pred->getState();    
+    if (state->St != pred_state->St || state->GDM != pred_state->GDM ||
+        progPoint.getLocationContext() != pred->getLocationContext())
+      continue;
+
+    // Condition 8.
+    if (node->getCFG().isBlkExpr(ps.getStmt()))
+      continue;
+    
+    // If we reach here, we can remove the node.  This means:
+    // (a) changing the predecessors successor to the successor of this node
+    // (b) changing the successors predecessor to the predecessor of this node
+    // (c) Putting 'node' onto freeNodes.
+    pred->replaceSuccessor(succ);
+    succ->replacePredecessor(pred);
+    if (!freeNodes)
+      freeNodes = new NodeList();
+    getNodeList(freeNodes)->push_back(node);
+    Nodes.RemoveNode(node);
+  }
+  
+  nl.clear();
+}
+
+//===----------------------------------------------------------------------===//
 // ExplodedNode.
 //===----------------------------------------------------------------------===//
 
@@ -57,6 +145,12 @@ void ExplodedNode::addPredecessor(ExplodedNode* V, ExplodedGraph &G) {
 #endif
 }
 
+void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
+  assert(getKind() == Size1);
+  P = reinterpret_cast<uintptr_t>(node);
+  assert(getKind() == Size1);
+}
+
 void ExplodedNode::NodeGroup::addNode(ExplodedNode* N, ExplodedGraph &G) {
   assert((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
   assert(!getFlag());
@@ -129,10 +223,24 @@ ExplodedNode *ExplodedGraph::getNode(const ProgramPoint& L,
   NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
 
   if (!V) {
-    // Allocate a new node.
-    V = (NodeTy*) getAllocator().Allocate<NodeTy>();
+    if (freeNodes && !getNodeList(freeNodes)->empty()) {
+      NodeList *nl = getNodeList(freeNodes);
+      V = nl->back();
+      nl->pop_back();
+    }
+    else {
+      // Allocate a new node.
+      V = (NodeTy*) getAllocator().Allocate<NodeTy>();
+    }
+
     new (V) NodeTy(L, State);
 
+    if (reclaimNodes) {
+      if (!recentlyAllocatedNodes)
+        recentlyAllocatedNodes = new NodeList();
+      getNodeList(recentlyAllocatedNodes)->push_back(V);
+    }
+
     // Insert the node into the node set and return it.
     Nodes.InsertNode(V, InsertPos);