Coverage Report

Created: 2018-11-16 02:38

/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.36M
    NodeGroup(bool Flag = false) : P(Flag) {
93
7.36M
      assert(getFlag() == Flag);
94
7.36M
    }
95
96
    ExplodedNode * const *begin() const;
97
98
    ExplodedNode * const *end() const;
99
100
    unsigned size() const;
101
102
7.46M
    bool empty() const { return P == 0 || 
getFlag() != 07.40M
; }
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
35.3M
    bool getFlag() const {
118
35.3M
      return (P & 1);
119
35.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.68M
      : Location(loc), State(std::move(state)), Succs(IsSink) {
139
3.68M
    assert(isSink() == IsSink);
140
3.68M
  }
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
200k
  const StackFrameContext *getStackFrame() const {
150
200k
    return getLocation().getStackFrame();
151
200k
  }
152
153
226
  const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
154
155
780
  CFG &getCFG() const { return *getLocationContext()->getCFG(); }
156
157
794k
  ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
158
159
  template <typename T>
160
  T &getAnalysis() const {
161
    return *getLocationContext()->getAnalysis<T>();
162
  }
163
164
8.71M
  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::PreStmt> clang::ento::ExplodedNode::getLocationAs<clang::PreStmt>() const
Line
Count
Source
167
839k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
839k
    return Location.getAs<T>();
169
839k
  }
llvm::Optional<clang::PostStmt> clang::ento::ExplodedNode::getLocationAs<clang::PostStmt>() const
Line
Count
Source
167
52.8k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
52.8k
    return Location.getAs<T>();
169
52.8k
  }
llvm::Optional<clang::CallEnter> clang::ento::ExplodedNode::getLocationAs<clang::CallEnter>() const
Line
Count
Source
167
887k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
887k
    return Location.getAs<T>();
169
887k
  }
llvm::Optional<clang::CallExitEnd> clang::ento::ExplodedNode::getLocationAs<clang::CallExitEnd>() const
Line
Count
Source
167
1.41k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
1.41k
    return Location.getAs<T>();
169
1.41k
  }
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::PostStore> clang::ento::ExplodedNode::getLocationAs<clang::PostStore>() const
Line
Count
Source
167
43.6k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
43.6k
    return Location.getAs<T>();
169
43.6k
  }
llvm::Optional<clang::PostInitializer> clang::ento::ExplodedNode::getLocationAs<clang::PostInitializer>() const
Line
Count
Source
167
45.3k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
45.3k
    return Location.getAs<T>();
169
45.3k
  }
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
403
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
403
    return Location.getAs<T>();
169
403
  }
llvm::Optional<clang::FunctionExitPoint> clang::ento::ExplodedNode::getLocationAs<clang::FunctionExitPoint>() const
Line
Count
Source
167
355
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
168
355
    return Location.getAs<T>();
169
355
  }
170
171
  /// Get the value of an arbitrary expression at this node.
172
305k
  SVal getSVal(const Stmt *S) const {
173
305k
    return getState()->getSVal(S, getLocationContext());
174
305k
  }
175
176
  static void Profile(llvm::FoldingSetNodeID &ID,
177
                      const ProgramPoint &Loc,
178
                      const ProgramStateRef &state,
179
3.35M
                      bool IsSink) {
180
3.35M
    ID.Add(Loc);
181
3.35M
    ID.AddPointer(state.get());
182
3.35M
    ID.AddBoolean(IsSink);
183
3.35M
  }
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
22.6k
  bool succ_empty() const { return Succs.empty(); }
197
5.60M
  bool pred_empty() const { return Preds.empty(); }
198
199
6.87M
  bool isSink() const { return Succs.getFlag(); }
200
201
  bool hasSinglePred() const {
202
    return (pred_size() == 1);
203
  }
204
205
4.55M
  ExplodedNode *getFirstPred() {
206
4.55M
    return pred_empty() ? 
nullptr38.3k
:
*(pred_begin())4.51M
;
207
4.55M
  }
208
209
4.47M
  const ExplodedNode *getFirstPred() const {
210
4.47M
    return const_cast<ExplodedNode*>(this)->getFirstPred();
211
4.47M
  }
212
213
1.17k
  ExplodedNode *getFirstSucc() {
214
1.17k
    return succ_empty() ? 
nullptr143
:
*(succ_begin())1.03k
;
215
1.17k
  }
216
217
1.17k
  const ExplodedNode *getFirstSucc() const {
218
1.17k
    return const_cast<ExplodedNode*>(this)->getFirstSucc();
219
1.17k
  }
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
6.92M
  pred_iterator pred_begin() { return Preds.begin(); }
228
852k
  pred_iterator pred_end() { return Preds.end(); }
229
230
2.05M
  const_pred_iterator pred_begin() const {
231
2.05M
    return const_cast<ExplodedNode*>(this)->pred_begin();
232
2.05M
  }
233
852k
  const_pred_iterator pred_end() const {
234
852k
    return const_cast<ExplodedNode*>(this)->pred_end();
235
852k
  }
236
237
2.30M
  succ_iterator succ_begin() { return Succs.begin(); }
238
926k
  succ_iterator succ_end() { return Succs.end(); }
