Coverage Report

Created: 2018-09-25 23:22

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
Line
Count
Source (jump to first uncovered line)
1
//===- SymbolManager.h - Management of Symbolic Values ----------*- 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 SymbolManager, a class that manages symbolic values
11
//  created for use by ExprEngine and related classes.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
16
#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
17
18
#include "clang/AST/Expr.h"
19
#include "clang/AST/Type.h"
20
#include "clang/Analysis/AnalysisDeclContext.h"
21
#include "clang/Basic/LLVM.h"
22
#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
23
#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
24
#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
25
#include "llvm/ADT/DenseMap.h"
26
#include "llvm/ADT/DenseSet.h"
27
#include "llvm/ADT/FoldingSet.h"
28
#include "llvm/Support/Allocator.h"
29
#include <cassert>
30
31
namespace clang {
32
33
class ASTContext;
34
class Stmt;
35
36
namespace ento {
37
38
class BasicValueFactory;
39
class StoreManager;
40
41
///A symbol representing the value stored at a MemRegion.
42
class SymbolRegionValue : public SymbolData {
43
  const TypedValueRegion *R;
44
45
public:
46
  SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
47
13.6k
      : SymbolData(SymbolRegionValueKind, sym), R(r) {
48
13.6k
    assert(r);
49
13.6k
    assert(isValidTypeForSymbol(r->getValueType()));
50
13.6k
  }
51
52
1.20M
  const TypedValueRegion* getRegion() const { return R; }
53
54
623k
  static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
55
623k
    profile.AddInteger((unsigned) SymbolRegionValueKind);
56
623k
    profile.AddPointer(R);
57
623k
  }
58
59
330k
  void Profile(llvm::FoldingSetNodeID& profile) override {
60
330k
    Profile(profile, R);
61
330k
  }
62
63
  void dumpToStream(raw_ostream &os) const override;
64
1.05k
  const MemRegion *getOriginRegion() const override { return getRegion(); }
65
66
  QualType getType() const override;
67
68
  // Implement isa<T> support.
69
22.7k
  static bool classof(const SymExpr *SE) {
70
22.7k
    return SE->getKind() == SymbolRegionValueKind;
71
22.7k
  }
72
};
73
74
/// A symbol representing the result of an expression in the case when we do
75
/// not know anything about what the expression is.
76
class SymbolConjured : public SymbolData {
77
  const Stmt *S;
78
  QualType T;
79
  unsigned Count;
80
  const LocationContext *LCtx;
81
  const void *SymbolTag;
82
83
public:
84
  SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx,
85
                 QualType t, unsigned count, const void *symbolTag)
86
      : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count),
87
38.4k
        LCtx(lctx), SymbolTag(symbolTag) {
88
38.4k
    // FIXME: 's' might be a nullptr if we're conducting invalidation
89
38.4k
    // that was caused by a destructor call on a temporary object,
90
38.4k
    // which has no statement associated with it.
91
38.4k
    // Due to this, we might be creating the same invalidation symbol for
92
38.4k
    // two different invalidation passes (for two different temporaries).
93
38.4k
    assert(lctx);
94
38.4k
    assert(isValidTypeForSymbol(t));
95
38.4k
  }
96
97
57
  const Stmt *getStmt() const { return S; }
98
0
  unsigned getCount() const { return Count; }
99
0
  const void *getTag() const { return SymbolTag; }
100
101
  QualType getType() const override;
102
103
  void dumpToStream(raw_ostream &os) const override;
104
105
  static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
106
                      QualType T, unsigned Count, const LocationContext *LCtx,
107
219k
                      const void *SymbolTag) {
108
219k
    profile.AddInteger((unsigned) SymbolConjuredKind);
109
219k
    profile.AddPointer(S);
110
219k
    profile.AddPointer(LCtx);
111
219k
    profile.Add(T);
112
219k
    profile.AddInteger(Count);
113
219k
    profile.AddPointer(SymbolTag);
114
219k
  }
115
116
133k
  void Profile(llvm::FoldingSetNodeID& profile) override {
117
133k
    Profile(profile, S, T, Count, LCtx, SymbolTag);
118
133k
  }
