From 1efffab67364f5afcc25f5f5f77e0f7ba5d41055 Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Sat, 16 Mar 2013 01:07:58 +0000 Subject: [PATCH] [analyzer] Separate graph trimming from creating the single-path graph. When we generate a path diagnostic for a bug report, we have to take the full ExplodedGraph and limit it down to a single path. We do this in two steps: "trimming", which limits the graph to all the paths that lead to this particular bug, and "creating the report graph", which finds the shortest path in the trimmed path to any error node. With BugReporterVisitor false positive suppression, this becomes more expensive: it's possible for some paths through the trimmed graph to be invalid (i.e. likely false positives) but others to be valid. Therefore we have to run the visitors over each path in the graph until we find one that is valid, or until we've ruled them all out. This can become quite expensive. This commit separates out graph trimming from creating the report graph, performing the first only once per bug equivalence class and the second once per bug report. It also cleans up that portion of the code by introducing some wrapper classes. This seems to recover most of the performance regression described in my last commit. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177216 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/StaticAnalyzer/Core/BugReporter.cpp | 126 +++++++++++++----------- 1 file changed, 68 insertions(+), 58 deletions(-) diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp index 0b095dff61..cc67343d34 100644 --- a/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -1873,44 +1873,69 @@ void BugReporter::FlushReports() { // PathDiagnostics generation. //===----------------------------------------------------------------------===// -static std::pair, - std::pair > -MakeReportGraph(const ExplodedGraph* G, - SmallVectorImpl &nodes) { - - // Create the trimmed graph. It will contain the shortest paths from the - // error nodes to the root. In the new graph we should only have one - // error node unless there are two or more error nodes with the same minimum - // path length. - InterExplodedGraphMap NodeMap, InverseMap; - OwningPtr GTrim(G->trim(nodes, &NodeMap, &InverseMap)); +namespace { +/// A wrapper around a report graph, which contains only a single path, and its +/// node maps. +class ReportGraph { +public: + OwningPtr Graph; + InterExplodedGraphMap BackMap; + ExplodedNode *ErrorNode; + size_t Index; +}; + +/// A wrapper around a trimmed graph and its node maps. +class TrimmedGraph { + InterExplodedGraphMap ForwardMap; + InterExplodedGraphMap InverseMap; + OwningPtr G; +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)); + } + + void createBestReportGraph(ArrayRef Nodes, + ReportGraph &GraphWrapper) const; +}; + +} + + +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 (NMap) which maps from nodes in the original graph to nodes + // the node map which maps from nodes in the original graph to nodes // in the new graph. - - std::queue WS; - typedef llvm::DenseMap IndexMapTy; + std::queue WS; + typedef llvm::SmallDenseMap IndexMapTy; IndexMapTy IndexMap; - for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) { - const ExplodedNode *originalNode = nodes[nodeIndex]; - if (const ExplodedNode *N = NodeMap.lookup(originalNode)) { + 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); - IndexMap[originalNode] = nodeIndex; + IndexMap[OriginalNode] = i; } } assert(!WS.empty() && "No error node found in the trimmed graph."); - // Create a new (third!) graph with a single path. This is the 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; + llvm::DenseMap Visited; unsigned cnt = 0; const ExplodedNode *Root = 0; @@ -1938,13 +1963,10 @@ MakeReportGraph(const ExplodedGraph* G, // Now walk from the root down the BFS path, always taking the successor // with the lowest number. - ExplodedNode *Last = 0, *First = 0; - InterExplodedGraphMap *BM = new InterExplodedGraphMap(); - unsigned NodeIndex = 0; - + ExplodedNode *Last = 0; for ( const ExplodedNode *N = Root ;;) { // Lookup the number associated with the current node. - llvm::DenseMap::iterator I = Visited.find(N); + llvm::DenseMap::iterator I = Visited.find(N); assert(I != Visited.end()); // Create the equivalent node in the new graph with the same state @@ -1952,9 +1974,9 @@ MakeReportGraph(const ExplodedGraph* G, ExplodedNode *NewN = GNew->getNode(N->getLocation(), N->getState()); // Store the mapping to the original node. - InterExplodedGraphMap::iterator IMitr = InverseMap.find(N); + InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(N); assert(IMitr != InverseMap.end() && "No mapping to original node."); - (*BM)[NewN] = (const ExplodedNode*) IMitr->second; + GraphWrapper.BackMap[NewN] = IMitr->second; // Link up the new node with the previous node. if (Last) @@ -1963,40 +1985,32 @@ MakeReportGraph(const ExplodedGraph* G, Last = NewN; // Are we at the final node? - IndexMapTy::iterator IMI = - IndexMap.find((const ExplodedNode*)(IMitr->second)); + IndexMapTy::iterator IMI = IndexMap.find(IMitr->second); if (IMI != IndexMap.end()) { - First = NewN; - NodeIndex = IMI->second; + GraphWrapper.ErrorNode = NewN; + GraphWrapper.Index = IMI->second; break; } // Find the next successor node. We choose the node that is marked // with the lowest DFS number. - ExplodedNode::const_succ_iterator SI = N->succ_begin(); - ExplodedNode::const_succ_iterator SE = N->succ_end(); - N = 0; - - for (unsigned MinVal = 0; SI != SE; ++SI) { - + unsigned MinVal = -1U; + for (ExplodedNode::const_succ_iterator SI = N->succ_begin(), + SE = N->succ_end(); + SI != SE; ++SI) { I = Visited.find(*SI); if (I == Visited.end()) continue; - if (!N || I->second < MinVal) { + if (I->second < MinVal) { N = *SI; MinVal = I->second; } } - assert(N); + assert(MinVal != -1U); } - - assert(First); - - return std::make_pair(std::make_pair(GNew, BM), - std::make_pair(First, NodeIndex)); } /// CompactPathDiagnostic - This function postprocesses a PathDiagnostic object @@ -2120,30 +2134,26 @@ bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, typedef PathDiagnosticConsumer::PathGenerationScheme PathGenerationScheme; PathGenerationScheme ActiveScheme = PC.getGenerationScheme(); + TrimmedGraph TrimG(&getGraph(), errorNodes); + for (size_t Remaining = bugReports.size(); Remaining > 0; --Remaining) { // Construct a new graph that contains only a single path from the error // node to a root. - // FIXME: It might be possible to reuse some of this work instead of - // redoing it every time we mark a report invalid. - const std::pair, - std::pair >& - GPair = MakeReportGraph(&getGraph(), errorNodes); + ReportGraph ErrorGraph; + TrimG.createBestReportGraph(errorNodes, ErrorGraph); // Find the BugReport with the original location. - assert(GPair.second.second < bugReports.size()); - BugReport *R = bugReports[GPair.second.second]; + assert(ErrorGraph.Index < bugReports.size()); + BugReport *R = bugReports[ErrorGraph.Index]; assert(R && "No original report found for sliced graph."); assert(R->isValid() && "Report selected by trimmed graph marked invalid."); // Don't try to reuse this report if it ends up being suppressed. - errorNodes[GPair.second.second] = 0; - - OwningPtr ReportGraph(GPair.first.first); - OwningPtr BackMap(GPair.first.second); - const ExplodedNode *N = GPair.second.first; + errorNodes[ErrorGraph.Index] = 0; // Start building the path diagnostic... - PathDiagnosticBuilder PDB(*this, R, *BackMap, &PC); + PathDiagnosticBuilder PDB(*this, R, ErrorGraph.BackMap, &PC); + const ExplodedNode *N = ErrorGraph.ErrorNode; // Register additional node visitors. R->addVisitor(new NilReceiverBRVisitor()); -- 2.40.0