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