119
120
  // Implement isa<T> support.
121
1.34k
  static bool classof(const SymExpr *SE) {
122
1.34k
    return SE->getKind() == SymbolConjuredKind;
123
1.34k
  }
124
};
125
126
/// A symbol representing the value of a MemRegion whose parent region has
127
/// symbolic value.
128
class SymbolDerived : public SymbolData {
129
  SymbolRef parentSymbol;
130
  const TypedValueRegion *R;
131
132
public:
133
  SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
134
1.22k
      : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {
135
1.22k
    assert(parent);
136
1.22k
    assert(r);
137
1.22k
    assert(isValidTypeForSymbol(r->getValueType()));
138
1.22k
  }
139
140
301k
  SymbolRef getParentSymbol() const { return parentSymbol; }
141
225
  const TypedValueRegion *getRegion() const { return R; }
142
143
  QualType getType() const override;
144
145
  void dumpToStream(raw_ostream &os) const override;
146
109
  const MemRegion *getOriginRegion() const override { return getRegion(); }
147
148
  static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
149
26.5k
                      const TypedValueRegion *r) {
150
26.5k
    profile.AddInteger((unsigned) SymbolDerivedKind);
151
26.5k
    profile.AddPointer(r);
152
26.5k
    profile.AddPointer(parent);
153
26.5k
  }
154
155
15.3k
  void Profile(llvm::FoldingSetNodeID& profile) override {
156
15.3k
    Profile(profile, parentSymbol, R);
157
15.3k
  }
158
159
  // Implement isa<T> support.
160
31.0k
  static bool classof(const SymExpr *SE) {
161
31.0k
    return SE->getKind() == SymbolDerivedKind;
162
31.0k
  }
163
};
164
165
/// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
166
///  Clients should not ask the SymbolManager for a region's extent. Always use
167
///  SubRegion::getExtent instead -- the value returned may not be a symbol.
168
class SymbolExtent : public SymbolData {
169
  const SubRegion *R;
170
171
public:
172
  SymbolExtent(SymbolID sym, const SubRegion *r)
173
1.53k
      : SymbolData(SymbolExtentKind, sym), R(r) {
174
1.53k
    assert(r);
175
1.53k
  }
176
177
16.4k
  const SubRegion *getRegion() const { return R; }
178
179
  QualType getType() const override;
180
181
  void dumpToStream(raw_ostream &os) const override;
182
183
2.92k
  static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
184
2.92k
    profile.AddInteger((unsigned) SymbolExtentKind);
185
2.92k
    profile.AddPointer(R);
186
2.92k
  }
187
188
866
  void Profile(llvm::FoldingSetNodeID& profile) override {
189
866
    Profile(profile, R);
190
866
  }
191
192
  // Implement isa<T> support.
193
0
  static bool classof(const SymExpr *SE) {
194
0
    return SE->getKind() == SymbolExtentKind;
195
0
  }
196
};
197
198
/// SymbolMetadata - Represents path-dependent metadata about a specific region.
199
///  Metadata symbols remain live as long as they are marked as in use before
200
///  dead-symbol sweeping AND their associated regions are still alive.
201
///  Intended for use by checkers.
202
class SymbolMetadata : public SymbolData {
203
  const MemRegion* R;
204
  const Stmt *S;
205
  QualType T;
206
  const LocationContext *LCtx;
207
  unsigned Count;
208
  const void *Tag;
209
210
public:
211
  SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t,
212
                 const LocationContext *LCtx, unsigned count, const void *tag)
213
      : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), LCtx(LCtx),
214
367
        Count(count), Tag(tag) {
215
367
      assert(r);
216
367
      assert(s);
217
367
      assert(isValidTypeForSymbol(t));
218
367
      assert(LCtx);
219
367
      assert(tag);
220
367
    }
221
222
2.32k
  const MemRegion *getRegion() const { return R; }
223
0
  const Stmt *getStmt() const { return S; }
224
0
  const LocationContext *getLocationContext() const { return LCtx; }
225
0
  unsigned getCount() const { return Count; }
226
0
  const void *getTag() const { return Tag; }
227
228
  QualType getType() const override;
