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