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_ANALYSIS_EXPLODEDGRAPH
20 #define LLVM_CLANG_ANALYSIS_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"
41 //===----------------------------------------------------------------------===//
42 // ExplodedGraph "implementation" classes. These classes are not typed to
43 // contain a specific kind of state. Typed-specialized versions are defined
44 // on top of these classes.
45 //===----------------------------------------------------------------------===//
47 class ExplodedNode
: public llvm::FoldingSetNode
{
48 friend class ExplodedGraph
;
49 friend class GRCoreEngine
;
50 friend class GRStmtNodeBuilder
;
51 friend class GRBranchNodeBuilder
;
52 friend class GRIndirectGotoNodeBuilder
;
53 friend class GRSwitchNodeBuilder
;
54 friend class GREndPathNodeBuilder
;
57 enum { Size1
= 0x0, SizeOther
= 0x1, AuxFlag
= 0x2, Mask
= 0x3 };
60 unsigned getKind() const {
64 void* getPtr() const {
66 return reinterpret_cast<void*>(P
& ~Mask
);
69 ExplodedNode
*getNode() const {
70 return reinterpret_cast<ExplodedNode
*>(getPtr());
76 ExplodedNode
**begin() const;
78 ExplodedNode
**end() const;
80 unsigned size() const;
82 bool empty() const { return (P
& ~Mask
) == 0; }
84 void addNode(ExplodedNode
* N
, ExplodedGraph
&G
);
91 bool getFlag() const {
92 return P
& AuxFlag
? true : false;
96 /// Location - The program location (within a function body) associated
98 const ProgramPoint Location
;
100 /// State - The state associated with this node.
101 const GRState
* State
;
103 /// Preds - The predecessors of this node.
106 /// Succs - The successors of this node.
111 explicit ExplodedNode(const ProgramPoint
& loc
, const GRState
* state
)
112 : Location(loc
), State(state
) {}
114 /// getLocation - Returns the edge associated with the given node.
115 ProgramPoint
getLocation() const { return Location
; }
117 const LocationContext
*getLocationContext() const {
118 return getLocation().getLocationContext();
121 const Decl
&getCodeDecl() const { return *getLocationContext()->getDecl(); }
123 CFG
&getCFG() const { return *getLocationContext()->getCFG(); }
125 ParentMap
&getParentMap() const {return getLocationContext()->getParentMap();}
127 LiveVariables
&getLiveVariables() const {
128 return *getLocationContext()->getLiveVariables();
131 const GRState
* getState() const { return State
; }
133 template <typename T
>
134 const T
* getLocationAs() const { return llvm::dyn_cast
<T
>(&Location
); }
136 static void Profile(llvm::FoldingSetNodeID
&ID
,
137 const ProgramPoint
& Loc
, const GRState
* state
) {
139 ID
.AddPointer(state
);
142 void Profile(llvm::FoldingSetNodeID
& ID
) const {
143 Profile(ID
, getLocation(), getState());
146 /// addPredeccessor - Adds a predecessor to the current node, and
147 /// in tandem add this node as a successor of the other node.
148 void addPredecessor(ExplodedNode
* V
, ExplodedGraph
&G
);
150 unsigned succ_size() const { return Succs
.size(); }
151 unsigned pred_size() const { return Preds
.size(); }
152 bool succ_empty() const { return Succs
.empty(); }
153 bool pred_empty() const { return Preds
.empty(); }
155 bool isSink() const { return Succs
.getFlag(); }
156 void markAsSink() { Succs
.setFlag(); }
158 ExplodedNode
* getFirstPred() {
159 return pred_empty() ? NULL
: *(pred_begin());
162 const ExplodedNode
* getFirstPred() const {
163 return const_cast<ExplodedNode
*>(this)->getFirstPred();
166 // Iterators over successor and predecessor vertices.
167 typedef ExplodedNode
** succ_iterator
;
168 typedef const ExplodedNode
* const * const_succ_iterator
;
169 typedef ExplodedNode
** pred_iterator
;
170 typedef const ExplodedNode
* const * const_pred_iterator
;
172 pred_iterator
pred_begin() { return Preds
.begin(); }
173 pred_iterator
pred_end() { return Preds
.end(); }
175 const_pred_iterator
pred_begin() const {
176 return const_cast<ExplodedNode
*>(this)->pred_begin();
178 const_pred_iterator
pred_end() const {
179 return const_cast<ExplodedNode
*>(this)->pred_end();
182 succ_iterator
succ_begin() { return Succs
.begin(); }
183 succ_iterator
succ_end() { return Succs
.end(); }
185 const_succ_iterator
succ_begin() const {
186 return const_cast<ExplodedNode
*>(this)->succ_begin();
188 const_succ_iterator
succ_end() const {
189 return const_cast<ExplodedNode
*>(this)->succ_end();
199 virtual void AddEdge(ExplodedNode
* Src
, ExplodedNode
* Dst
) = 0;
202 static void SetAuditor(Auditor
* A
);
205 // FIXME: Is this class necessary?
206 class InterExplodedGraphMap
{
207 llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*> M
;
208 friend class ExplodedGraph
;
211 ExplodedNode
* getMappedNode(const ExplodedNode
* N
) const;
213 InterExplodedGraphMap() {}
214 virtual ~InterExplodedGraphMap() {}
217 class ExplodedGraph
{
219 friend class GRCoreEngine
;
222 typedef llvm::SmallVector
<ExplodedNode
*,2> RootsTy
;
223 typedef llvm::SmallVector
<ExplodedNode
*,10> EndNodesTy
;
225 /// Roots - The roots of the simulation graph. Usually there will be only
226 /// one, but clients are free to establish multiple subgraphs within a single
227 /// SimulGraph. Moreover, these subgraphs can often merge when paths from
228 /// different roots reach the same state at the same program location.
231 /// EndNodes - The nodes in the simulation graph which have been
232 /// specially marked as the endpoint of an abstract simulation path.
235 /// Nodes - The nodes in the graph.
236 llvm::FoldingSet
<ExplodedNode
> Nodes
;
238 /// BVC - Allocator and context for allocating nodes and their predecessor
239 /// and successor groups.
240 BumpVectorContext BVC
;
242 /// NumNodes - The number of nodes in the graph.
246 /// getNode - Retrieve the node associated with a (Location,State) pair,
247 /// where the 'Location' is a ProgramPoint in the CFG. If no node for
248 /// this pair exists, it is created. IsNew is set to true if
249 /// the node was freshly created.
251 ExplodedNode
* getNode(const ProgramPoint
& L
, const GRState
*State
,
254 ExplodedGraph
* MakeEmptyGraph() const {
255 return new ExplodedGraph();
258 /// addRoot - Add an untyped node to the set of roots.
259 ExplodedNode
* addRoot(ExplodedNode
* V
) {
264 /// addEndOfPath - Add an untyped node to the set of EOP nodes.
265 ExplodedNode
* addEndOfPath(ExplodedNode
* V
) {
266 EndNodes
.push_back(V
);
270 ExplodedGraph() : NumNodes(0) {}
274 unsigned num_roots() const { return Roots
.size(); }
275 unsigned num_eops() const { return EndNodes
.size(); }
277 bool empty() const { return NumNodes
== 0; }
278 unsigned size() const { return NumNodes
; }
281 typedef ExplodedNode NodeTy
;
282 typedef llvm::FoldingSet
<ExplodedNode
> AllNodesTy
;
283 typedef NodeTy
** roots_iterator
;
284 typedef NodeTy
* const * const_roots_iterator
;
285 typedef NodeTy
** eop_iterator
;
286 typedef NodeTy
* const * const_eop_iterator
;
287 typedef AllNodesTy::iterator node_iterator
;
288 typedef AllNodesTy::const_iterator const_node_iterator
;
290 node_iterator
nodes_begin() { return Nodes
.begin(); }
292 node_iterator
nodes_end() { return Nodes
.end(); }
294 const_node_iterator
nodes_begin() const { return Nodes
.begin(); }
296 const_node_iterator
nodes_end() const { return Nodes
.end(); }
298 roots_iterator
roots_begin() { return Roots
.begin(); }
300 roots_iterator
roots_end() { return Roots
.end(); }
302 const_roots_iterator
roots_begin() const { return Roots
.begin(); }
304 const_roots_iterator
roots_end() const { return Roots
.end(); }
306 eop_iterator
eop_begin() { return EndNodes
.begin(); }
308 eop_iterator
eop_end() { return EndNodes
.end(); }
310 const_eop_iterator
eop_begin() const { return EndNodes
.begin(); }
312 const_eop_iterator
eop_end() const { return EndNodes
.end(); }
314 llvm::BumpPtrAllocator
& getAllocator() { return BVC
.getAllocator(); }
315 BumpVectorContext
&getNodeAllocator() { return BVC
; }
317 typedef llvm::DenseMap
<const ExplodedNode
*, ExplodedNode
*> NodeMap
;
319 std::pair
<ExplodedGraph
*, InterExplodedGraphMap
*>
320 Trim(const NodeTy
* const* NBeg
, const NodeTy
* const* NEnd
,
321 llvm::DenseMap
<const void*, const void*> *InverseMap
= 0) const;
323 ExplodedGraph
* TrimInternal(const ExplodedNode
* const * NBeg
,
324 const ExplodedNode
* const * NEnd
,
325 InterExplodedGraphMap
*M
,
326 llvm::DenseMap
<const void*, const void*> *InverseMap
) const;
329 class ExplodedNodeSet
{
330 typedef llvm::SmallPtrSet
<ExplodedNode
*,5> ImplTy
;
334 ExplodedNodeSet(ExplodedNode
* N
) {
335 assert (N
&& !static_cast<ExplodedNode
*>(N
)->isSink());
341 inline void Add(ExplodedNode
* N
) {
342 if (N
&& !static_cast<ExplodedNode
*>(N
)->isSink()) Impl
.insert(N
);
345 ExplodedNodeSet
& operator=(const ExplodedNodeSet
&X
) {
350 typedef ImplTy::iterator iterator
;
351 typedef ImplTy::const_iterator const_iterator
;
353 unsigned size() const { return Impl
.size(); }
354 bool empty() const { return Impl
.empty(); }
356 void clear() { Impl
.clear(); }
357 void insert(const ExplodedNodeSet
&S
) {
361 Impl
.insert(S
.begin(), S
.end());
364 inline iterator
begin() { return Impl
.begin(); }
365 inline iterator
end() { return Impl
.end(); }
367 inline const_iterator
begin() const { return Impl
.begin(); }
368 inline const_iterator
end() const { return Impl
.end(); }
371 } // end clang namespace
376 template<> struct GraphTraits
<clang::ExplodedNode
*> {
377 typedef clang::ExplodedNode NodeType
;
378 typedef NodeType::succ_iterator ChildIteratorType
;
379 typedef llvm::df_iterator
<NodeType
*> nodes_iterator
;
381 static inline NodeType
* getEntryNode(NodeType
* N
) {
385 static inline ChildIteratorType
child_begin(NodeType
* N
) {
386 return N
->succ_begin();
389 static inline ChildIteratorType
child_end(NodeType
* N
) {
390 return N
->succ_end();
393 static inline nodes_iterator
nodes_begin(NodeType
* N
) {
397 static inline nodes_iterator
nodes_end(NodeType
* N
) {
402 template<> struct GraphTraits
<const clang::ExplodedNode
*> {
403 typedef const clang::ExplodedNode NodeType
;
404 typedef NodeType::const_succ_iterator ChildIteratorType
;
405 typedef llvm::df_iterator
<NodeType
*> nodes_iterator
;
407 static inline NodeType
* getEntryNode(NodeType
* N
) {
411 static inline ChildIteratorType
child_begin(NodeType
* N
) {
412 return N
->succ_begin();
415 static inline ChildIteratorType
child_end(NodeType
* N
) {
416 return N
->succ_end();
419 static inline nodes_iterator
nodes_begin(NodeType
* N
) {
423 static inline nodes_iterator
nodes_end(NodeType
* N
) {
428 } // end llvm namespace