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