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