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