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