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