static analyzer: Further reduce the analyzer's memory usage when analyzing sqlite3 by 7-10% by recylcing "uninteresting" ExplodedNodes.

The optimization involves eagerly pruning ExplodedNodes from the ExplodedGraph that contain
practically no difference between the predecessor and successor nodes.  For example, if
the state is different between a predecessor and a node, the node is left in.  Only for
the 'environment' component of the state do we not care if the ExplodedNodes are different.
This paves the way for future optimizations where we can reclaim the environment objects.

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

4 files changed, 121 insertions, 4 deletions

diff --git a/lib/StaticAnalyzer/Checkers/AnalysisConsumer.cpp b/lib/StaticAnalyzer/Checkers/AnalysisConsumer.cpp
index a20f995639..2b210a8804 100644
--- a/lib/StaticAnalyzer/Checkers/AnalysisConsumer.cpp
+++ b/lib/StaticAnalyzer/Checkers/AnalysisConsumer.cpp
@@ -194,7 +194,8 @@ public:
                                   Opts.PurgeDead, Opts.EagerlyAssume,
                                   Opts.TrimGraph, Opts.InlineCall,
                                   Opts.UnoptimizedCFG, Opts.CFGAddImplicitDtors,
-                                  Opts.CFGAddInitializers));
+                                  Opts.CFGAddInitializers,
+                                  Opts.EagerlyTrimEGraph));
   }
 
   virtual void HandleTranslationUnit(ASTContext &C);
diff --git a/lib/StaticAnalyzer/Checkers/ExprEngine.cpp b/lib/StaticAnalyzer/Checkers/ExprEngine.cpp
index cadbca6b3d..e2ad17e590 100644
--- a/lib/StaticAnalyzer/Checkers/ExprEngine.cpp
+++ b/lib/StaticAnalyzer/Checkers/ExprEngine.cpp
@@ -338,6 +338,11 @@ ExprEngine::ExprEngine(AnalysisManager &mgr, TransferFuncs *tf)
   // FIXME: Eventually remove the TF object entirely.
   TF->RegisterChecks(*this);
   TF->RegisterPrinters(getStateManager().Printers);
+  
+  if (mgr.shouldEagerlyTrimExplodedGraph()) {
+    // Enable eager node reclaimation when constructing the ExplodedGraph.  
+    G.enableNodeReclamation();
+  }
 }
 
 ExprEngine::~ExprEngine() {
@@ -573,6 +578,8 @@ void ExprEngine::processCFGElement(const CFGElement E,
 }
 
 void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) {
+  // Reclaim any unnecessary nodes in the ExplodedGraph.
+  G.reclaimRecentlyAllocatedNodes();
   // Recycle any unused states in the GRStateManager.
   StateMgr.recycleUnusedStates();
   
diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp
index 13cca35aac..69aa664f9c 100644
--- a/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -783,7 +783,8 @@ void CallEnterNodeBuilder::generateNode(const GRState *state) {
                          OldMgr.shouldInlineCall(),
                      OldMgr.getAnalysisContextManager().getUseUnoptimizedCFG(),
                      OldMgr.getAnalysisContextManager().getAddImplicitDtors(),
-                     OldMgr.getAnalysisContextManager().getAddInitializers());
+                     OldMgr.getAnalysisContextManager().getAddInitializers(),
+                     OldMgr.shouldEagerlyTrimExplodedGraph());
     llvm::OwningPtr<TransferFuncs> TF(MakeCFRefCountTF(AMgr.getASTContext(),
                                                          /* GCEnabled */ false,
                                                         AMgr.getLangOptions()));
diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index 4c4612fab5..9e8566056f 100644
--- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/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);