• 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 <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 
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 
MakeEmptyGraph()298   std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
299     return llvm::make_unique<ExplodedGraph>();
300   }
301 
302   /// addRoot - Add an untyped node to the set of roots.
addRoot(ExplodedNode * V)303   ExplodedNode *addRoot(ExplodedNode *V) {
304     Roots.push_back(V);
305     return V;
306   }
307 
308   /// addEndOfPath - Add an untyped node to the set of EOP nodes.
addEndOfPath(ExplodedNode * V)309   ExplodedNode *addEndOfPath(ExplodedNode *V) {
310     EndNodes.push_back(V);
311     return V;
312   }
313 
314   ExplodedGraph();
315 
316   ~ExplodedGraph();
317 
num_roots()318   unsigned num_roots() const { return Roots.size(); }
num_eops()319   unsigned num_eops() const { return EndNodes.size(); }
320 
empty()321   bool empty() const { return NumNodes == 0; }
size()322   unsigned size() const { return NumNodes; }
323 
324   // Iterators.
325   typedef ExplodedNode                        NodeTy;
326   typedef llvm::FoldingSet<ExplodedNode>      AllNodesTy;
327   typedef NodeVector::iterator                roots_iterator;
328   typedef NodeVector::const_iterator          const_roots_iterator;
329   typedef NodeVector::iterator                eop_iterator;
330   typedef NodeVector::const_iterator          const_eop_iterator;
331   typedef AllNodesTy::iterator                node_iterator;
332   typedef AllNodesTy::const_iterator          const_node_iterator;
333 
nodes_begin()334   node_iterator nodes_begin() { return Nodes.begin(); }
335 
nodes_end()336   node_iterator nodes_end() { return Nodes.end(); }
337 
nodes_begin()338   const_node_iterator nodes_begin() const { return Nodes.begin(); }
339 
nodes_end()340   const_node_iterator nodes_end() const { return Nodes.end(); }
341 
roots_begin()342   roots_iterator roots_begin() { return Roots.begin(); }
343 
roots_end()344   roots_iterator roots_end() { return Roots.end(); }
345 
roots_begin()346   const_roots_iterator roots_begin() const { return Roots.begin(); }
347 
roots_end()348   const_roots_iterator roots_end() const { return Roots.end(); }
349 
eop_begin()350   eop_iterator eop_begin() { return EndNodes.begin(); }
351 
eop_end()352   eop_iterator eop_end() { return EndNodes.end(); }
353 
eop_begin()354   const_eop_iterator eop_begin() const { return EndNodes.begin(); }
355 
eop_end()356   const_eop_iterator eop_end() const { return EndNodes.end(); }
357 
getAllocator()358   llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
getNodeAllocator()359   BumpVectorContext &getNodeAllocator() { return BVC; }
360 
361   typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap;
362 
363   /// Creates a trimmed version of the graph that only contains paths leading
364   /// to the given nodes.
365   ///
366   /// \param Nodes The nodes which must appear in the final graph. Presumably
367   ///              these are end-of-path nodes (i.e. they have no successors).
368   /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
369   ///                        the returned graph.
370   /// \param[out] InverseMap An optional map from nodes in the returned graph to
371   ///                        nodes in this graph.
372   /// \returns The trimmed graph
373   std::unique_ptr<ExplodedGraph>
374   trim(ArrayRef<const NodeTy *> Nodes,
375        InterExplodedGraphMap *ForwardMap = nullptr,
376        InterExplodedGraphMap *InverseMap = nullptr) const;
377 
378   /// Enable tracking of recently allocated nodes for potential reclamation
379   /// when calling reclaimRecentlyAllocatedNodes().
enableNodeReclamation(unsigned Interval)380   void enableNodeReclamation(unsigned Interval) {
381     ReclaimCounter = ReclaimNodeInterval = Interval;
382   }
383 
384   /// Reclaim "uninteresting" nodes created since the last time this method
385   /// was called.
386   void reclaimRecentlyAllocatedNodes();
387 
388   /// \brief Returns true if nodes for the given expression kind are always
389   ///        kept around.
390   static bool isInterestingLValueExpr(const Expr *Ex);
391 
392 private:
393   bool shouldCollect(const ExplodedNode *node);
394   void collectNode(ExplodedNode *node);
395 };
396 
397 class ExplodedNodeSet {
398   typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy;
399   ImplTy Impl;
400 
401 public:
ExplodedNodeSet(ExplodedNode * N)402   ExplodedNodeSet(ExplodedNode *N) {
403     assert (N && !static_cast<ExplodedNode*>(N)->isSink());
404     Impl.insert(N);
405   }
406 
ExplodedNodeSet()407   ExplodedNodeSet() {}
408 
Add(ExplodedNode * N)409   inline void Add(ExplodedNode *N) {
410     if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
411   }
412 
413   typedef ImplTy::iterator       iterator;
414   typedef ImplTy::const_iterator const_iterator;
415 
size()416   unsigned size() const { return Impl.size();  }
empty()417   bool empty()    const { return Impl.empty(); }
erase(ExplodedNode * N)418   bool erase(ExplodedNode *N) { return Impl.erase(N); }
419 
clear()420   void clear() { Impl.clear(); }
insert(const ExplodedNodeSet & S)421   void insert(const ExplodedNodeSet &S) {
422     assert(&S != this);
423     if (empty())
424       Impl = S.Impl;
425     else
426       Impl.insert(S.begin(), S.end());
427   }
428 
begin()429   inline iterator begin() { return Impl.begin(); }
end()430   inline iterator end()   { return Impl.end();   }
431 
begin()432   inline const_iterator begin() const { return Impl.begin(); }
end()433   inline const_iterator end()   const { return Impl.end();   }
434 };
435 
436 } // end GR namespace
437 
438 } // end clang namespace
439 
440 // GraphTraits
441 
442 namespace llvm {
443   template<> struct GraphTraits<clang::ento::ExplodedNode*> {
444     typedef clang::ento::ExplodedNode NodeType;
445     typedef NodeType::succ_iterator  ChildIteratorType;
446     typedef llvm::df_iterator<NodeType*>      nodes_iterator;
447 
448     static inline NodeType* getEntryNode(NodeType* N) {
449       return N;
450     }
451 
452     static inline ChildIteratorType child_begin(NodeType* N) {
453       return N->succ_begin();
454     }
455 
456     static inline ChildIteratorType child_end(NodeType* N) {
457       return N->succ_end();
458     }
459 
460     static inline nodes_iterator nodes_begin(NodeType* N) {
461       return df_begin(N);
462     }
463 
464     static inline nodes_iterator nodes_end(NodeType* N) {
465       return df_end(N);
466     }
467   };
468 
469   template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
470     typedef const clang::ento::ExplodedNode NodeType;
471     typedef NodeType::const_succ_iterator   ChildIteratorType;
472     typedef llvm::df_iterator<NodeType*>       nodes_iterator;
473 
474     static inline NodeType* getEntryNode(NodeType* N) {
475       return N;
476     }
477 
478     static inline ChildIteratorType child_begin(NodeType* N) {
479       return N->succ_begin();
480     }
481 
482     static inline ChildIteratorType child_end(NodeType* N) {
483       return N->succ_end();
484     }
485 
486     static inline nodes_iterator nodes_begin(NodeType* N) {
487       return df_begin(N);
488     }
489 
490     static inline nodes_iterator nodes_end(NodeType* N) {
491       return df_end(N);
492     }
493   };
494 
495 } // end llvm namespace
496 
497 #endif
498