1 //== SymbolManager.h - Management of Symbolic Values ------------*- C++ -*--==// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines SymbolManager, a class that manages symbolic values 11 // created for use by ExprEngine and related classes. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_GR_SYMMGR_H 16 #define LLVM_CLANG_GR_SYMMGR_H 17 18 #include "clang/AST/Decl.h" 19 #include "clang/AST/Expr.h" 20 #include "clang/Analysis/AnalysisContext.h" 21 #include "clang/Basic/LLVM.h" 22 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/ADT/DenseSet.h" 25 #include "llvm/ADT/FoldingSet.h" 26 #include "llvm/Support/Allocator.h" 27 #include "llvm/Support/DataTypes.h" 28 29 namespace clang { 30 class ASTContext; 31 class StackFrameContext; 32 33 namespace ento { 34 class BasicValueFactory; 35 class MemRegion; 36 class SubRegion; 37 class TypedValueRegion; 38 class VarRegion; 39 40 /// \brief Symbolic value. These values used to capture symbolic execution of 41 /// the program. 42 class SymExpr : public llvm::FoldingSetNode { 43 virtual void anchor(); 44 public: 45 enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, 46 MetadataKind, 47 BEGIN_SYMBOLS = RegionValueKind, 48 END_SYMBOLS = MetadataKind, 49 SymIntKind, IntSymKind, SymSymKind, 50 BEGIN_BINARYSYMEXPRS = SymIntKind, 51 END_BINARYSYMEXPRS = SymSymKind, 52 CastSymbolKind }; 53 private: 54 Kind K; 55 56 protected: SymExpr(Kind k)57 SymExpr(Kind k) : K(k) {} 58 59 public: ~SymExpr()60 virtual ~SymExpr() {} 61 getKind()62 Kind getKind() const { return K; } 63 64 virtual void dump() const; 65 dumpToStream(raw_ostream & os)66 virtual void dumpToStream(raw_ostream &os) const {} 67 68 virtual QualType getType() const = 0; 69 virtual void Profile(llvm::FoldingSetNodeID& profile) = 0; 70 71 /// \brief Iterator over symbols that the current symbol depends on. 72 /// 73 /// For SymbolData, it's the symbol itself; for expressions, it's the 74 /// expression symbol and all the operands in it. Note, SymbolDerived is 75 /// treated as SymbolData - the iterator will NOT visit the parent region. 76 class symbol_iterator { 77 SmallVector<const SymExpr*, 5> itr; 78 void expand(); 79 public: symbol_iterator()80 symbol_iterator() {} 81 symbol_iterator(const SymExpr *SE); 82 83 symbol_iterator &operator++(); 84 const SymExpr* operator*(); 85 86 bool operator==(const symbol_iterator &X) const; 87 bool operator!=(const symbol_iterator &X) const; 88 }; 89 symbol_begin()90 symbol_iterator symbol_begin() const { 91 return symbol_iterator(this); 92 } symbol_end()93 static symbol_iterator symbol_end() { return symbol_iterator(); } 94 95 unsigned computeComplexity() const; 96 }; 97 98 typedef const SymExpr* SymbolRef; 99 typedef SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy; 100 101 typedef unsigned SymbolID; 102 /// \brief A symbol representing data which can be stored in a memory location 103 /// (region). 104 class SymbolData : public SymExpr { 105 void anchor() override; 106 const SymbolID Sym; 107 108 protected: SymbolData(Kind k,SymbolID sym)109 SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {} 110 111 public: ~SymbolData()112 virtual ~SymbolData() {} 113 getSymbolID()114 SymbolID getSymbolID() const { return Sym; } 115 116 // Implement isa<T> support. classof(const SymExpr * SE)117 static inline bool classof(const SymExpr *SE) { 118 Kind k = SE->getKind(); 119 return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; 120 } 121 }; 122 123 ///\brief A symbol representing the value stored at a MemRegion. 124 class SymbolRegionValue : public SymbolData { 125 const TypedValueRegion *R; 126 127 public: SymbolRegionValue(SymbolID sym,const TypedValueRegion * r)128 SymbolRegionValue(SymbolID sym, const TypedValueRegion *r) 129 : SymbolData(RegionValueKind, sym), R(r) {} 130 getRegion()131 const TypedValueRegion* getRegion() const { return R; } 132 Profile(llvm::FoldingSetNodeID & profile,const TypedValueRegion * R)133 static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) { 134 profile.AddInteger((unsigned) RegionValueKind); 135 profile.AddPointer(R); 136 } 137 Profile(llvm::FoldingSetNodeID & profile)138 void Profile(llvm::FoldingSetNodeID& profile) override { 139 Profile(profile, R); 140 } 141 142 void dumpToStream(raw_ostream &os) const override; 143 144 QualType getType() const override; 145 146 // Implement isa<T> support. classof(const SymExpr * SE)147 static inline bool classof(const SymExpr *SE) { 148 return SE->getKind() == RegionValueKind; 149 } 150 }; 151 152 /// A symbol representing the result of an expression in the case when we do 153 /// not know anything about what the expression is. 154 class SymbolConjured : public SymbolData { 155 const Stmt *S; 156 QualType T; 157 unsigned Count; 158 const LocationContext *LCtx; 159 const void *SymbolTag; 160 161 public: SymbolConjured(SymbolID sym,const Stmt * s,const LocationContext * lctx,QualType t,unsigned count,const void * symbolTag)162 SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx, 163 QualType t, unsigned count, 164 const void *symbolTag) 165 : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count), 166 LCtx(lctx), 167 SymbolTag(symbolTag) {} 168 getStmt()169 const Stmt *getStmt() const { return S; } getCount()170 unsigned getCount() const { return Count; } getTag()171 const void *getTag() const { return SymbolTag; } 172 173 QualType getType() const override; 174 175 void dumpToStream(raw_ostream &os) const override; 176 Profile(llvm::FoldingSetNodeID & profile,const Stmt * S,QualType T,unsigned Count,const LocationContext * LCtx,const void * SymbolTag)177 static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S, 178 QualType T, unsigned Count, const LocationContext *LCtx, 179 const void *SymbolTag) { 180 profile.AddInteger((unsigned) ConjuredKind); 181 profile.AddPointer(S); 182 profile.AddPointer(LCtx); 183 profile.Add(T); 184 profile.AddInteger(Count); 185 profile.AddPointer(SymbolTag); 186 } 187 Profile(llvm::FoldingSetNodeID & profile)188 void Profile(llvm::FoldingSetNodeID& profile) override { 189 Profile(profile, S, T, Count, LCtx, SymbolTag); 190 } 191 192 // Implement isa<T> support. classof(const SymExpr * SE)193 static inline bool classof(const SymExpr *SE) { 194 return SE->getKind() == ConjuredKind; 195 } 196 }; 197 198 /// A symbol representing the value of a MemRegion whose parent region has 199 /// symbolic value. 200 class SymbolDerived : public SymbolData { 201 SymbolRef parentSymbol; 202 const TypedValueRegion *R; 203 204 public: SymbolDerived(SymbolID sym,SymbolRef parent,const TypedValueRegion * r)205 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r) 206 : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {} 207 getParentSymbol()208 SymbolRef getParentSymbol() const { return parentSymbol; } getRegion()209 const TypedValueRegion *getRegion() const { return R; } 210 211 QualType getType() const override; 212 213 void dumpToStream(raw_ostream &os) const override; 214 Profile(llvm::FoldingSetNodeID & profile,SymbolRef parent,const TypedValueRegion * r)215 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent, 216 const TypedValueRegion *r) { 217 profile.AddInteger((unsigned) DerivedKind); 218 profile.AddPointer(r); 219 profile.AddPointer(parent); 220 } 221 Profile(llvm::FoldingSetNodeID & profile)222 void Profile(llvm::FoldingSetNodeID& profile) override { 223 Profile(profile, parentSymbol, R); 224 } 225 226 // Implement isa<T> support. classof(const SymExpr * SE)227 static inline bool classof(const SymExpr *SE) { 228 return SE->getKind() == DerivedKind; 229 } 230 }; 231 232 /// SymbolExtent - Represents the extent (size in bytes) of a bounded region. 233 /// Clients should not ask the SymbolManager for a region's extent. Always use 234 /// SubRegion::getExtent instead -- the value returned may not be a symbol. 235 class SymbolExtent : public SymbolData { 236 const SubRegion *R; 237 238 public: SymbolExtent(SymbolID sym,const SubRegion * r)239 SymbolExtent(SymbolID sym, const SubRegion *r) 240 : SymbolData(ExtentKind, sym), R(r) {} 241 getRegion()242 const SubRegion *getRegion() const { return R; } 243 244 QualType getType() const override; 245 246 void dumpToStream(raw_ostream &os) const override; 247 Profile(llvm::FoldingSetNodeID & profile,const SubRegion * R)248 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) { 249 profile.AddInteger((unsigned) ExtentKind); 250 profile.AddPointer(R); 251 } 252 Profile(llvm::FoldingSetNodeID & profile)253 void Profile(llvm::FoldingSetNodeID& profile) override { 254 Profile(profile, R); 255 } 256 257 // Implement isa<T> support. classof(const SymExpr * SE)258 static inline bool classof(const SymExpr *SE) { 259 return SE->getKind() == ExtentKind; 260 } 261 }; 262 263 /// SymbolMetadata - Represents path-dependent metadata about a specific region. 264 /// Metadata symbols remain live as long as they are marked as in use before 265 /// dead-symbol sweeping AND their associated regions are still alive. 266 /// Intended for use by checkers. 267 class SymbolMetadata : public SymbolData { 268 const MemRegion* R; 269 const Stmt *S; 270 QualType T; 271 unsigned Count; 272 const void *Tag; 273 public: SymbolMetadata(SymbolID sym,const MemRegion * r,const Stmt * s,QualType t,unsigned count,const void * tag)274 SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t, 275 unsigned count, const void *tag) 276 : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {} 277 getRegion()278 const MemRegion *getRegion() const { return R; } getStmt()279 const Stmt *getStmt() const { return S; } getCount()280 unsigned getCount() const { return Count; } getTag()281 const void *getTag() const { return Tag; } 282 283 QualType getType() const override; 284 285 void dumpToStream(raw_ostream &os) const override; 286 Profile(llvm::FoldingSetNodeID & profile,const MemRegion * R,const Stmt * S,QualType T,unsigned Count,const void * Tag)287 static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R, 288 const Stmt *S, QualType T, unsigned Count, 289 const void *Tag) { 290 profile.AddInteger((unsigned) MetadataKind); 291 profile.AddPointer(R); 292 profile.AddPointer(S); 293 profile.Add(T); 294 profile.AddInteger(Count); 295 profile.AddPointer(Tag); 296 } 297 Profile(llvm::FoldingSetNodeID & profile)298 void Profile(llvm::FoldingSetNodeID& profile) override { 299 Profile(profile, R, S, T, Count, Tag); 300 } 301 302 // Implement isa<T> support. classof(const SymExpr * SE)303 static inline bool classof(const SymExpr *SE) { 304 return SE->getKind() == MetadataKind; 305 } 306 }; 307 308 /// \brief Represents a cast expression. 309 class SymbolCast : public SymExpr { 310 const SymExpr *Operand; 311 /// Type of the operand. 312 QualType FromTy; 313 /// The type of the result. 314 QualType ToTy; 315 316 public: SymbolCast(const SymExpr * In,QualType From,QualType To)317 SymbolCast(const SymExpr *In, QualType From, QualType To) : 318 SymExpr(CastSymbolKind), Operand(In), FromTy(From), ToTy(To) { } 319 getType()320 QualType getType() const override { return ToTy; } 321 getOperand()322 const SymExpr *getOperand() const { return Operand; } 323 324 void dumpToStream(raw_ostream &os) const override; 325 Profile(llvm::FoldingSetNodeID & ID,const SymExpr * In,QualType From,QualType To)326 static void Profile(llvm::FoldingSetNodeID& ID, 327 const SymExpr *In, QualType From, QualType To) { 328 ID.AddInteger((unsigned) CastSymbolKind); 329 ID.AddPointer(In); 330 ID.Add(From); 331 ID.Add(To); 332 } 333 Profile(llvm::FoldingSetNodeID & ID)334 void Profile(llvm::FoldingSetNodeID& ID) override { 335 Profile(ID, Operand, FromTy, ToTy); 336 } 337 338 // Implement isa<T> support. classof(const SymExpr * SE)339 static inline bool classof(const SymExpr *SE) { 340 return SE->getKind() == CastSymbolKind; 341 } 342 }; 343 344 /// \brief Represents a symbolic expression involving a binary operator 345 class BinarySymExpr : public SymExpr { 346 BinaryOperator::Opcode Op; 347 QualType T; 348 349 protected: BinarySymExpr(Kind k,BinaryOperator::Opcode op,QualType t)350 BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t) 351 : SymExpr(k), Op(op), T(t) {} 352 353 public: 354 // FIXME: We probably need to make this out-of-line to avoid redundant 355 // generation of virtual functions. getType()356 QualType getType() const override { return T; } 357 getOpcode()358 BinaryOperator::Opcode getOpcode() const { return Op; } 359 360 // Implement isa<T> support. classof(const SymExpr * SE)361 static inline bool classof(const SymExpr *SE) { 362 Kind k = SE->getKind(); 363 return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; 364 } 365 }; 366 367 /// \brief Represents a symbolic expression like 'x' + 3. 368 class SymIntExpr : public BinarySymExpr { 369 const SymExpr *LHS; 370 const llvm::APSInt& RHS; 371 372 public: SymIntExpr(const SymExpr * lhs,BinaryOperator::Opcode op,const llvm::APSInt & rhs,QualType t)373 SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 374 const llvm::APSInt& rhs, QualType t) 375 : BinarySymExpr(SymIntKind, op, t), LHS(lhs), RHS(rhs) {} 376 377 void dumpToStream(raw_ostream &os) const override; 378 getLHS()379 const SymExpr *getLHS() const { return LHS; } getRHS()380 const llvm::APSInt &getRHS() const { return RHS; } 381 Profile(llvm::FoldingSetNodeID & ID,const SymExpr * lhs,BinaryOperator::Opcode op,const llvm::APSInt & rhs,QualType t)382 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 383 BinaryOperator::Opcode op, const llvm::APSInt& rhs, 384 QualType t) { 385 ID.AddInteger((unsigned) SymIntKind); 386 ID.AddPointer(lhs); 387 ID.AddInteger(op); 388 ID.AddPointer(&rhs); 389 ID.Add(t); 390 } 391 Profile(llvm::FoldingSetNodeID & ID)392 void Profile(llvm::FoldingSetNodeID& ID) override { 393 Profile(ID, LHS, getOpcode(), RHS, getType()); 394 } 395 396 // Implement isa<T> support. classof(const SymExpr * SE)397 static inline bool classof(const SymExpr *SE) { 398 return SE->getKind() == SymIntKind; 399 } 400 }; 401 402 /// \brief Represents a symbolic expression like 3 - 'x'. 403 class IntSymExpr : public BinarySymExpr { 404 const llvm::APSInt& LHS; 405 const SymExpr *RHS; 406 407 public: IntSymExpr(const llvm::APSInt & lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType t)408 IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op, 409 const SymExpr *rhs, QualType t) 410 : BinarySymExpr(IntSymKind, op, t), LHS(lhs), RHS(rhs) {} 411 412 void dumpToStream(raw_ostream &os) const override; 413 getRHS()414 const SymExpr *getRHS() const { return RHS; } getLHS()415 const llvm::APSInt &getLHS() const { return LHS; } 416 Profile(llvm::FoldingSetNodeID & ID,const llvm::APSInt & lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType t)417 static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs, 418 BinaryOperator::Opcode op, const SymExpr *rhs, 419 QualType t) { 420 ID.AddInteger((unsigned) IntSymKind); 421 ID.AddPointer(&lhs); 422 ID.AddInteger(op); 423 ID.AddPointer(rhs); 424 ID.Add(t); 425 } 426 Profile(llvm::FoldingSetNodeID & ID)427 void Profile(llvm::FoldingSetNodeID& ID) override { 428 Profile(ID, LHS, getOpcode(), RHS, getType()); 429 } 430 431 // Implement isa<T> support. classof(const SymExpr * SE)432 static inline bool classof(const SymExpr *SE) { 433 return SE->getKind() == IntSymKind; 434 } 435 }; 436 437 /// \brief Represents a symbolic expression like 'x' + 'y'. 438 class SymSymExpr : public BinarySymExpr { 439 const SymExpr *LHS; 440 const SymExpr *RHS; 441 442 public: SymSymExpr(const SymExpr * lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType t)443 SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, 444 QualType t) 445 : BinarySymExpr(SymSymKind, op, t), LHS(lhs), RHS(rhs) {} 446 getLHS()447 const SymExpr *getLHS() const { return LHS; } getRHS()448 const SymExpr *getRHS() const { return RHS; } 449 450 void dumpToStream(raw_ostream &os) const override; 451 Profile(llvm::FoldingSetNodeID & ID,const SymExpr * lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType t)452 static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs, 453 BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) { 454 ID.AddInteger((unsigned) SymSymKind); 455 ID.AddPointer(lhs); 456 ID.AddInteger(op); 457 ID.AddPointer(rhs); 458 ID.Add(t); 459 } 460 Profile(llvm::FoldingSetNodeID & ID)461 void Profile(llvm::FoldingSetNodeID& ID) override { 462 Profile(ID, LHS, getOpcode(), RHS, getType()); 463 } 464 465 // Implement isa<T> support. classof(const SymExpr * SE)466 static inline bool classof(const SymExpr *SE) { 467 return SE->getKind() == SymSymKind; 468 } 469 }; 470 471 class SymbolManager { 472 typedef llvm::FoldingSet<SymExpr> DataSetTy; 473 typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy; 474 475 DataSetTy DataSet; 476 /// Stores the extra dependencies between symbols: the data should be kept 477 /// alive as long as the key is live. 478 SymbolDependTy SymbolDependencies; 479 unsigned SymbolCounter; 480 llvm::BumpPtrAllocator& BPAlloc; 481 BasicValueFactory &BV; 482 ASTContext &Ctx; 483 484 public: SymbolManager(ASTContext & ctx,BasicValueFactory & bv,llvm::BumpPtrAllocator & bpalloc)485 SymbolManager(ASTContext &ctx, BasicValueFactory &bv, 486 llvm::BumpPtrAllocator& bpalloc) 487 : SymbolDependencies(16), SymbolCounter(0), 488 BPAlloc(bpalloc), BV(bv), Ctx(ctx) {} 489 490 ~SymbolManager(); 491 492 static bool canSymbolicate(QualType T); 493 494 /// \brief Make a unique symbol for MemRegion R according to its kind. 495 const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R); 496 497 const SymbolConjured* conjureSymbol(const Stmt *E, 498 const LocationContext *LCtx, 499 QualType T, 500 unsigned VisitCount, 501 const void *SymbolTag = nullptr); 502 503 const SymbolConjured* conjureSymbol(const Expr *E, 504 const LocationContext *LCtx, 505 unsigned VisitCount, 506 const void *SymbolTag = nullptr) { 507 return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag); 508 } 509 510 const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol, 511 const TypedValueRegion *R); 512 513 const SymbolExtent *getExtentSymbol(const SubRegion *R); 514 515 /// \brief Creates a metadata symbol associated with a specific region. 516 /// 517 /// VisitCount can be used to differentiate regions corresponding to 518 /// different loop iterations, thus, making the symbol path-dependent. 519 const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S, 520 QualType T, unsigned VisitCount, 521 const void *SymbolTag = nullptr); 522 523 const SymbolCast* getCastSymbol(const SymExpr *Operand, 524 QualType From, QualType To); 525 526 const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 527 const llvm::APSInt& rhs, QualType t); 528 getSymIntExpr(const SymExpr & lhs,BinaryOperator::Opcode op,const llvm::APSInt & rhs,QualType t)529 const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op, 530 const llvm::APSInt& rhs, QualType t) { 531 return getSymIntExpr(&lhs, op, rhs, t); 532 } 533 534 const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs, 535 BinaryOperator::Opcode op, 536 const SymExpr *rhs, QualType t); 537 538 const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, 539 const SymExpr *rhs, QualType t); 540 getType(const SymExpr * SE)541 QualType getType(const SymExpr *SE) const { 542 return SE->getType(); 543 } 544 545 /// \brief Add artificial symbol dependency. 546 /// 547 /// The dependent symbol should stay alive as long as the primary is alive. 548 void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent); 549 550 const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary); 551 getContext()552 ASTContext &getContext() { return Ctx; } getBasicVals()553 BasicValueFactory &getBasicVals() { return BV; } 554 }; 555 556 /// \brief A class responsible for cleaning up unused symbols. 557 class SymbolReaper { 558 enum SymbolStatus { 559 NotProcessed, 560 HaveMarkedDependents 561 }; 562 563 typedef llvm::DenseSet<SymbolRef> SymbolSetTy; 564 typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy; 565 typedef llvm::DenseSet<const MemRegion *> RegionSetTy; 566 567 SymbolMapTy TheLiving; 568 SymbolSetTy MetadataInUse; 569 SymbolSetTy TheDead; 570 571 RegionSetTy RegionRoots; 572 573 const StackFrameContext *LCtx; 574 const Stmt *Loc; 575 SymbolManager& SymMgr; 576 StoreRef reapedStore; 577 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; 578 579 public: 580 /// \brief Construct a reaper object, which removes everything which is not 581 /// live before we execute statement s in the given location context. 582 /// 583 /// If the statement is NULL, everything is this and parent contexts is 584 /// considered live. 585 /// If the stack frame context is NULL, everything on stack is considered 586 /// dead. SymbolReaper(const StackFrameContext * Ctx,const Stmt * s,SymbolManager & symmgr,StoreManager & storeMgr)587 SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr, 588 StoreManager &storeMgr) 589 : LCtx(Ctx), Loc(s), SymMgr(symmgr), 590 reapedStore(nullptr, storeMgr) {} 591 ~SymbolReaper()592 ~SymbolReaper() {} 593 getLocationContext()594 const LocationContext *getLocationContext() const { return LCtx; } 595 596 bool isLive(SymbolRef sym); 597 bool isLiveRegion(const MemRegion *region); 598 bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const; 599 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; 600 601 /// \brief Unconditionally marks a symbol as live. 602 /// 603 /// This should never be 604 /// used by checkers, only by the state infrastructure such as the store and 605 /// environment. Checkers should instead use metadata symbols and markInUse. 606 void markLive(SymbolRef sym); 607 608 /// \brief Marks a symbol as important to a checker. 609 /// 610 /// For metadata symbols, 611 /// this will keep the symbol alive as long as its associated region is also 612 /// live. For other symbols, this has no effect; checkers are not permitted 613 /// to influence the life of other symbols. This should be used before any 614 /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback. 615 void markInUse(SymbolRef sym); 616 617 /// \brief If a symbol is known to be live, marks the symbol as live. 618 /// 619 /// Otherwise, if the symbol cannot be proven live, it is marked as dead. 620 /// Returns true if the symbol is dead, false if live. 621 bool maybeDead(SymbolRef sym); 622 623 typedef SymbolSetTy::const_iterator dead_iterator; dead_begin()624 dead_iterator dead_begin() const { return TheDead.begin(); } dead_end()625 dead_iterator dead_end() const { return TheDead.end(); } 626 hasDeadSymbols()627 bool hasDeadSymbols() const { 628 return !TheDead.empty(); 629 } 630 631 typedef RegionSetTy::const_iterator region_iterator; region_begin()632 region_iterator region_begin() const { return RegionRoots.begin(); } region_end()633 region_iterator region_end() const { return RegionRoots.end(); } 634 635 /// \brief Returns whether or not a symbol has been confirmed dead. 636 /// 637 /// This should only be called once all marking of dead symbols has completed. 638 /// (For checkers, this means only in the evalDeadSymbols callback.) isDead(SymbolRef sym)639 bool isDead(SymbolRef sym) const { 640 return TheDead.count(sym); 641 } 642 643 void markLive(const MemRegion *region); 644 645 /// \brief Set to the value of the symbolic store after 646 /// StoreManager::removeDeadBindings has been called. setReapedStore(StoreRef st)647 void setReapedStore(StoreRef st) { reapedStore = st; } 648 649 private: 650 /// Mark the symbols dependent on the input symbol as live. 651 void markDependentsLive(SymbolRef sym); 652 }; 653 654 class SymbolVisitor { 655 public: 656 /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols. 657 /// 658 /// The method returns \c true if symbols should continue be scanned and \c 659 /// false otherwise. 660 virtual bool VisitSymbol(SymbolRef sym) = 0; VisitMemRegion(const MemRegion * region)661 virtual bool VisitMemRegion(const MemRegion *region) { return true; } 662 virtual ~SymbolVisitor(); 663 }; 664 665 } // end GR namespace 666 667 } // end clang namespace 668 669 namespace llvm { 670 static inline raw_ostream &operator<<(raw_ostream &os, 671 const clang::ento::SymExpr *SE) { 672 SE->dumpToStream(os); 673 return os; 674 } 675 } // end llvm namespace 676 #endif 677