aboutsummaryrefslogtreecommitdiffstats
path: root/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
blob: e87772c04b9be1679cca53a3d0e96153a2a64a98 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
//===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
//  This file defines the template classes ExplodedNode and ExplodedGraph,
//  which represent a path-sensitive, intra-procedural "exploded graph."
//  See "Precise interprocedural dataflow analysis via graph reachability"
//  by Reps, Horwitz, and Sagiv
//  (http://portal.acm.org/citation.cfm?id=199462) for the definition of an
//  exploded graph.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H

#include "clang/Analysis/AnalysisDeclContext.h"
#include "clang/Analysis/ProgramPoint.h"
#include "clang/Analysis/Support/BumpVector.h"
#include "clang/Basic/LLVM.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Compiler.h"
#include <cassert>
#include <cstdint>
#include <memory>
#include <utility>
#include <vector>

namespace clang {

class CFG;
class Decl;
class Expr;
class ParentMap;
class Stmt;

namespace ento {

class ExplodedGraph;

//===----------------------------------------------------------------------===//
// ExplodedGraph "implementation" classes.  These classes are not typed to
// contain a specific kind of state.  Typed-specialized versions are defined
// on top of these classes.
//===----------------------------------------------------------------------===//

// ExplodedNode is not constified all over the engine because we need to add
// successors to it at any time after creating it.

class ExplodedNode : public llvm::FoldingSetNode {
  friend class BranchNodeBuilder;
  friend class CoreEngine;
  friend class EndOfFunctionNodeBuilder;
  friend class ExplodedGraph;
  friend class IndirectGotoNodeBuilder;
  friend class NodeBuilder;
  friend class SwitchNodeBuilder;

  /// Efficiently stores a list of ExplodedNodes, or an optional flag.
  ///
  /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
  /// for the case when there is only one node in the group. This is a fairly
  /// common case in an ExplodedGraph, where most nodes have only one
  /// predecessor and many have only one successor. It can also be used to
  /// store a flag rather than a node list, which ExplodedNode uses to mark
  /// whether a node is a sink. If the flag is set, the group is implicitly
  /// empty and no nodes may be added.
  class NodeGroup {
    // Conceptually a discriminated union. If the low bit is set, the node is
    // a sink. If the low bit is not set, the pointer refers to the storage
    // for the nodes in the group.
    // This is not a PointerIntPair in order to keep the storage type opaque.
    uintptr_t P;

  public:
    NodeGroup(bool Flag = false) : P(Flag) {
      assert(getFlag() == Flag);
    }

    ExplodedNode * const *begin() const;

    ExplodedNode * const *end() const;

    unsigned size() const;

    bool empty() const { return P == 0 || getFlag() != 0; }

    /// Adds a node to the list.
    ///
    /// The group must not have been created with its flag set.
    void addNode(ExplodedNode *N, ExplodedGraph &G);

    /// Replaces the single node in this group with a new node.
    ///
    /// Note that this should only be used when you know the group was not
    /// created with its flag set, and that the group is empty or contains
    /// only a single node.
    void replaceNode(ExplodedNode *node);

    /// Returns whether this group was created with its flag set.
    bool getFlag() const {
      return (P & 1);
    }
  };

  /// Location - The program location (within a function body) associated
  ///  with this node.
  const ProgramPoint Location;

  /// State - The state associated with this node.
  ProgramStateRef State;

  /// Preds - The predecessors of this node.
  NodeGroup Preds;

  /// Succs - The successors of this node.
  NodeGroup Succs;

  int64_t Id;

public:
  explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
                        int64_t Id, bool IsSink)
      : Location(loc), State(std::move(state)), Succs(IsSink), Id(Id) {
    assert(isSink() == IsSink);
  }

  /// getLocation - Returns the edge associated with the given node.
  ProgramPoint getLocation() const { return Location; }

  const LocationContext *getLocationContext() const {
    return getLocation().getLocationContext();
  }

  const StackFrameContext *getStackFrame() const {
    return getLocation().getStackFrame();
  }

  const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }

  CFG &getCFG() const { return *getLocationContext()->getCFG(); }

  const CFGBlock *getCFGBlock() const;

