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();
46 SymbolRegionValueKind,
51 BEGIN_SYMBOLS = SymbolRegionValueKind,
52 END_SYMBOLS = SymbolMetadataKind,
56 BEGIN_BINARYSYMEXPRS = SymIntExprKind,
57 END_BINARYSYMEXPRS = SymSymExprKind,
65 SymExpr(Kind k) : K(k) {}
70 Kind getKind() const { return K; }
72 virtual void dump() const;
74 virtual void dumpToStream(raw_ostream &os) const {}
76 virtual QualType getType() const = 0;
77 virtual void Profile(llvm::FoldingSetNodeID& profile) = 0;
79 /// \brief Iterator over symbols that the current symbol depends on.
81 /// For SymbolData, it's the symbol itself; for expressions, it's the
82 /// expression symbol and all the operands in it. Note, SymbolDerived is
83 /// treated as SymbolData - the iterator will NOT visit the parent region.
84 class symbol_iterator {
85 SmallVector<const SymExpr*, 5> itr;
89 symbol_iterator(const SymExpr *SE);
91 symbol_iterator &operator++();
92 const SymExpr* operator*();
94 bool operator==(const symbol_iterator &X) const;
95 bool operator!=(const symbol_iterator &X) const;
98 symbol_iterator symbol_begin() const {
99 return symbol_iterator(this);
101 static symbol_iterator symbol_end() { return symbol_iterator(); }
103 unsigned computeComplexity() const;
106 typedef const SymExpr* SymbolRef;
107 typedef SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy;
109 typedef unsigned SymbolID;
110 /// \brief A symbol representing data which can be stored in a memory location
112 class SymbolData : public SymExpr {
113 void anchor() override;
117 SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {}
120 ~SymbolData() override {}
122 SymbolID getSymbolID() const { return Sym; }
124 // Implement isa<T> support.
125 static inline bool classof(const SymExpr *SE) {
126 Kind k = SE->getKind();
127 return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
131 ///\brief A symbol representing the value stored at a MemRegion.
132 class SymbolRegionValue : public SymbolData {
133 const TypedValueRegion *R;
136 SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
137 : SymbolData(SymbolRegionValueKind, sym), R(r) {}
139 const TypedValueRegion* getRegion() const { return R; }
141 static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
142 profile.AddInteger((unsigned) SymbolRegionValueKind);
143 profile.AddPointer(R);
146 void Profile(llvm::FoldingSetNodeID& profile) override {
150 void dumpToStream(raw_ostream &os) const override;
152 QualType getType() const override;
154 // Implement isa<T> support.
155 static inline bool classof(const SymExpr *SE) {
156 return SE->getKind() == SymbolRegionValueKind;
160 /// A symbol representing the result of an expression in the case when we do
161 /// not know anything about what the expression is.
162 class SymbolConjured : public SymbolData {
166 const LocationContext *LCtx;
167 const void *SymbolTag;
170 SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx,
171 QualType t, unsigned count, const void *symbolTag)
172 : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count),
173 LCtx(lctx), SymbolTag(symbolTag) {}
175 const Stmt *getStmt() const { return S; }
176 unsigned getCount() const { return Count; }
177 const void *getTag() const { return SymbolTag; }
179 QualType getType() const override;
181 void dumpToStream(raw_ostream &os) const override;
183 static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
184 QualType T, unsigned Count, const LocationContext *LCtx,
185 const void *SymbolTag) {
186 profile.AddInteger((unsigned) SymbolConjuredKind);
187 profile.AddPointer(S);
188 profile.AddPointer(LCtx);
190 profile.AddInteger(Count);
191 profile.AddPointer(SymbolTag);
194 void Profile(llvm::FoldingSetNodeID& profile) override {
195 Profile(profile, S, T, Count, LCtx, SymbolTag);
198 // Implement isa<T> support.
199 static inline bool classof(const SymExpr *SE) {
200 return SE->getKind() == SymbolConjuredKind;
204 /// A symbol representing the value of a MemRegion whose parent region has
206 class SymbolDerived : public SymbolData {
207 SymbolRef parentSymbol;
208 const TypedValueRegion *R;
211 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
212 : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {}
214 SymbolRef getParentSymbol() const { return parentSymbol; }
215 const TypedValueRegion *getRegion() const { return R; }
217 QualType getType() const override;
219 void dumpToStream(raw_ostream &os) const override;
221 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
222 const TypedValueRegion *r) {
223 profile.AddInteger((unsigned) SymbolDerivedKind);
224 profile.AddPointer(r);
225 profile.AddPointer(parent);
228 void Profile(llvm::FoldingSetNodeID& profile) override {
229 Profile(profile, parentSymbol, R);
232 // Implement isa<T> support.
233 static inline bool classof(const SymExpr *SE) {
234 return SE->getKind() == SymbolDerivedKind;
238 /// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
239 /// Clients should not ask the SymbolManager for a region's extent. Always use
240 /// SubRegion::getExtent instead -- the value returned may not be a symbol.
241 class SymbolExtent : public SymbolData {
245 SymbolExtent(SymbolID sym, const SubRegion *r)
246 : SymbolData(SymbolExtentKind, sym), R(r) {}
248 const SubRegion *getRegion() const { return R; }
250 QualType getType() const override;
252 void dumpToStream(raw_ostream &os) const override;
254 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
255 profile.AddInteger((unsigned) SymbolExtentKind);
256 profile.AddPointer(R);
259 void Profile(llvm::FoldingSetNodeID& profile) override {
263 // Implement isa<T> support.
264 static inline bool classof(const SymExpr *SE) {
265 return SE->getKind() == SymbolExtentKind;
269 /// SymbolMetadata - Represents path-dependent metadata about a specific region.
270 /// Metadata symbols remain live as long as they are marked as in use before
271 /// dead-symbol sweeping AND their associated regions are still alive.
272 /// Intended for use by checkers.
273 class SymbolMetadata : public SymbolData {
280 SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t,
281 unsigned count, const void *tag)
282 : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {}
284 const MemRegion *getRegion() const { return R; }
285 const Stmt *getStmt() const { return S; }
286 unsigned getCount() const { return Count; }
287 const void *getTag() const { return Tag; }
289 QualType getType() const override;
291 void dumpToStream(raw_ostream &os) const override;
293 static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
294 const Stmt *S, QualType T, unsigned Count,
296 profile.AddInteger((unsigned) SymbolMetadataKind);
297 profile.AddPointer(R);
298 profile.AddPointer(S);
300 profile.AddInteger(Count);
301 profile.AddPointer(Tag);
304 void Profile(llvm::FoldingSetNodeID& profile) override {
305 Profile(profile, R, S, T, Count, Tag);
308 // Implement isa<T> support.
309 static inline bool classof(const SymExpr *SE) {
310 return SE->getKind() == SymbolMetadataKind;
314 /// \brief Represents a cast expression.
315 class SymbolCast : public SymExpr {
316 const SymExpr *Operand;
317 /// Type of the operand.
319 /// The type of the result.
323 SymbolCast(const SymExpr *In, QualType From, QualType To) :
324 SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) { }
326 QualType getType() const override { return ToTy; }
328 const SymExpr *getOperand() const { return Operand; }
330 void dumpToStream(raw_ostream &os) const override;
332 static void Profile(llvm::FoldingSetNodeID& ID,
333 const SymExpr *In, QualType From, QualType To) {
334 ID.AddInteger((unsigned) SymbolCastKind);
340 void Profile(llvm::FoldingSetNodeID& ID) override {
341 Profile(ID, Operand, FromTy, ToTy);
344 // Implement isa<T> support.
345 static inline bool classof(const SymExpr *SE) {
346 return SE->getKind() == SymbolCastKind;
350 /// \brief Represents a symbolic expression involving a binary operator
351 class BinarySymExpr : public SymExpr {
352 BinaryOperator::Opcode Op;
356 BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
357 : SymExpr(k), Op(op), T(t) {}
360 // FIXME: We probably need to make this out-of-line to avoid redundant
361 // generation of virtual functions.
362 QualType getType() const override { return T; }
364 BinaryOperator::Opcode getOpcode() const { return Op; }
366 // Implement isa<T> support.
367 static inline bool classof(const SymExpr *SE) {
368 Kind k = SE->getKind();
369 return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
373 /// \brief Represents a symbolic expression like 'x' + 3.
374 class SymIntExpr : public BinarySymExpr {
376 const llvm::APSInt& RHS;
379 SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
380 const llvm::APSInt& rhs, QualType t)
381 : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {}
383 void dumpToStream(raw_ostream &os) const override;
385 const SymExpr *getLHS() const { return LHS; }
386 const llvm::APSInt &getRHS() const { return RHS; }
388 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
389 BinaryOperator::Opcode op, const llvm::APSInt& rhs,
391 ID.AddInteger((unsigned) SymIntExprKind);
398 void Profile(llvm::FoldingSetNodeID& ID) override {
399 Profile(ID, LHS, getOpcode(), RHS, getType());
402 // Implement isa<T> support.
403 static inline bool classof(const SymExpr *SE) {
404 return SE->getKind() == SymIntExprKind;
408 /// \brief Represents a symbolic expression like 3 - 'x'.
409 class IntSymExpr : public BinarySymExpr {
410 const llvm::APSInt& LHS;
414 IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op,
415 const SymExpr *rhs, QualType t)
416 : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {}
418 void dumpToStream(raw_ostream &os) const override;
420 const SymExpr *getRHS() const { return RHS; }
421 const llvm::APSInt &getLHS() const { return LHS; }
423 static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
424 BinaryOperator::Opcode op, const SymExpr *rhs,
426 ID.AddInteger((unsigned) IntSymExprKind);
433 void Profile(llvm::FoldingSetNodeID& ID) override {
434 Profile(ID, LHS, getOpcode(), RHS, getType());
437 // Implement isa<T> support.
438 static inline bool classof(const SymExpr *SE) {
439 return SE->getKind() == IntSymExprKind;
443 /// \brief Represents a symbolic expression like 'x' + 'y'.
444 class SymSymExpr : public BinarySymExpr {
449 SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
451 : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {}
453 const SymExpr *getLHS() const { return LHS; }
454 const SymExpr *getRHS() const { return RHS; }
456 void dumpToStream(raw_ostream &os) const override;
458 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
459 BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
460 ID.AddInteger((unsigned) SymSymExprKind);
467 void Profile(llvm::FoldingSetNodeID& ID) override {
468 Profile(ID, LHS, getOpcode(), RHS, getType());
471 // Implement isa<T> support.
472 static inline bool classof(const SymExpr *SE) {
473 return SE->getKind() == SymSymExprKind;
477 class SymbolManager {
478 typedef llvm::FoldingSet<SymExpr> DataSetTy;
479 typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy;
482 /// Stores the extra dependencies between symbols: the data should be kept
483 /// alive as long as the key is live.
484 SymbolDependTy SymbolDependencies;
485 unsigned SymbolCounter;
486 llvm::BumpPtrAllocator& BPAlloc;
487 BasicValueFactory &BV;
491 SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
492 llvm::BumpPtrAllocator& bpalloc)
493 : SymbolDependencies(16), SymbolCounter(0),
494 BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
498 static bool canSymbolicate(QualType T);
500 /// \brief Make a unique symbol for MemRegion R according to its kind.
501 const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
503 const SymbolConjured* conjureSymbol(const Stmt *E,
504 const LocationContext *LCtx,
507 const void *SymbolTag = nullptr);
509 const SymbolConjured* conjureSymbol(const Expr *E,
510 const LocationContext *LCtx,
512 const void *SymbolTag = nullptr) {
513 return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
516 const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
517 const TypedValueRegion *R);
519 const SymbolExtent *getExtentSymbol(const SubRegion *R);
521 /// \brief Creates a metadata symbol associated with a specific region.
523 /// VisitCount can be used to differentiate regions corresponding to
524 /// different loop iterations, thus, making the symbol path-dependent.
525 const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S,
526 QualType T, unsigned VisitCount,
527 const void *SymbolTag = nullptr);
529 const SymbolCast* getCastSymbol(const SymExpr *Operand,
530 QualType From, QualType To);
532 const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
533 const llvm::APSInt& rhs, QualType t);
535 const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
536 const llvm::APSInt& rhs, QualType t) {
537 return getSymIntExpr(&lhs, op, rhs, t);
540 const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
541 BinaryOperator::Opcode op,
542 const SymExpr *rhs, QualType t);
544 const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
545 const SymExpr *rhs, QualType t);
547 QualType getType(const SymExpr *SE) const {
548 return SE->getType();
551 /// \brief Add artificial symbol dependency.
553 /// The dependent symbol should stay alive as long as the primary is alive.
554 void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
556 const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
558 ASTContext &getContext() { return Ctx; }
559 BasicValueFactory &getBasicVals() { return BV; }
562 /// \brief A class responsible for cleaning up unused symbols.
569 typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
570 typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy;
571 typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
573 SymbolMapTy TheLiving;
574 SymbolSetTy MetadataInUse;
577 RegionSetTy RegionRoots;
579 const StackFrameContext *LCtx;
581 SymbolManager& SymMgr;
582 StoreRef reapedStore;
583 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
586 /// \brief Construct a reaper object, which removes everything which is not
587 /// live before we execute statement s in the given location context.
589 /// If the statement is NULL, everything is this and parent contexts is
591 /// If the stack frame context is NULL, everything on stack is considered
593 SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr,
594 StoreManager &storeMgr)
595 : LCtx(Ctx), Loc(s), SymMgr(symmgr),
596 reapedStore(nullptr, storeMgr) {}
598 const LocationContext *getLocationContext() const { return LCtx; }
600 bool isLive(SymbolRef sym);
601 bool isLiveRegion(const MemRegion *region);
602 bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
603 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
605 /// \brief Unconditionally marks a symbol as live.
607 /// This should never be
608 /// used by checkers, only by the state infrastructure such as the store and
609 /// environment. Checkers should instead use metadata symbols and markInUse.
610 void markLive(SymbolRef sym);
612 /// \brief Marks a symbol as important to a checker.
614 /// For metadata symbols,
615 /// this will keep the symbol alive as long as its associated region is also
616 /// live. For other symbols, this has no effect; checkers are not permitted
617 /// to influence the life of other symbols. This should be used before any
618 /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
619 void markInUse(SymbolRef sym);
621 /// \brief If a symbol is known to be live, marks the symbol as live.
623 /// Otherwise, if the symbol cannot be proven live, it is marked as dead.
624 /// Returns true if the symbol is dead, false if live.
625 bool maybeDead(SymbolRef sym);
627 typedef SymbolSetTy::const_iterator dead_iterator;
628 dead_iterator dead_begin() const { return TheDead.begin(); }
629 dead_iterator dead_end() const { return TheDead.end(); }
631 bool hasDeadSymbols() const {
632 return !TheDead.empty();
635 typedef RegionSetTy::const_iterator region_iterator;
636 region_iterator region_begin() const { return RegionRoots.begin(); }
637 region_iterator region_end() const { return RegionRoots.end(); }
639 /// \brief Returns whether or not a symbol has been confirmed dead.
641 /// This should only be called once all marking of dead symbols has completed.
642 /// (For checkers, this means only in the evalDeadSymbols callback.)
643 bool isDead(SymbolRef sym) const {
644 return TheDead.count(sym);
647 void markLive(const MemRegion *region);
648 void markElementIndicesLive(const MemRegion *region);
650 /// \brief Set to the value of the symbolic store after
651 /// StoreManager::removeDeadBindings has been called.
652 void setReapedStore(StoreRef st) { reapedStore = st; }
655 /// Mark the symbols dependent on the input symbol as live.
656 void markDependentsLive(SymbolRef sym);
659 class SymbolVisitor {
661 ~SymbolVisitor() = default;
664 SymbolVisitor() = default;
665 SymbolVisitor(const SymbolVisitor &) = default;
666 SymbolVisitor(SymbolVisitor &&) {}
668 /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols.
670 /// The method returns \c true if symbols should continue be scanned and \c
672 virtual bool VisitSymbol(SymbolRef sym) = 0;
673 virtual bool VisitMemRegion(const MemRegion *region) { return true; }
676 } // end GR namespace
678 } // end clang namespace
681 static inline raw_ostream &operator<<(raw_ostream &os,
682 const clang::ento::SymExpr *SE) {
683 SE->dumpToStream(os);
686 } // end llvm namespace