229
230
  void dumpToStream(raw_ostream &os) const override;
231
232
  static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
233
                      const Stmt *S, QualType T, const LocationContext *LCtx,
234
471
                      unsigned Count, const void *Tag) {
235
471
    profile.AddInteger((unsigned) SymbolMetadataKind);
236
471
    profile.AddPointer(R);
237
471
    profile.AddPointer(S);
238
471
    profile.Add(T);
239
471
    profile.AddPointer(LCtx);
240
471
    profile.AddInteger(Count);
241
471
    profile.AddPointer(Tag);
242
471
  }
243
244
80
  void Profile(llvm::FoldingSetNodeID& profile) override {
245
80
    Profile(profile, R, S, T, LCtx, Count, Tag);
246
80
  }
247
248
  // Implement isa<T> support.
249
5.73k
  static bool classof(const SymExpr *SE) {
250
5.73k
    return SE->getKind() == SymbolMetadataKind;
251
5.73k
  }
252
};
253
254
/// Represents a cast expression.
255
class SymbolCast : public SymExpr {
256
  const SymExpr *Operand;
257
258
  /// Type of the operand.
259
  QualType FromTy;
260
261
  /// The type of the result.
262
  QualType ToTy;
263
264
public:
265
  SymbolCast(const SymExpr *In, QualType From, QualType To)
266
25
      : SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) {
267
25
    assert(In);
268
25
    assert(isValidTypeForSymbol(From));
269
25
    // FIXME: GenericTaintChecker creates symbols of void type.
270
25
    // Otherwise, 'To' should also be a valid type.
271
25
  }
272
273
0
  unsigned computeComplexity() const override {
274
0
    if (Complexity == 0)
275
0
      Complexity = 1 + Operand->computeComplexity();
276
0
    return Complexity;
277
0
  }
278
279
94
  QualType getType() const override { return ToTy; }
280
281
455
  const SymExpr *getOperand() const { return Operand; }
282
283
  void dumpToStream(raw_ostream &os) const override;
284
285
  static void Profile(llvm::FoldingSetNodeID& ID,
286
37
                      const SymExpr *In, QualType From, QualType To) {
287
37
    ID.AddInteger((unsigned) SymbolCastKind);
288
37
    ID.AddPointer(In);
289
37
    ID.Add(From);
290
37
    ID.Add(To);
291
37
  }
292
293
7
  void Profile(llvm::FoldingSetNodeID& ID) override {
294
7
    Profile(ID, Operand, FromTy, ToTy);
295
7
  }
296
297
  // Implement isa<T> support.
298
22.5k
  static bool classof(const SymExpr *SE) {
299
22.5k
    return SE->getKind() == SymbolCastKind;
300
22.5k
  }
301
};
302
303
/// Represents a symbolic expression involving a binary operator
304
class BinarySymExpr : public SymExpr {
305
  BinaryOperator::Opcode Op;
306
  QualType T;
307
308
protected:
309
  BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
310
18.3k
      : SymExpr(k), Op(op), T(t) {
311
18.3k
    assert(classof(this));
312
18.3k
    // Binary expressions are results of arithmetic. Pointer arithmetic is not
313
18.3k
    // handled by binary expressions, but it is instead handled by applying
314
18.3k
    // sub-regions to regions.
315
18.3k
    assert(isValidTypeForSymbol(t) && !Loc::isLocType(t));
316
18.3k
  }
317
318
public:
319
  // FIXME: We probably need to make this out-of-line to avoid redundant
320
  // generation of virtual functions.
321
514k
  QualType getType() const override { return T; }
322
323
720k
  BinaryOperator::Opcode getOpcode() const { return Op; }
324
325
  // Implement isa<T> support.
326
140k
  static bool classof(const SymExpr *SE) {
327
140k
    Kind k = SE->getKind();
328
140k
    return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
329
140k
  }
330
};
331
332
/// Represents a symbolic expression like 'x' + 3.
333
class SymIntExpr : public BinarySymExpr {
334
  const SymExpr *LHS;
335
  const llvm::APSInt& RHS;
336
337
public:
338
  SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
339
             const llvm::APSInt &rhs, QualType t)
