Coverage Report

Created: 2018-07-19 20:53

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
Line
Count
Source (jump to first uncovered line)
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/Analysis/AnalysisDeclContext.h"
23
#include "clang/Analysis/ProgramPoint.h"
24
#include "clang/Analysis/Support/BumpVector.h"
25
#include "clang/Basic/LLVM.h"
26
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
27
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
28
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.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;
69
  friend class EndOfFunctionNodeBuilder;
70
  friend class ExplodedGraph;
71
  friend class IndirectGotoNodeBuilder;
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
7.09M
    NodeGroup(bool Flag = false) : P(Flag) {
93
7.09M
      assert(getFlag() == Flag);
94
7.09M
    }
95
96
    ExplodedNode * const *begin() const;
97
98
    ExplodedNode * const *end() const;
99
100
    unsigned size() const;
101
102
6.20M
    bool empty() const { return P == 0 || 
getFlag() != 06.13M
; }
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
32.3M
    bool getFlag() const {
118
32.3M
      return (P & 1);
119
32.3M
    }
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.
127
  ProgramStateRef State;
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:
136
  explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
137
                        bool IsSink)
138
3.54M
      : Location(loc), State(std::move(state)), Succs(IsSink) {
139
3.54M
    assert(isSink() == IsSink);
140
3.54M
  }
141
142
  /// getLocation - Returns the edge associated with the given node.
143
24.6M
  ProgramPoint getLocation() const { return Location; }
144
145
11.2M
  const LocationContext *getLocationContext() const {
146
11.2M
    return getLocation().getLocationContext();
147
11.2M
  }
148
149
121k
  const StackFrameContext *getStackFrame() const {
150
121k
    return getLocation().getStackFrame();
151
121k
  }
152
153
243
  const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
154
155
598
  CFG &getCFG() const { return *getLocationContext()->getCFG(); }
156
157
756k
  ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
158
159
  template <typename T>
160
  T &getAnalysis() const {
161
    return *getLocationContext()->getAnalysis<T>();
162
  }
163
164
8.28M
  const ProgramStateRef &getState() const { return State; }
165
166
  template <typename T>
167
1.79M
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
1.79M
    return Location.getAs<T>();
169
1.79M
  }
llvm::Optional<clang::PostStmt> clang::ento::ExplodedNode::getLocationAs<clang::PostStmt>() const
Line
Count
Source
167
39.9k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
39.9k
    return Location.getAs<T>();
169
39.9k
  }
llvm::Optional<clang::CallEnter> clang::ento::ExplodedNode::getLocationAs<clang::CallEnter>() const
Line
Count
Source
167
833k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
833k
    return Location.getAs<T>();
169
833k
  }
llvm::Optional<clang::CallExitEnd> clang::ento::ExplodedNode::getLocationAs<clang::CallExitEnd>() const
Line
Count
Source
167
692
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
692
    return Location.getAs<T>();
169
692
  }
llvm::Optional<clang::StmtPoint> clang::ento::ExplodedNode::getLocationAs<clang::StmtPoint>() const
Line
Count
Source
167
639
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
639
    return Location.getAs<T>();
169
639
  }
llvm::Optional<clang::PreStmt> clang::ento::ExplodedNode::getLocationAs<clang::PreStmt>() const
Line
Count
Source
167
795k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
795k
    return Location.getAs<T>();
169
795k
  }
llvm::Optional<clang::PostStore> clang::ento::ExplodedNode::getLocationAs<clang::PostStore>() const
Line
Count
Source
167
34.3k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
34.3k
    return Location.getAs<T>();
169
34.3k
  }
llvm::Optional<clang::PostInitializer> clang::ento::ExplodedNode::getLocationAs<clang::PostInitializer>() const
Line
Count
Source
167
36.0k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
36.0k
    return Location.getAs<T>();
169
36.0k
  }
llvm::Optional<clang::CallExitBegin> clang::ento::ExplodedNode::getLocationAs<clang::CallExitBegin>() const
Line
Count
Source
167
50.3k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
50.3k
    return Location.getAs<T>();
