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