[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 <rdar://problem/13433687>.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177468 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 24 insertions, 4 deletions

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<const NodeTy *> Nodes,
+  ExplodedGraph *trim(ArrayRef<const NodeTy *> 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<const ExplodedNode *> 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<const ExplodedNode *> 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<const ExplodedNode *, 16> 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<const NodeTy *> Sinks,
+ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks, bool BreakCycles,
                     InterExplodedGraphMap *ForwardMap,
                     InterExplodedGraphMap *InverseMap) const{
 
@@ -429,7 +443,8 @@ ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
          I != E; ++I) {
       Pass2Ty::iterator PI = Pass2.find(*I);
       if (PI != Pass2.end()) {
-        const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
+        if (!BreakCycles || !isDescendent(PI->second, NewN))
+          const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
         continue;
       }