SymbolManager.h revision 309124
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 15280031Sdim#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H 16280031Sdim#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_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" 22309124Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 23226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 24309124Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 25249423Sdim#include "llvm/ADT/DenseMap.h" 26249423Sdim#include "llvm/ADT/DenseSet.h" 27249423Sdim#include "llvm/ADT/FoldingSet.h" 28276479Sdim#include "llvm/Support/Allocator.h" 29218887Sdim#include "llvm/Support/DataTypes.h" 30218887Sdim 31218887Sdimnamespace clang { 32218887Sdim class ASTContext; 33218887Sdim class StackFrameContext; 34218887Sdim 35218887Sdimnamespace ento { 36218887Sdim class BasicValueFactory; 37218887Sdim class SubRegion; 38226633Sdim class TypedValueRegion; 39218887Sdim class VarRegion; 40218887Sdim 41234353Sdim///\brief A symbol representing the value stored at a MemRegion. 42218887Sdimclass SymbolRegionValue : public SymbolData { 43226633Sdim const TypedValueRegion *R; 44218887Sdim 45218887Sdimpublic: 46226633Sdim SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 47296417Sdim : SymbolData(SymbolRegionValueKind, sym), R(r) {} 48218887Sdim 49226633Sdim const TypedValueRegion* getRegion() const { return R; } 50218887Sdim 51226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { 52296417Sdim profile.AddInteger((unsigned) SymbolRegionValueKind); 53218887Sdim profile.AddPointer(R); 54218887Sdim } 55218887Sdim 56276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 57218887Sdim Profile(profile, R); 58218887Sdim } 59218887Sdim 60276479Sdim void dumpToStream(raw_ostream &os) const override; 61309124Sdim const MemRegion *getOriginRegion() const override { return getRegion(); } 62218887Sdim 63276479Sdim QualType getType() const override; 64218887Sdim 65218887Sdim // Implement isa<T> support. 66226633Sdim static inline bool classof(const SymExpr *SE) { 67296417Sdim return SE->getKind() == SymbolRegionValueKind; 68218887Sdim } 69218887Sdim}; 70218887Sdim 71234353Sdim/// A symbol representing the result of an expression in the case when we do 72234353Sdim/// not know anything about what the expression is. 73218887Sdimclass SymbolConjured : public SymbolData { 74226633Sdim const Stmt *S; 75218887Sdim QualType T; 76218887Sdim unsigned Count; 77234353Sdim const LocationContext *LCtx; 78226633Sdim const void *SymbolTag; 79218887Sdim 80218887Sdimpublic: 81234353Sdim SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 82296417Sdim QualType t, unsigned count, const void *symbolTag) 83296417Sdim : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count), 84296417Sdim LCtx(lctx), SymbolTag(symbolTag) {} 85218887Sdim 86226633Sdim const Stmt *getStmt() const { return S; } 87218887Sdim unsigned getCount() const { return Count; } 88226633Sdim const void *getTag() const { return SymbolTag; } 89218887Sdim 90276479Sdim QualType getType() const override; 91218887Sdim 92276479Sdim void dumpToStream(raw_ostream &os) const override; 93218887Sdim 94226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 95234353Sdim QualType T, unsigned Count, const LocationContext *LCtx, 96234353Sdim const void *SymbolTag) { 97296417Sdim profile.AddInteger((unsigned) SymbolConjuredKind); 98218887Sdim profile.AddPointer(S); 99234353Sdim profile.AddPointer(LCtx); 100218887Sdim profile.Add(T); 101218887Sdim profile.AddInteger(Count); 102218887Sdim profile.AddPointer(SymbolTag); 103218887Sdim } 104218887Sdim 105276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 106234353Sdim Profile(profile, S, T, Count, LCtx, SymbolTag); 107218887Sdim } 108218887Sdim 109218887Sdim // Implement isa<T> support. 110226633Sdim static inline bool classof(const SymExpr *SE) { 111296417Sdim return SE->getKind() == SymbolConjuredKind; 112218887Sdim } 113218887Sdim}; 114218887Sdim 115226633Sdim/// A symbol representing the value of a MemRegion whose parent region has 116226633Sdim/// symbolic value. 117218887Sdimclass SymbolDerived : public SymbolData { 118218887Sdim SymbolRef parentSymbol; 119226633Sdim const TypedValueRegion *R; 120218887Sdim 121218887Sdimpublic: 122226633Sdim SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 123296417Sdim : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {} 124218887Sdim 125218887Sdim SymbolRef getParentSymbol() const { return parentSymbol; } 126226633Sdim const TypedValueRegion *getRegion() const { return R; } 127218887Sdim 128276479Sdim QualType getType() const override; 129218887Sdim 130276479Sdim void dumpToStream(raw_ostream &os) const override; 131309124Sdim const MemRegion *getOriginRegion() const override { return getRegion(); } 132218887Sdim 133218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 134226633Sdim const TypedValueRegion *r) { 135296417Sdim profile.AddInteger((unsigned) SymbolDerivedKind); 136218887Sdim profile.AddPointer(r); 137218887Sdim profile.AddPointer(parent); 138218887Sdim } 139218887Sdim 140276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 141218887Sdim Profile(profile, parentSymbol, R); 142218887Sdim } 143218887Sdim 144218887Sdim // Implement isa<T> support. 145226633Sdim static inline bool classof(const SymExpr *SE) { 146296417Sdim return SE->getKind() == SymbolDerivedKind; 147218887Sdim } 148218887Sdim}; 149218887Sdim 150218887Sdim/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 151218887Sdim/// Clients should not ask the SymbolManager for a region's extent. Always use 152218887Sdim/// SubRegion::getExtent instead -- the value returned may not be a symbol. 153218887Sdimclass SymbolExtent : public SymbolData { 154218887Sdim const SubRegion *R; 155218887Sdim 156218887Sdimpublic: 157218887Sdim SymbolExtent(SymbolID sym, const SubRegion *r) 158296417Sdim : SymbolData(SymbolExtentKind, sym), R(r) {} 159218887Sdim 160218887Sdim const SubRegion *getRegion() const { return R; } 161218887Sdim 162276479Sdim QualType getType() const override; 163218887Sdim 164276479Sdim void dumpToStream(raw_ostream &os) const override; 165218887Sdim 166218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 167296417Sdim profile.AddInteger((unsigned) SymbolExtentKind); 168218887Sdim profile.AddPointer(R); 169218887Sdim } 170218887Sdim 171276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 172218887Sdim Profile(profile, R); 173218887Sdim } 174218887Sdim 175218887Sdim // Implement isa<T> support. 176226633Sdim static inline bool classof(const SymExpr *SE) { 177296417Sdim return SE->getKind() == SymbolExtentKind; 178218887Sdim } 179218887Sdim}; 180218887Sdim 181218887Sdim/// SymbolMetadata - Represents path-dependent metadata about a specific region. 182218887Sdim/// Metadata symbols remain live as long as they are marked as in use before 183218887Sdim/// dead-symbol sweeping AND their associated regions are still alive. 184218887Sdim/// Intended for use by checkers. 185218887Sdimclass SymbolMetadata : public SymbolData { 186218887Sdim const MemRegion* R; 187226633Sdim const Stmt *S; 188218887Sdim QualType T; 189218887Sdim unsigned Count; 190226633Sdim const void *Tag; 191218887Sdimpublic: 192226633Sdim SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 193226633Sdim unsigned count, const void *tag) 194296417Sdim : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} 195218887Sdim 196218887Sdim const MemRegion *getRegion() const { return R; } 197226633Sdim const Stmt *getStmt() const { return S; } 198218887Sdim unsigned getCount() const { return Count; } 199226633Sdim const void *getTag() const { return Tag; } 200218887Sdim 201276479Sdim QualType getType() const override; 202218887Sdim 203276479Sdim void dumpToStream(raw_ostream &os) const override; 204218887Sdim 205218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 206218887Sdim const Stmt *S, QualType T, unsigned Count, 207218887Sdim const void *Tag) { 208296417Sdim profile.AddInteger((unsigned) SymbolMetadataKind); 209218887Sdim profile.AddPointer(R); 210218887Sdim profile.AddPointer(S); 211218887Sdim profile.Add(T); 212218887Sdim profile.AddInteger(Count); 213218887Sdim profile.AddPointer(Tag); 214218887Sdim } 215218887Sdim 216276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 217218887Sdim Profile(profile, R, S, T, Count, Tag); 218218887Sdim } 219218887Sdim 220218887Sdim // Implement isa<T> support. 221226633Sdim static inline bool classof(const SymExpr *SE) { 222296417Sdim return SE->getKind() == SymbolMetadataKind; 223218887Sdim } 224218887Sdim}; 225218887Sdim 226234353Sdim/// \brief Represents a cast expression. 227234353Sdimclass SymbolCast : public SymExpr { 228234353Sdim const SymExpr *Operand; 229234353Sdim /// Type of the operand. 230234353Sdim QualType FromTy; 231234353Sdim /// The type of the result. 232234353Sdim QualType ToTy; 233234353Sdim 234234353Sdimpublic: 235234353Sdim SymbolCast(const SymExpr *In, QualType From, QualType To) : 236296417Sdim SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) { } 237234353Sdim 238276479Sdim QualType getType() const override { return ToTy; } 239234353Sdim 240234353Sdim const SymExpr *getOperand() const { return Operand; } 241234353Sdim 242276479Sdim void dumpToStream(raw_ostream &os) const override; 243234353Sdim 244234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, 245234353Sdim const SymExpr *In, QualType From, QualType To) { 246296417Sdim ID.AddInteger((unsigned) SymbolCastKind); 247234353Sdim ID.AddPointer(In); 248234353Sdim ID.Add(From); 249234353Sdim ID.Add(To); 250234353Sdim } 251234353Sdim 252276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 253234353Sdim Profile(ID, Operand, FromTy, ToTy); 254234353Sdim } 255234353Sdim 256234353Sdim // Implement isa<T> support. 257234353Sdim static inline bool classof(const SymExpr *SE) { 258296417Sdim return SE->getKind() == SymbolCastKind; 259234353Sdim } 260234353Sdim}; 261234353Sdim 262251662Sdim/// \brief Represents a symbolic expression involving a binary operator 263251662Sdimclass BinarySymExpr : public SymExpr { 264218887Sdim BinaryOperator::Opcode Op; 265218887Sdim QualType T; 266218887Sdim 267251662Sdimprotected: 268251662Sdim BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) 269251662Sdim : SymExpr(k), Op(op), T(t) {} 270251662Sdim 271218887Sdimpublic: 272218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 273218887Sdim // generation of virtual functions. 274276479Sdim QualType getType() const override { return T; } 275218887Sdim 276218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 277218887Sdim 278251662Sdim // Implement isa<T> support. 279251662Sdim static inline bool classof(const SymExpr *SE) { 280251662Sdim Kind k = SE->getKind(); 281251662Sdim return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; 282251662Sdim } 283251662Sdim}; 284251662Sdim 285251662Sdim/// \brief Represents a symbolic expression like 'x' + 3. 286251662Sdimclass SymIntExpr : public BinarySymExpr { 287251662Sdim const SymExpr *LHS; 288251662Sdim const llvm::APSInt& RHS; 289251662Sdim 290251662Sdimpublic: 291251662Sdim SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 292251662Sdim const llvm::APSInt& rhs, QualType t) 293296417Sdim : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {} 294251662Sdim 295276479Sdim void dumpToStream(raw_ostream &os) const override; 296218887Sdim 297218887Sdim const SymExpr *getLHS() const { return LHS; } 298218887Sdim const llvm::APSInt &getRHS() const { return RHS; } 299218887Sdim 300218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 301218887Sdim BinaryOperator::Opcode op, const llvm::APSInt& rhs, 302218887Sdim QualType t) { 303296417Sdim ID.AddInteger((unsigned) SymIntExprKind); 304218887Sdim ID.AddPointer(lhs); 305218887Sdim ID.AddInteger(op); 306218887Sdim ID.AddPointer(&rhs); 307218887Sdim ID.Add(t); 308218887Sdim } 309218887Sdim 310276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 311251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 312218887Sdim } 313218887Sdim 314218887Sdim // Implement isa<T> support. 315226633Sdim static inline bool classof(const SymExpr *SE) { 316296417Sdim return SE->getKind() == SymIntExprKind; 317218887Sdim } 318218887Sdim}; 319218887Sdim 320251662Sdim/// \brief Represents a symbolic expression like 3 - 'x'. 321251662Sdimclass IntSymExpr : public BinarySymExpr { 322234353Sdim const llvm::APSInt& LHS; 323234353Sdim const SymExpr *RHS; 324234353Sdim 325234353Sdimpublic: 326234353Sdim IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, 327234353Sdim const SymExpr *rhs, QualType t) 328296417Sdim : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {} 329234353Sdim 330276479Sdim void dumpToStream(raw_ostream &os) const override; 331234353Sdim 332234353Sdim const SymExpr *getRHS() const { return RHS; } 333234353Sdim const llvm::APSInt &getLHS() const { return LHS; } 334234353Sdim 335234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 336234353Sdim BinaryOperator::Opcode op, const SymExpr *rhs, 337234353Sdim QualType t) { 338296417Sdim ID.AddInteger((unsigned) IntSymExprKind); 339234353Sdim ID.AddPointer(&lhs); 340234353Sdim ID.AddInteger(op); 341234353Sdim ID.AddPointer(rhs); 342234353Sdim ID.Add(t); 343234353Sdim } 344234353Sdim 345276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 346251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 347234353Sdim } 348234353Sdim 349234353Sdim // Implement isa<T> support. 350234353Sdim static inline bool classof(const SymExpr *SE) { 351296417Sdim return SE->getKind() == IntSymExprKind; 352234353Sdim } 353234353Sdim}; 354234353Sdim 355251662Sdim/// \brief Represents a symbolic expression like 'x' + 'y'. 356251662Sdimclass SymSymExpr : public BinarySymExpr { 357218887Sdim const SymExpr *LHS; 358218887Sdim const SymExpr *RHS; 359218887Sdim 360218887Sdimpublic: 361218887Sdim SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 362218887Sdim QualType t) 363296417Sdim : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {} 364218887Sdim 365218887Sdim const SymExpr *getLHS() const { return LHS; } 366218887Sdim const SymExpr *getRHS() const { return RHS; } 367218887Sdim 368276479Sdim void dumpToStream(raw_ostream &os) const override; 369218887Sdim 370218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 371218887Sdim BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 372296417Sdim ID.AddInteger((unsigned) SymSymExprKind); 373218887Sdim ID.AddPointer(lhs); 374218887Sdim ID.AddInteger(op); 375218887Sdim ID.AddPointer(rhs); 376218887Sdim ID.Add(t); 377218887Sdim } 378218887Sdim 379276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 380251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 381218887Sdim } 382218887Sdim 383218887Sdim // Implement isa<T> support. 384226633Sdim static inline bool classof(const SymExpr *SE) { 385296417Sdim return SE->getKind() == SymSymExprKind; 386218887Sdim } 387218887Sdim}; 388218887Sdim 389218887Sdimclass SymbolManager { 390218887Sdim typedef llvm::FoldingSet<SymExpr> DataSetTy; 391226633Sdim typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; 392226633Sdim 393218887Sdim DataSetTy DataSet; 394226633Sdim /// Stores the extra dependencies between symbols: the data should be kept 395226633Sdim /// alive as long as the key is live. 396226633Sdim SymbolDependTy SymbolDependencies; 397218887Sdim unsigned SymbolCounter; 398218887Sdim llvm::BumpPtrAllocator& BPAlloc; 399218887Sdim BasicValueFactory &BV; 400226633Sdim ASTContext &Ctx; 401218887Sdim 402218887Sdimpublic: 403226633Sdim SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 404218887Sdim llvm::BumpPtrAllocator& bpalloc) 405226633Sdim : SymbolDependencies(16), SymbolCounter(0), 406226633Sdim BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 407218887Sdim 408218887Sdim ~SymbolManager(); 409218887Sdim 410218887Sdim static bool canSymbolicate(QualType T); 411218887Sdim 412226633Sdim /// \brief Make a unique symbol for MemRegion R according to its kind. 413226633Sdim const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 414218887Sdim 415243830Sdim const SymbolConjured* conjureSymbol(const Stmt *E, 416243830Sdim const LocationContext *LCtx, 417243830Sdim QualType T, 418243830Sdim unsigned VisitCount, 419276479Sdim const void *SymbolTag = nullptr); 420218887Sdim 421243830Sdim const SymbolConjured* conjureSymbol(const Expr *E, 422243830Sdim const LocationContext *LCtx, 423243830Sdim unsigned VisitCount, 424276479Sdim const void *SymbolTag = nullptr) { 425243830Sdim return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag); 426218887Sdim } 427218887Sdim 428218887Sdim const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 429226633Sdim const TypedValueRegion *R); 430218887Sdim 431218887Sdim const SymbolExtent *getExtentSymbol(const SubRegion *R); 432218887Sdim 433226633Sdim /// \brief Creates a metadata symbol associated with a specific region. 434226633Sdim /// 435226633Sdim /// VisitCount can be used to differentiate regions corresponding to 436226633Sdim /// different loop iterations, thus, making the symbol path-dependent. 437276479Sdim const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S, 438218887Sdim QualType T, unsigned VisitCount, 439276479Sdim const void *SymbolTag = nullptr); 440218887Sdim 441234353Sdim const SymbolCast* getCastSymbol(const SymExpr *Operand, 442234353Sdim QualType From, QualType To); 443234353Sdim 444218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 445218887Sdim const llvm::APSInt& rhs, QualType t); 446218887Sdim 447218887Sdim const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 448218887Sdim const llvm::APSInt& rhs, QualType t) { 449218887Sdim return getSymIntExpr(&lhs, op, rhs, t); 450218887Sdim } 451218887Sdim 452234353Sdim const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, 453234353Sdim BinaryOperator::Opcode op, 454234353Sdim const SymExpr *rhs, QualType t); 455234353Sdim 456218887Sdim const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 457218887Sdim const SymExpr *rhs, QualType t); 458218887Sdim 459218887Sdim QualType getType(const SymExpr *SE) const { 460243830Sdim return SE->getType(); 461218887Sdim } 462218887Sdim 463226633Sdim /// \brief Add artificial symbol dependency. 464226633Sdim /// 465226633Sdim /// The dependent symbol should stay alive as long as the primary is alive. 466226633Sdim void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); 467226633Sdim 468226633Sdim const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); 469226633Sdim 470218887Sdim ASTContext &getContext() { return Ctx; } 471218887Sdim BasicValueFactory &getBasicVals() { return BV; } 472218887Sdim}; 473218887Sdim 474239462Sdim/// \brief A class responsible for cleaning up unused symbols. 475218887Sdimclass SymbolReaper { 476226633Sdim enum SymbolStatus { 477226633Sdim NotProcessed, 478226633Sdim HaveMarkedDependents 479226633Sdim }; 480218887Sdim 481226633Sdim typedef llvm::DenseSet<SymbolRef> SymbolSetTy; 482226633Sdim typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; 483226633Sdim typedef llvm::DenseSet<const MemRegion *> RegionSetTy; 484226633Sdim 485226633Sdim SymbolMapTy TheLiving; 486226633Sdim SymbolSetTy MetadataInUse; 487226633Sdim SymbolSetTy TheDead; 488226633Sdim 489226633Sdim RegionSetTy RegionRoots; 490226633Sdim 491239462Sdim const StackFrameContext *LCtx; 492218887Sdim const Stmt *Loc; 493218887Sdim SymbolManager& SymMgr; 494226633Sdim StoreRef reapedStore; 495226633Sdim llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 496218887Sdim 497218887Sdimpublic: 498239462Sdim /// \brief Construct a reaper object, which removes everything which is not 499239462Sdim /// live before we execute statement s in the given location context. 500239462Sdim /// 501239462Sdim /// If the statement is NULL, everything is this and parent contexts is 502239462Sdim /// considered live. 503243830Sdim /// If the stack frame context is NULL, everything on stack is considered 504243830Sdim /// dead. 505243830Sdim SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr, 506226633Sdim StoreManager &storeMgr) 507243830Sdim : LCtx(Ctx), Loc(s), SymMgr(symmgr), 508276479Sdim reapedStore(nullptr, storeMgr) {} 509218887Sdim 510218887Sdim const LocationContext *getLocationContext() const { return LCtx; } 511218887Sdim 512218887Sdim bool isLive(SymbolRef sym); 513226633Sdim bool isLiveRegion(const MemRegion *region); 514234353Sdim bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 515226633Sdim bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 516218887Sdim 517226633Sdim /// \brief Unconditionally marks a symbol as live. 518226633Sdim /// 519226633Sdim /// This should never be 520226633Sdim /// used by checkers, only by the state infrastructure such as the store and 521226633Sdim /// environment. Checkers should instead use metadata symbols and markInUse. 522218887Sdim void markLive(SymbolRef sym); 523218887Sdim 524226633Sdim /// \brief Marks a symbol as important to a checker. 525226633Sdim /// 526226633Sdim /// For metadata symbols, 527226633Sdim /// this will keep the symbol alive as long as its associated region is also 528226633Sdim /// live. For other symbols, this has no effect; checkers are not permitted 529226633Sdim /// to influence the life of other symbols. This should be used before any 530226633Sdim /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 531218887Sdim void markInUse(SymbolRef sym); 532218887Sdim 533226633Sdim /// \brief If a symbol is known to be live, marks the symbol as live. 534226633Sdim /// 535226633Sdim /// Otherwise, if the symbol cannot be proven live, it is marked as dead. 536226633Sdim /// Returns true if the symbol is dead, false if live. 537218887Sdim bool maybeDead(SymbolRef sym); 538218887Sdim 539226633Sdim typedef SymbolSetTy::const_iterator dead_iterator; 540218887Sdim dead_iterator dead_begin() const { return TheDead.begin(); } 541218887Sdim dead_iterator dead_end() const { return TheDead.end(); } 542218887Sdim 543218887Sdim bool hasDeadSymbols() const { 544218887Sdim return !TheDead.empty(); 545218887Sdim } 546226633Sdim 547226633Sdim typedef RegionSetTy::const_iterator region_iterator; 548226633Sdim region_iterator region_begin() const { return RegionRoots.begin(); } 549226633Sdim region_iterator region_end() const { return RegionRoots.end(); } 550218887Sdim 551226633Sdim /// \brief Returns whether or not a symbol has been confirmed dead. 552226633Sdim /// 553226633Sdim /// This should only be called once all marking of dead symbols has completed. 554226633Sdim /// (For checkers, this means only in the evalDeadSymbols callback.) 555218887Sdim bool isDead(SymbolRef sym) const { 556218887Sdim return TheDead.count(sym); 557218887Sdim } 558226633Sdim 559226633Sdim void markLive(const MemRegion *region); 560296417Sdim void markElementIndicesLive(const MemRegion *region); 561226633Sdim 562226633Sdim /// \brief Set to the value of the symbolic store after 563226633Sdim /// StoreManager::removeDeadBindings has been called. 564226633Sdim void setReapedStore(StoreRef st) { reapedStore = st; } 565226633Sdim 566226633Sdimprivate: 567226633Sdim /// Mark the symbols dependent on the input symbol as live. 568226633Sdim void markDependentsLive(SymbolRef sym); 569218887Sdim}; 570218887Sdim 571218887Sdimclass SymbolVisitor { 572296417Sdimprotected: 573296417Sdim ~SymbolVisitor() = default; 574296417Sdim 575218887Sdimpublic: 576296417Sdim SymbolVisitor() = default; 577296417Sdim SymbolVisitor(const SymbolVisitor &) = default; 578296417Sdim SymbolVisitor(SymbolVisitor &&) {} 579296417Sdim 580226633Sdim /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. 581226633Sdim /// 582226633Sdim /// The method returns \c true if symbols should continue be scanned and \c 583226633Sdim /// false otherwise. 584218887Sdim virtual bool VisitSymbol(SymbolRef sym) = 0; 585226633Sdim virtual bool VisitMemRegion(const MemRegion *region) { return true; } 586218887Sdim}; 587218887Sdim 588218887Sdim} // end GR namespace 589218887Sdim 590218887Sdim} // end clang namespace 591218887Sdim 592218887Sdimnamespace llvm { 593226633Sdimstatic inline raw_ostream &operator<<(raw_ostream &os, 594234353Sdim const clang::ento::SymExpr *SE) { 595218887Sdim SE->dumpToStream(os); 596218887Sdim return os; 597218887Sdim} 598218887Sdim} // end llvm namespace 599218887Sdim#endif 600