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 
214  return succ_empty() ? nullptr : *(succ_begin());
215  }
216 
217  const ExplodedNode *getFirstSucc() const {
218  return const_cast<ExplodedNode*>(this)->getFirstSucc();
219  }
220 
221  // Iterators over successor and predecessor vertices.
222  using succ_iterator = ExplodedNode * const *;
223  using const_succ_iterator = const ExplodedNode * const *;
224  using pred_iterator = ExplodedNode * const *;
225  using const_pred_iterator = const ExplodedNode * const *;
226 
227  pred_iterator pred_begin() { return Preds.begin(); }
228  pred_iterator pred_end() { return Preds.end(); }
229 
231  return const_cast<ExplodedNode*>(this)->pred_begin();
232  }
234  return const_cast<ExplodedNode*>(this)->pred_end();
235  }
236 
237  succ_iterator succ_begin() { return Succs.begin(); }
238  succ_iterator succ_end() { return Succs.end(); }
239 
241  return const_cast<ExplodedNode*>(this)->succ_begin();
242  }
244  return const_cast<ExplodedNode*>(this)->succ_end();
245  }
246 
247  int64_t getID(ExplodedGraph *G) const;
248 
249  /// The node is trivial if it has only one successor, only one predecessor,
250  /// it's predecessor has only one successor,
251  /// and its program state is the same as the program state of the previous
252  /// node.
253  /// Trivial nodes may be skipped while printing exploded graph.
254  bool isTrivial() const;
255 
256 private:
257  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
258  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
259 };
260 
261 using InterExplodedGraphMap =
262  llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
263 
265 protected:
266  friend class CoreEngine;
267 
268  // Type definitions.
269  using NodeVector = std::vector<ExplodedNode *>;
270 
271  /// The roots of the simulation graph. Usually there will be only
272  /// one, but clients are free to establish multiple subgraphs within a single
273  /// SimulGraph. Moreover, these subgraphs can often merge when paths from
274  /// different roots reach the same state at the same program location.
276 
277  /// The nodes in the simulation graph which have been
278  /// specially marked as the endpoint of an abstract simulation path.
280 
281  /// Nodes - The nodes in the graph.
282  llvm::FoldingSet<ExplodedNode> Nodes;
283 
284  /// BVC - Allocator and context for allocating nodes and their predecessor
285  /// and successor groups.
287 
288  /// NumNodes - The number of nodes in the graph.
289  unsigned NumNodes = 0;
290 
291  /// A list of recently allocated nodes that can potentially be recycled.
293 
294  /// A list of nodes that can be reused.
296 
297  /// Determines how often nodes are reclaimed.
298  ///
299  /// If this is 0, nodes will never be reclaimed.
300  unsigned ReclaimNodeInterval = 0;
301 
302  /// Counter to determine when to reclaim nodes.
303  unsigned ReclaimCounter;
304 
305 public:
306  ExplodedGraph();
307  ~ExplodedGraph();
308 
309  /// Retrieve the node associated with a (Location,State) pair,
310  /// where the 'Location' is a ProgramPoint in the CFG. If no node for
311  /// this pair exists, it is created. IsNew is set to true if
312  /// the node was freshly created.
313  ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
314  bool IsSink = false,
315  bool* IsNew = nullptr);
316 
317  /// Create a node for a (Location, State) pair,
318  /// but don't store it for deduplication later. This
319  /// is useful when copying an already completed
320  /// ExplodedGraph for further processing.
321  ExplodedNode *createUncachedNode(const ProgramPoint &L,
323  bool IsSink = false);
324 
325  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
326  return llvm::make_unique<ExplodedGraph>();
327  }
328 
329  /// addRoot - Add an untyped node to the set of roots.
331  Roots.push_back(V);
332  return V;
333  }
334 
335  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
337  EndNodes.push_back(V);
338  return V;
339  }
340 
341  unsigned num_roots() const { return Roots.size(); }
342  unsigned num_eops() const { return EndNodes.size(); }
343 
344  bool empty() const { return NumNodes == 0; }
345  unsigned size() const { return NumNodes; }
346 
347  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
348 
349  // Iterators.
351  using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
352  using roots_iterator = NodeVector::iterator;
353  using const_roots_iterator = NodeVector::const_iterator;
354  using eop_iterator = NodeVector::iterator;
355  using const_eop_iterator = NodeVector::const_iterator;
356  using node_iterator = AllNodesTy::iterator;
357  using const_node_iterator = AllNodesTy::const_iterator;
358 
359  node_iterator nodes_begin() { return Nodes.begin(); }
360 
361  node_iterator nodes_end() { return Nodes.end(); }
362 
363  const_node_iterator nodes_begin() const { return Nodes.begin(); }
364 
365  const_node_iterator nodes_end() const { return Nodes.end(); }
366 
367  roots_iterator roots_begin() { return Roots.begin(); }
368 
369  roots_iterator roots_end() { return Roots.end(); }
370 
371  const_roots_iterator roots_begin() const { return Roots.begin(); }
372 
373  const_roots_iterator roots_end() const { return Roots.end(); }
374 
375  eop_iterator eop_begin() { return EndNodes.begin(); }
376 
377  eop_iterator eop_end() { return EndNodes.end(); }
378 
379  const_eop_iterator eop_begin() const { return EndNodes.begin(); }
380 
381  const_eop_iterator eop_end() const { return EndNodes.end(); }
382 
383  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
385 
386  using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
387 
388  /// Creates a trimmed version of the graph that only contains paths leading
389  /// to the given nodes.
390  ///
391  /// \param Nodes The nodes which must appear in the final graph. Presumably
392  /// these are end-of-path nodes (i.e. they have no successors).
393  /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
394  /// the returned graph.
395  /// \param[out] InverseMap An optional map from nodes in the returned graph to
396  /// nodes in this graph.
397  /// \returns The trimmed graph
398  std::unique_ptr<ExplodedGraph>
399  trim(ArrayRef<const NodeTy *> Nodes,
400  InterExplodedGraphMap *ForwardMap = nullptr,
401  InterExplodedGraphMap *InverseMap = nullptr) const;
402 
403  /// Enable tracking of recently allocated nodes for potential reclamation
404  /// when calling reclaimRecentlyAllocatedNodes().
405  void enableNodeReclamation(unsigned Interval) {
406  ReclaimCounter = ReclaimNodeInterval = Interval;
407  }
408 
409  /// Reclaim "uninteresting" nodes created since the last time this method
410  /// was called.
411  void reclaimRecentlyAllocatedNodes();
412 
413  /// Returns true if nodes for the given expression kind are always
414  /// kept around.
415  static bool isInterestingLValueExpr(const Expr *Ex);
416 
417 private:
418  bool shouldCollect(const ExplodedNode *node);
419  void collectNode(ExplodedNode *node);
420 };
421 
424  ImplTy Impl;
425 
426 public:
428  assert(N && !static_cast<ExplodedNode*>(N)->isSink());
429  Impl.insert(N);
430  }
431 
432  ExplodedNodeSet() = default;
433 
434  void Add(ExplodedNode *N) {
435  if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
436  }
437 
438  using iterator = ImplTy::iterator;
439  using const_iterator = ImplTy::const_iterator;
440 
441  unsigned size() const { return Impl.size(); }
442  bool empty() const { return Impl.empty(); }
443  bool erase(ExplodedNode *N) { return Impl.remove(N); }
444 
445  void clear() { Impl.clear(); }
446 
447  void insert(const ExplodedNodeSet &S) {
448  assert(&S != this);
449  if (empty())
450  Impl = S.Impl;
451  else
452  Impl.insert(S.begin(), S.end());
453  }
454 
455  iterator begin() { return Impl.begin(); }
456  iterator end() { return Impl.end(); }
457 
458  const_iterator begin() const { return Impl.begin(); }
459  const_iterator end() const { return Impl.end(); }
460 };
461 
462 } // namespace ento
463 
464 } // namespace clang
465 
466 // GraphTraits
467 
468 namespace llvm {
469  template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
473  using nodes_iterator = llvm::df_iterator<GraphTy>;
474 
475  static NodeRef getEntryNode(const GraphTy G) {
476  return *G->roots_begin();
477  }
478 
479  static bool predecessorOfTrivial(NodeRef N) {
480  return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
481  }
482 
484  if (predecessorOfTrivial(N))
485  return child_begin(*N->succ_begin());
486  return N->succ_begin();
487  }
488 
490  if (predecessorOfTrivial(N))
491  return child_end(N->getFirstSucc());
492  return N->succ_end();
493  }
494 
496  return df_begin(G);
497  }
498 
499  static nodes_iterator nodes_end(const GraphTy G) {
500  return df_end(G);
501  }
502  };
503 } // namespace llvm
504 
505 #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:87
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:2072
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:185
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:106
pred_iterator pred_end()
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1003
ExplodedNode * getFirstSucc()
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:90
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, it&#39;s predecessor has only one...
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:181
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:153
ExplodedNode *const * pred_iterator
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
const_iterator begin() const