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