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/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 class SymExpr : public llvm::FoldingSetNode {
  44 public:
  45   enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind,
  46               MetadataKind,
  47               BEGIN_SYMBOLS = RegionValueKind,
  48               END_SYMBOLS = MetadataKind,
  49               SymIntKind, SymSymKind };
  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   void dump() const;
  62
  63   virtual void dumpToStream(raw_ostream &os) const = 0;
  64
  65   virtual QualType getType(ASTContext&) const = 0;
  66   virtual void Profile(llvm::FoldingSetNodeID& profile) = 0;
  67
  68   // Implement isa<T> support.
  69   static inline bool classof(const SymExpr*) { return true; }
  70 };
  71
  72 typedef unsigned SymbolID;
  73
  74 class SymbolData : public SymExpr {
  75 private:
  76   const SymbolID Sym;
  77
  78 protected:
  79   SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {}
  80
  81 public:
  82   virtual ~SymbolData() {}
  83
  84   SymbolID getSymbolID() const { return Sym; }
  85
  86   // Implement isa<T> support.
  87   static inline bool classof(const SymExpr *SE) {
  88     Kind k = SE->getKind();
  89     return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
  90   }
  91 };
  92
  93 typedef const SymbolData* SymbolRef;
  94 typedef llvm::SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy;
  95
  96 /// A symbol representing the value of a MemRegion.
  97 class SymbolRegionValue : public SymbolData {
  98   const TypedValueRegion *R;
  99
 100 public:
 101   SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
 102     : SymbolData(RegionValueKind, sym), R(r) {}
 103
 104   const TypedValueRegion* getRegion() const { return R; }
 105
 106   static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
 107     profile.AddInteger((unsigned) RegionValueKind);
 108     profile.AddPointer(R);
 109   }
 110
 111   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 112     Profile(profile, R);
 113   }
 114
 115   void dumpToStream(raw_ostream &os) const;
 116
 117   QualType getType(ASTContext&) const;
 118
 119   // Implement isa<T> support.
 120   static inline bool classof(const SymExpr *SE) {
 121     return SE->getKind() == RegionValueKind;
 122   }
 123 };
 124
 125 /// A symbol representing the result of an expression.
 126 class SymbolConjured : public SymbolData {
 127   const Stmt *S;
 128   QualType T;
 129   unsigned Count;
 130   const void *SymbolTag;
 131
 132 public:
 133   SymbolConjured(SymbolID sym, const Stmt *s, QualType t, unsigned count,
 134                  const void *symbolTag)
 135     : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count),
 136       SymbolTag(symbolTag) {}
 137
 138   const Stmt *getStmt() const { return S; }
 139   unsigned getCount() const { return Count; }
 140   const void *getTag() const { return SymbolTag; }
 141
 142   QualType getType(ASTContext&) const;
 143
 144   void dumpToStream(raw_ostream &os) const;
 145
 146   static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
 147                       QualType T, unsigned Count, const void *SymbolTag) {
 148     profile.AddInteger((unsigned) ConjuredKind);
 149     profile.AddPointer(S);
 150     profile.Add(T);
 151     profile.AddInteger(Count);
 152     profile.AddPointer(SymbolTag);
 153   }
 154
 155   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 156     Profile(profile, S, T, Count, SymbolTag);
 157   }
 158
 159   // Implement isa<T> support.
 160   static inline bool classof(const SymExpr *SE) {
 161     return SE->getKind() == ConjuredKind;
 162   }
 163 };
 164
 165 /// A symbol representing the value of a MemRegion whose parent region has
 166 /// symbolic value.
 167 class SymbolDerived : public SymbolData {
 168   SymbolRef parentSymbol;
 169   const TypedValueRegion *R;
 170
 171 public:
 172   SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
 173     : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {}
 174
 175   SymbolRef getParentSymbol() const { return parentSymbol; }
 176   const TypedValueRegion *getRegion() const { return R; }
 177
 178   QualType getType(ASTContext&) const;
 179
 180   void dumpToStream(raw_ostream &os) const;
 181
 182   static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
 183                       const TypedValueRegion *r) {
 184     profile.AddInteger((unsigned) DerivedKind);
 185     profile.AddPointer(r);
 186     profile.AddPointer(parent);
 187   }
 188
 189   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 190     Profile(profile, parentSymbol, R);
 191   }
 192
 193   // Implement isa<T> support.
 194   static inline bool classof(const SymExpr *SE) {
 195     return SE->getKind() == DerivedKind;
 196   }
 197 };
 198
 199 /// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
 200 ///  Clients should not ask the SymbolManager for a region's extent. Always use
 201 ///  SubRegion::getExtent instead -- the value returned may not be a symbol.
 202 class SymbolExtent : public SymbolData {
 203   const SubRegion *R;
 204
 205 public:
 206   SymbolExtent(SymbolID sym, const SubRegion *r)
 207   : SymbolData(ExtentKind, sym), R(r) {}
 208
 209   const SubRegion *getRegion() const { return R; }
 210
 211   QualType getType(ASTContext&) const;
 212
 213   void dumpToStream(raw_ostream &os) const;
 214
 215   static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
 216     profile.AddInteger((unsigned) ExtentKind);
 217     profile.AddPointer(R);
 218   }
 219
 220   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 221     Profile(profile, R);
 222   }
 223
 224   // Implement isa<T> support.
 225   static inline bool classof(const SymExpr *SE) {
 226     return SE->getKind() == ExtentKind;
 227   }
 228 };
 229
 230 /// SymbolMetadata - Represents path-dependent metadata about a specific region.
 231 ///  Metadata symbols remain live as long as they are marked as in use before
 232 ///  dead-symbol sweeping AND their associated regions are still alive.
 233 ///  Intended for use by checkers.
 234 class SymbolMetadata : public SymbolData {
 235   const MemRegion* R;
 236   const Stmt *S;
 237   QualType T;
 238   unsigned Count;
 239   const void *Tag;
 240 public:
 241   SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t,
 242                  unsigned count, const void *tag)
 243   : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {}
 244
 245   const MemRegion *getRegion() const { return R; }
 246   const Stmt *getStmt() const { return S; }
 247   unsigned getCount() const { return Count; }
 248   const void *getTag() const { return Tag; }
 249
 250   QualType getType(ASTContext&) const;
 251
 252   void dumpToStream(raw_ostream &os) const;
 253
 254   static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
 255                       const Stmt *S, QualType T, unsigned Count,
 256                       const void *Tag) {
 257     profile.AddInteger((unsigned) MetadataKind);
 258     profile.AddPointer(R);
 259     profile.AddPointer(S);
 260     profile.Add(T);
 261     profile.AddInteger(Count);
 262     profile.AddPointer(Tag);
 263   }
 264
 265   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 266     Profile(profile, R, S, T, Count, Tag);
 267   }
 268
 269   // Implement isa<T> support.
 270   static inline bool classof(const SymExpr *SE) {
 271     return SE->getKind() == MetadataKind;
 272   }
 273 };
 274
 275 /// SymIntExpr - Represents symbolic expression like 'x' + 3.
 276 class SymIntExpr : public SymExpr {
 277   const SymExpr *LHS;
 278   BinaryOperator::Opcode Op;
 279   const llvm::APSInt& RHS;
 280   QualType T;
 281
 282 public:
 283   SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 284              const llvm::APSInt& rhs, QualType t)
 285     : SymExpr(SymIntKind), LHS(lhs), Op(op), RHS(rhs), T(t) {}
 286
 287   // FIXME: We probably need to make this out-of-line to avoid redundant
 288   // generation of virtual functions.
 289   QualType getType(ASTContext &C) const { return T; }
 290
 291   BinaryOperator::Opcode getOpcode() const { return Op; }
 292
 293   void dumpToStream(raw_ostream &os) const;
 294
 295   const SymExpr *getLHS() const { return LHS; }
 296   const llvm::APSInt &getRHS() const { return RHS; }
 297
 298   static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
 299                       BinaryOperator::Opcode op, const llvm::APSInt& rhs,
 300                       QualType t) {
 301     ID.AddInteger((unsigned) SymIntKind);
 302     ID.AddPointer(lhs);
 303     ID.AddInteger(op);
 304     ID.AddPointer(&rhs);
 305     ID.Add(t);
 306   }
 307
 308   void Profile(llvm::FoldingSetNodeID& ID) {
 309     Profile(ID, LHS, Op, RHS, T);
 310   }
 311
 312   // Implement isa<T> support.
 313   static inline bool classof(const SymExpr *SE) {
 314     return SE->getKind() == SymIntKind;
 315   }
 316 };
 317
 318 /// SymSymExpr - Represents symbolic expression like 'x' + 'y'.
 319 class SymSymExpr : public SymExpr {
 320   const SymExpr *LHS;
 321   BinaryOperator::Opcode Op;
 322   const SymExpr *RHS;
 323   QualType T;
 324
 325 public:
 326   SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
 327              QualType t)
 328     : SymExpr(SymSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {}
 329
 330   BinaryOperator::Opcode getOpcode() const { return Op; }
 331   const SymExpr *getLHS() const { return LHS; }
 332   const SymExpr *getRHS() const { return RHS; }
 333
 334   // FIXME: We probably need to make this out-of-line to avoid redundant
 335   // generation of virtual functions.
 336   QualType getType(ASTContext &C) const { return T; }
 337
 338   void dumpToStream(raw_ostream &os) const;
 339
 340   static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
 341                     BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
 342     ID.AddInteger((unsigned) SymSymKind);
 343     ID.AddPointer(lhs);
 344     ID.AddInteger(op);
 345     ID.AddPointer(rhs);
 346     ID.Add(t);
 347   }
 348
 349   void Profile(llvm::FoldingSetNodeID& ID) {
 350     Profile(ID, LHS, Op, RHS, T);
 351   }
 352
 353   // Implement isa<T> support.
 354   static inline bool classof(const SymExpr *SE) {
 355     return SE->getKind() == SymSymKind;
 356   }
 357 };
 358
 359 class SymbolManager {
 360   typedef llvm::FoldingSet<SymExpr> DataSetTy;
 361   typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy;
 362
 363   DataSetTy DataSet;
 364   /// Stores the extra dependencies between symbols: the data should be kept
 365   /// alive as long as the key is live.
 366   SymbolDependTy SymbolDependencies;
 367   unsigned SymbolCounter;
 368   llvm::BumpPtrAllocator& BPAlloc;
 369   BasicValueFactory &BV;
 370   ASTContext &Ctx;
 371
 372 public:
 373   SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
 374                 llvm::BumpPtrAllocator& bpalloc)
 375     : SymbolDependencies(16), SymbolCounter(0),
 376       BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
 377
 378   ~SymbolManager();
 379
 380   static bool canSymbolicate(QualType T);
 381
 382   /// \brief Make a unique symbol for MemRegion R according to its kind.
 383   const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
 384
 385   const SymbolConjured* getConjuredSymbol(const Stmt *E, QualType T,
 386                                           unsigned VisitCount,
 387                                           const void *SymbolTag = 0);
 388
 389   const SymbolConjured* getConjuredSymbol(const Expr *E, unsigned VisitCount,
 390                                           const void *SymbolTag = 0) {
 391     return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag);
 392   }
 393
 394   const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
 395                                         const TypedValueRegion *R);
 396
 397   const SymbolExtent *getExtentSymbol(const SubRegion *R);
 398
 399   /// \brief Creates a metadata symbol associated with a specific region.
 400   ///
 401   /// VisitCount can be used to differentiate regions corresponding to
 402   /// different loop iterations, thus, making the symbol path-dependent.
 403   const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt *S,
 404                                           QualType T, unsigned VisitCount,
 405                                           const void *SymbolTag = 0);
 406
 407   const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 408                                   const llvm::APSInt& rhs, QualType t);
 409
 410   const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
 411                                   const llvm::APSInt& rhs, QualType t) {
 412     return getSymIntExpr(&lhs, op, rhs, t);
 413   }
 414
 415   const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 416                                   const SymExpr *rhs, QualType t);
 417
 418   QualType getType(const SymExpr *SE) const {
 419     return SE->getType(Ctx);
 420   }
 421
 422   /// \brief Add artificial symbol dependency.
 423   ///
 424   /// The dependent symbol should stay alive as long as the primary is alive.
 425   void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
 426
 427   const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
 428
 429   ASTContext &getContext() { return Ctx; }
 430   BasicValueFactory &getBasicVals() { return BV; }
 431 };
 432
 433 class SymbolReaper {
 434   enum SymbolStatus {
 435     NotProcessed,
 436     HaveMarkedDependents
 437   };
 438
 439   typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
 440   typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy;
 441   typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
 442
 443   SymbolMapTy TheLiving;
 444   SymbolSetTy MetadataInUse;
 445   SymbolSetTy TheDead;
 446
 447   RegionSetTy RegionRoots;
 448
 449   const LocationContext *LCtx;
 450   const Stmt *Loc;
 451   SymbolManager& SymMgr;
 452   StoreRef reapedStore;
 453   llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
 454
 455 public:
 456   SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr,
 457                StoreManager &storeMgr)
 458    : LCtx(ctx), Loc(s), SymMgr(symmgr), reapedStore(0, storeMgr) {}
 459
 460   ~SymbolReaper() {}
 461
 462   const LocationContext *getLocationContext() const { return LCtx; }
 463   const Stmt *getCurrentStatement() const { return Loc; }
 464
 465   bool isLive(SymbolRef sym);
 466   bool isLiveRegion(const MemRegion *region);
 467   bool isLive(const Stmt *ExprVal) const;
 468   bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
 469
 470   /// \brief Unconditionally marks a symbol as live.
 471   ///
 472   /// This should never be
 473   /// used by checkers, only by the state infrastructure such as the store and
 474   /// environment. Checkers should instead use metadata symbols and markInUse.
 475   void markLive(SymbolRef sym);
 476
 477   /// \brief Marks a symbol as important to a checker.
 478   ///
 479   /// For metadata symbols,
 480   /// this will keep the symbol alive as long as its associated region is also
 481   /// live. For other symbols, this has no effect; checkers are not permitted
 482   /// to influence the life of other symbols. This should be used before any
 483   /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
 484   void markInUse(SymbolRef sym);
 485
 486   /// \brief If a symbol is known to be live, marks the symbol as live.
 487   ///
 488   ///  Otherwise, if the symbol cannot be proven live, it is marked as dead.
 489   ///  Returns true if the symbol is dead, false if live.
 490   bool maybeDead(SymbolRef sym);
 491
 492   typedef SymbolSetTy::const_iterator dead_iterator;
 493   dead_iterator dead_begin() const { return TheDead.begin(); }
 494   dead_iterator dead_end() const { return TheDead.end(); }
 495
 496   bool hasDeadSymbols() const {
 497     return !TheDead.empty();
 498   }
 499
 500   typedef RegionSetTy::const_iterator region_iterator;
 501   region_iterator region_begin() const { return RegionRoots.begin(); }
 502   region_iterator region_end() const { return RegionRoots.end(); }
 503
 504   /// \brief Returns whether or not a symbol has been confirmed dead.
 505   ///
 506   /// This should only be called once all marking of dead symbols has completed.
 507   /// (For checkers, this means only in the evalDeadSymbols callback.)
 508   bool isDead(SymbolRef sym) const {
 509     return TheDead.count(sym);
 510   }
 511
 512   void markLive(const MemRegion *region);
 513
 514   /// \brief Set to the value of the symbolic store after
 515   /// StoreManager::removeDeadBindings has been called.
 516   void setReapedStore(StoreRef st) { reapedStore = st; }
 517
 518 private:
 519   /// Mark the symbols dependent on the input symbol as live.
 520   void markDependentsLive(SymbolRef sym);
 521 };
 522
 523 class SymbolVisitor {
 524 public:
 525   /// \brief A visitor method invoked by ProgramStateManager::scanReachableSymbols.
 526   ///
 527   /// The method returns \c true if symbols should continue be scanned and \c
 528   /// false otherwise.
 529   virtual bool VisitSymbol(SymbolRef sym) = 0;
 530   virtual bool VisitMemRegion(const MemRegion *region) { return true; }
 531   virtual ~SymbolVisitor();
 532 };
 533
 534 } // end GR namespace
 535
 536 } // end clang namespace
 537
 538 namespace llvm {
 539 static inline raw_ostream &operator<<(raw_ostream &os,
 540                                             const clang::ento::SymExpr *SE) {
 541   SE->dumpToStream(os);
 542   return os;
 543 }
 544 } // end llvm namespace
 545 #endif