Improved ExplodedGraph::Trim to only show nodes reachable from a reverse BFS

from the sources, and to try and generate only a single path from sources
to roots.


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

1 files changed, 46 insertions, 13 deletions

diff --git a/Analysis/ExplodedGraph.cpp b/Analysis/ExplodedGraph.cpp
index 421b9e3846..2ba46d77d6 100644
--- a/Analysis/ExplodedGraph.cpp
+++ b/Analysis/ExplodedGraph.cpp
@@ -17,6 +17,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include <vector>
+#include <list>
 
 using namespace clang;
 
@@ -89,7 +90,7 @@ ExplodedNodeImpl::NodeGroup::~NodeGroup() {
 ExplodedGraphImpl* ExplodedGraphImpl::Trim(ExplodedNodeImpl** BeginSources,
                                            ExplodedNodeImpl** EndSources) const{
   
-  typedef llvm::DenseSet<ExplodedNodeImpl*> Pass1Ty;
+  typedef llvm::DenseMap<ExplodedNodeImpl*, ExplodedNodeImpl*> Pass1Ty;
   typedef llvm::DenseMap<ExplodedNodeImpl*, ExplodedNodeImpl*> Pass2Ty;
   
   Pass1Ty Pass1;
@@ -101,30 +102,58 @@ ExplodedGraphImpl* ExplodedGraphImpl::Trim(ExplodedNodeImpl** BeginSources,
     
     // Enqueue the source nodes to the first worklist. 
     
-    llvm::SmallVector<ExplodedNodeImpl*, 10> WL1;
+    std::list<std::pair<ExplodedNodeImpl*, ExplodedNodeImpl*> > WL1;
   
     for (ExplodedNodeImpl** I = BeginSources; I != EndSources; ++I)
-      WL1.push_back(*I);
+      WL1.push_back(std::make_pair(*I, *I));
     
     // Process the worklist.
 
     while (!WL1.empty()) {
       
-      ExplodedNodeImpl* N = WL1.back();
+      ExplodedNodeImpl* N = WL1.back().first;
+      ExplodedNodeImpl* Src = WL1.back().second;
+      
       WL1.pop_back();
       
-      if (Pass1.count(N))
+      if (Pass1.find(N) != Pass1.end())
         continue;
       
-      Pass1.insert(N);
+      bool PredHasSameSource = false;
+      bool VisitPreds = true;
+            
+      for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end();
+            I!=E; ++I) {
+        
+        Pass1Ty::iterator pi = Pass1.find(*I);
+        
+        if (pi == Pass1.end())
+          continue;
+        
+        VisitPreds = false;
+        
+        if (pi->second == Src) {
+          PredHasSameSource = true;
+          break;
+        }
+      }
+      
+      if (VisitPreds || !PredHasSameSource) {
+        
+        Pass1[N] = Src;
       
-      if (N->Preds.empty()) {
-        WL2.push_back(N);
-        continue;      
+        if (N->Preds.empty()) {
+          WL2.push_back(N);
+          continue;      
+        }
       }
+      else
+        Pass1[N] = NULL;
       
-      for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I)
-        WL1.push_back(*I);
+      if (VisitPreds)
+        for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end();
+             I!=E; ++I)
+          WL1.push_front(std::make_pair(*I, Src));
     }
   }
   
@@ -182,8 +211,12 @@ ExplodedGraphImpl* ExplodedGraphImpl::Trim(ExplodedNodeImpl** BeginSources,
 
       // Enqueue nodes to the worklist that were marked during pass 1.
       
-      if (Pass1.count(*I))
-        WL2.push_back(*I);
+      Pass1Ty::iterator pi = Pass1.find(*I);
+      
+      if (pi == Pass1.end() || pi->second == NULL)
+        continue;
+            
+      WL2.push_back(*I);
     }
     
     if (N->isSink())