diff options
| -rw-r--r-- | include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h | 11 | ||||
| -rw-r--r-- | lib/StaticAnalyzer/Core/CoreEngine.cpp | 1 | ||||
| -rw-r--r-- | lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 26 | ||||
| -rw-r--r-- | lib/StaticAnalyzer/Core/ExprEngine.cpp | 5 |
4 files changed, 26 insertions, 17 deletions
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index 785c286137..1c81af9586 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -25,7 +25,6 @@ #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" @@ -241,7 +240,6 @@ public: class ExplodedGraph { protected: friend class CoreEngine; - friend class ExplodedNode; // Type definitions. typedef std::vector<ExplodedNode *> NodeVector; @@ -267,13 +265,16 @@ protected: unsigned NumNodes; /// A list of recently allocated nodes that can potentially be recycled. - llvm::DenseSet<ExplodedNode*> ChangedNodes; + NodeVector 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: @@ -360,12 +361,12 @@ public: llvm::DenseMap<const void*, const void*> *InverseMap) const; /// Enable tracking of recently allocated nodes for potential reclamation - /// when calling reclaimChangedNodes(). + /// when calling reclaimRecentlyAllocatedNodes(). void enableNodeReclamation() { reclaimNodes = true; } /// Reclaim "uninteresting" nodes created since the last time this method /// was called. - void reclaimChangedNodes(); + void reclaimRecentlyAllocatedNodes(); private: bool shouldCollect(const ExplodedNode *node); diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp index 764c540d0e..e7c3d2a3b3 100644 --- a/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -192,7 +192,6 @@ bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, --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 52892116a2..0dcbe1ff4a 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -45,8 +45,10 @@ void ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) { // Cleanup. //===----------------------------------------------------------------------===// +static const unsigned CounterTop = 1000; + ExplodedGraph::ExplodedGraph() - : NumNodes(0), reclaimNodes(false) {} + : NumNodes(0), reclaimNodes(false), reclaimCounter(CounterTop) {} ExplodedGraph::~ExplodedGraph() {} @@ -125,12 +127,19 @@ void ExplodedGraph::collectNode(ExplodedNode *node) { node->~ExplodedNode(); } -void ExplodedGraph::reclaimChangedNodes() { +void ExplodedGraph::reclaimRecentlyAllocatedNodes() { if (ChangedNodes.empty()) return; - for (llvm::DenseSet<ExplodedNode*>::iterator it = - ChangedNodes.begin(), et = ChangedNodes.end(); + // 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(); it != et; ++it) { ExplodedNode *node = *it; if (shouldCollect(node)) @@ -151,12 +160,6 @@ void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) { 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 @@ -253,6 +256,9 @@ ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, 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 c65c38ba2d..b0ed1815f9 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -238,7 +238,10 @@ static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, } void ExprEngine::ProcessStmt(const CFGStmt S, - ExplodedNode *Pred) { + ExplodedNode *Pred) { + // Reclaim any unnecessary nodes in the ExplodedGraph. + G.reclaimRecentlyAllocatedNodes(); + currentStmt = S.getStmt(); PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(), currentStmt->getLocStart(), |