Coverage Report

Created: 2019-02-23 12:57

/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
// 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
21
#include "clang/Analysis/AnalysisDeclContext.h"
22
#include "clang/Analysis/ProgramPoint.h"
23
#include "clang/Analysis/Support/BumpVector.h"
24
#include "clang/Basic/LLVM.h"
25
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
26
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
27
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.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;
68
  friend class EndOfFunctionNodeBuilder;
69
  friend class ExplodedGraph;
70
  friend class IndirectGotoNodeBuilder;
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
8.10M
    NodeGroup(bool Flag = false) : P(Flag) {
92
8.10M
      assert(getFlag() == Flag);
93
8.10M
    }
94
95
    ExplodedNode * const *begin() const;
96
97
    ExplodedNode * const *end() const;
98
99
    unsigned size() const;
100
101
8.13M
    bool empty() const { return P == 0 || 
getFlag() != 08.06M
; }
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
37.9M
    bool getFlag() const {
117
37.9M
      return (P & 1);
118
37.9M
    }
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.
126
  ProgramStateRef State;
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:
135
  explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
136
                        bool IsSink)
137
4.05M
      : Location(loc), State(std::move(state)), Succs(IsSink) {
138
4.05M
    assert(isSink() == IsSink);
139
4.05M
  }
140
141
  /// getLocation - Returns the edge associated with the given node.
142
28.4M
  ProgramPoint getLocation() const { return Location; }
143
144
13.2M
  const LocationContext *getLocationContext() const {
145
13.2M
    return getLocation().getLocationContext();
146
13.2M
  }
147
148
235k
  const StackFrameContext *getStackFrame() const {
149
235k
    return getLocation().getStackFrame();
150
235k
  }
151
152
286
  const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
153
154
908
  CFG &getCFG() const { return *getLocationContext()->getCFG(); }
155
156
856k
  ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
157
158
  template <typename T>
159
  T &getAnalysis() const {
160
    return *getLocationContext()->getAnalysis<T>();
161
  }
162
163
10.8M
  const ProgramStateRef &getState() const { return State; }
164
165
  template <typename T>
166
2.13M
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
2.13M
    return Location.getAs<T>();
168
2.13M
  }
llvm::Optional<clang::PreStmt> clang::ento::ExplodedNode::getLocationAs<clang::PreStmt>() const &
Line
Count
Source
166
909k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
909k
    return Location.getAs<T>();
168
909k
  }
llvm::Optional<clang::BlockEdge> clang::ento::ExplodedNode::getLocationAs<clang::BlockEdge>() const &
Line
Count
Source
166
24.7k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
24.7k
    return Location.getAs<T>();
168
24.7k
  }
llvm::Optional<clang::CallExitBegin> clang::ento::ExplodedNode::getLocationAs<clang::CallExitBegin>() const &
Line
Count
Source
166
88.7k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
88.7k
    return Location.getAs<T>();
168
88.7k
  }
llvm::Optional<clang::PostStmt> clang::ento::ExplodedNode::getLocationAs<clang::PostStmt>() const &
Line
Count
Source
166
56.5k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
56.5k
    return Location.getAs<T>();
168
56.5k
  }
llvm::Optional<clang::CallEnter> clang::ento::ExplodedNode::getLocationAs<clang::CallEnter>() const &
Line
Count
Source
166
959k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
959k
    return Location.getAs<T>();
168
959k
  }
llvm::Optional<clang::CallExitEnd> clang::ento::ExplodedNode::getLocationAs<clang::CallExitEnd>() const &
Line
Count
Source
166
1.45k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
1.45k
    return Location.getAs<T>();
168
1.45k
  }
llvm::Optional<clang::StmtPoint> clang::ento::ExplodedNode::getLocationAs<clang::StmtPoint>() const &
Line
Count
Source
166
1.38k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
1.38k
    return Location.getAs<T>();
168
1.38k
  }
llvm::Optional<clang::PostStore> clang::ento::ExplodedNode::getLocationAs<clang::PostStore>() const &
Line
Count
Source
166
46.2k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
46.2k
    return Location.getAs<T>();
168
46.2k
  }
llvm::Optional<clang::PostInitializer> clang::ento::ExplodedNode::getLocationAs<clang::PostInitializer>() const &
Line
Count
Source
166
48.1k
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
48.1k
    return Location.getAs<T>();
168
48.1k
  }
llvm::Optional<clang::PreImplicitCall> clang::ento::ExplodedNode::getLocationAs<clang::PreImplicitCall>() const &
Line
Count
Source
166
427
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
427
    return Location.getAs<T>();
168
427
  }
llvm::Optional<clang::FunctionExitPoint> clang::ento::ExplodedNode::getLocationAs<clang::FunctionExitPoint>() const &
Line
Count
Source
166
379
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167
379
    return Location.getAs<T>();
168
379
  }
169
170
  /// Get the value of an arbitrary expression at this node.
171
318k
  SVal getSVal(const Stmt *S) const {
172
318k
    return getState()->getSVal(S, getLocationContext());
173
318k
  }
174
175
  static void Profile(llvm::FoldingSetNodeID &ID,
176
                      const ProgramPoint &Loc,
177
                      const ProgramStateRef &state,
178
3.55M
                      bool IsSink) {
179
3.55M
    ID.Add(Loc);
180
3.55M
    ID.AddPointer(state.get());
181
3.55M
    ID.AddBoolean(IsSink);
182
3.55M
  }
