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_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/DataTypes.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,
  53               BEGIN_BINARYSYMEXPRS = SymIntKind,
  54               END_BINARYSYMEXPRS = SymSymKind,
  55               CastSymbolKind };
  56 private:
  57   Kind K;
  58
  59 protected:
  60   SymExpr(Kind k) : K(k) {}
  61
  62 public:
  63   virtual ~SymExpr() {}
  64
  65   Kind getKind() const { return K; }
  66
  67   virtual void dump() const;
  68
  69   virtual void dumpToStream(raw_ostream &os) const {}
  70
  71   virtual QualType getType() const = 0;
  72   virtual void Profile(llvm::FoldingSetNodeID& profile) = 0;
  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 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() 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() 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() 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() 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() 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() 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 /// \brief Represents a symbolic expression involving a binary operator
 348 class BinarySymExpr : public SymExpr {
 349   BinaryOperator::Opcode Op;
 350   QualType T;
 351
 352 protected:
 353   BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
 354     : SymExpr(k), Op(op), T(t) {}
 355
 356 public:
 357   // FIXME: We probably need to make this out-of-line to avoid redundant
 358   // generation of virtual functions.
 359   QualType getType() const { return T; }
 360
 361   BinaryOperator::Opcode getOpcode() const { return Op; }
 362
 363   // Implement isa<T> support.
 364   static inline bool classof(const SymExpr *SE) {
 365     Kind k = SE->getKind();
 366     return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
 367   }
 368 };
 369
 370 /// \brief Represents a symbolic expression like 'x' + 3.
 371 class SymIntExpr : public BinarySymExpr {
 372   const SymExpr *LHS;
 373   const llvm::APSInt& RHS;
 374
 375 public:
 376   SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 377              const llvm::APSInt& rhs, QualType t)
 378     : BinarySymExpr(SymIntKind, op, t), LHS(lhs), RHS(rhs) {}
 379
 380   virtual void dumpToStream(raw_ostream &os) const;
 381
 382   const SymExpr *getLHS() const { return LHS; }
 383   const llvm::APSInt &getRHS() const { return RHS; }
 384
 385   static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
 386                       BinaryOperator::Opcode op, const llvm::APSInt& rhs,
 387                       QualType t) {
 388     ID.AddInteger((unsigned) SymIntKind);
 389     ID.AddPointer(lhs);
 390     ID.AddInteger(op);
 391     ID.AddPointer(&rhs);
 392     ID.Add(t);
 393   }
 394
 395   void Profile(llvm::FoldingSetNodeID& ID) {
 396     Profile(ID, LHS, getOpcode(), RHS, getType());
 397   }
 398
 399   // Implement isa<T> support.
 400   static inline bool classof(const SymExpr *SE) {
 401     return SE->getKind() == SymIntKind;
 402   }
 403 };
 404
 405 /// \brief Represents a symbolic expression like 3 - 'x'.
 406 class IntSymExpr : public BinarySymExpr {
 407   const llvm::APSInt& LHS;
 408   const SymExpr *RHS;
 409
 410 public:
 411   IntSymExpr(const llvm::APSInt& lhs, BinaryOperator::Opcode op,
 412              const SymExpr *rhs, QualType t)
 413     : BinarySymExpr(IntSymKind, op, t), LHS(lhs), RHS(rhs) {}
 414
 415   virtual void dumpToStream(raw_ostream &os) const;
 416
 417   const SymExpr *getRHS() const { return RHS; }
 418   const llvm::APSInt &getLHS() const { return LHS; }
 419
 420   static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
 421                       BinaryOperator::Opcode op, const SymExpr *rhs,
 422                       QualType t) {
 423     ID.AddInteger((unsigned) IntSymKind);
 424     ID.AddPointer(&lhs);
 425     ID.AddInteger(op);
 426     ID.AddPointer(rhs);
 427     ID.Add(t);
 428   }
 429
 430   void Profile(llvm::FoldingSetNodeID& ID) {
 431     Profile(ID, LHS, getOpcode(), RHS, getType());
 432   }
 433
 434   // Implement isa<T> support.
 435   static inline bool classof(const SymExpr *SE) {
 436     return SE->getKind() == IntSymKind;
 437   }
 438 };
 439
 440 /// \brief Represents a symbolic expression like 'x' + 'y'.
 441 class SymSymExpr : public BinarySymExpr {
 442   const SymExpr *LHS;
 443   const SymExpr *RHS;
 444
 445 public:
 446   SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
 447              QualType t)
 448     : BinarySymExpr(SymSymKind, op, t), LHS(lhs), RHS(rhs) {}
 449
 450   const SymExpr *getLHS() const { return LHS; }
 451   const SymExpr *getRHS() const { return RHS; }
 452
 453   virtual void dumpToStream(raw_ostream &os) const;
 454
 455   static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
 456                     BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
 457     ID.AddInteger((unsigned) SymSymKind);
 458     ID.AddPointer(lhs);
 459     ID.AddInteger(op);
 460     ID.AddPointer(rhs);
 461     ID.Add(t);
 462   }
 463
 464   void Profile(llvm::FoldingSetNodeID& ID) {
 465     Profile(ID, LHS, getOpcode(), RHS, getType());
 466   }
 467
 468   // Implement isa<T> support.
 469   static inline bool classof(const SymExpr *SE) {
 470     return SE->getKind() == SymSymKind;
 471   }
 472 };
 473
 474 class SymbolManager {
 475   typedef llvm::FoldingSet<SymExpr> DataSetTy;
 476   typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy;
 477
 478   DataSetTy DataSet;
 479   /// Stores the extra dependencies between symbols: the data should be kept
 480   /// alive as long as the key is live.
 481   SymbolDependTy SymbolDependencies;
 482   unsigned SymbolCounter;
 483   llvm::BumpPtrAllocator& BPAlloc;
 484   BasicValueFactory &BV;
 485   ASTContext &Ctx;
 486
 487 public:
 488   SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
 489                 llvm::BumpPtrAllocator& bpalloc)
 490     : SymbolDependencies(16), SymbolCounter(0),
 491       BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
 492
 493   ~SymbolManager();
 494
 495   static bool canSymbolicate(QualType T);
 496
 497   /// \brief Make a unique symbol for MemRegion R according to its kind.
 498   const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
 499
 500   const SymbolConjured* conjureSymbol(const Stmt *E,
 501                                       const LocationContext *LCtx,
 502                                       QualType T,
 503                                       unsigned VisitCount,
 504                                       const void *SymbolTag = 0);
 505
 506   const SymbolConjured* conjureSymbol(const Expr *E,
 507                                       const LocationContext *LCtx,
 508                                       unsigned VisitCount,
 509                                       const void *SymbolTag = 0) {
 510     return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
 511   }
 512
 513   const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
 514                                         const TypedValueRegion *R);
 515
 516   const SymbolExtent *getExtentSymbol(const SubRegion *R);
 517
 518   /// \brief Creates a metadata symbol associated with a specific region.
 519   ///
 520   /// VisitCount can be used to differentiate regions corresponding to
 521   /// different loop iterations, thus, making the symbol path-dependent.
 522   const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt *S,
 523                                           QualType T, unsigned VisitCount,
 524                                           const void *SymbolTag = 0);
 525
 526   const SymbolCast* getCastSymbol(const SymExpr *Operand,
 527                                   QualType From, QualType To);
 528
 529   const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 530                                   const llvm::APSInt& rhs, QualType t);
 531
 532   const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
 533                                   const llvm::APSInt& rhs, QualType t) {
 534     return getSymIntExpr(&lhs, op, rhs, t);
 535   }
 536
 537   const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
 538                                   BinaryOperator::Opcode op,
 539                                   const SymExpr *rhs, QualType t);
 540
 541   const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 542                                   const SymExpr *rhs, QualType t);
 543
 544   QualType getType(const SymExpr *SE) const {
 545     return SE->getType();
 546   }
 547
 548   /// \brief Add artificial symbol dependency.
 549   ///
 550   /// The dependent symbol should stay alive as long as the primary is alive.
 551   void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
 552
 553   const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
 554
 555   ASTContext &getContext() { return Ctx; }
 556   BasicValueFactory &getBasicVals() { return BV; }
 557 };
 558
 559 /// \brief A class responsible for cleaning up unused symbols.
 560 class SymbolReaper {
 561   enum SymbolStatus {
 562     NotProcessed,
 563     HaveMarkedDependents
 564   };
 565
 566   typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
 567   typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy;
 568   typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
 569
 570   SymbolMapTy TheLiving;
 571   SymbolSetTy MetadataInUse;
 572   SymbolSetTy TheDead;
 573
 574   RegionSetTy RegionRoots;
 575
 576   const StackFrameContext *LCtx;
 577   const Stmt *Loc;
 578   SymbolManager& SymMgr;
 579   StoreRef reapedStore;
 580   llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
 581
 582 public:
 583   /// \brief Construct a reaper object, which removes everything which is not
 584   /// live before we execute statement s in the given location context.
 585   ///
 586   /// If the statement is NULL, everything is this and parent contexts is
 587   /// considered live.
 588   /// If the stack frame context is NULL, everything on stack is considered
 589   /// dead.
 590   SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr,
 591                StoreManager &storeMgr)
 592    : LCtx(Ctx), Loc(s), SymMgr(symmgr),
 593      reapedStore(0, storeMgr) {}
 594
 595   ~SymbolReaper() {}
 596
 597   const LocationContext *getLocationContext() const { return LCtx; }
 598
 599   bool isLive(SymbolRef sym);
 600   bool isLiveRegion(const MemRegion *region);
 601   bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
 602   bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
 603
 604   /// \brief Unconditionally marks a symbol as live.
 605   ///
 606   /// This should never be
 607   /// used by checkers, only by the state infrastructure such as the store and
 608   /// environment. Checkers should instead use metadata symbols and markInUse.
 609   void markLive(SymbolRef sym);
 610
 611   /// \brief Marks a symbol as important to a checker.
 612   ///
 613   /// For metadata symbols,
 614   /// this will keep the symbol alive as long as its associated region is also
 615   /// live. For other symbols, this has no effect; checkers are not permitted
 616   /// to influence the life of other symbols. This should be used before any
 617   /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
 618   void markInUse(SymbolRef sym);
 619
 620   /// \brief If a symbol is known to be live, marks the symbol as live.
 621   ///
 622   ///  Otherwise, if the symbol cannot be proven live, it is marked as dead.
 623   ///  Returns true if the symbol is dead, false if live.
 624   bool maybeDead(SymbolRef sym);
 625
 626   typedef SymbolSetTy::const_iterator dead_iterator;
 627   dead_iterator dead_begin() const { return TheDead.begin(); }
 628   dead_iterator dead_end() const { return TheDead.end(); }
 629
 630   bool hasDeadSymbols() const {
 631     return !TheDead.empty();
 632   }
 633
 634   typedef RegionSetTy::const_iterator region_iterator;
 635   region_iterator region_begin() const { return RegionRoots.begin(); }
 636   region_iterator region_end() const { return RegionRoots.end(); }
 637
 638   /// \brief Returns whether or not a symbol has been confirmed dead.
 639   ///
 640   /// This should only be called once all marking of dead symbols has completed.
 641   /// (For checkers, this means only in the evalDeadSymbols callback.)
 642   bool isDead(SymbolRef sym) const {
 643     return TheDead.count(sym);
 644   }
 645
 646   void markLive(const MemRegion *region);
 647
 648   /// \brief Set to the value of the symbolic store after
 649   /// StoreManager::removeDeadBindings has been called.
 650   void setReapedStore(StoreRef st) { reapedStore = st; }
 651
 652 private:
 653   /// Mark the symbols dependent on the input symbol as live.
 654   void markDependentsLive(SymbolRef sym);
 655 };
 656
 657 class SymbolVisitor {
 658 public:
 659   /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols.
 660   ///
 661   /// The method returns \c true if symbols should continue be scanned and \c
 662   /// false otherwise.
 663   virtual bool VisitSymbol(SymbolRef sym) = 0;
 664   virtual bool VisitMemRegion(const MemRegion *region) { return true; }
 665   virtual ~SymbolVisitor();
 666 };
 667
 668 } // end GR namespace
 669
 670 } // end clang namespace
 671
 672 namespace llvm {
 673 static inline raw_ostream &operator<<(raw_ostream &os,
 674                                       const clang::ento::SymExpr *SE) {
 675   SE->dumpToStream(os);
 676   return os;
 677 }
 678 } // end llvm namespace
 679 #endif