1218887Sdim//== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines SymbolManager, a class that manages symbolic values 11218887Sdim// created for use by ExprEngine and related classes. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#ifndef LLVM_CLANG_GR_SYMMGR_H 16218887Sdim#define LLVM_CLANG_GR_SYMMGR_H 17218887Sdim 18218887Sdim#include "clang/AST/Decl.h" 19218887Sdim#include "clang/AST/Expr.h" 20218887Sdim#include "clang/Analysis/AnalysisContext.h" 21226890Sdim#include "clang/Basic/LLVM.h" 22226890Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 23252723Sdim#include "llvm/ADT/DenseMap.h" 24252723Sdim#include "llvm/ADT/DenseSet.h" 25252723Sdim#include "llvm/ADT/FoldingSet.h" 26218887Sdim#include "llvm/Support/DataTypes.h" 27218887Sdim 28218887Sdimnamespace llvm { 29218887Sdimclass BumpPtrAllocator; 30218887Sdim} 31218887Sdim 32218887Sdimnamespace clang { 33218887Sdim class ASTContext; 34218887Sdim class StackFrameContext; 35218887Sdim 36218887Sdimnamespace ento { 37218887Sdim class BasicValueFactory; 38218887Sdim class MemRegion; 39218887Sdim class SubRegion; 40226890Sdim class TypedValueRegion; 41218887Sdim class VarRegion; 42218887Sdim 43235633Sdim/// \brief Symbolic value. These values used to capture symbolic execution of 44235633Sdim/// the program. 45218887Sdimclass SymExpr : public llvm::FoldingSetNode { 46235633Sdim virtual void anchor(); 47218887Sdimpublic: 48226890Sdim enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, 49218887Sdim MetadataKind, 50226890Sdim BEGIN_SYMBOLS = RegionValueKind, 51226890Sdim END_SYMBOLS = MetadataKind, 52252723Sdim SymIntKind, IntSymKind, SymSymKind, 53252723Sdim BEGIN_BINARYSYMEXPRS = SymIntKind, 54252723Sdim END_BINARYSYMEXPRS = SymSymKind, 55252723Sdim CastSymbolKind }; 56218887Sdimprivate: 57218887Sdim Kind K; 58218887Sdim 59218887Sdimprotected: 60218887Sdim SymExpr(Kind k) : K(k) {} 61218887Sdim 62218887Sdimpublic: 63218887Sdim virtual ~SymExpr() {} 64218887Sdim 65218887Sdim Kind getKind() const { return K; } 66218887Sdim 67235633Sdim virtual void dump() const; 68218887Sdim 69235633Sdim virtual void dumpToStream(raw_ostream &os) const {} 70218887Sdim 71245431Sdim virtual QualType getType() const = 0; 72218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; 73218887Sdim 74235633Sdim /// \brief Iterator over symbols that the current symbol depends on. 75235633Sdim /// 76235633Sdim /// For SymbolData, it's the symbol itself; for expressions, it's the 77235633Sdim /// expression symbol and all the operands in it. Note, SymbolDerived is 78235633Sdim /// treated as SymbolData - the iterator will NOT visit the parent region. 79235633Sdim class symbol_iterator { 80235633Sdim SmallVector<const SymExpr*, 5> itr; 81235633Sdim void expand(); 82235633Sdim public: 83235633Sdim symbol_iterator() {} 84235633Sdim symbol_iterator(const SymExpr *SE); 85235633Sdim 86235633Sdim symbol_iterator &operator++(); 87235633Sdim const SymExpr* operator*(); 88235633Sdim 89235633Sdim bool operator==(const symbol_iterator &X) const; 90235633Sdim bool operator!=(const symbol_iterator &X) const; 91235633Sdim }; 92235633Sdim 93235633Sdim symbol_iterator symbol_begin() const { 94235633Sdim return symbol_iterator(this); 95235633Sdim } 96235633Sdim static symbol_iterator symbol_end() { return symbol_iterator(); } 97245431Sdim 98245431Sdim unsigned computeComplexity() const; 99218887Sdim}; 100218887Sdim 101235633Sdimtypedef const SymExpr* SymbolRef; 102252723Sdimtypedef SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy; 103235633Sdim 104218887Sdimtypedef unsigned SymbolID; 105235633Sdim/// \brief A symbol representing data which can be stored in a memory location 106235633Sdim/// (region). 107218887Sdimclass SymbolData : public SymExpr { 108235633Sdim virtual void anchor(); 109218887Sdim const SymbolID Sym; 110218887Sdim 111218887Sdimprotected: 112218887Sdim SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {} 113218887Sdim 114218887Sdimpublic: 115218887Sdim virtual ~SymbolData() {} 116218887Sdim 117218887Sdim SymbolID getSymbolID() const { return Sym; } 118218887Sdim 119218887Sdim // Implement isa<T> support. 120226890Sdim static inline bool classof(const SymExpr *SE) { 121218887Sdim Kind k = SE->getKind(); 122226890Sdim return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; 123218887Sdim } 124218887Sdim}; 125218887Sdim 126235633Sdim///\brief A symbol representing the value stored at a MemRegion. 127218887Sdimclass SymbolRegionValue : public SymbolData { 128226890Sdim const TypedValueRegion *R; 129218887Sdim 130218887Sdimpublic: 131226890Sdim SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 132218887Sdim : SymbolData(RegionValueKind, sym), R(r) {} 133218887Sdim 134226890Sdim const TypedValueRegion* getRegion() const { return R; } 135218887Sdim 136226890Sdim static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { 137218887Sdim profile.AddInteger((unsigned) RegionValueKind); 138218887Sdim profile.AddPointer(R); 139218887Sdim } 140218887Sdim 141218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 142218887Sdim Profile(profile, R); 143218887Sdim } 144218887Sdim 145235633Sdim virtual void dumpToStream(raw_ostream &os) const; 146218887Sdim 147245431Sdim QualType getType() const; 148218887Sdim 149218887Sdim // Implement isa<T> support. 150226890Sdim static inline bool classof(const SymExpr *SE) { 151218887Sdim return SE->getKind() == RegionValueKind; 152218887Sdim } 153218887Sdim}; 154218887Sdim 155235633Sdim/// A symbol representing the result of an expression in the case when we do 156235633Sdim/// not know anything about what the expression is. 157218887Sdimclass SymbolConjured : public SymbolData { 158226890Sdim const Stmt *S; 159218887Sdim QualType T; 160218887Sdim unsigned Count; 161235633Sdim const LocationContext *LCtx; 162226890Sdim const void *SymbolTag; 163218887Sdim 164218887Sdimpublic: 165235633Sdim SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 166235633Sdim QualType t, unsigned count, 167226890Sdim const void *symbolTag) 168218887Sdim : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), 169235633Sdim LCtx(lctx), 170218887Sdim SymbolTag(symbolTag) {} 171218887Sdim 172226890Sdim const Stmt *getStmt() const { return S; } 173218887Sdim unsigned getCount() const { return Count; } 174226890Sdim const void *getTag() const { return SymbolTag; } 175218887Sdim 176245431Sdim QualType getType() const; 177218887Sdim 178235633Sdim virtual void dumpToStream(raw_ostream &os) const; 179218887Sdim 180226890Sdim static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 181235633Sdim QualType T, unsigned Count, const LocationContext *LCtx, 182235633Sdim const void *SymbolTag) { 183218887Sdim profile.AddInteger((unsigned) ConjuredKind); 184218887Sdim profile.AddPointer(S); 185235633Sdim profile.AddPointer(LCtx); 186218887Sdim profile.Add(T); 187218887Sdim profile.AddInteger(Count); 188218887Sdim profile.AddPointer(SymbolTag); 189218887Sdim } 190218887Sdim 191218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 192235633Sdim Profile(profile, S, T, Count, LCtx, SymbolTag); 193218887Sdim } 194218887Sdim 195218887Sdim // Implement isa<T> support. 196226890Sdim static inline bool classof(const SymExpr *SE) { 197218887Sdim return SE->getKind() == ConjuredKind; 198218887Sdim } 199218887Sdim}; 200218887Sdim 201226890Sdim/// A symbol representing the value of a MemRegion whose parent region has 202226890Sdim/// symbolic value. 203218887Sdimclass SymbolDerived : public SymbolData { 204218887Sdim SymbolRef parentSymbol; 205226890Sdim const TypedValueRegion *R; 206218887Sdim 207218887Sdimpublic: 208226890Sdim SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 209218887Sdim : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} 210218887Sdim 211218887Sdim SymbolRef getParentSymbol() const { return parentSymbol; } 212226890Sdim const TypedValueRegion *getRegion() const { return R; } 213218887Sdim 214245431Sdim QualType getType() const; 215218887Sdim 216235633Sdim virtual void dumpToStream(raw_ostream &os) const; 217218887Sdim 218218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 219226890Sdim const TypedValueRegion *r) { 220218887Sdim profile.AddInteger((unsigned) DerivedKind); 221218887Sdim profile.AddPointer(r); 222218887Sdim profile.AddPointer(parent); 223218887Sdim } 224218887Sdim 225218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 226218887Sdim Profile(profile, parentSymbol, R); 227218887Sdim } 228218887Sdim 229218887Sdim // Implement isa<T> support. 230226890Sdim static inline bool classof(const SymExpr *SE) { 231218887Sdim return SE->getKind() == DerivedKind; 232218887Sdim } 233218887Sdim}; 234218887Sdim 235218887Sdim/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 236218887Sdim/// Clients should not ask the SymbolManager for a region's extent. Always use 237218887Sdim/// SubRegion::getExtent instead -- the value returned may not be a symbol. 238218887Sdimclass SymbolExtent : public SymbolData { 239218887Sdim const SubRegion *R; 240218887Sdim 241218887Sdimpublic: 242218887Sdim SymbolExtent(SymbolID sym, const SubRegion *r) 243218887Sdim : SymbolData(ExtentKind, sym), R(r) {} 244218887Sdim 245218887Sdim const SubRegion *getRegion() const { return R; } 246218887Sdim 247245431Sdim QualType getType() const; 248218887Sdim 249235633Sdim virtual void dumpToStream(raw_ostream &os) const; 250218887Sdim 251218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 252218887Sdim profile.AddInteger((unsigned) ExtentKind); 253218887Sdim profile.AddPointer(R); 254218887Sdim } 255218887Sdim 256218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 257218887Sdim Profile(profile, R); 258218887Sdim } 259218887Sdim 260218887Sdim // Implement isa<T> support. 261226890Sdim static inline bool classof(const SymExpr *SE) { 262218887Sdim return SE->getKind() == ExtentKind; 263218887Sdim } 264218887Sdim}; 265218887Sdim 266218887Sdim/// SymbolMetadata - Represents path-dependent metadata about a specific region. 267218887Sdim/// Metadata symbols remain live as long as they are marked as in use before 268218887Sdim/// dead-symbol sweeping AND their associated regions are still alive. 269218887Sdim/// Intended for use by checkers. 270218887Sdimclass SymbolMetadata : public SymbolData { 271218887Sdim const MemRegion* R; 272226890Sdim const Stmt *S; 273218887Sdim QualType T; 274218887Sdim unsigned Count; 275226890Sdim const void *Tag; 276218887Sdimpublic: 277226890Sdim SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 278226890Sdim unsigned count, const void *tag) 279218887Sdim : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} 280218887Sdim 281218887Sdim const MemRegion *getRegion() const { return R; } 282226890Sdim const Stmt *getStmt() const { return S; } 283218887Sdim unsigned getCount() const { return Count; } 284226890Sdim const void *getTag() const { return Tag; } 285218887Sdim 286245431Sdim QualType getType() const; 287218887Sdim 288235633Sdim virtual void dumpToStream(raw_ostream &os) const; 289218887Sdim 290218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 291218887Sdim const Stmt *S, QualType T, unsigned Count, 292218887Sdim const void *Tag) { 293218887Sdim profile.AddInteger((unsigned) MetadataKind); 294218887Sdim profile.AddPointer(R); 295218887Sdim profile.AddPointer(S); 296218887Sdim profile.Add(T); 297218887Sdim profile.AddInteger(Count); 298218887Sdim profile.AddPointer(Tag); 299218887Sdim } 300218887Sdim 301218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 302218887Sdim Profile(profile, R, S, T, Count, Tag); 303218887Sdim } 304218887Sdim 305218887Sdim // Implement isa<T> support. 306226890Sdim static inline bool classof(const SymExpr *SE) { 307218887Sdim return SE->getKind() == MetadataKind; 308218887Sdim } 309218887Sdim}; 310218887Sdim 311235633Sdim/// \brief Represents a cast expression. 312235633Sdimclass SymbolCast : public SymExpr { 313235633Sdim const SymExpr *Operand; 314235633Sdim /// Type of the operand. 315235633Sdim QualType FromTy; 316235633Sdim /// The type of the result. 317235633Sdim QualType ToTy; 318235633Sdim 319235633Sdimpublic: 320235633Sdim SymbolCast(const SymExpr *In, QualType From, QualType To) : 321235633Sdim SymExpr(CastSymbolKind), Operand(In), FromTy(From), ToTy(To) { } 322235633Sdim 323245431Sdim QualType getType() const { return ToTy; } 324235633Sdim 325235633Sdim const SymExpr *getOperand() const { return Operand; } 326235633Sdim 327235633Sdim virtual void dumpToStream(raw_ostream &os) const; 328235633Sdim 329235633Sdim static void Profile(llvm::FoldingSetNodeID& ID, 330235633Sdim const SymExpr *In, QualType From, QualType To) { 331235633Sdim ID.AddInteger((unsigned) CastSymbolKind); 332235633Sdim ID.AddPointer(In); 333235633Sdim ID.Add(From); 334235633Sdim ID.Add(To); 335235633Sdim } 336235633Sdim 337235633Sdim void Profile(llvm::FoldingSetNodeID& ID) { 338235633Sdim Profile(ID, Operand, FromTy, ToTy); 339235633Sdim } 340235633Sdim 341235633Sdim // Implement isa<T> support. 342235633Sdim static inline bool classof(const SymExpr *SE) { 343235633Sdim return SE->getKind() == CastSymbolKind; 344235633Sdim } 345235633Sdim}; 346235633Sdim 347252723Sdim/// \brief Represents a symbolic expression involving a binary operator 348252723Sdimclass BinarySymExpr : public SymExpr { 349218887Sdim BinaryOperator::Opcode Op; 350218887Sdim QualType T; 351218887Sdim 352252723Sdimprotected: 353252723Sdim BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) 354252723Sdim : SymExpr(k), Op(op), T(t) {} 355252723Sdim 356218887Sdimpublic: 357218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 358218887Sdim // generation of virtual functions. 359245431Sdim QualType getType() const { return T; } 360218887Sdim 361218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 362218887Sdim 363252723Sdim // Implement isa<T> support. 364252723Sdim static inline bool classof(const SymExpr *SE) { 365252723Sdim Kind k = SE->getKind(); 366252723Sdim return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; 367252723Sdim } 368252723Sdim}; 369252723Sdim 370252723Sdim/// \brief Represents a symbolic expression like 'x' + 3. 371252723Sdimclass SymIntExpr : public BinarySymExpr { 372252723Sdim const SymExpr *LHS; 373252723Sdim const llvm::APSInt& RHS; 374252723Sdim 375252723Sdimpublic: 376252723Sdim SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 377252723Sdim const llvm::APSInt& rhs, QualType t) 378252723Sdim : BinarySymExpr(SymIntKind, op, t), LHS(lhs), RHS(rhs) {} 379252723Sdim 380235633Sdim virtual void dumpToStream(raw_ostream &os) const; 381218887Sdim 382218887Sdim const SymExpr *getLHS() const { return LHS; } 383218887Sdim const llvm::APSInt &getRHS() const { return RHS; } 384218887Sdim 385218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 386218887Sdim BinaryOperator::Opcode op, const llvm::APSInt& rhs, 387218887Sdim QualType t) { 388218887Sdim ID.AddInteger((unsigned) SymIntKind); 389218887Sdim ID.AddPointer(lhs); 390218887Sdim ID.AddInteger(op); 391218887Sdim ID.AddPointer(&rhs); 392218887Sdim ID.Add(t); 393218887Sdim } 394218887Sdim 395218887Sdim void Profile(llvm::FoldingSetNodeID& ID) { 396252723Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 397218887Sdim } 398218887Sdim 399218887Sdim // Implement isa<T> support. 400226890Sdim static inline bool classof(const SymExpr *SE) { 401218887Sdim return SE->getKind() == SymIntKind; 402218887Sdim } 403218887Sdim}; 404218887Sdim 405252723Sdim/// \brief Represents a symbolic expression like 3 - 'x'. 406252723Sdimclass IntSymExpr : public BinarySymExpr { 407235633Sdim const llvm::APSInt& LHS; 408235633Sdim const SymExpr *RHS; 409235633Sdim 410235633Sdimpublic: 411235633Sdim IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, 412235633Sdim const SymExpr *rhs, QualType t) 413252723Sdim : BinarySymExpr(IntSymKind, op, t), LHS(lhs), RHS(rhs) {} 414235633Sdim 415235633Sdim virtual void dumpToStream(raw_ostream &os) const; 416235633Sdim 417235633Sdim const SymExpr *getRHS() const { return RHS; } 418235633Sdim const llvm::APSInt &getLHS() const { return LHS; } 419235633Sdim 420235633Sdim static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 421235633Sdim BinaryOperator::Opcode op, const SymExpr *rhs, 422235633Sdim QualType t) { 423235633Sdim ID.AddInteger((unsigned) IntSymKind); 424235633Sdim ID.AddPointer(&lhs); 425235633Sdim ID.AddInteger(op); 426235633Sdim ID.AddPointer(rhs); 427235633Sdim ID.Add(t); 428235633Sdim } 429235633Sdim 430235633Sdim void Profile(llvm::FoldingSetNodeID& ID) { 431252723Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 432235633Sdim } 433235633Sdim 434235633Sdim // Implement isa<T> support. 435235633Sdim static inline bool classof(const SymExpr *SE) { 436235633Sdim return SE->getKind() == IntSymKind; 437235633Sdim } 438235633Sdim}; 439235633Sdim 440252723Sdim/// \brief Represents a symbolic expression like 'x' + 'y'. 441252723Sdimclass SymSymExpr : public BinarySymExpr { 442218887Sdim const SymExpr *LHS; 443218887Sdim const SymExpr *RHS; 444218887Sdim 445218887Sdimpublic: 446218887Sdim SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 447218887Sdim QualType t) 448252723Sdim : BinarySymExpr(SymSymKind, op, t), LHS(lhs), RHS(rhs) {} 449218887Sdim 450218887Sdim const SymExpr *getLHS() const { return LHS; } 451218887Sdim const SymExpr *getRHS() const { return RHS; } 452218887Sdim 453235633Sdim virtual void dumpToStream(raw_ostream &os) const; 454218887Sdim 455218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 456218887Sdim BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 457218887Sdim ID.AddInteger((unsigned) SymSymKind); 458218887Sdim ID.AddPointer(lhs); 459218887Sdim ID.AddInteger(op); 460218887Sdim ID.AddPointer(rhs); 461218887Sdim ID.Add(t); 462218887Sdim } 463218887Sdim 464218887Sdim void Profile(llvm::FoldingSetNodeID& ID) { 465252723Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 466218887Sdim } 467218887Sdim 468218887Sdim // Implement isa<T> support. 469226890Sdim static inline bool classof(const SymExpr *SE) { 470218887Sdim return SE->getKind() == SymSymKind; 471218887Sdim } 472218887Sdim}; 473218887Sdim 474218887Sdimclass SymbolManager { 475218887Sdim typedef llvm::FoldingSet<SymExpr> DataSetTy; 476226890Sdim typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; 477226890Sdim 478218887Sdim DataSetTy DataSet; 479226890Sdim /// Stores the extra dependencies between symbols: the data should be kept 480226890Sdim /// alive as long as the key is live. 481226890Sdim SymbolDependTy SymbolDependencies; 482218887Sdim unsigned SymbolCounter; 483218887Sdim llvm::BumpPtrAllocator& BPAlloc; 484218887Sdim BasicValueFactory &BV; 485226890Sdim ASTContext &Ctx; 486218887Sdim 487218887Sdimpublic: 488226890Sdim SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 489218887Sdim llvm::BumpPtrAllocator& bpalloc) 490226890Sdim : SymbolDependencies(16), SymbolCounter(0), 491226890Sdim BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 492218887Sdim 493218887Sdim ~SymbolManager(); 494218887Sdim 495218887Sdim static bool canSymbolicate(QualType T); 496218887Sdim 497226890Sdim /// \brief Make a unique symbol for MemRegion R according to its kind. 498226890Sdim const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 499218887Sdim 500245431Sdim const SymbolConjured* conjureSymbol(const Stmt *E, 501245431Sdim const LocationContext *LCtx, 502245431Sdim QualType T, 503245431Sdim unsigned VisitCount, 504245431Sdim const void *SymbolTag = 0); 505218887Sdim 506245431Sdim const SymbolConjured* conjureSymbol(const Expr *E, 507245431Sdim const LocationContext *LCtx, 508245431Sdim unsigned VisitCount, 509245431Sdim const void *SymbolTag = 0) { 510245431Sdim return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag); 511218887Sdim } 512218887Sdim 513218887Sdim const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 514226890Sdim const TypedValueRegion *R); 515218887Sdim 516218887Sdim const SymbolExtent *getExtentSymbol(const SubRegion *R); 517218887Sdim 518226890Sdim /// \brief Creates a metadata symbol associated with a specific region. 519226890Sdim /// 520226890Sdim /// VisitCount can be used to differentiate regions corresponding to 521226890Sdim /// different loop iterations, thus, making the symbol path-dependent. 522226890Sdim const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt *S, 523218887Sdim QualType T, unsigned VisitCount, 524226890Sdim const void *SymbolTag = 0); 525218887Sdim 526235633Sdim const SymbolCast* getCastSymbol(const SymExpr *Operand, 527235633Sdim QualType From, QualType To); 528235633Sdim 529218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 530218887Sdim const llvm::APSInt& rhs, QualType t); 531218887Sdim 532218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 533218887Sdim const llvm::APSInt& rhs, QualType t) { 534218887Sdim return getSymIntExpr(&lhs, op, rhs, t); 535218887Sdim } 536218887Sdim 537235633Sdim const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, 538235633Sdim BinaryOperator::Opcode op, 539235633Sdim const SymExpr *rhs, QualType t); 540235633Sdim 541218887Sdim const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 542218887Sdim const SymExpr *rhs, QualType t); 543218887Sdim 544218887Sdim QualType getType(const SymExpr *SE) const { 545245431Sdim return SE->getType(); 546218887Sdim } 547218887Sdim 548226890Sdim /// \brief Add artificial symbol dependency. 549226890Sdim /// 550226890Sdim /// The dependent symbol should stay alive as long as the primary is alive. 551226890Sdim void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); 552226890Sdim 553226890Sdim const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); 554226890Sdim 555218887Sdim ASTContext &getContext() { return Ctx; } 556218887Sdim BasicValueFactory &getBasicVals() { return BV; } 557218887Sdim}; 558218887Sdim 559245431Sdim/// \brief A class responsible for cleaning up unused symbols. 560218887Sdimclass SymbolReaper { 561226890Sdim enum SymbolStatus { 562226890Sdim NotProcessed, 563226890Sdim HaveMarkedDependents 564226890Sdim }; 565218887Sdim 566226890Sdim typedef llvm::DenseSet<SymbolRef> SymbolSetTy; 567226890Sdim typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; 568226890Sdim typedef llvm::DenseSet<const MemRegion *> RegionSetTy; 569226890Sdim 570226890Sdim SymbolMapTy TheLiving; 571226890Sdim SymbolSetTy MetadataInUse; 572226890Sdim SymbolSetTy TheDead; 573226890Sdim 574226890Sdim RegionSetTy RegionRoots; 575226890Sdim 576245431Sdim const StackFrameContext *LCtx; 577218887Sdim const Stmt *Loc; 578218887Sdim SymbolManager& SymMgr; 579226890Sdim StoreRef reapedStore; 580226890Sdim llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 581218887Sdim 582218887Sdimpublic: 583245431Sdim /// \brief Construct a reaper object, which removes everything which is not 584245431Sdim /// live before we execute statement s in the given location context. 585245431Sdim /// 586245431Sdim /// If the statement is NULL, everything is this and parent contexts is 587245431Sdim /// considered live. 588245431Sdim /// If the stack frame context is NULL, everything on stack is considered 589245431Sdim /// dead. 590245431Sdim SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr, 591226890Sdim StoreManager &storeMgr) 592245431Sdim : LCtx(Ctx), Loc(s), SymMgr(symmgr), 593245431Sdim reapedStore(0, storeMgr) {} 594218887Sdim 595218887Sdim ~SymbolReaper() {} 596218887Sdim 597218887Sdim const LocationContext *getLocationContext() const { return LCtx; } 598218887Sdim 599218887Sdim bool isLive(SymbolRef sym); 600226890Sdim bool isLiveRegion(const MemRegion *region); 601235633Sdim bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 602226890Sdim bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 603218887Sdim 604226890Sdim /// \brief Unconditionally marks a symbol as live. 605226890Sdim /// 606226890Sdim /// This should never be 607226890Sdim /// used by checkers, only by the state infrastructure such as the store and 608226890Sdim /// environment. Checkers should instead use metadata symbols and markInUse. 609218887Sdim void markLive(SymbolRef sym); 610218887Sdim 611226890Sdim /// \brief Marks a symbol as important to a checker. 612226890Sdim /// 613226890Sdim /// For metadata symbols, 614226890Sdim /// this will keep the symbol alive as long as its associated region is also 615226890Sdim /// live. For other symbols, this has no effect; checkers are not permitted 616226890Sdim /// to influence the life of other symbols. This should be used before any 617226890Sdim /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 618218887Sdim void markInUse(SymbolRef sym); 619218887Sdim 620226890Sdim /// \brief If a symbol is known to be live, marks the symbol as live. 621226890Sdim /// 622226890Sdim /// Otherwise, if the symbol cannot be proven live, it is marked as dead. 623226890Sdim /// Returns true if the symbol is dead, false if live. 624218887Sdim bool maybeDead(SymbolRef sym); 625218887Sdim 626226890Sdim typedef SymbolSetTy::const_iterator dead_iterator; 627218887Sdim dead_iterator dead_begin() const { return TheDead.begin(); } 628218887Sdim dead_iterator dead_end() const { return TheDead.end(); } 629218887Sdim 630218887Sdim bool hasDeadSymbols() const { 631218887Sdim return !TheDead.empty(); 632218887Sdim } 633226890Sdim 634226890Sdim typedef RegionSetTy::const_iterator region_iterator; 635226890Sdim region_iterator region_begin() const { return RegionRoots.begin(); } 636226890Sdim region_iterator region_end() const { return RegionRoots.end(); } 637218887Sdim 638226890Sdim /// \brief Returns whether or not a symbol has been confirmed dead. 639226890Sdim /// 640226890Sdim /// This should only be called once all marking of dead symbols has completed. 641226890Sdim /// (For checkers, this means only in the evalDeadSymbols callback.) 642218887Sdim bool isDead(SymbolRef sym) const { 643218887Sdim return TheDead.count(sym); 644218887Sdim } 645226890Sdim 646226890Sdim void markLive(const MemRegion *region); 647226890Sdim 648226890Sdim /// \brief Set to the value of the symbolic store after 649226890Sdim /// StoreManager::removeDeadBindings has been called. 650226890Sdim void setReapedStore(StoreRef st) { reapedStore = st; } 651226890Sdim 652226890Sdimprivate: 653226890Sdim /// Mark the symbols dependent on the input symbol as live. 654226890Sdim void markDependentsLive(SymbolRef sym); 655218887Sdim}; 656218887Sdim 657218887Sdimclass SymbolVisitor { 658218887Sdimpublic: 659226890Sdim /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. 660226890Sdim /// 661226890Sdim /// The method returns \c true if symbols should continue be scanned and \c 662226890Sdim /// false otherwise. 663218887Sdim virtual bool VisitSymbol(SymbolRef sym) = 0; 664226890Sdim virtual bool VisitMemRegion(const MemRegion *region) { return true; } 665218887Sdim virtual ~SymbolVisitor(); 666218887Sdim}; 667218887Sdim 668218887Sdim} // end GR namespace 669218887Sdim 670218887Sdim} // end clang namespace 671218887Sdim 672218887Sdimnamespace llvm { 673226890Sdimstatic inline raw_ostream &operator<<(raw_ostream &os, 674235633Sdim const clang::ento::SymExpr *SE) { 675218887Sdim SE->dumpToStream(os); 676218887Sdim return os; 677218887Sdim} 678218887Sdim} // end llvm namespace 679218887Sdim#endif 680