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" 23249423Sdim#include "llvm/ADT/DenseMap.h" 24249423Sdim#include "llvm/ADT/DenseSet.h" 25249423Sdim#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; 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, 52251662Sdim SymIntKind, IntSymKind, SymSymKind, 53251662Sdim BEGIN_BINARYSYMEXPRS = SymIntKind, 54251662Sdim END_BINARYSYMEXPRS = SymSymKind, 55251662Sdim 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 67234353Sdim virtual void dump() const; 68218887Sdim 69234353Sdim virtual void dumpToStream(raw_ostream &os) const {} 70218887Sdim 71243830Sdim virtual QualType getType() const = 0; 72218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; 73218887Sdim 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(); } 97239462Sdim 98239462Sdim unsigned computeComplexity() const; 99218887Sdim}; 100218887Sdim 101234353Sdimtypedef const SymExpr* SymbolRef; 102249423Sdimtypedef SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy; 103234353Sdim 104218887Sdimtypedef unsigned SymbolID; 105234353Sdim/// \brief A symbol representing data which can be stored in a memory location 106234353Sdim/// (region). 107218887Sdimclass SymbolData : public SymExpr { 108234353Sdim 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. 120226633Sdim static inline bool classof(const SymExpr *SE) { 121218887Sdim Kind k = SE->getKind(); 122226633Sdim return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; 123218887Sdim } 124218887Sdim}; 125218887Sdim 126234353Sdim///\brief A symbol representing the value stored at a MemRegion. 127218887Sdimclass SymbolRegionValue : public SymbolData { 128226633Sdim const TypedValueRegion *R; 129218887Sdim 130218887Sdimpublic: 131226633Sdim SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 132218887Sdim : SymbolData(RegionValueKind, sym), R(r) {} 133218887Sdim 134226633Sdim const TypedValueRegion* getRegion() const { return R; } 135218887Sdim 136226633Sdim 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 145234353Sdim virtual void dumpToStream(raw_ostream &os) const; 146218887Sdim 147243830Sdim QualType getType() const; 148218887Sdim 149218887Sdim // Implement isa<T> support. 150226633Sdim static inline bool classof(const SymExpr *SE) { 151218887Sdim return SE->getKind() == RegionValueKind; 152218887Sdim } 153218887Sdim}; 154218887Sdim 155234353Sdim/// A symbol representing the result of an expression in the case when we do 156234353Sdim/// not know anything about what the expression is. 157218887Sdimclass SymbolConjured : public SymbolData { 158226633Sdim const Stmt *S; 159218887Sdim QualType T; 160218887Sdim unsigned Count; 161234353Sdim const LocationContext *LCtx; 162226633Sdim const void *SymbolTag; 163218887Sdim 164218887Sdimpublic: 165234353Sdim SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 166234353Sdim QualType t, unsigned count, 167226633Sdim const void *symbolTag) 168218887Sdim : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), 169234353Sdim LCtx(lctx), 170218887Sdim SymbolTag(symbolTag) {} 171218887Sdim 172226633Sdim const Stmt *getStmt() const { return S; } 173218887Sdim unsigned getCount() const { return Count; } 174226633Sdim const void *getTag() const { return SymbolTag; } 175218887Sdim 176243830Sdim QualType getType() const; 177218887Sdim 178234353Sdim virtual void dumpToStream(raw_ostream &os) const; 179218887Sdim 180226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 181234353Sdim QualType T, unsigned Count, const LocationContext *LCtx, 182234353Sdim const void *SymbolTag) { 183218887Sdim profile.AddInteger((unsigned) ConjuredKind); 184218887Sdim profile.AddPointer(S); 185234353Sdim profile.AddPointer(LCtx); 186218887Sdim profile.Add(T); 187218887Sdim profile.AddInteger(Count); 188218887Sdim profile.AddPointer(SymbolTag); 189218887Sdim } 190218887Sdim 191218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 192234353Sdim Profile(profile, S, T, Count, LCtx, SymbolTag); 193218887Sdim } 194218887Sdim 195218887Sdim // Implement isa<T> support. 196226633Sdim static inline bool classof(const SymExpr *SE) { 197218887Sdim return SE->getKind() == ConjuredKind; 198218887Sdim } 199218887Sdim}; 200218887Sdim 201226633Sdim/// A symbol representing the value of a MemRegion whose parent region has 202226633Sdim/// symbolic value. 203218887Sdimclass SymbolDerived : public SymbolData { 204218887Sdim SymbolRef parentSymbol; 205226633Sdim const TypedValueRegion *R; 206218887Sdim 207218887Sdimpublic: 208226633Sdim SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 209218887Sdim : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} 210218887Sdim 211218887Sdim SymbolRef getParentSymbol() const { return parentSymbol; } 212226633Sdim const TypedValueRegion *getRegion() const { return R; } 213218887Sdim 214243830Sdim QualType getType() const; 215218887Sdim 216234353Sdim virtual void dumpToStream(raw_ostream &os) const; 217218887Sdim 218218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 219226633Sdim 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. 230226633Sdim 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 247243830Sdim QualType getType() const; 248218887Sdim 249234353Sdim 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. 261226633Sdim 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; 272226633Sdim const Stmt *S; 273218887Sdim QualType T; 274218887Sdim unsigned Count; 275226633Sdim const void *Tag; 276218887Sdimpublic: 277226633Sdim SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 278226633Sdim 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; } 282226633Sdim const Stmt *getStmt() const { return S; } 283218887Sdim unsigned getCount() const { return Count; } 284226633Sdim const void *getTag() const { return Tag; } 285218887Sdim 286243830Sdim QualType getType() const; 287218887Sdim 288234353Sdim 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. 306226633Sdim static inline bool classof(const SymExpr *SE) { 307218887Sdim return SE->getKind() == MetadataKind; 308218887Sdim } 309218887Sdim}; 310218887Sdim 311234353Sdim/// \brief Represents a cast expression. 312234353Sdimclass SymbolCast : public SymExpr { 313234353Sdim const SymExpr *Operand; 314234353Sdim /// Type of the operand. 315234353Sdim QualType FromTy; 316234353Sdim /// The type of the result. 317234353Sdim QualType ToTy; 318234353Sdim 319234353Sdimpublic: 320234353Sdim SymbolCast(const SymExpr *In, QualType From, QualType To) : 321234353Sdim SymExpr(CastSymbolKind), Operand(In), FromTy(From), ToTy(To) { } 322234353Sdim 323243830Sdim QualType getType() const { return ToTy; } 324234353Sdim 325234353Sdim const SymExpr *getOperand() const { return Operand; } 326234353Sdim 327234353Sdim virtual void dumpToStream(raw_ostream &os) const; 328234353Sdim 329234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, 330234353Sdim const SymExpr *In, QualType From, QualType To) { 331234353Sdim ID.AddInteger((unsigned) CastSymbolKind); 332234353Sdim ID.AddPointer(In); 333234353Sdim ID.Add(From); 334234353Sdim ID.Add(To); 335234353Sdim } 336234353Sdim 337234353Sdim void Profile(llvm::FoldingSetNodeID& ID) { 338234353Sdim Profile(ID, Operand, FromTy, ToTy); 339234353Sdim } 340234353Sdim 341234353Sdim // Implement isa<T> support. 342234353Sdim static inline bool classof(const SymExpr *SE) { 343234353Sdim return SE->getKind() == CastSymbolKind; 344234353Sdim } 345234353Sdim}; 346234353Sdim 347251662Sdim/// \brief Represents a symbolic expression involving a binary operator 348251662Sdimclass BinarySymExpr : public SymExpr { 349218887Sdim BinaryOperator::Opcode Op; 350218887Sdim QualType T; 351218887Sdim 352251662Sdimprotected: 353251662Sdim BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) 354251662Sdim : SymExpr(k), Op(op), T(t) {} 355251662Sdim 356218887Sdimpublic: 357218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 358218887Sdim // generation of virtual functions. 359243830Sdim QualType getType() const { return T; } 360218887Sdim 361218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 362218887Sdim 363251662Sdim // Implement isa<T> support. 364251662Sdim static inline bool classof(const SymExpr *SE) { 365251662Sdim Kind k = SE->getKind(); 366251662Sdim return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; 367251662Sdim } 368251662Sdim}; 369251662Sdim 370251662Sdim/// \brief Represents a symbolic expression like 'x' + 3. 371251662Sdimclass SymIntExpr : public BinarySymExpr { 372251662Sdim const SymExpr *LHS; 373251662Sdim const llvm::APSInt& RHS; 374251662Sdim 375251662Sdimpublic: 376251662Sdim SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 377251662Sdim const llvm::APSInt& rhs, QualType t) 378251662Sdim : BinarySymExpr(SymIntKind, op, t), LHS(lhs), RHS(rhs) {} 379251662Sdim 380234353Sdim 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) { 396251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 397218887Sdim } 398218887Sdim 399218887Sdim // Implement isa<T> support. 400226633Sdim static inline bool classof(const SymExpr *SE) { 401218887Sdim return SE->getKind() == SymIntKind; 402218887Sdim } 403218887Sdim}; 404218887Sdim 405251662Sdim/// \brief Represents a symbolic expression like 3 - 'x'. 406251662Sdimclass IntSymExpr : public BinarySymExpr { 407234353Sdim const llvm::APSInt& LHS; 408234353Sdim const SymExpr *RHS; 409234353Sdim 410234353Sdimpublic: 411234353Sdim IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, 412234353Sdim const SymExpr *rhs, QualType t) 413251662Sdim : BinarySymExpr(IntSymKind, op, t), LHS(lhs), RHS(rhs) {} 414234353Sdim 415234353Sdim virtual void dumpToStream(raw_ostream &os) const; 416234353Sdim 417234353Sdim const SymExpr *getRHS() const { return RHS; } 418234353Sdim const llvm::APSInt &getLHS() const { return LHS; } 419234353Sdim 420234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 421234353Sdim BinaryOperator::Opcode op, const SymExpr *rhs, 422234353Sdim QualType t) { 423234353Sdim ID.AddInteger((unsigned) IntSymKind); 424234353Sdim ID.AddPointer(&lhs); 425234353Sdim ID.AddInteger(op); 426234353Sdim ID.AddPointer(rhs); 427234353Sdim ID.Add(t); 428234353Sdim } 429234353Sdim 430234353Sdim void Profile(llvm::FoldingSetNodeID& ID) { 431251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 432234353Sdim } 433234353Sdim 434234353Sdim // Implement isa<T> support. 435234353Sdim static inline bool classof(const SymExpr *SE) { 436234353Sdim return SE->getKind() == IntSymKind; 437234353Sdim } 438234353Sdim}; 439234353Sdim 440251662Sdim/// \brief Represents a symbolic expression like 'x' + 'y'. 441251662Sdimclass 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) 448251662Sdim : BinarySymExpr(SymSymKind, op, t), LHS(lhs), RHS(rhs) {} 449218887Sdim 450218887Sdim const SymExpr *getLHS() const { return LHS; } 451218887Sdim const SymExpr *getRHS() const { return RHS; } 452218887Sdim 453234353Sdim 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) { 465251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 466218887Sdim } 467218887Sdim 468218887Sdim // Implement isa<T> support. 469226633Sdim static inline bool classof(const SymExpr *SE) { 470218887Sdim return SE->getKind() == SymSymKind; 471218887Sdim } 472218887Sdim}; 473218887Sdim 474218887Sdimclass SymbolManager { 475218887Sdim typedef llvm::FoldingSet<SymExpr> DataSetTy; 476226633Sdim typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; 477226633Sdim 478218887Sdim DataSetTy DataSet; 479226633Sdim /// Stores the extra dependencies between symbols: the data should be kept 480226633Sdim /// alive as long as the key is live. 481226633Sdim SymbolDependTy SymbolDependencies; 482218887Sdim unsigned SymbolCounter; 483218887Sdim llvm::BumpPtrAllocator& BPAlloc; 484218887Sdim BasicValueFactory &BV; 485226633Sdim ASTContext &Ctx; 486218887Sdim 487218887Sdimpublic: 488226633Sdim SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 489218887Sdim llvm::BumpPtrAllocator& bpalloc) 490226633Sdim : SymbolDependencies(16), SymbolCounter(0), 491226633Sdim BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 492218887Sdim 493218887Sdim ~SymbolManager(); 494218887Sdim 495218887Sdim static bool canSymbolicate(QualType T); 496218887Sdim 497226633Sdim /// \brief Make a unique symbol for MemRegion R according to its kind. 498226633Sdim const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 499218887Sdim 500243830Sdim const SymbolConjured* conjureSymbol(const Stmt *E, 501243830Sdim const LocationContext *LCtx, 502243830Sdim QualType T, 503243830Sdim unsigned VisitCount, 504243830Sdim const void *SymbolTag = 0); 505218887Sdim 506243830Sdim const SymbolConjured* conjureSymbol(const Expr *E, 507243830Sdim const LocationContext *LCtx, 508243830Sdim unsigned VisitCount, 509243830Sdim const void *SymbolTag = 0) { 510243830Sdim return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag); 511218887Sdim } 512218887Sdim 513218887Sdim const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 514226633Sdim const TypedValueRegion *R); 515218887Sdim 516218887Sdim const SymbolExtent *getExtentSymbol(const SubRegion *R); 517218887Sdim 518226633Sdim /// \brief Creates a metadata symbol associated with a specific region. 519226633Sdim /// 520226633Sdim /// VisitCount can be used to differentiate regions corresponding to 521226633Sdim /// different loop iterations, thus, making the symbol path-dependent. 522226633Sdim const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt *S, 523218887Sdim QualType T, unsigned VisitCount, 524226633Sdim const void *SymbolTag = 0); 525218887Sdim 526234353Sdim const SymbolCast* getCastSymbol(const SymExpr *Operand, 527234353Sdim QualType From, QualType To); 528234353Sdim 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 537234353Sdim const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, 538234353Sdim BinaryOperator::Opcode op, 539234353Sdim const SymExpr *rhs, QualType t); 540234353Sdim 541218887Sdim const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 542218887Sdim const SymExpr *rhs, QualType t); 543218887Sdim 544218887Sdim QualType getType(const SymExpr *SE) const { 545243830Sdim return SE->getType(); 546218887Sdim } 547218887Sdim 548226633Sdim /// \brief Add artificial symbol dependency. 549226633Sdim /// 550226633Sdim /// The dependent symbol should stay alive as long as the primary is alive. 551226633Sdim void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); 552226633Sdim 553226633Sdim const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); 554226633Sdim 555218887Sdim ASTContext &getContext() { return Ctx; } 556218887Sdim BasicValueFactory &getBasicVals() { return BV; } 557218887Sdim}; 558218887Sdim 559239462Sdim/// \brief A class responsible for cleaning up unused symbols. 560218887Sdimclass SymbolReaper { 561226633Sdim enum SymbolStatus { 562226633Sdim NotProcessed, 563226633Sdim HaveMarkedDependents 564226633Sdim }; 565218887Sdim 566226633Sdim typedef llvm::DenseSet<SymbolRef> SymbolSetTy; 567226633Sdim typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; 568226633Sdim typedef llvm::DenseSet<const MemRegion *> RegionSetTy; 569226633Sdim 570226633Sdim SymbolMapTy TheLiving; 571226633Sdim SymbolSetTy MetadataInUse; 572226633Sdim SymbolSetTy TheDead; 573226633Sdim 574226633Sdim RegionSetTy RegionRoots; 575226633Sdim 576239462Sdim const StackFrameContext *LCtx; 577218887Sdim const Stmt *Loc; 578218887Sdim SymbolManager& SymMgr; 579226633Sdim StoreRef reapedStore; 580226633Sdim llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 581218887Sdim 582218887Sdimpublic: 583239462Sdim /// \brief Construct a reaper object, which removes everything which is not 584239462Sdim /// live before we execute statement s in the given location context. 585239462Sdim /// 586239462Sdim /// If the statement is NULL, everything is this and parent contexts is 587239462Sdim /// considered live. 588243830Sdim /// If the stack frame context is NULL, everything on stack is considered 589243830Sdim /// dead. 590243830Sdim SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr, 591226633Sdim StoreManager &storeMgr) 592243830Sdim : LCtx(Ctx), Loc(s), SymMgr(symmgr), 593239462Sdim reapedStore(0, storeMgr) {} 594218887Sdim 595218887Sdim ~SymbolReaper() {} 596218887Sdim 597218887Sdim const LocationContext *getLocationContext() const { return LCtx; } 598218887Sdim 599218887Sdim bool isLive(SymbolRef sym); 600226633Sdim bool isLiveRegion(const MemRegion *region); 601234353Sdim bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 602226633Sdim bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 603218887Sdim 604226633Sdim /// \brief Unconditionally marks a symbol as live. 605226633Sdim /// 606226633Sdim /// This should never be 607226633Sdim /// used by checkers, only by the state infrastructure such as the store and 608226633Sdim /// environment. Checkers should instead use metadata symbols and markInUse. 609218887Sdim void markLive(SymbolRef sym); 610218887Sdim 611226633Sdim /// \brief Marks a symbol as important to a checker. 612226633Sdim /// 613226633Sdim /// For metadata symbols, 614226633Sdim /// this will keep the symbol alive as long as its associated region is also 615226633Sdim /// live. For other symbols, this has no effect; checkers are not permitted 616226633Sdim /// to influence the life of other symbols. This should be used before any 617226633Sdim /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 618218887Sdim void markInUse(SymbolRef sym); 619218887Sdim 620226633Sdim /// \brief If a symbol is known to be live, marks the symbol as live. 621226633Sdim /// 622226633Sdim /// Otherwise, if the symbol cannot be proven live, it is marked as dead. 623226633Sdim /// Returns true if the symbol is dead, false if live. 624218887Sdim bool maybeDead(SymbolRef sym); 625218887Sdim 626226633Sdim 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 } 633226633Sdim 634226633Sdim typedef RegionSetTy::const_iterator region_iterator; 635226633Sdim region_iterator region_begin() const { return RegionRoots.begin(); } 636226633Sdim region_iterator region_end() const { return RegionRoots.end(); } 637218887Sdim 638226633Sdim /// \brief Returns whether or not a symbol has been confirmed dead. 639226633Sdim /// 640226633Sdim /// This should only be called once all marking of dead symbols has completed. 641226633Sdim /// (For checkers, this means only in the evalDeadSymbols callback.) 642218887Sdim bool isDead(SymbolRef sym) const { 643218887Sdim return TheDead.count(sym); 644218887Sdim } 645226633Sdim 646226633Sdim void markLive(const MemRegion *region); 647226633Sdim 648226633Sdim /// \brief Set to the value of the symbolic store after 649226633Sdim /// StoreManager::removeDeadBindings has been called. 650226633Sdim void setReapedStore(StoreRef st) { reapedStore = st; } 651226633Sdim 652226633Sdimprivate: 653226633Sdim /// Mark the symbols dependent on the input symbol as live. 654226633Sdim void markDependentsLive(SymbolRef sym); 655218887Sdim}; 656218887Sdim 657218887Sdimclass SymbolVisitor { 658218887Sdimpublic: 659226633Sdim /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. 660226633Sdim /// 661226633Sdim /// The method returns \c true if symbols should continue be scanned and \c 662226633Sdim /// false otherwise. 663218887Sdim virtual bool VisitSymbol(SymbolRef sym) = 0; 664226633Sdim 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 { 673226633Sdimstatic inline raw_ostream &operator<<(raw_ostream &os, 674234353Sdim const clang::ento::SymExpr *SE) { 675218887Sdim SE->dumpToStream(os); 676218887Sdim return os; 677218887Sdim} 678218887Sdim} // end llvm namespace 679218887Sdim#endif 680