clang  9.0.0svn
ExplodedGraph.h
Go to the documentation of this file.
1 //===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the template classes ExplodedNode and ExplodedGraph,
10 // which represent a path-sensitive, intra-procedural "exploded graph."
11 // See "Precise interprocedural dataflow analysis via graph reachability"
12 // by Reps, Horwitz, and Sagiv
13 // (http://portal.acm.org/citation.cfm?id=199462) for the definition of an
14 // exploded graph.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
19 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
20 
24 #include "clang/Basic/LLVM.h"
28 #include "llvm/ADT/ArrayRef.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/DepthFirstIterator.h"
31 #include "llvm/ADT/FoldingSet.h"
32 #include "llvm/ADT/GraphTraits.h"
33 #include "llvm/ADT/Optional.h"
34 #include "llvm/ADT/STLExtras.h"
35 #include "llvm/ADT/SetVector.h"
36 #include "llvm/Support/Allocator.h"
37 #include "llvm/Support/Compiler.h"
38 #include <cassert>
39 #include <cstdint>
40 #include <memory>
41 #include <utility>
42 #include <vector>
43 
44 namespace clang {
45 
46 class CFG;
47 class Decl;
48 class Expr;
49 class ParentMap;
50 class Stmt;
51 
52 namespace ento {
53 
54 class ExplodedGraph;
55 
56 //===----------------------------------------------------------------------===//
57 // ExplodedGraph "implementation" classes. These classes are not typed to
58 // contain a specific kind of state. Typed-specialized versions are defined
59 // on top of these classes.
60 //===----------------------------------------------------------------------===//
61 
62 // ExplodedNode is not constified all over the engine because we need to add
63 // successors to it at any time after creating it.
64 
65 class ExplodedNode : public llvm::FoldingSetNode {
66  friend class BranchNodeBuilder;
67  friend class CoreEngine;
69  friend class ExplodedGraph;
71  friend class NodeBuilder;
72  friend class SwitchNodeBuilder;
73 
74  /// Efficiently stores a list of ExplodedNodes, or an optional flag.
75  ///
76  /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
77  /// for the case when there is only one node in the group. This is a fairly
78  /// common case in an ExplodedGraph, where most nodes have only one
79  /// predecessor and many have only one successor. It can also be used to
80  /// store a flag rather than a node list, which ExplodedNode uses to mark
81  /// whether a node is a sink. If the flag is set, the group is implicitly
82  /// empty and no nodes may be added.
83  class NodeGroup {
84  // Conceptually a discriminated union. If the low bit is set, the node is
85  // a sink. If the low bit is not set, the pointer refers to the storage
86  // for the nodes in the group.
87  // This is not a PointerIntPair in order to keep the storage type opaque.
88  uintptr_t P;
89 
90  public:
91  NodeGroup(bool Flag = false) : P(Flag) {
92  assert(getFlag() == Flag);
93  }
94 
95  ExplodedNode * const *begin() const;
96 
97  ExplodedNode * const *end() const;
98 
99  unsigned size() const;
100 
101  bool empty() const { return P == 0 || getFlag() != 0; }
102 
103  /// Adds a node to the list.
104  ///
105  /// The group must not have been created with its flag set.
106  void addNode(ExplodedNode *N, ExplodedGraph &G);
107 
108  /// Replaces the single node in this group with a new node.
109  ///
110  /// Note that this should only be used when you know the group was not
111  /// created with its flag set, and that the group is empty or contains
112  /// only a single node.
113  void replaceNode(ExplodedNode *node);
114 
115  /// Returns whether this group was created with its flag set.
116  bool getFlag() const {
117  return (P & 1);
118  }
119  };
120 
121  /// Location - The program location (within a function body) associated
122  /// with this node.
123  const ProgramPoint Location;
124 
125  /// State - The state associated with this node.
127 
128  /// Preds - The predecessors of this node.
129  NodeGroup Preds;
130 
131  /// Succs - The successors of this node.
132  NodeGroup Succs;
133 
134 public:
136  bool IsSink)
137  : Location(loc), State(std::move(state)), Succs(IsSink) {
138  assert(isSink() == IsSink);
139  }
140 
141  /// getLocation - Returns the edge associated with the given node.
142  ProgramPoint getLocation() const { return Location; }
143 
145  return getLocation().getLocationContext();
146  }
147 
149  return getLocation().getStackFrame();
150  }
151 
152  const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
153 
154  CFG &getCFG() const { return *getLocationContext()->getCFG(); }
155 
157 
158  template <typename T>
159  T &getAnalysis() const {
160  return *getLocationContext()->getAnalysis<T>();
161  }
162 
163  const ProgramStateRef &getState() const { return State; }
164 
165  template <typename T>
166  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167  return Location.getAs<T>();
168  }
169 
170  /// Get the value of an arbitrary expression at this node.
171  SVal getSVal(const Stmt *S) const {
172  return getState()->getSVal(S, getLocationContext());
173  }
174 
175  static void Profile(llvm::FoldingSetNodeID &ID,
176  const ProgramPoint &Loc,
177  const ProgramStateRef &state,
178  bool IsSink) {
179  ID.Add(Loc);
180  ID.AddPointer(state.get());
181  ID.AddBoolean(IsSink);
182  }
183 
184  void Profile(llvm::FoldingSetNodeID& ID) const {
185  // We avoid copy constructors by not using accessors.
186  Profile(ID, Location, State, isSink());
187  }
188 
189  /// addPredeccessor - Adds a predecessor to the current node, and
190  /// in tandem add this node as a successor of the other node.
192 
193  unsigned succ_size() const { return Succs.size(); }
194  unsigned pred_size() const { return Preds.size(); }
195  bool succ_empty() const { return Succs.empty(); }
196  bool pred_empty() const { return Preds.empty(); }
197 
198  bool isSink() const { return Succs.getFlag(); }
199 
200  bool hasSinglePred() const {
201  return (pred_size() == 1);
202  }
203 
205  return pred_empty() ? nullptr : *(pred_begin());
206  }
207 
208  const ExplodedNode *getFirstPred() const {
209  return const_cast<ExplodedNode*>(this)->getFirstPred();
210  }
211 
213  return succ_empty() ? nullptr : *(succ_begin());
214  }
215 
216  const ExplodedNode *getFirstSucc() const {
217  return const_cast<ExplodedNode*>(this)->getFirstSucc();
218  }
219 
220  // Iterators over successor and predecessor vertices.
221  using succ_iterator = ExplodedNode * const *;
222  using const_succ_iterator = const ExplodedNode * const *;
223  using pred_iterator = ExplodedNode * const *;
224  using const_pred_iterator = const ExplodedNode * const *;
225 
226  pred_iterator pred_begin() { return Preds.begin(); }
227  pred_iterator pred_end() { return Preds.end(); }
228 
230  return const_cast<ExplodedNode*>(this)->pred_begin();
231  }
233  return const_cast<ExplodedNode*>(this)->pred_end();
234  }
235 
236  succ_iterator succ_begin() { return Succs.begin(); }
237  succ_iterator succ_end() { return Succs.end(); }
238 
240  return const_cast<ExplodedNode*>(this)->succ_begin();
241  }
243  return const_cast<ExplodedNode*>(this)->succ_end();
244  }
245 
246  int64_t getID(ExplodedGraph *G) const;
247 
248  /// The node is trivial if it has only one successor, only one predecessor,
249  /// it's predecessor has only one successor,
250  /// and its program state is the same as the program state of the previous
251  /// node.
252  /// Trivial nodes may be skipped while printing exploded graph.
253  bool isTrivial() const;
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  /// 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  /// 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  /// 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  template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
472  using nodes_iterator = llvm::df_iterator<GraphTy>;
473 
474  static NodeRef getEntryNode(const GraphTy G) {
475  return *G->roots_begin();
476  }
477 
478  static bool predecessorOfTrivial(NodeRef N) {
479  return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
480  }
481 
483  if (predecessorOfTrivial(N))
484  return child_begin(*N->succ_begin());
485  return N->succ_begin();
486  }
487 
489  if (predecessorOfTrivial(N))
490  return child_end(N->getFirstSucc());
491  return N->succ_end();
492  }
493 
495  return df_begin(G);
496  }
497 
498  static nodes_iterator nodes_end(const GraphTy G) {
499  return df_end(G);
500  }
501  };
502 } // namespace llvm
503 
504 #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:29
Stmt - This represents one statement.
Definition: Stmt.h:65
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:55
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:2118
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:108
pred_iterator pred_end()
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1002
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:227
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:89
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:75
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:54
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:421
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:68
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