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