From 0f3a34fb7fea37ebfbcba8b400ccb697b9559b49 Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Fri, 22 Mar 2013 21:15:33 +0000 Subject: [PATCH] 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 --- .../Core/PathSensitive/ExplodedGraph.h | 6 +----- lib/StaticAnalyzer/Core/BugReporter.cpp | 3 +-- lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 19 ++----------------- 3 files changed, 4 insertions(+), 24 deletions(-) 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; } -- 2.49.0