Coverage Report

Created: 2022-07-16 07:03

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