1 //=-- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -*- C++ -*------=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the template classes ExplodedNode and ExplodedGraph,
11 // which represent a path-sensitive, intra-procedural "exploded graph."
13 //===----------------------------------------------------------------------===//
15 #include "clang/StaticAnalyzer/PathSensitive/ExplodedGraph.h"
16 #include "clang/StaticAnalyzer/PathSensitive/GRState.h"
17 #include "clang/AST/Stmt.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallVector.h"
23 using namespace clang
;
26 //===----------------------------------------------------------------------===//
28 //===----------------------------------------------------------------------===//
30 // An out of line virtual method to provide a home for the class vtable.
31 ExplodedNode::Auditor::~Auditor() {}
34 static ExplodedNode::Auditor
* NodeAuditor
= 0;
37 void ExplodedNode::SetAuditor(ExplodedNode::Auditor
* A
) {
43 //===----------------------------------------------------------------------===//
45 //===----------------------------------------------------------------------===//
47 static inline BumpVector
<ExplodedNode
*>& getVector(void* P
) {
48 return *reinterpret_cast<BumpVector
<ExplodedNode
*>*>(P
);
51 void ExplodedNode::addPredecessor(ExplodedNode
* V
, ExplodedGraph
&G
) {
52 assert (!V
->isSink());
54 V
->Succs
.addNode(this, G
);
56 if (NodeAuditor
) NodeAuditor
->AddEdge(V
, this);
60 void ExplodedNode::NodeGroup::addNode(ExplodedNode
* N
, ExplodedGraph
&G
) {
61 assert((reinterpret_cast<uintptr_t>(N
) & Mask
) == 0x0);
64 if (getKind() == Size1
) {
65 if (ExplodedNode
* NOld
= getNode()) {
66 BumpVectorContext
&Ctx
= G
.getNodeAllocator();
67 BumpVector
<ExplodedNode
*> *V
=
68 G
.getAllocator().Allocate
<BumpVector
<ExplodedNode
*> >();
69 new (V
) BumpVector
<ExplodedNode
*>(Ctx
, 4);
71 assert((reinterpret_cast<uintptr_t>(V
) & Mask
) == 0x0);
72 V
->push_back(NOld
, Ctx
);
74 P
= reinterpret_cast<uintptr_t>(V
) | SizeOther
;
75 assert(getPtr() == (void*) V
);
76 assert(getKind() == SizeOther
);
79 P
= reinterpret_cast<uintptr_t>(N
);
80 assert(getKind() == Size1
);
84 assert(getKind() == SizeOther
);
85 getVector(getPtr()).push_back(N
, G
.getNodeAllocator());
89 unsigned ExplodedNode::NodeGroup::size() const {
93 if (getKind() == Size1
)
94 return getNode() ? 1 : 0;
96 return getVector(getPtr()).size();
99 ExplodedNode
**ExplodedNode::NodeGroup::begin() const {
103 if (getKind() == Size1
)
104 return (ExplodedNode
**) (getPtr() ? &P
: NULL
);
106 return const_cast<ExplodedNode
**>(&*(getVector(getPtr()).begin()));
109 ExplodedNode
** ExplodedNode::NodeGroup::end() const {
113 if (getKind() == Size1
)
114 return (ExplodedNode
**) (getPtr() ? &P
+1 : NULL
);
116 // Dereferencing end() is undefined behaviour. The vector is not empty, so
117 // we can dereference the last elem and then add 1 to the result.
118 return const_cast<ExplodedNode
**>(getVector(getPtr()).end());
122 ExplodedNode
*ExplodedGraph::getNode(const ProgramPoint
& L
,
123 const GRState
* State
, bool* IsNew
) {
124 // Profile 'State' to determine if we already have an existing node.
125 llvm::FoldingSetNodeID profile
;
128 NodeTy::Profile(profile
, L
, State
);
129 NodeTy
* V
= Nodes
.FindNodeOrInsertPos(profile
, InsertPos
);
132 // Allocate a new node.
133 V
= (NodeTy
*) getAllocator().Allocate
<NodeTy
>();
134 new (V
) NodeTy(L
, State
);
136 // Insert the node into the node set and return it.
137 Nodes
.InsertNode(V
, InsertPos
);
141 if (IsNew
) *IsNew
= true;
144 if (IsNew
) *IsNew
= false;
149 std::pair
<ExplodedGraph
*, InterExplodedGraphMap
*>
150 ExplodedGraph::Trim(const NodeTy
* const* NBeg
, const NodeTy
* const* NEnd
,
151 llvm::DenseMap
<const void*, const void*> *InverseMap
) const {
154 return std::make_pair((ExplodedGraph
*) 0,
155 (InterExplodedGraphMap
*) 0);
157 assert (NBeg
< NEnd
);
159 llvm::OwningPtr
<InterExplodedGraphMap
> M(new InterExplodedGraphMap());
161 ExplodedGraph
* G
= TrimInternal(NBeg
, NEnd
, M
.get(), InverseMap
);
163 return std::make_pair(static_cast<ExplodedGraph
*>(G
), M
.take());
167 ExplodedGraph::TrimInternal(const ExplodedNode
* const* BeginSources
,
168 const ExplodedNode
* const* EndSources
,
169 InterExplodedGraphMap
* M
,
170 llvm::DenseMap
<const void*, const void*> *InverseMap
) const {
172 typedef llvm::DenseSet
<const ExplodedNode
*> Pass1Ty
;
175 typedef llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*> Pass2Ty
;
176 Pass2Ty
& Pass2
= M
->M
;
178 llvm::SmallVector
<const ExplodedNode
*, 10> WL1
, WL2
;
180 // ===- Pass 1 (reverse DFS) -===
181 for (const ExplodedNode
* const* I
= BeginSources
; I
!= EndSources
; ++I
) {
186 // Process the first worklist until it is empty. Because it is a std::list
187 // it acts like a FIFO queue.
188 while (!WL1
.empty()) {
189 const ExplodedNode
*N
= WL1
.back();
192 // Have we already visited this node? If so, continue to the next one.
196 // Otherwise, mark this node as visited.
199 // If this is a root enqueue it to the second worklist.
200 if (N
->Preds
.empty()) {
205 // Visit our predecessors and enqueue them.
206 for (ExplodedNode
** I
=N
->Preds
.begin(), **E
=N
->Preds
.end(); I
!=E
; ++I
)
210 // We didn't hit a root? Return with a null pointer for the new graph.
214 // Create an empty graph.
215 ExplodedGraph
* G
= MakeEmptyGraph();
217 // ===- Pass 2 (forward DFS to construct the new graph) -===
218 while (!WL2
.empty()) {
219 const ExplodedNode
* N
= WL2
.back();
222 // Skip this node if we have already processed it.
223 if (Pass2
.find(N
) != Pass2
.end())
226 // Create the corresponding node in the new graph and record the mapping
227 // from the old node to the new node.
228 ExplodedNode
* NewN
= G
->getNode(N
->getLocation(), N
->State
, NULL
);
231 // Also record the reverse mapping from the new node to the old node.
232 if (InverseMap
) (*InverseMap
)[NewN
] = N
;
234 // If this node is a root, designate it as such in the graph.
235 if (N
->Preds
.empty())
238 // In the case that some of the intended predecessors of NewN have already
239 // been created, we should hook them up as predecessors.
241 // Walk through the predecessors of 'N' and hook up their corresponding
242 // nodes in the new graph (if any) to the freshly created node.
243 for (ExplodedNode
**I
=N
->Preds
.begin(), **E
=N
->Preds
.end(); I
!=E
; ++I
) {
244 Pass2Ty::iterator PI
= Pass2
.find(*I
);
245 if (PI
== Pass2
.end())
248 NewN
->addPredecessor(PI
->second
, *G
);
251 // In the case that some of the intended successors of NewN have already
252 // been created, we should hook them up as successors. Otherwise, enqueue
253 // the new nodes from the original graph that should have nodes created
255 for (ExplodedNode
**I
=N
->Succs
.begin(), **E
=N
->Succs
.end(); I
!=E
; ++I
) {
256 Pass2Ty::iterator PI
= Pass2
.find(*I
);
257 if (PI
!= Pass2
.end()) {
258 PI
->second
->addPredecessor(NewN
, *G
);
262 // Enqueue nodes to the worklist that were marked during pass 1.
267 // Finally, explictly mark all nodes without any successors as sinks.
276 InterExplodedGraphMap::getMappedNode(const ExplodedNode
* N
) const {
277 llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*>::const_iterator I
=
280 return I
== M
.end() ? 0 : I
->second
;