aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis')
-rw-r--r--lib/Analysis/BugReporter.cpp25
-rw-r--r--lib/Analysis/ExplodedGraph.cpp63
-rw-r--r--lib/Analysis/GRCoreEngine.cpp36
3 files changed, 81 insertions, 43 deletions
diff --git a/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp
index 19a031a1ae..af4fd384e8 100644
--- a/lib/Analysis/BugReporter.cpp
+++ b/lib/Analysis/BugReporter.cpp
@@ -1286,8 +1286,7 @@ BugReportEquivClass::~BugReportEquivClass() {
GRBugReporter::~GRBugReporter() { FlushReports(); }
BugReporterData::~BugReporterData() {}
-ExplodedGraph<GRState>&
-GRBugReporter::getGraph() { return Eng.getGraph(); }
+ExplodedGraph &GRBugReporter::getGraph() { return Eng.getGraph(); }
GRStateManager&
GRBugReporter::getStateManager() { return Eng.getStateManager(); }
@@ -1332,9 +1331,9 @@ void BugReporter::FlushReports() {
// PathDiagnostics generation.
//===----------------------------------------------------------------------===//
-static std::pair<std::pair<ExplodedGraph<GRState>*, NodeBackMap*>,
+static std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
std::pair<ExplodedNode*, unsigned> >
-MakeReportGraph(const ExplodedGraph<GRState>* G,
+MakeReportGraph(const ExplodedGraph* G,
const ExplodedNode** NStart,
const ExplodedNode** NEnd) {
@@ -1342,7 +1341,7 @@ MakeReportGraph(const ExplodedGraph<GRState>* 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<GRState>* GTrim;
+ ExplodedGraph* GTrim;
InterExplodedGraphMap* NMap;
llvm::DenseMap<const void*, const void*> InverseMap;
@@ -1350,7 +1349,7 @@ MakeReportGraph(const ExplodedGraph<GRState>* G,
// Create owning pointers for GTrim and NMap just to ensure that they are
// released when this function exists.
- llvm::OwningPtr<ExplodedGraph<GRState> > AutoReleaseGTrim(GTrim);
+ llvm::OwningPtr<ExplodedGraph> AutoReleaseGTrim(GTrim);
llvm::OwningPtr<InterExplodedGraphMap> AutoReleaseNMap(NMap);
// Find the (first) error node in the trimmed graph. We just need to consult
@@ -1358,7 +1357,7 @@ MakeReportGraph(const ExplodedGraph<GRState>* G,
// in the new graph.
std::queue<const ExplodedNode*> WS;
- typedef llvm::DenseMap<const ExplodedNode*,unsigned> IndexMapTy;
+ typedef llvm::DenseMap<const ExplodedNode*, unsigned> IndexMapTy;
IndexMapTy IndexMap;
for (const ExplodedNode** I = NStart; I != NEnd; ++I)
@@ -1372,9 +1371,8 @@ MakeReportGraph(const ExplodedGraph<GRState>* G,
// Create a new (third!) graph with a single path. This is the graph
// that will be returned to the caller.
- ExplodedGraph<GRState> *GNew =
- new ExplodedGraph<GRState>(GTrim->getCFG(), GTrim->getCodeDecl(),
- GTrim->getContext());
+ ExplodedGraph *GNew = new ExplodedGraph(GTrim->getCFG(), GTrim->getCodeDecl(),
+ GTrim->getContext());
// 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
@@ -1418,8 +1416,7 @@ MakeReportGraph(const ExplodedGraph<GRState>* G,
// Create the equivalent node in the new graph with the same state
// and location.
- ExplodedNode* NewN =
- GNew->getNode(N->getLocation(), N->getState());
+ ExplodedNode* NewN = GNew->getNode(N->getLocation(), N->getState());
// Store the mapping to the original node.
llvm::DenseMap<const void*, const void*>::iterator IMitr=InverseMap.find(N);
@@ -1576,7 +1573,7 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
// Construct a new graph that contains only a single path from the error
// node to a root.
- const std::pair<std::pair<ExplodedGraph<GRState>*, NodeBackMap*>,
+ const std::pair<std::pair<ExplodedGraph*, NodeBackMap*>,
std::pair<ExplodedNode*, unsigned> >&
GPair = MakeReportGraph(&getGraph(), &Nodes[0], &Nodes[0] + Nodes.size());
@@ -1588,7 +1585,7 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
assert(R && "No original report found for sliced graph.");
- llvm::OwningPtr<ExplodedGraph<GRState> > ReportGraph(GPair.first.first);
+ llvm::OwningPtr<ExplodedGraph> ReportGraph(GPair.first.first);
llvm::OwningPtr<NodeBackMap> BackMap(GPair.first.second);
const ExplodedNode *N = GPair.second.first;
diff --git a/lib/Analysis/ExplodedGraph.cpp b/lib/Analysis/ExplodedGraph.cpp
index f80aa113e4..88bb120f5d 100644
--- a/lib/Analysis/ExplodedGraph.cpp
+++ b/lib/Analysis/ExplodedGraph.cpp
@@ -127,13 +127,56 @@ ExplodedNode::NodeGroup::~NodeGroup() {
if (getKind() == SizeOther) delete &getVector(getPtr());
}
-ExplodedGraphImpl*
-ExplodedGraphImpl::Trim(const ExplodedNode* const* BeginSources,
- const ExplodedNode* const* EndSources,
- InterExplodedGraphMapImpl* M,
- llvm::DenseMap<const void*, const void*> *InverseMap)
-const {
+ExplodedNode *ExplodedGraph::getNode(const ProgramPoint& L,
+ const GRState* State, bool* IsNew) {
+ // Profile 'State' to determine if we already have an existing node.
+ llvm::FoldingSetNodeID profile;
+ void* InsertPos = 0;
+ NodeTy::Profile(profile, L, State);
+ NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
+
+ if (!V) {
+ // Allocate a new node.
+ V = (NodeTy*) Allocator.Allocate<NodeTy>();
+ new (V) NodeTy(L, State);
+
+ // Insert the node into the node set and return it.
+ Nodes.InsertNode(V, InsertPos);
+
+ ++NumNodes;
+
+ if (IsNew) *IsNew = true;
+ }
+ else
+ if (IsNew) *IsNew = false;
+
+ return V;
+}
+
+std::pair<ExplodedGraph*, InterExplodedGraphMap*>
+ExplodedGraph::Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd,
+ llvm::DenseMap<const void*, const void*> *InverseMap) const {
+
+ if (NBeg == NEnd)
+ return std::make_pair((ExplodedGraph*) 0,
+ (InterExplodedGraphMap*) 0);
+
+ assert (NBeg < NEnd);
+
+ llvm::OwningPtr<InterExplodedGraphMap> M(new InterExplodedGraphMap());
+
+ ExplodedGraph* G = TrimInternal(NBeg, NEnd, M.get(), InverseMap);
+
+ return std::make_pair(static_cast<ExplodedGraph*>(G), M.take());
+}
+
+ExplodedGraph*
+ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources,
+ const ExplodedNode* const* EndSources,
+ InterExplodedGraphMap* M,
+ llvm::DenseMap<const void*, const void*> *InverseMap) const {
+
typedef llvm::DenseSet<const ExplodedNode*> Pass1Ty;
Pass1Ty Pass1;
@@ -177,7 +220,7 @@ const {
return 0;
// Create an empty graph.
- ExplodedGraphImpl* G = MakeEmptyGraph();
+ ExplodedGraph* G = MakeEmptyGraph();
// ===- Pass 2 (forward DFS to construct the new graph) -===
while (!WL2.empty()) {
@@ -190,7 +233,7 @@ const {
// Create the corresponding node in the new graph and record the mapping
// from the old node to the new node.
- ExplodedNode* NewN = G->getNodeImpl(N->getLocation(), N->State, NULL);
+ ExplodedNode* NewN = G->getNode(N->getLocation(), N->State, NULL);
Pass2[N] = NewN;
// Also record the reverse mapping from the new node to the old node.
@@ -238,12 +281,10 @@ const {
}
ExplodedNode*
-InterExplodedGraphMapImpl::getMappedImplNode(const ExplodedNode* N) const {
+InterExplodedGraphMap::getMappedNode(const ExplodedNode* N) const {
llvm::DenseMap<const ExplodedNode*, ExplodedNode*>::iterator I =
M.find(N);
return I == M.end() ? 0 : I->second;
}
-InterExplodedGraphMapImpl::InterExplodedGraphMapImpl() {}
-
diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp
index e0b53a8a7f..492b4fe336 100644
--- a/lib/Analysis/GRCoreEngine.cpp
+++ b/lib/Analysis/GRCoreEngine.cpp
@@ -341,11 +341,11 @@ void GRCoreEngineImpl::HandlePostStmt(const PostStmt& L, CFGBlock* B,
/// GenerateNode - Utility method to generate nodes, hook up successors,
/// and add nodes to the worklist.
-void GRCoreEngineImpl::GenerateNode(const ProgramPoint& Loc, const void* State,
- ExplodedNode* Pred) {
+void GRCoreEngineImpl::GenerateNode(const ProgramPoint& Loc,
+ const GRState* State, ExplodedNode* Pred) {
bool IsNew;
- ExplodedNode* Node = G->getNodeImpl(Loc, State, &IsNew);
+ ExplodedNode* Node = G->getNode(Loc, State, &IsNew);
if (Pred)
Node->addPredecessor(Pred); // Link 'Node' with its predecessor.
@@ -383,7 +383,7 @@ void GRStmtNodeBuilderImpl::GenerateAutoTransition(ExplodedNode* N) {
}
bool IsNew;
- ExplodedNode* Succ = Eng.G->getNodeImpl(Loc, N->State, &IsNew);
+ ExplodedNode* Succ = Eng.G->getNode(Loc, N->State, &IsNew);
Succ->addPredecessor(N);
if (IsNew)
@@ -426,7 +426,7 @@ static inline PostStmt GetPostLoc(const Stmt* S, ProgramPoint::Kind K,
}
ExplodedNode*
-GRStmtNodeBuilderImpl::generateNodeImpl(const Stmt* S, const void* State,
+GRStmtNodeBuilderImpl::generateNodeImpl(const Stmt* S, const GRState* State,
ExplodedNode* Pred,
ProgramPoint::Kind K,
const void *tag) {
@@ -437,10 +437,10 @@ GRStmtNodeBuilderImpl::generateNodeImpl(const Stmt* S, const void* State,
ExplodedNode*
GRStmtNodeBuilderImpl::generateNodeImpl(const ProgramPoint &Loc,
- const void* State,
+ const GRState* State,
ExplodedNode* Pred) {
bool IsNew;
- ExplodedNode* N = Eng.G->getNodeImpl(Loc, State, &IsNew);
+ ExplodedNode* N = Eng.G->getNode(Loc, State, &IsNew);
N->addPredecessor(Pred);
Deferred.erase(Pred);
@@ -454,8 +454,8 @@ GRStmtNodeBuilderImpl::generateNodeImpl(const ProgramPoint &Loc,
return NULL;
}
-ExplodedNode* GRBranchNodeBuilderImpl::generateNodeImpl(const void* State,
- bool branch) {
+ExplodedNode* GRBranchNodeBuilderImpl::generateNodeImpl(const GRState* State,
+ bool branch) {
// If the branch has been marked infeasible we should not generate a node.
if (!isFeasible(branch))
@@ -464,7 +464,7 @@ ExplodedNode* GRBranchNodeBuilderImpl::generateNodeImpl(const void* State,
bool IsNew;
ExplodedNode* Succ =
- Eng.G->getNodeImpl(BlockEdge(Src, branch ? DstT : DstF), State, &IsNew);
+ Eng.G->getNode(BlockEdge(Src, branch ? DstT : DstF), State, &IsNew);
Succ->addPredecessor(Pred);
@@ -492,12 +492,12 @@ GRBranchNodeBuilderImpl::~GRBranchNodeBuilderImpl() {
ExplodedNode*
GRIndirectGotoNodeBuilderImpl::generateNodeImpl(const Iterator& I,
- const void* St,
+ const GRState* St,
bool isSink) {
bool IsNew;
ExplodedNode* Succ =
- Eng.G->getNodeImpl(BlockEdge(Src, I.getBlock()), St, &IsNew);
+ Eng.G->getNode(BlockEdge(Src, I.getBlock()), St, &IsNew);
Succ->addPredecessor(Pred);
@@ -517,11 +517,11 @@ GRIndirectGotoNodeBuilderImpl::generateNodeImpl(const Iterator& I,
ExplodedNode*
GRSwitchNodeBuilderImpl::generateCaseStmtNodeImpl(const Iterator& I,
- const void* St) {
+ const GRState* St) {
bool IsNew;
- ExplodedNode* Succ = Eng.G->getNodeImpl(BlockEdge(Src, I.getBlock()),
+ ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock()),
St, &IsNew);
Succ->addPredecessor(Pred);
@@ -535,7 +535,7 @@ GRSwitchNodeBuilderImpl::generateCaseStmtNodeImpl(const Iterator& I,
ExplodedNode*
-GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(const void* St,
+GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(const GRState* St,
bool isSink) {
// Get the block for the default case.
@@ -544,7 +544,7 @@ GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(const void* St,
bool IsNew;
- ExplodedNode* Succ = Eng.G->getNodeImpl(BlockEdge(Src, DefaultBlock),
+ ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock),
St, &IsNew);
Succ->addPredecessor(Pred);
@@ -566,14 +566,14 @@ GREndPathNodeBuilderImpl::~GREndPathNodeBuilderImpl() {
}
ExplodedNode*
-GREndPathNodeBuilderImpl::generateNodeImpl(const void* State,
+GREndPathNodeBuilderImpl::generateNodeImpl(const GRState* State,
const void *tag,
ExplodedNode* P) {
HasGeneratedNode = true;
bool IsNew;
ExplodedNode* Node =
- Eng.G->getNodeImpl(BlockEntrance(&B, tag), State, &IsNew);
+ Eng.G->getNode(BlockEntrance(&B, tag), State, &IsNew);
Node->addPredecessor(P ? P : Pred);
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-05 16:43:23 +0000