1 //=-- ExplodedGraph.h - 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."
12 // See "Precise interprocedural dataflow analysis via graph reachability"
13 // by Reps, Horwitz, and Sagiv
14 // (http://portal.acm.org/citation.cfm?id=199462) for the definition of an
17 //===----------------------------------------------------------------------===//
19 #ifndef LLVM_CLANG_GR_EXPLODEDGRAPH
20 #define LLVM_CLANG_GR_EXPLODEDGRAPH
22 #include "clang/Analysis/ProgramPoint.h"
23 #include "clang/Analysis/AnalysisContext.h"
24 #include "clang/AST/Decl.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/FoldingSet.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/Support/Allocator.h"
29 #include "llvm/ADT/OwningPtr.h"
30 #include "llvm/ADT/GraphTraits.h"
31 #include "llvm/ADT/DepthFirstIterator.h"
32 #include "llvm/Support/Casting.h"
33 #include "clang/Analysis/Support/BumpVector.h"
44 //===----------------------------------------------------------------------===//
45 // ExplodedGraph "implementation" classes. These classes are not typed to
46 // contain a specific kind of state. Typed-specialized versions are defined
47 // on top of these classes.
48 //===----------------------------------------------------------------------===//
50 class ExplodedNode
: public llvm::FoldingSetNode
{
51 friend class ExplodedGraph
;
52 friend class CoreEngine
;
53 friend class StmtNodeBuilder
;
54 friend class BranchNodeBuilder
;
55 friend class IndirectGotoNodeBuilder
;
56 friend class SwitchNodeBuilder
;
57 friend class EndPathNodeBuilder
;
60 enum { Size1
= 0x0, SizeOther
= 0x1, AuxFlag
= 0x2, Mask
= 0x3 };
63 unsigned getKind() const {
67 void* getPtr() const {
69 return reinterpret_cast<void*>(P
& ~Mask
);
72 ExplodedNode
*getNode() const {
73 return reinterpret_cast<ExplodedNode
*>(getPtr());
79 ExplodedNode
**begin() const;
81 ExplodedNode
**end() const;
83 unsigned size() const;
85 bool empty() const { return (P
& ~Mask
) == 0; }
87 void addNode(ExplodedNode
* N
, ExplodedGraph
&G
);
94 bool getFlag() const {
95 return P
& AuxFlag
? true : false;
99 /// Location - The program location (within a function body) associated
101 const ProgramPoint Location
;
103 /// State - The state associated with this node.
104 const GRState
* State
;
106 /// Preds - The predecessors of this node.
109 /// Succs - The successors of this node.
114 explicit ExplodedNode(const ProgramPoint
& loc
, const GRState
* state
)
115 : Location(loc
), State(state
) {}
117 /// getLocation - Returns the edge associated with the given node.
118 ProgramPoint
getLocation() const { return Location
; }
120 const LocationContext
*getLocationContext() const {
121 return getLocation().getLocationContext();
124 const Decl
&getCodeDecl() const { return *getLocationContext()->getDecl(); }
126 CFG
&getCFG() const { return *getLocationContext()->getCFG(); }
128 ParentMap
&getParentMap() const {return getLocationContext()->getParentMap();}
130 LiveVariables
&getLiveVariables() const {
131 return *getLocationContext()->getLiveVariables();
134 const GRState
* getState() const { return State
; }
136 template <typename T
>
137 const T
* getLocationAs() const { return llvm::dyn_cast
<T
>(&Location
); }
139 static void Profile(llvm::FoldingSetNodeID
&ID
,
140 const ProgramPoint
& Loc
, const GRState
* state
) {
142 ID
.AddPointer(state
);
145 void Profile(llvm::FoldingSetNodeID
& ID
) const {
146 Profile(ID
, getLocation(), getState());
149 /// addPredeccessor - Adds a predecessor to the current node, and
150 /// in tandem add this node as a successor of the other node.
151 void addPredecessor(ExplodedNode
* V
, ExplodedGraph
&G
);
153 unsigned succ_size() const { return Succs
.size(); }
154 unsigned pred_size() const { return Preds
.size(); }
155 bool succ_empty() const { return Succs
.empty(); }
156 bool pred_empty() const { return Preds
.empty(); }
158 bool isSink() const { return Succs
.getFlag(); }
159 void markAsSink() { Succs
.setFlag(); }
161 ExplodedNode
* getFirstPred() {
162 return pred_empty() ? NULL
: *(pred_begin());
165 const ExplodedNode
* getFirstPred() const {
166 return const_cast<ExplodedNode
*>(this)->getFirstPred();
169 // Iterators over successor and predecessor vertices.
170 typedef ExplodedNode
** succ_iterator
;
171 typedef const ExplodedNode
* const * const_succ_iterator
;
172 typedef ExplodedNode
** pred_iterator
;
173 typedef const ExplodedNode
* const * const_pred_iterator
;
175 pred_iterator
pred_begin() { return Preds
.begin(); }
176 pred_iterator
pred_end() { return Preds
.end(); }
178 const_pred_iterator
pred_begin() const {
179 return const_cast<ExplodedNode
*>(this)->pred_begin();
181 const_pred_iterator
pred_end() const {
182 return const_cast<ExplodedNode
*>(this)->pred_end();
185 succ_iterator
succ_begin() { return Succs
.begin(); }
186 succ_iterator
succ_end() { return Succs
.end(); }
188 const_succ_iterator
succ_begin() const {
189 return const_cast<ExplodedNode
*>(this)->succ_begin();
191 const_succ_iterator
succ_end() const {
192 return const_cast<ExplodedNode
*>(this)->succ_end();
202 virtual void AddEdge(ExplodedNode
* Src
, ExplodedNode
* Dst
) = 0;
205 static void SetAuditor(Auditor
* A
);
208 // FIXME: Is this class necessary?
209 class InterExplodedGraphMap
{
210 llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*> M
;
211 friend class ExplodedGraph
;
214 ExplodedNode
* getMappedNode(const ExplodedNode
* N
) const;
216 InterExplodedGraphMap() {}
217 virtual ~InterExplodedGraphMap() {}
220 class ExplodedGraph
{
222 friend class CoreEngine
;
225 typedef llvm::SmallVector
<ExplodedNode
*,2> RootsTy
;
226 typedef llvm::SmallVector
<ExplodedNode
*,10> EndNodesTy
;
228 /// Roots - The roots of the simulation graph. Usually there will be only
229 /// one, but clients are free to establish multiple subgraphs within a single
230 /// SimulGraph. Moreover, these subgraphs can often merge when paths from
231 /// different roots reach the same state at the same program location.
234 /// EndNodes - The nodes in the simulation graph which have been
235 /// specially marked as the endpoint of an abstract simulation path.
238 /// Nodes - The nodes in the graph.
239 llvm::FoldingSet
<ExplodedNode
> Nodes
;
241 /// BVC - Allocator and context for allocating nodes and their predecessor
242 /// and successor groups.
243 BumpVectorContext BVC
;
245 /// NumNodes - The number of nodes in the graph.
249 /// getNode - Retrieve the node associated with a (Location,State) pair,
250 /// where the 'Location' is a ProgramPoint in the CFG. If no node for
251 /// this pair exists, it is created. IsNew is set to true if
252 /// the node was freshly created.
254 ExplodedNode
* getNode(const ProgramPoint
& L
, const GRState
*State
,
257 ExplodedGraph
* MakeEmptyGraph() const {
258 return new ExplodedGraph();
261 /// addRoot - Add an untyped node to the set of roots.
262 ExplodedNode
* addRoot(ExplodedNode
* V
) {
267 /// addEndOfPath - Add an untyped node to the set of EOP nodes.
268 ExplodedNode
* addEndOfPath(ExplodedNode
* V
) {
269 EndNodes
.push_back(V
);
273 ExplodedGraph() : NumNodes(0) {}
277 unsigned num_roots() const { return Roots
.size(); }
278 unsigned num_eops() const { return EndNodes
.size(); }
280 bool empty() const { return NumNodes
== 0; }
281 unsigned size() const { return NumNodes
; }
284 typedef ExplodedNode NodeTy
;
285 typedef llvm::FoldingSet
<ExplodedNode
> AllNodesTy
;
286 typedef NodeTy
** roots_iterator
;
287 typedef NodeTy
* const * const_roots_iterator
;
288 typedef NodeTy
** eop_iterator
;
289 typedef NodeTy
* const * const_eop_iterator
;
290 typedef AllNodesTy::iterator node_iterator
;
291 typedef AllNodesTy::const_iterator const_node_iterator
;
293 node_iterator
nodes_begin() { return Nodes
.begin(); }
295 node_iterator
nodes_end() { return Nodes
.end(); }
297 const_node_iterator
nodes_begin() const { return Nodes
.begin(); }
299 const_node_iterator
nodes_end() const { return Nodes
.end(); }
301 roots_iterator
roots_begin() { return Roots
.begin(); }
303 roots_iterator
roots_end() { return Roots
.end(); }
305 const_roots_iterator
roots_begin() const { return Roots
.begin(); }
307 const_roots_iterator
roots_end() const { return Roots
.end(); }
309 eop_iterator
eop_begin() { return EndNodes
.begin(); }
311 eop_iterator
eop_end() { return EndNodes
.end(); }
313 const_eop_iterator
eop_begin() const { return EndNodes
.begin(); }
315 const_eop_iterator
eop_end() const { return EndNodes
.end(); }
317 llvm::BumpPtrAllocator
& getAllocator() { return BVC
.getAllocator(); }
318 BumpVectorContext
&getNodeAllocator() { return BVC
; }
320 typedef llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*> NodeMap
;
322 std::pair
<ExplodedGraph
*, InterExplodedGraphMap
*>
323 Trim(const NodeTy
* const* NBeg
, const NodeTy
* const* NEnd
,
324 llvm::DenseMap
<const void*, const void*> *InverseMap
= 0) const;
326 ExplodedGraph
* TrimInternal(const ExplodedNode
* const * NBeg
,
327 const ExplodedNode
* const * NEnd
,
328 InterExplodedGraphMap
*M
,
329 llvm::DenseMap
<const void*, const void*> *InverseMap
) const;
332 class ExplodedNodeSet
{
333 typedef llvm::SmallPtrSet
<ExplodedNode
*,5> ImplTy
;
337 ExplodedNodeSet(ExplodedNode
* N
) {
338 assert (N
&& !static_cast<ExplodedNode
*>(N
)->isSink());
344 inline void Add(ExplodedNode
* N
) {
345 if (N
&& !static_cast<ExplodedNode
*>(N
)->isSink()) Impl
.insert(N
);
348 ExplodedNodeSet
& operator=(const ExplodedNodeSet
&X
) {
353 typedef ImplTy::iterator iterator
;
354 typedef ImplTy::const_iterator const_iterator
;
356 unsigned size() const { return Impl
.size(); }
357 bool empty() const { return Impl
.empty(); }
359 void clear() { Impl
.clear(); }
360 void insert(const ExplodedNodeSet
&S
) {
364 Impl
.insert(S
.begin(), S
.end());
367 inline iterator
begin() { return Impl
.begin(); }
368 inline iterator
end() { return Impl
.end(); }
370 inline const_iterator
begin() const { return Impl
.begin(); }
371 inline const_iterator
end() const { return Impl
.end(); }
374 } // end GR namespace
376 } // end clang namespace
381 template<> struct GraphTraits
<clang::ento::ExplodedNode
*> {
382 typedef clang::ento::ExplodedNode NodeType
;
383 typedef NodeType::succ_iterator ChildIteratorType
;
384 typedef llvm::df_iterator
<NodeType
*> nodes_iterator
;
386 static inline NodeType
* getEntryNode(NodeType
* N
) {
390 static inline ChildIteratorType
child_begin(NodeType
* N
) {
391 return N
->succ_begin();
394 static inline ChildIteratorType
child_end(NodeType
* N
) {
395 return N
->succ_end();
398 static inline nodes_iterator
nodes_begin(NodeType
* N
) {
402 static inline nodes_iterator
nodes_end(NodeType
* N
) {
407 template<> struct GraphTraits
<const clang::ento::ExplodedNode
*> {
408 typedef const clang::ento::ExplodedNode NodeType
;
409 typedef NodeType::const_succ_iterator ChildIteratorType
;
410 typedef llvm::df_iterator
<NodeType
*> nodes_iterator
;
412 static inline NodeType
* getEntryNode(NodeType
* N
) {
416 static inline ChildIteratorType
child_begin(NodeType
* N
) {
417 return N
->succ_begin();
420 static inline ChildIteratorType
child_end(NodeType
* N
) {
421 return N
->succ_end();
424 static inline nodes_iterator
nodes_begin(NodeType
* N
) {
428 static inline nodes_iterator
nodes_end(NodeType
* N
) {
433 } // end llvm namespace