169
50.3k
  }
llvm::Optional<clang::PreImplicitCall> clang::ento::ExplodedNode::getLocationAs<clang::PreImplicitCall>() const
Line
Count
Source
167
339
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
339
    return Location.getAs<T>();
169
339
  }
170
171
  /// Get the value of an arbitrary expression at this node.
172
288k
  SVal getSVal(const Stmt *S) const {
173
288k
    return getState()->getSVal(S, getLocationContext());
174
288k
  }
175
176
  static void Profile(llvm::FoldingSetNodeID &ID,
177
                      const ProgramPoint &Loc,
178
                      const ProgramStateRef &state,
179
3.30M
                      bool IsSink) {
180
3.30M
    ID.Add(Loc);
181
3.30M
    ID.AddPointer(state.get());
182
3.30M
    ID.AddBoolean(IsSink);
183
3.30M
  }
184
185
1.44M
  void Profile(llvm::FoldingSetNodeID& ID) const {
186
1.44M
    // We avoid copy constructors by not using accessors.
187
1.44M
    Profile(ID, Location, State, isSink());
188
1.44M
  }
189
190
  /// addPredeccessor - Adds a predecessor to the current node, and
191
  ///  in tandem add this node as a successor of the other node.
192
  void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
193
194
2.32M
  unsigned succ_size() const { return Succs.size(); }
195
2.21M
  unsigned pred_size() const { return Preds.size(); }
196
17.5k
  bool succ_empty() const { return Succs.empty(); }
197
4.43M
  bool pred_empty() const { return Preds.empty(); }
198
199
6.74M
  bool isSink() const { return Succs.getFlag(); }
200
201
  bool hasSinglePred() const {
202
    return (pred_size() == 1);
203
  }
204
205
3.42M
  ExplodedNode *getFirstPred() {
206
3.42M
    return pred_empty() ? 
nullptr37.2k
:
*(pred_begin())3.38M
;
207
3.42M
  }
208
209
3.35M
  const ExplodedNode *getFirstPred() const {
210
3.35M
    return const_cast<ExplodedNode*>(this)->getFirstPred();
211
3.35M
  }
212
213
1.01k
  const ExplodedNode *getFirstSucc() const {
214
1.01k
    return succ_empty() ? 
nullptr129
:
*(succ_begin())882
;
215
1.01k
  }
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
5.75M
  pred_iterator pred_begin() { return Preds.begin(); }
224
808k
  pred_iterator pred_end() { return Preds.end(); }
225
226
2.00M
  const_pred_iterator pred_begin() const {
227
2.00M
    return const_cast<ExplodedNode*>(this)->pred_begin();
228
2.00M
  }
229
808k
  const_pred_iterator pred_end() const {
230
808k
    return const_cast<ExplodedNode*>(this)->pred_end();
231
808k
  }
232
233
2.26M
  succ_iterator succ_begin() { return Succs.begin(); }
234
880k
  succ_iterator succ_end() { return Succs.end(); }
235
236
1.92M
  const_succ_iterator succ_begin() const {
237
1.92M
    return const_cast<ExplodedNode*>(this)->succ_begin();
238
1.92M
  }
239
880k
  const_succ_iterator succ_end() const {
240
880k
    return const_cast<ExplodedNode*>(this)->succ_end();
241
880k
  }
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
336k
  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
257
336k
  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
258
};
259
260
using InterExplodedGraphMap =
261
    llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
262
263
class ExplodedGraph {
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.
274
  NodeVector Roots;
275
276
  /// The nodes in the simulation graph which have been
277
  /// specially marked as the endpoint of an abstract simulation path.
278
  NodeVector EndNodes;
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.
285
  BumpVectorContext BVC;
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.
291
  NodeVector ChangedNodes;
292
  
293
  /// A list of nodes that can be reused.
294
  NodeVector FreeNodes;
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,
321
    ProgramStateRef State,
322
    bool IsSink = false);
