From 10aa55410bbecbb658ce14a5f801d50cf06d12df Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 12 Mar 2009 23:41:59 +0000 Subject: Use the correct data structures! ExplodedGraph::TrimGraph: - Just do a DFS both ways instead of BFS-DFS. We're just determining what subset of the nodes are reachable from the root and reverse-reachable from the bug nodes. DFS is more efficient for this task. BugReporter: - MakeReportGraph: Do a reverse-BFS instead of a reverse-DFS to determine the approximate shortest path through the simulation graph. We were seeing some weird cases where too many loops were being reported for simple bugs. Possibly we will need to replace this with actually computing the shortest path in terms of line numbers. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@66842 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ExplodedGraph.cpp | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'lib/Analysis/ExplodedGraph.cpp') diff --git a/lib/Analysis/ExplodedGraph.cpp b/lib/Analysis/ExplodedGraph.cpp index 0e72af91e1..20de6c48c3 100644 --- a/lib/Analysis/ExplodedGraph.cpp +++ b/lib/Analysis/ExplodedGraph.cpp @@ -18,7 +18,6 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include -#include using namespace clang; @@ -133,10 +132,9 @@ const { typedef llvm::DenseMap Pass2Ty; Pass2Ty& Pass2 = M->M; - std::list WL1; - llvm::SmallVector WL2; + llvm::SmallVector WL1, WL2; - // ===- Pass 1 (reverse BFS) -=== + // ===- Pass 1 (reverse DFS) -=== for (const ExplodedNodeImpl* const* I = BeginSources; I != EndSources; ++I) { assert(*I); WL1.push_back(*I); @@ -163,7 +161,7 @@ const { // Visit our predecessors and enqueue them. for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I) - WL1.push_front(*I); + WL1.push_back(*I); } // We didn't hit a root? Return with a null pointer for the new graph. -- cgit v1.2.3-18-g5258