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