From a5f80b2ea6d30c5055c067530d63bb0dcaf937d0 Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Mon, 18 Mar 2013 23:34:37 +0000 Subject: [PATCH] [analyzer] Do part of the work to find shortest bug paths up front. Splitting the graph trimming and the path-finding (r177216) already recovered quite a bit of performance lost to increased suppression. We can still do better by also performing the reverse BFS up front (needed for shortest-path-finding) and only walking the shortest path for each report. This does mean we have to walk back up the path and invalidate all the BFS numbers if the report turns out to be invalid, but it's probably still faster than redoing the full BFS every time. More performance work for git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177353 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/StaticAnalyzer/Core/BugReporter.cpp | 157 +++++++++++++++++------- 1 file changed, 115 insertions(+), 42 deletions(-) diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp index cc67343d34..25792d8119 100644 --- a/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -1888,86 +1888,109 @@ 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, &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, &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()) + PriorityMapTy::iterator I = PriorityMap.find(Node); + if (I != PriorityMap.end()) { + assert(I->second <= Priority); continue; + } - Visited[Node] = cnt++; + PriorityMap[Node] = Priority; - if (Node->pred_empty()) { + if (Node->pred_empty()) 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. @@ -1998,9 +2021,9 @@ void TrimmedGraph::createBestReportGraph(ArrayRef Nodes, 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) { @@ -2013,6 +2036,54 @@ 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()); + WS.push(*PI); + } + + // Update all nodes possibly affected by this change. + while (!WS.empty()) { + const ExplodedNode *N = WS.front(); + WS.pop(); + + 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()); + 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) { @@ -2215,8 +2286,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.40.0