239
240
1.97M
  const_succ_iterator succ_begin() const {
241
1.97M
    return const_cast<ExplodedNode*>(this)->succ_begin();
242
1.97M
  }
243
926k
  const_succ_iterator succ_end() const {
244
926k
    return const_cast<ExplodedNode*>(this)->succ_end();
245
926k
  }
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
333k
  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
258
333k
  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
259
};
260
261
using InterExplodedGraphMap =
262
    llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
263
264
class ExplodedGraph {
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.
275
  NodeVector Roots;
276
277
  /// The nodes in the simulation graph which have been
278
  /// specially marked as the endpoint of an abstract simulation path.
279
  NodeVector EndNodes;
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.
286
  BumpVectorContext BVC;
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.
292
  NodeVector ChangedNodes;
293
294
  /// A list of nodes that can be reused.
295
  NodeVector FreeNodes;
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,
322
    ProgramStateRef State,
323
    bool IsSink = false);
324
325
9.13k
  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
326
9.13k
    return llvm::make_unique<ExplodedGraph>();
327
9.13k
  }
328
329
  /// addRoot - Add an untyped node to the set of roots.
330
28.0k
  ExplodedNode *addRoot(ExplodedNode *V) {
331
28.0k
    Roots.push_back(V);
332
28.0k
    return V;
333
28.0k
  }
334
335
  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
336
16.7k
  ExplodedNode *addEndOfPath(ExplodedNode *V) {
337
16.7k
    EndNodes.push_back(V);
338
16.7k
    return V;
339
16.7k
  }
340
341
9.80k
  unsigned num_roots() const { return Roots.size(); }
342
0
  unsigned num_eops() const { return EndNodes.size(); }
343
344
0
  bool empty() const { return NumNodes == 0; }
345
0
  unsigned size() const { return NumNodes; }
346
347
9.80k
  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
348
349
  // Iterators.
350
  using NodeTy = ExplodedNode;
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
329
  node_iterator nodes_begin() { return Nodes.begin(); }
360
361
586
  node_iterator nodes_end() { return Nodes.end(); }
362
363
0
  const_node_iterator nodes_begin() const { return Nodes.begin(); }
364
365
0
  const_node_iterator nodes_end() const { return Nodes.end(); }
366
367
10.1k
  roots_iterator roots_begin() { return Roots.begin(); }
368
369
0
  roots_iterator roots_end() { return Roots.end(); }
370
371
0
  const_roots_iterator roots_begin() const { return Roots.begin(); }
372
373
0
  const_roots_iterator roots_end() const { return Roots.end(); }
374
375
0
  eop_iterator eop_begin() { return EndNodes.begin(); }
376
377
0
  eop_iterator eop_end() { return EndNodes.end(); }
378
379
0
  const_eop_iterator eop_begin() const { return EndNodes.begin(); }
380
381
0
  const_eop_iterator eop_end() const { return EndNodes.end(); }
382
383
3.40M
  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
384
75.7k
  BumpVectorContext &getNodeAllocator() { return BVC; }
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
9.80k
  void enableNodeReclamation(unsigned Interval) {
406
9.80k
    ReclaimCounter = ReclaimNodeInterval = Interval;
407
9.80k
  }
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
422
class ExplodedNodeSet {
423
  using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
424
  ImplTy Impl;
425
426
public:
427
869k
  ExplodedNodeSet(ExplodedNode *N) {
428
869k
    assert(N && !static_cast<ExplodedNode*>(N)->isSink());
429
869k
    Impl.insert(N);
430
869k
  }
431
432
7.80M
  ExplodedNodeSet() = default;
433
434
3.60M
  void Add(ExplodedNode *N) {
435
3.60M
    if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
436
3.60M
  }
437
438
  using iterator = ImplTy::iterator;
439
  using const_iterator = ImplTy::const_iterator;
440
441
4.75k
  unsigned size() const { return Impl.size();  }
442
8.97M
  bool empty()    const { return Impl.empty(); }
443
2.29M
  bool erase(ExplodedNode *N) { return Impl.remove(N); }
444
445
945k
  void clear() { Impl.clear(); }
446
447
5.04M
  void insert(const ExplodedNodeSet &S) {
448
5.04M
    assert(&S != this);
449
5.04M
    if (empty())
450
5.04M
      Impl = S.Impl;
451
370
    else
452
370
      Impl.insert(S.begin(), S.end());
453
5.04M
  }
454
455
2.80M
  iterator begin() { return Impl.begin(); }
456
2.79M
  iterator end() { return Impl.end(); }
457
458
2.12M
  const_iterator begin() const { return Impl.begin(); }
459
2.12M
  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 *> {
470
    using GraphTy = clang::ento::ExplodedGraph *;
471
    using NodeRef = clang::ento::ExplodedNode *;
472
    using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
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
483
    static ChildIteratorType child_begin(NodeRef N) {
484
      if (predecessorOfTrivial(N))
485
        return child_begin(*N->succ_begin());
486
      return N->succ_begin();
487
    }
488
489
    static ChildIteratorType child_end(NodeRef N) {
490
      if (predecessorOfTrivial(N))
491
        return child_end(N->getFirstSucc());
492
      return N->succ_end();
493
    }
494
495
    static nodes_iterator nodes_begin(const GraphTy G) {
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