340
16.8k
      : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {
341
16.8k
    assert(lhs);
342
16.8k
  }
343
344
  void dumpToStream(raw_ostream &os) const override;
345
346
2.02M
  const SymExpr *getLHS() const { return LHS; }
347
196k
  const llvm::APSInt &getRHS() const { return RHS; }
348
349
2.45k
  unsigned computeComplexity() const override {
350
2.45k
    if (Complexity == 0)
351
363
      Complexity = 1 + LHS->computeComplexity();
352
2.45k
    return Complexity;
353
2.45k
  }
354
355
  static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
356
                      BinaryOperator::Opcode op, const llvm::APSInt& rhs,
357
395k
                      QualType t) {
358
395k
    ID.AddInteger((unsigned) SymIntExprKind);
359
395k
    ID.AddPointer(lhs);
360
395k
    ID.AddInteger(op);
361
395k
    ID.AddPointer(&rhs);
362
395k
    ID.Add(t);
363
395k
  }
364
365
248k
  void Profile(llvm::FoldingSetNodeID& ID) override {
366
248k
    Profile(ID, LHS, getOpcode(), RHS, getType());
367
248k
  }
368
369
  // Implement isa<T> support.
370
606k
  static bool classof(const SymExpr *SE) {
371
606k
    return SE->getKind() == SymIntExprKind;
372
606k
  }
373
};
374
375
/// Represents a symbolic expression like 3 - 'x'.
376
class IntSymExpr : public BinarySymExpr {
377
  const llvm::APSInt& LHS;
378
  const SymExpr *RHS;
379
380
public:
381
  IntSymExpr(const llvm::APSInt &lhs, BinaryOperator::Opcode op,
382
             const SymExpr *rhs, QualType t)
383
119
      : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {
384
119
    assert(rhs);
385
119
  }
386
387
  void dumpToStream(raw_ostream &os) const override;
388
389
4.41k
  const SymExpr *getRHS() const { return RHS; }
390
0
  const llvm::APSInt &getLHS() const { return LHS; }
391
392
20
  unsigned computeComplexity() const override {
393
20
    if (Complexity == 0)
394
12
      Complexity = 1 + RHS->computeComplexity();
395
20
    return Complexity;
396
20
  }
397
398
  static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
399
                      BinaryOperator::Opcode op, const SymExpr *rhs,
400
193
                      QualType t) {
401
193
    ID.AddInteger((unsigned) IntSymExprKind);
402
193
    ID.AddPointer(&lhs);
403
193
    ID.AddInteger(op);
404
193
    ID.AddPointer(rhs);
405
193
    ID.Add(t);
406
193
  }
407
408
57
  void Profile(llvm::FoldingSetNodeID& ID) override {
409
57
    Profile(ID, LHS, getOpcode(), RHS, getType());
410
57
  }
411
412
  // Implement isa<T> support.
413
0
  static bool classof(const SymExpr *SE) {
414
0
    return SE->getKind() == IntSymExprKind;
415
0
  }
416
};
417
418
/// Represents a symbolic expression like 'x' + 'y'.
419
class SymSymExpr : public BinarySymExpr {
420
  const SymExpr *LHS;
421
  const SymExpr *RHS;
422
423
public:
424
  SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
425
             QualType t)
426
1.40k
      : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {
427
1.40k
    assert(lhs);
428
1.40k
    assert(rhs);
429
1.40k
  }
430
431
810k
  const SymExpr *getLHS() const { return LHS; }
432
754k
  const SymExpr *getRHS() const { return RHS; }
433
434
  void dumpToStream(raw_ostream &os) const override;
435
436
6.56k
  unsigned computeComplexity() const override {
437
6.56k
    if (Complexity == 0)
438
314
      Complexity = RHS->computeComplexity() + LHS->computeComplexity();
439
6.56k
    return Complexity;
440
6.56k
  }
441
442
  static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
443
45.2k
                    BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
444
45.2k
    ID.AddInteger((unsigned) SymSymExprKind);
445
45.2k
    ID.AddPointer(lhs);
446
45.2k
    ID.AddInteger(op);
