[analyzer] Re-apply "Do part of the work to find shortest bug paths up front".

With the assurance that the trimmed graph does not contain cycles,
this patch is safe (with a few tweaks), and provides the performance
boost it was intended to.

Part of performance work for <rdar://problem/13433687>.

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

1 files changed, 126 insertions, 43 deletions

diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp
index 51fdab5c68..7b5ad29ab1 100644
--- a/lib/StaticAnalyzer/Core/BugReporter.cpp
+++ b/lib/StaticAnalyzer/Core/BugReporter.cpp
@@ -1888,87 +1888,114 @@ public:
 class TrimmedGraph {
   InterExplodedGraphMap ForwardMap;
   InterExplodedGraphMap InverseMap;
+
+  typedef llvm::DenseMap<const ExplodedNode *, unsigned> PriorityMapTy;
+  PriorityMapTy PriorityMap;
+
   OwningPtr<ExplodedGraph> G;
+  const ExplodedNode *Root;
 public:
-  /// 
   TrimmedGraph(const ExplodedGraph *OriginalGraph,
-               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, /*BreakCycles=*/true,
-                                &ForwardMap, &InverseMap));
-  }
+               ArrayRef<const ExplodedNode *> Nodes);
 
   void createBestReportGraph(ArrayRef<const ExplodedNode *> Nodes,
                              ReportGraph &GraphWrapper) const;
+
+  void removeErrorNode(const ExplodedNode *Node);
 };
 
 }
 
