From c9963132736782d0c9178c744b3e2307cfb98a08 Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Sat, 16 Mar 2013 01:07:53 +0000 Subject: [analyzer] Eliminate InterExplodedGraphMap class and NodeBackMap typedef. ...in favor of this typedef: typedef llvm::DenseMap InterExplodedGraphMap; Use this everywhere the previous class and typedef were used. Took the opportunity to ArrayRef-ize ExplodedGraph::trim while I'm at it. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177215 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 52 +++++++++---------------------- 1 file changed, 14 insertions(+), 38 deletions(-) (limited to 'lib/StaticAnalyzer/Core/ExplodedGraph.cpp') diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index 2210b4e2d7..ca466d8907 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -331,45 +331,31 @@ ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, return V; } -std::pair -ExplodedGraph::Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd, - llvm::DenseMap *InverseMap) const { +ExplodedGraph * +ExplodedGraph::trim(ArrayRef Sinks, + InterExplodedGraphMap *ForwardMap, + InterExplodedGraphMap *InverseMap) const{ - if (NBeg == NEnd) - return std::make_pair((ExplodedGraph*) 0, - (InterExplodedGraphMap*) 0); - - assert (NBeg < NEnd); - - OwningPtr M(new InterExplodedGraphMap()); - - ExplodedGraph* G = TrimInternal(NBeg, NEnd, M.get(), InverseMap); - - return std::make_pair(static_cast(G), M.take()); -} - -ExplodedGraph* -ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, - const ExplodedNode* const* EndSources, - InterExplodedGraphMap* M, - llvm::DenseMap *InverseMap) const { + if (Nodes.empty()) + return 0; typedef llvm::DenseSet Pass1Ty; Pass1Ty Pass1; - typedef llvm::DenseMap Pass2Ty; - Pass2Ty& Pass2 = M->M; + typedef InterExplodedGraphMap Pass2Ty; + InterExplodedGraphMap Pass2Scratch; + Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch; SmallVector WL1, WL2; // ===- Pass 1 (reverse DFS) -=== - for (const ExplodedNode* const* I = BeginSources; I != EndSources; ++I) { + for (ArrayRef::iterator I = Sinks.begin(), E = Sinks.end(); + I != E; ++I) { if (*I) WL1.push_back(*I); } - // Process the first worklist until it is empty. Because it is a std::list - // it acts like a FIFO queue. + // Process the first worklist until it is empty. while (!WL1.empty()) { const ExplodedNode *N = WL1.back(); WL1.pop_back(); @@ -432,7 +418,7 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, if (PI == Pass2.end()) continue; - NewN->addPredecessor(PI->second, *G); + NewN->addPredecessor(const_cast(PI->second), *G); } // In the case that some of the intended successors of NewN have already @@ -443,7 +429,7 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, I != E; ++I) { Pass2Ty::iterator PI = Pass2.find(*I); if (PI != Pass2.end()) { - PI->second->addPredecessor(NewN, *G); + const_cast(PI->second)->addPredecessor(NewN, *G); continue; } @@ -456,13 +442,3 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, return G; } -void InterExplodedGraphMap::anchor() { } - -ExplodedNode* -InterExplodedGraphMap::getMappedNode(const ExplodedNode *N) const { - llvm::DenseMap::const_iterator I = - M.find(N); - - return I == M.end() ? 0 : I->second; -} - -- cgit v1.2.3-70-g09d2 From f4cf6b10f863b9bc716a09b2b2a8c497dcc6aa9b Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Wed, 20 Mar 2013 00:35:31 +0000 Subject: [analyzer] Break cycles (optionally) when trimming an ExplodedGraph. Having a trimmed graph with no cycles (a DAG) is much more convenient for trying to find shortest paths, which is exactly what BugReporter needs to do. Part of the performance work for . git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177468 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h | 6 +++++- lib/StaticAnalyzer/Core/BugReporter.cpp | 3 ++- lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 19 +++++++++++++++++-- 3 files changed, 24 insertions(+), 4 deletions(-) (limited to 'lib/StaticAnalyzer/Core/ExplodedGraph.cpp') diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index 5211916407..208c12bd74 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -363,12 +363,16 @@ public: /// /// \param Nodes The nodes which must appear in the final graph. Presumably /// these are end-of-path nodes (i.e. they have no successors). + /// \param BreakCycles Whether or not the trimmed graph should make an effort + /// to eliminate cycles. Note that this may result in some + /// unnecessary nodes being included in the final graph + /// (i.e. nodes that would have only appeared in a cycle). /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in /// the returned graph. /// \param[out] InverseMap An optional map from nodes in the returned graph to /// nodes in this graph. /// \returns The trimmed graph - ExplodedGraph *trim(ArrayRef Nodes, + ExplodedGraph *trim(ArrayRef Nodes, bool BreakCycles = false, InterExplodedGraphMap *ForwardMap = 0, InterExplodedGraphMap *InverseMap = 0) const; diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp index cc67343d34..51fdab5c68 100644 --- a/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -1895,7 +1895,8 @@ public: ArrayRef Nodes) { // The trimmed graph is created in the body of the constructor to ensure // that the DenseMaps have been initialized already. - G.reset(OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap)); + G.reset(OriginalGraph->trim(Nodes, /*BreakCycles=*/true, + &ForwardMap, &InverseMap)); } void createBestReportGraph(ArrayRef Nodes, diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index ca466d8907..f9d4345bae 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -331,8 +331,22 @@ ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, return V; } +static bool isDescendent(const ExplodedNode *Parent, const ExplodedNode *Child){ + SmallVector WL; + WL.push_back(Parent); + + while (!WL.empty()) { + const ExplodedNode *N = WL.pop_back_val(); + if (N == Child) + return true; + WL.append(N->succ_begin(), N->succ_end()); + } + + return false; +} + ExplodedGraph * -ExplodedGraph::trim(ArrayRef Sinks, +ExplodedGraph::trim(ArrayRef Sinks, bool BreakCycles, InterExplodedGraphMap *ForwardMap, InterExplodedGraphMap *InverseMap) const{ @@ -429,7 +443,8 @@ ExplodedGraph::trim(ArrayRef Sinks, I != E; ++I) { Pass2Ty::iterator PI = Pass2.find(*I); if (PI != Pass2.end()) { - const_cast(PI->second)->addPredecessor(NewN, *G); + if (!BreakCycles || !isDescendent(PI->second, NewN)) + const_cast(PI->second)->addPredecessor(NewN, *G); continue; } -- cgit v1.2.3-70-g09d2 From 0f3a34fb7fea37ebfbcba8b400ccb697b9559b49 Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Fri, 22 Mar 2013 21:15:33 +0000 Subject: Revert "[analyzer] Break cycles (optionally) when trimming an ExplodedGraph." The algorithm used here was ridiculously slow when a potential back-edge pointed to a node that already had a lot of successors. The previous commit makes this feature unnecessary anyway. This reverts r177468 / f4cf6b10f863b9bc716a09b2b2a8c497dcc6aa9b. Conflicts: lib/StaticAnalyzer/Core/BugReporter.cpp git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177765 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h | 6 +----- lib/StaticAnalyzer/Core/BugReporter.cpp | 3 +-- lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 19 ++----------------- 3 files changed, 4 insertions(+), 24 deletions(-) (limited to 'lib/StaticAnalyzer/Core/ExplodedGraph.cpp') diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index 208c12bd74..5211916407 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -363,16 +363,12 @@ public: /// /// \param Nodes The nodes which must appear in the final graph. Presumably /// these are end-of-path nodes (i.e. they have no successors). - /// \param BreakCycles Whether or not the trimmed graph should make an effort - /// to eliminate cycles. Note that this may result in some - /// unnecessary nodes being included in the final graph - /// (i.e. nodes that would have only appeared in a cycle). /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in /// the returned graph. /// \param[out] InverseMap An optional map from nodes in the returned graph to /// nodes in this graph. /// \returns The trimmed graph - ExplodedGraph *trim(ArrayRef Nodes, bool BreakCycles = false, + ExplodedGraph *trim(ArrayRef Nodes, InterExplodedGraphMap *ForwardMap = 0, InterExplodedGraphMap *InverseMap = 0) const; diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp index ab80d9e8ac..8f8eb3bb85 100644 --- a/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -1936,8 +1936,7 @@ TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph, // The trimmed graph is created in the body of the constructor to ensure // that the DenseMaps have been initialized already. InterExplodedGraphMap ForwardMap; - G.reset(OriginalGraph->trim(Nodes, /*BreakCycles=*/false, - &ForwardMap, &InverseMap)); + G.reset(OriginalGraph->trim(Nodes, &ForwardMap, &InverseMap)); // Find the (first) error node in the trimmed graph. We just need to consult // the node map which maps from nodes in the original graph to nodes diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index f9d4345bae..ca466d8907 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -331,22 +331,8 @@ ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, return V; } -static bool isDescendent(const ExplodedNode *Parent, const ExplodedNode *Child){ - SmallVector WL; - WL.push_back(Parent); - - while (!WL.empty()) { - const ExplodedNode *N = WL.pop_back_val(); - if (N == Child) - return true; - WL.append(N->succ_begin(), N->succ_end()); - } - - return false; -} - ExplodedGraph * -ExplodedGraph::trim(ArrayRef Sinks, bool BreakCycles, +ExplodedGraph::trim(ArrayRef Sinks, InterExplodedGraphMap *ForwardMap, InterExplodedGraphMap *InverseMap) const{ @@ -443,8 +429,7 @@ ExplodedGraph::trim(ArrayRef Sinks, bool BreakCycles, I != E; ++I) { Pass2Ty::iterator PI = Pass2.find(*I); if (PI != Pass2.end()) { - if (!BreakCycles || !isDescendent(PI->second, NewN)) - const_cast(PI->second)->addPredecessor(NewN, *G); + const_cast(PI->second)->addPredecessor(NewN, *G); continue; } -- cgit v1.2.3-70-g09d2 From 3655119ab1cb7b26926afeeb0f96cb21a21e410a Mon Sep 17 00:00:00 2001 From: Anna Zaks Date: Wed, 27 Mar 2013 17:36:01 +0000 Subject: [analyzer] Cleanup: only get the PostStmt when we need the underlying Stmt + comment git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@178153 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib/StaticAnalyzer/Core/ExplodedGraph.cpp') diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index ca466d8907..af9518acc7 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -117,8 +117,7 @@ bool ExplodedGraph::shouldCollect(const ExplodedNode *node) { return false; // Condition 4. - PostStmt ps = progPoint.castAs(); - if (ps.getTag()) + if (progPoint.getTag()) return false; // Conditions 5, 6, and 7. @@ -128,8 +127,9 @@ bool ExplodedGraph::shouldCollect(const ExplodedNode *node) { progPoint.getLocationContext() != pred->getLocationContext()) return false; - // All further checks require expressions. - const Expr *Ex = dyn_cast(ps.getStmt()); + // All further checks require expressions. As per #3, we know that we have + // a PostStmt. + const Expr *Ex = dyn_cast(progPoint.castAs().getStmt()); if (!Ex) return false; -- cgit v1.2.3-70-g09d2