447
45.2k
    ID.AddPointer(rhs);
448
45.2k
    ID.Add(t);
449
45.2k
  }
450
451
34.1k
  void Profile(llvm::FoldingSetNodeID& ID) override {
452
34.1k
    Profile(ID, LHS, getOpcode(), RHS, getType());
453
34.1k
  }
454
455
  // Implement isa<T> support.
456
87.8k
  static bool classof(const SymExpr *SE) {
457
87.8k
    return SE->getKind() == SymSymExprKind;
458
87.8k
  }
459
};
460
461
class SymbolManager {
462
  using DataSetTy = llvm::FoldingSet<SymExpr>;
463
  using SymbolDependTy = llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy *>;
464
465
  DataSetTy DataSet;
466
467
  /// Stores the extra dependencies between symbols: the data should be kept
468
  /// alive as long as the key is live.
469
  SymbolDependTy SymbolDependencies;
470
471
  unsigned SymbolCounter = 0;
472
  llvm::BumpPtrAllocator& BPAlloc;
473
  BasicValueFactory &BV;
474
  ASTContext &Ctx;
475
476
public:
477
  SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
478
                llvm::BumpPtrAllocator& bpalloc)
479
9.75k
      : SymbolDependencies(16), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
480
  ~SymbolManager();
481
482
  static bool canSymbolicate(QualType T);
483
484
  /// Make a unique symbol for MemRegion R according to its kind.
485
  const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
486
487
  const SymbolConjured* conjureSymbol(const Stmt *E,
488
                                      const LocationContext *LCtx,
489
                                      QualType T,
490
                                      unsigned VisitCount,
491
                                      const void *SymbolTag = nullptr);
492
493
  const SymbolConjured* conjureSymbol(const Expr *E,
494
                                      const LocationContext *LCtx,
495
                                      unsigned VisitCount,
496
0
                                      const void *SymbolTag = nullptr) {
497
0
    return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
498
0
  }
499
500
  const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
501
                                        const TypedValueRegion *R);
502
503
  const SymbolExtent *getExtentSymbol(const SubRegion *R);
504
505
  /// Creates a metadata symbol associated with a specific region.
506
  ///
507
  /// VisitCount can be used to differentiate regions corresponding to
508
  /// different loop iterations, thus, making the symbol path-dependent.
509
  const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S,
510
                                          QualType T,
511
                                          const LocationContext *LCtx,
512
                                          unsigned VisitCount,
513
                                          const void *SymbolTag = nullptr);
514
515
  const SymbolCast* getCastSymbol(const SymExpr *Operand,
516
                                  QualType From, QualType To);
517
518
  const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
519
                                  const llvm::APSInt& rhs, QualType t);
520
521
  const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
522
0
                                  const llvm::APSInt& rhs, QualType t) {
523
0
    return getSymIntExpr(&lhs, op, rhs, t);
524
0
  }
525
526
  const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
527
                                  BinaryOperator::Opcode op,
528
                                  const SymExpr *rhs, QualType t);
529
530
  const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
531
                                  const SymExpr *rhs, QualType t);
532
533
292
  QualType getType(const SymExpr *SE) const {
534
292
    return SE->getType();
535
292
  }
536
537
  /// Add artificial symbol dependency.
538
  ///
539
  /// The dependent symbol should stay alive as long as the primary is alive.
540
  void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
541
542
  const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
543
544
575
  ASTContext &getContext() { return Ctx; }
545
268
  BasicValueFactory &getBasicVals() { return BV; }
