clang  6.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  static void Profile(llvm::FoldingSetNodeID &ID,
160  const ProgramPoint &Loc,
161  const ProgramStateRef &state,
162  bool IsSink) {
163  ID.Add(Loc);
164  ID.AddPointer(state.get());
165  ID.AddBoolean(IsSink);
166  }
167 
168  void Profile(llvm::FoldingSetNodeID& ID) const {
169  // We avoid copy constructors by not using accessors.
170  Profile(ID, Location, State, isSink());
171  }
172 
173  /// addPredeccessor - Adds a predecessor to the current node, and
174  /// in tandem add this node as a successor of the other node.
176 
177  unsigned succ_size() const { return Succs.size(); }
178  unsigned pred_size() const { return Preds.size(); }
179  bool succ_empty() const { return Succs.empty(); }
180  bool pred_empty() const { return Preds.empty(); }
181 
182  bool isSink() const { return Succs.getFlag(); }
183 
184  bool hasSinglePred() const {
185  return (pred_size() == 1);
186  }
187 
189  return pred_empty() ? nullptr : *(pred_begin());
190  }
191 
192  const ExplodedNode *getFirstPred() const {
193  return const_cast<ExplodedNode*>(this)->getFirstPred();
194  }
195 
196  const ExplodedNode *getFirstSucc() const {
197  return succ_empty() ? nullptr : *(succ_begin());
198  }
199 
200  // Iterators over successor and predecessor vertices.
201  typedef ExplodedNode* const * succ_iterator;
202  typedef const ExplodedNode* const * const_succ_iterator;
203  typedef ExplodedNode* const * pred_iterator;
204  typedef const ExplodedNode* const * const_pred_iterator;
205 
206  pred_iterator pred_begin() { return Preds.begin(); }
207  pred_iterator pred_end() { return Preds.end(); }
208 
209  const_pred_iterator pred_begin() const {
210  return const_cast<ExplodedNode*>(this)->pred_begin();
211  }
212  const_pred_iterator pred_end() const {
213  return const_cast<ExplodedNode*>(this)->pred_end();
214  }
215 
216  succ_iterator succ_begin() { return Succs.begin(); }
217  succ_iterator succ_end() { return Succs.end(); }
218 
219  const_succ_iterator succ_begin() const {
220  return const_cast<ExplodedNode*>(this)->succ_begin();
221  }
222  const_succ_iterator succ_end() const {
223  return const_cast<ExplodedNode*>(this)->succ_end();
224  }
225 
226  // For debugging.
227 
228 public:
229 
230  class Auditor {
231  public:
232  virtual ~Auditor();
233  virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0;
234  };
235 
236  static void SetAuditor(Auditor* A);
237 
238 private:
239  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
240  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
241 };
242 
243 typedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>
245 
247 protected:
248  friend class CoreEngine;
249 
250  // Type definitions.
251  typedef std::vector<ExplodedNode *> NodeVector;
252 
253  /// The roots of the simulation graph. Usually there will be only
254  /// one, but clients are free to establish multiple subgraphs within a single
255  /// SimulGraph. Moreover, these subgraphs can often merge when paths from
256  /// different roots reach the same state at the same program location.
257  NodeVector Roots;
258 
259  /// The nodes in the simulation graph which have been
260  /// specially marked as the endpoint of an abstract simulation path.
261  NodeVector EndNodes;
262 
263  /// Nodes - The nodes in the graph.
264  llvm::FoldingSet<ExplodedNode> Nodes;
265 
266  /// BVC - Allocator and context for allocating nodes and their predecessor
267  /// and successor groups.
269 
270  /// NumNodes - The number of nodes in the graph.
271  unsigned NumNodes;
272 
273  /// A list of recently allocated nodes that can potentially be recycled.
274  NodeVector ChangedNodes;
275 
276  /// A list of nodes that can be reused.
277  NodeVector FreeNodes;
278 
279  /// Determines how often nodes are reclaimed.
280  ///
281  /// If this is 0, nodes will never be reclaimed.
283 
284  /// Counter to determine when to reclaim nodes.
285  unsigned ReclaimCounter;
286 
287 public:
288 
289  /// \brief Retrieve the node associated with a (Location,State) pair,
290  /// where the 'Location' is a ProgramPoint in the CFG. If no node for
291  /// this pair exists, it is created. IsNew is set to true if
292  /// the node was freshly created.
293  ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
294  bool IsSink = false,
295  bool* IsNew = nullptr);
296 
297  /// \brief Create a node for a (Location, State) pair,
298  /// but don't store it for deduplication later. This
299  /// is useful when copying an already completed
300  /// ExplodedGraph for further processing.
301  ExplodedNode *createUncachedNode(const ProgramPoint &L,
303  bool IsSink = false);
304 
305  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
306  return llvm::make_unique<ExplodedGraph>();
307  }
308 
309  /// addRoot - Add an untyped node to the set of roots.
311  Roots.push_back(V);
312  return V;
313  }
314 
315  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
317  EndNodes.push_back(V);
318  return V;
319  }
320 
321  ExplodedGraph();
322 
323  ~ExplodedGraph();
324 
325  unsigned num_roots() const { return Roots.size(); }
326  unsigned num_eops() const { return EndNodes.size(); }
327 
328  bool empty() const { return NumNodes == 0; }
329  unsigned size() const { return NumNodes; }
330 
331  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
332 
333  // Iterators.
335  typedef llvm::FoldingSet<ExplodedNode> AllNodesTy;
336  typedef NodeVector::iterator roots_iterator;
337  typedef NodeVector::const_iterator const_roots_iterator;
338  typedef NodeVector::iterator eop_iterator;
339  typedef NodeVector::const_iterator const_eop_iterator;
340  typedef AllNodesTy::iterator node_iterator;
341  typedef AllNodesTy::const_iterator const_node_iterator;
342 
343  node_iterator nodes_begin() { return Nodes.begin(); }
344 
345  node_iterator nodes_end() { return Nodes.end(); }
346 
347  const_node_iterator nodes_begin() const { return Nodes.begin(); }
348 
349  const_node_iterator nodes_end() const { return Nodes.end(); }
350 
351  roots_iterator roots_begin() { return Roots.begin(); }
352 
353  roots_iterator roots_end() { return Roots.end(); }
354 
355  const_roots_iterator roots_begin() const { return Roots.begin(); }
356 
357  const_roots_iterator roots_end() const { return Roots.end(); }
358 
359  eop_iterator eop_begin() { return EndNodes.begin(); }
360 
361  eop_iterator eop_end() { return EndNodes.end(); }
362 
363  const_eop_iterator eop_begin() const { return EndNodes.begin(); }
364 
365  const_eop_iterator eop_end() const { return EndNodes.end(); }
366 
367  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
369 
370  typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> NodeMap;
371 
372  /// Creates a trimmed version of the graph that only contains paths leading
373  /// to the given nodes.
374  ///
375  /// \param Nodes The nodes which must appear in the final graph. Presumably
376  /// these are end-of-path nodes (i.e. they have no successors).
377  /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
378  /// the returned graph.
379  /// \param[out] InverseMap An optional map from nodes in the returned graph to
380  /// nodes in this graph.
381  /// \returns The trimmed graph
382  std::unique_ptr<ExplodedGraph>
383  trim(ArrayRef<const NodeTy *> Nodes,
384  InterExplodedGraphMap *ForwardMap = nullptr,
385  InterExplodedGraphMap *InverseMap = nullptr) const;
386 
387  /// Enable tracking of recently allocated nodes for potential reclamation
388  /// when calling reclaimRecentlyAllocatedNodes().
389  void enableNodeReclamation(unsigned Interval) {
390  ReclaimCounter = ReclaimNodeInterval = Interval;
391  }
392 
393  /// Reclaim "uninteresting" nodes created since the last time this method
394  /// was called.
395  void reclaimRecentlyAllocatedNodes();
396 
397  /// \brief Returns true if nodes for the given expression kind are always
398  /// kept around.
399  static bool isInterestingLValueExpr(const Expr *Ex);
400 
401 private:
402  bool shouldCollect(const ExplodedNode *node);
403  void collectNode(ExplodedNode *node);
404 };
405 
408  ImplTy Impl;
409 
410 public:
412  assert (N && !static_cast<ExplodedNode*>(N)->isSink());
413  Impl.insert(N);
414  }
415 
417 
418  inline void Add(ExplodedNode *N) {
419  if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
420  }
421 
422  typedef ImplTy::iterator iterator;
423  typedef ImplTy::const_iterator const_iterator;
424 
425  unsigned size() const { return Impl.size(); }
426  bool empty() const { return Impl.empty(); }
427  bool erase(ExplodedNode *N) { return Impl.remove(N); }
428 
429  void clear() { Impl.clear(); }
430  void insert(const ExplodedNodeSet &S) {
431  assert(&S != this);
432  if (empty())
433  Impl = S.Impl;
434  else
435  Impl.insert(S.begin(), S.end());
436  }
437 
438  inline iterator begin() { return Impl.begin(); }
439  inline iterator end() { return Impl.end(); }
440 
441  inline const_iterator begin() const { return Impl.begin(); }
442  inline const_iterator end() const { return Impl.end(); }
443 };
444 
445 } // end GR namespace
446 
447 } // end clang namespace
448 
449 // GraphTraits
450 
451 namespace llvm {
452  template<> struct GraphTraits<clang::ento::ExplodedNode*> {
455  typedef llvm::df_iterator<NodeRef> nodes_iterator;
456 
457  static NodeRef getEntryNode(NodeRef N) { return N; }
458 
459  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
460 
461  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
462 
463  static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
464 
465  static nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
466  };
467 
468  template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
471  typedef llvm::df_iterator<NodeRef> nodes_iterator;
472 
473  static NodeRef getEntryNode(NodeRef N) { return N; }
474 
475  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
476 
477  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
478 
479  static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
480 
481  static nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
482  };
483 
484 } // end llvm namespace
485 
486 #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
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:54
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:1865
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:808
const FunctionProtoType * T
This is the simplest builder which generates nodes in the ExplodedGraph.
Definition: CoreEngine.h:211
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.
ParentMap & getParentMap() const
void insert(const ExplodedNodeSet &S)
CoreEngine - Implements the core logic of the graph-reachability analysis.
Definition: CoreEngine.h:43
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:402
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:179
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:151
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
const_iterator begin() const