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