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_GR_SYMMGR_H
16 #define LLVM_CLANG_GR_SYMMGR_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/StoreRef.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/DenseSet.h"
25 #include "llvm/ADT/FoldingSet.h"
26 #include "llvm/Support/DataTypes.h"
29 class BumpPtrAllocator;
34 class StackFrameContext;
37 class BasicValueFactory;
40 class TypedValueRegion;
43 /// \brief Symbolic value. These values used to capture symbolic execution of
45 class SymExpr : public llvm::FoldingSetNode {
46 virtual void anchor();
48 enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind,
50 BEGIN_SYMBOLS = RegionValueKind,
51 END_SYMBOLS = MetadataKind,
52 SymIntKind, IntSymKind, SymSymKind,
53 BEGIN_BINARYSYMEXPRS = SymIntKind,
54 END_BINARYSYMEXPRS = SymSymKind,
60 SymExpr(Kind k) : K(k) {}
65 Kind getKind() const { return K; }
67 virtual void dump() const;
69 virtual void dumpToStream(raw_ostream &os) const {}
71 virtual QualType getType() const = 0;
72 virtual void Profile(llvm::FoldingSetNodeID& profile) = 0;
74 /// \brief Iterator over symbols that the current symbol depends on.
76 /// For SymbolData, it's the symbol itself; for expressions, it's the
77 /// expression symbol and all the operands in it. Note, SymbolDerived is
78 /// treated as SymbolData - the iterator will NOT visit the parent region.
79 class symbol_iterator {
80 SmallVector<const SymExpr*, 5> itr;
84 symbol_iterator(const SymExpr *SE);
86 symbol_iterator &operator++();
87 const SymExpr* operator*();
89 bool operator==(const symbol_iterator &X) const;
90 bool operator!=(const symbol_iterator &X) const;
93 symbol_iterator symbol_begin() const {
94 return symbol_iterator(this);
96 static symbol_iterator symbol_end() { return symbol_iterator(); }
98 unsigned computeComplexity() const;
101 typedef const SymExpr* SymbolRef;
102 typedef SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy;
104 typedef unsigned SymbolID;
105 /// \brief A symbol representing data which can be stored in a memory location
107 class SymbolData : public SymExpr {
108 virtual void anchor();
112 SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {}
115 virtual ~SymbolData() {}
117 SymbolID getSymbolID() const { return Sym; }
119 // Implement isa<T> support.
120 static inline bool classof(const SymExpr *SE) {
121 Kind k = SE->getKind();
122 return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
126 ///\brief A symbol representing the value stored at a MemRegion.
127 class SymbolRegionValue : public SymbolData {
128 const TypedValueRegion *R;
131 SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
132 : SymbolData(RegionValueKind, sym), R(r) {}
134 const TypedValueRegion* getRegion() const { return R; }
136 static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
137 profile.AddInteger((unsigned) RegionValueKind);
138 profile.AddPointer(R);
141 virtual void Profile(llvm::FoldingSetNodeID& profile) {
145 virtual void dumpToStream(raw_ostream &os) const;
147 QualType getType() const;
149 // Implement isa<T> support.
150 static inline bool classof(const SymExpr *SE) {
151 return SE->getKind() == RegionValueKind;
155 /// A symbol representing the result of an expression in the case when we do
156 /// not know anything about what the expression is.
157 class SymbolConjured : public SymbolData {
161 const LocationContext *LCtx;
162 const void *SymbolTag;
165 SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx,
166 QualType t, unsigned count,
167 const void *symbolTag)
168 : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count),
170 SymbolTag(symbolTag) {}
172 const Stmt *getStmt() const { return S; }
173 unsigned getCount() const { return Count; }
174 const void *getTag() const { return SymbolTag; }
176 QualType getType() const;
178 virtual void dumpToStream(raw_ostream &os) const;
180 static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
181 QualType T, unsigned Count, const LocationContext *LCtx,
182 const void *SymbolTag) {
183 profile.AddInteger((unsigned) ConjuredKind);
184 profile.AddPointer(S);
185 profile.AddPointer(LCtx);
187 profile.AddInteger(Count);
188 profile.AddPointer(SymbolTag);
191 virtual void Profile(llvm::FoldingSetNodeID& profile) {
192 Profile(profile, S, T, Count, LCtx, SymbolTag);
195 // Implement isa<T> support.
196 static inline bool classof(const SymExpr *SE) {
197 return SE->getKind() == ConjuredKind;
201 /// A symbol representing the value of a MemRegion whose parent region has
203 class SymbolDerived : public SymbolData {
204 SymbolRef parentSymbol;
205 const TypedValueRegion *R;
208 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
209 : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {}
211 SymbolRef getParentSymbol() const { return parentSymbol; }
212 const TypedValueRegion *getRegion() const { return R; }
214 QualType getType() const;
216 virtual void dumpToStream(raw_ostream &os) const;
218 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
219 const TypedValueRegion *r) {
220 profile.AddInteger((unsigned) DerivedKind);
221 profile.AddPointer(r);
222 profile.AddPointer(parent);
225 virtual void Profile(llvm::FoldingSetNodeID& profile) {
226 Profile(profile, parentSymbol, R);
229 // Implement isa<T> support.
230 static inline bool classof(const SymExpr *SE) {
231 return SE->getKind() == DerivedKind;
235 /// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
236 /// Clients should not ask the SymbolManager for a region's extent. Always use
237 /// SubRegion::getExtent instead -- the value returned may not be a symbol.
238 class SymbolExtent : public SymbolData {
242 SymbolExtent(SymbolID sym, const SubRegion *r)
243 : SymbolData(ExtentKind, sym), R(r) {}
245 const SubRegion *getRegion() const { return R; }
247 QualType getType() const;
249 virtual void dumpToStream(raw_ostream &os) const;
251 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
252 profile.AddInteger((unsigned) ExtentKind);
253 profile.AddPointer(R);
256 virtual void Profile(llvm::FoldingSetNodeID& profile) {
260 // Implement isa<T> support.
261 static inline bool classof(const SymExpr *SE) {
262 return SE->getKind() == ExtentKind;
266 /// SymbolMetadata - Represents path-dependent metadata about a specific region.
267 /// Metadata symbols remain live as long as they are marked as in use before
268 /// dead-symbol sweeping AND their associated regions are still alive.
269 /// Intended for use by checkers.
270 class SymbolMetadata : public SymbolData {
277 SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t,
278 unsigned count, const void *tag)
279 : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {}
281 const MemRegion *getRegion() const { return R; }
282 const Stmt *getStmt() const { return S; }
283 unsigned getCount() const { return Count; }
284 const void *getTag() const { return Tag; }
286 QualType getType() const;
288 virtual void dumpToStream(raw_ostream &os) const;
290 static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
291 const Stmt *S, QualType T, unsigned Count,
293 profile.AddInteger((unsigned) MetadataKind);
294 profile.AddPointer(R);
295 profile.AddPointer(S);
297 profile.AddInteger(Count);
298 profile.AddPointer(Tag);
301 virtual void Profile(llvm::FoldingSetNodeID& profile) {
302 Profile(profile, R, S, T, Count, Tag);
305 // Implement isa<T> support.
306 static inline bool classof(const SymExpr *SE) {
307 return SE->getKind() == MetadataKind;
311 /// \brief Represents a cast expression.
312 class SymbolCast : public SymExpr {
313 const SymExpr *Operand;
314 /// Type of the operand.
316 /// The type of the result.
320 SymbolCast(const SymExpr *In, QualType From, QualType To) :
321 SymExpr(CastSymbolKind), Operand(In), FromTy(From), ToTy(To) { }
323 QualType getType() const { return ToTy; }
325 const SymExpr *getOperand() const { return Operand; }
327 virtual void dumpToStream(raw_ostream &os) const;
329 static void Profile(llvm::FoldingSetNodeID& ID,
330 const SymExpr *In, QualType From, QualType To) {
331 ID.AddInteger((unsigned) CastSymbolKind);
337 void Profile(llvm::FoldingSetNodeID& ID) {
338 Profile(ID, Operand, FromTy, ToTy);
341 // Implement isa<T> support.
342 static inline bool classof(const SymExpr *SE) {
343 return SE->getKind() == CastSymbolKind;
347 /// \brief Represents a symbolic expression involving a binary operator
348 class BinarySymExpr : public SymExpr {
349 BinaryOperator::Opcode Op;
353 BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
354 : SymExpr(k), Op(op), T(t) {}
357 // FIXME: We probably need to make this out-of-line to avoid redundant
358 // generation of virtual functions.
359 QualType getType() const { return T; }
361 BinaryOperator::Opcode getOpcode() const { return Op; }
363 // Implement isa<T> support.
364 static inline bool classof(const SymExpr *SE) {
365 Kind k = SE->getKind();
366 return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
370 /// \brief Represents a symbolic expression like 'x' + 3.
371 class SymIntExpr : public BinarySymExpr {
373 const llvm::APSInt& RHS;
376 SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
377 const llvm::APSInt& rhs, QualType t)
378 : BinarySymExpr(SymIntKind, op, t), LHS(lhs), RHS(rhs) {}
380 virtual void dumpToStream(raw_ostream &os) const;
382 const SymExpr *getLHS() const { return LHS; }
383 const llvm::APSInt &getRHS() const { return RHS; }
385 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
386 BinaryOperator::Opcode op, const llvm::APSInt& rhs,
388 ID.AddInteger((unsigned) SymIntKind);
395 void Profile(llvm::FoldingSetNodeID& ID) {
396 Profile(ID, LHS, getOpcode(), RHS, getType());
399 // Implement isa<T> support.
400 static inline bool classof(const SymExpr *SE) {
401 return SE->getKind() == SymIntKind;
405 /// \brief Represents a symbolic expression like 3 - 'x'.
406 class IntSymExpr : public BinarySymExpr {
407 const llvm::APSInt& LHS;
411 IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op,
412 const SymExpr *rhs, QualType t)
413 : BinarySymExpr(IntSymKind, op, t), LHS(lhs), RHS(rhs) {}
415 virtual void dumpToStream(raw_ostream &os) const;
417 const SymExpr *getRHS() const { return RHS; }
418 const llvm::APSInt &getLHS() const { return LHS; }
420 static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
421 BinaryOperator::Opcode op, const SymExpr *rhs,
423 ID.AddInteger((unsigned) IntSymKind);
430 void Profile(llvm::FoldingSetNodeID& ID) {
431 Profile(ID, LHS, getOpcode(), RHS, getType());
434 // Implement isa<T> support.
435 static inline bool classof(const SymExpr *SE) {
436 return SE->getKind() == IntSymKind;
440 /// \brief Represents a symbolic expression like 'x' + 'y'.
441 class SymSymExpr : public BinarySymExpr {
446 SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
448 : BinarySymExpr(SymSymKind, op, t), LHS(lhs), RHS(rhs) {}
450 const SymExpr *getLHS() const { return LHS; }
451 const SymExpr *getRHS() const { return RHS; }
453 virtual void dumpToStream(raw_ostream &os) const;
455 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
456 BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
457 ID.AddInteger((unsigned) SymSymKind);
464 void Profile(llvm::FoldingSetNodeID& ID) {
465 Profile(ID, LHS, getOpcode(), RHS, getType());
468 // Implement isa<T> support.
469 static inline bool classof(const SymExpr *SE) {
470 return SE->getKind() == SymSymKind;
474 class SymbolManager {
475 typedef llvm::FoldingSet<SymExpr> DataSetTy;
476 typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy;
479 /// Stores the extra dependencies between symbols: the data should be kept
480 /// alive as long as the key is live.
481 SymbolDependTy SymbolDependencies;
482 unsigned SymbolCounter;
483 llvm::BumpPtrAllocator& BPAlloc;
484 BasicValueFactory &BV;
488 SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
489 llvm::BumpPtrAllocator& bpalloc)
490 : SymbolDependencies(16), SymbolCounter(0),
491 BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
495 static bool canSymbolicate(QualType T);
497 /// \brief Make a unique symbol for MemRegion R according to its kind.
498 const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
500 const SymbolConjured* conjureSymbol(const Stmt *E,
501 const LocationContext *LCtx,
504 const void *SymbolTag = 0);
506 const SymbolConjured* conjureSymbol(const Expr *E,
507 const LocationContext *LCtx,
509 const void *SymbolTag = 0) {
510 return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
513 const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
514 const TypedValueRegion *R);
516 const SymbolExtent *getExtentSymbol(const SubRegion *R);
518 /// \brief Creates a metadata symbol associated with a specific region.
520 /// VisitCount can be used to differentiate regions corresponding to
521 /// different loop iterations, thus, making the symbol path-dependent.
522 const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt *S,
523 QualType T, unsigned VisitCount,
524 const void *SymbolTag = 0);
526 const SymbolCast* getCastSymbol(const SymExpr *Operand,
527 QualType From, QualType To);
529 const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
530 const llvm::APSInt& rhs, QualType t);
532 const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
533 const llvm::APSInt& rhs, QualType t) {
534 return getSymIntExpr(&lhs, op, rhs, t);
537 const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
538 BinaryOperator::Opcode op,
539 const SymExpr *rhs, QualType t);
541 const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
542 const SymExpr *rhs, QualType t);
544 QualType getType(const SymExpr *SE) const {
545 return SE->getType();
548 /// \brief Add artificial symbol dependency.
550 /// The dependent symbol should stay alive as long as the primary is alive.
551 void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
553 const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
555 ASTContext &getContext() { return Ctx; }
556 BasicValueFactory &getBasicVals() { return BV; }
559 /// \brief A class responsible for cleaning up unused symbols.
566 typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
567 typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy;
568 typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
570 SymbolMapTy TheLiving;
571 SymbolSetTy MetadataInUse;
574 RegionSetTy RegionRoots;
576 const StackFrameContext *LCtx;
578 SymbolManager& SymMgr;
579 StoreRef reapedStore;
580 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
583 /// \brief Construct a reaper object, which removes everything which is not
584 /// live before we execute statement s in the given location context.
586 /// If the statement is NULL, everything is this and parent contexts is
588 /// If the stack frame context is NULL, everything on stack is considered
590 SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr,
591 StoreManager &storeMgr)
592 : LCtx(Ctx), Loc(s), SymMgr(symmgr),
593 reapedStore(0, storeMgr) {}
597 const LocationContext *getLocationContext() const { return LCtx; }
599 bool isLive(SymbolRef sym);
600 bool isLiveRegion(const MemRegion *region);
601 bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
602 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
604 /// \brief Unconditionally marks a symbol as live.
606 /// This should never be
607 /// used by checkers, only by the state infrastructure such as the store and
608 /// environment. Checkers should instead use metadata symbols and markInUse.
609 void markLive(SymbolRef sym);
611 /// \brief Marks a symbol as important to a checker.
613 /// For metadata symbols,
614 /// this will keep the symbol alive as long as its associated region is also
615 /// live. For other symbols, this has no effect; checkers are not permitted
616 /// to influence the life of other symbols. This should be used before any
617 /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
618 void markInUse(SymbolRef sym);
620 /// \brief If a symbol is known to be live, marks the symbol as live.
622 /// Otherwise, if the symbol cannot be proven live, it is marked as dead.
623 /// Returns true if the symbol is dead, false if live.
624 bool maybeDead(SymbolRef sym);
626 typedef SymbolSetTy::const_iterator dead_iterator;
627 dead_iterator dead_begin() const { return TheDead.begin(); }
628 dead_iterator dead_end() const { return TheDead.end(); }
630 bool hasDeadSymbols() const {
631 return !TheDead.empty();
634 typedef RegionSetTy::const_iterator region_iterator;
635 region_iterator region_begin() const { return RegionRoots.begin(); }
636 region_iterator region_end() const { return RegionRoots.end(); }
638 /// \brief Returns whether or not a symbol has been confirmed dead.
640 /// This should only be called once all marking of dead symbols has completed.
641 /// (For checkers, this means only in the evalDeadSymbols callback.)
642 bool isDead(SymbolRef sym) const {
643 return TheDead.count(sym);
646 void markLive(const MemRegion *region);
648 /// \brief Set to the value of the symbolic store after
649 /// StoreManager::removeDeadBindings has been called.
650 void setReapedStore(StoreRef st) { reapedStore = st; }
653 /// Mark the symbols dependent on the input symbol as live.
654 void markDependentsLive(SymbolRef sym);
657 class SymbolVisitor {
659 /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols.
661 /// The method returns \c true if symbols should continue be scanned and \c
663 virtual bool VisitSymbol(SymbolRef sym) = 0;
664 virtual bool VisitMemRegion(const MemRegion *region) { return true; }
665 virtual ~SymbolVisitor();
668 } // end GR namespace
670 } // end clang namespace
673 static inline raw_ostream &operator<<(raw_ostream &os,
674 const clang::ento::SymExpr *SE) {
675 SE->dumpToStream(os);
678 } // end llvm namespace