Added --trim-path-graph to the driver to trim paths from the ExplodedGraph

that are not related to error nodes.

Fixed bug where we did not detect some NULL dereferences.

Added "ExplodedGraph::Trim" to trim all nodes that cannot transitively reach
a set of provided nodes.

Fixed subtle bug in ExplodedNodeImpl where we could create predecessor
iterators that included the mangled "sink" bit.  The better fix is to integrate
this bit into the void* for the wrapped State, not the NodeGroups representing
a node's predecessors and successors.


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

1 files changed, 122 insertions, 8 deletions

diff --git a/Analysis/ExplodedGraph.cpp b/Analysis/ExplodedGraph.cpp
index 274565bf6c..421b9e3846 100644
--- a/Analysis/ExplodedGraph.cpp
+++ b/Analysis/ExplodedGraph.cpp
@@ -13,6 +13,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/PathSensitive/ExplodedGraph.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include <vector>
 
 using namespace clang;
@@ -25,6 +28,7 @@ static inline std::vector<ExplodedNodeImpl*>& getVector(void* P) {
 void ExplodedNodeImpl::NodeGroup::addNode(ExplodedNodeImpl* N) {
   
   assert ((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
+  assert (!getFlag());
   
   if (getKind() == Size1) {
     if (ExplodedNodeImpl* NOld = getNode()) {
@@ -47,14 +51,11 @@ void ExplodedNodeImpl::NodeGroup::addNode(ExplodedNodeImpl* N) {
   }
 }
 
-bool ExplodedNodeImpl::NodeGroup::empty() const {
-  if (getKind() == Size1)
-    return getNode() ? false : true;
-  else
-    return getVector(getPtr()).empty();
-}
 
 unsigned ExplodedNodeImpl::NodeGroup::size() const {
+  if (getFlag())
+    return 0;
+  
   if (getKind() == Size1)
     return getNode() ? 1 : 0;
   else
@@ -62,15 +63,21 @@ unsigned ExplodedNodeImpl::NodeGroup::size() const {
 }
 
 ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::begin() const {
+  if (getFlag())
+    return NULL;
+  
   if (getKind() == Size1)
-    return (ExplodedNodeImpl**) &P;
+    return (ExplodedNodeImpl**) (getPtr() ? &P : NULL);
   else
     return const_cast<ExplodedNodeImpl**>(&*(getVector(getPtr()).begin()));
 }
 
 ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::end() const {
+  if (getFlag())
+    return NULL;
+  
   if (getKind() == Size1)
-    return (ExplodedNodeImpl**) (P ? &P+1 : &P);
+    return (ExplodedNodeImpl**) (getPtr() ? &P+1 : NULL);
   else
     return const_cast<ExplodedNodeImpl**>(&*(getVector(getPtr()).end()));
 }
@@ -78,3 +85,110 @@ ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::end() const {
 ExplodedNodeImpl::NodeGroup::~NodeGroup() {
   if (getKind() == SizeOther) delete &getVector(getPtr());
 }
+
+ExplodedGraphImpl* ExplodedGraphImpl::Trim(ExplodedNodeImpl** BeginSources,
+                                           ExplodedNodeImpl** EndSources) const{
+  
+  typedef llvm::DenseSet<ExplodedNodeImpl*> Pass1Ty;
+  typedef llvm::DenseMap<ExplodedNodeImpl*, ExplodedNodeImpl*> Pass2Ty;
+  
+  Pass1Ty Pass1;
+  Pass2Ty Pass2;
+  
+  llvm::SmallVector<ExplodedNodeImpl*, 10> WL2;
+
+  { // ===- Pass 1 (reverse BFS) -===
+    
+    // Enqueue the source nodes to the first worklist. 
+    
+    llvm::SmallVector<ExplodedNodeImpl*, 10> WL1;
+  
+    for (ExplodedNodeImpl** I = BeginSources; I != EndSources; ++I)
+      WL1.push_back(*I);
+    
+    // Process the worklist.
+
+    while (!WL1.empty()) {
+      
+      ExplodedNodeImpl* N = WL1.back();
+      WL1.pop_back();
+      
+      if (Pass1.count(N))
+        continue;
+      
+      Pass1.insert(N);
+      
+      if (N->Preds.empty()) {
+        WL2.push_back(N);
+        continue;      
+      }
+      
+      for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I)
+        WL1.push_back(*I);
+    }
+  }
+  
+  if (WL2.empty())
+    return NULL;
+    
+  ExplodedGraphImpl* G = MakeEmptyGraph();
+  
+  // ===- Pass 2 (forward DFS to construct the new graph) -===
+  
+  while (!WL2.empty()) {
+    
+    ExplodedNodeImpl* N = WL2.back();
+    WL2.pop_back();
+    
+    // Skip this node if we have already processed it.
+    
+    if (Pass2.find(N) != Pass2.end())
+      continue;
+    
+    // Create the corresponding node in the new graph.
+    
+    ExplodedNodeImpl* NewN = G->getNodeImpl(N->getLocation(), N->State, NULL);
+    Pass2[N] = NewN;
+    
+    if (N->Preds.empty())
+      G->addRoot(NewN);
+    
+    // In the case that some of the intended predecessors of NewN have already
+    // been created, we should hook them up as predecessors.
+    
+    for (ExplodedNodeImpl **I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I) {
+        
+      Pass2Ty::iterator PI = Pass2.find(*I);
+
+      if (PI == Pass2.end())
+        continue;
+      
+      NewN->addPredecessor(PI->second);
+    }
+
+    // In the case that some of the intended successors of NewN have already
+    // been created, we should hook them up as successors.  Otherwise, enqueue
+    // the new nodes from the original graph that should have nodes created
+    // in the new graph.
+   
+    for (ExplodedNodeImpl **I=N->Succs.begin(), **E=N->Succs.end(); I!=E; ++I) {
+      
+      Pass2Ty::iterator PI = Pass2.find(*I);
+      
+      if (PI != Pass2.end()) {
+        PI->second->addPredecessor(NewN);
+        continue;
+      }
+
+      // Enqueue nodes to the worklist that were marked during pass 1.
+      
+      if (Pass1.count(*I))
+        WL2.push_back(*I);
+    }
+    
+    if (N->isSink())
+      NewN->markAsSink();
+  }
+    
+  return G;
+}