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 58using namespace clang; 59using namespace ento; 60 61#define DEBUG_TYPE "MemRegion" 62 63//===----------------------------------------------------------------------===// 64// MemRegion Construction. 65//===----------------------------------------------------------------------===// 66 67template <typename RegionTy, typename SuperTy, typename Arg1Ty> 68RegionTy* 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 84template <typename RegionTy, typename SuperTy, typename Arg1Ty, typename Arg2Ty> 85RegionTy* 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 101template <typename RegionTy, typename SuperTy, 102 typename Arg1Ty, typename Arg2Ty, typename Arg3Ty> 103RegionTy* 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 124MemRegion::~MemRegion() = default; 125 126// All regions and their data are BumpPtrAllocated. No need to call their 127// destructors. 128MemRegionManager::~MemRegionManager() = default; 129 130//===----------------------------------------------------------------------===// 131// Basic methods. 132//===----------------------------------------------------------------------===// 133 134bool 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 147MemRegionManager &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 159const StackFrameContext *VarRegion::getStackFrame() const { 160 const auto *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace()); 161 return SSR ? SSR->getStackFrame() : nullptr; 162} 163 164ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const SubRegion *sReg) 165 : DeclRegion(sReg, ObjCIvarRegionKind), IVD(ivd) { 166 assert(IVD); 167} 168 169const ObjCIvarDecl *ObjCIvarRegion::getDecl() const { return IVD; } 170 171QualType ObjCIvarRegion::getValueType() const { 172 return getDecl()->getType(); 173} 174 175QualType CXXBaseObjectRegion::getValueType() const { 176 return QualType(getDecl()->getTypeForDecl(), 0); 177} 178 179QualType CXXDerivedObjectRegion::getValueType() const { 180 return QualType(getDecl()->getTypeForDecl(), 0); 181} 182 183QualType ParamVarRegion::getValueType() const { 184 assert(getDecl() && 185 "`ParamVarRegion` support functions without `Decl` not implemented" 186 " yet."); 187 return getDecl()->getType(); 188} 189 190const 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 214void MemSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 215 ID.AddInteger(static_cast<unsigned>(getKind())); 216} 217 218void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 219 ID.AddInteger(static_cast<unsigned>(getKind())); 220 ID.AddPointer(getStackFrame()); 221} 222 223void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 224 ID.AddInteger(static_cast<unsigned>(getKind())); 225 ID.AddPointer(getCodeRegion()); 226} 227 228void 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 236void 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 244void 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 253void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const { 254 ProfileRegion(ID, Ex, Cnt, superRegion); 255} 256 257void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const { 258 CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion); 259} 260 261void 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 269void 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 277void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const { 278 CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion); 279} 280 281void FieldRegion::Profile(llvm::FoldingSetNodeID &ID) const { 282 ProfileRegion(ID, getDecl(), superRegion); 283} 284 285void 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 293void ObjCIvarRegion::Profile(llvm::FoldingSetNodeID &ID) const { 294 ProfileRegion(ID, getDecl(), superRegion); 295} 296 297void 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 305void NonParamVarRegion::Profile(llvm::FoldingSetNodeID &ID) const { 306 ProfileRegion(ID, getDecl(), superRegion); 307} 308 309void 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 317void ParamVarRegion::Profile(llvm::FoldingSetNodeID &ID) const { 318 ProfileRegion(ID, getOriginExpr(), getIndex(), superRegion); 319} 320 321void 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 328void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const { 329 SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion()); 330} 331 332void 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 341void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const { 342 ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion); 343} 344 345void FunctionCodeRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 346 const NamedDecl *FD, 347 const MemRegion*) { 348 ID.AddInteger(MemRegion::FunctionCodeRegionKind); 349 ID.AddPointer(FD); 350} 351 352void FunctionCodeRegion::Profile(llvm::FoldingSetNodeID& ID) const { 353 FunctionCodeRegion::ProfileRegion(ID, FD, superRegion); 354} 355 356void 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 364void BlockCodeRegion::Profile(llvm::FoldingSetNodeID& ID) const { 365 BlockCodeRegion::ProfileRegion(ID, BD, locTy, AC, superRegion); 366} 367 368void 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 380void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const { 381 BlockDataRegion::ProfileRegion(ID, BC, LC, BlockCount, getSuperRegion()); 382} 383 384void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 385 Expr const *Ex, 386 const MemRegion *sReg) { 387 ID.AddPointer(Ex); 388 ID.AddPointer(sReg); 389} 390 391void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 392 ProfileRegion(ID, Ex, getSuperRegion()); 393} 394 395void 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 404void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 405 ProfileRegion(ID, getDecl(), isVirtual(), superRegion); 406} 407 408void CXXDerivedObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 409 const CXXRecordDecl *RD, 410 const MemRegion *SReg) { 411 ID.AddPointer(RD); 412 ID.AddPointer(SReg); 413} 414 415void CXXDerivedObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 416 ProfileRegion(ID, getDecl(), superRegion); 417} 418 419//===----------------------------------------------------------------------===// 420// Region anchors. 421//===----------------------------------------------------------------------===// 422 423void GlobalsSpaceRegion::anchor() {} 424 425void NonStaticGlobalSpaceRegion::anchor() {} 426 427void StackSpaceRegion::anchor() {} 428 429void TypedRegion::anchor() {} 430 431void TypedValueRegion::anchor() {} 432 433void CodeTextRegion::anchor() {} 434 435void SubRegion::anchor() {} 436 437//===----------------------------------------------------------------------===// 438// Region pretty-printing. 439//===----------------------------------------------------------------------===// 440 441LLVM_DUMP_METHOD void MemRegion::dump() const { 442 dumpToStream(llvm::errs()); 443} 444 445std::string MemRegion::getString() const { 446 std::string s; 447 llvm::raw_string_ostream os(s); 448 dumpToStream(os); 449 return s; 450} 451 452void MemRegion::dumpToStream(raw_ostream &os) const { 453 os << "<Unknown Region>"; 454} 455 456void AllocaRegion::dumpToStream(raw_ostream &os) const { 457 os << "alloca{S" << Ex->getID(getContext()) << ',' << Cnt << '}'; 458} 459 460void FunctionCodeRegion::dumpToStream(raw_ostream &os) const { 461 os << "code{" << getDecl()->getDeclName().getAsString() << '}'; 462} 463 464void BlockCodeRegion::dumpToStream(raw_ostream &os) const { 465 os << "block_code{" << static_cast<const void *>(this) << '}'; 466} 467 468void BlockDataRegion::dumpToStream(raw_ostream &os) const { 469 os << "block_data{" << BC; 470 os << "; "; 471 for (BlockDataRegion::referenced_vars_iterator 472 I = referenced_vars_begin(), 473 E = referenced_vars_end(); I != E; ++I) 474 os << "(" << I.getCapturedRegion() << "<-" << 475 I.getOriginalRegion() << ") "; 476 os << '}'; 477} 478 479void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const { 480 // FIXME: More elaborate pretty-printing. 481 os << "{ S" << CL->getID(getContext()) << " }"; 482} 483 484void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const { 485 os << "temp_object{" << getValueType() << ", " 486 << "S" << Ex->getID(getContext()) << '}'; 487} 488 489void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const { 490 os << "Base{" << superRegion << ',' << getDecl()->getName() << '}'; 491} 492 493void CXXDerivedObjectRegion::dumpToStream(raw_ostream &os) const { 494 os << "Derived{" << superRegion << ',' << getDecl()->getName() << '}'; 495} 496 497void CXXThisRegion::dumpToStream(raw_ostream &os) const { 498 os << "this"; 499} 500 501void ElementRegion::dumpToStream(raw_ostream &os) const { 502 os << "Element{" << superRegion << ',' << Index << ',' << getElementType() 503 << '}'; 504} 505 506void FieldRegion::dumpToStream(raw_ostream &os) const { 507 os << superRegion << "." << *getDecl(); 508} 509 510void ObjCIvarRegion::dumpToStream(raw_ostream &os) const { 511 os << "Ivar{" << superRegion << ',' << *getDecl() << '}'; 512} 513 514void StringRegion::dumpToStream(raw_ostream &os) const { 515 assert(Str != nullptr && "Expecting non-null StringLiteral"); 516 Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts())); 517} 518 519void ObjCStringRegion::dumpToStream(raw_ostream &os) const { 520 assert(Str != nullptr && "Expecting non-null ObjCStringLiteral"); 521 Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts())); 522} 523 524void SymbolicRegion::dumpToStream(raw_ostream &os) const { 525 if (isa<HeapSpaceRegion>(getSuperRegion())) 526 os << "Heap"; 527 os << "SymRegion{" << sym << '}'; 528} 529 530void 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 537LLVM_DUMP_METHOD void RegionRawOffset::dump() const { 538 dumpToStream(llvm::errs()); 539} 540 541void RegionRawOffset::dumpToStream(raw_ostream &os) const { 542 os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}'; 543} 544 545void CodeSpaceRegion::dumpToStream(raw_ostream &os) const { 546 os << "CodeSpaceRegion"; 547} 548 549void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const { 550 os << "StaticGlobalsMemSpace{" << CR << '}'; 551} 552 553void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const { 554 os << "GlobalInternalSpaceRegion"; 555} 556 557void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const { 558 os << "GlobalSystemSpaceRegion"; 559} 560 561void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const { 562 os << "GlobalImmutableSpaceRegion"; 563} 564 565void HeapSpaceRegion::dumpToStream(raw_ostream &os) const { 566 os << "HeapSpaceRegion"; 567} 568 569void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const { 570 os << "UnknownSpaceRegion"; 571} 572 573void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const { 574 os << "StackArgumentsSpaceRegion"; 575} 576 577void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const { 578 os << "StackLocalsSpaceRegion"; 579} 580 581void 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 593bool MemRegion::canPrintPretty() const { 594 return canPrintPrettyAsExpr(); 595} 596 597bool MemRegion::canPrintPrettyAsExpr() const { 598 return false; 599} 600 601void MemRegion::printPretty(raw_ostream &os) const { 602 assert(canPrintPretty() && "This region cannot be printed pretty."); 603 os << "'"; 604 printPrettyAsExpr(os); 605 os << "'"; 606} 607 608void MemRegion::printPrettyAsExpr(raw_ostream &) const { 609 llvm_unreachable("This region cannot be printed pretty."); 610} 611 612bool NonParamVarRegion::canPrintPrettyAsExpr() const { return true; } 613 614void NonParamVarRegion::printPrettyAsExpr(raw_ostream &os) const { 615 os << getDecl()->getName(); 616} 617 618bool ParamVarRegion::canPrintPrettyAsExpr() const { return true; } 619 620void 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 627bool ObjCIvarRegion::canPrintPrettyAsExpr() const { 628 return true; 629} 630 631void ObjCIvarRegion::printPrettyAsExpr(raw_ostream &os) const { 632 os << getDecl()->getName(); 633} 634 635bool FieldRegion::canPrintPretty() const { 636 return true; 637} 638 639bool FieldRegion::canPrintPrettyAsExpr() const { 640 return superRegion->canPrintPrettyAsExpr(); 641} 642 643void FieldRegion::printPrettyAsExpr(raw_ostream &os) const { 644 assert(canPrintPrettyAsExpr()); 645 superRegion->printPrettyAsExpr(os); 646 os << "." << getDecl()->getName(); 647} 648 649void 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 659bool CXXBaseObjectRegion::canPrintPrettyAsExpr() const { 660 return superRegion->canPrintPrettyAsExpr(); 661} 662 663void CXXBaseObjectRegion::printPrettyAsExpr(raw_ostream &os) const { 664 superRegion->printPrettyAsExpr(os); 665} 666 667bool CXXDerivedObjectRegion::canPrintPrettyAsExpr() const { 668 return superRegion->canPrintPrettyAsExpr(); 669} 670 671void CXXDerivedObjectRegion::printPrettyAsExpr(raw_ostream &os) const { 672 superRegion->printPrettyAsExpr(os); 673} 674 675std::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 714SourceRange 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 736DefinedOrUnknownSVal 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 838template <typename REG> 839const 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 848template <typename REG, typename ARG> 849const 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 858const StackLocalsSpaceRegion* 859MemRegionManager::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 871const StackArgumentsSpaceRegion * 872MemRegionManager::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 884const 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 906const HeapSpaceRegion *MemRegionManager::getHeapRegion() { 907 return LazyAllocate(heap); 908} 909 910const UnknownSpaceRegion *MemRegionManager::getUnknownRegion() { 911 return LazyAllocate(unknown); 912} 913 914const CodeSpaceRegion *MemRegionManager::getCodeRegion() { 915 return LazyAllocate(code); 916} 917 918//===----------------------------------------------------------------------===// 919// Constructing regions. 920//===----------------------------------------------------------------------===// 921 922const StringRegion *MemRegionManager::getStringRegion(const StringLiteral *Str){ 923 return getSubRegion<StringRegion>( 924 Str, cast<GlobalInternalSpaceRegion>(getGlobalsRegion())); 925} 926 927const ObjCStringRegion * 928MemRegionManager::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. 936static llvm::PointerUnion<const StackFrameContext *, const VarRegion *> 937getStackOrCaptureRegionForDeclContext(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 964const 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 1064const NonParamVarRegion * 1065MemRegionManager::getNonParamVarRegion(const VarDecl *D, 1066 const MemRegion *superR) { 1067 D = D->getCanonicalDecl(); 1068 return getSubRegion<NonParamVarRegion>(D, superR); 1069} 1070 1071const ParamVarRegion * 1072MemRegionManager::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 1080const BlockDataRegion * 1081MemRegionManager::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 1112const CXXTempObjectRegion * 1113MemRegionManager::getCXXStaticTempObjectRegion(const Expr *Ex) { 1114 return getSubRegion<CXXTempObjectRegion>( 1115 Ex, getGlobalsRegion(MemRegion::GlobalInternalSpaceRegionKind, nullptr)); 1116} 1117 1118const CompoundLiteralRegion* 1119MemRegionManager::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 1134const ElementRegion* 1135MemRegionManager::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 1156const FunctionCodeRegion * 1157MemRegionManager::getFunctionCodeRegion(const NamedDecl *FD) { 1158 // To think: should we canonicalize the declaration here? 1159 return getSubRegion<FunctionCodeRegion>(FD, getCodeRegion()); 1160} 1161 1162const BlockCodeRegion * 1163MemRegionManager::getBlockCodeRegion(const BlockDecl *BD, CanQualType locTy, 1164 AnalysisDeclContext *AC) { 1165 return getSubRegion<BlockCodeRegion>(BD, locTy, AC, getCodeRegion()); 1166} 1167 1168const SymbolicRegion * 1169MemRegionManager::getSymbolicRegion(SymbolRef sym, 1170 const MemSpaceRegion *MemSpace) { 1171 if (MemSpace == nullptr) 1172 MemSpace = getUnknownRegion(); 1173 return getSubRegion<SymbolicRegion>(sym, MemSpace); 1174} 1175 1176const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) { 1177 return getSubRegion<SymbolicRegion>(Sym, getHeapRegion()); 1178} 1179 1180const FieldRegion* 1181MemRegionManager::getFieldRegion(const FieldDecl *d, 1182 const SubRegion* superRegion){ 1183 return getSubRegion<FieldRegion>(d, superRegion); 1184} 1185 1186const ObjCIvarRegion* 1187MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d, 1188 const SubRegion* superRegion) { 1189 return getSubRegion<ObjCIvarRegion>(d, superRegion); 1190} 1191 1192const CXXTempObjectRegion* 1193MemRegionManager::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. 1202static 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 1222const CXXBaseObjectRegion * 1223MemRegionManager::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 1242const CXXDerivedObjectRegion * 1243MemRegionManager::getCXXDerivedObjectRegion(const CXXRecordDecl *RD, 1244 const SubRegion *Super) { 1245 return getSubRegion<CXXDerivedObjectRegion>(RD, Super); 1246} 1247 1248const CXXThisRegion* 1249MemRegionManager::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 1269const AllocaRegion* 1270MemRegionManager::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 1277const 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 1289bool MemRegion::hasStackStorage() const { 1290 return isa<StackSpaceRegion>(getMemorySpace()); 1291} 1292 1293bool MemRegion::hasStackNonParametersStorage() const { 1294 return isa<StackLocalsSpaceRegion>(getMemorySpace()); 1295} 1296 1297bool MemRegion::hasStackParametersStorage() const { 1298 return isa<StackArgumentsSpaceRegion>(getMemorySpace()); 1299} 1300 1301bool 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. 1307const 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. 1327const 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 1334bool MemRegion::isSubRegionOf(const MemRegion *) const { 1335 return false; 1336} 1337 1338//===----------------------------------------------------------------------===// 1339// View handling. 1340//===----------------------------------------------------------------------===// 1341 1342const 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 1365const 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 1376RegionRawOffset 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 1426static 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 1440static 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 1614RegionOffset MemRegion::getAsOffset() const { 1615 if (!cachedOffset) 1616 cachedOffset = calculateOffset(this); 1617 return *cachedOffset; 1618} 1619 1620//===----------------------------------------------------------------------===// 1621// BlockDataRegion 1622//===----------------------------------------------------------------------===// 1623 1624std::pair<const VarRegion *, const VarRegion *> 1625BlockDataRegion::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 1647void 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 1686BlockDataRegion::referenced_vars_iterator 1687BlockDataRegion::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 1702BlockDataRegion::referenced_vars_iterator 1703BlockDataRegion::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 1718const 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 1732void RegionAndSymbolInvalidationTraits::setTrait(SymbolRef Sym, 1733 InvalidationKinds IK) { 1734 SymTraitsMap[Sym] |= IK; 1735} 1736 1737void 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 1746bool 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 1755bool 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