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