include/clang/GR/PathSensitive/MemRegion.h

   1 //== MemRegion.h - Abstract memory regions for static analysis --*- 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 MemRegion and its subclasses.  MemRegion defines a
  11 //  partially-typed abstraction of memory useful for path-sensitive dataflow
  12 //  analyses.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CLANG_ANALYSIS_MEMREGION_H
  17 #define LLVM_CLANG_ANALYSIS_MEMREGION_H
  18
  19 #include "clang/AST/Decl.h"
  20 #include "clang/AST/DeclObjC.h"
  21 #include "clang/GR/PathSensitive/SVals.h"
  22 #include "llvm/Support/Casting.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24 #include "llvm/ADT/FoldingSet.h"
  25 #include <string>
  26
  27 namespace llvm {
  28 class BumpPtrAllocator;
  29 class raw_ostream;
  30 }
  31
  32 namespace clang {
  33
  34 class MemRegionManager;
  35 class MemSpaceRegion;
  36 class LocationContext;
  37 class StackFrameContext;
  38 class SValBuilder;
  39 class VarRegion;
  40 class CodeTextRegion;
  41
  42 /// Represent a region's offset within the top level base region.
  43 class RegionOffset {
  44   /// The base region.
  45   const MemRegion *R;
  46
  47   /// The bit offset within the base region. It shouldn't be negative.
  48   int64_t Offset;
  49
  50 public:
  51   RegionOffset(const MemRegion *r) : R(r), Offset(0) {}
  52   RegionOffset(const MemRegion *r, int64_t off) : R(r), Offset(off) {}
  53
  54   const MemRegion *getRegion() const { return R; }
  55   int64_t getOffset() const { return Offset; }
  56 };
  57
  58 //===----------------------------------------------------------------------===//
  59 // Base region classes.
  60 //===----------------------------------------------------------------------===//
  61
  62 /// MemRegion - The root abstract class for all memory regions.
  63 class MemRegion : public llvm::FoldingSetNode {
  64   friend class MemRegionManager;
  65 public:
  66   enum Kind {
  67     // Memory spaces.
  68     GenericMemSpaceRegionKind,
  69     StackLocalsSpaceRegionKind,
  70     StackArgumentsSpaceRegionKind,
  71     HeapSpaceRegionKind,
  72     UnknownSpaceRegionKind,
  73     NonStaticGlobalSpaceRegionKind,
  74     StaticGlobalSpaceRegionKind,
  75     BEG_GLOBAL_MEMSPACES = NonStaticGlobalSpaceRegionKind,
  76     END_GLOBAL_MEMSPACES = StaticGlobalSpaceRegionKind,
  77     BEG_MEMSPACES = GenericMemSpaceRegionKind,
  78     END_MEMSPACES = StaticGlobalSpaceRegionKind,
  79     // Untyped regions.
  80     SymbolicRegionKind,
  81     AllocaRegionKind,
  82     // Typed regions.
  83     BEG_TYPED_REGIONS,
  84     FunctionTextRegionKind = BEG_TYPED_REGIONS,
  85     BlockTextRegionKind,
  86     BlockDataRegionKind,
  87     CompoundLiteralRegionKind,
  88     CXXThisRegionKind,
  89     StringRegionKind,
  90     ElementRegionKind,
  91     // Decl Regions.
  92     BEG_DECL_REGIONS,
  93     VarRegionKind = BEG_DECL_REGIONS,
  94     FieldRegionKind,
  95     ObjCIvarRegionKind,
  96     END_DECL_REGIONS = ObjCIvarRegionKind,
  97     CXXTempObjectRegionKind,
  98     CXXBaseObjectRegionKind,
  99     END_TYPED_REGIONS = CXXBaseObjectRegionKind
 100   };
 101
 102 private:
 103   const Kind kind;
 104
 105 protected:
 106   MemRegion(Kind k) : kind(k) {}
 107   virtual ~MemRegion();
 108
 109 public:
 110   ASTContext &getContext() const;
 111
 112   virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0;
 113
 114   virtual MemRegionManager* getMemRegionManager() const = 0;
 115
 116   std::string getString() const;
 117
 118   const MemSpaceRegion *getMemorySpace() const;
 119
 120   const MemRegion *getBaseRegion() const;
 121
 122   const MemRegion *StripCasts() const;
 123
 124   bool hasGlobalsOrParametersStorage() const;
 125
 126   bool hasStackStorage() const;
 127
 128   bool hasStackNonParametersStorage() const;
 129
 130   bool hasStackParametersStorage() const;
 131
 132   /// Compute the offset within the top level memory object.
 133   RegionOffset getAsOffset() const;
 134
 135   virtual void dumpToStream(llvm::raw_ostream& os) const;
 136
 137   void dump() const;
 138
 139   Kind getKind() const { return kind; }
 140
 141   template<typename RegionTy> const RegionTy* getAs() const;
 142
 143   virtual bool isBoundable() const { return false; }
 144
 145   static bool classof(const MemRegion*) { return true; }
 146 };
 147
 148 /// MemSpaceRegion - A memory region that represents and "memory space";
 149 ///  for example, the set of global variables, the stack frame, etc.
 150 class MemSpaceRegion : public MemRegion {
 151 protected:
 152   friend class MemRegionManager;
 153
 154   MemRegionManager *Mgr;
 155
 156   MemSpaceRegion(MemRegionManager *mgr, Kind k = GenericMemSpaceRegionKind)
 157     : MemRegion(k), Mgr(mgr) {
 158     assert(classof(this));
 159   }
 160
 161   MemRegionManager* getMemRegionManager() const { return Mgr; }
 162
 163 public:
 164   bool isBoundable() const { return false; }
 165
 166   void Profile(llvm::FoldingSetNodeID &ID) const;
 167
 168   static bool classof(const MemRegion *R) {
 169     Kind k = R->getKind();
 170     return k >= BEG_MEMSPACES && k <= END_MEMSPACES;
 171   }
 172 };
 173
 174 class GlobalsSpaceRegion : public MemSpaceRegion {
 175 protected:
 176   GlobalsSpaceRegion(MemRegionManager *mgr, Kind k)
 177     : MemSpaceRegion(mgr, k) {}
 178 public:
 179   static bool classof(const MemRegion *R) {
 180     Kind k = R->getKind();
 181     return k >= BEG_GLOBAL_MEMSPACES && k <= END_GLOBAL_MEMSPACES;
 182   }
 183 };
 184
 185 class StaticGlobalSpaceRegion : public GlobalsSpaceRegion {
 186   friend class MemRegionManager;
 187
 188   const CodeTextRegion *CR;
 189
 190   StaticGlobalSpaceRegion(MemRegionManager *mgr, const CodeTextRegion *cr)
 191     : GlobalsSpaceRegion(mgr, StaticGlobalSpaceRegionKind), CR(cr) {}
 192
 193 public:
 194   void Profile(llvm::FoldingSetNodeID &ID) const;
 195
 196   void dumpToStream(llvm::raw_ostream& os) const;
 197
 198   const CodeTextRegion *getCodeRegion() const { return CR; }
 199
 200   static bool classof(const MemRegion *R) {
 201     return R->getKind() == StaticGlobalSpaceRegionKind;
 202   }
 203 };
 204
 205 class NonStaticGlobalSpaceRegion : public GlobalsSpaceRegion {
 206   friend class MemRegionManager;
 207
 208   NonStaticGlobalSpaceRegion(MemRegionManager *mgr)
 209     : GlobalsSpaceRegion(mgr, NonStaticGlobalSpaceRegionKind) {}
 210
 211 public:
 212
 213   void dumpToStream(llvm::raw_ostream& os) const;
 214
 215   static bool classof(const MemRegion *R) {
 216     return R->getKind() == NonStaticGlobalSpaceRegionKind;
 217   }
 218 };
 219
 220 class HeapSpaceRegion : public MemSpaceRegion {
 221   friend class MemRegionManager;
 222
 223   HeapSpaceRegion(MemRegionManager *mgr)
 224     : MemSpaceRegion(mgr, HeapSpaceRegionKind) {}
 225 public:
 226   static bool classof(const MemRegion *R) {
 227     return R->getKind() == HeapSpaceRegionKind;
 228   }
 229 };
 230
 231 class UnknownSpaceRegion : public MemSpaceRegion {
 232   friend class MemRegionManager;
 233   UnknownSpaceRegion(MemRegionManager *mgr)
 234     : MemSpaceRegion(mgr, UnknownSpaceRegionKind) {}
 235 public:
 236   static bool classof(const MemRegion *R) {
 237     return R->getKind() == UnknownSpaceRegionKind;
 238   }
 239 };
 240
 241 class StackSpaceRegion : public MemSpaceRegion {
 242 private:
 243   const StackFrameContext *SFC;
 244
 245 protected:
 246   StackSpaceRegion(MemRegionManager *mgr, Kind k, const StackFrameContext *sfc)
 247     : MemSpaceRegion(mgr, k), SFC(sfc) {
 248     assert(classof(this));
 249   }
 250
 251 public:
 252   const StackFrameContext *getStackFrame() const { return SFC; }
 253
 254   void Profile(llvm::FoldingSetNodeID &ID) const;
 255
 256   static bool classof(const MemRegion *R) {
 257     Kind k = R->getKind();
 258     return k >= StackLocalsSpaceRegionKind &&
 259            k <= StackArgumentsSpaceRegionKind;
 260   }
 261 };
 262
 263 class StackLocalsSpaceRegion : public StackSpaceRegion {
 264 private:
 265   friend class MemRegionManager;
 266   StackLocalsSpaceRegion(MemRegionManager *mgr, const StackFrameContext *sfc)
 267     : StackSpaceRegion(mgr, StackLocalsSpaceRegionKind, sfc) {}
 268 public:
 269   static bool classof(const MemRegion *R) {
 270     return R->getKind() == StackLocalsSpaceRegionKind;
 271   }
 272 };
 273
 274 class StackArgumentsSpaceRegion : public StackSpaceRegion {
 275 private:
 276   friend class MemRegionManager;
 277   StackArgumentsSpaceRegion(MemRegionManager *mgr, const StackFrameContext *sfc)
 278     : StackSpaceRegion(mgr, StackArgumentsSpaceRegionKind, sfc) {}
 279 public:
 280   static bool classof(const MemRegion *R) {
 281     return R->getKind() == StackArgumentsSpaceRegionKind;
 282   }
 283 };
 284
 285
 286 /// SubRegion - A region that subsets another larger region.  Most regions
 287 ///  are subclasses of SubRegion.
 288 class SubRegion : public MemRegion {
 289 protected:
 290   const MemRegion* superRegion;
 291   SubRegion(const MemRegion* sReg, Kind k) : MemRegion(k), superRegion(sReg) {}
 292 public:
 293   const MemRegion* getSuperRegion() const {
 294     return superRegion;
 295   }
 296
 297   /// getExtent - Returns the size of the region in bytes.
 298   virtual DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const {
 299     return UnknownVal();
 300   }
 301
 302   MemRegionManager* getMemRegionManager() const;
 303
 304   bool isSubRegionOf(const MemRegion* R) const;
 305
 306   static bool classof(const MemRegion* R) {
 307     return R->getKind() > END_MEMSPACES;
 308   }
 309 };
 310
 311 //===----------------------------------------------------------------------===//
 312 // MemRegion subclasses.
 313 //===----------------------------------------------------------------------===//
 314
 315 /// AllocaRegion - A region that represents an untyped blob of bytes created
 316 ///  by a call to 'alloca'.
 317 class AllocaRegion : public SubRegion {
 318   friend class MemRegionManager;
 319 protected:
 320   unsigned Cnt; // Block counter.  Used to distinguish different pieces of
 321                 // memory allocated by alloca at the same call site.
 322   const Expr* Ex;
 323
 324   AllocaRegion(const Expr* ex, unsigned cnt, const MemRegion *superRegion)
 325     : SubRegion(superRegion, AllocaRegionKind), Cnt(cnt), Ex(ex) {}
 326
 327 public:
 328
 329   const Expr* getExpr() const { return Ex; }
 330
 331   bool isBoundable() const { return true; }
 332
 333   DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const;
 334
 335   void Profile(llvm::FoldingSetNodeID& ID) const;
 336
 337   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr* Ex,
 338                             unsigned Cnt, const MemRegion *superRegion);
 339
 340   void dumpToStream(llvm::raw_ostream& os) const;
 341
 342   static bool classof(const MemRegion* R) {
 343     return R->getKind() == AllocaRegionKind;
 344   }
 345 };
 346
 347 /// TypedRegion - An abstract class representing regions that are typed.
 348 class TypedRegion : public SubRegion {
 349 protected:
 350   TypedRegion(const MemRegion* sReg, Kind k) : SubRegion(sReg, k) {}
 351
 352 public:
 353   virtual QualType getValueType() const = 0;
 354
 355   virtual QualType getLocationType() const {
 356     // FIXME: We can possibly optimize this later to cache this value.
 357     return getContext().getPointerType(getValueType());
 358   }
 359
 360   QualType getDesugaredValueType(ASTContext &Context) const {
 361     QualType T = getValueType();
 362     return T.getTypePtrOrNull() ? T.getDesugaredType(Context) : T;
 363   }
 364
 365   QualType getDesugaredLocationType(ASTContext &Context) const {
 366     return getLocationType().getDesugaredType(Context);
 367   }
 368
 369   bool isBoundable() const { return true; }
 370
 371   static bool classof(const MemRegion* R) {
 372     unsigned k = R->getKind();
 373     return k >= BEG_TYPED_REGIONS && k <= END_TYPED_REGIONS;
 374   }
 375 };
 376
 377
 378 class CodeTextRegion : public TypedRegion {
 379 protected:
 380   CodeTextRegion(const MemRegion *sreg, Kind k) : TypedRegion(sreg, k) {}
 381 public:
 382   QualType getValueType() const {
 383     assert(0 && "Do not get the object type of a CodeTextRegion.");
 384     return QualType();
 385   }
 386
 387   bool isBoundable() const { return false; }
 388
 389   static bool classof(const MemRegion* R) {
 390     Kind k = R->getKind();
 391     return k >= FunctionTextRegionKind && k <= BlockTextRegionKind;
 392   }
 393 };
 394
 395 /// FunctionTextRegion - A region that represents code texts of function.
 396 class FunctionTextRegion : public CodeTextRegion {
 397   const FunctionDecl *FD;
 398 public:
 399   FunctionTextRegion(const FunctionDecl* fd, const MemRegion* sreg)
 400     : CodeTextRegion(sreg, FunctionTextRegionKind), FD(fd) {}
 401
 402   QualType getLocationType() const {
 403     return getContext().getPointerType(FD->getType());
 404   }
 405
 406   const FunctionDecl *getDecl() const {
 407     return FD;
 408   }
 409
 410   virtual void dumpToStream(llvm::raw_ostream& os) const;
 411
 412   void Profile(llvm::FoldingSetNodeID& ID) const;
 413
 414   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const FunctionDecl *FD,
 415                             const MemRegion*);
 416
 417   static bool classof(const MemRegion* R) {
 418     return R->getKind() == FunctionTextRegionKind;
 419   }
 420 };
 421
 422
 423 /// BlockTextRegion - A region that represents code texts of blocks (closures).
 424 ///  Blocks are represented with two kinds of regions.  BlockTextRegions
 425 ///  represent the "code", while BlockDataRegions represent instances of blocks,
 426 ///  which correspond to "code+data".  The distinction is important, because
 427 ///  like a closure a block captures the values of externally referenced
 428 ///  variables.
 429 class BlockTextRegion : public CodeTextRegion {
 430   friend class MemRegionManager;
 431
 432   const BlockDecl *BD;
 433   AnalysisContext *AC;
 434   CanQualType locTy;
 435
 436   BlockTextRegion(const BlockDecl *bd, CanQualType lTy,
 437                   AnalysisContext *ac, const MemRegion* sreg)
 438     : CodeTextRegion(sreg, BlockTextRegionKind), BD(bd), AC(ac), locTy(lTy) {}
 439
 440 public:
 441   QualType getLocationType() const {
 442     return locTy;
 443   }
 444
 445   const BlockDecl *getDecl() const {
 446     return BD;
 447   }
 448
 449   AnalysisContext *getAnalysisContext() const { return AC; }
 450
 451   virtual void dumpToStream(llvm::raw_ostream& os) const;
 452
 453   void Profile(llvm::FoldingSetNodeID& ID) const;
 454
 455   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const BlockDecl *BD,
 456                             CanQualType, const AnalysisContext*,
 457                             const MemRegion*);
 458
 459   static bool classof(const MemRegion* R) {
 460     return R->getKind() == BlockTextRegionKind;
 461   }
 462 };
 463
 464 /// BlockDataRegion - A region that represents a block instance.
 465 ///  Blocks are represented with two kinds of regions.  BlockTextRegions
 466 ///  represent the "code", while BlockDataRegions represent instances of blocks,
 467 ///  which correspond to "code+data".  The distinction is important, because
 468 ///  like a closure a block captures the values of externally referenced
 469 ///  variables.
 470 class BlockDataRegion : public SubRegion {
 471   friend class MemRegionManager;
 472   const BlockTextRegion *BC;
 473   const LocationContext *LC; // Can be null */
 474   void *ReferencedVars;
 475
 476   BlockDataRegion(const BlockTextRegion *bc, const LocationContext *lc,
 477                   const MemRegion *sreg)
 478   : SubRegion(sreg, BlockDataRegionKind), BC(bc), LC(lc), ReferencedVars(0) {}
 479
 480 public:
 481   const BlockTextRegion *getCodeRegion() const { return BC; }
 482
 483   const BlockDecl *getDecl() const { return BC->getDecl(); }
 484
 485   class referenced_vars_iterator {
 486     const MemRegion * const *R;
 487   public:
 488     explicit referenced_vars_iterator(const MemRegion * const *r) : R(r) {}
 489
 490     operator const MemRegion * const *() const {
 491       return R;
 492     }
 493
 494     const VarRegion* operator*() const {
 495       return cast<VarRegion>(*R);
 496     }
 497
 498     bool operator==(const referenced_vars_iterator &I) const {
 499       return I.R == R;
 500     }
 501     bool operator!=(const referenced_vars_iterator &I) const {
 502       return I.R != R;
 503     }
 504     referenced_vars_iterator& operator++() {
 505       ++R;
 506       return *this;
 507     }
 508   };
 509
 510   referenced_vars_iterator referenced_vars_begin() const;
 511   referenced_vars_iterator referenced_vars_end() const;
 512
 513   virtual void dumpToStream(llvm::raw_ostream& os) const;
 514
 515   void Profile(llvm::FoldingSetNodeID& ID) const;
 516
 517   static void ProfileRegion(llvm::FoldingSetNodeID&, const BlockTextRegion *,
 518                             const LocationContext *, const MemRegion *);
 519
 520   static bool classof(const MemRegion* R) {
 521     return R->getKind() == BlockDataRegionKind;
 522   }
 523 private:
 524   void LazyInitializeReferencedVars();
 525 };
 526
 527 /// SymbolicRegion - A special, "non-concrete" region. Unlike other region
 528 ///  clases, SymbolicRegion represents a region that serves as an alias for
 529 ///  either a real region, a NULL pointer, etc.  It essentially is used to
 530 ///  map the concept of symbolic values into the domain of regions.  Symbolic
 531 ///  regions do not need to be typed.
 532 class SymbolicRegion : public SubRegion {
 533 protected:
 534   const SymbolRef sym;
 535
 536 public:
 537   SymbolicRegion(const SymbolRef s, const MemRegion* sreg)
 538     : SubRegion(sreg, SymbolicRegionKind), sym(s) {}
 539
 540   SymbolRef getSymbol() const {
 541     return sym;
 542   }
 543
 544   bool isBoundable() const { return true; }
 545
 546   DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const;
 547
 548   void Profile(llvm::FoldingSetNodeID& ID) const;
 549
 550   static void ProfileRegion(llvm::FoldingSetNodeID& ID,
 551                             SymbolRef sym,
 552                             const MemRegion* superRegion);
 553
 554   void dumpToStream(llvm::raw_ostream& os) const;
 555
 556   static bool classof(const MemRegion* R) {
 557     return R->getKind() == SymbolicRegionKind;
 558   }
 559 };
 560
 561 /// StringRegion - Region associated with a StringLiteral.
 562 class StringRegion : public TypedRegion {
 563   friend class MemRegionManager;
 564   const StringLiteral* Str;
 565 protected:
 566
 567   StringRegion(const StringLiteral* str, const MemRegion* sreg)
 568     : TypedRegion(sreg, StringRegionKind), Str(str) {}
 569
 570   static void ProfileRegion(llvm::FoldingSetNodeID& ID,
 571                             const StringLiteral* Str,
 572                             const MemRegion* superRegion);
 573
 574 public:
 575
 576   const StringLiteral* getStringLiteral() const { return Str; }
 577
 578   QualType getValueType() const {
 579     return Str->getType();
 580   }
 581
 582   DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const;
 583
 584   bool isBoundable() const { return false; }
 585
 586   void Profile(llvm::FoldingSetNodeID& ID) const {
 587     ProfileRegion(ID, Str, superRegion);
 588   }
 589
 590   void dumpToStream(llvm::raw_ostream& os) const;
 591
 592   static bool classof(const MemRegion* R) {
 593     return R->getKind() == StringRegionKind;
 594   }
 595 };
 596
 597 /// CompoundLiteralRegion - A memory region representing a compound literal.
 598 ///   Compound literals are essentially temporaries that are stack allocated
 599 ///   or in the global constant pool.
 600 class CompoundLiteralRegion : public TypedRegion {
 601 private:
 602   friend class MemRegionManager;
 603   const CompoundLiteralExpr* CL;
 604
 605   CompoundLiteralRegion(const CompoundLiteralExpr* cl, const MemRegion* sReg)
 606     : TypedRegion(sReg, CompoundLiteralRegionKind), CL(cl) {}
 607
 608   static void ProfileRegion(llvm::FoldingSetNodeID& ID,
 609                             const CompoundLiteralExpr* CL,
 610                             const MemRegion* superRegion);
 611 public:
 612   QualType getValueType() const {
 613     return CL->getType();
 614   }
 615
 616   bool isBoundable() const { return !CL->isFileScope(); }
 617
 618   void Profile(llvm::FoldingSetNodeID& ID) const;
 619
 620   void dumpToStream(llvm::raw_ostream& os) const;
 621
 622   const CompoundLiteralExpr* getLiteralExpr() const { return CL; }
 623
 624   static bool classof(const MemRegion* R) {
 625     return R->getKind() == CompoundLiteralRegionKind;
 626   }
 627 };
 628
 629 class DeclRegion : public TypedRegion {
 630 protected:
 631   const Decl* D;
 632
 633   DeclRegion(const Decl* d, const MemRegion* sReg, Kind k)
 634     : TypedRegion(sReg, k), D(d) {}
 635
 636   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D,
 637                       const MemRegion* superRegion, Kind k);
 638
 639 public:
 640   const Decl* getDecl() const { return D; }
 641   void Profile(llvm::FoldingSetNodeID& ID) const;
 642
 643   DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const;
 644
 645   static bool classof(const MemRegion* R) {
 646     unsigned k = R->getKind();
 647     return k >= BEG_DECL_REGIONS && k <= END_DECL_REGIONS;
 648   }
 649 };
 650
 651 class VarRegion : public DeclRegion {
 652   friend class MemRegionManager;
 653
 654   // Constructors and private methods.
 655   VarRegion(const VarDecl* vd, const MemRegion* sReg)
 656     : DeclRegion(vd, sReg, VarRegionKind) {}
 657
 658   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const VarDecl* VD,
 659                             const MemRegion *superRegion) {
 660     DeclRegion::ProfileRegion(ID, VD, superRegion, VarRegionKind);
 661   }
 662
 663   void Profile(llvm::FoldingSetNodeID& ID) const;
 664
 665 public:
 666   const VarDecl *getDecl() const { return cast<VarDecl>(D); }
 667
 668   const StackFrameContext *getStackFrame() const;
 669
 670   QualType getValueType() const {
 671     // FIXME: We can cache this if needed.
 672     return getDecl()->getType();
 673   }
 674
 675   void dumpToStream(llvm::raw_ostream& os) const;
 676
 677   static bool classof(const MemRegion* R) {
 678     return R->getKind() == VarRegionKind;
 679   }
 680 };
 681
 682 /// CXXThisRegion - Represents the region for the implicit 'this' parameter
 683 ///  in a call to a C++ method.  This region doesn't represent the object
 684 ///  referred to by 'this', but rather 'this' itself.
 685 class CXXThisRegion : public TypedRegion {
 686   friend class MemRegionManager;
 687   CXXThisRegion(const PointerType *thisPointerTy,
 688                 const MemRegion *sReg)
 689     : TypedRegion(sReg, CXXThisRegionKind), ThisPointerTy(thisPointerTy) {}
 690
 691   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
 692                             const PointerType *PT,
 693                             const MemRegion *sReg);
 694
 695   void Profile(llvm::FoldingSetNodeID &ID) const;
 696
 697 public:
 698   QualType getValueType() const {
 699     return QualType(ThisPointerTy, 0);
 700   }
 701
 702   void dumpToStream(llvm::raw_ostream& os) const;
 703
 704   static bool classof(const MemRegion* R) {
 705     return R->getKind() == CXXThisRegionKind;
 706   }
 707
 708 private:
 709   const PointerType *ThisPointerTy;
 710 };
 711
 712 class FieldRegion : public DeclRegion {
 713   friend class MemRegionManager;
 714
 715   FieldRegion(const FieldDecl* fd, const MemRegion* sReg)
 716     : DeclRegion(fd, sReg, FieldRegionKind) {}
 717
 718 public:
 719
 720   void dumpToStream(llvm::raw_ostream& os) const;
 721
 722   const FieldDecl* getDecl() const { return cast<FieldDecl>(D); }
 723
 724   QualType getValueType() const {
 725     // FIXME: We can cache this if needed.
 726     return getDecl()->getType();
 727   }
 728
 729   DefinedOrUnknownSVal getExtent(SValBuilder &svalBuilder) const;
 730
 731   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const FieldDecl* FD,
 732                             const MemRegion* superRegion) {
 733     DeclRegion::ProfileRegion(ID, FD, superRegion, FieldRegionKind);
 734   }
 735
 736   static bool classof(const MemRegion* R) {
 737     return R->getKind() == FieldRegionKind;
 738   }
 739 };
 740
 741 class ObjCIvarRegion : public DeclRegion {
 742
 743   friend class MemRegionManager;
 744
 745   ObjCIvarRegion(const ObjCIvarDecl* ivd, const MemRegion* sReg)
 746     : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
 747
 748   static void ProfileRegion(llvm::FoldingSetNodeID& ID, const ObjCIvarDecl* ivd,
 749                             const MemRegion* superRegion) {
 750     DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
 751   }
 752
 753 public:
 754   const ObjCIvarDecl* getDecl() const { return cast<ObjCIvarDecl>(D); }
 755   QualType getValueType() const { return getDecl()->getType(); }
 756
 757   void dumpToStream(llvm::raw_ostream& os) const;
 758
 759   static bool classof(const MemRegion* R) {
 760     return R->getKind() == ObjCIvarRegionKind;
 761   }
 762 };
 763 //===----------------------------------------------------------------------===//
 764 // Auxillary data classes for use with MemRegions.
 765 //===----------------------------------------------------------------------===//
 766
 767 class ElementRegion;
 768
 769 class RegionRawOffset {
 770 private:
 771   friend class ElementRegion;
 772
 773   const MemRegion *Region;
 774   int64_t Offset;
 775
 776   RegionRawOffset(const MemRegion* reg, int64_t offset = 0)
 777     : Region(reg), Offset(offset) {}
 778
 779 public:
 780   // FIXME: Eventually support symbolic offsets.
 781   int64_t getByteOffset() const { return Offset; }
 782   const MemRegion *getRegion() const { return Region; }
 783
 784   void dumpToStream(llvm::raw_ostream& os) const;
 785   void dump() const;
 786 };
 787
 788 class ElementRegion : public TypedRegion {
 789   friend class MemRegionManager;
 790
 791   QualType ElementType;
 792   NonLoc Index;
 793
 794   ElementRegion(QualType elementType, NonLoc Idx, const MemRegion* sReg)
 795     : TypedRegion(sReg, ElementRegionKind),
 796       ElementType(elementType), Index(Idx) {
 797     assert((!isa<nonloc::ConcreteInt>(&Idx) ||
 798            cast<nonloc::ConcreteInt>(&Idx)->getValue().isSigned()) &&
 799            "The index must be signed");
 800   }
 801
 802   static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType elementType,
 803                             SVal Idx, const MemRegion* superRegion);
 804
 805 public:
 806
 807   NonLoc getIndex() const { return Index; }
 808
 809   QualType getValueType() const {
 810     return ElementType;
 811   }
 812
 813   QualType getElementType() const {
 814     return ElementType;
 815   }
 816   /// Compute the offset within the array. The array might also be a subobject.
 817   RegionRawOffset getAsArrayOffset() const;
 818
 819   void dumpToStream(llvm::raw_ostream& os) const;
 820
 821   void Profile(llvm::FoldingSetNodeID& ID) const;
 822
 823   static bool classof(const MemRegion* R) {
 824     return R->getKind() == ElementRegionKind;
 825   }
 826 };
 827
 828 // C++ temporary object associated with an expression.
 829 class CXXTempObjectRegion : public TypedRegion {
 830   friend class MemRegionManager;
 831
 832   Expr const *Ex;
 833
 834   CXXTempObjectRegion(Expr const *E, MemRegion const *sReg)
 835     : TypedRegion(sReg, CXXTempObjectRegionKind), Ex(E) {}
 836
 837   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
 838                             Expr const *E, const MemRegion *sReg);
 839
 840 public:
 841   QualType getValueType() const {
 842     return Ex->getType();
 843   }
 844
 845   void dumpToStream(llvm::raw_ostream& os) const;
 846
 847   void Profile(llvm::FoldingSetNodeID &ID) const;
 848
 849   static bool classof(const MemRegion* R) {
 850     return R->getKind() == CXXTempObjectRegionKind;
 851   }
 852 };
 853
 854 // CXXBaseObjectRegion represents a base object within a C++ object. It is
 855 // identified by the base class declaration and the region of its parent object.
 856 class CXXBaseObjectRegion : public TypedRegion {
 857   friend class MemRegionManager;
 858
 859   const CXXRecordDecl *decl;
 860
 861   CXXBaseObjectRegion(const CXXRecordDecl *d, const MemRegion *sReg)
 862     : TypedRegion(sReg, CXXBaseObjectRegionKind), decl(d) {}
 863
 864   static void ProfileRegion(llvm::FoldingSetNodeID &ID,
 865                             const CXXRecordDecl *decl, const MemRegion *sReg);
 866
 867 public:
 868   QualType getValueType() const;
 869
 870   void dumpToStream(llvm::raw_ostream& os) const;
 871
 872   void Profile(llvm::FoldingSetNodeID &ID) const;
 873
 874   static bool classof(const MemRegion *region) {
 875     return region->getKind() == CXXBaseObjectRegionKind;
 876   }
 877 };
 878
 879 template<typename RegionTy>
 880 const RegionTy* MemRegion::getAs() const {
 881   if (const RegionTy* RT = dyn_cast<RegionTy>(this))
 882     return RT;
 883
 884   return NULL;
 885 }
 886
 887 //===----------------------------------------------------------------------===//
 888 // MemRegionManager - Factory object for creating regions.
 889 //===----------------------------------------------------------------------===//
 890
 891 class MemRegionManager {
 892   ASTContext &C;
 893   llvm::BumpPtrAllocator& A;
 894   llvm::FoldingSet<MemRegion> Regions;
 895
 896   NonStaticGlobalSpaceRegion *globals;
 897
 898   llvm::DenseMap<const StackFrameContext *, StackLocalsSpaceRegion *>
 899     StackLocalsSpaceRegions;
 900   llvm::DenseMap<const StackFrameContext *, StackArgumentsSpaceRegion *>
 901     StackArgumentsSpaceRegions;
 902   llvm::DenseMap<const CodeTextRegion *, StaticGlobalSpaceRegion *>
 903     StaticsGlobalSpaceRegions;
 904
 905   HeapSpaceRegion *heap;
 906   UnknownSpaceRegion *unknown;
 907   MemSpaceRegion *code;
 908
 909 public:
 910   MemRegionManager(ASTContext &c, llvm::BumpPtrAllocator& a)
 911     : C(c), A(a), globals(0), heap(0), unknown(0), code(0) {}
 912
 913   ~MemRegionManager();
 914
 915   ASTContext &getContext() { return C; }
 916
 917   llvm::BumpPtrAllocator &getAllocator() { return A; }
 918
 919   /// getStackLocalsRegion - Retrieve the memory region associated with the
 920   ///  specified stack frame.
 921   const StackLocalsSpaceRegion *
 922   getStackLocalsRegion(const StackFrameContext *STC);
 923
 924   /// getStackArgumentsRegion - Retrieve the memory region associated with
 925   ///  function/method arguments of the specified stack frame.
 926   const StackArgumentsSpaceRegion *
 927   getStackArgumentsRegion(const StackFrameContext *STC);
 928
 929   /// getGlobalsRegion - Retrieve the memory region associated with
 930   ///  global variables.
 931   const GlobalsSpaceRegion *getGlobalsRegion(const CodeTextRegion *R = 0);
 932
 933   /// getHeapRegion - Retrieve the memory region associated with the
 934   ///  generic "heap".
 935   const HeapSpaceRegion *getHeapRegion();
 936
 937   /// getUnknownRegion - Retrieve the memory region associated with unknown
 938   /// memory space.
 939   const MemSpaceRegion *getUnknownRegion();
 940
 941   const MemSpaceRegion *getCodeRegion();
 942
 943   /// getAllocaRegion - Retrieve a region associated with a call to alloca().
 944   const AllocaRegion *getAllocaRegion(const Expr* Ex, unsigned Cnt,
 945                                       const LocationContext *LC);
 946
 947   /// getCompoundLiteralRegion - Retrieve the region associated with a
 948   ///  given CompoundLiteral.
 949   const CompoundLiteralRegion*
 950   getCompoundLiteralRegion(const CompoundLiteralExpr* CL,
 951                            const LocationContext *LC);
 952
 953   /// getCXXThisRegion - Retrieve the [artifical] region associated with the
 954   ///  parameter 'this'.
 955   const CXXThisRegion *getCXXThisRegion(QualType thisPointerTy,
 956                                         const LocationContext *LC);
 957
 958   /// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
 959   const SymbolicRegion* getSymbolicRegion(SymbolRef sym);
 960
 961   const StringRegion* getStringRegion(const StringLiteral* Str);
 962
 963   /// getVarRegion - Retrieve or create the memory region associated with
 964   ///  a specified VarDecl and LocationContext.
 965   const VarRegion* getVarRegion(const VarDecl *D, const LocationContext *LC);
 966
 967   /// getVarRegion - Retrieve or create the memory region associated with
 968   ///  a specified VarDecl and super region.
 969   const VarRegion* getVarRegion(const VarDecl *D, const MemRegion *superR);
 970
 971   /// getElementRegion - Retrieve the memory region associated with the
 972   ///  associated element type, index, and super region.
 973   const ElementRegion *getElementRegion(QualType elementType, NonLoc Idx,
 974                                         const MemRegion *superRegion,
 975                                         ASTContext &Ctx);
 976
 977   const ElementRegion *getElementRegionWithSuper(const ElementRegion *ER,
 978                                                  const MemRegion *superRegion) {
 979     return getElementRegion(ER->getElementType(), ER->getIndex(),
 980                             superRegion, ER->getContext());
 981   }
 982
 983   /// getFieldRegion - Retrieve or create the memory region associated with
 984   ///  a specified FieldDecl.  'superRegion' corresponds to the containing
 985   ///  memory region (which typically represents the memory representing
 986   ///  a structure or class).
 987   const FieldRegion *getFieldRegion(const FieldDecl* fd,
 988                                     const MemRegion* superRegion);
 989
 990   const FieldRegion *getFieldRegionWithSuper(const FieldRegion *FR,
 991                                              const MemRegion *superRegion) {
 992     return getFieldRegion(FR->getDecl(), superRegion);
 993   }
 994
 995   /// getObjCIvarRegion - Retrieve or create the memory region associated with
 996   ///   a specified Objective-c instance variable.  'superRegion' corresponds
 997   ///   to the containing region (which typically represents the Objective-C
 998   ///   object).
 999   const ObjCIvarRegion *getObjCIvarRegion(const ObjCIvarDecl* ivd,
1000                                           const MemRegion* superRegion);
1001
1002   const CXXTempObjectRegion *getCXXTempObjectRegion(Expr const *Ex,
1003                                                     LocationContext const *LC);
1004
1005   const CXXBaseObjectRegion *getCXXBaseObjectRegion(const CXXRecordDecl *decl,
1006                                                   const MemRegion *superRegion);
1007
1008   const FunctionTextRegion *getFunctionTextRegion(const FunctionDecl *FD);
1009   const BlockTextRegion *getBlockTextRegion(const BlockDecl *BD,
1010                                             CanQualType locTy,
1011                                             AnalysisContext *AC);
1012
1013   /// getBlockDataRegion - Get the memory region associated with an instance
1014   ///  of a block.  Unlike many other MemRegions, the LocationContext*
1015   ///  argument is allowed to be NULL for cases where we have no known
1016   ///  context.
1017   const BlockDataRegion *getBlockDataRegion(const BlockTextRegion *bc,
1018                                             const LocationContext *lc = NULL);
1019
1020   bool isGlobalsRegion(const MemRegion* R) {
1021     assert(R);
1022     return R == globals;
1023   }
1024
1025 private:
1026   template <typename RegionTy, typename A1>
1027   RegionTy* getRegion(const A1 a1);
1028
1029   template <typename RegionTy, typename A1>
1030   RegionTy* getSubRegion(const A1 a1, const MemRegion* superRegion);
1031
1032   template <typename RegionTy, typename A1, typename A2>
1033   RegionTy* getRegion(const A1 a1, const A2 a2);
1034
1035   template <typename RegionTy, typename A1, typename A2>
1036   RegionTy* getSubRegion(const A1 a1, const A2 a2,
1037                          const MemRegion* superRegion);
1038
1039   template <typename RegionTy, typename A1, typename A2, typename A3>
1040   RegionTy* getSubRegion(const A1 a1, const A2 a2, const A3 a3,
1041                          const MemRegion* superRegion);
1042
1043   template <typename REG>
1044   const REG* LazyAllocate(REG*& region);
1045
1046   template <typename REG, typename ARG>
1047   const REG* LazyAllocate(REG*& region, ARG a);
1048 };
1049
1050 //===----------------------------------------------------------------------===//
1051 // Out-of-line member definitions.
1052 //===----------------------------------------------------------------------===//
1053
1054 inline ASTContext& MemRegion::getContext() const {
1055   return getMemRegionManager()->getContext();
1056 }
1057
1058 } // end clang namespace
1059
1060 //===----------------------------------------------------------------------===//
1061 // Pretty-printing regions.
1062 //===----------------------------------------------------------------------===//
1063
1064 namespace llvm {
1065 static inline raw_ostream& operator<<(raw_ostream& os,
1066                                       const clang::MemRegion* R) {
1067   R->dumpToStream(os);
1068   return os;
1069 }
1070 } // end llvm namespace
1071
1072 #endif