Reduce peak memory usage of the static analyzer on sqlite3 (when using inlining) by 30%.

This is accomplished by periodically reclaiming nodes in the graph.  This was an optimization
done before the CFG was linearized, but the CFG linearization destroyed that optimization since each
freshly created node couldn't be reclaimed and we only looked at a window of nodes created between
each ProcessStmt.  This optimization can be reclaimed my merely expanding the window to N number of nodes.

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

2 files changed, 27 insertions, 6 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index dcaa9e5a2d..76308fa2f3 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -275,6 +275,9 @@ protected:
   
   /// A flag that indicates whether nodes should be recycled.
   bool reclaimNodes;
+  
+  /// Counter to determine when to reclaim nodes.
+  unsigned reclaimCounter;
 
 public:
 
@@ -302,9 +305,7 @@ public:
     return V;
   }
 
-  ExplodedGraph()
-    : NumNodes(0), recentlyAllocatedNodes(0),
-      freeNodes(0), reclaimNodes(false) {}
+  ExplodedGraph();
 
   ~ExplodedGraph();
   
diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index 160925b08f..bb0abfa965 100644
--- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
@@ -15,6 +15,7 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/AST/Stmt.h"
+#include "clang/AST/ParentMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
@@ -47,6 +48,13 @@ void ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) {
 typedef std::vector<ExplodedNode*> NodeList;
 static inline NodeList*& getNodeList(void *&p) { return (NodeList*&) p; }
 
+static const unsigned CounterTop = 1000;
+
+ExplodedGraph::ExplodedGraph()
+  : NumNodes(0), recentlyAllocatedNodes(0),
+    freeNodes(0), reclaimNodes(false),
+    reclaimCounter(CounterTop) {}
+
 ExplodedGraph::~ExplodedGraph() {
   if (reclaimNodes) {
     delete getNodeList(recentlyAllocatedNodes);
@@ -61,6 +69,15 @@ ExplodedGraph::~ExplodedGraph() {
 void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
   if (!recentlyAllocatedNodes)
     return;
+
+  // Only periodically relcaim nodes so that we can build up a set of
+  // nodes that meet the reclamation criteria.  Freshly created nodes
+  // by definition have no successor, and thus cannot be reclaimed (see below).
+  assert(reclaimCounter > 0);
+  if (--reclaimCounter != 0)
+    return;
+  reclaimCounter = CounterTop;
+  
   NodeList &nl = *getNodeList(recentlyAllocatedNodes);
  
   // Reclaimn all nodes that match *all* the following criteria:
@@ -72,7 +89,7 @@ void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
   // (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.
+  // (8) The PostStmt is for a non-consumed Stmt or Expr.
   
   for (NodeList::iterator i = nl.begin(), e = nl.end() ; i != e; ++i) {
     ExplodedNode *node = *i;
@@ -110,8 +127,11 @@ void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
       continue;
 
     // Condition 8.
-    if (node->getCFG().isBlkExpr(ps.getStmt()))
-      continue;
+    if (const Expr *Ex = dyn_cast<Expr>(ps.getStmt())) {
+      ParentMap &PM = progPoint.getLocationContext()->getParentMap();
+      if (!PM.isConsumedExpr(Ex))
+        continue;
+    }
     
     // If we reach here, we can remove the node.  This means:
     // (a) changing the predecessors successor to the successor of this node