[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>.

llvm-svn: 177468

2 files changed, 19 insertions, 3 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
index cc67343d340..51fdab5c683 100644
--- a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp
+++ b/clang/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/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index ca466d89070..f9d4345baef 100644
--- a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/clang/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;
       }