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