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/Core/PathSensitive/ExplodedGraph.h"
16 #include "clang/StaticAnalyzer/Core/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 typedef std::vector
<ExplodedNode
*> NodeList
;
48 static inline NodeList
*& getNodeList(void *&p
) { return (NodeList
*&) p
; }
50 ExplodedGraph::~ExplodedGraph() {
52 delete getNodeList(recentlyAllocatedNodes
);
53 delete getNodeList(freeNodes
);
57 //===----------------------------------------------------------------------===//
59 //===----------------------------------------------------------------------===//
61 void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
62 if (!recentlyAllocatedNodes
)
64 NodeList
&nl
= *getNodeList(recentlyAllocatedNodes
);
66 // Reclaimn all nodes that match *all* the following criteria:
68 // (1) 1 predecessor (that has one successor)
69 // (2) 1 successor (that has one predecessor)
70 // (3) The ProgramPoint is for a PostStmt.
71 // (4) There is no 'tag' for the ProgramPoint.
72 // (5) The 'store' is the same as the predecessor.
73 // (6) The 'GDM' is the same as the predecessor.
74 // (7) The LocationContext is the same as the predecessor.
75 // (8) The PostStmt is for a non-CFGElement expression.
77 for (NodeList::iterator i
= nl
.begin(), e
= nl
.end() ; i
!= e
; ++i
) {
78 ExplodedNode
*node
= *i
;
80 // Conditions 1 and 2.
81 if (node
->pred_size() != 1 || node
->succ_size() != 1)
84 ExplodedNode
*pred
= *(node
->pred_begin());
85 if (pred
->succ_size() != 1)
88 ExplodedNode
*succ
= *(node
->succ_begin());
89 if (succ
->pred_size() != 1)
93 ProgramPoint progPoint
= node
->getLocation();
94 if (!isa
<PostStmt
>(progPoint
))
98 PostStmt ps
= cast
<PostStmt
>(progPoint
);
99 if (ps
.getTag() || isa
<PostStmtCustom
>(ps
))
102 if (isa
<BinaryOperator
>(ps
.getStmt()))
105 // Conditions 5, 6, and 7.
106 const GRState
*state
= node
->getState();
107 const GRState
*pred_state
= pred
->getState();
108 if (state
->St
!= pred_state
->St
|| state
->GDM
!= pred_state
->GDM
||
109 progPoint
.getLocationContext() != pred
->getLocationContext())
113 if (node
->getCFG().isBlkExpr(ps
.getStmt()))
116 // If we reach here, we can remove the node. This means:
117 // (a) changing the predecessors successor to the successor of this node
118 // (b) changing the successors predecessor to the predecessor of this node
119 // (c) Putting 'node' onto freeNodes.
120 pred
->replaceSuccessor(succ
);
121 succ
->replacePredecessor(pred
);
123 freeNodes
= new NodeList();
124 getNodeList(freeNodes
)->push_back(node
);
125 Nodes
.RemoveNode(node
);
127 node
->~ExplodedNode();
133 //===----------------------------------------------------------------------===//
135 //===----------------------------------------------------------------------===//
137 static inline BumpVector
<ExplodedNode
*>& getVector(void* P
) {
138 return *reinterpret_cast<BumpVector
<ExplodedNode
*>*>(P
);
141 void ExplodedNode::addPredecessor(ExplodedNode
* V
, ExplodedGraph
&G
) {
142 assert (!V
->isSink());
144 V
->Succs
.addNode(this, G
);
146 if (NodeAuditor
) NodeAuditor
->AddEdge(V
, this);
150 void ExplodedNode::NodeGroup::replaceNode(ExplodedNode
*node
) {
151 assert(getKind() == Size1
);
152 P
= reinterpret_cast<uintptr_t>(node
);
153 assert(getKind() == Size1
);
156 void ExplodedNode::NodeGroup::addNode(ExplodedNode
* N
, ExplodedGraph
&G
) {
157 assert((reinterpret_cast<uintptr_t>(N
) & Mask
) == 0x0);
160 if (getKind() == Size1
) {
161 if (ExplodedNode
* NOld
= getNode()) {
162 BumpVectorContext
&Ctx
= G
.getNodeAllocator();
163 BumpVector
<ExplodedNode
*> *V
=
164 G
.getAllocator().Allocate
<BumpVector
<ExplodedNode
*> >();
165 new (V
) BumpVector
<ExplodedNode
*>(Ctx
, 4);
167 assert((reinterpret_cast<uintptr_t>(V
) & Mask
) == 0x0);
168 V
->push_back(NOld
, Ctx
);
169 V
->push_back(N
, Ctx
);
170 P
= reinterpret_cast<uintptr_t>(V
) | SizeOther
;
171 assert(getPtr() == (void*) V
);
172 assert(getKind() == SizeOther
);
175 P
= reinterpret_cast<uintptr_t>(N
);
176 assert(getKind() == Size1
);
180 assert(getKind() == SizeOther
);
181 getVector(getPtr()).push_back(N
, G
.getNodeAllocator());
185 unsigned ExplodedNode::NodeGroup::size() const {
189 if (getKind() == Size1
)
190 return getNode() ? 1 : 0;
192 return getVector(getPtr()).size();
195 ExplodedNode
**ExplodedNode::NodeGroup::begin() const {
199 if (getKind() == Size1
)
200 return (ExplodedNode
**) (getPtr() ? &P
: NULL
);
202 return const_cast<ExplodedNode
**>(&*(getVector(getPtr()).begin()));
205 ExplodedNode
** ExplodedNode::NodeGroup::end() const {
209 if (getKind() == Size1
)
210 return (ExplodedNode
**) (getPtr() ? &P
+1 : NULL
);
212 // Dereferencing end() is undefined behaviour. The vector is not empty, so
213 // we can dereference the last elem and then add 1 to the result.
214 return const_cast<ExplodedNode
**>(getVector(getPtr()).end());
218 ExplodedNode
*ExplodedGraph::getNode(const ProgramPoint
& L
,
219 const GRState
* State
, bool* IsNew
) {
220 // Profile 'State' to determine if we already have an existing node.
221 llvm::FoldingSetNodeID profile
;
224 NodeTy::Profile(profile
, L
, State
);
225 NodeTy
* V
= Nodes
.FindNodeOrInsertPos(profile
, InsertPos
);
228 if (freeNodes
&& !getNodeList(freeNodes
)->empty()) {
229 NodeList
*nl
= getNodeList(freeNodes
);
234 // Allocate a new node.
235 V
= (NodeTy
*) getAllocator().Allocate
<NodeTy
>();
238 new (V
) NodeTy(L
, State
);
241 if (!recentlyAllocatedNodes
)
242 recentlyAllocatedNodes
= new NodeList();
243 getNodeList(recentlyAllocatedNodes
)->push_back(V
);
246 // Insert the node into the node set and return it.
247 Nodes
.InsertNode(V
, InsertPos
);
251 if (IsNew
) *IsNew
= true;
254 if (IsNew
) *IsNew
= false;
259 std::pair
<ExplodedGraph
*, InterExplodedGraphMap
*>
260 ExplodedGraph::Trim(const NodeTy
* const* NBeg
, const NodeTy
* const* NEnd
,
261 llvm::DenseMap
<const void*, const void*> *InverseMap
) const {
264 return std::make_pair((ExplodedGraph
*) 0,
265 (InterExplodedGraphMap
*) 0);
267 assert (NBeg
< NEnd
);
269 llvm::OwningPtr
<InterExplodedGraphMap
> M(new InterExplodedGraphMap());
271 ExplodedGraph
* G
= TrimInternal(NBeg
, NEnd
, M
.get(), InverseMap
);
273 return std::make_pair(static_cast<ExplodedGraph
*>(G
), M
.take());
277 ExplodedGraph::TrimInternal(const ExplodedNode
* const* BeginSources
,
278 const ExplodedNode
* const* EndSources
,
279 InterExplodedGraphMap
* M
,
280 llvm::DenseMap
<const void*, const void*> *InverseMap
) const {
282 typedef llvm::DenseSet
<const ExplodedNode
*> Pass1Ty
;
285 typedef llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*> Pass2Ty
;
286 Pass2Ty
& Pass2
= M
->M
;
288 llvm::SmallVector
<const ExplodedNode
*, 10> WL1
, WL2
;
290 // ===- Pass 1 (reverse DFS) -===
291 for (const ExplodedNode
* const* I
= BeginSources
; I
!= EndSources
; ++I
) {
296 // Process the first worklist until it is empty. Because it is a std::list
297 // it acts like a FIFO queue.
298 while (!WL1
.empty()) {
299 const ExplodedNode
*N
= WL1
.back();
302 // Have we already visited this node? If so, continue to the next one.
306 // Otherwise, mark this node as visited.
309 // If this is a root enqueue it to the second worklist.
310 if (N
->Preds
.empty()) {
315 // Visit our predecessors and enqueue them.
316 for (ExplodedNode
** I
=N
->Preds
.begin(), **E
=N
->Preds
.end(); I
!=E
; ++I
)
320 // We didn't hit a root? Return with a null pointer for the new graph.
324 // Create an empty graph.
325 ExplodedGraph
* G
= MakeEmptyGraph();
327 // ===- Pass 2 (forward DFS to construct the new graph) -===
328 while (!WL2
.empty()) {
329 const ExplodedNode
* N
= WL2
.back();
332 // Skip this node if we have already processed it.
333 if (Pass2
.find(N
) != Pass2
.end())
336 // Create the corresponding node in the new graph and record the mapping
337 // from the old node to the new node.
338 ExplodedNode
* NewN
= G
->getNode(N
->getLocation(), N
->State
, NULL
);
341 // Also record the reverse mapping from the new node to the old node.
342 if (InverseMap
) (*InverseMap
)[NewN
] = N
;
344 // If this node is a root, designate it as such in the graph.
345 if (N
->Preds
.empty())
348 // In the case that some of the intended predecessors of NewN have already
349 // been created, we should hook them up as predecessors.
351 // Walk through the predecessors of 'N' and hook up their corresponding
352 // nodes in the new graph (if any) to the freshly created node.
353 for (ExplodedNode
**I
=N
->Preds
.begin(), **E
=N
->Preds
.end(); I
!=E
; ++I
) {
354 Pass2Ty::iterator PI
= Pass2
.find(*I
);
355 if (PI
== Pass2
.end())
358 NewN
->addPredecessor(PI
->second
, *G
);
361 // In the case that some of the intended successors of NewN have already
362 // been created, we should hook them up as successors. Otherwise, enqueue
363 // the new nodes from the original graph that should have nodes created
365 for (ExplodedNode
**I
=N
->Succs
.begin(), **E
=N
->Succs
.end(); I
!=E
; ++I
) {
366 Pass2Ty::iterator PI
= Pass2
.find(*I
);
367 if (PI
!= Pass2
.end()) {
368 PI
->second
->addPredecessor(NewN
, *G
);
372 // Enqueue nodes to the worklist that were marked during pass 1.
377 // Finally, explictly mark all nodes without any successors as sinks.
386 InterExplodedGraphMap::getMappedNode(const ExplodedNode
* N
) const {
387 llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*>::const_iterator I
=
390 return I
== M
.end() ? 0 : I
->second
;