SymbolManager.h revision 218887
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" 21218887Sdim#include "llvm/Support/DataTypes.h" 22218887Sdim#include "llvm/ADT/FoldingSet.h" 23218887Sdim#include "llvm/ADT/DenseSet.h" 24218887Sdim 25218887Sdimnamespace llvm { 26218887Sdimclass BumpPtrAllocator; 27218887Sdimclass raw_ostream; 28218887Sdim} 29218887Sdim 30218887Sdimnamespace clang { 31218887Sdim class ASTContext; 32218887Sdim class StackFrameContext; 33218887Sdim 34218887Sdimnamespace ento { 35218887Sdim class BasicValueFactory; 36218887Sdim class MemRegion; 37218887Sdim class SubRegion; 38218887Sdim class TypedRegion; 39218887Sdim class VarRegion; 40218887Sdim 41218887Sdimclass SymExpr : public llvm::FoldingSetNode { 42218887Sdimpublic: 43218887Sdim enum Kind { BEGIN_SYMBOLS, 44218887Sdim RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, 45218887Sdim MetadataKind, 46218887Sdim END_SYMBOLS, 47218887Sdim SymIntKind, SymSymKind }; 48218887Sdimprivate: 49218887Sdim Kind K; 50218887Sdim 51218887Sdimprotected: 52218887Sdim SymExpr(Kind k) : K(k) {} 53218887Sdim 54218887Sdimpublic: 55218887Sdim virtual ~SymExpr() {} 56218887Sdim 57218887Sdim Kind getKind() const { return K; } 58218887Sdim 59218887Sdim void dump() const; 60218887Sdim 61218887Sdim virtual void dumpToStream(llvm::raw_ostream &os) const = 0; 62218887Sdim 63218887Sdim virtual QualType getType(ASTContext&) const = 0; 64218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; 65218887Sdim 66218887Sdim // Implement isa<T> support. 67218887Sdim static inline bool classof(const SymExpr*) { return true; } 68218887Sdim}; 69218887Sdim 70218887Sdimtypedef unsigned SymbolID; 71218887Sdim 72218887Sdimclass SymbolData : public SymExpr { 73218887Sdimprivate: 74218887Sdim const SymbolID Sym; 75218887Sdim 76218887Sdimprotected: 77218887Sdim SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {} 78218887Sdim 79218887Sdimpublic: 80218887Sdim virtual ~SymbolData() {} 81218887Sdim 82218887Sdim SymbolID getSymbolID() const { return Sym; } 83218887Sdim 84218887Sdim // Implement isa<T> support. 85218887Sdim static inline bool classof(const SymExpr* SE) { 86218887Sdim Kind k = SE->getKind(); 87218887Sdim return k > BEGIN_SYMBOLS && k < END_SYMBOLS; 88218887Sdim } 89218887Sdim}; 90218887Sdim 91218887Sdimtypedef const SymbolData* SymbolRef; 92218887Sdim 93218887Sdim// A symbol representing the value of a MemRegion. 94218887Sdimclass SymbolRegionValue : public SymbolData { 95218887Sdim const TypedRegion *R; 96218887Sdim 97218887Sdimpublic: 98218887Sdim SymbolRegionValue(SymbolID sym, const TypedRegion *r) 99218887Sdim : SymbolData(RegionValueKind, sym), R(r) {} 100218887Sdim 101218887Sdim const TypedRegion* getRegion() const { return R; } 102218887Sdim 103218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const TypedRegion* R) { 104218887Sdim profile.AddInteger((unsigned) RegionValueKind); 105218887Sdim profile.AddPointer(R); 106218887Sdim } 107218887Sdim 108218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 109218887Sdim Profile(profile, R); 110218887Sdim } 111218887Sdim 112218887Sdim void dumpToStream(llvm::raw_ostream &os) const; 113218887Sdim 114218887Sdim QualType getType(ASTContext&) const; 115218887Sdim 116218887Sdim // Implement isa<T> support. 117218887Sdim static inline bool classof(const SymExpr* SE) { 118218887Sdim return SE->getKind() == RegionValueKind; 119218887Sdim } 120218887Sdim}; 121218887Sdim 122218887Sdim// A symbol representing the result of an expression. 123218887Sdimclass SymbolConjured : public SymbolData { 124218887Sdim const Stmt* S; 125218887Sdim QualType T; 126218887Sdim unsigned Count; 127218887Sdim const void* SymbolTag; 128218887Sdim 129218887Sdimpublic: 130218887Sdim SymbolConjured(SymbolID sym, const Stmt* s, QualType t, unsigned count, 131218887Sdim const void* symbolTag) 132218887Sdim : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), 133218887Sdim SymbolTag(symbolTag) {} 134218887Sdim 135218887Sdim const Stmt* getStmt() const { return S; } 136218887Sdim unsigned getCount() const { return Count; } 137218887Sdim const void* getTag() const { return SymbolTag; } 138218887Sdim 139218887Sdim QualType getType(ASTContext&) const; 140218887Sdim 141218887Sdim void dumpToStream(llvm::raw_ostream &os) const; 142218887Sdim 143218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const Stmt* S, 144218887Sdim QualType T, unsigned Count, const void* SymbolTag) { 145218887Sdim profile.AddInteger((unsigned) ConjuredKind); 146218887Sdim profile.AddPointer(S); 147218887Sdim profile.Add(T); 148218887Sdim profile.AddInteger(Count); 149218887Sdim profile.AddPointer(SymbolTag); 150218887Sdim } 151218887Sdim 152218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 153218887Sdim Profile(profile, S, T, Count, SymbolTag); 154218887Sdim } 155218887Sdim 156218887Sdim // Implement isa<T> support. 157218887Sdim static inline bool classof(const SymExpr* SE) { 158218887Sdim return SE->getKind() == ConjuredKind; 159218887Sdim } 160218887Sdim}; 161218887Sdim 162218887Sdim// A symbol representing the value of a MemRegion whose parent region has 163218887Sdim// symbolic value. 164218887Sdimclass SymbolDerived : public SymbolData { 165218887Sdim SymbolRef parentSymbol; 166218887Sdim const TypedRegion *R; 167218887Sdim 168218887Sdimpublic: 169218887Sdim SymbolDerived(SymbolID sym, SymbolRef parent, const TypedRegion *r) 170218887Sdim : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} 171218887Sdim 172218887Sdim SymbolRef getParentSymbol() const { return parentSymbol; } 173218887Sdim const TypedRegion *getRegion() const { return R; } 174218887Sdim 175218887Sdim QualType getType(ASTContext&) const; 176218887Sdim 177218887Sdim void dumpToStream(llvm::raw_ostream &os) const; 178218887Sdim 179218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 180218887Sdim const TypedRegion *r) { 181218887Sdim profile.AddInteger((unsigned) DerivedKind); 182218887Sdim profile.AddPointer(r); 183218887Sdim profile.AddPointer(parent); 184218887Sdim } 185218887Sdim 186218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 187218887Sdim Profile(profile, parentSymbol, R); 188218887Sdim } 189218887Sdim 190218887Sdim // Implement isa<T> support. 191218887Sdim static inline bool classof(const SymExpr* SE) { 192218887Sdim return SE->getKind() == DerivedKind; 193218887Sdim } 194218887Sdim}; 195218887Sdim 196218887Sdim/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 197218887Sdim/// Clients should not ask the SymbolManager for a region's extent. Always use 198218887Sdim/// SubRegion::getExtent instead -- the value returned may not be a symbol. 199218887Sdimclass SymbolExtent : public SymbolData { 200218887Sdim const SubRegion *R; 201218887Sdim 202218887Sdimpublic: 203218887Sdim SymbolExtent(SymbolID sym, const SubRegion *r) 204218887Sdim : SymbolData(ExtentKind, sym), R(r) {} 205218887Sdim 206218887Sdim const SubRegion *getRegion() const { return R; } 207218887Sdim 208218887Sdim QualType getType(ASTContext&) const; 209218887Sdim 210218887Sdim void dumpToStream(llvm::raw_ostream &os) const; 211218887Sdim 212218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 213218887Sdim profile.AddInteger((unsigned) ExtentKind); 214218887Sdim profile.AddPointer(R); 215218887Sdim } 216218887Sdim 217218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 218218887Sdim Profile(profile, R); 219218887Sdim } 220218887Sdim 221218887Sdim // Implement isa<T> support. 222218887Sdim static inline bool classof(const SymExpr* SE) { 223218887Sdim return SE->getKind() == ExtentKind; 224218887Sdim } 225218887Sdim}; 226218887Sdim 227218887Sdim/// SymbolMetadata - Represents path-dependent metadata about a specific region. 228218887Sdim/// Metadata symbols remain live as long as they are marked as in use before 229218887Sdim/// dead-symbol sweeping AND their associated regions are still alive. 230218887Sdim/// Intended for use by checkers. 231218887Sdimclass SymbolMetadata : public SymbolData { 232218887Sdim const MemRegion* R; 233218887Sdim const Stmt* S; 234218887Sdim QualType T; 235218887Sdim unsigned Count; 236218887Sdim const void* Tag; 237218887Sdimpublic: 238218887Sdim SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt* s, QualType t, 239218887Sdim unsigned count, const void* tag) 240218887Sdim : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} 241218887Sdim 242218887Sdim const MemRegion *getRegion() const { return R; } 243218887Sdim const Stmt* getStmt() const { return S; } 244218887Sdim unsigned getCount() const { return Count; } 245218887Sdim const void* getTag() const { return Tag; } 246218887Sdim 247218887Sdim QualType getType(ASTContext&) const; 248218887Sdim 249218887Sdim void dumpToStream(llvm::raw_ostream &os) const; 250218887Sdim 251218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 252218887Sdim const Stmt *S, QualType T, unsigned Count, 253218887Sdim const void *Tag) { 254218887Sdim profile.AddInteger((unsigned) MetadataKind); 255218887Sdim profile.AddPointer(R); 256218887Sdim profile.AddPointer(S); 257218887Sdim profile.Add(T); 258218887Sdim profile.AddInteger(Count); 259218887Sdim profile.AddPointer(Tag); 260218887Sdim } 261218887Sdim 262218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) { 263218887Sdim Profile(profile, R, S, T, Count, Tag); 264218887Sdim } 265218887Sdim 266218887Sdim // Implement isa<T> support. 267218887Sdim static inline bool classof(const SymExpr* SE) { 268218887Sdim return SE->getKind() == MetadataKind; 269218887Sdim } 270218887Sdim}; 271218887Sdim 272218887Sdim// SymIntExpr - Represents symbolic expression like 'x' + 3. 273218887Sdimclass SymIntExpr : public SymExpr { 274218887Sdim const SymExpr *LHS; 275218887Sdim BinaryOperator::Opcode Op; 276218887Sdim const llvm::APSInt& RHS; 277218887Sdim QualType T; 278218887Sdim 279218887Sdimpublic: 280218887Sdim SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 281218887Sdim const llvm::APSInt& rhs, QualType t) 282218887Sdim : SymExpr(SymIntKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} 283218887Sdim 284218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 285218887Sdim // generation of virtual functions. 286218887Sdim QualType getType(ASTContext& C) const { return T; } 287218887Sdim 288218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 289218887Sdim 290218887Sdim void dumpToStream(llvm::raw_ostream &os) const; 291218887Sdim 292218887Sdim const SymExpr *getLHS() const { return LHS; } 293218887Sdim const llvm::APSInt &getRHS() const { return RHS; } 294218887Sdim 295218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 296218887Sdim BinaryOperator::Opcode op, const llvm::APSInt& rhs, 297218887Sdim QualType t) { 298218887Sdim ID.AddInteger((unsigned) SymIntKind); 299218887Sdim ID.AddPointer(lhs); 300218887Sdim ID.AddInteger(op); 301218887Sdim ID.AddPointer(&rhs); 302218887Sdim ID.Add(t); 303218887Sdim } 304218887Sdim 305218887Sdim void Profile(llvm::FoldingSetNodeID& ID) { 306218887Sdim Profile(ID, LHS, Op, RHS, T); 307218887Sdim } 308218887Sdim 309218887Sdim // Implement isa<T> support. 310218887Sdim static inline bool classof(const SymExpr* SE) { 311218887Sdim return SE->getKind() == SymIntKind; 312218887Sdim } 313218887Sdim}; 314218887Sdim 315218887Sdim// SymSymExpr - Represents symbolic expression like 'x' + 'y'. 316218887Sdimclass SymSymExpr : public SymExpr { 317218887Sdim const SymExpr *LHS; 318218887Sdim BinaryOperator::Opcode Op; 319218887Sdim const SymExpr *RHS; 320218887Sdim QualType T; 321218887Sdim 322218887Sdimpublic: 323218887Sdim SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 324218887Sdim QualType t) 325218887Sdim : SymExpr(SymSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {} 326218887Sdim 327218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 328218887Sdim const SymExpr *getLHS() const { return LHS; } 329218887Sdim const SymExpr *getRHS() const { return RHS; } 330218887Sdim 331218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 332218887Sdim // generation of virtual functions. 333218887Sdim QualType getType(ASTContext& C) const { return T; } 334218887Sdim 335218887Sdim void dumpToStream(llvm::raw_ostream &os) const; 336218887Sdim 337218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 338218887Sdim BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 339218887Sdim ID.AddInteger((unsigned) SymSymKind); 340218887Sdim ID.AddPointer(lhs); 341218887Sdim ID.AddInteger(op); 342218887Sdim ID.AddPointer(rhs); 343218887Sdim ID.Add(t); 344218887Sdim } 345218887Sdim 346218887Sdim void Profile(llvm::FoldingSetNodeID& ID) { 347218887Sdim Profile(ID, LHS, Op, RHS, T); 348218887Sdim } 349218887Sdim 350218887Sdim // Implement isa<T> support. 351218887Sdim static inline bool classof(const SymExpr* SE) { 352218887Sdim return SE->getKind() == SymSymKind; 353218887Sdim } 354218887Sdim}; 355218887Sdim 356218887Sdimclass SymbolManager { 357218887Sdim typedef llvm::FoldingSet<SymExpr> DataSetTy; 358218887Sdim DataSetTy DataSet; 359218887Sdim unsigned SymbolCounter; 360218887Sdim llvm::BumpPtrAllocator& BPAlloc; 361218887Sdim BasicValueFactory &BV; 362218887Sdim ASTContext& Ctx; 363218887Sdim 364218887Sdimpublic: 365218887Sdim SymbolManager(ASTContext& ctx, BasicValueFactory &bv, 366218887Sdim llvm::BumpPtrAllocator& bpalloc) 367218887Sdim : SymbolCounter(0), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 368218887Sdim 369218887Sdim ~SymbolManager(); 370218887Sdim 371218887Sdim static bool canSymbolicate(QualType T); 372218887Sdim 373218887Sdim /// Make a unique symbol for MemRegion R according to its kind. 374218887Sdim const SymbolRegionValue* getRegionValueSymbol(const TypedRegion* R); 375218887Sdim 376218887Sdim const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T, 377218887Sdim unsigned VisitCount, 378218887Sdim const void* SymbolTag = 0); 379218887Sdim 380218887Sdim const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount, 381218887Sdim const void* SymbolTag = 0) { 382218887Sdim return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag); 383218887Sdim } 384218887Sdim 385218887Sdim const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 386218887Sdim const TypedRegion *R); 387218887Sdim 388218887Sdim const SymbolExtent *getExtentSymbol(const SubRegion *R); 389218887Sdim 390218887Sdim const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt* S, 391218887Sdim QualType T, unsigned VisitCount, 392218887Sdim const void* SymbolTag = 0); 393218887Sdim 394218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 395218887Sdim const llvm::APSInt& rhs, QualType t); 396218887Sdim 397218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 398218887Sdim const llvm::APSInt& rhs, QualType t) { 399218887Sdim return getSymIntExpr(&lhs, op, rhs, t); 400218887Sdim } 401218887Sdim 402218887Sdim const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 403218887Sdim const SymExpr *rhs, QualType t); 404218887Sdim 405218887Sdim QualType getType(const SymExpr *SE) const { 406218887Sdim return SE->getType(Ctx); 407218887Sdim } 408218887Sdim 409218887Sdim ASTContext &getContext() { return Ctx; } 410218887Sdim BasicValueFactory &getBasicVals() { return BV; } 411218887Sdim}; 412218887Sdim 413218887Sdimclass SymbolReaper { 414218887Sdim typedef llvm::DenseSet<SymbolRef> SetTy; 415218887Sdim 416218887Sdim SetTy TheLiving; 417218887Sdim SetTy MetadataInUse; 418218887Sdim SetTy TheDead; 419218887Sdim const LocationContext *LCtx; 420218887Sdim const Stmt *Loc; 421218887Sdim SymbolManager& SymMgr; 422218887Sdim 423218887Sdimpublic: 424218887Sdim SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr) 425218887Sdim : LCtx(ctx), Loc(s), SymMgr(symmgr) {} 426218887Sdim 427218887Sdim ~SymbolReaper() {} 428218887Sdim 429218887Sdim const LocationContext *getLocationContext() const { return LCtx; } 430218887Sdim const Stmt *getCurrentStatement() const { return Loc; } 431218887Sdim 432218887Sdim bool isLive(SymbolRef sym); 433218887Sdim bool isLive(const Stmt *ExprVal) const; 434218887Sdim bool isLive(const VarRegion *VR) const; 435218887Sdim 436218887Sdim // markLive - Unconditionally marks a symbol as live. This should never be 437218887Sdim // used by checkers, only by the state infrastructure such as the store and 438218887Sdim // environment. Checkers should instead use metadata symbols and markInUse. 439218887Sdim void markLive(SymbolRef sym); 440218887Sdim 441218887Sdim // markInUse - Marks a symbol as important to a checker. For metadata symbols, 442218887Sdim // this will keep the symbol alive as long as its associated region is also 443218887Sdim // live. For other symbols, this has no effect; checkers are not permitted 444218887Sdim // to influence the life of other symbols. This should be used before any 445218887Sdim // symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 446218887Sdim void markInUse(SymbolRef sym); 447218887Sdim 448218887Sdim // maybeDead - If a symbol is known to be live, marks the symbol as live. 449218887Sdim // Otherwise, if the symbol cannot be proven live, it is marked as dead. 450218887Sdim // Returns true if the symbol is dead, false if live. 451218887Sdim bool maybeDead(SymbolRef sym); 452218887Sdim 453218887Sdim typedef SetTy::const_iterator dead_iterator; 454218887Sdim dead_iterator dead_begin() const { return TheDead.begin(); } 455218887Sdim dead_iterator dead_end() const { return TheDead.end(); } 456218887Sdim 457218887Sdim bool hasDeadSymbols() const { 458218887Sdim return !TheDead.empty(); 459218887Sdim } 460218887Sdim 461218887Sdim /// isDead - Returns whether or not a symbol has been confirmed dead. This 462218887Sdim /// should only be called once all marking of dead symbols has completed. 463218887Sdim /// (For checkers, this means only in the evalDeadSymbols callback.) 464218887Sdim bool isDead(SymbolRef sym) const { 465218887Sdim return TheDead.count(sym); 466218887Sdim } 467218887Sdim}; 468218887Sdim 469218887Sdimclass SymbolVisitor { 470218887Sdimpublic: 471218887Sdim // VisitSymbol - A visitor method invoked by 472218887Sdim // GRStateManager::scanReachableSymbols. The method returns \c true if 473218887Sdim // symbols should continue be scanned and \c false otherwise. 474218887Sdim virtual bool VisitSymbol(SymbolRef sym) = 0; 475218887Sdim virtual ~SymbolVisitor(); 476218887Sdim}; 477218887Sdim 478218887Sdim} // end GR namespace 479218887Sdim 480218887Sdim} // end clang namespace 481218887Sdim 482218887Sdimnamespace llvm { 483218887Sdimstatic inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, 484218887Sdim const clang::ento::SymExpr *SE) { 485218887Sdim SE->dumpToStream(os); 486218887Sdim return os; 487218887Sdim} 488218887Sdim} // end llvm namespace 489218887Sdim#endif 490