SymbolManager.h revision 234353
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" 21226633Sdim#include "clang/Basic/LLVM.h" 22226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 23218887Sdim#include "llvm/Support/DataTypes.h" 24218887Sdim#include "llvm/ADT/FoldingSet.h" 25218887Sdim#include "llvm/ADT/DenseSet.h" 26226633Sdim#include "llvm/ADT/DenseMap.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; 40226633Sdim class TypedValueRegion; 41218887Sdim class VarRegion; 42218887Sdim 43234353Sdim/// \brief Symbolic value. These values used to capture symbolic execution of 44234353Sdim/// the program. 45218887Sdimclass SymExpr : public llvm::FoldingSetNode { 46234353Sdim virtual void anchor(); 47218887Sdimpublic: 48226633Sdim enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, 49218887Sdim MetadataKind, 50226633Sdim BEGIN_SYMBOLS = RegionValueKind, 51226633Sdim END_SYMBOLS = MetadataKind, 52234353Sdim SymIntKind, IntSymKind, SymSymKind, CastSymbolKind }; 53218887Sdimprivate: 54218887Sdim Kind K; 55218887Sdim 56218887Sdimprotected: 57218887Sdim SymExpr(Kind k) : K(k) {} 58218887Sdim 59218887Sdimpublic: 60218887Sdim virtual ~SymExpr() {} 61218887Sdim 62218887Sdim Kind getKind() const { return K; } 63218887Sdim 64234353Sdim virtual void dump() const; 65218887Sdim 66234353Sdim virtual void dumpToStream(raw_ostream &os) const {} 67218887Sdim 68218887Sdim virtual QualType getType(ASTContext&) const = 0; 69218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; 70218887Sdim 71218887Sdim // Implement isa<T> support. 72218887Sdim static inline bool classof(const SymExpr*) { return true; } 73234353Sdim 74234353Sdim /// \brief Iterator over symbols that the current symbol depends on. 75234353Sdim /// 76234353Sdim /// For SymbolData, it's the symbol itself; for expressions, it's the 77234353Sdim /// expression symbol and all the operands in it. Note, SymbolDerived is 78234353Sdim /// treated as SymbolData - the iterator will NOT visit the parent region. 79234353Sdim class symbol_iterator { 80234353Sdim SmallVector<const SymExpr*, 5> itr; 81234353Sdim void expand(); 82234353Sdim public: 83234353Sdim symbol_iterator() {} 84234353Sdim symbol_iterator(const SymExpr *SE); 85234353Sdim 86234353Sdim symbol_iterator &operator++(); 87234353Sdim const SymExpr* operator*(); 88234353Sdim 89234353Sdim bool operator==(const symbol_iterator &X) const; 90234353Sdim bool operator!=(const symbol_iterator &X) const; 91234353Sdim }; 92234353Sdim 93234353Sdim symbol_iterator symbol_begin() const { 94234353Sdim return symbol_iterator(this); 95234353Sdim } 96234353Sdim static symbol_iterator symbol_end() { return symbol_iterator(); } 97218887Sdim}; 98218887Sdim 99234353Sdimtypedef const SymExpr* SymbolRef; 100234353Sdimtypedef llvm::SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy; 101234353Sdim 102218887Sdimtypedef unsigned SymbolID; 103234353Sdim/// \brief A symbol representing data which can be stored in a memory location 104234353Sdim/// (region). 105218887Sdimclass SymbolData : public SymExpr { 106234353Sdim virtual void anchor(); 107218887Sdim const SymbolID Sym; 108218887Sdim 109218887Sdimprotected: 110218887Sdim SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {} 111218887Sdim 112218887Sdimpublic: 113218887Sdim virtual ~SymbolData() {} 114218887Sdim 115218887Sdim SymbolID getSymbolID() const { return Sym; } 116218887Sdim 117218887Sdim // Implement isa<T> support. 118226633Sdim static inline bool classof(const SymExpr *SE) { 119218887Sdim Kind k = SE->getKind(); 120226633Sdim return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; 121218887Sdim } 122218887Sdim}; 123218887Sdim 124234353Sdim///\brief A symbol representing the value stored at a MemRegion. 125218887Sdimclass SymbolRegionValue : public SymbolData { 126226633Sdim const TypedValueRegion *R; 127218887Sdim 128218887Sdimpublic: 129226633Sdim SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 130218887Sdim : SymbolData(RegionValueKind, sym), R(r) {} 131218887Sdim 132226633Sdim const TypedValueRegion* getRegion() const { return R; } 133218887Sdim 134226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { 135218887Sdim profile.AddInteger((unsigned) RegionValueKind); 136218887Sdim profile.AddPointer(R); 137218887Sdim } 138218887Sdim 139218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 140218887Sdim Profile(profile, R); 141218887Sdim } 142218887Sdim 143234353Sdim virtual void dumpToStream(raw_ostream &os) const; 144218887Sdim 145218887Sdim QualType getType(ASTContext&) const; 146218887Sdim 147218887Sdim // Implement isa<T> support. 148226633Sdim static inline bool classof(const SymExpr *SE) { 149218887Sdim return SE->getKind() == RegionValueKind; 150218887Sdim } 151218887Sdim}; 152218887Sdim 153234353Sdim/// A symbol representing the result of an expression in the case when we do 154234353Sdim/// not know anything about what the expression is. 155218887Sdimclass SymbolConjured : public SymbolData { 156226633Sdim const Stmt *S; 157218887Sdim QualType T; 158218887Sdim unsigned Count; 159234353Sdim const LocationContext *LCtx; 160226633Sdim const void *SymbolTag; 161218887Sdim 162218887Sdimpublic: 163234353Sdim SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 164234353Sdim QualType t, unsigned count, 165226633Sdim const void *symbolTag) 166218887Sdim : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), 167234353Sdim LCtx(lctx), 168218887Sdim SymbolTag(symbolTag) {} 169218887Sdim 170226633Sdim const Stmt *getStmt() const { return S; } 171218887Sdim unsigned getCount() const { return Count; } 172226633Sdim const void *getTag() const { return SymbolTag; } 173218887Sdim 174218887Sdim QualType getType(ASTContext&) const; 175218887Sdim 176234353Sdim virtual void dumpToStream(raw_ostream &os) const; 177218887Sdim 178226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 179234353Sdim QualType T, unsigned Count, const LocationContext *LCtx, 180234353Sdim const void *SymbolTag) { 181218887Sdim profile.AddInteger((unsigned) ConjuredKind); 182218887Sdim profile.AddPointer(S); 183234353Sdim profile.AddPointer(LCtx); 184218887Sdim profile.Add(T); 185218887Sdim profile.AddInteger(Count); 186218887Sdim profile.AddPointer(SymbolTag); 187218887Sdim } 188218887Sdim 189218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 190234353Sdim Profile(profile, S, T, Count, LCtx, SymbolTag); 191218887Sdim } 192218887Sdim 193218887Sdim // Implement isa<T> support. 194226633Sdim static inline bool classof(const SymExpr *SE) { 195218887Sdim return SE->getKind() == ConjuredKind; 196218887Sdim } 197218887Sdim}; 198218887Sdim 199226633Sdim/// A symbol representing the value of a MemRegion whose parent region has 200226633Sdim/// symbolic value. 201218887Sdimclass SymbolDerived : public SymbolData { 202218887Sdim SymbolRef parentSymbol; 203226633Sdim const TypedValueRegion *R; 204218887Sdim 205218887Sdimpublic: 206226633Sdim SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 207218887Sdim : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} 208218887Sdim 209218887Sdim SymbolRef getParentSymbol() const { return parentSymbol; } 210226633Sdim const TypedValueRegion *getRegion() const { return R; } 211218887Sdim 212218887Sdim QualType getType(ASTContext&) const; 213218887Sdim 214234353Sdim virtual void dumpToStream(raw_ostream &os) const; 215218887Sdim 216218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 217226633Sdim const TypedValueRegion *r) { 218218887Sdim profile.AddInteger((unsigned) DerivedKind); 219218887Sdim profile.AddPointer(r); 220218887Sdim profile.AddPointer(parent); 221218887Sdim } 222218887Sdim 223218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 224218887Sdim Profile(profile, parentSymbol, R); 225218887Sdim } 226218887Sdim 227218887Sdim // Implement isa<T> support. 228226633Sdim static inline bool classof(const SymExpr *SE) { 229218887Sdim return SE->getKind() == DerivedKind; 230218887Sdim } 231218887Sdim}; 232218887Sdim 233218887Sdim/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 234218887Sdim/// Clients should not ask the SymbolManager for a region's extent. Always use 235218887Sdim/// SubRegion::getExtent instead -- the value returned may not be a symbol. 236218887Sdimclass SymbolExtent : public SymbolData { 237218887Sdim const SubRegion *R; 238218887Sdim 239218887Sdimpublic: 240218887Sdim SymbolExtent(SymbolID sym, const SubRegion *r) 241218887Sdim : SymbolData(ExtentKind, sym), R(r) {} 242218887Sdim 243218887Sdim const SubRegion *getRegion() const { return R; } 244218887Sdim 245218887Sdim QualType getType(ASTContext&) const; 246218887Sdim 247234353Sdim virtual void dumpToStream(raw_ostream &os) const; 248218887Sdim 249218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 250218887Sdim profile.AddInteger((unsigned) ExtentKind); 251218887Sdim profile.AddPointer(R); 252218887Sdim } 253218887Sdim 254218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 255218887Sdim Profile(profile, R); 256218887Sdim } 257218887Sdim 258218887Sdim // Implement isa<T> support. 259226633Sdim static inline bool classof(const SymExpr *SE) { 260218887Sdim return SE->getKind() == ExtentKind; 261218887Sdim } 262218887Sdim}; 263218887Sdim 264218887Sdim/// SymbolMetadata - Represents path-dependent metadata about a specific region. 265218887Sdim/// Metadata symbols remain live as long as they are marked as in use before 266218887Sdim/// dead-symbol sweeping AND their associated regions are still alive. 267218887Sdim/// Intended for use by checkers. 268218887Sdimclass SymbolMetadata : public SymbolData { 269218887Sdim const MemRegion* R; 270226633Sdim const Stmt *S; 271218887Sdim QualType T; 272218887Sdim unsigned Count; 273226633Sdim const void *Tag; 274218887Sdimpublic: 275226633Sdim SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 276226633Sdim unsigned count, const void *tag) 277218887Sdim : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} 278218887Sdim 279218887Sdim const MemRegion *getRegion() const { return R; } 280226633Sdim const Stmt *getStmt() const { return S; } 281218887Sdim unsigned getCount() const { return Count; } 282226633Sdim const void *getTag() const { return Tag; } 283218887Sdim 284218887Sdim QualType getType(ASTContext&) const; 285218887Sdim 286234353Sdim virtual void dumpToStream(raw_ostream &os) const; 287218887Sdim 288218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 289218887Sdim const Stmt *S, QualType T, unsigned Count, 290218887Sdim const void *Tag) { 291218887Sdim profile.AddInteger((unsigned) MetadataKind); 292218887Sdim profile.AddPointer(R); 293218887Sdim profile.AddPointer(S); 294218887Sdim profile.Add(T); 295218887Sdim profile.AddInteger(Count); 296218887Sdim profile.AddPointer(Tag); 297218887Sdim } 298218887Sdim 299218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 300218887Sdim Profile(profile, R, S, T, Count, Tag); 301218887Sdim } 302218887Sdim 303218887Sdim // Implement isa<T> support. 304226633Sdim static inline bool classof(const SymExpr *SE) { 305218887Sdim return SE->getKind() == MetadataKind; 306218887Sdim } 307218887Sdim}; 308218887Sdim 309234353Sdim/// \brief Represents a cast expression. 310234353Sdimclass SymbolCast : public SymExpr { 311234353Sdim const SymExpr *Operand; 312234353Sdim /// Type of the operand. 313234353Sdim QualType FromTy; 314234353Sdim /// The type of the result. 315234353Sdim QualType ToTy; 316234353Sdim 317234353Sdimpublic: 318234353Sdim SymbolCast(const SymExpr *In, QualType From, QualType To) : 319234353Sdim SymExpr(CastSymbolKind), Operand(In), FromTy(From), ToTy(To) { } 320234353Sdim 321234353Sdim QualType getType(ASTContext &C) const { return ToTy; } 322234353Sdim 323234353Sdim const SymExpr *getOperand() const { return Operand; } 324234353Sdim 325234353Sdim virtual void dumpToStream(raw_ostream &os) const; 326234353Sdim 327234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, 328234353Sdim const SymExpr *In, QualType From, QualType To) { 329234353Sdim ID.AddInteger((unsigned) CastSymbolKind); 330234353Sdim ID.AddPointer(In); 331234353Sdim ID.Add(From); 332234353Sdim ID.Add(To); 333234353Sdim } 334234353Sdim 335234353Sdim void Profile(llvm::FoldingSetNodeID& ID) { 336234353Sdim Profile(ID, Operand, FromTy, ToTy); 337234353Sdim } 338234353Sdim 339234353Sdim // Implement isa<T> support. 340234353Sdim static inline bool classof(const SymExpr *SE) { 341234353Sdim return SE->getKind() == CastSymbolKind; 342234353Sdim } 343234353Sdim}; 344234353Sdim 345226633Sdim/// SymIntExpr - Represents symbolic expression like 'x' + 3. 346218887Sdimclass SymIntExpr : public SymExpr { 347218887Sdim const SymExpr *LHS; 348218887Sdim BinaryOperator::Opcode Op; 349218887Sdim const llvm::APSInt& RHS; 350218887Sdim QualType T; 351218887Sdim 352218887Sdimpublic: 353218887Sdim SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 354218887Sdim const llvm::APSInt& rhs, QualType t) 355218887Sdim : SymExpr(SymIntKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} 356218887Sdim 357218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 358218887Sdim // generation of virtual functions. 359226633Sdim QualType getType(ASTContext &C) const { return T; } 360218887Sdim 361218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 362218887Sdim 363234353Sdim virtual void dumpToStream(raw_ostream &os) const; 364218887Sdim 365218887Sdim const SymExpr *getLHS() const { return LHS; } 366218887Sdim const llvm::APSInt &getRHS() const { return RHS; } 367218887Sdim 368218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 369218887Sdim BinaryOperator::Opcode op, const llvm::APSInt& rhs, 370218887Sdim QualType t) { 371218887Sdim ID.AddInteger((unsigned) SymIntKind); 372218887Sdim ID.AddPointer(lhs); 373218887Sdim ID.AddInteger(op); 374218887Sdim ID.AddPointer(&rhs); 375218887Sdim ID.Add(t); 376218887Sdim } 377218887Sdim 378218887Sdim void Profile(llvm::FoldingSetNodeID& ID) { 379218887Sdim Profile(ID, LHS, Op, RHS, T); 380218887Sdim } 381218887Sdim 382218887Sdim // Implement isa<T> support. 383226633Sdim static inline bool classof(const SymExpr *SE) { 384218887Sdim return SE->getKind() == SymIntKind; 385218887Sdim } 386218887Sdim}; 387218887Sdim 388234353Sdim/// IntSymExpr - Represents symbolic expression like 3 - 'x'. 389234353Sdimclass IntSymExpr : public SymExpr { 390234353Sdim const llvm::APSInt& LHS; 391234353Sdim BinaryOperator::Opcode Op; 392234353Sdim const SymExpr *RHS; 393234353Sdim QualType T; 394234353Sdim 395234353Sdimpublic: 396234353Sdim IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, 397234353Sdim const SymExpr *rhs, QualType t) 398234353Sdim : SymExpr(IntSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} 399234353Sdim 400234353Sdim QualType getType(ASTContext &C) const { return T; } 401234353Sdim 402234353Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 403234353Sdim 404234353Sdim virtual void dumpToStream(raw_ostream &os) const; 405234353Sdim 406234353Sdim const SymExpr *getRHS() const { return RHS; } 407234353Sdim const llvm::APSInt &getLHS() const { return LHS; } 408234353Sdim 409234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 410234353Sdim BinaryOperator::Opcode op, const SymExpr *rhs, 411234353Sdim QualType t) { 412234353Sdim ID.AddInteger((unsigned) IntSymKind); 413234353Sdim ID.AddPointer(&lhs); 414234353Sdim ID.AddInteger(op); 415234353Sdim ID.AddPointer(rhs); 416234353Sdim ID.Add(t); 417234353Sdim } 418234353Sdim 419234353Sdim void Profile(llvm::FoldingSetNodeID& ID) { 420234353Sdim Profile(ID, LHS, Op, RHS, T); 421234353Sdim } 422234353Sdim 423234353Sdim // Implement isa<T> support. 424234353Sdim static inline bool classof(const SymExpr *SE) { 425234353Sdim return SE->getKind() == IntSymKind; 426234353Sdim } 427234353Sdim}; 428234353Sdim 429226633Sdim/// SymSymExpr - Represents symbolic expression like 'x' + 'y'. 430218887Sdimclass SymSymExpr : public SymExpr { 431218887Sdim const SymExpr *LHS; 432218887Sdim BinaryOperator::Opcode Op; 433218887Sdim const SymExpr *RHS; 434218887Sdim QualType T; 435218887Sdim 436218887Sdimpublic: 437218887Sdim SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 438218887Sdim QualType t) 439218887Sdim : SymExpr(SymSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} 440218887Sdim 441218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 442218887Sdim const SymExpr *getLHS() const { return LHS; } 443218887Sdim const SymExpr *getRHS() const { return RHS; } 444218887Sdim 445218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 446218887Sdim // generation of virtual functions. 447226633Sdim QualType getType(ASTContext &C) const { return T; } 448218887Sdim 449234353Sdim virtual void dumpToStream(raw_ostream &os) const; 450218887Sdim 451218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 452218887Sdim BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 453218887Sdim ID.AddInteger((unsigned) SymSymKind); 454218887Sdim ID.AddPointer(lhs); 455218887Sdim ID.AddInteger(op); 456218887Sdim ID.AddPointer(rhs); 457218887Sdim ID.Add(t); 458218887Sdim } 459218887Sdim 460218887Sdim void Profile(llvm::FoldingSetNodeID& ID) { 461218887Sdim Profile(ID, LHS, Op, RHS, T); 462218887Sdim } 463218887Sdim 464218887Sdim // Implement isa<T> support. 465226633Sdim static inline bool classof(const SymExpr *SE) { 466218887Sdim return SE->getKind() == SymSymKind; 467218887Sdim } 468218887Sdim}; 469218887Sdim 470218887Sdimclass SymbolManager { 471218887Sdim typedef llvm::FoldingSet<SymExpr> DataSetTy; 472226633Sdim typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; 473226633Sdim 474218887Sdim DataSetTy DataSet; 475226633Sdim /// Stores the extra dependencies between symbols: the data should be kept 476226633Sdim /// alive as long as the key is live. 477226633Sdim SymbolDependTy SymbolDependencies; 478218887Sdim unsigned SymbolCounter; 479218887Sdim llvm::BumpPtrAllocator& BPAlloc; 480218887Sdim BasicValueFactory &BV; 481226633Sdim ASTContext &Ctx; 482218887Sdim 483218887Sdimpublic: 484226633Sdim SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 485218887Sdim llvm::BumpPtrAllocator& bpalloc) 486226633Sdim : SymbolDependencies(16), SymbolCounter(0), 487226633Sdim BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 488218887Sdim 489218887Sdim ~SymbolManager(); 490218887Sdim 491218887Sdim static bool canSymbolicate(QualType T); 492218887Sdim 493226633Sdim /// \brief Make a unique symbol for MemRegion R according to its kind. 494226633Sdim const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 495218887Sdim 496234353Sdim const SymbolConjured* getConjuredSymbol(const Stmt *E, 497234353Sdim const LocationContext *LCtx, 498234353Sdim QualType T, 499218887Sdim unsigned VisitCount, 500226633Sdim const void *SymbolTag = 0); 501218887Sdim 502234353Sdim const SymbolConjured* getConjuredSymbol(const Expr *E, 503234353Sdim const LocationContext *LCtx, 504234353Sdim unsigned VisitCount, 505226633Sdim const void *SymbolTag = 0) { 506234353Sdim return getConjuredSymbol(E, LCtx, E->getType(), 507234353Sdim VisitCount, SymbolTag); 508218887Sdim } 509218887Sdim 510218887Sdim const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 511226633Sdim const TypedValueRegion *R); 512218887Sdim 513218887Sdim const SymbolExtent *getExtentSymbol(const SubRegion *R); 514218887Sdim 515226633Sdim /// \brief Creates a metadata symbol associated with a specific region. 516226633Sdim /// 517226633Sdim /// VisitCount can be used to differentiate regions corresponding to 518226633Sdim /// different loop iterations, thus, making the symbol path-dependent. 519226633Sdim const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt *S, 520218887Sdim QualType T, unsigned VisitCount, 521226633Sdim const void *SymbolTag = 0); 522218887Sdim 523234353Sdim const SymbolCast* getCastSymbol(const SymExpr *Operand, 524234353Sdim QualType From, QualType To); 525234353Sdim 526218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 527218887Sdim const llvm::APSInt& rhs, QualType t); 528218887Sdim 529218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 530218887Sdim const llvm::APSInt& rhs, QualType t) { 531218887Sdim return getSymIntExpr(&lhs, op, rhs, t); 532218887Sdim } 533218887Sdim 534234353Sdim const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, 535234353Sdim BinaryOperator::Opcode op, 536234353Sdim const SymExpr *rhs, QualType t); 537234353Sdim 538218887Sdim const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 539218887Sdim const SymExpr *rhs, QualType t); 540218887Sdim 541218887Sdim QualType getType(const SymExpr *SE) const { 542218887Sdim return SE->getType(Ctx); 543218887Sdim } 544218887Sdim 545226633Sdim /// \brief Add artificial symbol dependency. 546226633Sdim /// 547226633Sdim /// The dependent symbol should stay alive as long as the primary is alive. 548226633Sdim void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); 549226633Sdim 550226633Sdim const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); 551226633Sdim 552218887Sdim ASTContext &getContext() { return Ctx; } 553218887Sdim BasicValueFactory &getBasicVals() { return BV; } 554218887Sdim}; 555218887Sdim 556218887Sdimclass SymbolReaper { 557226633Sdim enum SymbolStatus { 558226633Sdim NotProcessed, 559226633Sdim HaveMarkedDependents 560226633Sdim }; 561218887Sdim 562226633Sdim typedef llvm::DenseSet<SymbolRef> SymbolSetTy; 563226633Sdim typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; 564226633Sdim typedef llvm::DenseSet<const MemRegion *> RegionSetTy; 565226633Sdim 566226633Sdim SymbolMapTy TheLiving; 567226633Sdim SymbolSetTy MetadataInUse; 568226633Sdim SymbolSetTy TheDead; 569226633Sdim 570226633Sdim RegionSetTy RegionRoots; 571226633Sdim 572218887Sdim const LocationContext *LCtx; 573218887Sdim const Stmt *Loc; 574218887Sdim SymbolManager& SymMgr; 575226633Sdim StoreRef reapedStore; 576226633Sdim llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 577218887Sdim 578218887Sdimpublic: 579226633Sdim SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr, 580226633Sdim StoreManager &storeMgr) 581226633Sdim : LCtx(ctx), Loc(s), SymMgr(symmgr), reapedStore(0, storeMgr) {} 582218887Sdim 583218887Sdim ~SymbolReaper() {} 584218887Sdim 585218887Sdim const LocationContext *getLocationContext() const { return LCtx; } 586218887Sdim const Stmt *getCurrentStatement() const { return Loc; } 587218887Sdim 588218887Sdim bool isLive(SymbolRef sym); 589226633Sdim bool isLiveRegion(const MemRegion *region); 590234353Sdim bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 591226633Sdim bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 592218887Sdim 593226633Sdim /// \brief Unconditionally marks a symbol as live. 594226633Sdim /// 595226633Sdim /// This should never be 596226633Sdim /// used by checkers, only by the state infrastructure such as the store and 597226633Sdim /// environment. Checkers should instead use metadata symbols and markInUse. 598218887Sdim void markLive(SymbolRef sym); 599218887Sdim 600226633Sdim /// \brief Marks a symbol as important to a checker. 601226633Sdim /// 602226633Sdim /// For metadata symbols, 603226633Sdim /// this will keep the symbol alive as long as its associated region is also 604226633Sdim /// live. For other symbols, this has no effect; checkers are not permitted 605226633Sdim /// to influence the life of other symbols. This should be used before any 606226633Sdim /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 607218887Sdim void markInUse(SymbolRef sym); 608218887Sdim 609226633Sdim /// \brief If a symbol is known to be live, marks the symbol as live. 610226633Sdim /// 611226633Sdim /// Otherwise, if the symbol cannot be proven live, it is marked as dead. 612226633Sdim /// Returns true if the symbol is dead, false if live. 613218887Sdim bool maybeDead(SymbolRef sym); 614218887Sdim 615226633Sdim typedef SymbolSetTy::const_iterator dead_iterator; 616218887Sdim dead_iterator dead_begin() const { return TheDead.begin(); } 617218887Sdim dead_iterator dead_end() const { return TheDead.end(); } 618218887Sdim 619218887Sdim bool hasDeadSymbols() const { 620218887Sdim return !TheDead.empty(); 621218887Sdim } 622226633Sdim 623226633Sdim typedef RegionSetTy::const_iterator region_iterator; 624226633Sdim region_iterator region_begin() const { return RegionRoots.begin(); } 625226633Sdim region_iterator region_end() const { return RegionRoots.end(); } 626218887Sdim 627226633Sdim /// \brief Returns whether or not a symbol has been confirmed dead. 628226633Sdim /// 629226633Sdim /// This should only be called once all marking of dead symbols has completed. 630226633Sdim /// (For checkers, this means only in the evalDeadSymbols callback.) 631218887Sdim bool isDead(SymbolRef sym) const { 632218887Sdim return TheDead.count(sym); 633218887Sdim } 634226633Sdim 635226633Sdim void markLive(const MemRegion *region); 636226633Sdim 637226633Sdim /// \brief Set to the value of the symbolic store after 638226633Sdim /// StoreManager::removeDeadBindings has been called. 639226633Sdim void setReapedStore(StoreRef st) { reapedStore = st; } 640226633Sdim 641226633Sdimprivate: 642226633Sdim /// Mark the symbols dependent on the input symbol as live. 643226633Sdim void markDependentsLive(SymbolRef sym); 644218887Sdim}; 645218887Sdim 646218887Sdimclass SymbolVisitor { 647218887Sdimpublic: 648226633Sdim /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. 649226633Sdim /// 650226633Sdim /// The method returns \c true if symbols should continue be scanned and \c 651226633Sdim /// false otherwise. 652218887Sdim virtual bool VisitSymbol(SymbolRef sym) = 0; 653226633Sdim virtual bool VisitMemRegion(const MemRegion *region) { return true; } 654218887Sdim virtual ~SymbolVisitor(); 655218887Sdim}; 656218887Sdim 657218887Sdim} // end GR namespace 658218887Sdim 659218887Sdim} // end clang namespace 660218887Sdim 661218887Sdimnamespace llvm { 662226633Sdimstatic inline raw_ostream &operator<<(raw_ostream &os, 663234353Sdim const clang::ento::SymExpr *SE) { 664218887Sdim SE->dumpToStream(os); 665218887Sdim return os; 666218887Sdim} 667218887Sdim} // end llvm namespace 668218887Sdim#endif 669