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