SymbolManager.h revision 280031
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" 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" 26276479Sdim#include "llvm/Support/Allocator.h" 27218887Sdim#include "llvm/Support/DataTypes.h" 28218887Sdim 29218887Sdimnamespace clang { 30218887Sdim class ASTContext; 31218887Sdim class StackFrameContext; 32218887Sdim 33218887Sdimnamespace ento { 34218887Sdim class BasicValueFactory; 35218887Sdim class MemRegion; 36218887Sdim class SubRegion; 37226633Sdim class TypedValueRegion; 38218887Sdim class VarRegion; 39218887Sdim 40234353Sdim/// \brief Symbolic value. These values used to capture symbolic execution of 41234353Sdim/// the program. 42218887Sdimclass SymExpr : public llvm::FoldingSetNode { 43234353Sdim virtual void anchor(); 44218887Sdimpublic: 45226633Sdim enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, 46218887Sdim MetadataKind, 47226633Sdim BEGIN_SYMBOLS = RegionValueKind, 48226633Sdim END_SYMBOLS = MetadataKind, 49251662Sdim SymIntKind, IntSymKind, SymSymKind, 50251662Sdim BEGIN_BINARYSYMEXPRS = SymIntKind, 51251662Sdim END_BINARYSYMEXPRS = SymSymKind, 52251662Sdim 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 68243830Sdim virtual QualType getType() const = 0; 69218887Sdim virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; 70218887Sdim 71234353Sdim /// \brief Iterator over symbols that the current symbol depends on. 72234353Sdim /// 73234353Sdim /// For SymbolData, it's the symbol itself; for expressions, it's the 74234353Sdim /// expression symbol and all the operands in it. Note, SymbolDerived is 75234353Sdim /// treated as SymbolData - the iterator will NOT visit the parent region. 76234353Sdim class symbol_iterator { 77234353Sdim SmallVector<const SymExpr*, 5> itr; 78234353Sdim void expand(); 79234353Sdim public: 80234353Sdim symbol_iterator() {} 81234353Sdim symbol_iterator(const SymExpr *SE); 82234353Sdim 83234353Sdim symbol_iterator &operator++(); 84234353Sdim const SymExpr* operator*(); 85234353Sdim 86234353Sdim bool operator==(const symbol_iterator &X) const; 87234353Sdim bool operator!=(const symbol_iterator &X) const; 88234353Sdim }; 89234353Sdim 90234353Sdim symbol_iterator symbol_begin() const { 91234353Sdim return symbol_iterator(this); 92234353Sdim } 93234353Sdim static symbol_iterator symbol_end() { return symbol_iterator(); } 94239462Sdim 95239462Sdim unsigned computeComplexity() const; 96218887Sdim}; 97218887Sdim 98234353Sdimtypedef const SymExpr* SymbolRef; 99249423Sdimtypedef SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy; 100234353Sdim 101218887Sdimtypedef unsigned SymbolID; 102234353Sdim/// \brief A symbol representing data which can be stored in a memory location 103234353Sdim/// (region). 104218887Sdimclass SymbolData : public SymExpr { 105276479Sdim void anchor() override; 106218887Sdim const SymbolID Sym; 107218887Sdim 108218887Sdimprotected: 109218887Sdim SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {} 110218887Sdim 111218887Sdimpublic: 112218887Sdim virtual ~SymbolData() {} 113218887Sdim 114218887Sdim SymbolID getSymbolID() const { return Sym; } 115218887Sdim 116218887Sdim // Implement isa<T> support. 117226633Sdim static inline bool classof(const SymExpr *SE) { 118218887Sdim Kind k = SE->getKind(); 119226633Sdim return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; 120218887Sdim } 121218887Sdim}; 122218887Sdim 123234353Sdim///\brief A symbol representing the value stored at a MemRegion. 124218887Sdimclass SymbolRegionValue : public SymbolData { 125226633Sdim const TypedValueRegion *R; 126218887Sdim 127218887Sdimpublic: 128226633Sdim SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 129218887Sdim : SymbolData(RegionValueKind, sym), R(r) {} 130218887Sdim 131226633Sdim const TypedValueRegion* getRegion() const { return R; } 132218887Sdim 133226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { 134218887Sdim profile.AddInteger((unsigned) RegionValueKind); 135218887Sdim profile.AddPointer(R); 136218887Sdim } 137218887Sdim 138276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 139218887Sdim Profile(profile, R); 140218887Sdim } 141218887Sdim 142276479Sdim void dumpToStream(raw_ostream &os) const override; 143218887Sdim 144276479Sdim QualType getType() const override; 145218887Sdim 146218887Sdim // Implement isa<T> support. 147226633Sdim static inline bool classof(const SymExpr *SE) { 148218887Sdim return SE->getKind() == RegionValueKind; 149218887Sdim } 150218887Sdim}; 151218887Sdim 152234353Sdim/// A symbol representing the result of an expression in the case when we do 153234353Sdim/// not know anything about what the expression is. 154218887Sdimclass SymbolConjured : public SymbolData { 155226633Sdim const Stmt *S; 156218887Sdim QualType T; 157218887Sdim unsigned Count; 158234353Sdim const LocationContext *LCtx; 159226633Sdim const void *SymbolTag; 160218887Sdim 161218887Sdimpublic: 162234353Sdim SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 163234353Sdim QualType t, unsigned count, 164226633Sdim const void *symbolTag) 165218887Sdim : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), 166234353Sdim LCtx(lctx), 167218887Sdim SymbolTag(symbolTag) {} 168218887Sdim 169226633Sdim const Stmt *getStmt() const { return S; } 170218887Sdim unsigned getCount() const { return Count; } 171226633Sdim const void *getTag() const { return SymbolTag; } 172218887Sdim 173276479Sdim QualType getType() const override; 174218887Sdim 175276479Sdim void dumpToStream(raw_ostream &os) const override; 176218887Sdim 177226633Sdim static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 178234353Sdim QualType T, unsigned Count, const LocationContext *LCtx, 179234353Sdim const void *SymbolTag) { 180218887Sdim profile.AddInteger((unsigned) ConjuredKind); 181218887Sdim profile.AddPointer(S); 182234353Sdim profile.AddPointer(LCtx); 183218887Sdim profile.Add(T); 184218887Sdim profile.AddInteger(Count); 185218887Sdim profile.AddPointer(SymbolTag); 186218887Sdim } 187218887Sdim 188276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 189234353Sdim Profile(profile, S, T, Count, LCtx, SymbolTag); 190218887Sdim } 191218887Sdim 192218887Sdim // Implement isa<T> support. 193226633Sdim static inline bool classof(const SymExpr *SE) { 194218887Sdim return SE->getKind() == ConjuredKind; 195218887Sdim } 196218887Sdim}; 197218887Sdim 198226633Sdim/// A symbol representing the value of a MemRegion whose parent region has 199226633Sdim/// symbolic value. 200218887Sdimclass SymbolDerived : public SymbolData { 201218887Sdim SymbolRef parentSymbol; 202226633Sdim const TypedValueRegion *R; 203218887Sdim 204218887Sdimpublic: 205226633Sdim SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 206218887Sdim : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} 207218887Sdim 208218887Sdim SymbolRef getParentSymbol() const { return parentSymbol; } 209226633Sdim const TypedValueRegion *getRegion() const { return R; } 210218887Sdim 211276479Sdim QualType getType() const override; 212218887Sdim 213276479Sdim void dumpToStream(raw_ostream &os) const override; 214218887Sdim 215218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 216226633Sdim const TypedValueRegion *r) { 217218887Sdim profile.AddInteger((unsigned) DerivedKind); 218218887Sdim profile.AddPointer(r); 219218887Sdim profile.AddPointer(parent); 220218887Sdim } 221218887Sdim 222276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 223218887Sdim Profile(profile, parentSymbol, R); 224218887Sdim } 225218887Sdim 226218887Sdim // Implement isa<T> support. 227226633Sdim static inline bool classof(const SymExpr *SE) { 228218887Sdim return SE->getKind() == DerivedKind; 229218887Sdim } 230218887Sdim}; 231218887Sdim 232218887Sdim/// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 233218887Sdim/// Clients should not ask the SymbolManager for a region's extent. Always use 234218887Sdim/// SubRegion::getExtent instead -- the value returned may not be a symbol. 235218887Sdimclass SymbolExtent : public SymbolData { 236218887Sdim const SubRegion *R; 237218887Sdim 238218887Sdimpublic: 239218887Sdim SymbolExtent(SymbolID sym, const SubRegion *r) 240218887Sdim : SymbolData(ExtentKind, sym), R(r) {} 241218887Sdim 242218887Sdim const SubRegion *getRegion() const { return R; } 243218887Sdim 244276479Sdim QualType getType() const override; 245218887Sdim 246276479Sdim void dumpToStream(raw_ostream &os) const override; 247218887Sdim 248218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 249218887Sdim profile.AddInteger((unsigned) ExtentKind); 250218887Sdim profile.AddPointer(R); 251218887Sdim } 252218887Sdim 253276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 254218887Sdim Profile(profile, R); 255218887Sdim } 256218887Sdim 257218887Sdim // Implement isa<T> support. 258226633Sdim static inline bool classof(const SymExpr *SE) { 259218887Sdim return SE->getKind() == ExtentKind; 260218887Sdim } 261218887Sdim}; 262218887Sdim 263218887Sdim/// SymbolMetadata - Represents path-dependent metadata about a specific region. 264218887Sdim/// Metadata symbols remain live as long as they are marked as in use before 265218887Sdim/// dead-symbol sweeping AND their associated regions are still alive. 266218887Sdim/// Intended for use by checkers. 267218887Sdimclass SymbolMetadata : public SymbolData { 268218887Sdim const MemRegion* R; 269226633Sdim const Stmt *S; 270218887Sdim QualType T; 271218887Sdim unsigned Count; 272226633Sdim const void *Tag; 273218887Sdimpublic: 274226633Sdim SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 275226633Sdim unsigned count, const void *tag) 276218887Sdim : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} 277218887Sdim 278218887Sdim const MemRegion *getRegion() const { return R; } 279226633Sdim const Stmt *getStmt() const { return S; } 280218887Sdim unsigned getCount() const { return Count; } 281226633Sdim const void *getTag() const { return Tag; } 282218887Sdim 283276479Sdim QualType getType() const override; 284218887Sdim 285276479Sdim void dumpToStream(raw_ostream &os) const override; 286218887Sdim 287218887Sdim static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 288218887Sdim const Stmt *S, QualType T, unsigned Count, 289218887Sdim const void *Tag) { 290218887Sdim profile.AddInteger((unsigned) MetadataKind); 291218887Sdim profile.AddPointer(R); 292218887Sdim profile.AddPointer(S); 293218887Sdim profile.Add(T); 294218887Sdim profile.AddInteger(Count); 295218887Sdim profile.AddPointer(Tag); 296218887Sdim } 297218887Sdim 298276479Sdim void Profile(llvm::FoldingSetNodeID& profile) override { 299218887Sdim Profile(profile, R, S, T, Count, Tag); 300218887Sdim } 301218887Sdim 302218887Sdim // Implement isa<T> support. 303226633Sdim static inline bool classof(const SymExpr *SE) { 304218887Sdim return SE->getKind() == MetadataKind; 305218887Sdim } 306218887Sdim}; 307218887Sdim 308234353Sdim/// \brief Represents a cast expression. 309234353Sdimclass SymbolCast : public SymExpr { 310234353Sdim const SymExpr *Operand; 311234353Sdim /// Type of the operand. 312234353Sdim QualType FromTy; 313234353Sdim /// The type of the result. 314234353Sdim QualType ToTy; 315234353Sdim 316234353Sdimpublic: 317234353Sdim SymbolCast(const SymExpr *In, QualType From, QualType To) : 318234353Sdim SymExpr(CastSymbolKind), Operand(In), FromTy(From), ToTy(To) { } 319234353Sdim 320276479Sdim QualType getType() const override { return ToTy; } 321234353Sdim 322234353Sdim const SymExpr *getOperand() const { return Operand; } 323234353Sdim 324276479Sdim void dumpToStream(raw_ostream &os) const override; 325234353Sdim 326234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, 327234353Sdim const SymExpr *In, QualType From, QualType To) { 328234353Sdim ID.AddInteger((unsigned) CastSymbolKind); 329234353Sdim ID.AddPointer(In); 330234353Sdim ID.Add(From); 331234353Sdim ID.Add(To); 332234353Sdim } 333234353Sdim 334276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 335234353Sdim Profile(ID, Operand, FromTy, ToTy); 336234353Sdim } 337234353Sdim 338234353Sdim // Implement isa<T> support. 339234353Sdim static inline bool classof(const SymExpr *SE) { 340234353Sdim return SE->getKind() == CastSymbolKind; 341234353Sdim } 342234353Sdim}; 343234353Sdim 344251662Sdim/// \brief Represents a symbolic expression involving a binary operator 345251662Sdimclass BinarySymExpr : public SymExpr { 346218887Sdim BinaryOperator::Opcode Op; 347218887Sdim QualType T; 348218887Sdim 349251662Sdimprotected: 350251662Sdim BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) 351251662Sdim : SymExpr(k), Op(op), T(t) {} 352251662Sdim 353218887Sdimpublic: 354218887Sdim // FIXME: We probably need to make this out-of-line to avoid redundant 355218887Sdim // generation of virtual functions. 356276479Sdim QualType getType() const override { return T; } 357218887Sdim 358218887Sdim BinaryOperator::Opcode getOpcode() const { return Op; } 359218887Sdim 360251662Sdim // Implement isa<T> support. 361251662Sdim static inline bool classof(const SymExpr *SE) { 362251662Sdim Kind k = SE->getKind(); 363251662Sdim return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; 364251662Sdim } 365251662Sdim}; 366251662Sdim 367251662Sdim/// \brief Represents a symbolic expression like 'x' + 3. 368251662Sdimclass SymIntExpr : public BinarySymExpr { 369251662Sdim const SymExpr *LHS; 370251662Sdim const llvm::APSInt& RHS; 371251662Sdim 372251662Sdimpublic: 373251662Sdim SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 374251662Sdim const llvm::APSInt& rhs, QualType t) 375251662Sdim : BinarySymExpr(SymIntKind, op, t), LHS(lhs), RHS(rhs) {} 376251662Sdim 377276479Sdim void dumpToStream(raw_ostream &os) const override; 378218887Sdim 379218887Sdim const SymExpr *getLHS() const { return LHS; } 380218887Sdim const llvm::APSInt &getRHS() const { return RHS; } 381218887Sdim 382218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 383218887Sdim BinaryOperator::Opcode op, const llvm::APSInt& rhs, 384218887Sdim QualType t) { 385218887Sdim ID.AddInteger((unsigned) SymIntKind); 386218887Sdim ID.AddPointer(lhs); 387218887Sdim ID.AddInteger(op); 388218887Sdim ID.AddPointer(&rhs); 389218887Sdim ID.Add(t); 390218887Sdim } 391218887Sdim 392276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 393251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 394218887Sdim } 395218887Sdim 396218887Sdim // Implement isa<T> support. 397226633Sdim static inline bool classof(const SymExpr *SE) { 398218887Sdim return SE->getKind() == SymIntKind; 399218887Sdim } 400218887Sdim}; 401218887Sdim 402251662Sdim/// \brief Represents a symbolic expression like 3 - 'x'. 403251662Sdimclass IntSymExpr : public BinarySymExpr { 404234353Sdim const llvm::APSInt& LHS; 405234353Sdim const SymExpr *RHS; 406234353Sdim 407234353Sdimpublic: 408234353Sdim IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, 409234353Sdim const SymExpr *rhs, QualType t) 410251662Sdim : BinarySymExpr(IntSymKind, op, t), LHS(lhs), RHS(rhs) {} 411234353Sdim 412276479Sdim void dumpToStream(raw_ostream &os) const override; 413234353Sdim 414234353Sdim const SymExpr *getRHS() const { return RHS; } 415234353Sdim const llvm::APSInt &getLHS() const { return LHS; } 416234353Sdim 417234353Sdim static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 418234353Sdim BinaryOperator::Opcode op, const SymExpr *rhs, 419234353Sdim QualType t) { 420234353Sdim ID.AddInteger((unsigned) IntSymKind); 421234353Sdim ID.AddPointer(&lhs); 422234353Sdim ID.AddInteger(op); 423234353Sdim ID.AddPointer(rhs); 424234353Sdim ID.Add(t); 425234353Sdim } 426234353Sdim 427276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 428251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 429234353Sdim } 430234353Sdim 431234353Sdim // Implement isa<T> support. 432234353Sdim static inline bool classof(const SymExpr *SE) { 433234353Sdim return SE->getKind() == IntSymKind; 434234353Sdim } 435234353Sdim}; 436234353Sdim 437251662Sdim/// \brief Represents a symbolic expression like 'x' + 'y'. 438251662Sdimclass SymSymExpr : public BinarySymExpr { 439218887Sdim const SymExpr *LHS; 440218887Sdim const SymExpr *RHS; 441218887Sdim 442218887Sdimpublic: 443218887Sdim SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 444218887Sdim QualType t) 445251662Sdim : BinarySymExpr(SymSymKind, op, t), LHS(lhs), RHS(rhs) {} 446218887Sdim 447218887Sdim const SymExpr *getLHS() const { return LHS; } 448218887Sdim const SymExpr *getRHS() const { return RHS; } 449218887Sdim 450276479Sdim void dumpToStream(raw_ostream &os) const override; 451218887Sdim 452218887Sdim static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 453218887Sdim BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 454218887Sdim ID.AddInteger((unsigned) SymSymKind); 455218887Sdim ID.AddPointer(lhs); 456218887Sdim ID.AddInteger(op); 457218887Sdim ID.AddPointer(rhs); 458218887Sdim ID.Add(t); 459218887Sdim } 460218887Sdim 461276479Sdim void Profile(llvm::FoldingSetNodeID& ID) override { 462251662Sdim Profile(ID, LHS, getOpcode(), RHS, getType()); 463218887Sdim } 464218887Sdim 465218887Sdim // Implement isa<T> support. 466226633Sdim static inline bool classof(const SymExpr *SE) { 467218887Sdim return SE->getKind() == SymSymKind; 468218887Sdim } 469218887Sdim}; 470218887Sdim 471218887Sdimclass SymbolManager { 472218887Sdim typedef llvm::FoldingSet<SymExpr> DataSetTy; 473226633Sdim typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; 474226633Sdim 475218887Sdim DataSetTy DataSet; 476226633Sdim /// Stores the extra dependencies between symbols: the data should be kept 477226633Sdim /// alive as long as the key is live. 478226633Sdim SymbolDependTy SymbolDependencies; 479218887Sdim unsigned SymbolCounter; 480218887Sdim llvm::BumpPtrAllocator& BPAlloc; 481218887Sdim BasicValueFactory &BV; 482226633Sdim ASTContext &Ctx; 483218887Sdim 484218887Sdimpublic: 485226633Sdim SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 486218887Sdim llvm::BumpPtrAllocator& bpalloc) 487226633Sdim : SymbolDependencies(16), SymbolCounter(0), 488226633Sdim BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 489218887Sdim 490218887Sdim ~SymbolManager(); 491218887Sdim 492218887Sdim static bool canSymbolicate(QualType T); 493218887Sdim 494226633Sdim /// \brief Make a unique symbol for MemRegion R according to its kind. 495226633Sdim const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 496218887Sdim 497243830Sdim const SymbolConjured* conjureSymbol(const Stmt *E, 498243830Sdim const LocationContext *LCtx, 499243830Sdim QualType T, 500243830Sdim unsigned VisitCount, 501276479Sdim const void *SymbolTag = nullptr); 502218887Sdim 503243830Sdim const SymbolConjured* conjureSymbol(const Expr *E, 504243830Sdim const LocationContext *LCtx, 505243830Sdim unsigned VisitCount, 506276479Sdim const void *SymbolTag = nullptr) { 507243830Sdim return conjureSymbol(E, LCtx, E->getType(), 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. 519276479Sdim const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S, 520218887Sdim QualType T, unsigned VisitCount, 521276479Sdim const void *SymbolTag = nullptr); 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 { 542243830Sdim return SE->getType(); 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 556239462Sdim/// \brief A class responsible for cleaning up unused symbols. 557218887Sdimclass SymbolReaper { 558226633Sdim enum SymbolStatus { 559226633Sdim NotProcessed, 560226633Sdim HaveMarkedDependents 561226633Sdim }; 562218887Sdim 563226633Sdim typedef llvm::DenseSet<SymbolRef> SymbolSetTy; 564226633Sdim typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; 565226633Sdim typedef llvm::DenseSet<const MemRegion *> RegionSetTy; 566226633Sdim 567226633Sdim SymbolMapTy TheLiving; 568226633Sdim SymbolSetTy MetadataInUse; 569226633Sdim SymbolSetTy TheDead; 570226633Sdim 571226633Sdim RegionSetTy RegionRoots; 572226633Sdim 573239462Sdim const StackFrameContext *LCtx; 574218887Sdim const Stmt *Loc; 575218887Sdim SymbolManager& SymMgr; 576226633Sdim StoreRef reapedStore; 577226633Sdim llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 578218887Sdim 579218887Sdimpublic: 580239462Sdim /// \brief Construct a reaper object, which removes everything which is not 581239462Sdim /// live before we execute statement s in the given location context. 582239462Sdim /// 583239462Sdim /// If the statement is NULL, everything is this and parent contexts is 584239462Sdim /// considered live. 585243830Sdim /// If the stack frame context is NULL, everything on stack is considered 586243830Sdim /// dead. 587243830Sdim SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr, 588226633Sdim StoreManager &storeMgr) 589243830Sdim : LCtx(Ctx), Loc(s), SymMgr(symmgr), 590276479Sdim reapedStore(nullptr, storeMgr) {} 591218887Sdim 592218887Sdim ~SymbolReaper() {} 593218887Sdim 594218887Sdim const LocationContext *getLocationContext() const { return LCtx; } 595218887Sdim 596218887Sdim bool isLive(SymbolRef sym); 597226633Sdim bool isLiveRegion(const MemRegion *region); 598234353Sdim bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 599226633Sdim bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 600218887Sdim 601226633Sdim /// \brief Unconditionally marks a symbol as live. 602226633Sdim /// 603226633Sdim /// This should never be 604226633Sdim /// used by checkers, only by the state infrastructure such as the store and 605226633Sdim /// environment. Checkers should instead use metadata symbols and markInUse. 606218887Sdim void markLive(SymbolRef sym); 607218887Sdim 608226633Sdim /// \brief Marks a symbol as important to a checker. 609226633Sdim /// 610226633Sdim /// For metadata symbols, 611226633Sdim /// this will keep the symbol alive as long as its associated region is also 612226633Sdim /// live. For other symbols, this has no effect; checkers are not permitted 613226633Sdim /// to influence the life of other symbols. This should be used before any 614226633Sdim /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 615218887Sdim void markInUse(SymbolRef sym); 616218887Sdim 617226633Sdim /// \brief If a symbol is known to be live, marks the symbol as live. 618226633Sdim /// 619226633Sdim /// Otherwise, if the symbol cannot be proven live, it is marked as dead. 620226633Sdim /// Returns true if the symbol is dead, false if live. 621218887Sdim bool maybeDead(SymbolRef sym); 622218887Sdim 623226633Sdim typedef SymbolSetTy::const_iterator dead_iterator; 624218887Sdim dead_iterator dead_begin() const { return TheDead.begin(); } 625218887Sdim dead_iterator dead_end() const { return TheDead.end(); } 626218887Sdim 627218887Sdim bool hasDeadSymbols() const { 628218887Sdim return !TheDead.empty(); 629218887Sdim } 630226633Sdim 631226633Sdim typedef RegionSetTy::const_iterator region_iterator; 632226633Sdim region_iterator region_begin() const { return RegionRoots.begin(); } 633226633Sdim region_iterator region_end() const { return RegionRoots.end(); } 634218887Sdim 635226633Sdim /// \brief Returns whether or not a symbol has been confirmed dead. 636226633Sdim /// 637226633Sdim /// This should only be called once all marking of dead symbols has completed. 638226633Sdim /// (For checkers, this means only in the evalDeadSymbols callback.) 639218887Sdim bool isDead(SymbolRef sym) const { 640218887Sdim return TheDead.count(sym); 641218887Sdim } 642226633Sdim 643226633Sdim void markLive(const MemRegion *region); 644226633Sdim 645226633Sdim /// \brief Set to the value of the symbolic store after 646226633Sdim /// StoreManager::removeDeadBindings has been called. 647226633Sdim void setReapedStore(StoreRef st) { reapedStore = st; } 648226633Sdim 649226633Sdimprivate: 650226633Sdim /// Mark the symbols dependent on the input symbol as live. 651226633Sdim void markDependentsLive(SymbolRef sym); 652218887Sdim}; 653218887Sdim 654218887Sdimclass SymbolVisitor { 655218887Sdimpublic: 656226633Sdim /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. 657226633Sdim /// 658226633Sdim /// The method returns \c true if symbols should continue be scanned and \c 659226633Sdim /// false otherwise. 660218887Sdim virtual bool VisitSymbol(SymbolRef sym) = 0; 661226633Sdim virtual bool VisitMemRegion(const MemRegion *region) { return true; } 662218887Sdim virtual ~SymbolVisitor(); 663218887Sdim}; 664218887Sdim 665218887Sdim} // end GR namespace 666218887Sdim 667218887Sdim} // end clang namespace 668218887Sdim 669218887Sdimnamespace llvm { 670226633Sdimstatic inline raw_ostream &operator<<(raw_ostream &os, 671234353Sdim const clang::ento::SymExpr *SE) { 672218887Sdim SE->dumpToStream(os); 673218887Sdim return os; 674218887Sdim} 675218887Sdim} // end llvm namespace 676218887Sdim#endif 677