-
-void TrimmedGraph::createBestReportGraph(ArrayRef<const ExplodedNode *> Nodes,
-                                         ReportGraph &GraphWrapper) const {
-  assert(!GraphWrapper.Graph && "ReportGraph is already in use");
-  assert(GraphWrapper.BackMap.empty() && "ReportGraph is already in use");
+TrimmedGraph::TrimmedGraph(const ExplodedGraph *OriginalGraph,
+                           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, /*BreakCycles=*/true,
+                              &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
   // in the new graph.
-  std::queue<const ExplodedNode *> WS;
+  std::queue<std::pair<const ExplodedNode *, unsigned> > WS;
   typedef llvm::SmallDenseMap<const ExplodedNode *, size_t, 32> IndexMapTy;
-  IndexMapTy IndexMap;
+  IndexMapTy IndexMap(llvm::NextPowerOf2(Nodes.size() + 1));
 
   for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
     const ExplodedNode *OriginalNode = Nodes[i];
     if (const ExplodedNode *N = ForwardMap.lookup(OriginalNode)) {
-      WS.push(N);
+      WS.push(std::make_pair(N, 0));
       IndexMap[OriginalNode] = i;
     }
   }
 
   assert(!WS.empty() && "No error node found in the trimmed graph.");
 
-  // Create a new graph with a single path.  This is the graph
-  // that will be returned to the caller.
-  ExplodedGraph *GNew = new ExplodedGraph();
-  GraphWrapper.Graph.reset(GNew);
-
-  // Sometimes the trimmed graph can contain a cycle.  Perform a reverse BFS
-  // to the root node, and then construct a new graph that contains only
-  // a single path.
-  llvm::DenseMap<const ExplodedNode *, unsigned> Visited;
-
-  unsigned cnt = 0;
-  const ExplodedNode *Root = 0;
-
+  // Perform a reverse BFS to find all the shortest paths.
+  Root = 0;
   while (!WS.empty()) {
-    const ExplodedNode *Node = WS.front();
+    const ExplodedNode *Node;
+    unsigned Priority;
+    llvm::tie(Node, Priority) = WS.front();
     WS.pop();
 
-    if (Visited.find(Node) != Visited.end())
-      continue;
+    PriorityMapTy::iterator PriorityEntry;
+    bool IsNew;
+    llvm::tie(PriorityEntry, IsNew) =
+      PriorityMap.insert(std::make_pair(Node, Priority));
 
-    Visited[Node] = cnt++;
+    if (!IsNew) {
+      assert(PriorityEntry->second <= Priority);
+      continue;
+    }
 
     if (Node->pred_empty()) {
+      assert(!Root && "more than one root");
       Root = Node;
-      break;
     }
 
-    for (ExplodedNode::const_pred_iterator I=Node->pred_begin(),
-         E=Node->pred_end(); I!=E; ++I)
-      WS.push(*I);
+    for (ExplodedNode::const_pred_iterator I = Node->pred_begin(),
+                                           E = Node->pred_end();
+         I != E; ++I)
+      WS.push(std::make_pair(*I, Priority + 1));
   }
-
+  
   assert(Root);
+}
+
+void TrimmedGraph::createBestReportGraph(ArrayRef<const ExplodedNode *> Nodes,
+                                         ReportGraph &GraphWrapper) const {
+  assert(!GraphWrapper.Graph && "ReportGraph is already in use");
+  assert(GraphWrapper.BackMap.empty() && "ReportGraph is already in use");
+
+  // 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
+  // in the new graph.
+  std::queue<std::pair<const ExplodedNode *, unsigned> > WS;
+  typedef llvm::SmallDenseMap<const ExplodedNode *, size_t, 32> IndexMapTy;
+  IndexMapTy IndexMap(llvm::NextPowerOf2(Nodes.size() + 1));
+
+  for (unsigned i = 0, count = Nodes.size(); i < count; ++i) {
+    const ExplodedNode *OriginalNode = Nodes[i];
+    if (const ExplodedNode *N = ForwardMap.lookup(OriginalNode)) {
+      WS.push(std::make_pair(N, 0));
+      IndexMap[OriginalNode] = i;
+    }
+  }
+
+  assert(!WS.empty() && "No error node found in the trimmed graph.");
+
+  // Create a new graph with a single path.  This is the graph
+  // that will be returned to the caller.
+  ExplodedGraph *GNew = new ExplodedGraph();
+  GraphWrapper.Graph.reset(GNew);
 
   // Now walk from the root down the BFS path, always taking the successor
   // with the lowest number.
   ExplodedNode *Last = 0;
   for ( const ExplodedNode *N = Root ;;) {
     // Lookup the number associated with the current node.
-    llvm::DenseMap<const ExplodedNode *,unsigned>::iterator I = Visited.find(N);
-    assert(I != Visited.end());
+    PriorityMapTy::const_iterator I = PriorityMap.find(N);
+    assert(I != PriorityMap.end());
 
     // Create the equivalent node in the new graph with the same state
     // and location.
@@ -1994,14 +2021,14 @@ void TrimmedGraph::createBestReportGraph(ArrayRef<const ExplodedNode *> Nodes,
     }
 
     // Find the next successor node.  We choose the node that is marked
-    // with the lowest DFS number.
+    // with the lowest BFS number.
     unsigned MinVal = -1U;
     for (ExplodedNode::const_succ_iterator SI = N->succ_begin(),
                                            SE = N->succ_end();
          SI != SE; ++SI) {
-      I = Visited.find(*SI);
+      I = PriorityMap.find(*SI);
 
-      if (I == Visited.end())
+      if (I == PriorityMap.end())
         continue;
 
       if (I->second < MinVal) {
@@ -2014,6 +2041,60 @@ void TrimmedGraph::createBestReportGraph(ArrayRef<const ExplodedNode *> Nodes,
   }
 }
 
+void TrimmedGraph::removeErrorNode(const ExplodedNode *ErrorNode) {
+  ErrorNode = ForwardMap[ErrorNode];
+  assert(ErrorNode && "not an error node");
+
+  PriorityMapTy::iterator PriorityEntry = PriorityMap.find(ErrorNode);
+  assert(PriorityEntry != PriorityMap.end() && "error node already removed");
+  PriorityMap.erase(PriorityEntry);
+
+  std::queue<const ExplodedNode *> WS;
+  for (ExplodedNode::const_pred_iterator PI = ErrorNode->pred_begin(),
+                                         PE = ErrorNode->pred_end();
+       PI != PE; ++PI) {
+    assert(PriorityMap.find(*PI) != PriorityMap.end() && "predecessor removed");
+    WS.push(*PI);
+  }
+
+  // Update all nodes possibly affected by this change.
+  while (!WS.empty()) {
+    const ExplodedNode *N = WS.front();
+    WS.pop();
+
+    PriorityEntry = PriorityMap.find(N);
+
+    // Did we process this node already and find it unreachable?
+    if (PriorityEntry == PriorityMap.end())
+      continue;
+
+    unsigned MinPriority = -1U;
+    for (ExplodedNode::const_succ_iterator SI = N->succ_begin(),
+                                           SE = N->succ_end();
+         SI != SE; ++SI) {
+      PriorityMapTy::iterator SuccEntry = PriorityMap.find(*SI);
+      if (SuccEntry == PriorityMap.end())
+        continue;
+      MinPriority = std::min(SuccEntry->second, MinPriority);
+    }
+
+    if (MinPriority == -1U)
+      PriorityMap.erase(N);
+    else if (PriorityMap[N] == MinPriority + 1)
+      continue;
+    else
+      PriorityMap[N] = MinPriority + 1;
+
+    for (ExplodedNode::const_pred_iterator PI = N->pred_begin(),
+                                           PE = N->pred_end();
+         PI != PE; ++PI) {
+      assert(PriorityMap.find(*PI) != PriorityMap.end() && "premature removal");
+      WS.push(*PI);
+    }
+  }
+}
+
+
 /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object
 ///  and collapses PathDiagosticPieces that are expanded by macros.
 static void CompactPathDiagnostic(PathPieces &path, const SourceManager& SM) {
@@ -2216,8 +2297,10 @@ bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD,
       finalReportConfigToken = R->getConfigurationChangeToken();
     } while (finalReportConfigToken != origReportConfigToken);
 
-    if (!R->isValid())
+    if (!R->isValid()) {
+      TrimG.removeErrorNode(R->getErrorNode());
       continue;
+    }
 
     // Finally, prune the diagnostic path of uninteresting stuff.
     if (!PD.path.empty()) {