• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- C++ -*-------==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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
15 //  exploded graph.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #ifndef LLVM_CLANG_GR_EXPLODEDGRAPH
20 #define LLVM_CLANG_GR_EXPLODEDGRAPH
21 
22 #include "clang/AST/Decl.h"
23 #include "clang/Analysis/AnalysisContext.h"
24 #include "clang/Analysis/ProgramPoint.h"
25 #include "clang/Analysis/Support/BumpVector.h"
26 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
27 #include "llvm/ADT/DepthFirstIterator.h"
28 #include "llvm/ADT/FoldingSet.h"
29 #include "llvm/ADT/GraphTraits.h"
30 #include "llvm/ADT/OwningPtr.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/Support/Allocator.h"
34 #include "llvm/Support/Casting.h"
35 #include <vector>
36 
37 namespace clang {
38 
39 class CFG;
40 
41 namespace ento {
42 
43 class ExplodedGraph;
44 
45 //===----------------------------------------------------------------------===//
46 // ExplodedGraph "implementation" classes.  These classes are not typed to
47 // contain a specific kind of state.  Typed-specialized versions are defined
48 // on top of these classes.
49 //===----------------------------------------------------------------------===//
50 
51 // ExplodedNode is not constified all over the engine because we need to add
52 // successors to it at any time after creating it.
53 
54 class ExplodedNode : public llvm::FoldingSetNode {
55   friend class ExplodedGraph;
56   friend class CoreEngine;
57   friend class NodeBuilder;
58   friend class BranchNodeBuilder;
59   friend class IndirectGotoNodeBuilder;
60   friend class SwitchNodeBuilder;
61   friend class EndOfFunctionNodeBuilder;
62 
63   /// Efficiently stores a list of ExplodedNodes, or an optional flag.
64   ///
65   /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
66   /// for the case when there is only one node in the group. This is a fairly
67   /// common case in an ExplodedGraph, where most nodes have only one
68   /// predecessor and many have only one successor. It can also be used to
69   /// store a flag rather than a node list, which ExplodedNode uses to mark
70   /// whether a node is a sink. If the flag is set, the group is implicitly
71   /// empty and no nodes may be added.
72   class NodeGroup {
73     // Conceptually a discriminated union. If the low bit is set, the node is
74     // a sink. If the low bit is not set, the pointer refers to the storage
75     // for the nodes in the group.
76     // This is not a PointerIntPair in order to keep the storage type opaque.
77     uintptr_t P;
78 
79   public:
P(Flag)80     NodeGroup(bool Flag = false) : P(Flag) {
81       assert(getFlag() == Flag);
82     }
83 
84     ExplodedNode * const *begin() const;
85 
86     ExplodedNode * const *end() const;
87 
88     unsigned size() const;
89 
empty()90     bool empty() const { return P == 0 || getFlag() != 0; }
91 
92     /// Adds a node to the list.
93     ///
94     /// The group must not have been created with its flag set.
95     void addNode(ExplodedNode *N, ExplodedGraph &G);
96 
97     /// Replaces the single node in this group with a new node.
98     ///
99     /// Note that this should only be used when you know the group was not
100     /// created with its flag set, and that the group is empty or contains
101     /// only a single node.
102     void replaceNode(ExplodedNode *node);
103 
104     /// Returns whether this group was created with its flag set.
getFlag()105     bool getFlag() const {
106       return (P & 1);
107     }
108   };
109 
110   /// Location - The program location (within a function body) associated
111   ///  with this node.
112   const ProgramPoint Location;
113 
114   /// State - The state associated with this node.
115   ProgramStateRef State;
116 
117   /// Preds - The predecessors of this node.
118   NodeGroup Preds;
119 
120   /// Succs - The successors of this node.
121   NodeGroup Succs;
122 
123 public:
124 
ExplodedNode(const ProgramPoint & loc,ProgramStateRef state,bool IsSink)125   explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
126                         bool IsSink)
127     : Location(loc), State(state), Succs(IsSink) {
128     assert(isSink() == IsSink);
129   }
130 
~ExplodedNode()131   ~ExplodedNode() {}
132 
133   /// getLocation - Returns the edge associated with the given node.
getLocation()134   ProgramPoint getLocation() const { return Location; }
135 
getLocationContext()136   const LocationContext *getLocationContext() const {
137     return getLocation().getLocationContext();
138   }
139 
getStackFrame()140   const StackFrameContext *getStackFrame() const {
141     return getLocationContext()->getCurrentStackFrame();
142   }
143 
getCodeDecl()144   const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
145 
getCFG()146   CFG &getCFG() const { return *getLocationContext()->getCFG(); }
147 
getParentMap()148   ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
149 
150   template <typename T>
getAnalysis()151   T &getAnalysis() const {
152     return *getLocationContext()->getAnalysis<T>();
153   }
154 
getState()155   const ProgramStateRef &getState() const { return State; }
156 
157   template <typename T>
getLocationAs()158   Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
159     return Location.getAs<T>();
160   }
161 
Profile(llvm::FoldingSetNodeID & ID,const ProgramPoint & Loc,const ProgramStateRef & state,bool IsSink)162   static void Profile(llvm::FoldingSetNodeID &ID,
163                       const ProgramPoint &Loc,
164                       const ProgramStateRef &state,
165                       bool IsSink) {
166     ID.Add(Loc);
167     ID.AddPointer(state.getPtr());
168     ID.AddBoolean(IsSink);
169   }
170 
Profile(llvm::FoldingSetNodeID & ID)171   void Profile(llvm::FoldingSetNodeID& ID) const {
172     // We avoid copy constructors by not using accessors.
173     Profile(ID, Location, State, isSink());
174   }
175 
176   /// addPredeccessor - Adds a predecessor to the current node, and
177   ///  in tandem add this node as a successor of the other node.
178   void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
179 
succ_size()180   unsigned succ_size() const { return Succs.size(); }
pred_size()181   unsigned pred_size() const { return Preds.size(); }
succ_empty()182   bool succ_empty() const { return Succs.empty(); }
pred_empty()183   bool pred_empty() const { return Preds.empty(); }
184 
isSink()185   bool isSink() const { return Succs.getFlag(); }
186 
hasSinglePred()187    bool hasSinglePred() const {
188     return (pred_size() == 1);
189   }
190 
getFirstPred()191   ExplodedNode *getFirstPred() {
192     return pred_empty() ? NULL : *(pred_begin());
193   }
194 
getFirstPred()195   const ExplodedNode *getFirstPred() const {
196     return const_cast<ExplodedNode*>(this)->getFirstPred();
197   }
198 
getFirstSucc()199   const ExplodedNode *getFirstSucc() const {
200     return succ_empty() ? NULL : *(succ_begin());
201   }
202 
203   // Iterators over successor and predecessor vertices.
204   typedef ExplodedNode*       const *       succ_iterator;
205   typedef const ExplodedNode* const * const_succ_iterator;
206   typedef ExplodedNode*       const *       pred_iterator;
207   typedef const ExplodedNode* const * const_pred_iterator;
208 
pred_begin()209   pred_iterator pred_begin() { return Preds.begin(); }
pred_end()210   pred_iterator pred_end() { return Preds.end(); }
211 
pred_begin()212   const_pred_iterator pred_begin() const {
213     return const_cast<ExplodedNode*>(this)->pred_begin();
214   }
pred_end()215   const_pred_iterator pred_end() const {
216     return const_cast<ExplodedNode*>(this)->pred_end();
217   }
218 
succ_begin()219   succ_iterator succ_begin() { return Succs.begin(); }
succ_end()220   succ_iterator succ_end() { return Succs.end(); }
221 
succ_begin()222   const_succ_iterator succ_begin() const {
223     return const_cast<ExplodedNode*>(this)->succ_begin();
224   }
succ_end()225   const_succ_iterator succ_end() const {
226     return const_cast<ExplodedNode*>(this)->succ_end();
227   }
228 
229   // For debugging.
230 
231 public:
232 
233   class Auditor {
234   public:
235     virtual ~Auditor();
236     virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0;
237   };
238 
239   static void SetAuditor(Auditor* A);
240 
241 private:
replaceSuccessor(ExplodedNode * node)242   void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
replacePredecessor(ExplodedNode * node)243   void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
244 };
245 
246 typedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>
247         InterExplodedGraphMap;
248 
249 class ExplodedGraph {
250 protected:
251   friend class CoreEngine;
252 
253   // Type definitions.
254   typedef std::vector<ExplodedNode *> NodeVector;
255 
256   /// The roots of the simulation graph. Usually there will be only
257   /// one, but clients are free to establish multiple subgraphs within a single
258   /// SimulGraph. Moreover, these subgraphs can often merge when paths from
259   /// different roots reach the same state at the same program location.
260   NodeVector Roots;
261 
262   /// The nodes in the simulation graph which have been
263   /// specially marked as the endpoint of an abstract simulation path.
264   NodeVector EndNodes;
265 
266   /// Nodes - The nodes in the graph.
267   llvm::FoldingSet<ExplodedNode> Nodes;
268 
269   /// BVC - Allocator and context for allocating nodes and their predecessor
270   /// and successor groups.
271   BumpVectorContext BVC;
272 
273   /// NumNodes - The number of nodes in the graph.
274   unsigned NumNodes;
275 
276   /// A list of recently allocated nodes that can potentially be recycled.
277   NodeVector ChangedNodes;
278 
279   /// A list of nodes that can be reused.
280   NodeVector FreeNodes;
281 
282   /// Determines how often nodes are reclaimed.
283   ///
284   /// If this is 0, nodes will never be reclaimed.
285   unsigned ReclaimNodeInterval;
286 
287   /// Counter to determine when to reclaim nodes.
288   unsigned ReclaimCounter;
289 
290 public:
291 
292   /// \brief Retrieve the node associated with a (Location,State) pair,
293   ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
294   ///  this pair exists, it is created. IsNew is set to true if
295   ///  the node was freshly created.
296   ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
297                         bool IsSink = false,
298                         bool* IsNew = 0);
299 
MakeEmptyGraph()300   ExplodedGraph* MakeEmptyGraph() const {
301     return new ExplodedGraph();
302   }
303 
304   /// addRoot - Add an untyped node to the set of roots.
addRoot(ExplodedNode * V)305   ExplodedNode *addRoot(ExplodedNode *V) {
306     Roots.push_back(V);
307     return V;
308   }
309 
310   /// addEndOfPath - Add an untyped node to the set of EOP nodes.
addEndOfPath(ExplodedNode * V)311   ExplodedNode *addEndOfPath(ExplodedNode *V) {
312     EndNodes.push_back(V);
313     return V;
314   }
315 
316   ExplodedGraph();
317 
318   ~ExplodedGraph();
319 
num_roots()320   unsigned num_roots() const { return Roots.size(); }
num_eops()321   unsigned num_eops() const { return EndNodes.size(); }
322 
empty()323   bool empty() const { return NumNodes == 0; }
size()324   unsigned size() const { return NumNodes; }
325 
326   // Iterators.
327   typedef ExplodedNode                        NodeTy;
328   typedef llvm::FoldingSet<ExplodedNode>      AllNodesTy;
329   typedef NodeVector::iterator                roots_iterator;
330   typedef NodeVector::const_iterator          const_roots_iterator;
331   typedef NodeVector::iterator                eop_iterator;
332   typedef NodeVector::const_iterator          const_eop_iterator;
333   typedef AllNodesTy::iterator                node_iterator;
334   typedef AllNodesTy::const_iterator          const_node_iterator;
335 
nodes_begin()336   node_iterator nodes_begin() { return Nodes.begin(); }
337 
nodes_end()338   node_iterator nodes_end() { return Nodes.end(); }
339 
nodes_begin()340   const_node_iterator nodes_begin() const { return Nodes.begin(); }
341 
nodes_end()342   const_node_iterator nodes_end() const { return Nodes.end(); }
343 
roots_begin()344   roots_iterator roots_begin() { return Roots.begin(); }
345 
roots_end()346   roots_iterator roots_end() { return Roots.end(); }
347 
roots_begin()348   const_roots_iterator roots_begin() const { return Roots.begin(); }
349 
roots_end()350   const_roots_iterator roots_end() const { return Roots.end(); }
351 
eop_begin()352   eop_iterator eop_begin() { return EndNodes.begin(); }
353 
eop_end()354   eop_iterator eop_end() { return EndNodes.end(); }
355 
eop_begin()356   const_eop_iterator eop_begin() const { return EndNodes.begin(); }
357 
eop_end()358   const_eop_iterator eop_end() const { return EndNodes.end(); }
359 
getAllocator()360   llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
getNodeAllocator()361   BumpVectorContext &getNodeAllocator() { return BVC; }
362 
363   typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap;
364 
365   /// Creates a trimmed version of the graph that only contains paths leading
366   /// to the given nodes.
367   ///
368   /// \param Nodes The nodes which must appear in the final graph. Presumably
369   ///              these are end-of-path nodes (i.e. they have no successors).
370   /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
371   ///                        the returned graph.
372   /// \param[out] InverseMap An optional map from nodes in the returned graph to
373   ///                        nodes in this graph.
374   /// \returns The trimmed graph
375   ExplodedGraph *trim(ArrayRef<const NodeTy *> Nodes,
376                       InterExplodedGraphMap *ForwardMap = 0,
377                       InterExplodedGraphMap *InverseMap = 0) const;
378 
379   /// Enable tracking of recently allocated nodes for potential reclamation
380   /// when calling reclaimRecentlyAllocatedNodes().
enableNodeReclamation(unsigned Interval)381   void enableNodeReclamation(unsigned Interval) {
382     ReclaimCounter = ReclaimNodeInterval = Interval;
383   }
384 
385   /// Reclaim "uninteresting" nodes created since the last time this method
386   /// was called.
387   void reclaimRecentlyAllocatedNodes();
388 
389   /// \brief Returns true if nodes for the given expression kind are always
390   ///        kept around.
391   static bool isInterestingLValueExpr(const Expr *Ex);
392 
393 private:
394   bool shouldCollect(const ExplodedNode *node);
395   void collectNode(ExplodedNode *node);
396 };
397 
398 class ExplodedNodeSet {
399   typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy;
400   ImplTy Impl;
401 
402 public:
ExplodedNodeSet(ExplodedNode * N)403   ExplodedNodeSet(ExplodedNode *N) {
404     assert (N && !static_cast<ExplodedNode*>(N)->isSink());
405     Impl.insert(N);
406   }
407 
ExplodedNodeSet()408   ExplodedNodeSet() {}
409 
Add(ExplodedNode * N)410   inline void Add(ExplodedNode *N) {
411     if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
412   }
413 
414   typedef ImplTy::iterator       iterator;
415   typedef ImplTy::const_iterator const_iterator;
416 
size()417   unsigned size() const { return Impl.size();  }
empty()418   bool empty()    const { return Impl.empty(); }
erase(ExplodedNode * N)419   bool erase(ExplodedNode *N) { return Impl.erase(N); }
420 
clear()421   void clear() { Impl.clear(); }
insert(const ExplodedNodeSet & S)422   void insert(const ExplodedNodeSet &S) {
423     assert(&S != this);
424     if (empty())
425       Impl = S.Impl;
426     else
427       Impl.insert(S.begin(), S.end());
428   }
429 
begin()430   inline iterator begin() { return Impl.begin(); }
end()431   inline iterator end()   { return Impl.end();   }
432 
begin()433   inline const_iterator begin() const { return Impl.begin(); }
end()434   inline const_iterator end()   const { return Impl.end();   }
435 };
436 
437 } // end GR namespace
438 
439 } // end clang namespace
440 
441 // GraphTraits
442 
443 namespace llvm {
444   template<> struct GraphTraits<clang::ento::ExplodedNode*> {
445     typedef clang::ento::ExplodedNode NodeType;
446     typedef NodeType::succ_iterator  ChildIteratorType;
447     typedef llvm::df_iterator<NodeType*>      nodes_iterator;
448 
449     static inline NodeType* getEntryNode(NodeType* N) {
450       return N;
451     }
452 
453     static inline ChildIteratorType child_begin(NodeType* N) {
454       return N->succ_begin();
455     }
456 
457     static inline ChildIteratorType child_end(NodeType* N) {
458       return N->succ_end();
459     }
460 
461     static inline nodes_iterator nodes_begin(NodeType* N) {
462       return df_begin(N);
463     }
464 
465     static inline nodes_iterator nodes_end(NodeType* N) {
466       return df_end(N);
467     }
468   };
469 
470   template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
471     typedef const clang::ento::ExplodedNode NodeType;
472     typedef NodeType::const_succ_iterator   ChildIteratorType;
473     typedef llvm::df_iterator<NodeType*>       nodes_iterator;
474 
475     static inline NodeType* getEntryNode(NodeType* N) {
476       return N;
477     }
478 
479     static inline ChildIteratorType child_begin(NodeType* N) {
480       return N->succ_begin();
481     }
482 
483     static inline ChildIteratorType child_end(NodeType* N) {
484       return N->succ_end();
485     }
486 
487     static inline nodes_iterator nodes_begin(NodeType* N) {
488       return df_begin(N);
489     }
490 
491     static inline nodes_iterator nodes_end(NodeType* N) {
492       return df_end(N);
493     }
494   };
495 
496 } // end llvm namespace
497 
498 #endif
499