1 //===- SymbolManager.h - Management of Symbolic Values ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines SymbolManager, a class that manages symbolic values
11 // created for use by ExprEngine and related classes.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
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"
38 class BasicValueFactory;
41 ///A symbol representing the value stored at a MemRegion.
42 class SymbolRegionValue : public SymbolData {
43 const TypedValueRegion *R;
46 SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
47 : SymbolData(SymbolRegionValueKind, sym), R(r) {
49 assert(isValidTypeForSymbol(r->getValueType()));
52 const TypedValueRegion* getRegion() const { return R; }
54 static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
55 profile.AddInteger((unsigned) SymbolRegionValueKind);
56 profile.AddPointer(R);
59 void Profile(llvm::FoldingSetNodeID& profile) override {
63 void dumpToStream(raw_ostream &os) const override;
64 const MemRegion *getOriginRegion() const override { return getRegion(); }
66 QualType getType() const override;
68 // Implement isa<T> support.
69 static bool classof(const SymExpr *SE) {
70 return SE->getKind() == SymbolRegionValueKind;
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 {
80 const LocationContext *LCtx;
81 const void *SymbolTag;
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 LCtx(lctx), SymbolTag(symbolTag) {
88 // FIXME: 's' might be a nullptr if we're conducting invalidation
89 // that was caused by a destructor call on a temporary object,
90 // which has no statement associated with it.
91 // Due to this, we might be creating the same invalidation symbol for
92 // two different invalidation passes (for two different temporaries).
94 assert(isValidTypeForSymbol(t));
97 const Stmt *getStmt() const { return S; }
98 unsigned getCount() const { return Count; }
99 const void *getTag() const { return SymbolTag; }
101 QualType getType() const override;
103 void dumpToStream(raw_ostream &os) const override;
105 static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
106 QualType T, unsigned Count, const LocationContext *LCtx,
107 const void *SymbolTag) {
108 profile.AddInteger((unsigned) SymbolConjuredKind);
109 profile.AddPointer(S);
110 profile.AddPointer(LCtx);
112 profile.AddInteger(Count);
113 profile.AddPointer(SymbolTag);
116 void Profile(llvm::FoldingSetNodeID& profile) override {
117 Profile(profile, S, T, Count, LCtx, SymbolTag);
120 // Implement isa<T> support.
121 static bool classof(const SymExpr *SE) {
122 return SE->getKind() == SymbolConjuredKind;
126 /// A symbol representing the value of a MemRegion whose parent region has
128 class SymbolDerived : public SymbolData {
129 SymbolRef parentSymbol;
130 const TypedValueRegion *R;
133 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
134 : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {
137 assert(isValidTypeForSymbol(r->getValueType()));
140 SymbolRef getParentSymbol() const { return parentSymbol; }
141 const TypedValueRegion *getRegion() const { return R; }
143 QualType getType() const override;
145 void dumpToStream(raw_ostream &os) const override;
146 const MemRegion *getOriginRegion() const override { return getRegion(); }
148 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
149 const TypedValueRegion *r) {
150 profile.AddInteger((unsigned) SymbolDerivedKind);
151 profile.AddPointer(r);
152 profile.AddPointer(parent);
155 void Profile(llvm::FoldingSetNodeID& profile) override {
156 Profile(profile, parentSymbol, R);
159 // Implement isa<T> support.
160 static bool classof(const SymExpr *SE) {
161 return SE->getKind() == SymbolDerivedKind;
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 {
172 SymbolExtent(SymbolID sym, const SubRegion *r)
173 : SymbolData(SymbolExtentKind, sym), R(r) {
177 const SubRegion *getRegion() const { return R; }
179 QualType getType() const override;
181 void dumpToStream(raw_ostream &os) const override;
183 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
184 profile.AddInteger((unsigned) SymbolExtentKind);
185 profile.AddPointer(R);
188 void Profile(llvm::FoldingSetNodeID& profile) override {
192 // Implement isa<T> support.
193 static bool classof(const SymExpr *SE) {
194 return SE->getKind() == SymbolExtentKind;
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 {
206 const LocationContext *LCtx;
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 Count(count), Tag(tag) {
217 assert(isValidTypeForSymbol(t));
222 const MemRegion *getRegion() const { return R; }
223 const Stmt *getStmt() const { return S; }
224 const LocationContext *getLocationContext() const { return LCtx; }
225 unsigned getCount() const { return Count; }
226 const void *getTag() const { return Tag; }
228 QualType getType() const override;
230 void dumpToStream(raw_ostream &os) const override;
232 static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
233 const Stmt *S, QualType T, const LocationContext *LCtx,
234 unsigned Count, const void *Tag) {
235 profile.AddInteger((unsigned) SymbolMetadataKind);
236 profile.AddPointer(R);
237 profile.AddPointer(S);
239 profile.AddPointer(LCtx);
240 profile.AddInteger(Count);
241 profile.AddPointer(Tag);
244 void Profile(llvm::FoldingSetNodeID& profile) override {
245 Profile(profile, R, S, T, LCtx, Count, Tag);
248 // Implement isa<T> support.
249 static bool classof(const SymExpr *SE) {
250 return SE->getKind() == SymbolMetadataKind;
254 /// Represents a cast expression.
255 class SymbolCast : public SymExpr {
256 const SymExpr *Operand;
258 /// Type of the operand.
261 /// The type of the result.
265 SymbolCast(const SymExpr *In, QualType From, QualType To)
266 : SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) {
268 assert(isValidTypeForSymbol(From));
269 // FIXME: GenericTaintChecker creates symbols of void type.
270 // Otherwise, 'To' should also be a valid type.
273 unsigned computeComplexity() const override {
275 Complexity = 1 + Operand->computeComplexity();
279 QualType getType() const override { return ToTy; }
281 const SymExpr *getOperand() const { return Operand; }
283 void dumpToStream(raw_ostream &os) const override;
285 static void Profile(llvm::FoldingSetNodeID& ID,
286 const SymExpr *In, QualType From, QualType To) {
287 ID.AddInteger((unsigned) SymbolCastKind);
293 void Profile(llvm::FoldingSetNodeID& ID) override {
294 Profile(ID, Operand, FromTy, ToTy);
297 // Implement isa<T> support.
298 static bool classof(const SymExpr *SE) {
299 return SE->getKind() == SymbolCastKind;
303 /// Represents a symbolic expression involving a binary operator
304 class BinarySymExpr : public SymExpr {
305 BinaryOperator::Opcode Op;
309 BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
310 : SymExpr(k), Op(op), T(t) {
311 assert(classof(this));
312 assert(isValidTypeForSymbol(t));
316 // FIXME: We probably need to make this out-of-line to avoid redundant
317 // generation of virtual functions.
318 QualType getType() const override { return T; }
320 BinaryOperator::Opcode getOpcode() const { return Op; }
322 // Implement isa<T> support.
323 static bool classof(const SymExpr *SE) {
324 Kind k = SE->getKind();
325 return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
329 /// Represents a symbolic expression like 'x' + 3.
330 class SymIntExpr : public BinarySymExpr {
332 const llvm::APSInt& RHS;
335 SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
336 const llvm::APSInt &rhs, QualType t)
337 : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {
341 void dumpToStream(raw_ostream &os) const override;
343 const SymExpr *getLHS() const { return LHS; }
344 const llvm::APSInt &getRHS() const { return RHS; }
346 unsigned computeComplexity() const override {
348 Complexity = 1 + LHS->computeComplexity();
352 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
353 BinaryOperator::Opcode op, const llvm::APSInt& rhs,
355 ID.AddInteger((unsigned) SymIntExprKind);
362 void Profile(llvm::FoldingSetNodeID& ID) override {
363 Profile(ID, LHS, getOpcode(), RHS, getType());
366 // Implement isa<T> support.
367 static bool classof(const SymExpr *SE) {
368 return SE->getKind() == SymIntExprKind;
372 /// Represents a symbolic expression like 3 - 'x'.
373 class IntSymExpr : public BinarySymExpr {
374 const llvm::APSInt& LHS;
378 IntSymExpr(const llvm::APSInt &lhs, BinaryOperator::Opcode op,
379 const SymExpr *rhs, QualType t)
380 : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {
384 void dumpToStream(raw_ostream &os) const override;
386 const SymExpr *getRHS() const { return RHS; }
387 const llvm::APSInt &getLHS() const { return LHS; }
389 unsigned computeComplexity() const override {
391 Complexity = 1 + RHS->computeComplexity();
395 static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
396 BinaryOperator::Opcode op, const SymExpr *rhs,
398 ID.AddInteger((unsigned) IntSymExprKind);
405 void Profile(llvm::FoldingSetNodeID& ID) override {
406 Profile(ID, LHS, getOpcode(), RHS, getType());
409 // Implement isa<T> support.
410 static bool classof(const SymExpr *SE) {
411 return SE->getKind() == IntSymExprKind;
415 /// Represents a symbolic expression like 'x' + 'y'.
416 class SymSymExpr : public BinarySymExpr {
421 SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
423 : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {
428 const SymExpr *getLHS() const { return LHS; }
429 const SymExpr *getRHS() const { return RHS; }
431 void dumpToStream(raw_ostream &os) const override;
433 unsigned computeComplexity() const override {
435 Complexity = RHS->computeComplexity() + LHS->computeComplexity();
439 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
440 BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
441 ID.AddInteger((unsigned) SymSymExprKind);
448 void Profile(llvm::FoldingSetNodeID& ID) override {
449 Profile(ID, LHS, getOpcode(), RHS, getType());
452 // Implement isa<T> support.
453 static bool classof(const SymExpr *SE) {
454 return SE->getKind() == SymSymExprKind;
458 class SymbolManager {
459 using DataSetTy = llvm::FoldingSet<SymExpr>;
460 using SymbolDependTy = llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy *>;
464 /// Stores the extra dependencies between symbols: the data should be kept
465 /// alive as long as the key is live.
466 SymbolDependTy SymbolDependencies;
468 unsigned SymbolCounter = 0;
469 llvm::BumpPtrAllocator& BPAlloc;
470 BasicValueFactory &BV;
474 SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
475 llvm::BumpPtrAllocator& bpalloc)
476 : SymbolDependencies(16), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
479 static bool canSymbolicate(QualType T);
481 /// Make a unique symbol for MemRegion R according to its kind.
482 const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
484 const SymbolConjured* conjureSymbol(const Stmt *E,
485 const LocationContext *LCtx,
488 const void *SymbolTag = nullptr);
490 const SymbolConjured* conjureSymbol(const Expr *E,
491 const LocationContext *LCtx,
493 const void *SymbolTag = nullptr) {
494 return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
497 const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
498 const TypedValueRegion *R);
500 const SymbolExtent *getExtentSymbol(const SubRegion *R);
502 /// Creates a metadata symbol associated with a specific region.
504 /// VisitCount can be used to differentiate regions corresponding to
505 /// different loop iterations, thus, making the symbol path-dependent.
506 const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S,
508 const LocationContext *LCtx,
510 const void *SymbolTag = nullptr);
512 const SymbolCast* getCastSymbol(const SymExpr *Operand,
513 QualType From, QualType To);
515 const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
516 const llvm::APSInt& rhs, QualType t);
518 const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
519 const llvm::APSInt& rhs, QualType t) {
520 return getSymIntExpr(&lhs, op, rhs, t);
523 const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
524 BinaryOperator::Opcode op,
525 const SymExpr *rhs, QualType t);
527 const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
528 const SymExpr *rhs, QualType t);
530 QualType getType(const SymExpr *SE) const {
531 return SE->getType();
534 /// Add artificial symbol dependency.
536 /// The dependent symbol should stay alive as long as the primary is alive.
537 void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
539 const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
541 ASTContext &getContext() { return Ctx; }
542 BasicValueFactory &getBasicVals() { return BV; }
545 /// A class responsible for cleaning up unused symbols.
552 using SymbolSetTy = llvm::DenseSet<SymbolRef>;
553 using SymbolMapTy = llvm::DenseMap<SymbolRef, SymbolStatus>;
554 using RegionSetTy = llvm::DenseSet<const MemRegion *>;
556 SymbolMapTy TheLiving;
557 SymbolSetTy MetadataInUse;
560 RegionSetTy RegionRoots;
562 const StackFrameContext *LCtx;
564 SymbolManager& SymMgr;
565 StoreRef reapedStore;
566 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
569 /// Construct a reaper object, which removes everything which is not
570 /// live before we execute statement s in the given location context.
572 /// If the statement is NULL, everything is this and parent contexts is
574 /// If the stack frame context is NULL, everything on stack is considered
576 SymbolReaper(const StackFrameContext *Ctx, const Stmt *s,
577 SymbolManager &symmgr, StoreManager &storeMgr)
578 : LCtx(Ctx), Loc(s), SymMgr(symmgr), reapedStore(nullptr, storeMgr) {}
580 const LocationContext *getLocationContext() const { return LCtx; }
582 bool isLive(SymbolRef sym);
583 bool isLiveRegion(const MemRegion *region);
584 bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
585 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
587 /// Unconditionally marks a symbol as live.
589 /// This should never be
590 /// used by checkers, only by the state infrastructure such as the store and
591 /// environment. Checkers should instead use metadata symbols and markInUse.
592 void markLive(SymbolRef sym);
594 /// Marks a symbol as important to a checker.
596 /// For metadata symbols,
597 /// this will keep the symbol alive as long as its associated region is also
598 /// live. For other symbols, this has no effect; checkers are not permitted
599 /// to influence the life of other symbols. This should be used before any
600 /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
601 void markInUse(SymbolRef sym);
603 /// If a symbol is known to be live, marks the symbol as live.
605 /// Otherwise, if the symbol cannot be proven live, it is marked as dead.
606 /// Returns true if the symbol is dead, false if live.
607 bool maybeDead(SymbolRef sym);
609 using dead_iterator = SymbolSetTy::const_iterator;
611 dead_iterator dead_begin() const { return TheDead.begin(); }
612 dead_iterator dead_end() const { return TheDead.end(); }
614 bool hasDeadSymbols() const {
615 return !TheDead.empty();
618 using region_iterator = RegionSetTy::const_iterator;
620 region_iterator region_begin() const { return RegionRoots.begin(); }
621 region_iterator region_end() const { return RegionRoots.end(); }
623 /// Returns whether or not a symbol has been confirmed dead.
625 /// This should only be called once all marking of dead symbols has completed.
626 /// (For checkers, this means only in the evalDeadSymbols callback.)
627 bool isDead(SymbolRef sym) const {
628 return TheDead.count(sym);
631 void markLive(const MemRegion *region);
632 void markElementIndicesLive(const MemRegion *region);
634 /// Set to the value of the symbolic store after
635 /// StoreManager::removeDeadBindings has been called.
636 void setReapedStore(StoreRef st) { reapedStore = st; }
639 /// Mark the symbols dependent on the input symbol as live.
640 void markDependentsLive(SymbolRef sym);
643 class SymbolVisitor {
645 ~SymbolVisitor() = default;
648 SymbolVisitor() = default;
649 SymbolVisitor(const SymbolVisitor &) = default;
650 SymbolVisitor(SymbolVisitor &&) {}
652 /// A visitor method invoked by ProgramStateManager::scanReachableSymbols.
654 /// The method returns \c true if symbols should continue be scanned and \c
656 virtual bool VisitSymbol(SymbolRef sym) = 0;
657 virtual bool VisitMemRegion(const MemRegion *region) { return true; }
664 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H