  const ParentMap &getParentMap() const {
    return getLocationContext()->getParentMap();
  }

  template <typename T>
  T &getAnalysis() const {
    return *getLocationContext()->getAnalysis<T>();
  }

  const ProgramStateRef &getState() const { return State; }

  template <typename T>
  Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
    return Location.getAs<T>();
  }

  /// Get the value of an arbitrary expression at this node.
  SVal getSVal(const Stmt *S) const {
    return getState()->getSVal(S, getLocationContext());
  }

  static void Profile(llvm::FoldingSetNodeID &ID,
                      const ProgramPoint &Loc,
                      const ProgramStateRef &state,
                      bool IsSink) {
    ID.Add(Loc);
    ID.AddPointer(state.get());
    ID.AddBoolean(IsSink);
  }

  void Profile(llvm::FoldingSetNodeID& ID) const {
    // We avoid copy constructors by not using accessors.
    Profile(ID, Location, State, isSink());
  }

  /// addPredeccessor - Adds a predecessor to the current node, and
  ///  in tandem add this node as a successor of the other node.
  void addPredecessor(ExplodedNode *V, ExplodedGraph &G);

  unsigned succ_size() const { return Succs.size(); }
  unsigned pred_size() const { return Preds.size(); }
  bool succ_empty() const { return Succs.empty(); }
  bool pred_empty() const { return Preds.empty(); }

  bool isSink() const { return Succs.getFlag(); }

  bool hasSinglePred() const {
    return (pred_size() == 1);
  }

  ExplodedNode *getFirstPred() {
    return pred_empty() ? nullptr : *(pred_begin());
  }

  const ExplodedNode *getFirstPred() const {
    return const_cast<ExplodedNode*>(this)->getFirstPred();
  }

  ExplodedNode *getFirstSucc() {
    return succ_empty() ? nullptr : *(succ_begin());
  }

  const ExplodedNode *getFirstSucc() const {
    return const_cast<ExplodedNode*>(this)->getFirstSucc();
  }

  // Iterators over successor and predecessor vertices.
  using succ_iterator = ExplodedNode * const *;
  using succ_range = llvm::iterator_range<succ_iterator>;

  using const_succ_iterator = const ExplodedNode * const *;
  using const_succ_range = llvm::iterator_range<const_succ_iterator>;

  using pred_iterator = ExplodedNode * const *;
  using pred_range = llvm::iterator_range<pred_iterator>;

  using const_pred_iterator = const ExplodedNode * const *;
  using const_pred_range = llvm::iterator_range<const_pred_iterator>;

  pred_iterator pred_begin() { return Preds.begin(); }
  pred_iterator pred_end() { return Preds.end(); }
  pred_range preds() { return {Preds.begin(), Preds.end()}; }

  const_pred_iterator pred_begin() const {
    return const_cast<ExplodedNode*>(this)->pred_begin();
  }
  const_pred_iterator pred_end() const {
    return const_cast<ExplodedNode*>(this)->pred_end();
  }
  const_pred_range preds() const { return {Preds.begin(), Preds.end()}; }

  succ_iterator succ_begin() { return Succs.begin(); }
  succ_iterator succ_end() { return Succs.end(); }
  succ_range succs() { return {Succs.begin(), Succs.end()}; }

  const_succ_iterator succ_begin() const {
    return const_cast<ExplodedNode*>(this)->succ_begin();
  }
  const_succ_iterator succ_end() const {
    return const_cast<ExplodedNode*>(this)->succ_end();
  }
  const_succ_range succs() const { return {Succs.begin(), Succs.end()}; }

  int64_t getID() const { return Id; }

  /// The node is trivial if it has only one successor, only one predecessor,
  /// it's predecessor has only one successor,
  /// and its program state is the same as the program state of the previous
  /// node.
  /// Trivial nodes may be skipped while printing exploded graph.
  bool isTrivial() const;

  /// If the node's program point corresponds to a statement, retrieve that
  /// statement. Useful for figuring out where to put a warning or a note.
  /// If the statement belongs to a body-farmed definition,
  /// retrieve the call site for that definition.
  const Stmt *getStmtForDiagnostics() const;

  /// Find the next statement that was executed on this node's execution path.
  /// Useful for explaining control flow that follows the current node.
  /// If the statement belongs to a body-farmed definition, retrieve the
  /// call site for that definition.
  const Stmt *getNextStmtForDiagnostics() const;

  /// Find the statement that was executed immediately before this node.
  /// Useful when the node corresponds to a CFG block entrance.
  /// If the statement belongs to a body-farmed definition, retrieve the
  /// call site for that definition.
  const Stmt *getPreviousStmtForDiagnostics() const;

  /// Find the statement that was executed at or immediately before this node.
  /// Useful when any nearby statement will do.
  /// If the statement belongs to a body-farmed definition, retrieve the
  /// call site for that definition.
  const Stmt *getCurrentOrPreviousStmtForDiagnostics() const;

