clang  7.0.0svn
ExplodedGraph.h
Go to the documentation of this file.
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"
27 #include "llvm/ADT/DepthFirstIterator.h"
28 #include "llvm/ADT/FoldingSet.h"
29 #include "llvm/ADT/GraphTraits.h"
30 #include "llvm/ADT/SetVector.h"
31 #include "llvm/Support/Allocator.h"
32 #include "llvm/Support/Casting.h"
33 #include <memory>
34 #include <utility>
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;
60  friend class SwitchNodeBuilder;
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:
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 
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.
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.
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:
125  bool IsSink)
126  : Location(loc), State(std::move(state)), Succs(IsSink) {
127  assert(isSink() == IsSink);
128  }
129 
130  /// getLocation - Returns the edge associated with the given node.
131  ProgramPoint getLocation() const { return Location; }
132 
134  return getLocation().getLocationContext();
135  }
136 
139  }
140 
141  const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
142 
143  CFG &getCFG() const { return *getLocationContext()->getCFG(); }
144 
146 
147  template <typename T>
148  T &getAnalysis() const {
149  return *getLocationContext()->getAnalysis<T>();
150  }
151 
152  const ProgramStateRef &getState() const { return State; }
153 
154  template <typename T>
155  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
156  return Location.getAs<T>();
157  }
158 
159  /// Get the value of an arbitrary expression at this node.
160  SVal getSVal(const Stmt *S) const {
161  return getState()->getSVal(S, getLocationContext());
162  }
163 
164  static void Profile(llvm::FoldingSetNodeID &ID,
165  const ProgramPoint &Loc,
166  const ProgramStateRef &state,
167  bool IsSink) {
168  ID.Add(Loc);
169  ID.AddPointer(state.get());
170  ID.AddBoolean(IsSink);
171  }
172 
173  void Profile(llvm::FoldingSetNodeID& ID) const {
174  // We avoid copy constructors by not using accessors.
175  Profile(ID, Location, State, isSink());
176  }
177 
178  /// addPredeccessor - Adds a predecessor to the current node, and
179  /// in tandem add this node as a successor of the other node.
181 
182  unsigned succ_size() const { return Succs.size(); }
183  unsigned pred_size() const { return Preds.size(); }
184  bool succ_empty() const { return Succs.empty(); }
185  bool pred_empty() const { return Preds.empty(); }
186 
187  bool isSink() const { return Succs.getFlag(); }
188 
189  bool hasSinglePred() const {
190  return (pred_size() == 1);
191  }
192 
194  return pred_empty() ? nullptr : *(pred_begin());
195  }
196 
197  const ExplodedNode *getFirstPred() const {
198  return const_cast<ExplodedNode*>(this)->getFirstPred();
199  }
200 
201  const ExplodedNode *getFirstSucc() const {
202  return succ_empty() ? nullptr : *(succ_begin());
203  }
204 
205  // Iterators over successor and predecessor vertices.
206  typedef ExplodedNode* const * succ_iterator;
207  typedef const ExplodedNode* const * const_succ_iterator;
208  typedef ExplodedNode* const * pred_iterator;
209  typedef const ExplodedNode* const * const_pred_iterator;
210 
211  pred_iterator pred_begin() { return Preds.begin(); }
212  pred_iterator pred_end() { return Preds.end(); }
213 
214  const_pred_iterator pred_begin() const {
215  return const_cast<ExplodedNode*>(this)->pred_begin();
216  }
217  const_pred_iterator pred_end() const {
218  return const_cast<ExplodedNode*>(this)->pred_end();
219  }
220 
221  succ_iterator succ_begin() { return Succs.begin(); }
222  succ_iterator succ_end() { return Succs.end(); }
223 
224  const_succ_iterator succ_begin() const {
225  return const_cast<ExplodedNode*>(this)->succ_begin();
226  }
227  const_succ_iterator succ_end() const {
228  return const_cast<ExplodedNode*>(this)->succ_end();
229  }
230 
231  // For debugging.
232 
233 public:
234 
235  class Auditor {
236  public:
237  virtual ~Auditor();
238  virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0;
239  };
240 
241  static void SetAuditor(Auditor* A);
242 
243 private:
244  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
245  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
246 };
247 
248 typedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>
250 
252 protected:
253  friend class CoreEngine;
254 
255  // Type definitions.
256  typedef std::vector<ExplodedNode *> NodeVector;
257 
258  /// The roots of the simulation graph. Usually there will be only
259  /// one, but clients are free to establish multiple subgraphs within a single
260  /// SimulGraph. Moreover, these subgraphs can often merge when paths from
261  /// different roots reach the same state at the same program location.
262  NodeVector Roots;
263 
264  /// The nodes in the simulation graph which have been
265  /// specially marked as the endpoint of an abstract simulation path.
266  NodeVector EndNodes;
267 
268  /// Nodes - The nodes in the graph.
269  llvm::FoldingSet<ExplodedNode> Nodes;
270 
271  /// BVC - Allocator and context for allocating nodes and their predecessor
272  /// and successor groups.
274 
275  /// NumNodes - The number of nodes in the graph.
276  unsigned NumNodes;
277 
278  /// A list of recently allocated nodes that can potentially be recycled.
279  NodeVector ChangedNodes;
280 
281  /// A list of nodes that can be reused.
282  NodeVector FreeNodes;
283 
284  /// Determines how often nodes are reclaimed.
285  ///
286  /// If this is 0, nodes will never be reclaimed.
288 
289  /// Counter to determine when to reclaim nodes.
290  unsigned ReclaimCounter;
291 
292 public:
293 
294  /// \brief Retrieve the node associated with a (Location,State) pair,
295  /// where the 'Location' is a ProgramPoint in the CFG. If no node for
296  /// this pair exists, it is created. IsNew is set to true if
297  /// the node was freshly created.
298  ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
299  bool IsSink = false,
300  bool* IsNew = nullptr);
301 
302  /// \brief Create a node for a (Location, State) pair,
303  /// but don't store it for deduplication later. This
304  /// is useful when copying an already completed
305  /// ExplodedGraph for further processing.
306  ExplodedNode *createUncachedNode(const ProgramPoint &L,
308  bool IsSink = false);
309 
310  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
311  return llvm::make_unique<ExplodedGraph>();
312  }
313 
314  /// addRoot - Add an untyped node to the set of roots.
316  Roots.push_back(V);
317  return V;
318  }
319 
320  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
322  EndNodes.push_back(V);
323  return V;
324  }
325 
326  ExplodedGraph();
327 
328  ~ExplodedGraph();
329 
330  unsigned num_roots() const { return Roots.size(); }
331  unsigned num_eops() const { return EndNodes.size(); }
332 
333  bool empty() const { return NumNodes == 0; }
334  unsigned size() const { return NumNodes; }
335 
336  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
337 
338  // Iterators.
340  typedef llvm::FoldingSet<ExplodedNode> AllNodesTy;
341  typedef NodeVector::iterator roots_iterator;
342  typedef NodeVector::const_iterator const_roots_iterator;
343  typedef NodeVector::iterator eop_iterator;
344  typedef NodeVector::const_iterator const_eop_iterator;
345  typedef AllNodesTy::iterator node_iterator;
346  typedef AllNodesTy::const_iterator const_node_iterator;
347 
348  node_iterator nodes_begin() { return Nodes.begin(); }
349 
350  node_iterator nodes_end() { return Nodes.end(); }
351 
352  const_node_iterator nodes_begin() const { return Nodes.begin(); }
353 
354  const_node_iterator nodes_end() const { return Nodes.end(); }
355 
356  roots_iterator roots_begin() { return Roots.begin(); }
357 
358  roots_iterator roots_end() { return Roots.end(); }
359 
360  const_roots_iterator roots_begin() const { return Roots.begin(); }
361 
362  const_roots_iterator roots_end() const { return Roots.end(); }
363 
364  eop_iterator eop_begin() { return EndNodes.begin(); }
365 
366  eop_iterator eop_end() { return EndNodes.end(); }
367 
368  const_eop_iterator eop_begin() const { return EndNodes.begin(); }
369 
370  const_eop_iterator eop_end() const { return EndNodes.end(); }
371 
372  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
374 
375  typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap;
376 
377  /// Creates a trimmed version of the graph that only contains paths leading
378  /// to the given nodes.
379  ///
380  /// \param Nodes The nodes which must appear in the final graph. Presumably
381  /// these are end-of-path nodes (i.e. they have no successors).
382  /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
383  /// the returned graph.
384  /// \param[out] InverseMap An optional map from nodes in the returned graph to
385  /// nodes in this graph.
386  /// \returns The trimmed graph
387  std::unique_ptr<ExplodedGraph>
388  trim(ArrayRef<const NodeTy *> Nodes,
389  InterExplodedGraphMap *ForwardMap = nullptr,
390  InterExplodedGraphMap *InverseMap = nullptr) const;
391 
392  /// Enable tracking of recently allocated nodes for potential reclamation
393  /// when calling reclaimRecentlyAllocatedNodes().
394  void enableNodeReclamation(unsigned Interval) {
395  ReclaimCounter = ReclaimNodeInterval = Interval;
396  }
397 
398  /// Reclaim "uninteresting" nodes created since the last time this method
399  /// was called.
400  void reclaimRecentlyAllocatedNodes();
401 
402  /// \brief Returns true if nodes for the given expression kind are always
403  /// kept around.
404  static bool isInterestingLValueExpr(const Expr *Ex);
405 
406 private:
407  bool shouldCollect(const ExplodedNode *node);
408  void collectNode(ExplodedNode *node);
409 };
410 
413  ImplTy Impl;
414 
415 public:
417  assert (N && !static_cast<ExplodedNode*>(N)->isSink());
418  Impl.insert(N);
419  }
420 
422 
423  inline void Add(ExplodedNode *N) {
424  if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
425  }
426 
427  typedef ImplTy::iterator iterator;
428  typedef ImplTy::const_iterator const_iterator;
429 
430  unsigned size() const { return Impl.size(); }
431  bool empty() const { return Impl.empty(); }
432  bool erase(ExplodedNode *N) { return Impl.remove(N); }
433 
434  void clear() { Impl.clear(); }
435  void insert(const ExplodedNodeSet &S) {
436  assert(&S != this);
437  if (empty())
438  Impl = S.Impl;
439  else
440  Impl.insert(S.begin(), S.end());
441  }
442 
443  inline iterator begin() { return Impl.begin(); }
444  inline iterator end() { return Impl.end(); }
445 
446  inline const_iterator begin() const { return Impl.begin(); }
447  inline const_iterator end() const { return Impl.end(); }
448 };
449 
450 } // end GR namespace
451 
452 } // end clang namespace
453 
454 // GraphTraits
455 
456 namespace llvm {
457  template<> struct GraphTraits<clang::ento::ExplodedNode*> {
460  typedef llvm::df_iterator<NodeRef> nodes_iterator;
461 
462  static NodeRef getEntryNode(NodeRef N) { return N; }
463 
464  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
465 
466  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
467 
468  static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
469 
470  static nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
471  };
472 
473  template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
476  typedef llvm::df_iterator<NodeRef> nodes_iterator;
477 
478  static NodeRef getEntryNode(NodeRef N) { return N; }
479 
480  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
481 
482  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
483 
484  static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
485 
486  static nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
487  };
488 
489 } // end llvm namespace
490 
491 #endif
clang::ento::ExplodedNode::succ_iterator ChildIteratorType
const_iterator end() const
unsigned ReclaimCounter
Counter to determine when to reclaim nodes.
void Profile(llvm::FoldingSetNodeID &ID) const
ExplodedNode *const * succ_iterator
const_roots_iterator roots_begin() const
const ExplodedNode * getFirstPred() const
AllNodesTy::const_iterator const_node_iterator
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:26
Stmt - This represents one statement.
Definition: Stmt.h:66
static ChildIteratorType child_begin(NodeRef N)
NodeVector FreeNodes
A list of nodes that can be reused.
unsigned NumNodes
NumNodes - The number of nodes in the graph.
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
const_eop_iterator eop_begin() const
StringRef P
const_succ_iterator succ_begin() const
const_node_iterator nodes_end() const
static nodes_iterator nodes_begin(NodeRef N)
const ProgramStateRef & getState() const
llvm::BumpPtrAllocator & getAllocator()
Definition: BumpVector.h:56
const_pred_iterator pred_end() const
ImplTy::const_iterator const_iterator
const_succ_iterator succ_end() const
static ChildIteratorType child_end(NodeRef N)
const Decl & getCodeDecl() const
llvm::DenseMap< const ExplodedNode *, ExplodedNode * > NodeMap
roots_iterator roots_begin()
NodeVector ChangedNodes
A list of recently allocated nodes that can potentially be recycled.
const_eop_iterator eop_end() const
LineState State
NodeVector EndNodes
The nodes in the simulation graph which have been specially marked as the endpoint of an abstract sim...
succ_iterator succ_begin()
Definition: Format.h:2011
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
i32 captured_struct **param SharedsTy A type which contains references the shared variables *param Shareds Context with the list of shared variables from the p *TaskFunction *param Data Additional data for task generation like final * state
Optional< T > getLocationAs() const LLVM_LVALUE_FUNCTION
void enableNodeReclamation(unsigned Interval)
Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAll...
unsigned succ_size() const
static nodes_iterator nodes_end(NodeRef N)
const StackFrameContext * getCurrentStackFrame() const
const LocationContext * getLocationContext() const
std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const
const_roots_iterator roots_end() const
ExplodedNode * getFirstPred()
unsigned pred_size() const
clang::ento::ExplodedNode::const_succ_iterator ChildIteratorType
std::vector< ExplodedNode * > NodeVector
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
Expr - This represents one expression.
Definition: Expr.h:106
pred_iterator pred_end()
CFG - Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:979
const FunctionProtoType * T
This is the simplest builder which generates nodes in the ExplodedGraph.
Definition: CoreEngine.h:212
void Add(ExplodedNode *N)
unsigned num_roots() const
const_node_iterator nodes_begin() const
static ChildIteratorType child_begin(NodeRef N)
llvm::FoldingSet< ExplodedNode > AllNodesTy
static void Profile(llvm::FoldingSetNodeID &ID, const ProgramPoint &Loc, const ProgramStateRef &state, bool IsSink)
NodeVector::const_iterator const_eop_iterator
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
Definition: opencl-c.h:82
ParentMap & getParentMap() const
ExplodedNode *const * pred_iterator
unsigned ReclaimNodeInterval
Determines how often nodes are reclaimed.
node_iterator nodes_begin()
BumpVectorContext BVC
BVC - Allocator and context for allocating nodes and their predecessor and successor groups...
const ExplodedNode *const * const_succ_iterator
roots_iterator roots_end()
llvm::FoldingSet< ExplodedNode > Nodes
Nodes - The nodes in the graph.
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:63
ParentMap & getParentMap() const
SVal getSVal(const Stmt *S) const
Get the value of an arbitrary expression at this node.
void insert(const ExplodedNodeSet &S)
CoreEngine - Implements the core logic of the graph-reachability analysis.
Definition: CoreEngine.h:44
Dataflow Directional Tag Classes.
BumpVectorContext & getNodeAllocator()
ExplodedNodeSet(ExplodedNode *N)
NodeVector Roots
The roots of the simulation graph.
const ExplodedNode * getFirstSucc() const
BranchNodeBuilder is responsible for constructing the nodes corresponding to the two branches of the ...
Definition: CoreEngine.h:403
NodeVector::iterator roots_iterator
ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, bool IsSink)
const Decl * getDecl() const
void reserve(unsigned NodeCount)
const ExplodedNode *const * const_pred_iterator
static ChildIteratorType child_end(NodeRef N)
succ_iterator succ_end()
static void SetAuditor(Auditor *A)
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:180
NodeVector::iterator eop_iterator
friend class EndOfFunctionNodeBuilder
Definition: ExplodedGraph.h:61
bool erase(ExplodedNode *N)
unsigned num_eops() const
pred_iterator pred_begin()
llvm::BumpPtrAllocator & getAllocator()
NodeVector::const_iterator const_roots_iterator
AllNodesTy::iterator node_iterator
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
const StackFrameContext * getStackFrame() const
const_pred_iterator pred_begin() const
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:152
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
const_iterator begin() const