323
324
8.86k
  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
325
8.86k
    return llvm::make_unique<ExplodedGraph>();
326
8.86k
  }
327
328
  /// addRoot - Add an untyped node to the set of roots.
329
27.1k
  ExplodedNode *addRoot(ExplodedNode *V) {
330
27.1k
    Roots.push_back(V);
331
27.1k
    return V;
332
27.1k
  }
333
334
  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
335
16.2k
  ExplodedNode *addEndOfPath(ExplodedNode *V) {
336
16.2k
    EndNodes.push_back(V);
337
16.2k
    return V;
338
16.2k
  }
339
340
9.37k
  unsigned num_roots() const { return Roots.size(); }
341
0
  unsigned num_eops() const { return EndNodes.size(); }
342
343
0
  bool empty() const { return NumNodes == 0; }
344
0
  unsigned size() const { return NumNodes; }
345
346
9.37k
  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
347
348
  // Iterators.
349
  using NodeTy = ExplodedNode;
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
329
  node_iterator nodes_begin() { return Nodes.begin(); }
359
360
586
  node_iterator nodes_end() { return Nodes.end(); }
361
362
0
  const_node_iterator nodes_begin() const { return Nodes.begin(); }
363
364
0
  const_node_iterator nodes_end() const { return Nodes.end(); }
365
366
9.98k
  roots_iterator roots_begin() { return Roots.begin(); }
367
368
0
  roots_iterator roots_end() { return Roots.end(); }
369
370
0
  const_roots_iterator roots_begin() const { return Roots.begin(); }
371
372
0
  const_roots_iterator roots_end() const { return Roots.end(); }
373
374
0
  eop_iterator eop_begin() { return EndNodes.begin(); }
375
376
0
  eop_iterator eop_end() { return EndNodes.end(); }
377
378
0
  const_eop_iterator eop_begin() const { return EndNodes.begin(); }
379
380
0
  const_eop_iterator eop_end() const { return EndNodes.end(); }
381
382
3.27M
  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
383
75.6k
  BumpVectorContext &getNodeAllocator() { return BVC; }
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
9.37k
  void enableNodeReclamation(unsigned Interval) {
405
9.37k
    ReclaimCounter = ReclaimNodeInterval = Interval;
406
9.37k
  }
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
421
class ExplodedNodeSet {
422
  using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
423
  ImplTy Impl;
424
425
public:
426
807k
  ExplodedNodeSet(ExplodedNode *N) {
427
807k
    assert(N && !static_cast<ExplodedNode*>(N)->isSink());
428
807k
    Impl.insert(N);
429
807k
  }
430
431
7.62M
  ExplodedNodeSet() = default;
432
433
3.57M
  void Add(ExplodedNode *N) {
434
3.57M
    if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
435
3.57M
  }
436
437
  using iterator = ImplTy::iterator;
438
  using const_iterator = ImplTy::const_iterator;
439
440
3.74k
  unsigned size() const { return Impl.size();  }
441
8.67M
  bool empty()    const { return Impl.empty(); }
442
2.24M
  bool erase(ExplodedNode *N) { return Impl.remove(N); }
443
444
889k
  void clear() { Impl.clear(); }
445
446
4.86M
  void insert(const ExplodedNodeSet &S) {
447
4.86M
    assert(&S != this);
448
4.86M
    if (empty())
449
4.86M
      Impl = S.Impl;
450
407
    else
451
407
      Impl.insert(S.begin(), S.end());
452
4.86M
  }
453
454
2.67M
  iterator begin() { return Impl.begin(); }
455
2.67M
  iterator end() { return Impl.end(); }
456
457
2.04M
  const_iterator begin() const { return Impl.begin(); }
458
2.04M
  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*> {
470
    using NodeRef = clang::ento::ExplodedNode *;
471
    using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
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*> {
486
    using NodeRef = const clang::ento::ExplodedNode *;
487
    using ChildIteratorType = clang::ento::ExplodedNode::const_succ_iterator;
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