MemRegion.cpp revision 732cdf383f9030ff2b9fb28dfbdae2285ded80c6
1//== MemRegion.cpp - 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#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 18#include "clang/Analysis/AnalysisContext.h" 19#include "clang/Analysis/Support/BumpVector.h" 20#include "clang/AST/CharUnits.h" 21#include "clang/AST/DeclObjC.h" 22#include "clang/AST/RecordLayout.h" 23#include "clang/Basic/SourceManager.h" 24#include "llvm/Support/raw_ostream.h" 25 26using namespace clang; 27using namespace ento; 28 29//===----------------------------------------------------------------------===// 30// MemRegion Construction. 31//===----------------------------------------------------------------------===// 32 33template<typename RegionTy> struct MemRegionManagerTrait; 34 35template <typename RegionTy, typename A1> 36RegionTy* MemRegionManager::getRegion(const A1 a1) { 37 38 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = 39 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1); 40 41 llvm::FoldingSetNodeID ID; 42 RegionTy::ProfileRegion(ID, a1, superRegion); 43 void *InsertPos; 44 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 45 InsertPos)); 46 47 if (!R) { 48 R = (RegionTy*) A.Allocate<RegionTy>(); 49 new (R) RegionTy(a1, superRegion); 50 Regions.InsertNode(R, InsertPos); 51 } 52 53 return R; 54} 55 56template <typename RegionTy, typename A1> 57RegionTy* MemRegionManager::getSubRegion(const A1 a1, 58 const MemRegion *superRegion) { 59 llvm::FoldingSetNodeID ID; 60 RegionTy::ProfileRegion(ID, a1, superRegion); 61 void *InsertPos; 62 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 63 InsertPos)); 64 65 if (!R) { 66 R = (RegionTy*) A.Allocate<RegionTy>(); 67 new (R) RegionTy(a1, superRegion); 68 Regions.InsertNode(R, InsertPos); 69 } 70 71 return R; 72} 73 74template <typename RegionTy, typename A1, typename A2> 75RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) { 76 77 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = 78 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2); 79 80 llvm::FoldingSetNodeID ID; 81 RegionTy::ProfileRegion(ID, a1, a2, superRegion); 82 void *InsertPos; 83 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 84 InsertPos)); 85 86 if (!R) { 87 R = (RegionTy*) A.Allocate<RegionTy>(); 88 new (R) RegionTy(a1, a2, superRegion); 89 Regions.InsertNode(R, InsertPos); 90 } 91 92 return R; 93} 94 95template <typename RegionTy, typename A1, typename A2> 96RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, 97 const MemRegion *superRegion) { 98 99 llvm::FoldingSetNodeID ID; 100 RegionTy::ProfileRegion(ID, a1, a2, superRegion); 101 void *InsertPos; 102 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 103 InsertPos)); 104 105 if (!R) { 106 R = (RegionTy*) A.Allocate<RegionTy>(); 107 new (R) RegionTy(a1, a2, superRegion); 108 Regions.InsertNode(R, InsertPos); 109 } 110 111 return R; 112} 113 114template <typename RegionTy, typename A1, typename A2, typename A3> 115RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3, 116 const MemRegion *superRegion) { 117 118 llvm::FoldingSetNodeID ID; 119 RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion); 120 void *InsertPos; 121 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 122 InsertPos)); 123 124 if (!R) { 125 R = (RegionTy*) A.Allocate<RegionTy>(); 126 new (R) RegionTy(a1, a2, a3, superRegion); 127 Regions.InsertNode(R, InsertPos); 128 } 129 130 return R; 131} 132 133//===----------------------------------------------------------------------===// 134// Object destruction. 135//===----------------------------------------------------------------------===// 136 137MemRegion::~MemRegion() {} 138 139MemRegionManager::~MemRegionManager() { 140 // All regions and their data are BumpPtrAllocated. No need to call 141 // their destructors. 142} 143 144//===----------------------------------------------------------------------===// 145// Basic methods. 146//===----------------------------------------------------------------------===// 147 148bool SubRegion::isSubRegionOf(const MemRegion* R) const { 149 const MemRegion* r = getSuperRegion(); 150 while (r != 0) { 151 if (r == R) 152 return true; 153 if (const SubRegion* sr = dyn_cast<SubRegion>(r)) 154 r = sr->getSuperRegion(); 155 else 156 break; 157 } 158 return false; 159} 160 161MemRegionManager* SubRegion::getMemRegionManager() const { 162 const SubRegion* r = this; 163 do { 164 const MemRegion *superRegion = r->getSuperRegion(); 165 if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) { 166 r = sr; 167 continue; 168 } 169 return superRegion->getMemRegionManager(); 170 } while (1); 171} 172 173const StackFrameContext *VarRegion::getStackFrame() const { 174 const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace()); 175 return SSR ? SSR->getStackFrame() : NULL; 176} 177 178//===----------------------------------------------------------------------===// 179// Region extents. 180//===----------------------------------------------------------------------===// 181 182DefinedOrUnknownSVal TypedValueRegion::getExtent(SValBuilder &svalBuilder) const { 183 ASTContext &Ctx = svalBuilder.getContext(); 184 QualType T = getDesugaredValueType(Ctx); 185 186 if (isa<VariableArrayType>(T)) 187 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 188 if (isa<IncompleteArrayType>(T)) 189 return UnknownVal(); 190 191 CharUnits size = Ctx.getTypeSizeInChars(T); 192 QualType sizeTy = svalBuilder.getArrayIndexType(); 193 return svalBuilder.makeIntVal(size.getQuantity(), sizeTy); 194} 195 196DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const { 197 DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder); 198 199 // A zero-length array at the end of a struct often stands for dynamically- 200 // allocated extra memory. 201 if (Extent.isZeroConstant()) { 202 QualType T = getDesugaredValueType(svalBuilder.getContext()); 203 204 if (isa<ConstantArrayType>(T)) 205 return UnknownVal(); 206 } 207 208 return Extent; 209} 210 211DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const { 212 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 213} 214 215DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const { 216 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 217} 218 219DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const { 220 return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1, 221 svalBuilder.getArrayIndexType()); 222} 223 224ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg) 225 : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {} 226 227const ObjCIvarDecl *ObjCIvarRegion::getDecl() const { 228 return cast<ObjCIvarDecl>(D); 229} 230 231QualType ObjCIvarRegion::getValueType() const { 232 return getDecl()->getType(); 233} 234 235QualType CXXBaseObjectRegion::getValueType() const { 236 return QualType(decl->getTypeForDecl(), 0); 237} 238 239//===----------------------------------------------------------------------===// 240// FoldingSet profiling. 241//===----------------------------------------------------------------------===// 242 243void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const { 244 ID.AddInteger((unsigned)getKind()); 245} 246 247void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 248 ID.AddInteger((unsigned)getKind()); 249 ID.AddPointer(getStackFrame()); 250} 251 252void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 253 ID.AddInteger((unsigned)getKind()); 254 ID.AddPointer(getCodeRegion()); 255} 256 257void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 258 const StringLiteral* Str, 259 const MemRegion* superRegion) { 260 ID.AddInteger((unsigned) StringRegionKind); 261 ID.AddPointer(Str); 262 ID.AddPointer(superRegion); 263} 264 265void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 266 const ObjCStringLiteral* Str, 267 const MemRegion* superRegion) { 268 ID.AddInteger((unsigned) ObjCStringRegionKind); 269 ID.AddPointer(Str); 270 ID.AddPointer(superRegion); 271} 272 273void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 274 const Expr *Ex, unsigned cnt, 275 const MemRegion *) { 276 ID.AddInteger((unsigned) AllocaRegionKind); 277 ID.AddPointer(Ex); 278 ID.AddInteger(cnt); 279} 280 281void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const { 282 ProfileRegion(ID, Ex, Cnt, superRegion); 283} 284 285void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const { 286 CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion); 287} 288 289void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 290 const CompoundLiteralExpr *CL, 291 const MemRegion* superRegion) { 292 ID.AddInteger((unsigned) CompoundLiteralRegionKind); 293 ID.AddPointer(CL); 294 ID.AddPointer(superRegion); 295} 296 297void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 298 const PointerType *PT, 299 const MemRegion *sRegion) { 300 ID.AddInteger((unsigned) CXXThisRegionKind); 301 ID.AddPointer(PT); 302 ID.AddPointer(sRegion); 303} 304 305void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const { 306 CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion); 307} 308 309void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 310 const ObjCIvarDecl *ivd, 311 const MemRegion* superRegion) { 312 DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind); 313} 314 315void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D, 316 const MemRegion* superRegion, Kind k) { 317 ID.AddInteger((unsigned) k); 318 ID.AddPointer(D); 319 ID.AddPointer(superRegion); 320} 321 322void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const { 323 DeclRegion::ProfileRegion(ID, D, superRegion, getKind()); 324} 325 326void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const { 327 VarRegion::ProfileRegion(ID, getDecl(), superRegion); 328} 329 330void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym, 331 const MemRegion *sreg) { 332 ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind); 333 ID.Add(sym); 334 ID.AddPointer(sreg); 335} 336 337void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const { 338 SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion()); 339} 340 341void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 342 QualType ElementType, SVal Idx, 343 const MemRegion* superRegion) { 344 ID.AddInteger(MemRegion::ElementRegionKind); 345 ID.Add(ElementType); 346 ID.AddPointer(superRegion); 347 Idx.Profile(ID); 348} 349 350void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const { 351 ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion); 352} 353 354void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 355 const NamedDecl *FD, 356 const MemRegion*) { 357 ID.AddInteger(MemRegion::FunctionTextRegionKind); 358 ID.AddPointer(FD); 359} 360 361void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const { 362 FunctionTextRegion::ProfileRegion(ID, FD, superRegion); 363} 364 365void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 366 const BlockDecl *BD, CanQualType, 367 const AnalysisDeclContext *AC, 368 const MemRegion*) { 369 ID.AddInteger(MemRegion::BlockTextRegionKind); 370 ID.AddPointer(BD); 371} 372 373void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const { 374 BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion); 375} 376 377void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 378 const BlockTextRegion *BC, 379 const LocationContext *LC, 380 const MemRegion *sReg) { 381 ID.AddInteger(MemRegion::BlockDataRegionKind); 382 ID.AddPointer(BC); 383 ID.AddPointer(LC); 384 ID.AddPointer(sReg); 385} 386 387void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const { 388 BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion()); 389} 390 391void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 392 Expr const *Ex, 393 const MemRegion *sReg) { 394 ID.AddPointer(Ex); 395 ID.AddPointer(sReg); 396} 397 398void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 399 ProfileRegion(ID, Ex, getSuperRegion()); 400} 401 402void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 403 const CXXRecordDecl *decl, 404 const MemRegion *sReg) { 405 ID.AddPointer(decl); 406 ID.AddPointer(sReg); 407} 408 409void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 410 ProfileRegion(ID, decl, superRegion); 411} 412 413//===----------------------------------------------------------------------===// 414// Region anchors. 415//===----------------------------------------------------------------------===// 416 417void GlobalsSpaceRegion::anchor() { } 418void HeapSpaceRegion::anchor() { } 419void UnknownSpaceRegion::anchor() { } 420void StackLocalsSpaceRegion::anchor() { } 421void StackArgumentsSpaceRegion::anchor() { } 422void TypedRegion::anchor() { } 423void TypedValueRegion::anchor() { } 424void CodeTextRegion::anchor() { } 425void SubRegion::anchor() { } 426 427//===----------------------------------------------------------------------===// 428// Region pretty-printing. 429//===----------------------------------------------------------------------===// 430 431void MemRegion::dump() const { 432 dumpToStream(llvm::errs()); 433} 434 435std::string MemRegion::getString() const { 436 std::string s; 437 llvm::raw_string_ostream os(s); 438 dumpToStream(os); 439 return os.str(); 440} 441 442void MemRegion::dumpToStream(raw_ostream &os) const { 443 os << "<Unknown Region>"; 444} 445 446void AllocaRegion::dumpToStream(raw_ostream &os) const { 447 os << "alloca{" << (const void*) Ex << ',' << Cnt << '}'; 448} 449 450void FunctionTextRegion::dumpToStream(raw_ostream &os) const { 451 os << "code{" << getDecl()->getDeclName().getAsString() << '}'; 452} 453 454void BlockTextRegion::dumpToStream(raw_ostream &os) const { 455 os << "block_code{" << (const void*) this << '}'; 456} 457 458void BlockDataRegion::dumpToStream(raw_ostream &os) const { 459 os << "block_data{" << BC << '}'; 460} 461 462void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const { 463 // FIXME: More elaborate pretty-printing. 464 os << "{ " << (const void*) CL << " }"; 465} 466 467void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const { 468 os << "temp_object{" << getValueType().getAsString() << ',' 469 << (const void*) Ex << '}'; 470} 471 472void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const { 473 os << "base{" << superRegion << ',' << decl->getName() << '}'; 474} 475 476void CXXThisRegion::dumpToStream(raw_ostream &os) const { 477 os << "this"; 478} 479 480void ElementRegion::dumpToStream(raw_ostream &os) const { 481 os << "element{" << superRegion << ',' 482 << Index << ',' << getElementType().getAsString() << '}'; 483} 484 485void FieldRegion::dumpToStream(raw_ostream &os) const { 486 os << superRegion << "->" << *getDecl(); 487} 488 489void ObjCIvarRegion::dumpToStream(raw_ostream &os) const { 490 os << "ivar{" << superRegion << ',' << *getDecl() << '}'; 491} 492 493void StringRegion::dumpToStream(raw_ostream &os) const { 494 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts())); 495} 496 497void ObjCStringRegion::dumpToStream(raw_ostream &os) const { 498 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts())); 499} 500 501void SymbolicRegion::dumpToStream(raw_ostream &os) const { 502 os << "SymRegion{" << sym << '}'; 503} 504 505void VarRegion::dumpToStream(raw_ostream &os) const { 506 os << *cast<VarDecl>(D); 507} 508 509void RegionRawOffset::dump() const { 510 dumpToStream(llvm::errs()); 511} 512 513void RegionRawOffset::dumpToStream(raw_ostream &os) const { 514 os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}'; 515} 516 517void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const { 518 os << "StaticGlobalsMemSpace{" << CR << '}'; 519} 520 521void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const { 522 os << "GlobalInternalSpaceRegion"; 523} 524 525void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const { 526 os << "GlobalSystemSpaceRegion"; 527} 528 529void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const { 530 os << "GlobalImmutableSpaceRegion"; 531} 532 533void HeapSpaceRegion::dumpToStream(raw_ostream &os) const { 534 os << "HeapSpaceRegion"; 535} 536 537void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const { 538 os << "UnknownSpaceRegion"; 539} 540 541void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const { 542 os << "StackArgumentsSpaceRegion"; 543} 544 545void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const { 546 os << "StackLocalsSpaceRegion"; 547} 548 549bool MemRegion::canPrintPretty() const { 550 return false; 551} 552 553void MemRegion::printPretty(raw_ostream &os) const { 554 return; 555} 556 557bool VarRegion::canPrintPretty() const { 558 return true; 559} 560 561void VarRegion::printPretty(raw_ostream &os) const { 562 os << getDecl()->getName(); 563} 564 565bool FieldRegion::canPrintPretty() const { 566 return superRegion->canPrintPretty(); 567} 568 569void FieldRegion::printPretty(raw_ostream &os) const { 570 superRegion->printPretty(os); 571 os << "." << getDecl()->getName(); 572} 573 574//===----------------------------------------------------------------------===// 575// MemRegionManager methods. 576//===----------------------------------------------------------------------===// 577 578template <typename REG> 579const REG *MemRegionManager::LazyAllocate(REG*& region) { 580 if (!region) { 581 region = (REG*) A.Allocate<REG>(); 582 new (region) REG(this); 583 } 584 585 return region; 586} 587 588template <typename REG, typename ARG> 589const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) { 590 if (!region) { 591 region = (REG*) A.Allocate<REG>(); 592 new (region) REG(this, a); 593 } 594 595 return region; 596} 597 598const StackLocalsSpaceRegion* 599MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) { 600 assert(STC); 601 StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC]; 602 603 if (R) 604 return R; 605 606 R = A.Allocate<StackLocalsSpaceRegion>(); 607 new (R) StackLocalsSpaceRegion(this, STC); 608 return R; 609} 610 611const StackArgumentsSpaceRegion * 612MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) { 613 assert(STC); 614 StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC]; 615 616 if (R) 617 return R; 618 619 R = A.Allocate<StackArgumentsSpaceRegion>(); 620 new (R) StackArgumentsSpaceRegion(this, STC); 621 return R; 622} 623 624const GlobalsSpaceRegion 625*MemRegionManager::getGlobalsRegion(MemRegion::Kind K, 626 const CodeTextRegion *CR) { 627 if (!CR) { 628 if (K == MemRegion::GlobalSystemSpaceRegionKind) 629 return LazyAllocate(SystemGlobals); 630 if (K == MemRegion::GlobalImmutableSpaceRegionKind) 631 return LazyAllocate(ImmutableGlobals); 632 assert(K == MemRegion::GlobalInternalSpaceRegionKind); 633 return LazyAllocate(InternalGlobals); 634 } 635 636 assert(K == MemRegion::StaticGlobalSpaceRegionKind); 637 StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR]; 638 if (R) 639 return R; 640 641 R = A.Allocate<StaticGlobalSpaceRegion>(); 642 new (R) StaticGlobalSpaceRegion(this, CR); 643 return R; 644} 645 646const HeapSpaceRegion *MemRegionManager::getHeapRegion() { 647 return LazyAllocate(heap); 648} 649 650const MemSpaceRegion *MemRegionManager::getUnknownRegion() { 651 return LazyAllocate(unknown); 652} 653 654const MemSpaceRegion *MemRegionManager::getCodeRegion() { 655 return LazyAllocate(code); 656} 657 658//===----------------------------------------------------------------------===// 659// Constructing regions. 660//===----------------------------------------------------------------------===// 661const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){ 662 return getSubRegion<StringRegion>(Str, getGlobalsRegion()); 663} 664 665const ObjCStringRegion * 666MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){ 667 return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion()); 668} 669 670/// Look through a chain of LocationContexts to either find the 671/// StackFrameContext that matches a DeclContext, or find a VarRegion 672/// for a variable captured by a block. 673static llvm::PointerUnion<const StackFrameContext *, const VarRegion *> 674getStackOrCaptureRegionForDeclContext(const LocationContext *LC, 675 const DeclContext *DC, 676 const VarDecl *VD) { 677 while (LC) { 678 if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) { 679 if (cast<DeclContext>(SFC->getDecl()) == DC) 680 return SFC; 681 } 682 if (const BlockInvocationContext *BC = 683 dyn_cast<BlockInvocationContext>(LC)) { 684 const BlockDataRegion *BR = 685 static_cast<const BlockDataRegion*>(BC->getContextData()); 686 // FIXME: This can be made more efficient. 687 for (BlockDataRegion::referenced_vars_iterator 688 I = BR->referenced_vars_begin(), 689 E = BR->referenced_vars_end(); I != E; ++I) { 690 if (const VarRegion *VR = dyn_cast<VarRegion>(I.getOriginalRegion())) 691 if (VR->getDecl() == VD) 692 return cast<VarRegion>(I.getCapturedRegion()); 693 } 694 } 695 696 LC = LC->getParent(); 697 } 698 return (const StackFrameContext*)0; 699} 700 701const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D, 702 const LocationContext *LC) { 703 const MemRegion *sReg = 0; 704 705 if (D->hasGlobalStorage() && !D->isStaticLocal()) { 706 707 // First handle the globals defined in system headers. 708 if (C.getSourceManager().isInSystemHeader(D->getLocation())) { 709 // Whitelist the system globals which often DO GET modified, assume the 710 // rest are immutable. 711 if (D->getName().find("errno") != StringRef::npos) 712 sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind); 713 else 714 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 715 716 // Treat other globals as GlobalInternal unless they are constants. 717 } else { 718 QualType GQT = D->getType(); 719 const Type *GT = GQT.getTypePtrOrNull(); 720 // TODO: We could walk the complex types here and see if everything is 721 // constified. 722 if (GT && GQT.isConstQualified() && GT->isArithmeticType()) 723 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 724 else 725 sReg = getGlobalsRegion(); 726 } 727 728 // Finally handle static locals. 729 } else { 730 // FIXME: Once we implement scope handling, we will need to properly lookup 731 // 'D' to the proper LocationContext. 732 const DeclContext *DC = D->getDeclContext(); 733 llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V = 734 getStackOrCaptureRegionForDeclContext(LC, DC, D); 735 736 if (V.is<const VarRegion*>()) 737 return V.get<const VarRegion*>(); 738 739 const StackFrameContext *STC = V.get<const StackFrameContext*>(); 740 741 if (!STC) 742 sReg = getUnknownRegion(); 743 else { 744 if (D->hasLocalStorage()) { 745 sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D) 746 ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC)) 747 : static_cast<const MemRegion*>(getStackLocalsRegion(STC)); 748 } 749 else { 750 assert(D->isStaticLocal()); 751 const Decl *STCD = STC->getDecl(); 752 if (isa<FunctionDecl>(STCD) || isa<ObjCMethodDecl>(STCD)) 753 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, 754 getFunctionTextRegion(cast<NamedDecl>(STCD))); 755 else if (const BlockDecl *BD = dyn_cast<BlockDecl>(STCD)) { 756 const BlockTextRegion *BTR = 757 getBlockTextRegion(BD, 758 C.getCanonicalType(BD->getSignatureAsWritten()->getType()), 759 STC->getAnalysisDeclContext()); 760 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, 761 BTR); 762 } 763 else { 764 sReg = getGlobalsRegion(); 765 } 766 } 767 } 768 } 769 770 return getSubRegion<VarRegion>(D, sReg); 771} 772 773const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D, 774 const MemRegion *superR) { 775 return getSubRegion<VarRegion>(D, superR); 776} 777 778const BlockDataRegion * 779MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC, 780 const LocationContext *LC) { 781 const MemRegion *sReg = 0; 782 const BlockDecl *BD = BC->getDecl(); 783 if (!BD->hasCaptures()) { 784 // This handles 'static' blocks. 785 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 786 } 787 else { 788 if (LC) { 789 // FIXME: Once we implement scope handling, we want the parent region 790 // to be the scope. 791 const StackFrameContext *STC = LC->getCurrentStackFrame(); 792 assert(STC); 793 sReg = getStackLocalsRegion(STC); 794 } 795 else { 796 // We allow 'LC' to be NULL for cases where want BlockDataRegions 797 // without context-sensitivity. 798 sReg = getUnknownRegion(); 799 } 800 } 801 802 return getSubRegion<BlockDataRegion>(BC, LC, sReg); 803} 804 805const CompoundLiteralRegion* 806MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL, 807 const LocationContext *LC) { 808 809 const MemRegion *sReg = 0; 810 811 if (CL->isFileScope()) 812 sReg = getGlobalsRegion(); 813 else { 814 const StackFrameContext *STC = LC->getCurrentStackFrame(); 815 assert(STC); 816 sReg = getStackLocalsRegion(STC); 817 } 818 819 return getSubRegion<CompoundLiteralRegion>(CL, sReg); 820} 821 822const ElementRegion* 823MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx, 824 const MemRegion* superRegion, 825 ASTContext &Ctx){ 826 827 QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType(); 828 829 llvm::FoldingSetNodeID ID; 830 ElementRegion::ProfileRegion(ID, T, Idx, superRegion); 831 832 void *InsertPos; 833 MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); 834 ElementRegion* R = cast_or_null<ElementRegion>(data); 835 836 if (!R) { 837 R = (ElementRegion*) A.Allocate<ElementRegion>(); 838 new (R) ElementRegion(T, Idx, superRegion); 839 Regions.InsertNode(R, InsertPos); 840 } 841 842 return R; 843} 844 845const FunctionTextRegion * 846MemRegionManager::getFunctionTextRegion(const NamedDecl *FD) { 847 return getSubRegion<FunctionTextRegion>(FD, getCodeRegion()); 848} 849 850const BlockTextRegion * 851MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy, 852 AnalysisDeclContext *AC) { 853 return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion()); 854} 855 856 857/// getSymbolicRegion - Retrieve or create a "symbolic" memory region. 858const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) { 859 return getSubRegion<SymbolicRegion>(sym, getUnknownRegion()); 860} 861 862const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) { 863 return getSubRegion<SymbolicRegion>(Sym, getHeapRegion()); 864} 865 866const FieldRegion* 867MemRegionManager::getFieldRegion(const FieldDecl *d, 868 const MemRegion* superRegion){ 869 return getSubRegion<FieldRegion>(d, superRegion); 870} 871 872const ObjCIvarRegion* 873MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d, 874 const MemRegion* superRegion) { 875 return getSubRegion<ObjCIvarRegion>(d, superRegion); 876} 877 878const CXXTempObjectRegion* 879MemRegionManager::getCXXTempObjectRegion(Expr const *E, 880 LocationContext const *LC) { 881 const StackFrameContext *SFC = LC->getCurrentStackFrame(); 882 assert(SFC); 883 return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC)); 884} 885 886const CXXBaseObjectRegion * 887MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *decl, 888 const MemRegion *superRegion) { 889 // Check that the base class is actually a direct base of this region. 890 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(superRegion)) { 891 if (const CXXRecordDecl *Class = TVR->getValueType()->getAsCXXRecordDecl()){ 892 if (Class->isVirtuallyDerivedFrom(decl)) { 893 // Virtual base regions should not be layered, since the layout rules 894 // are different. 895 while (const CXXBaseObjectRegion *Base = 896 dyn_cast<CXXBaseObjectRegion>(superRegion)) { 897 superRegion = Base->getSuperRegion(); 898 } 899 assert(superRegion && !isa<MemSpaceRegion>(superRegion)); 900 901 } else { 902 // Non-virtual bases should always be direct bases. 903#ifndef NDEBUG 904 bool FoundBase = false; 905 for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(), 906 E = Class->bases_end(); 907 I != E; ++I) { 908 if (I->getType()->getAsCXXRecordDecl() == decl) { 909 FoundBase = true; 910 break; 911 } 912 } 913 914 assert(FoundBase && "Not a direct base class of this region"); 915#endif 916 } 917 } 918 } 919 920 return getSubRegion<CXXBaseObjectRegion>(decl, superRegion); 921} 922 923const CXXThisRegion* 924MemRegionManager::getCXXThisRegion(QualType thisPointerTy, 925 const LocationContext *LC) { 926 const StackFrameContext *STC = LC->getCurrentStackFrame(); 927 assert(STC); 928 const PointerType *PT = thisPointerTy->getAs<PointerType>(); 929 assert(PT); 930 return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC)); 931} 932 933const AllocaRegion* 934MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt, 935 const LocationContext *LC) { 936 const StackFrameContext *STC = LC->getCurrentStackFrame(); 937 assert(STC); 938 return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC)); 939} 940 941const MemSpaceRegion *MemRegion::getMemorySpace() const { 942 const MemRegion *R = this; 943 const SubRegion* SR = dyn_cast<SubRegion>(this); 944 945 while (SR) { 946 R = SR->getSuperRegion(); 947 SR = dyn_cast<SubRegion>(R); 948 } 949 950 return dyn_cast<MemSpaceRegion>(R); 951} 952 953bool MemRegion::hasStackStorage() const { 954 return isa<StackSpaceRegion>(getMemorySpace()); 955} 956 957bool MemRegion::hasStackNonParametersStorage() const { 958 return isa<StackLocalsSpaceRegion>(getMemorySpace()); 959} 960 961bool MemRegion::hasStackParametersStorage() const { 962 return isa<StackArgumentsSpaceRegion>(getMemorySpace()); 963} 964 965bool MemRegion::hasGlobalsOrParametersStorage() const { 966 const MemSpaceRegion *MS = getMemorySpace(); 967 return isa<StackArgumentsSpaceRegion>(MS) || 968 isa<GlobalsSpaceRegion>(MS); 969} 970 971// getBaseRegion strips away all elements and fields, and get the base region 972// of them. 973const MemRegion *MemRegion::getBaseRegion() const { 974 const MemRegion *R = this; 975 while (true) { 976 switch (R->getKind()) { 977 case MemRegion::ElementRegionKind: 978 case MemRegion::FieldRegionKind: 979 case MemRegion::ObjCIvarRegionKind: 980 case MemRegion::CXXBaseObjectRegionKind: 981 R = cast<SubRegion>(R)->getSuperRegion(); 982 continue; 983 default: 984 break; 985 } 986 break; 987 } 988 return R; 989} 990 991bool MemRegion::isSubRegionOf(const MemRegion *R) const { 992 return false; 993} 994 995//===----------------------------------------------------------------------===// 996// View handling. 997//===----------------------------------------------------------------------===// 998 999const MemRegion *MemRegion::StripCasts(bool StripBaseCasts) const { 1000 const MemRegion *R = this; 1001 while (true) { 1002 switch (R->getKind()) { 1003 case ElementRegionKind: { 1004 const ElementRegion *ER = cast<ElementRegion>(R); 1005 if (!ER->getIndex().isZeroConstant()) 1006 return R; 1007 R = ER->getSuperRegion(); 1008 break; 1009 } 1010 case CXXBaseObjectRegionKind: 1011 if (!StripBaseCasts) 1012 return R; 1013 R = cast<CXXBaseObjectRegion>(R)->getSuperRegion(); 1014 break; 1015 default: 1016 return R; 1017 } 1018 } 1019} 1020 1021// FIXME: Merge with the implementation of the same method in Store.cpp 1022static bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 1023 if (const RecordType *RT = Ty->getAs<RecordType>()) { 1024 const RecordDecl *D = RT->getDecl(); 1025 if (!D->getDefinition()) 1026 return false; 1027 } 1028 1029 return true; 1030} 1031 1032RegionRawOffset ElementRegion::getAsArrayOffset() const { 1033 CharUnits offset = CharUnits::Zero(); 1034 const ElementRegion *ER = this; 1035 const MemRegion *superR = NULL; 1036 ASTContext &C = getContext(); 1037 1038 // FIXME: Handle multi-dimensional arrays. 1039 1040 while (ER) { 1041 superR = ER->getSuperRegion(); 1042 1043 // FIXME: generalize to symbolic offsets. 1044 SVal index = ER->getIndex(); 1045 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) { 1046 // Update the offset. 1047 int64_t i = CI->getValue().getSExtValue(); 1048 1049 if (i != 0) { 1050 QualType elemType = ER->getElementType(); 1051 1052 // If we are pointing to an incomplete type, go no further. 1053 if (!IsCompleteType(C, elemType)) { 1054 superR = ER; 1055 break; 1056 } 1057 1058 CharUnits size = C.getTypeSizeInChars(elemType); 1059 offset += (i * size); 1060 } 1061 1062 // Go to the next ElementRegion (if any). 1063 ER = dyn_cast<ElementRegion>(superR); 1064 continue; 1065 } 1066 1067 return NULL; 1068 } 1069 1070 assert(superR && "super region cannot be NULL"); 1071 return RegionRawOffset(superR, offset); 1072} 1073 1074RegionOffset MemRegion::getAsOffset() const { 1075 const MemRegion *R = this; 1076 const MemRegion *SymbolicOffsetBase = 0; 1077 int64_t Offset = 0; 1078 1079 while (1) { 1080 switch (R->getKind()) { 1081 default: 1082 return RegionOffset(R, RegionOffset::Symbolic); 1083 1084 case SymbolicRegionKind: 1085 case AllocaRegionKind: 1086 case CompoundLiteralRegionKind: 1087 case CXXThisRegionKind: 1088 case StringRegionKind: 1089 case VarRegionKind: 1090 case CXXTempObjectRegionKind: 1091 goto Finish; 1092 1093 case ObjCIvarRegionKind: 1094 // This is a little strange, but it's a compromise between 1095 // ObjCIvarRegions having unknown compile-time offsets (when using the 1096 // non-fragile runtime) and yet still being distinct, non-overlapping 1097 // regions. Thus we treat them as "like" base regions for the purposes 1098 // of computing offsets. 1099 goto Finish; 1100 1101 case CXXBaseObjectRegionKind: { 1102 const CXXBaseObjectRegion *BOR = cast<CXXBaseObjectRegion>(R); 1103 R = BOR->getSuperRegion(); 1104 1105 QualType Ty; 1106 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) { 1107 Ty = TVR->getDesugaredValueType(getContext()); 1108 } else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 1109 // If our base region is symbolic, we don't know what type it really is. 1110 // Pretend the type of the symbol is the true dynamic type. 1111 // (This will at least be self-consistent for the life of the symbol.) 1112 Ty = SR->getSymbol()->getType()->getPointeeType(); 1113 } 1114 1115 const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl(); 1116 if (!Child) { 1117 // We cannot compute the offset of the base class. 1118 SymbolicOffsetBase = R; 1119 } 1120 1121 // Don't bother calculating precise offsets if we already have a 1122 // symbolic offset somewhere in the chain. 1123 if (SymbolicOffsetBase) 1124 continue; 1125 1126 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child); 1127 1128 CharUnits BaseOffset; 1129 const CXXRecordDecl *Base = BOR->getDecl(); 1130 if (Child->isVirtuallyDerivedFrom(Base)) 1131 BaseOffset = Layout.getVBaseClassOffset(Base); 1132 else 1133 BaseOffset = Layout.getBaseClassOffset(Base); 1134 1135 // The base offset is in chars, not in bits. 1136 Offset += BaseOffset.getQuantity() * getContext().getCharWidth(); 1137 break; 1138 } 1139 case ElementRegionKind: { 1140 const ElementRegion *ER = cast<ElementRegion>(R); 1141 R = ER->getSuperRegion(); 1142 1143 QualType EleTy = ER->getValueType(); 1144 if (!IsCompleteType(getContext(), EleTy)) { 1145 // We cannot compute the offset of the base class. 1146 SymbolicOffsetBase = R; 1147 continue; 1148 } 1149 1150 SVal Index = ER->getIndex(); 1151 if (const nonloc::ConcreteInt *CI=dyn_cast<nonloc::ConcreteInt>(&Index)) { 1152 // Don't bother calculating precise offsets if we already have a 1153 // symbolic offset somewhere in the chain. 1154 if (SymbolicOffsetBase) 1155 continue; 1156 1157 int64_t i = CI->getValue().getSExtValue(); 1158 // This type size is in bits. 1159 Offset += i * getContext().getTypeSize(EleTy); 1160 } else { 1161 // We cannot compute offset for non-concrete index. 1162 SymbolicOffsetBase = R; 1163 } 1164 break; 1165 } 1166 case FieldRegionKind: { 1167 const FieldRegion *FR = cast<FieldRegion>(R); 1168 R = FR->getSuperRegion(); 1169 1170 const RecordDecl *RD = FR->getDecl()->getParent(); 1171 if (!RD->isCompleteDefinition()) { 1172 // We cannot compute offset for incomplete type. 1173 SymbolicOffsetBase = R; 1174 } 1175 1176 // Don't bother calculating precise offsets if we already have a 1177 // symbolic offset somewhere in the chain. 1178 if (SymbolicOffsetBase) 1179 continue; 1180 1181 // Get the field number. 1182 unsigned idx = 0; 1183 for (RecordDecl::field_iterator FI = RD->field_begin(), 1184 FE = RD->field_end(); FI != FE; ++FI, ++idx) 1185 if (FR->getDecl() == *FI) 1186 break; 1187 1188 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD); 1189 // This is offset in bits. 1190 Offset += Layout.getFieldOffset(idx); 1191 break; 1192 } 1193 } 1194 } 1195 1196 Finish: 1197 if (SymbolicOffsetBase) 1198 return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic); 1199 return RegionOffset(R, Offset); 1200} 1201 1202//===----------------------------------------------------------------------===// 1203// BlockDataRegion 1204//===----------------------------------------------------------------------===// 1205 1206void BlockDataRegion::LazyInitializeReferencedVars() { 1207 if (ReferencedVars) 1208 return; 1209 1210 AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext(); 1211 AnalysisDeclContext::referenced_decls_iterator I, E; 1212 llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl()); 1213 1214 if (I == E) { 1215 ReferencedVars = (void*) 0x1; 1216 return; 1217 } 1218 1219 MemRegionManager &MemMgr = *getMemRegionManager(); 1220 llvm::BumpPtrAllocator &A = MemMgr.getAllocator(); 1221 BumpVectorContext BC(A); 1222 1223 typedef BumpVector<const MemRegion*> VarVec; 1224 VarVec *BV = (VarVec*) A.Allocate<VarVec>(); 1225 new (BV) VarVec(BC, E - I); 1226 VarVec *BVOriginal = (VarVec*) A.Allocate<VarVec>(); 1227 new (BVOriginal) VarVec(BC, E - I); 1228 1229 for ( ; I != E; ++I) { 1230 const VarDecl *VD = *I; 1231 const VarRegion *VR = 0; 1232 const VarRegion *OriginalVR = 0; 1233 1234 if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) { 1235 VR = MemMgr.getVarRegion(VD, this); 1236 OriginalVR = MemMgr.getVarRegion(VD, LC); 1237 } 1238 else { 1239 if (LC) { 1240 VR = MemMgr.getVarRegion(VD, LC); 1241 OriginalVR = VR; 1242 } 1243 else { 1244 VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion()); 1245 OriginalVR = MemMgr.getVarRegion(VD, LC); 1246 } 1247 } 1248 1249 assert(VR); 1250 assert(OriginalVR); 1251 BV->push_back(VR, BC); 1252 BVOriginal->push_back(OriginalVR, BC); 1253 } 1254 1255 ReferencedVars = BV; 1256 OriginalVars = BVOriginal; 1257} 1258 1259BlockDataRegion::referenced_vars_iterator 1260BlockDataRegion::referenced_vars_begin() const { 1261 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars(); 1262 1263 BumpVector<const MemRegion*> *Vec = 1264 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars); 1265 1266 if (Vec == (void*) 0x1) 1267 return BlockDataRegion::referenced_vars_iterator(0, 0); 1268 1269 BumpVector<const MemRegion*> *VecOriginal = 1270 static_cast<BumpVector<const MemRegion*>*>(OriginalVars); 1271 1272 return BlockDataRegion::referenced_vars_iterator(Vec->begin(), 1273 VecOriginal->begin()); 1274} 1275 1276BlockDataRegion::referenced_vars_iterator 1277BlockDataRegion::referenced_vars_end() const { 1278 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars(); 1279 1280 BumpVector<const MemRegion*> *Vec = 1281 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars); 1282 1283 if (Vec == (void*) 0x1) 1284 return BlockDataRegion::referenced_vars_iterator(0, 0); 1285 1286 BumpVector<const MemRegion*> *VecOriginal = 1287 static_cast<BumpVector<const MemRegion*>*>(OriginalVars); 1288 1289 return BlockDataRegion::referenced_vars_iterator(Vec->end(), 1290 VecOriginal->end()); 1291} 1292