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/StoreRef.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/DenseSet.h"
25 #include "llvm/ADT/FoldingSet.h"
26 #include "llvm/Support/Allocator.h"
27 #include "llvm/Support/DataTypes.h"
31 class StackFrameContext;
34 class BasicValueFactory;
37 class TypedValueRegion;
40 /// \brief Symbolic value. These values used to capture symbolic execution of
42 class SymExpr : public llvm::FoldingSetNode {
43 virtual void anchor();
45 enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind,
47 BEGIN_SYMBOLS = RegionValueKind,
48 END_SYMBOLS = MetadataKind,
49 SymIntKind, IntSymKind, SymSymKind,
50 BEGIN_BINARYSYMEXPRS = SymIntKind,
51 END_BINARYSYMEXPRS = SymSymKind,
57 SymExpr(Kind k) : K(k) {}
62 Kind getKind() const { return K; }
64 virtual void dump() const;
66 virtual void dumpToStream(raw_ostream &os) const {}
68 virtual QualType getType() const = 0;
69 virtual void Profile(llvm::FoldingSetNodeID& profile) = 0;
71 /// \brief Iterator over symbols that the current symbol depends on.
73 /// For SymbolData, it's the symbol itself; for expressions, it's the
74 /// expression symbol and all the operands in it. Note, SymbolDerived is
75 /// treated as SymbolData - the iterator will NOT visit the parent region.
76 class symbol_iterator {
77 SmallVector<const SymExpr*, 5> itr;
81 symbol_iterator(const SymExpr *SE);
83 symbol_iterator &operator++();
84 const SymExpr* operator*();
86 bool operator==(const symbol_iterator &X) const;
87 bool operator!=(const symbol_iterator &X) const;
90 symbol_iterator symbol_begin() const {
91 return symbol_iterator(this);
93 static symbol_iterator symbol_end() { return symbol_iterator(); }
95 unsigned computeComplexity() const;
98 typedef const SymExpr* SymbolRef;
99 typedef SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy;
101 typedef unsigned SymbolID;
102 /// \brief A symbol representing data which can be stored in a memory location
104 class SymbolData : public SymExpr {
105 void anchor() override;
109 SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {}
112 virtual ~SymbolData() {}
114 SymbolID getSymbolID() const { return Sym; }
116 // Implement isa<T> support.
117 static inline bool classof(const SymExpr *SE) {
118 Kind k = SE->getKind();
119 return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
123 ///\brief A symbol representing the value stored at a MemRegion.
124 class SymbolRegionValue : public SymbolData {
125 const TypedValueRegion *R;
128 SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
129 : SymbolData(RegionValueKind, sym), R(r) {}
131 const TypedValueRegion* getRegion() const { return R; }
133 static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
134 profile.AddInteger((unsigned) RegionValueKind);
135 profile.AddPointer(R);
138 void Profile(llvm::FoldingSetNodeID& profile) override {
142 void dumpToStream(raw_ostream &os) const override;
144 QualType getType() const override;
146 // Implement isa<T> support.
147 static inline bool classof(const SymExpr *SE) {
148 return SE->getKind() == RegionValueKind;
152 /// A symbol representing the result of an expression in the case when we do
153 /// not know anything about what the expression is.
154 class SymbolConjured : public SymbolData {
158 const LocationContext *LCtx;
159 const void *SymbolTag;
162 SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx,
163 QualType t, unsigned count,
164 const void *symbolTag)
165 : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count),
167 SymbolTag(symbolTag) {}
169 const Stmt *getStmt() const { return S; }
170 unsigned getCount() const { return Count; }
171 const void *getTag() const { return SymbolTag; }
173 QualType getType() const override;
175 void dumpToStream(raw_ostream &os) const override;
177 static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
178 QualType T, unsigned Count, const LocationContext *LCtx,
179 const void *SymbolTag) {
180 profile.AddInteger((unsigned) ConjuredKind);
181 profile.AddPointer(S);
182 profile.AddPointer(LCtx);
184 profile.AddInteger(Count);
185 profile.AddPointer(SymbolTag);
188 void Profile(llvm::FoldingSetNodeID& profile) override {
189 Profile(profile, S, T, Count, LCtx, SymbolTag);
192 // Implement isa<T> support.
193 static inline bool classof(const SymExpr *SE) {
194 return SE->getKind() == ConjuredKind;
198 /// A symbol representing the value of a MemRegion whose parent region has
200 class SymbolDerived : public SymbolData {
201 SymbolRef parentSymbol;
202 const TypedValueRegion *R;
205 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
206 : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {}
208 SymbolRef getParentSymbol() const { return parentSymbol; }
209 const TypedValueRegion *getRegion() const { return R; }
211 QualType getType() const override;
213 void dumpToStream(raw_ostream &os) const override;
215 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
216 const TypedValueRegion *r) {
217 profile.AddInteger((unsigned) DerivedKind);
218 profile.AddPointer(r);
219 profile.AddPointer(parent);
222 void Profile(llvm::FoldingSetNodeID& profile) override {
223 Profile(profile, parentSymbol, R);
226 // Implement isa<T> support.
227 static inline bool classof(const SymExpr *SE) {
228 return SE->getKind() == DerivedKind;
232 /// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
233 /// Clients should not ask the SymbolManager for a region's extent. Always use
234 /// SubRegion::getExtent instead -- the value returned may not be a symbol.
235 class SymbolExtent : public SymbolData {
239 SymbolExtent(SymbolID sym, const SubRegion *r)
240 : SymbolData(ExtentKind, sym), R(r) {}
242 const SubRegion *getRegion() const { return R; }
244 QualType getType() const override;
246 void dumpToStream(raw_ostream &os) const override;
248 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
249 profile.AddInteger((unsigned) ExtentKind);
250 profile.AddPointer(R);
253 void Profile(llvm::FoldingSetNodeID& profile) override {
257 // Implement isa<T> support.
258 static inline bool classof(const SymExpr *SE) {
259 return SE->getKind() == ExtentKind;
263 /// SymbolMetadata - Represents path-dependent metadata about a specific region.
264 /// Metadata symbols remain live as long as they are marked as in use before
265 /// dead-symbol sweeping AND their associated regions are still alive.
266 /// Intended for use by checkers.
267 class SymbolMetadata : public SymbolData {
274 SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t,
275 unsigned count, const void *tag)
276 : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {}
278 const MemRegion *getRegion() const { return R; }
279 const Stmt *getStmt() const { return S; }
280 unsigned getCount() const { return Count; }
281 const void *getTag() const { return Tag; }
283 QualType getType() const override;
285 void dumpToStream(raw_ostream &os) const override;
287 static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
288 const Stmt *S, QualType T, unsigned Count,
290 profile.AddInteger((unsigned) MetadataKind);
291 profile.AddPointer(R);
292 profile.AddPointer(S);
294 profile.AddInteger(Count);
295 profile.AddPointer(Tag);
298 void Profile(llvm::FoldingSetNodeID& profile) override {
299 Profile(profile, R, S, T, Count, Tag);
302 // Implement isa<T> support.
303 static inline bool classof(const SymExpr *SE) {
304 return SE->getKind() == MetadataKind;
308 /// \brief Represents a cast expression.
309 class SymbolCast : public SymExpr {
310 const SymExpr *Operand;
311 /// Type of the operand.
313 /// The type of the result.
317 SymbolCast(const SymExpr *In, QualType From, QualType To) :
318 SymExpr(CastSymbolKind), Operand(In), FromTy(From), ToTy(To) { }
320 QualType getType() const override { return ToTy; }
322 const SymExpr *getOperand() const { return Operand; }
324 void dumpToStream(raw_ostream &os) const override;
326 static void Profile(llvm::FoldingSetNodeID& ID,
327 const SymExpr *In, QualType From, QualType To) {
328 ID.AddInteger((unsigned) CastSymbolKind);
334 void Profile(llvm::FoldingSetNodeID& ID) override {
335 Profile(ID, Operand, FromTy, ToTy);
338 // Implement isa<T> support.
339 static inline bool classof(const SymExpr *SE) {
340 return SE->getKind() == CastSymbolKind;
344 /// \brief Represents a symbolic expression involving a binary operator
345 class BinarySymExpr : public SymExpr {
346 BinaryOperator::Opcode Op;
350 BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
351 : SymExpr(k), Op(op), T(t) {}
354 // FIXME: We probably need to make this out-of-line to avoid redundant
355 // generation of virtual functions.
356 QualType getType() const override { return T; }
358 BinaryOperator::Opcode getOpcode() const { return Op; }
360 // Implement isa<T> support.
361 static inline bool classof(const SymExpr *SE) {
362 Kind k = SE->getKind();
363 return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
367 /// \brief Represents a symbolic expression like 'x' + 3.
368 class SymIntExpr : public BinarySymExpr {
370 const llvm::APSInt& RHS;
373 SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
374 const llvm::APSInt& rhs, QualType t)
375 : BinarySymExpr(SymIntKind, op, t), LHS(lhs), RHS(rhs) {}
377 void dumpToStream(raw_ostream &os) const override;
379 const SymExpr *getLHS() const { return LHS; }
380 const llvm::APSInt &getRHS() const { return RHS; }
382 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
383 BinaryOperator::Opcode op, const llvm::APSInt& rhs,
385 ID.AddInteger((unsigned) SymIntKind);
392 void Profile(llvm::FoldingSetNodeID& ID) override {
393 Profile(ID, LHS, getOpcode(), RHS, getType());
396 // Implement isa<T> support.
397 static inline bool classof(const SymExpr *SE) {
398 return SE->getKind() == SymIntKind;
402 /// \brief Represents a symbolic expression like 3 - 'x'.
403 class IntSymExpr : public BinarySymExpr {
404 const llvm::APSInt& LHS;
408 IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op,
409 const SymExpr *rhs, QualType t)
410 : BinarySymExpr(IntSymKind, op, t), LHS(lhs), RHS(rhs) {}
412 void dumpToStream(raw_ostream &os) const override;
414 const SymExpr *getRHS() const { return RHS; }
415 const llvm::APSInt &getLHS() const { return LHS; }
417 static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
418 BinaryOperator::Opcode op, const SymExpr *rhs,
420 ID.AddInteger((unsigned) IntSymKind);
427 void Profile(llvm::FoldingSetNodeID& ID) override {
428 Profile(ID, LHS, getOpcode(), RHS, getType());
431 // Implement isa<T> support.
432 static inline bool classof(const SymExpr *SE) {
433 return SE->getKind() == IntSymKind;
437 /// \brief Represents a symbolic expression like 'x' + 'y'.
438 class SymSymExpr : public BinarySymExpr {
443 SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
445 : BinarySymExpr(SymSymKind, op, t), LHS(lhs), RHS(rhs) {}
447 const SymExpr *getLHS() const { return LHS; }
448 const SymExpr *getRHS() const { return RHS; }
450 void dumpToStream(raw_ostream &os) const override;
452 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
453 BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
454 ID.AddInteger((unsigned) SymSymKind);
461 void Profile(llvm::FoldingSetNodeID& ID) override {
462 Profile(ID, LHS, getOpcode(), RHS, getType());
465 // Implement isa<T> support.
466 static inline bool classof(const SymExpr *SE) {
467 return SE->getKind() == SymSymKind;
471 class SymbolManager {
472 typedef llvm::FoldingSet<SymExpr> DataSetTy;
473 typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy;
476 /// Stores the extra dependencies between symbols: the data should be kept
477 /// alive as long as the key is live.
478 SymbolDependTy SymbolDependencies;
479 unsigned SymbolCounter;
480 llvm::BumpPtrAllocator& BPAlloc;
481 BasicValueFactory &BV;
485 SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
486 llvm::BumpPtrAllocator& bpalloc)
487 : SymbolDependencies(16), SymbolCounter(0),
488 BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
492 static bool canSymbolicate(QualType T);
494 /// \brief Make a unique symbol for MemRegion R according to its kind.
495 const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
497 const SymbolConjured* conjureSymbol(const Stmt *E,
498 const LocationContext *LCtx,
501 const void *SymbolTag = nullptr);
503 const SymbolConjured* conjureSymbol(const Expr *E,
504 const LocationContext *LCtx,
506 const void *SymbolTag = nullptr) {
507 return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
510 const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
511 const TypedValueRegion *R);
513 const SymbolExtent *getExtentSymbol(const SubRegion *R);
515 /// \brief Creates a metadata symbol associated with a specific region.
517 /// VisitCount can be used to differentiate regions corresponding to
518 /// different loop iterations, thus, making the symbol path-dependent.
519 const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S,
520 QualType T, unsigned VisitCount,
521 const void *SymbolTag = nullptr);
523 const SymbolCast* getCastSymbol(const SymExpr *Operand,
524 QualType From, QualType To);
526 const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
527 const llvm::APSInt& rhs, QualType t);
529 const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
530 const llvm::APSInt& rhs, QualType t) {
531 return getSymIntExpr(&lhs, op, rhs, t);
534 const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
535 BinaryOperator::Opcode op,
536 const SymExpr *rhs, QualType t);
538 const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
539 const SymExpr *rhs, QualType t);
541 QualType getType(const SymExpr *SE) const {
542 return SE->getType();
545 /// \brief Add artificial symbol dependency.
547 /// The dependent symbol should stay alive as long as the primary is alive.
548 void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
550 const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
552 ASTContext &getContext() { return Ctx; }
553 BasicValueFactory &getBasicVals() { return BV; }
556 /// \brief A class responsible for cleaning up unused symbols.
563 typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
564 typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy;
565 typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
567 SymbolMapTy TheLiving;
568 SymbolSetTy MetadataInUse;
571 RegionSetTy RegionRoots;
573 const StackFrameContext *LCtx;
575 SymbolManager& SymMgr;
576 StoreRef reapedStore;
577 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
580 /// \brief Construct a reaper object, which removes everything which is not
581 /// live before we execute statement s in the given location context.
583 /// If the statement is NULL, everything is this and parent contexts is
585 /// If the stack frame context is NULL, everything on stack is considered
587 SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr,
588 StoreManager &storeMgr)
589 : LCtx(Ctx), Loc(s), SymMgr(symmgr),
590 reapedStore(nullptr, storeMgr) {}
594 const LocationContext *getLocationContext() const { return LCtx; }
596 bool isLive(SymbolRef sym);
597 bool isLiveRegion(const MemRegion *region);
598 bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
599 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
601 /// \brief Unconditionally marks a symbol as live.
603 /// This should never be
604 /// used by checkers, only by the state infrastructure such as the store and
605 /// environment. Checkers should instead use metadata symbols and markInUse.
606 void markLive(SymbolRef sym);
608 /// \brief Marks a symbol as important to a checker.
610 /// For metadata symbols,
611 /// this will keep the symbol alive as long as its associated region is also
612 /// live. For other symbols, this has no effect; checkers are not permitted
613 /// to influence the life of other symbols. This should be used before any
614 /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
615 void markInUse(SymbolRef sym);
617 /// \brief If a symbol is known to be live, marks the symbol as live.
619 /// Otherwise, if the symbol cannot be proven live, it is marked as dead.
620 /// Returns true if the symbol is dead, false if live.
621 bool maybeDead(SymbolRef sym);
623 typedef SymbolSetTy::const_iterator dead_iterator;
624 dead_iterator dead_begin() const { return TheDead.begin(); }
625 dead_iterator dead_end() const { return TheDead.end(); }
627 bool hasDeadSymbols() const {
628 return !TheDead.empty();
631 typedef RegionSetTy::const_iterator region_iterator;
632 region_iterator region_begin() const { return RegionRoots.begin(); }
633 region_iterator region_end() const { return RegionRoots.end(); }
635 /// \brief Returns whether or not a symbol has been confirmed dead.
637 /// This should only be called once all marking of dead symbols has completed.
638 /// (For checkers, this means only in the evalDeadSymbols callback.)
639 bool isDead(SymbolRef sym) const {
640 return TheDead.count(sym);
643 void markLive(const MemRegion *region);
645 /// \brief Set to the value of the symbolic store after
646 /// StoreManager::removeDeadBindings has been called.
647 void setReapedStore(StoreRef st) { reapedStore = st; }
650 /// Mark the symbols dependent on the input symbol as live.
651 void markDependentsLive(SymbolRef sym);
654 class SymbolVisitor {
656 /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols.
658 /// The method returns \c true if symbols should continue be scanned and \c
660 virtual bool VisitSymbol(SymbolRef sym) = 0;
661 virtual bool VisitMemRegion(const MemRegion *region) { return true; }
662 virtual ~SymbolVisitor();
665 } // end GR namespace
667 } // end clang namespace
670 static inline raw_ostream &operator<<(raw_ostream &os,
671 const clang::ento::SymExpr *SE) {
672 SE->dumpToStream(os);
675 } // end llvm namespace