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/Decl.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/Analysis/AnalysisContext.h"
21 #include "clang/Basic/LLVM.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
25 #include "llvm/ADT/DenseMap.h"
26 #include "llvm/ADT/DenseSet.h"
27 #include "llvm/ADT/FoldingSet.h"
28 #include "llvm/Support/Allocator.h"
29 #include "llvm/Support/DataTypes.h"
33 class StackFrameContext;
36 class BasicValueFactory;
38 class TypedValueRegion;
41 ///\brief 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 const TypedValueRegion* getRegion() const { return R; }
51 static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
52 profile.AddInteger((unsigned) SymbolRegionValueKind);
53 profile.AddPointer(R);
56 void Profile(llvm::FoldingSetNodeID& profile) override {
60 void dumpToStream(raw_ostream &os) const override;
61 const MemRegion *getOriginRegion() const override { return getRegion(); }
63 QualType getType() const override;
65 // Implement isa<T> support.
66 static inline bool classof(const SymExpr *SE) {
67 return SE->getKind() == SymbolRegionValueKind;
71 /// A symbol representing the result of an expression in the case when we do
72 /// not know anything about what the expression is.
73 class SymbolConjured : public SymbolData {
77 const LocationContext *LCtx;
78 const void *SymbolTag;
81 SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx,
82 QualType t, unsigned count, const void *symbolTag)
83 : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count),
84 LCtx(lctx), SymbolTag(symbolTag) {}
86 const Stmt *getStmt() const { return S; }
87 unsigned getCount() const { return Count; }
88 const void *getTag() const { return SymbolTag; }
90 QualType getType() const override;
92 void dumpToStream(raw_ostream &os) const override;
94 static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
95 QualType T, unsigned Count, const LocationContext *LCtx,
96 const void *SymbolTag) {
97 profile.AddInteger((unsigned) SymbolConjuredKind);
98 profile.AddPointer(S);
99 profile.AddPointer(LCtx);
101 profile.AddInteger(Count);
102 profile.AddPointer(SymbolTag);
105 void Profile(llvm::FoldingSetNodeID& profile) override {
106 Profile(profile, S, T, Count, LCtx, SymbolTag);
109 // Implement isa<T> support.
110 static inline bool classof(const SymExpr *SE) {
111 return SE->getKind() == SymbolConjuredKind;
115 /// A symbol representing the value of a MemRegion whose parent region has
117 class SymbolDerived : public SymbolData {
118 SymbolRef parentSymbol;
119 const TypedValueRegion *R;
122 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
123 : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {}
125 SymbolRef getParentSymbol() const { return parentSymbol; }
126 const TypedValueRegion *getRegion() const { return R; }
128 QualType getType() const override;
130 void dumpToStream(raw_ostream &os) const override;
131 const MemRegion *getOriginRegion() const override { return getRegion(); }
133 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
134 const TypedValueRegion *r) {
135 profile.AddInteger((unsigned) SymbolDerivedKind);
136 profile.AddPointer(r);
137 profile.AddPointer(parent);
140 void Profile(llvm::FoldingSetNodeID& profile) override {
141 Profile(profile, parentSymbol, R);
144 // Implement isa<T> support.
145 static inline bool classof(const SymExpr *SE) {
146 return SE->getKind() == SymbolDerivedKind;
150 /// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
151 /// Clients should not ask the SymbolManager for a region's extent. Always use
152 /// SubRegion::getExtent instead -- the value returned may not be a symbol.
153 class SymbolExtent : public SymbolData {
157 SymbolExtent(SymbolID sym, const SubRegion *r)
158 : SymbolData(SymbolExtentKind, sym), R(r) {}
160 const SubRegion *getRegion() const { return R; }
162 QualType getType() const override;
164 void dumpToStream(raw_ostream &os) const override;
166 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
167 profile.AddInteger((unsigned) SymbolExtentKind);
168 profile.AddPointer(R);
171 void Profile(llvm::FoldingSetNodeID& profile) override {
175 // Implement isa<T> support.
176 static inline bool classof(const SymExpr *SE) {
177 return SE->getKind() == SymbolExtentKind;
181 /// SymbolMetadata - Represents path-dependent metadata about a specific region.
182 /// Metadata symbols remain live as long as they are marked as in use before
183 /// dead-symbol sweeping AND their associated regions are still alive.
184 /// Intended for use by checkers.
185 class SymbolMetadata : public SymbolData {
189 const LocationContext *LCtx;
193 SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t,
194 const LocationContext *LCtx, unsigned count, const void *tag)
195 : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), LCtx(LCtx),
196 Count(count), Tag(tag) {}
198 const MemRegion *getRegion() const { return R; }
199 const Stmt *getStmt() const { return S; }
200 const LocationContext *getLocationContext() const { return LCtx; }
201 unsigned getCount() const { return Count; }
202 const void *getTag() const { return Tag; }
204 QualType getType() const override;
206 void dumpToStream(raw_ostream &os) const override;
208 static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
209 const Stmt *S, QualType T, const LocationContext *LCtx,
210 unsigned Count, const void *Tag) {
211 profile.AddInteger((unsigned) SymbolMetadataKind);
212 profile.AddPointer(R);
213 profile.AddPointer(S);
215 profile.AddPointer(LCtx);
216 profile.AddInteger(Count);
217 profile.AddPointer(Tag);
220 void Profile(llvm::FoldingSetNodeID& profile) override {
221 Profile(profile, R, S, T, LCtx, Count, Tag);
224 // Implement isa<T> support.
225 static inline bool classof(const SymExpr *SE) {
226 return SE->getKind() == SymbolMetadataKind;
230 /// \brief Represents a cast expression.
231 class SymbolCast : public SymExpr {
232 const SymExpr *Operand;
233 /// Type of the operand.
235 /// The type of the result.
239 SymbolCast(const SymExpr *In, QualType From, QualType To) :
240 SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) { }
242 QualType getType() const override { return ToTy; }
244 const SymExpr *getOperand() const { return Operand; }
246 void dumpToStream(raw_ostream &os) const override;
248 static void Profile(llvm::FoldingSetNodeID& ID,
249 const SymExpr *In, QualType From, QualType To) {
250 ID.AddInteger((unsigned) SymbolCastKind);
256 void Profile(llvm::FoldingSetNodeID& ID) override {
257 Profile(ID, Operand, FromTy, ToTy);
260 // Implement isa<T> support.
261 static inline bool classof(const SymExpr *SE) {
262 return SE->getKind() == SymbolCastKind;
266 /// \brief Represents a symbolic expression involving a binary operator
267 class BinarySymExpr : public SymExpr {
268 BinaryOperator::Opcode Op;
272 BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
273 : SymExpr(k), Op(op), T(t) {}
276 // FIXME: We probably need to make this out-of-line to avoid redundant
277 // generation of virtual functions.
278 QualType getType() const override { return T; }
280 BinaryOperator::Opcode getOpcode() const { return Op; }
282 // Implement isa<T> support.
283 static inline bool classof(const SymExpr *SE) {
284 Kind k = SE->getKind();
285 return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
289 /// \brief Represents a symbolic expression like 'x' + 3.
290 class SymIntExpr : public BinarySymExpr {
292 const llvm::APSInt& RHS;
295 SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
296 const llvm::APSInt& rhs, QualType t)
297 : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {}
299 void dumpToStream(raw_ostream &os) const override;
301 const SymExpr *getLHS() const { return LHS; }
302 const llvm::APSInt &getRHS() const { return RHS; }
304 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
305 BinaryOperator::Opcode op, const llvm::APSInt& rhs,
307 ID.AddInteger((unsigned) SymIntExprKind);
314 void Profile(llvm::FoldingSetNodeID& ID) override {
315 Profile(ID, LHS, getOpcode(), RHS, getType());
318 // Implement isa<T> support.
319 static inline bool classof(const SymExpr *SE) {
320 return SE->getKind() == SymIntExprKind;
324 /// \brief Represents a symbolic expression like 3 - 'x'.
325 class IntSymExpr : public BinarySymExpr {
326 const llvm::APSInt& LHS;
330 IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op,
331 const SymExpr *rhs, QualType t)
332 : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {}
334 void dumpToStream(raw_ostream &os) const override;
336 const SymExpr *getRHS() const { return RHS; }
337 const llvm::APSInt &getLHS() const { return LHS; }
339 static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
340 BinaryOperator::Opcode op, const SymExpr *rhs,
342 ID.AddInteger((unsigned) IntSymExprKind);
349 void Profile(llvm::FoldingSetNodeID& ID) override {
350 Profile(ID, LHS, getOpcode(), RHS, getType());
353 // Implement isa<T> support.
354 static inline bool classof(const SymExpr *SE) {
355 return SE->getKind() == IntSymExprKind;
359 /// \brief Represents a symbolic expression like 'x' + 'y'.
360 class SymSymExpr : public BinarySymExpr {
365 SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
367 : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {}
369 const SymExpr *getLHS() const { return LHS; }
370 const SymExpr *getRHS() const { return RHS; }
372 void dumpToStream(raw_ostream &os) const override;
374 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
375 BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
376 ID.AddInteger((unsigned) SymSymExprKind);
383 void Profile(llvm::FoldingSetNodeID& ID) override {
384 Profile(ID, LHS, getOpcode(), RHS, getType());
387 // Implement isa<T> support.
388 static inline bool classof(const SymExpr *SE) {
389 return SE->getKind() == SymSymExprKind;
393 class SymbolManager {
394 typedef llvm::FoldingSet<SymExpr> DataSetTy;
395 typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy;
398 /// Stores the extra dependencies between symbols: the data should be kept
399 /// alive as long as the key is live.
400 SymbolDependTy SymbolDependencies;
401 unsigned SymbolCounter;
402 llvm::BumpPtrAllocator& BPAlloc;
403 BasicValueFactory &BV;
407 SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
408 llvm::BumpPtrAllocator& bpalloc)
409 : SymbolDependencies(16), SymbolCounter(0),
410 BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
414 static bool canSymbolicate(QualType T);
416 /// \brief Make a unique symbol for MemRegion R according to its kind.
417 const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
419 const SymbolConjured* conjureSymbol(const Stmt *E,
420 const LocationContext *LCtx,
423 const void *SymbolTag = nullptr);
425 const SymbolConjured* conjureSymbol(const Expr *E,
426 const LocationContext *LCtx,
428 const void *SymbolTag = nullptr) {
429 return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
432 const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
433 const TypedValueRegion *R);
435 const SymbolExtent *getExtentSymbol(const SubRegion *R);
437 /// \brief Creates a metadata symbol associated with a specific region.
439 /// VisitCount can be used to differentiate regions corresponding to
440 /// different loop iterations, thus, making the symbol path-dependent.
441 const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S,
443 const LocationContext *LCtx,
445 const void *SymbolTag = nullptr);
447 const SymbolCast* getCastSymbol(const SymExpr *Operand,
448 QualType From, QualType To);
450 const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
451 const llvm::APSInt& rhs, QualType t);
453 const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
454 const llvm::APSInt& rhs, QualType t) {
455 return getSymIntExpr(&lhs, op, rhs, t);
458 const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
459 BinaryOperator::Opcode op,
460 const SymExpr *rhs, QualType t);
462 const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
463 const SymExpr *rhs, QualType t);
465 QualType getType(const SymExpr *SE) const {
466 return SE->getType();
469 /// \brief Add artificial symbol dependency.
471 /// The dependent symbol should stay alive as long as the primary is alive.
472 void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
474 const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
476 ASTContext &getContext() { return Ctx; }
477 BasicValueFactory &getBasicVals() { return BV; }
480 /// \brief A class responsible for cleaning up unused symbols.
487 typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
488 typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy;
489 typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
491 SymbolMapTy TheLiving;
492 SymbolSetTy MetadataInUse;
495 RegionSetTy RegionRoots;
497 const StackFrameContext *LCtx;
499 SymbolManager& SymMgr;
500 StoreRef reapedStore;
501 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
504 /// \brief Construct a reaper object, which removes everything which is not
505 /// live before we execute statement s in the given location context.
507 /// If the statement is NULL, everything is this and parent contexts is
509 /// If the stack frame context is NULL, everything on stack is considered
511 SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr,
512 StoreManager &storeMgr)
513 : LCtx(Ctx), Loc(s), SymMgr(symmgr),
514 reapedStore(nullptr, storeMgr) {}
516 const LocationContext *getLocationContext() const { return LCtx; }
518 bool isLive(SymbolRef sym);
519 bool isLiveRegion(const MemRegion *region);
520 bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
521 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
523 /// \brief Unconditionally marks a symbol as live.
525 /// This should never be
526 /// used by checkers, only by the state infrastructure such as the store and
527 /// environment. Checkers should instead use metadata symbols and markInUse.
528 void markLive(SymbolRef sym);
530 /// \brief Marks a symbol as important to a checker.
532 /// For metadata symbols,
533 /// this will keep the symbol alive as long as its associated region is also
534 /// live. For other symbols, this has no effect; checkers are not permitted
535 /// to influence the life of other symbols. This should be used before any
536 /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
537 void markInUse(SymbolRef sym);
539 /// \brief If a symbol is known to be live, marks the symbol as live.
541 /// Otherwise, if the symbol cannot be proven live, it is marked as dead.
542 /// Returns true if the symbol is dead, false if live.
543 bool maybeDead(SymbolRef sym);
545 typedef SymbolSetTy::const_iterator dead_iterator;
546 dead_iterator dead_begin() const { return TheDead.begin(); }
547 dead_iterator dead_end() const { return TheDead.end(); }
549 bool hasDeadSymbols() const {
550 return !TheDead.empty();
553 typedef RegionSetTy::const_iterator region_iterator;
554 region_iterator region_begin() const { return RegionRoots.begin(); }
555 region_iterator region_end() const { return RegionRoots.end(); }
557 /// \brief Returns whether or not a symbol has been confirmed dead.
559 /// This should only be called once all marking of dead symbols has completed.
560 /// (For checkers, this means only in the evalDeadSymbols callback.)
561 bool isDead(SymbolRef sym) const {
562 return TheDead.count(sym);
565 void markLive(const MemRegion *region);
566 void markElementIndicesLive(const MemRegion *region);
568 /// \brief Set to the value of the symbolic store after
569 /// StoreManager::removeDeadBindings has been called.
570 void setReapedStore(StoreRef st) { reapedStore = st; }
573 /// Mark the symbols dependent on the input symbol as live.
574 void markDependentsLive(SymbolRef sym);
577 class SymbolVisitor {
579 ~SymbolVisitor() = default;
582 SymbolVisitor() = default;
583 SymbolVisitor(const SymbolVisitor &) = default;
584 SymbolVisitor(SymbolVisitor &&) {}
586 /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols.
588 /// The method returns \c true if symbols should continue be scanned and \c
590 virtual bool VisitSymbol(SymbolRef sym) = 0;
591 virtual bool VisitMemRegion(const MemRegion *region) { return true; }
594 } // end GR namespace
596 } // end clang namespace
599 static inline raw_ostream &operator<<(raw_ostream &os,
600 const clang::ento::SymExpr *SE) {
601 SE->dumpToStream(os);
604 } // end llvm namespace