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