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