From 86e04ceaadf5e42877a0d76e766af45bf68224ff Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Wed, 20 Mar 2013 00:35:37 +0000 Subject: [PATCH] [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 . llvm-svn: 177469 --- clang/lib/StaticAnalyzer/Core/BugReporter.cpp | 169 +++++++++++++++++++------- 1 file changed, 126 insertions(+), 43 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp index 51fdab5..7b5ad29 100644 --- a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -1888,87 +1888,114 @@ public: class TrimmedGraph { InterExplodedGraphMap ForwardMap; InterExplodedGraphMap InverseMap; + + typedef llvm::DenseMap PriorityMapTy; + PriorityMapTy PriorityMap; + OwningPtr G; + const ExplodedNode *Root; public: - /// TrimmedGraph(const ExplodedGraph *OriginalGraph, - ArrayRef 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 Nodes); void createBestReportGraph(ArrayRef Nodes, ReportGraph &GraphWrapper) const; + + void removeErrorNode(const ExplodedNode *Node); }; } - -void TrimmedGraph::createBestReportGraph(ArrayRef 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 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 WS; + std::queue > WS; typedef llvm::SmallDenseMap 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 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 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 > WS; + typedef llvm::SmallDenseMap 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::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 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 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 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()) { -- 2.7.4