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