Coverage Report

Created: 2018-09-23 03:40

/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.38M
    NodeGroup(bool Flag = false) : P(Flag) {
93
7.38M
      assert(getFlag() == Flag);
94
7.38M
    }
95
96
    ExplodedNode * const *begin() const;
97
98
    ExplodedNode * const *end() const;
99
100
    unsigned size() const;
101
102
6.53M
    bool empty() const { return P == 0 || 
getFlag() != 06.46M
; }
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
33.5M
    bool getFlag() const {
118
33.5M
      return (P & 1);
119
33.5M
    }
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.69M
      : Location(loc), State(std::move(state)), Succs(IsSink) {
139
3.69M
    assert(isSink() == IsSink);
140
3.69M
  }
141
142
  /// getLocation - Returns the edge associated with the given node.
143
25.5M
  ProgramPoint getLocation() const { return Location; }
144
145
11.5M
  const LocationContext *getLocationContext() const {
146
11.5M
    return getLocation().getLocationContext();
147
11.5M
  }
148
149
199k
  const StackFrameContext *getStackFrame() const {
150
199k
    return getLocation().getStackFrame();
151
199k
  }
152
153
226
  const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
154
155
751
  CFG &getCFG() const { return *getLocationContext()->getCFG(); }
156
157
792k
  ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
158
159
  template <typename T>
160
  T &getAnalysis() const {
161
    return *getLocationContext()->getAnalysis<T>();
162
  }
163
164
8.73M
  const ProgramStateRef &getState() const { return State; }
165
166
  template <typename T>
167
1.93M
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
1.93M
    return Location.getAs<T>();
169
1.93M
  }
llvm::Optional<clang::PostStmt> clang::ento::ExplodedNode::getLocationAs<clang::PostStmt>() const
Line
Count
Source
167
53.4k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
53.4k
    return Location.getAs<T>();
169
53.4k
  }
llvm::Optional<clang::CallEnter> clang::ento::ExplodedNode::getLocationAs<clang::CallEnter>() const
Line
Count
Source
167
886k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
886k
    return Location.getAs<T>();
169
886k
  }
llvm::Optional<clang::CallExitEnd> clang::ento::ExplodedNode::getLocationAs<clang::CallExitEnd>() const
Line
Count
Source
167
1.42k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
1.42k
    return Location.getAs<T>();
169
1.42k
  }
llvm::Optional<clang::StmtPoint> clang::ento::ExplodedNode::getLocationAs<clang::StmtPoint>() const
Line
Count
Source
167
1.34k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
1.34k
    return Location.getAs<T>();
169
1.34k
  }
llvm::Optional<clang::PreStmt> clang::ento::ExplodedNode::getLocationAs<clang::PreStmt>() const
Line
Count
Source
167
838k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
838k
    return Location.getAs<T>();
169
838k
  }
llvm::Optional<clang::PostStore> clang::ento::ExplodedNode::getLocationAs<clang::PostStore>() const
Line
Count
Source
167
44.2k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
44.2k
    return Location.getAs<T>();
169
44.2k
  }
llvm::Optional<clang::PostInitializer> clang::ento::ExplodedNode::getLocationAs<clang::PostInitializer>() const
Line
Count
Source
167
45.8k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
45.8k
    return Location.getAs<T>();
169
45.8k
  }
llvm::Optional<clang::CallExitBegin> clang::ento::ExplodedNode::getLocationAs<clang::CallExitBegin>() const
Line
Count
Source
167
60.9k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
60.9k
    return Location.getAs<T>();
169
60.9k
  }
llvm::Optional<clang::PreImplicitCall> clang::ento::ExplodedNode::getLocationAs<clang::PreImplicitCall>() const
Line
Count
Source
167
385
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
385
    return Location.getAs<T>();
169
385
  }
llvm::Optional<clang::FunctionExitPoint> clang::ento::ExplodedNode::getLocationAs<clang::FunctionExitPoint>() const
Line
Count
Source
167
337
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
337
    return Location.getAs<T>();
169
337
  }
170
171
  /// Get the value of an arbitrary expression at this node.
172
306k
  SVal getSVal(const Stmt *S) const {
173
306k
    return getState()->getSVal(S, getLocationContext());
174
306k
  }
175
176
  static void Profile(llvm::FoldingSetNodeID &ID,
177
                      const ProgramPoint &Loc,
178
                      const ProgramStateRef &state,
179
3.36M
                      bool IsSink) {
180
3.36M
    ID.Add(Loc);
181
3.36M
    ID.AddPointer(state.get());
182
3.36M
    ID.AddBoolean(IsSink);
183
3.36M
  }
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.34M
  unsigned succ_size() const { return Succs.size(); }
195
2.23M
  unsigned pred_size() const { return Preds.size(); }
196
22.3k
  bool succ_empty() const { return Succs.empty(); }
197
4.66M
  bool pred_empty() const { return Preds.empty(); }
198
199
6.89M
  bool isSink() const { return Succs.getFlag(); }
200
201
  bool hasSinglePred() const {
202
    return (pred_size() == 1);
203
  }
204
205
3.61M
  ExplodedNode *getFirstPred() {
206
3.61M
    return pred_empty() ? 
nullptr38.3k
:
*(pred_begin())3.57M
;
207
3.61M
  }
208
209
3.54M
  const ExplodedNode *getFirstPred() const {
210
3.54M
    return const_cast<ExplodedNode*>(this)->getFirstPred();
211
3.54M
  }
212
213
1.14k
  const ExplodedNode *getFirstSucc() const {
214
1.14k
    return succ_empty() ? 
nullptr137
:
*(succ_begin())1.00k
;
215
1.14k
  }
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.99M
  pred_iterator pred_begin() { return Preds.begin(); }
