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