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