summaryrefslogtreecommitdiffstats
path: root/clang
diff options
context:
space:
mode:
Diffstat (limited to 'clang')
-rw-r--r--clang/include/clang/Driver/CC1Options.td2
-rw-r--r--clang/include/clang/Frontend/AnalyzerOptions.h2
-rw-r--r--clang/include/clang/StaticAnalyzer/PathSensitive/AnalysisManager.h9
-rw-r--r--clang/include/clang/StaticAnalyzer/PathSensitive/ExplodedGraph.h31
-rw-r--r--clang/include/clang/StaticAnalyzer/PathSensitive/GRState.h1
-rw-r--r--clang/lib/Frontend/CompilerInvocation.cpp1
-rw-r--r--clang/lib/StaticAnalyzer/Checkers/AnalysisConsumer.cpp3
-rw-r--r--clang/lib/StaticAnalyzer/Checkers/ExprEngine.cpp7
-rw-r--r--clang/lib/StaticAnalyzer/Core/CoreEngine.cpp3
-rw-r--r--clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp112
10 files changed, 161 insertions, 10 deletions
diff --git a/clang/include/clang/Driver/CC1Options.td b/clang/include/clang/Driver/CC1Options.td
index 813ee5bcc37..097a0301e14 100644
--- a/clang/include/clang/Driver/CC1Options.td
+++ b/clang/include/clang/Driver/CC1Options.td
@@ -107,6 +107,8 @@ def analyzer_eagerly_assume : Flag<"-analyzer-eagerly-assume">,
HelpText<"Eagerly assume the truth/falseness of some symbolic constraints">;
def analyzer_no_purge_dead : Flag<"-analyzer-no-purge-dead">,
HelpText<"Don't remove dead symbols, bindings, and constraints before processing a statement">;
+def analyzer_no_eagerly_trim_egraph : Flag<"-analyzer-no-eagerly-trim-egraph">,
+ HelpText<"Don't eagerly remove uninteresting ExplodedNodes from the ExplodedGraph">;
def trim_egraph : Flag<"-trim-egraph">,
HelpText<"Only show error-related paths in the analysis graph">;
def analyzer_viz_egraph_graphviz : Flag<"-analyzer-viz-egraph-graphviz">,
diff --git a/clang/include/clang/Frontend/AnalyzerOptions.h b/clang/include/clang/Frontend/AnalyzerOptions.h
index 8704fff6873..32075c760c9 100644
--- a/clang/include/clang/Frontend/AnalyzerOptions.h
+++ b/clang/include/clang/Frontend/AnalyzerOptions.h
@@ -80,6 +80,7 @@ public:
unsigned UnoptimizedCFG : 1;
unsigned CFGAddImplicitDtors : 1;
unsigned CFGAddInitializers : 1;
+ unsigned EagerlyTrimEGraph : 1;
public:
AnalyzerOptions() {
@@ -103,6 +104,7 @@ public:
UnoptimizedCFG = 0;
CFGAddImplicitDtors = 0;
CFGAddInitializers = 0;
+ EagerlyTrimEGraph = 0;
}
};
diff --git a/clang/include/clang/StaticAnalyzer/PathSensitive/AnalysisManager.h b/clang/include/clang/StaticAnalyzer/PathSensitive/AnalysisManager.h
index ba86ed8ba2e..2ecb19e5271 100644
--- a/clang/include/clang/StaticAnalyzer/PathSensitive/AnalysisManager.h
+++ b/clang/include/clang/StaticAnalyzer/PathSensitive/AnalysisManager.h
@@ -69,6 +69,7 @@ class AnalysisManager : public BugReporterData {
bool EagerlyAssume;
bool TrimGraph;
bool InlineCall;
+ bool EagerlyTrimEGraph;
public:
AnalysisManager(ASTContext &ctx, Diagnostic &diags,
@@ -79,14 +80,16 @@ public:
unsigned maxnodes, unsigned maxvisit,
bool vizdot, bool vizubi, bool purge, bool eager, bool trim,
bool inlinecall, bool useUnoptimizedCFG,
- bool addImplicitDtors, bool addInitializers)
+ bool addImplicitDtors, bool addInitializers,
+ bool eagerlyTrimEGraph)
: AnaCtxMgr(useUnoptimizedCFG, addImplicitDtors, addInitializers),
Ctx(ctx), Diags(diags), LangInfo(lang), PD(pd),
CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr),Idxer(idxer),
AScope(ScopeDecl), MaxNodes(maxnodes), MaxVisit(maxvisit),
VisualizeEGDot(vizdot), VisualizeEGUbi(vizubi), PurgeDead(purge),
- EagerlyAssume(eager), TrimGraph(trim), InlineCall(inlinecall) {}
+ EagerlyAssume(eager), TrimGraph(trim), InlineCall(inlinecall),
+ EagerlyTrimEGraph(eagerlyTrimEGraph) {}
~AnalysisManager() { FlushDiagnostics(); }
@@ -146,6 +149,8 @@ public:
return VisualizeEGDot || VisualizeEGUbi;
}
+ bool shouldEagerlyTrimExplodedGraph() const { return EagerlyTrimEGraph; }
+
bool shouldTrimGraph() const { return TrimGraph; }
bool shouldPurgeDead() const { return PurgeDead; }
diff --git a/clang/include/clang/StaticAnalyzer/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/PathSensitive/ExplodedGraph.h
index 0d6044b5d2b..8c65608c7fe 100644
--- a/clang/include/clang/StaticAnalyzer/PathSensitive/ExplodedGraph.h
+++ b/clang/include/clang/StaticAnalyzer/PathSensitive/ExplodedGraph.h
@@ -75,7 +75,7 @@ class ExplodedNode : public llvm::FoldingSetNode {
ExplodedNode *getNode() const {
return reinterpret_cast<ExplodedNode*>(getPtr());
}
-
+
public:
NodeGroup() : P(0) {}
@@ -89,6 +89,8 @@ class ExplodedNode : public llvm::FoldingSetNode {
void addNode(ExplodedNode* N, ExplodedGraph &G);
+ void replaceNode(ExplodedNode *node);
+
void setFlag() {
assert(P == 0);
P = AuxFlag;
@@ -208,6 +210,10 @@ public:
};
static void SetAuditor(Auditor* A);
+
+private:
+ void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
+ void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
};
// FIXME: Is this class necessary?
@@ -249,6 +255,15 @@ protected:
/// NumNodes - The number of nodes in the graph.
unsigned NumNodes;
+
+ /// A list of recently allocated nodes that can potentially be recycled.
+ void *recentlyAllocatedNodes;
+
+ /// A list of nodes that can be reused.
+ void *freeNodes;
+
+ /// A flag that indicates whether nodes should be recycled.
+ bool reclaimNodes;
public:
/// getNode - Retrieve the node associated with a (Location,State) pair,
@@ -275,10 +290,10 @@ public:
return V;
}
- ExplodedGraph() : NumNodes(0) {}
-
- ~ExplodedGraph() {}
+ ExplodedGraph() : NumNodes(0), recentlyAllocatedNodes(0), freeNodes(0) {}
+ ~ExplodedGraph();
+
unsigned num_roots() const { return Roots.size(); }
unsigned num_eops() const { return EndNodes.size(); }
@@ -332,6 +347,14 @@ public:
const ExplodedNode* const * NEnd,
InterExplodedGraphMap *M,
llvm::DenseMap<const void*, const void*> *InverseMap) const;
+
+ /// Enable tracking of recently allocated nodes for potential reclamation
+ /// when calling reclaimRecentlyAllocatedNodes().
+ void enableNodeReclamation() { reclaimNodes = true; }
+
+ /// Reclaim "uninteresting" nodes created since the last time this method
+ /// was called.
+ void reclaimRecentlyAllocatedNodes();
};
class ExplodedNodeSet {
diff --git a/clang/include/clang/StaticAnalyzer/PathSensitive/GRState.h b/clang/include/clang/StaticAnalyzer/PathSensitive/GRState.h
index 5a87cb4fb70..d06ffd644a2 100644
--- a/clang/include/clang/StaticAnalyzer/PathSensitive/GRState.h
+++ b/clang/include/clang/StaticAnalyzer/PathSensitive/GRState.h
@@ -78,6 +78,7 @@ private:
void operator=(const GRState& R) const; // Do not implement.
friend class GRStateManager;
+ friend class ExplodedGraph;
llvm::PointerIntPair<GRStateManager *, 1, bool> stateMgr;
Environment Env; // Maps a Stmt to its current SVal.
diff --git a/clang/lib/Frontend/CompilerInvocation.cpp b/clang/lib/Frontend/CompilerInvocation.cpp
index e90cf8ddd2f..6fc73738223 100644
--- a/clang/lib/Frontend/CompilerInvocation.cpp
+++ b/clang/lib/Frontend/CompilerInvocation.cpp
@@ -878,6 +878,7 @@ static void ParseAnalyzerArgs(AnalyzerOptions &Opts, ArgList &Args,
Opts.TrimGraph = Args.hasArg(OPT_trim_egraph);
Opts.MaxNodes = Args.getLastArgIntValue(OPT_analyzer_max_nodes, 150000,Diags);
Opts.MaxLoop = Args.getLastArgIntValue(OPT_analyzer_max_loop, 4, Diags);
+ Opts.EagerlyTrimEGraph = !Args.hasArg(OPT_analyzer_no_eagerly_trim_egraph);
Opts.InlineCall = Args.hasArg(OPT_analyzer_inline_call);
Opts.IdempotentOps = Args.hasArg(OPT_analysis_WarnIdempotentOps);
Opts.ObjCSelfInitCheck = Args.hasArg(OPT_analysis_WarnObjCSelfInit);
diff --git a/clang/lib/StaticAnalyzer/Checkers/AnalysisConsumer.cpp b/clang/lib/StaticAnalyzer/Checkers/AnalysisConsumer.cpp
index a20f995639d..2b210a88047 100644
--- a/clang/lib/StaticAnalyzer/Checkers/AnalysisConsumer.cpp
+++ b/clang/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/clang/lib/StaticAnalyzer/Checkers/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Checkers/ExprEngine.cpp
index cadbca6b3d0..e2ad17e590b 100644
--- a/clang/lib/StaticAnalyzer/Checkers/ExprEngine.cpp
+++ b/clang/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/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
index 13cca35aacf..69aa664f9c1 100644
--- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/clang/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/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);
OpenPOWER on IntegriCloud