Coverage Report

Created: 2021-01-19 06:58

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