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/GR/PathSensitive/ExplodedGraph.h"
16 #include "clang/GR/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
;
25 //===----------------------------------------------------------------------===//
27 //===----------------------------------------------------------------------===//
29 // An out of line virtual method to provide a home for the class vtable.
30 ExplodedNode::Auditor::~Auditor() {}
33 static ExplodedNode::Auditor
* NodeAuditor
= 0;
36 void ExplodedNode::SetAuditor(ExplodedNode::Auditor
* A
) {
42 //===----------------------------------------------------------------------===//
44 //===----------------------------------------------------------------------===//
46 static inline BumpVector
<ExplodedNode
*>& getVector(void* P
) {
47 return *reinterpret_cast<BumpVector
<ExplodedNode
*>*>(P
);
50 void ExplodedNode::addPredecessor(ExplodedNode
* V
, ExplodedGraph
&G
) {
51 assert (!V
->isSink());
53 V
->Succs
.addNode(this, G
);
55 if (NodeAuditor
) NodeAuditor
->AddEdge(V
, this);
59 void ExplodedNode::NodeGroup::addNode(ExplodedNode
* N
, ExplodedGraph
&G
) {
60 assert((reinterpret_cast<uintptr_t>(N
) & Mask
) == 0x0);
63 if (getKind() == Size1
) {
64 if (ExplodedNode
* NOld
= getNode()) {
65 BumpVectorContext
&Ctx
= G
.getNodeAllocator();
66 BumpVector
<ExplodedNode
*> *V
=
67 G
.getAllocator().Allocate
<BumpVector
<ExplodedNode
*> >();
68 new (V
) BumpVector
<ExplodedNode
*>(Ctx
, 4);
70 assert((reinterpret_cast<uintptr_t>(V
) & Mask
) == 0x0);
71 V
->push_back(NOld
, Ctx
);
73 P
= reinterpret_cast<uintptr_t>(V
) | SizeOther
;
74 assert(getPtr() == (void*) V
);
75 assert(getKind() == SizeOther
);
78 P
= reinterpret_cast<uintptr_t>(N
);
79 assert(getKind() == Size1
);
83 assert(getKind() == SizeOther
);
84 getVector(getPtr()).push_back(N
, G
.getNodeAllocator());
88 unsigned ExplodedNode::NodeGroup::size() const {
92 if (getKind() == Size1
)
93 return getNode() ? 1 : 0;
95 return getVector(getPtr()).size();
98 ExplodedNode
**ExplodedNode::NodeGroup::begin() const {
102 if (getKind() == Size1
)
103 return (ExplodedNode
**) (getPtr() ? &P
: NULL
);
105 return const_cast<ExplodedNode
**>(&*(getVector(getPtr()).begin()));
108 ExplodedNode
** ExplodedNode::NodeGroup::end() const {
112 if (getKind() == Size1
)
113 return (ExplodedNode
**) (getPtr() ? &P
+1 : NULL
);
115 // Dereferencing end() is undefined behaviour. The vector is not empty, so
116 // we can dereference the last elem and then add 1 to the result.
117 return const_cast<ExplodedNode
**>(getVector(getPtr()).end());
121 ExplodedNode
*ExplodedGraph::getNode(const ProgramPoint
& L
,
122 const GRState
* State
, bool* IsNew
) {
123 // Profile 'State' to determine if we already have an existing node.
124 llvm::FoldingSetNodeID profile
;
127 NodeTy::Profile(profile
, L
, State
);
128 NodeTy
* V
= Nodes
.FindNodeOrInsertPos(profile
, InsertPos
);
131 // Allocate a new node.
132 V
= (NodeTy
*) getAllocator().Allocate
<NodeTy
>();
133 new (V
) NodeTy(L
, State
);
135 // Insert the node into the node set and return it.
136 Nodes
.InsertNode(V
, InsertPos
);
140 if (IsNew
) *IsNew
= true;
143 if (IsNew
) *IsNew
= false;
148 std::pair
<ExplodedGraph
*, InterExplodedGraphMap
*>
149 ExplodedGraph::Trim(const NodeTy
* const* NBeg
, const NodeTy
* const* NEnd
,
150 llvm::DenseMap
<const void*, const void*> *InverseMap
) const {
153 return std::make_pair((ExplodedGraph
*) 0,
154 (InterExplodedGraphMap
*) 0);
156 assert (NBeg
< NEnd
);
158 llvm::OwningPtr
<InterExplodedGraphMap
> M(new InterExplodedGraphMap());
160 ExplodedGraph
* G
= TrimInternal(NBeg
, NEnd
, M
.get(), InverseMap
);
162 return std::make_pair(static_cast<ExplodedGraph
*>(G
), M
.take());
166 ExplodedGraph::TrimInternal(const ExplodedNode
* const* BeginSources
,
167 const ExplodedNode
* const* EndSources
,
168 InterExplodedGraphMap
* M
,
169 llvm::DenseMap
<const void*, const void*> *InverseMap
) const {
171 typedef llvm::DenseSet
<const ExplodedNode
*> Pass1Ty
;
174 typedef llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*> Pass2Ty
;
175 Pass2Ty
& Pass2
= M
->M
;
177 llvm::SmallVector
<const ExplodedNode
*, 10> WL1
, WL2
;
179 // ===- Pass 1 (reverse DFS) -===
180 for (const ExplodedNode
* const* I
= BeginSources
; I
!= EndSources
; ++I
) {
185 // Process the first worklist until it is empty. Because it is a std::list
186 // it acts like a FIFO queue.
187 while (!WL1
.empty()) {
188 const ExplodedNode
*N
= WL1
.back();
191 // Have we already visited this node? If so, continue to the next one.
195 // Otherwise, mark this node as visited.
198 // If this is a root enqueue it to the second worklist.
199 if (N
->Preds
.empty()) {
204 // Visit our predecessors and enqueue them.
205 for (ExplodedNode
** I
=N
->Preds
.begin(), **E
=N
->Preds
.end(); I
!=E
; ++I
)
209 // We didn't hit a root? Return with a null pointer for the new graph.
213 // Create an empty graph.
214 ExplodedGraph
* G
= MakeEmptyGraph();
216 // ===- Pass 2 (forward DFS to construct the new graph) -===
217 while (!WL2
.empty()) {
218 const ExplodedNode
* N
= WL2
.back();
221 // Skip this node if we have already processed it.
222 if (Pass2
.find(N
) != Pass2
.end())
225 // Create the corresponding node in the new graph and record the mapping
226 // from the old node to the new node.
227 ExplodedNode
* NewN
= G
->getNode(N
->getLocation(), N
->State
, NULL
);
230 // Also record the reverse mapping from the new node to the old node.
231 if (InverseMap
) (*InverseMap
)[NewN
] = N
;
233 // If this node is a root, designate it as such in the graph.
234 if (N
->Preds
.empty())
237 // In the case that some of the intended predecessors of NewN have already
238 // been created, we should hook them up as predecessors.
240 // Walk through the predecessors of 'N' and hook up their corresponding
241 // nodes in the new graph (if any) to the freshly created node.
242 for (ExplodedNode
**I
=N
->Preds
.begin(), **E
=N
->Preds
.end(); I
!=E
; ++I
) {
243 Pass2Ty::iterator PI
= Pass2
.find(*I
);
244 if (PI
== Pass2
.end())
247 NewN
->addPredecessor(PI
->second
, *G
);
250 // In the case that some of the intended successors of NewN have already
251 // been created, we should hook them up as successors. Otherwise, enqueue
252 // the new nodes from the original graph that should have nodes created
254 for (ExplodedNode
**I
=N
->Succs
.begin(), **E
=N
->Succs
.end(); I
!=E
; ++I
) {
255 Pass2Ty::iterator PI
= Pass2
.find(*I
);
256 if (PI
!= Pass2
.end()) {
257 PI
->second
->addPredecessor(NewN
, *G
);
261 // Enqueue nodes to the worklist that were marked during pass 1.
266 // Finally, explictly mark all nodes without any successors as sinks.
275 InterExplodedGraphMap::getMappedNode(const ExplodedNode
* N
) const {
276 llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*>::const_iterator I
=
279 return I
== M
.end() ? 0 : I
->second
;