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