contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h

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