Move ExplodedNode reclaimation out of ExprEngine and into CoreEngine. Also have it based on adding predecessors/successors, not node allocation. No measurable performance change.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@150720 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index 1c81af9..785c286 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -25,6 +25,7 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/DenseSet.h"
#include "llvm/Support/Allocator.h"
#include "llvm/ADT/OwningPtr.h"
#include "llvm/ADT/GraphTraits.h"
@@ -240,6 +241,7 @@
class ExplodedGraph {
protected:
friend class CoreEngine;
+ friend class ExplodedNode;
// Type definitions.
typedef std::vector<ExplodedNode *> NodeVector;
@@ -265,16 +267,13 @@
unsigned NumNodes;
/// A list of recently allocated nodes that can potentially be recycled.
- NodeVector ChangedNodes;
+ llvm::DenseSet<ExplodedNode*> ChangedNodes;
/// A list of nodes that can be reused.
NodeVector FreeNodes;
/// A flag that indicates whether nodes should be recycled.
bool reclaimNodes;
-
- /// Counter to determine when to reclaim nodes.
- unsigned reclaimCounter;
public:
@@ -361,12 +360,12 @@
llvm::DenseMap<const void*, const void*> *InverseMap) const;
/// Enable tracking of recently allocated nodes for potential reclamation
- /// when calling reclaimRecentlyAllocatedNodes().
+ /// when calling reclaimChangedNodes().
void enableNodeReclamation() { reclaimNodes = true; }
/// Reclaim "uninteresting" nodes created since the last time this method
/// was called.
- void reclaimRecentlyAllocatedNodes();
+ void reclaimChangedNodes();
private:
bool shouldCollect(const ExplodedNode *node);
diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp
index e7c3d2a..764c540 100644
--- a/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -192,6 +192,7 @@
--Steps;
}
+ getGraph().reclaimChangedNodes();
const WorkListUnit& WU = WList->dequeue();
// Set the current block counter.
diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index 0dcbe1f..5289211 100644
--- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
@@ -45,10 +45,8 @@
// Cleanup.
//===----------------------------------------------------------------------===//
-static const unsigned CounterTop = 1000;
-
ExplodedGraph::ExplodedGraph()
- : NumNodes(0), reclaimNodes(false), reclaimCounter(CounterTop) {}
+ : NumNodes(0), reclaimNodes(false) {}
ExplodedGraph::~ExplodedGraph() {}
@@ -127,19 +125,12 @@
node->~ExplodedNode();
}
-void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
+void ExplodedGraph::reclaimChangedNodes() {
if (ChangedNodes.empty())
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;
-
- for (NodeVector::iterator it = ChangedNodes.begin(), et = ChangedNodes.end();
+ for (llvm::DenseSet<ExplodedNode*>::iterator it =
+ ChangedNodes.begin(), et = ChangedNodes.end();
it != et; ++it) {
ExplodedNode *node = *it;
if (shouldCollect(node))
@@ -160,6 +151,12 @@
assert (!V->isSink());
Preds.addNode(V, G);
V->Succs.addNode(this, G);
+ if (G.reclaimNodes) {
+ if (Succs.size() == 1 && Preds.size() == 1)
+ G.ChangedNodes.insert(this);
+ if (V->Succs.size() == 1 && V->Preds.size() == 1)
+ G.ChangedNodes.insert(V);
+ }
#ifndef NDEBUG
if (NodeAuditor) NodeAuditor->AddEdge(V, this);
#endif
@@ -256,9 +253,6 @@
new (V) NodeTy(L, State, IsSink);
- if (reclaimNodes)
- ChangedNodes.push_back(V);
-
// Insert the node into the node set and return it.
Nodes.InsertNode(V, InsertPos);
++NumNodes;
diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp
index b0ed181..c65c38b 100644
--- a/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -238,10 +238,7 @@
}
void ExprEngine::ProcessStmt(const CFGStmt S,
- ExplodedNode *Pred) {
- // Reclaim any unnecessary nodes in the ExplodedGraph.
- G.reclaimRecentlyAllocatedNodes();
-
+ ExplodedNode *Pred) {
currentStmt = S.getStmt();
PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
currentStmt->getLocStart(),