546
};
547
548
/// A class responsible for cleaning up unused symbols.
549
class SymbolReaper {
550
  enum SymbolStatus {
551
    NotProcessed,
552
    HaveMarkedDependents
553
  };
554
555
  using SymbolSetTy = llvm::DenseSet<SymbolRef>;
556
  using SymbolMapTy = llvm::DenseMap<SymbolRef, SymbolStatus>;
557
  using RegionSetTy = llvm::DenseSet<const MemRegion *>;
558
559
  SymbolMapTy TheLiving;
560
  SymbolSetTy MetadataInUse;
561
  SymbolSetTy TheDead;
562
563
  RegionSetTy RegionRoots;
564
565
  const StackFrameContext *LCtx;
566
  const Stmt *Loc;
567
  SymbolManager& SymMgr;
568
  StoreRef reapedStore;
569
  llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
570
571
public:
572
  /// Construct a reaper object, which removes everything which is not
573
  /// live before we execute statement s in the given location context.
574
  ///
575
  /// If the statement is NULL, everything is this and parent contexts is
576
  /// considered live.
577
  /// If the stack frame context is NULL, everything on stack is considered
578
  /// dead.
579
  SymbolReaper(const StackFrameContext *Ctx, const Stmt *s,
580
               SymbolManager &symmgr, StoreManager &storeMgr)
581
260k
      : LCtx(Ctx), Loc(s), SymMgr(symmgr), reapedStore(nullptr, storeMgr) {}
582
583
  const LocationContext *getLocationContext() const { return LCtx; }
584
585
  bool isLive(SymbolRef sym);
586
  bool isLiveRegion(const MemRegion *region);
587
  bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
588
  bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
589
590
  /// Unconditionally marks a symbol as live.
591
  ///
592
  /// This should never be
593
  /// used by checkers, only by the state infrastructure such as the store and
594
  /// environment. Checkers should instead use metadata symbols and markInUse.
595
  void markLive(SymbolRef sym);
596
597
  /// Marks a symbol as important to a checker.
598
  ///
599
  /// For metadata symbols,
600
  /// this will keep the symbol alive as long as its associated region is also
601
  /// live. For other symbols, this has no effect; checkers are not permitted
602
  /// to influence the life of other symbols. This should be used before any
603
  /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
604
  void markInUse(SymbolRef sym);
605
606
  /// If a symbol is known to be live, marks the symbol as live.
607
  ///
608
  ///  Otherwise, if the symbol cannot be proven live, it is marked as dead.
609
  ///  Returns true if the symbol is dead, false if live.
610
  bool maybeDead(SymbolRef sym);
611
612
  using dead_iterator = SymbolSetTy::const_iterator;
613
614
2.27k
  dead_iterator dead_begin() const { return TheDead.begin(); }
615
2.27k
  dead_iterator dead_end() const { return TheDead.end(); }
616
617
332k
  bool hasDeadSymbols() const {
618
332k
    return !TheDead.empty();
619
332k
  }
620
621
  using region_iterator = RegionSetTy::const_iterator;
622
623
260k
  region_iterator region_begin() const { return RegionRoots.begin(); }
624
260k
  region_iterator region_end() const { return RegionRoots.end(); }
625
626
  /// Returns whether or not a symbol has been confirmed dead.
627
  ///
628
  /// This should only be called once all marking of dead symbols has completed.
629
  /// (For checkers, this means only in the evalDeadSymbols callback.)
630
3.69k
  bool isDead(SymbolRef sym) const {
631
3.69k
    return TheDead.count(sym);
632
3.69k
  }
633
634
  void markLive(const MemRegion *region);
635
  void markElementIndicesLive(const MemRegion *region);
636
637
  /// Set to the value of the symbolic store after
638
  /// StoreManager::removeDeadBindings has been called.
639
260k
  void setReapedStore(StoreRef st) { reapedStore = st; }
640
641
private:
642
  /// Mark the symbols dependent on the input symbol as live.
643
  void markDependentsLive(SymbolRef sym);
644
};
645
646
class SymbolVisitor {
647
protected:
648
  ~SymbolVisitor() = default;
649
650
public:
651
264k
  SymbolVisitor() = default;
652
  SymbolVisitor(const SymbolVisitor &) = default;
653
  SymbolVisitor(SymbolVisitor &&) {}
654
655
  /// A visitor method invoked by ProgramStateManager::scanReachableSymbols.
656
  ///
657
  /// The method returns \c true if symbols should continue be scanned and \c
658
  /// false otherwise.
659
  virtual bool VisitSymbol(SymbolRef sym) = 0;
660
877
  virtual bool VisitMemRegion(const MemRegion *region) { return true; }
661
};
662
663
} // namespace ento
664
665
} // namespace clang
666
667
#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H