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