private:
  void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
  void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
};

using InterExplodedGraphMap =
    llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;

class ExplodedGraph {
protected:
  friend class CoreEngine;

  // Type definitions.
  using NodeVector = std::vector<ExplodedNode *>;

  /// The roots of the simulation graph. Usually there will be only
  /// one, but clients are free to establish multiple subgraphs within a single
  /// SimulGraph. Moreover, these subgraphs can often merge when paths from
  /// different roots reach the same state at the same program location.
  NodeVector Roots;

  /// The nodes in the simulation graph which have been
  /// specially marked as the endpoint of an abstract simulation path.
  NodeVector EndNodes;

  /// Nodes - The nodes in the graph.
  llvm::FoldingSet<ExplodedNode> Nodes;

  /// BVC - Allocator and context for allocating nodes and their predecessor
  /// and successor groups.
  BumpVectorContext BVC;

  /// NumNodes - The number of nodes in the graph.
  int64_t NumNodes = 0;

  /// A list of recently allocated nodes that can potentially be recycled.
  NodeVector ChangedNodes;

  /// A list of nodes that can be reused.
  NodeVector FreeNodes;

  /// Determines how often nodes are reclaimed.
  ///
  /// If this is 0, nodes will never be reclaimed.
  unsigned ReclaimNodeInterval = 0;

  /// Counter to determine when to reclaim nodes.
  unsigned ReclaimCounter;

public:
  ExplodedGraph();
  ~ExplodedGraph();