183
184
1.44M
  void Profile(llvm::FoldingSetNodeID& ID) const {
185
1.44M
    // We avoid copy constructors by not using accessors.
186
1.44M
    Profile(ID, Location, State, isSink());
187
1.44M
  }
188
189
  /// addPredeccessor - Adds a predecessor to the current node, and
190
  ///  in tandem add this node as a successor of the other node.
191
  void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
192
193
2.45M
  unsigned succ_size() const { return Succs.size(); }
194
2.34M
  unsigned pred_size() const { return Preds.size(); }
195
26.6k
  bool succ_empty() const { return Succs.empty(); }
196
6.08M
  bool pred_empty() const { return Preds.empty(); }
197
198
7.12M
  bool isSink() const { return Succs.getFlag(); }
199
200
  bool hasSinglePred() const {
201
    return (pred_size() == 1);
202
  }
203
204
4.94M
  ExplodedNode *getFirstPred() {
205
4.94M
    return pred_empty() ? 
nullptr40.5k
:
*(pred_begin())4.90M
;
206
4.94M
  }
207
208
4.87M
  const ExplodedNode *getFirstPred() const {
209
4.87M
    return const_cast<ExplodedNode*>(this)->getFirstPred();
210
4.87M
  }
211
212
1.42k
  ExplodedNode *getFirstSucc() {
213
1.42k
    return succ_empty() ? 
nullptr151
:
*(succ_begin())1.27k
;
214
1.42k
  }
215
216
1.42k
  const ExplodedNode *getFirstSucc() const {
217
1.42k
    return const_cast<ExplodedNode*>(this)->getFirstSucc();
218
1.42k
  }
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
7.46M
  pred_iterator pred_begin() { return Preds.begin(); }
227
923k
  pred_iterator pred_end() { return Preds.end(); }
228
229
2.19M
  const_pred_iterator pred_begin() const {
230
2.19M
    return const_cast<ExplodedNode*>(this)->pred_begin();
231
2.19M
  }
232
923k
  const_pred_iterator pred_end() const {
233
923k
    return const_cast<ExplodedNode*>(this)->pred_end();
234
923k
  }
235
236
2.47M
  succ_iterator succ_begin() { return Succs.begin(); }
237
1.02M
  succ_iterator succ_end() { return Succs.end(); }
238
239
2.13M
  const_succ_iterator succ_begin() const {
240
2.13M
    return const_cast<ExplodedNode*>(this)->succ_begin();
241
2.13M
  }
242
1.02M
  const_succ_iterator succ_end() const {
243
1.02M
    return const_cast<ExplodedNode*>(this)->succ_end();
244
1.02M
  }
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
339k
  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
257
339k
  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
9.66k
  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
325
9.66k
    return llvm::make_unique<ExplodedGraph>();
326
9.66k
  }
327
328
  /// addRoot - Add an untyped node to the set of roots.
329
29.8k
  ExplodedNode *addRoot(ExplodedNode *V) {
330
29.8k
    Roots.push_back(V);
331
29.8k
    return V;
332
29.8k
  }
333
334
  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
335
17.5k
  ExplodedNode *addEndOfPath(ExplodedNode *V) {
336
17.5k
    EndNodes.push_back(V);
337
17.5k
    return V;
338
17.5k
  }
339
340
10.5k
  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
10.5k
  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
330
  node_iterator nodes_begin() { return Nodes.begin(); }
359
360
587
  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
10.7k
  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.77M
  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
383
78.0k
  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
10.5k
  void enableNodeReclamation(unsigned Interval) {
405
10.5k
    ReclaimCounter = ReclaimNodeInterval = Interval;
406
10.5k
  }
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
1.20M
  ExplodedNodeSet(ExplodedNode *N) {
427
1.20M
    assert(N && !static_cast<ExplodedNode*>(N)->isSink());
428
1.20M
    Impl.insert(N);
429
1.20M
  }
430
431
9.14M
  ExplodedNodeSet() = default;
432
433
3.68M
  void Add(ExplodedNode *N) {
434
3.68M
    if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
435
3.68M
  }
436
437
  using iterator = ImplTy::iterator;
438
  using const_iterator = ImplTy::const_iterator;
439
440
7.54k
  unsigned size() const { return Impl.size();  }
441
11.6M
  bool empty()    const { return Impl.empty(); }
442
2.50M
  bool erase(ExplodedNode *N) { return Impl.remove(N); }
443
444
1.50M
  void clear() { Impl.clear(); }
445
446
6.46M
  void insert(const ExplodedNodeSet &S) {
447
6.46M
    assert(&S != this);
448
6.46M
    if (empty())
449
6.46M
      Impl = S.Impl;
450
388
    else
451
388
      Impl.insert(S.begin(), S.end());
452
6.46M
  }
453
454
3.32M
  iterator begin() { return Impl.begin(); }
455
3.31M
  iterator end() { return Impl.end(); }
456
457
2.98M
  const_iterator begin() const { return Impl.begin(); }
458
2.98M
  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 *> {
469
    using GraphTy = clang::ento::ExplodedGraph *;
470
    using NodeRef = clang::ento::ExplodedNode *;
471
    using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
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
482
    static ChildIteratorType child_begin(NodeRef N) {
483
      if (predecessorOfTrivial(N))
484
        return child_begin(*N->succ_begin());
485
      return N->succ_begin();
486
    }
487
488
    static ChildIteratorType child_end(NodeRef N) {
489
      if (predecessorOfTrivial(N))
490
        return child_end(N->getFirstSucc());
491
      return N->succ_end();
492
    }
493
494
    static nodes_iterator nodes_begin(const GraphTy G) {
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