From c9963132736782d0c9178c744b3e2307cfb98a08 Mon Sep 17 00:00:00 2001 From: Jordan Rose Date: Sat, 16 Mar 2013 01:07:53 +0000 Subject: [PATCH] [analyzer] Eliminate InterExplodedGraphMap class and NodeBackMap typedef. ...in favor of this typedef: typedef llvm::DenseMap InterExplodedGraphMap; Use this everywhere the previous class and typedef were used. Took the opportunity to ArrayRef-ize ExplodedGraph::trim while I'm at it. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177215 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Core/PathSensitive/ExplodedGraph.h | 35 ++++++------- .../Core/PathSensitive/ExprEngine.h | 7 +-- lib/StaticAnalyzer/Core/BugReporter.cpp | 40 +++++--------- lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 52 +++++-------------- lib/StaticAnalyzer/Core/ExprEngine.cpp | 8 +-- 5 files changed, 50 insertions(+), 92 deletions(-) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index 70be1f8c63..5211916407 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -239,18 +239,8 @@ private: void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } }; -// FIXME: Is this class necessary? -class InterExplodedGraphMap { - virtual void anchor(); - llvm::DenseMap M; - friend class ExplodedGraph; - -public: - ExplodedNode *getMappedNode(const ExplodedNode *N) const; - - InterExplodedGraphMap() {} - virtual ~InterExplodedGraphMap() {} -}; +typedef llvm::DenseMap + InterExplodedGraphMap; class ExplodedGraph { protected: @@ -368,14 +358,19 @@ public: typedef llvm::DenseMap NodeMap; - std::pair - Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd, - llvm::DenseMap *InverseMap = 0) const; - - ExplodedGraph* TrimInternal(const ExplodedNode* const * NBeg, - const ExplodedNode* const * NEnd, - InterExplodedGraphMap *M, - llvm::DenseMap *InverseMap) const; + /// Creates a trimmed version of the graph that only contains paths leading + /// to the given nodes. + /// + /// \param Nodes The nodes which must appear in the final graph. Presumably + /// these are end-of-path nodes (i.e. they have no successors). + /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in + /// the returned graph. + /// \param[out] InverseMap An optional map from nodes in the returned graph to + /// nodes in this graph. + /// \returns The trimmed graph + ExplodedGraph *trim(ArrayRef Nodes, + InterExplodedGraphMap *ForwardMap = 0, + InterExplodedGraphMap *InverseMap = 0) const; /// Enable tracking of recently allocated nodes for potential reclamation /// when calling reclaimRecentlyAllocatedNodes(). diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index 60c35f807e..8fa74fefef 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -146,11 +146,12 @@ public: void enqueueEndOfPath(ExplodedNodeSet &S); void GenerateCallExitNode(ExplodedNode *N); - /// ViewGraph - Visualize the ExplodedGraph created by executing the - /// simulation. + /// Visualize the ExplodedGraph created by executing the simulation. void ViewGraph(bool trim = false); - void ViewGraph(ExplodedNode** Beg, ExplodedNode** End); + /// Visualize a trimmed ExplodedGraph that only contains paths to the given + /// nodes. + void ViewGraph(ArrayRef Nodes); /// getInitialState - Return the initial state used for the root vertex /// in the ExplodedGraph. diff --git a/lib/StaticAnalyzer/Core/BugReporter.cpp b/lib/StaticAnalyzer/Core/BugReporter.cpp index 46108f44ea..0b095dff61 100644 --- a/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -299,19 +299,14 @@ static void adjustCallLocations(PathPieces &Pieces, // PathDiagnosticBuilder and its associated routines and helper objects. //===----------------------------------------------------------------------===// -typedef llvm::DenseMap NodeBackMap; - namespace { class NodeMapClosure : public BugReport::NodeResolver { - NodeBackMap& M; + InterExplodedGraphMap &M; public: - NodeMapClosure(NodeBackMap *m) : M(*m) {} - ~NodeMapClosure() {} + NodeMapClosure(InterExplodedGraphMap &m) : M(m) {} const ExplodedNode *getOriginalNode(const ExplodedNode *N) { - NodeBackMap::iterator I = M.find(N); - return I == M.end() ? 0 : I->second; + return M.lookup(N); } }; @@ -323,7 +318,7 @@ public: const LocationContext *LC; PathDiagnosticBuilder(GRBugReporter &br, - BugReport *r, NodeBackMap *Backmap, + BugReport *r, InterExplodedGraphMap &Backmap, PathDiagnosticConsumer *pdc) : BugReporterContext(br), R(r), PDC(pdc), NMC(Backmap), LC(r->getErrorNode()->getLocationContext()) @@ -1878,7 +1873,7 @@ void BugReporter::FlushReports() { // PathDiagnostics generation. //===----------------------------------------------------------------------===// -static std::pair, +static std::pair, std::pair > MakeReportGraph(const ExplodedGraph* G, SmallVectorImpl &nodes) { @@ -1887,17 +1882,8 @@ MakeReportGraph(const ExplodedGraph* G, // 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. - ExplodedGraph* GTrim; - InterExplodedGraphMap* NMap; - - llvm::DenseMap InverseMap; - llvm::tie(GTrim, NMap) = G->Trim(nodes.data(), nodes.data() + nodes.size(), - &InverseMap); - - // Create owning pointers for GTrim and NMap just to ensure that they are - // released when this function exists. - OwningPtr AutoReleaseGTrim(GTrim); - OwningPtr AutoReleaseNMap(NMap); + InterExplodedGraphMap NodeMap, InverseMap; + OwningPtr GTrim(G->trim(nodes, &NodeMap, &InverseMap)); // 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 @@ -1909,7 +1895,7 @@ MakeReportGraph(const ExplodedGraph* G, for (unsigned nodeIndex = 0 ; nodeIndex < nodes.size(); ++nodeIndex) { const ExplodedNode *originalNode = nodes[nodeIndex]; - if (const ExplodedNode *N = NMap->getMappedNode(originalNode)) { + if (const ExplodedNode *N = NodeMap.lookup(originalNode)) { WS.push(N); IndexMap[originalNode] = nodeIndex; } @@ -1953,7 +1939,7 @@ 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; - NodeBackMap *BM = new NodeBackMap(); + InterExplodedGraphMap *BM = new InterExplodedGraphMap(); unsigned NodeIndex = 0; for ( const ExplodedNode *N = Root ;;) { @@ -1966,7 +1952,7 @@ MakeReportGraph(const ExplodedGraph* G, ExplodedNode *NewN = GNew->getNode(N->getLocation(), N->getState()); // Store the mapping to the original node. - llvm::DenseMap::iterator IMitr=InverseMap.find(N); + InterExplodedGraphMap::iterator IMitr = InverseMap.find(N); assert(IMitr != InverseMap.end() && "No mapping to original node."); (*BM)[NewN] = (const ExplodedNode*) IMitr->second; @@ -2139,7 +2125,7 @@ bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, // 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, + const std::pair, std::pair >& GPair = MakeReportGraph(&getGraph(), errorNodes); @@ -2153,11 +2139,11 @@ bool GRBugReporter::generatePathDiagnostic(PathDiagnostic& PD, errorNodes[GPair.second.second] = 0; OwningPtr ReportGraph(GPair.first.first); - OwningPtr BackMap(GPair.first.second); + OwningPtr BackMap(GPair.first.second); const ExplodedNode *N = GPair.second.first; // Start building the path diagnostic... - PathDiagnosticBuilder PDB(*this, R, BackMap.get(), &PC); + PathDiagnosticBuilder PDB(*this, R, *BackMap, &PC); // Register additional node visitors. R->addVisitor(new NilReceiverBRVisitor()); diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index 2210b4e2d7..ca466d8907 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -331,45 +331,31 @@ ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, return V; } -std::pair -ExplodedGraph::Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd, - llvm::DenseMap *InverseMap) const { +ExplodedGraph * +ExplodedGraph::trim(ArrayRef Sinks, + InterExplodedGraphMap *ForwardMap, + InterExplodedGraphMap *InverseMap) const{ - if (NBeg == NEnd) - return std::make_pair((ExplodedGraph*) 0, - (InterExplodedGraphMap*) 0); - - assert (NBeg < NEnd); - - OwningPtr M(new InterExplodedGraphMap()); - - ExplodedGraph* G = TrimInternal(NBeg, NEnd, M.get(), InverseMap); - - return std::make_pair(static_cast(G), M.take()); -} - -ExplodedGraph* -ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, - const ExplodedNode* const* EndSources, - InterExplodedGraphMap* M, - llvm::DenseMap *InverseMap) const { + if (Nodes.empty()) + return 0; typedef llvm::DenseSet Pass1Ty; Pass1Ty Pass1; - typedef llvm::DenseMap Pass2Ty; - Pass2Ty& Pass2 = M->M; + typedef InterExplodedGraphMap Pass2Ty; + InterExplodedGraphMap Pass2Scratch; + Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch; SmallVector WL1, WL2; // ===- Pass 1 (reverse DFS) -=== - for (const ExplodedNode* const* I = BeginSources; I != EndSources; ++I) { + for (ArrayRef::iterator I = Sinks.begin(), E = Sinks.end(); + I != E; ++I) { if (*I) WL1.push_back(*I); } - // Process the first worklist until it is empty. Because it is a std::list - // it acts like a FIFO queue. + // Process the first worklist until it is empty. while (!WL1.empty()) { const ExplodedNode *N = WL1.back(); WL1.pop_back(); @@ -432,7 +418,7 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, if (PI == Pass2.end()) continue; - NewN->addPredecessor(PI->second, *G); + NewN->addPredecessor(const_cast(PI->second), *G); } // In the case that some of the intended successors of NewN have already @@ -443,7 +429,7 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, I != E; ++I) { Pass2Ty::iterator PI = Pass2.find(*I); if (PI != Pass2.end()) { - PI->second->addPredecessor(NewN, *G); + const_cast(PI->second)->addPredecessor(NewN, *G); continue; } @@ -456,13 +442,3 @@ ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources, return G; } -void InterExplodedGraphMap::anchor() { } - -ExplodedNode* -InterExplodedGraphMap::getMappedNode(const ExplodedNode *N) const { - llvm::DenseMap::const_iterator I = - M.find(N); - - return I == M.end() ? 0 : I->second; -} - diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp index 437af86ccf..53cea0f9a2 100644 --- a/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2301,7 +2301,7 @@ GetGraphNode::iterator> void ExprEngine::ViewGraph(bool trim) { #ifndef NDEBUG if (trim) { - std::vector Src; + std::vector Src; // Flush any outstanding reports to make sure we cover all the nodes. // This does not cause them to get displayed. @@ -2315,7 +2315,7 @@ void ExprEngine::ViewGraph(bool trim) { if (N) Src.push_back(N); } - ViewGraph(&Src[0], &Src[0]+Src.size()); + ViewGraph(Src); } else { GraphPrintCheckerState = this; @@ -2329,12 +2329,12 @@ void ExprEngine::ViewGraph(bool trim) { #endif } -void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) { +void ExprEngine::ViewGraph(ArrayRef Nodes) { #ifndef NDEBUG GraphPrintCheckerState = this; GraphPrintSourceManager = &getContext().getSourceManager(); - std::auto_ptr TrimmedG(G.Trim(Beg, End).first); + OwningPtr TrimmedG(G.trim(Nodes)); if (!TrimmedG.get()) llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; -- 2.40.0