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