224
851k
  pred_iterator pred_end() { return Preds.end(); }
225
226
2.06M
  const_pred_iterator pred_begin() const {
227
2.06M
    return const_cast<ExplodedNode*>(this)->pred_begin();
228
2.06M
  }
229
851k
  const_pred_iterator pred_end() const {
230
851k
    return const_cast<ExplodedNode*>(this)->pred_end();
231
851k
  }
232
233
2.32M
  succ_iterator succ_begin() { return Succs.begin(); }
234
929k
  succ_iterator succ_end() { return Succs.end(); }
235
236
1.98M
  const_succ_iterator succ_begin() const {
237
1.98M
    return const_cast<ExplodedNode*>(this)->succ_begin();
238
1.98M
  }
239
929k
  const_succ_iterator succ_end() const {
240
929k
    return const_cast<ExplodedNode*>(this)->succ_end();
241
929k
  }
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
337k
  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
252
337k
  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
253
};
254
255
using InterExplodedGraphMap =
256
    llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
257
258
class ExplodedGraph {
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.
269
  NodeVector Roots;
270
271
  /// The nodes in the simulation graph which have been
272
  /// specially marked as the endpoint of an abstract simulation path.
273
  NodeVector EndNodes;
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.
280
  BumpVectorContext BVC;
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.
286
  NodeVector ChangedNodes;
287
288
  /// A list of nodes that can be reused.
289
  NodeVector FreeNodes;
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,
316
    ProgramStateRef State,
317
    bool IsSink = false);
318
319
9.13k
  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
320
9.13k
    return llvm::make_unique<ExplodedGraph>();
321
9.13k
  }
322
323
  /// addRoot - Add an untyped node to the set of roots.
324
28.0k
  ExplodedNode *addRoot(ExplodedNode *V) {
325
28.0k
    Roots.push_back(V);
326
28.0k
    return V;
327
28.0k
  }
328
329
  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
330
16.7k
  ExplodedNode *addEndOfPath(ExplodedNode *V) {
331
16.7k
    EndNodes.push_back(V);
332
16.7k
    return V;
333
16.7k
  }
334
335
9.75k
  unsigned num_roots() const { return Roots.size(); }
336
0
  unsigned num_eops() const { return EndNodes.size(); }
337
338
0
  bool empty() const { return NumNodes == 0; }
339
0
  unsigned size() const { return NumNodes; }
340
341
9.75k
  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
342
343
  // Iterators.
344
  using NodeTy = ExplodedNode;
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
329
  node_iterator nodes_begin() { return Nodes.begin(); }
354
355
586
  node_iterator nodes_end() { return Nodes.end(); }
356
357
0
  const_node_iterator nodes_begin() const { return Nodes.begin(); }
358
359
0
  const_node_iterator nodes_end() const { return Nodes.end(); }
360
361
10.2k
  roots_iterator roots_begin() { return Roots.begin(); }
362
363
0
  roots_iterator roots_end() { return Roots.end(); }
364
365
0
  const_roots_iterator roots_begin() const { return Roots.begin(); }
366
367
0
  const_roots_iterator roots_end() const { return Roots.end(); }
368
369
0
  eop_iterator eop_begin() { return EndNodes.begin(); }
370
371
0
  eop_iterator eop_end() { return EndNodes.end(); }
372
373
0
  const_eop_iterator eop_begin() const { return EndNodes.begin(); }
374
375
0
  const_eop_iterator eop_end() const { return EndNodes.end(); }
376
377
3.41M
  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
378
76.2k
  BumpVectorContext &getNodeAllocator() { return BVC; }
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
9.75k
  void enableNodeReclamation(unsigned Interval) {
400
9.75k
    ReclaimCounter = ReclaimNodeInterval = Interval;
401
9.75k
  }
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
416
class ExplodedNodeSet {
417
  using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
418
  ImplTy Impl;
419
420
public:
421
871k
  ExplodedNodeSet(ExplodedNode *N) {
422
871k
    assert(N && !static_cast<ExplodedNode*>(N)->isSink());
423
871k
    Impl.insert(N);
424
871k
  }
425
426
7.82M
  ExplodedNodeSet() = default;
427
428
3.61M
  void Add(ExplodedNode *N) {
429
3.61M
    if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
430
3.61M
  }
431
432
  using iterator = ImplTy::iterator;
433
  using const_iterator = ImplTy::const_iterator;
434
435
4.70k
  unsigned size() const { return Impl.size();  }
436
8.99M
  bool empty()    const { return Impl.empty(); }
437
2.30M
  bool erase(ExplodedNode *N) { return Impl.remove(N); }
438
439
944k
  void clear() { Impl.clear(); }
440
441
5.05M
  void insert(const ExplodedNodeSet &S) {
442
5.05M
    assert(&S != this);
443
5.05M
    if (empty())
444
5.05M
      Impl = S.Impl;
445
375
    else
446
375
      Impl.insert(S.begin(), S.end());
447
5.05M
  }
448
449
2.81M
  iterator begin() { return Impl.begin(); }
450
2.80M
  iterator end() { return Impl.end(); }
451
452
2.13M
  const_iterator begin() const { return Impl.begin(); }
453
2.13M
  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 *> {
465
    using GraphTy = clang::ento::ExplodedGraph *;
466
    using NodeRef = clang::ento::ExplodedNode *;
467
    using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
468
    using nodes_iterator = llvm::df_iterator<GraphTy>;
469
470
    static NodeRef getEntryNode(const GraphTy G) {
471
      return *G->roots_begin();
472
    }
473
474
    static ChildIteratorType child_begin(NodeRef N) {
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
481
    static ChildIteratorType child_end(NodeRef N) {
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
488
    static nodes_iterator nodes_begin(const GraphTy G) {
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