  /// Retrieve the node associated with a (Location,State) pair,
  ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
  ///  this pair exists, it is created. IsNew is set to true if
  ///  the node was freshly created.
  ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
                        bool IsSink = false,
                        bool* IsNew = nullptr);

  /// Create a node for a (Location, State) pair,
  ///  but don't store it for deduplication later.  This
  ///  is useful when copying an already completed
  ///  ExplodedGraph for further processing.
  ExplodedNode *createUncachedNode(const ProgramPoint &L,
    ProgramStateRef State,
    int64_t Id,
    bool IsSink = false);

  std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
    return std::make_unique<ExplodedGraph>();
  }

  /// addRoot - Add an untyped node to the set of roots.
  ExplodedNode *addRoot(ExplodedNode *V) {
    Roots.push_back(V);
    return V;
  }

  /// addEndOfPath - Add an untyped node to the set of EOP nodes.
  ExplodedNode *addEndOfPath(ExplodedNode *V) {
    EndNodes.push_back(V);
    return V;
  }

  unsigned num_roots() const { return Roots.size(); }
  unsigned num_eops() const { return EndNodes.size(); }

  bool empty() const { return NumNodes == 0; }
  unsigned size() const { return NumNodes; }

  void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }

  // Iterators.
  using NodeTy = ExplodedNode;
  using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
  using roots_iterator = NodeVector::iterator;
  using const_roots_iterator = NodeVector::const_iterator;
  using eop_iterator = NodeVector::iterator;
  using const_eop_iterator = NodeVector::const_iterator;
  using node_iterator = AllNodesTy::iterator;
  using const_node_iterator = AllNodesTy::const_iterator;

  node_iterator nodes_begin() { return Nodes.begin(); }

  node_iterator nodes_end() { return Nodes.end(); }

  const_node_iterator nodes_begin() const { return Nodes.begin(); }

  const_node_iterator nodes_end() const { return Nodes.end(); }

  roots_iterator roots_begin() { return Roots.begin(); }

  roots_iterator roots_end() { return Roots.end(); }

  const_roots_iterator roots_begin() const { return Roots.begin(); }

  const_roots_iterator roots_end() const { return Roots.end(); }

  eop_iterator eop_begin() { return EndNodes.begin(); }

  eop_iterator eop_end() { return EndNodes.end(); }

  const_eop_iterator eop_begin() const { return EndNodes.begin(); }

  const_eop_iterator eop_end() const { return EndNodes.end(); }

  llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
  BumpVectorContext &getNodeAllocator() { return BVC; }

  using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;

  /// Creates a trimmed version of the graph that only contains paths leading
  /// to the given nodes.
  ///
  /// \param Nodes The nodes which must appear in the final graph. Presumably
  ///              these are end-of-path nodes (i.e. they have no successors).
  /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
  ///                        the returned graph.
  /// \param[out] InverseMap An optional map from nodes in the returned graph to
  ///                        nodes in this graph.
  /// \returns The trimmed graph
  std::unique_ptr<ExplodedGraph>
  trim(ArrayRef<const NodeTy *> Nodes,
       InterExplodedGraphMap *ForwardMap = nullptr,
       InterExplodedGraphMap *InverseMap = nullptr) const;

  /// Enable tracking of recently allocated nodes for potential reclamation
  /// when calling reclaimRecentlyAllocatedNodes().
  void enableNodeReclamation(unsigned Interval) {
    ReclaimCounter = ReclaimNodeInterval = Interval;
  }

  /// Reclaim "uninteresting" nodes created since the last time this method
  /// was called.
  void reclaimRecentlyAllocatedNodes();

  /// Returns true if nodes for the given expression kind are always
  ///        kept around.
  static bool isInterestingLValueExpr(const Expr *Ex);

private:
  bool shouldCollect(const ExplodedNode *node);
  void collectNode(ExplodedNode *node);
};

class ExplodedNodeSet {
  using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
  ImplTy Impl;

public:
  ExplodedNodeSet(ExplodedNode *N) {
    assert(N && !static_cast<ExplodedNode*>(N)->isSink());
    Impl.insert(N);
  }

  ExplodedNodeSet() = default;

  void Add(ExplodedNode *N) {
    if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
  }

  using iterator = ImplTy::iterator;
  using const_iterator = ImplTy::const_iterator;

  unsigned size() const { return Impl.size();  }
  bool empty()    const { return Impl.empty(); }
  bool erase(ExplodedNode *N) { return Impl.remove(N); }

  void clear() { Impl.clear(); }

  void insert(const ExplodedNodeSet &S) {
    assert(&S != this);
    if (empty())
      Impl = S.Impl;
    else
      Impl.insert(S.begin(), S.end());
  }

  iterator begin() { return Impl.begin(); }
  iterator end() { return Impl.end(); }

  const_iterator begin() const { return Impl.begin(); }
  const_iterator end() const { return Impl.end(); }
};

} // namespace ento

} // namespace clang

// GraphTraits

namespace llvm {
  template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
    using GraphTy = clang::ento::ExplodedGraph *;
    using NodeRef = clang::ento::ExplodedNode *;
    using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
    using nodes_iterator = llvm::df_iterator<GraphTy>;

    static NodeRef getEntryNode(const GraphTy G) {
      return *G->roots_begin();
    }

    static bool predecessorOfTrivial(NodeRef N) {
      return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
    }

    static ChildIteratorType child_begin(NodeRef N) {
      if (predecessorOfTrivial(N))
        return child_begin(*N->succ_begin());
      return N->succ_begin();
    }

    static ChildIteratorType child_end(NodeRef N) {
      if (predecessorOfTrivial(N))
        return child_end(N->getFirstSucc());
      return N->succ_end();
    }

    static nodes_iterator nodes_begin(const GraphTy G) {
      return df_begin(G);
    }

    static nodes_iterator nodes_end(const GraphTy G) {
      return df_end(G);
    }
  };
} // namespace llvm

#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H