MemRegion.cpp revision 249423
1218887Sdim//== MemRegion.cpp - Abstract memory regions for static analysis --*- C++ -*--// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines MemRegion and its subclasses. MemRegion defines a 11218887Sdim// partially-typed abstraction of memory useful for path-sensitive dataflow 12218887Sdim// analyses. 13218887Sdim// 14218887Sdim//===----------------------------------------------------------------------===// 15218887Sdim 16218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 17249423Sdim#include "clang/AST/Attr.h" 18218887Sdim#include "clang/AST/CharUnits.h" 19234353Sdim#include "clang/AST/DeclObjC.h" 20218887Sdim#include "clang/AST/RecordLayout.h" 21249423Sdim#include "clang/Analysis/AnalysisContext.h" 22249423Sdim#include "clang/Analysis/Support/BumpVector.h" 23234353Sdim#include "clang/Basic/SourceManager.h" 24249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 25218887Sdim#include "llvm/Support/raw_ostream.h" 26218887Sdim 27218887Sdimusing namespace clang; 28218887Sdimusing namespace ento; 29218887Sdim 30218887Sdim//===----------------------------------------------------------------------===// 31218887Sdim// MemRegion Construction. 32218887Sdim//===----------------------------------------------------------------------===// 33218887Sdim 34218887Sdimtemplate<typename RegionTy> struct MemRegionManagerTrait; 35218887Sdim 36218887Sdimtemplate <typename RegionTy, typename A1> 37218887SdimRegionTy* MemRegionManager::getRegion(const A1 a1) { 38218887Sdim 39218887Sdim const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = 40218887Sdim MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1); 41218887Sdim 42218887Sdim llvm::FoldingSetNodeID ID; 43218887Sdim RegionTy::ProfileRegion(ID, a1, superRegion); 44226633Sdim void *InsertPos; 45218887Sdim RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 46218887Sdim InsertPos)); 47218887Sdim 48218887Sdim if (!R) { 49218887Sdim R = (RegionTy*) A.Allocate<RegionTy>(); 50218887Sdim new (R) RegionTy(a1, superRegion); 51218887Sdim Regions.InsertNode(R, InsertPos); 52218887Sdim } 53218887Sdim 54218887Sdim return R; 55218887Sdim} 56218887Sdim 57218887Sdimtemplate <typename RegionTy, typename A1> 58218887SdimRegionTy* MemRegionManager::getSubRegion(const A1 a1, 59218887Sdim const MemRegion *superRegion) { 60218887Sdim llvm::FoldingSetNodeID ID; 61218887Sdim RegionTy::ProfileRegion(ID, a1, superRegion); 62226633Sdim void *InsertPos; 63218887Sdim RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 64218887Sdim InsertPos)); 65218887Sdim 66218887Sdim if (!R) { 67218887Sdim R = (RegionTy*) A.Allocate<RegionTy>(); 68218887Sdim new (R) RegionTy(a1, superRegion); 69218887Sdim Regions.InsertNode(R, InsertPos); 70218887Sdim } 71218887Sdim 72218887Sdim return R; 73218887Sdim} 74218887Sdim 75218887Sdimtemplate <typename RegionTy, typename A1, typename A2> 76218887SdimRegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) { 77218887Sdim 78218887Sdim const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion = 79218887Sdim MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2); 80218887Sdim 81218887Sdim llvm::FoldingSetNodeID ID; 82218887Sdim RegionTy::ProfileRegion(ID, a1, a2, superRegion); 83226633Sdim void *InsertPos; 84218887Sdim RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 85218887Sdim InsertPos)); 86218887Sdim 87218887Sdim if (!R) { 88218887Sdim R = (RegionTy*) A.Allocate<RegionTy>(); 89218887Sdim new (R) RegionTy(a1, a2, superRegion); 90218887Sdim Regions.InsertNode(R, InsertPos); 91218887Sdim } 92218887Sdim 93218887Sdim return R; 94218887Sdim} 95218887Sdim 96218887Sdimtemplate <typename RegionTy, typename A1, typename A2> 97218887SdimRegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, 98218887Sdim const MemRegion *superRegion) { 99218887Sdim 100218887Sdim llvm::FoldingSetNodeID ID; 101218887Sdim RegionTy::ProfileRegion(ID, a1, a2, superRegion); 102226633Sdim void *InsertPos; 103218887Sdim RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 104218887Sdim InsertPos)); 105218887Sdim 106218887Sdim if (!R) { 107218887Sdim R = (RegionTy*) A.Allocate<RegionTy>(); 108218887Sdim new (R) RegionTy(a1, a2, superRegion); 109218887Sdim Regions.InsertNode(R, InsertPos); 110218887Sdim } 111218887Sdim 112218887Sdim return R; 113218887Sdim} 114218887Sdim 115218887Sdimtemplate <typename RegionTy, typename A1, typename A2, typename A3> 116218887SdimRegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3, 117218887Sdim const MemRegion *superRegion) { 118218887Sdim 119218887Sdim llvm::FoldingSetNodeID ID; 120218887Sdim RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion); 121226633Sdim void *InsertPos; 122218887Sdim RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, 123218887Sdim InsertPos)); 124218887Sdim 125218887Sdim if (!R) { 126218887Sdim R = (RegionTy*) A.Allocate<RegionTy>(); 127218887Sdim new (R) RegionTy(a1, a2, a3, superRegion); 128218887Sdim Regions.InsertNode(R, InsertPos); 129218887Sdim } 130218887Sdim 131218887Sdim return R; 132218887Sdim} 133218887Sdim 134218887Sdim//===----------------------------------------------------------------------===// 135218887Sdim// Object destruction. 136218887Sdim//===----------------------------------------------------------------------===// 137218887Sdim 138218887SdimMemRegion::~MemRegion() {} 139218887Sdim 140218887SdimMemRegionManager::~MemRegionManager() { 141218887Sdim // All regions and their data are BumpPtrAllocated. No need to call 142218887Sdim // their destructors. 143218887Sdim} 144218887Sdim 145218887Sdim//===----------------------------------------------------------------------===// 146218887Sdim// Basic methods. 147218887Sdim//===----------------------------------------------------------------------===// 148218887Sdim 149218887Sdimbool SubRegion::isSubRegionOf(const MemRegion* R) const { 150218887Sdim const MemRegion* r = getSuperRegion(); 151218887Sdim while (r != 0) { 152218887Sdim if (r == R) 153218887Sdim return true; 154218887Sdim if (const SubRegion* sr = dyn_cast<SubRegion>(r)) 155218887Sdim r = sr->getSuperRegion(); 156218887Sdim else 157218887Sdim break; 158218887Sdim } 159218887Sdim return false; 160218887Sdim} 161218887Sdim 162218887SdimMemRegionManager* SubRegion::getMemRegionManager() const { 163218887Sdim const SubRegion* r = this; 164218887Sdim do { 165218887Sdim const MemRegion *superRegion = r->getSuperRegion(); 166218887Sdim if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) { 167218887Sdim r = sr; 168218887Sdim continue; 169218887Sdim } 170218887Sdim return superRegion->getMemRegionManager(); 171218887Sdim } while (1); 172218887Sdim} 173218887Sdim 174218887Sdimconst StackFrameContext *VarRegion::getStackFrame() const { 175218887Sdim const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace()); 176218887Sdim return SSR ? SSR->getStackFrame() : NULL; 177218887Sdim} 178218887Sdim 179218887Sdim//===----------------------------------------------------------------------===// 180218887Sdim// Region extents. 181218887Sdim//===----------------------------------------------------------------------===// 182218887Sdim 183239462SdimDefinedOrUnknownSVal TypedValueRegion::getExtent(SValBuilder &svalBuilder) const { 184226633Sdim ASTContext &Ctx = svalBuilder.getContext(); 185218887Sdim QualType T = getDesugaredValueType(Ctx); 186218887Sdim 187218887Sdim if (isa<VariableArrayType>(T)) 188218887Sdim return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 189218887Sdim if (isa<IncompleteArrayType>(T)) 190218887Sdim return UnknownVal(); 191218887Sdim 192218887Sdim CharUnits size = Ctx.getTypeSizeInChars(T); 193218887Sdim QualType sizeTy = svalBuilder.getArrayIndexType(); 194218887Sdim return svalBuilder.makeIntVal(size.getQuantity(), sizeTy); 195218887Sdim} 196218887Sdim 197218887SdimDefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const { 198249423Sdim // Force callers to deal with bitfields explicitly. 199249423Sdim if (getDecl()->isBitField()) 200249423Sdim return UnknownVal(); 201249423Sdim 202218887Sdim DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder); 203218887Sdim 204218887Sdim // A zero-length array at the end of a struct often stands for dynamically- 205218887Sdim // allocated extra memory. 206218887Sdim if (Extent.isZeroConstant()) { 207218887Sdim QualType T = getDesugaredValueType(svalBuilder.getContext()); 208218887Sdim 209218887Sdim if (isa<ConstantArrayType>(T)) 210218887Sdim return UnknownVal(); 211218887Sdim } 212218887Sdim 213218887Sdim return Extent; 214218887Sdim} 215218887Sdim 216218887SdimDefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const { 217218887Sdim return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 218218887Sdim} 219218887Sdim 220218887SdimDefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const { 221218887Sdim return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this)); 222218887Sdim} 223218887Sdim 224218887SdimDefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const { 225218887Sdim return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1, 226218887Sdim svalBuilder.getArrayIndexType()); 227218887Sdim} 228218887Sdim 229234353SdimObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg) 230234353Sdim : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {} 231234353Sdim 232234353Sdimconst ObjCIvarDecl *ObjCIvarRegion::getDecl() const { 233234353Sdim return cast<ObjCIvarDecl>(D); 234234353Sdim} 235234353Sdim 236234353SdimQualType ObjCIvarRegion::getValueType() const { 237234353Sdim return getDecl()->getType(); 238234353Sdim} 239234353Sdim 240218887SdimQualType CXXBaseObjectRegion::getValueType() const { 241249423Sdim return QualType(getDecl()->getTypeForDecl(), 0); 242218887Sdim} 243218887Sdim 244218887Sdim//===----------------------------------------------------------------------===// 245218887Sdim// FoldingSet profiling. 246218887Sdim//===----------------------------------------------------------------------===// 247218887Sdim 248218887Sdimvoid MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const { 249218887Sdim ID.AddInteger((unsigned)getKind()); 250218887Sdim} 251218887Sdim 252218887Sdimvoid StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 253218887Sdim ID.AddInteger((unsigned)getKind()); 254218887Sdim ID.AddPointer(getStackFrame()); 255218887Sdim} 256218887Sdim 257218887Sdimvoid StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const { 258218887Sdim ID.AddInteger((unsigned)getKind()); 259218887Sdim ID.AddPointer(getCodeRegion()); 260218887Sdim} 261218887Sdim 262218887Sdimvoid StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 263218887Sdim const StringLiteral* Str, 264218887Sdim const MemRegion* superRegion) { 265218887Sdim ID.AddInteger((unsigned) StringRegionKind); 266218887Sdim ID.AddPointer(Str); 267218887Sdim ID.AddPointer(superRegion); 268218887Sdim} 269218887Sdim 270234353Sdimvoid ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 271234353Sdim const ObjCStringLiteral* Str, 272234353Sdim const MemRegion* superRegion) { 273234353Sdim ID.AddInteger((unsigned) ObjCStringRegionKind); 274234353Sdim ID.AddPointer(Str); 275234353Sdim ID.AddPointer(superRegion); 276234353Sdim} 277234353Sdim 278218887Sdimvoid AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 279226633Sdim const Expr *Ex, unsigned cnt, 280249423Sdim const MemRegion *superRegion) { 281218887Sdim ID.AddInteger((unsigned) AllocaRegionKind); 282218887Sdim ID.AddPointer(Ex); 283218887Sdim ID.AddInteger(cnt); 284249423Sdim ID.AddPointer(superRegion); 285218887Sdim} 286218887Sdim 287218887Sdimvoid AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const { 288218887Sdim ProfileRegion(ID, Ex, Cnt, superRegion); 289218887Sdim} 290218887Sdim 291218887Sdimvoid CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const { 292218887Sdim CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion); 293218887Sdim} 294218887Sdim 295218887Sdimvoid CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 296226633Sdim const CompoundLiteralExpr *CL, 297218887Sdim const MemRegion* superRegion) { 298218887Sdim ID.AddInteger((unsigned) CompoundLiteralRegionKind); 299218887Sdim ID.AddPointer(CL); 300218887Sdim ID.AddPointer(superRegion); 301218887Sdim} 302218887Sdim 303218887Sdimvoid CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 304218887Sdim const PointerType *PT, 305218887Sdim const MemRegion *sRegion) { 306218887Sdim ID.AddInteger((unsigned) CXXThisRegionKind); 307218887Sdim ID.AddPointer(PT); 308218887Sdim ID.AddPointer(sRegion); 309218887Sdim} 310218887Sdim 311218887Sdimvoid CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const { 312218887Sdim CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion); 313218887Sdim} 314218887Sdim 315234353Sdimvoid ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 316234353Sdim const ObjCIvarDecl *ivd, 317234353Sdim const MemRegion* superRegion) { 318234353Sdim DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind); 319234353Sdim} 320234353Sdim 321226633Sdimvoid DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D, 322218887Sdim const MemRegion* superRegion, Kind k) { 323218887Sdim ID.AddInteger((unsigned) k); 324218887Sdim ID.AddPointer(D); 325218887Sdim ID.AddPointer(superRegion); 326218887Sdim} 327218887Sdim 328218887Sdimvoid DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const { 329218887Sdim DeclRegion::ProfileRegion(ID, D, superRegion, getKind()); 330218887Sdim} 331218887Sdim 332218887Sdimvoid VarRegion::Profile(llvm::FoldingSetNodeID &ID) const { 333218887Sdim VarRegion::ProfileRegion(ID, getDecl(), superRegion); 334218887Sdim} 335218887Sdim 336218887Sdimvoid SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym, 337218887Sdim const MemRegion *sreg) { 338218887Sdim ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind); 339218887Sdim ID.Add(sym); 340218887Sdim ID.AddPointer(sreg); 341218887Sdim} 342218887Sdim 343218887Sdimvoid SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const { 344218887Sdim SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion()); 345218887Sdim} 346218887Sdim 347218887Sdimvoid ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 348218887Sdim QualType ElementType, SVal Idx, 349218887Sdim const MemRegion* superRegion) { 350218887Sdim ID.AddInteger(MemRegion::ElementRegionKind); 351218887Sdim ID.Add(ElementType); 352218887Sdim ID.AddPointer(superRegion); 353218887Sdim Idx.Profile(ID); 354218887Sdim} 355218887Sdim 356218887Sdimvoid ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const { 357218887Sdim ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion); 358218887Sdim} 359218887Sdim 360218887Sdimvoid FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 361243830Sdim const NamedDecl *FD, 362218887Sdim const MemRegion*) { 363218887Sdim ID.AddInteger(MemRegion::FunctionTextRegionKind); 364218887Sdim ID.AddPointer(FD); 365218887Sdim} 366218887Sdim 367218887Sdimvoid FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const { 368218887Sdim FunctionTextRegion::ProfileRegion(ID, FD, superRegion); 369218887Sdim} 370218887Sdim 371218887Sdimvoid BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 372218887Sdim const BlockDecl *BD, CanQualType, 373234353Sdim const AnalysisDeclContext *AC, 374218887Sdim const MemRegion*) { 375218887Sdim ID.AddInteger(MemRegion::BlockTextRegionKind); 376218887Sdim ID.AddPointer(BD); 377218887Sdim} 378218887Sdim 379218887Sdimvoid BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const { 380218887Sdim BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion); 381218887Sdim} 382218887Sdim 383218887Sdimvoid BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, 384218887Sdim const BlockTextRegion *BC, 385218887Sdim const LocationContext *LC, 386218887Sdim const MemRegion *sReg) { 387218887Sdim ID.AddInteger(MemRegion::BlockDataRegionKind); 388218887Sdim ID.AddPointer(BC); 389218887Sdim ID.AddPointer(LC); 390218887Sdim ID.AddPointer(sReg); 391218887Sdim} 392218887Sdim 393218887Sdimvoid BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const { 394218887Sdim BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion()); 395218887Sdim} 396218887Sdim 397218887Sdimvoid CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 398218887Sdim Expr const *Ex, 399218887Sdim const MemRegion *sReg) { 400218887Sdim ID.AddPointer(Ex); 401218887Sdim ID.AddPointer(sReg); 402218887Sdim} 403218887Sdim 404218887Sdimvoid CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 405218887Sdim ProfileRegion(ID, Ex, getSuperRegion()); 406218887Sdim} 407218887Sdim 408218887Sdimvoid CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, 409249423Sdim const CXXRecordDecl *RD, 410249423Sdim bool IsVirtual, 411249423Sdim const MemRegion *SReg) { 412249423Sdim ID.AddPointer(RD); 413249423Sdim ID.AddBoolean(IsVirtual); 414249423Sdim ID.AddPointer(SReg); 415218887Sdim} 416218887Sdim 417218887Sdimvoid CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const { 418249423Sdim ProfileRegion(ID, getDecl(), isVirtual(), superRegion); 419218887Sdim} 420218887Sdim 421218887Sdim//===----------------------------------------------------------------------===// 422234353Sdim// Region anchors. 423234353Sdim//===----------------------------------------------------------------------===// 424234353Sdim 425234353Sdimvoid GlobalsSpaceRegion::anchor() { } 426234353Sdimvoid HeapSpaceRegion::anchor() { } 427234353Sdimvoid UnknownSpaceRegion::anchor() { } 428234353Sdimvoid StackLocalsSpaceRegion::anchor() { } 429234353Sdimvoid StackArgumentsSpaceRegion::anchor() { } 430234353Sdimvoid TypedRegion::anchor() { } 431234353Sdimvoid TypedValueRegion::anchor() { } 432234353Sdimvoid CodeTextRegion::anchor() { } 433234353Sdimvoid SubRegion::anchor() { } 434234353Sdim 435234353Sdim//===----------------------------------------------------------------------===// 436218887Sdim// Region pretty-printing. 437218887Sdim//===----------------------------------------------------------------------===// 438218887Sdim 439218887Sdimvoid MemRegion::dump() const { 440218887Sdim dumpToStream(llvm::errs()); 441218887Sdim} 442218887Sdim 443218887Sdimstd::string MemRegion::getString() const { 444218887Sdim std::string s; 445218887Sdim llvm::raw_string_ostream os(s); 446218887Sdim dumpToStream(os); 447218887Sdim return os.str(); 448218887Sdim} 449218887Sdim 450226633Sdimvoid MemRegion::dumpToStream(raw_ostream &os) const { 451218887Sdim os << "<Unknown Region>"; 452218887Sdim} 453218887Sdim 454226633Sdimvoid AllocaRegion::dumpToStream(raw_ostream &os) const { 455243830Sdim os << "alloca{" << (const void*) Ex << ',' << Cnt << '}'; 456218887Sdim} 457218887Sdim 458226633Sdimvoid FunctionTextRegion::dumpToStream(raw_ostream &os) const { 459218887Sdim os << "code{" << getDecl()->getDeclName().getAsString() << '}'; 460218887Sdim} 461218887Sdim 462226633Sdimvoid BlockTextRegion::dumpToStream(raw_ostream &os) const { 463243830Sdim os << "block_code{" << (const void*) this << '}'; 464218887Sdim} 465218887Sdim 466226633Sdimvoid BlockDataRegion::dumpToStream(raw_ostream &os) const { 467218887Sdim os << "block_data{" << BC << '}'; 468218887Sdim} 469218887Sdim 470226633Sdimvoid CompoundLiteralRegion::dumpToStream(raw_ostream &os) const { 471218887Sdim // FIXME: More elaborate pretty-printing. 472243830Sdim os << "{ " << (const void*) CL << " }"; 473218887Sdim} 474218887Sdim 475226633Sdimvoid CXXTempObjectRegion::dumpToStream(raw_ostream &os) const { 476226633Sdim os << "temp_object{" << getValueType().getAsString() << ',' 477243830Sdim << (const void*) Ex << '}'; 478218887Sdim} 479218887Sdim 480226633Sdimvoid CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const { 481249423Sdim os << "base{" << superRegion << ',' << getDecl()->getName() << '}'; 482218887Sdim} 483218887Sdim 484226633Sdimvoid CXXThisRegion::dumpToStream(raw_ostream &os) const { 485218887Sdim os << "this"; 486218887Sdim} 487218887Sdim 488226633Sdimvoid ElementRegion::dumpToStream(raw_ostream &os) const { 489218887Sdim os << "element{" << superRegion << ',' 490218887Sdim << Index << ',' << getElementType().getAsString() << '}'; 491218887Sdim} 492218887Sdim 493226633Sdimvoid FieldRegion::dumpToStream(raw_ostream &os) const { 494226633Sdim os << superRegion << "->" << *getDecl(); 495218887Sdim} 496218887Sdim 497226633Sdimvoid ObjCIvarRegion::dumpToStream(raw_ostream &os) const { 498226633Sdim os << "ivar{" << superRegion << ',' << *getDecl() << '}'; 499218887Sdim} 500218887Sdim 501226633Sdimvoid StringRegion::dumpToStream(raw_ostream &os) const { 502234353Sdim Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts())); 503218887Sdim} 504218887Sdim 505234353Sdimvoid ObjCStringRegion::dumpToStream(raw_ostream &os) const { 506234353Sdim Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts())); 507234353Sdim} 508234353Sdim 509226633Sdimvoid SymbolicRegion::dumpToStream(raw_ostream &os) const { 510218887Sdim os << "SymRegion{" << sym << '}'; 511218887Sdim} 512218887Sdim 513226633Sdimvoid VarRegion::dumpToStream(raw_ostream &os) const { 514226633Sdim os << *cast<VarDecl>(D); 515218887Sdim} 516218887Sdim 517218887Sdimvoid RegionRawOffset::dump() const { 518218887Sdim dumpToStream(llvm::errs()); 519218887Sdim} 520218887Sdim 521226633Sdimvoid RegionRawOffset::dumpToStream(raw_ostream &os) const { 522218887Sdim os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}'; 523218887Sdim} 524218887Sdim 525226633Sdimvoid StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const { 526218887Sdim os << "StaticGlobalsMemSpace{" << CR << '}'; 527218887Sdim} 528218887Sdim 529234353Sdimvoid GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const { 530234353Sdim os << "GlobalInternalSpaceRegion"; 531234353Sdim} 532234353Sdim 533234353Sdimvoid GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const { 534234353Sdim os << "GlobalSystemSpaceRegion"; 535234353Sdim} 536234353Sdim 537234353Sdimvoid GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const { 538234353Sdim os << "GlobalImmutableSpaceRegion"; 539234353Sdim} 540234353Sdim 541239462Sdimvoid HeapSpaceRegion::dumpToStream(raw_ostream &os) const { 542239462Sdim os << "HeapSpaceRegion"; 543239462Sdim} 544239462Sdim 545239462Sdimvoid UnknownSpaceRegion::dumpToStream(raw_ostream &os) const { 546239462Sdim os << "UnknownSpaceRegion"; 547239462Sdim} 548239462Sdim 549239462Sdimvoid StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const { 550239462Sdim os << "StackArgumentsSpaceRegion"; 551239462Sdim} 552239462Sdim 553239462Sdimvoid StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const { 554239462Sdim os << "StackLocalsSpaceRegion"; 555239462Sdim} 556239462Sdim 557239462Sdimbool MemRegion::canPrintPretty() const { 558239462Sdim return false; 559239462Sdim} 560239462Sdim 561239462Sdimvoid MemRegion::printPretty(raw_ostream &os) const { 562234353Sdim return; 563234353Sdim} 564234353Sdim 565239462Sdimbool VarRegion::canPrintPretty() const { 566239462Sdim return true; 567239462Sdim} 568239462Sdim 569239462Sdimvoid VarRegion::printPretty(raw_ostream &os) const { 570234353Sdim os << getDecl()->getName(); 571234353Sdim} 572234353Sdim 573249423Sdimbool ObjCIvarRegion::canPrintPretty() const { 574249423Sdim return true; 575249423Sdim} 576249423Sdim 577249423Sdimvoid ObjCIvarRegion::printPretty(raw_ostream &os) const { 578249423Sdim os << getDecl()->getName(); 579249423Sdim} 580249423Sdim 581239462Sdimbool FieldRegion::canPrintPretty() const { 582239462Sdim return superRegion->canPrintPretty(); 583234353Sdim} 584234353Sdim 585239462Sdimvoid FieldRegion::printPretty(raw_ostream &os) const { 586239462Sdim superRegion->printPretty(os); 587239462Sdim os << "." << getDecl()->getName(); 588239462Sdim} 589239462Sdim 590218887Sdim//===----------------------------------------------------------------------===// 591218887Sdim// MemRegionManager methods. 592218887Sdim//===----------------------------------------------------------------------===// 593218887Sdim 594218887Sdimtemplate <typename REG> 595218887Sdimconst REG *MemRegionManager::LazyAllocate(REG*& region) { 596218887Sdim if (!region) { 597218887Sdim region = (REG*) A.Allocate<REG>(); 598218887Sdim new (region) REG(this); 599218887Sdim } 600218887Sdim 601218887Sdim return region; 602218887Sdim} 603218887Sdim 604218887Sdimtemplate <typename REG, typename ARG> 605218887Sdimconst REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) { 606218887Sdim if (!region) { 607218887Sdim region = (REG*) A.Allocate<REG>(); 608218887Sdim new (region) REG(this, a); 609218887Sdim } 610218887Sdim 611218887Sdim return region; 612218887Sdim} 613218887Sdim 614218887Sdimconst StackLocalsSpaceRegion* 615218887SdimMemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) { 616218887Sdim assert(STC); 617218887Sdim StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC]; 618218887Sdim 619218887Sdim if (R) 620218887Sdim return R; 621218887Sdim 622218887Sdim R = A.Allocate<StackLocalsSpaceRegion>(); 623218887Sdim new (R) StackLocalsSpaceRegion(this, STC); 624218887Sdim return R; 625218887Sdim} 626218887Sdim 627218887Sdimconst StackArgumentsSpaceRegion * 628218887SdimMemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) { 629218887Sdim assert(STC); 630218887Sdim StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC]; 631218887Sdim 632218887Sdim if (R) 633218887Sdim return R; 634218887Sdim 635218887Sdim R = A.Allocate<StackArgumentsSpaceRegion>(); 636218887Sdim new (R) StackArgumentsSpaceRegion(this, STC); 637218887Sdim return R; 638218887Sdim} 639218887Sdim 640218887Sdimconst GlobalsSpaceRegion 641234353Sdim*MemRegionManager::getGlobalsRegion(MemRegion::Kind K, 642234353Sdim const CodeTextRegion *CR) { 643234353Sdim if (!CR) { 644234353Sdim if (K == MemRegion::GlobalSystemSpaceRegionKind) 645234353Sdim return LazyAllocate(SystemGlobals); 646234353Sdim if (K == MemRegion::GlobalImmutableSpaceRegionKind) 647234353Sdim return LazyAllocate(ImmutableGlobals); 648234353Sdim assert(K == MemRegion::GlobalInternalSpaceRegionKind); 649234353Sdim return LazyAllocate(InternalGlobals); 650234353Sdim } 651218887Sdim 652234353Sdim assert(K == MemRegion::StaticGlobalSpaceRegionKind); 653218887Sdim StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR]; 654218887Sdim if (R) 655218887Sdim return R; 656218887Sdim 657218887Sdim R = A.Allocate<StaticGlobalSpaceRegion>(); 658218887Sdim new (R) StaticGlobalSpaceRegion(this, CR); 659218887Sdim return R; 660218887Sdim} 661218887Sdim 662218887Sdimconst HeapSpaceRegion *MemRegionManager::getHeapRegion() { 663218887Sdim return LazyAllocate(heap); 664218887Sdim} 665218887Sdim 666218887Sdimconst MemSpaceRegion *MemRegionManager::getUnknownRegion() { 667218887Sdim return LazyAllocate(unknown); 668218887Sdim} 669218887Sdim 670218887Sdimconst MemSpaceRegion *MemRegionManager::getCodeRegion() { 671218887Sdim return LazyAllocate(code); 672218887Sdim} 673218887Sdim 674218887Sdim//===----------------------------------------------------------------------===// 675218887Sdim// Constructing regions. 676218887Sdim//===----------------------------------------------------------------------===// 677218887Sdimconst StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){ 678218887Sdim return getSubRegion<StringRegion>(Str, getGlobalsRegion()); 679218887Sdim} 680218887Sdim 681234353Sdimconst ObjCStringRegion * 682234353SdimMemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){ 683234353Sdim return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion()); 684234353Sdim} 685234353Sdim 686239462Sdim/// Look through a chain of LocationContexts to either find the 687239462Sdim/// StackFrameContext that matches a DeclContext, or find a VarRegion 688239462Sdim/// for a variable captured by a block. 689239462Sdimstatic llvm::PointerUnion<const StackFrameContext *, const VarRegion *> 690239462SdimgetStackOrCaptureRegionForDeclContext(const LocationContext *LC, 691239462Sdim const DeclContext *DC, 692239462Sdim const VarDecl *VD) { 693239462Sdim while (LC) { 694239462Sdim if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) { 695239462Sdim if (cast<DeclContext>(SFC->getDecl()) == DC) 696239462Sdim return SFC; 697239462Sdim } 698239462Sdim if (const BlockInvocationContext *BC = 699239462Sdim dyn_cast<BlockInvocationContext>(LC)) { 700239462Sdim const BlockDataRegion *BR = 701239462Sdim static_cast<const BlockDataRegion*>(BC->getContextData()); 702239462Sdim // FIXME: This can be made more efficient. 703239462Sdim for (BlockDataRegion::referenced_vars_iterator 704239462Sdim I = BR->referenced_vars_begin(), 705239462Sdim E = BR->referenced_vars_end(); I != E; ++I) { 706239462Sdim if (const VarRegion *VR = dyn_cast<VarRegion>(I.getOriginalRegion())) 707239462Sdim if (VR->getDecl() == VD) 708239462Sdim return cast<VarRegion>(I.getCapturedRegion()); 709239462Sdim } 710239462Sdim } 711239462Sdim 712239462Sdim LC = LC->getParent(); 713239462Sdim } 714239462Sdim return (const StackFrameContext*)0; 715239462Sdim} 716239462Sdim 717218887Sdimconst VarRegion* MemRegionManager::getVarRegion(const VarDecl *D, 718218887Sdim const LocationContext *LC) { 719218887Sdim const MemRegion *sReg = 0; 720218887Sdim 721234353Sdim if (D->hasGlobalStorage() && !D->isStaticLocal()) { 722234353Sdim 723234353Sdim // First handle the globals defined in system headers. 724234353Sdim if (C.getSourceManager().isInSystemHeader(D->getLocation())) { 725234353Sdim // Whitelist the system globals which often DO GET modified, assume the 726234353Sdim // rest are immutable. 727234353Sdim if (D->getName().find("errno") != StringRef::npos) 728234353Sdim sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind); 729234353Sdim else 730234353Sdim sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 731234353Sdim 732234353Sdim // Treat other globals as GlobalInternal unless they are constants. 733234353Sdim } else { 734234353Sdim QualType GQT = D->getType(); 735234353Sdim const Type *GT = GQT.getTypePtrOrNull(); 736234353Sdim // TODO: We could walk the complex types here and see if everything is 737234353Sdim // constified. 738234353Sdim if (GT && GQT.isConstQualified() && GT->isArithmeticType()) 739234353Sdim sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 740234353Sdim else 741234353Sdim sReg = getGlobalsRegion(); 742234353Sdim } 743234353Sdim 744234353Sdim // Finally handle static locals. 745234353Sdim } else { 746218887Sdim // FIXME: Once we implement scope handling, we will need to properly lookup 747218887Sdim // 'D' to the proper LocationContext. 748218887Sdim const DeclContext *DC = D->getDeclContext(); 749239462Sdim llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V = 750239462Sdim getStackOrCaptureRegionForDeclContext(LC, DC, D); 751239462Sdim 752239462Sdim if (V.is<const VarRegion*>()) 753239462Sdim return V.get<const VarRegion*>(); 754239462Sdim 755239462Sdim const StackFrameContext *STC = V.get<const StackFrameContext*>(); 756218887Sdim 757218887Sdim if (!STC) 758218887Sdim sReg = getUnknownRegion(); 759218887Sdim else { 760218887Sdim if (D->hasLocalStorage()) { 761218887Sdim sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D) 762218887Sdim ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC)) 763218887Sdim : static_cast<const MemRegion*>(getStackLocalsRegion(STC)); 764218887Sdim } 765218887Sdim else { 766218887Sdim assert(D->isStaticLocal()); 767243830Sdim const Decl *STCD = STC->getDecl(); 768243830Sdim if (isa<FunctionDecl>(STCD) || isa<ObjCMethodDecl>(STCD)) 769234353Sdim sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, 770243830Sdim getFunctionTextRegion(cast<NamedDecl>(STCD))); 771243830Sdim else if (const BlockDecl *BD = dyn_cast<BlockDecl>(STCD)) { 772218887Sdim const BlockTextRegion *BTR = 773218887Sdim getBlockTextRegion(BD, 774218887Sdim C.getCanonicalType(BD->getSignatureAsWritten()->getType()), 775234353Sdim STC->getAnalysisDeclContext()); 776234353Sdim sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind, 777234353Sdim BTR); 778218887Sdim } 779218887Sdim else { 780218887Sdim sReg = getGlobalsRegion(); 781218887Sdim } 782218887Sdim } 783218887Sdim } 784218887Sdim } 785218887Sdim 786218887Sdim return getSubRegion<VarRegion>(D, sReg); 787218887Sdim} 788218887Sdim 789218887Sdimconst VarRegion *MemRegionManager::getVarRegion(const VarDecl *D, 790218887Sdim const MemRegion *superR) { 791218887Sdim return getSubRegion<VarRegion>(D, superR); 792218887Sdim} 793218887Sdim 794218887Sdimconst BlockDataRegion * 795218887SdimMemRegionManager::getBlockDataRegion(const BlockTextRegion *BC, 796218887Sdim const LocationContext *LC) { 797218887Sdim const MemRegion *sReg = 0; 798234353Sdim const BlockDecl *BD = BC->getDecl(); 799234353Sdim if (!BD->hasCaptures()) { 800234353Sdim // This handles 'static' blocks. 801234353Sdim sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); 802218887Sdim } 803218887Sdim else { 804234353Sdim if (LC) { 805234353Sdim // FIXME: Once we implement scope handling, we want the parent region 806234353Sdim // to be the scope. 807234353Sdim const StackFrameContext *STC = LC->getCurrentStackFrame(); 808234353Sdim assert(STC); 809234353Sdim sReg = getStackLocalsRegion(STC); 810234353Sdim } 811234353Sdim else { 812234353Sdim // We allow 'LC' to be NULL for cases where want BlockDataRegions 813234353Sdim // without context-sensitivity. 814234353Sdim sReg = getUnknownRegion(); 815234353Sdim } 816218887Sdim } 817218887Sdim 818218887Sdim return getSubRegion<BlockDataRegion>(BC, LC, sReg); 819218887Sdim} 820218887Sdim 821218887Sdimconst CompoundLiteralRegion* 822226633SdimMemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL, 823218887Sdim const LocationContext *LC) { 824218887Sdim 825218887Sdim const MemRegion *sReg = 0; 826218887Sdim 827218887Sdim if (CL->isFileScope()) 828218887Sdim sReg = getGlobalsRegion(); 829218887Sdim else { 830218887Sdim const StackFrameContext *STC = LC->getCurrentStackFrame(); 831218887Sdim assert(STC); 832218887Sdim sReg = getStackLocalsRegion(STC); 833218887Sdim } 834218887Sdim 835218887Sdim return getSubRegion<CompoundLiteralRegion>(CL, sReg); 836218887Sdim} 837218887Sdim 838218887Sdimconst ElementRegion* 839218887SdimMemRegionManager::getElementRegion(QualType elementType, NonLoc Idx, 840218887Sdim const MemRegion* superRegion, 841226633Sdim ASTContext &Ctx){ 842218887Sdim 843218887Sdim QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType(); 844218887Sdim 845218887Sdim llvm::FoldingSetNodeID ID; 846218887Sdim ElementRegion::ProfileRegion(ID, T, Idx, superRegion); 847218887Sdim 848226633Sdim void *InsertPos; 849218887Sdim MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); 850218887Sdim ElementRegion* R = cast_or_null<ElementRegion>(data); 851218887Sdim 852218887Sdim if (!R) { 853218887Sdim R = (ElementRegion*) A.Allocate<ElementRegion>(); 854218887Sdim new (R) ElementRegion(T, Idx, superRegion); 855218887Sdim Regions.InsertNode(R, InsertPos); 856218887Sdim } 857218887Sdim 858218887Sdim return R; 859218887Sdim} 860218887Sdim 861218887Sdimconst FunctionTextRegion * 862243830SdimMemRegionManager::getFunctionTextRegion(const NamedDecl *FD) { 863218887Sdim return getSubRegion<FunctionTextRegion>(FD, getCodeRegion()); 864218887Sdim} 865218887Sdim 866218887Sdimconst BlockTextRegion * 867218887SdimMemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy, 868234353Sdim AnalysisDeclContext *AC) { 869218887Sdim return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion()); 870218887Sdim} 871218887Sdim 872218887Sdim 873218887Sdim/// getSymbolicRegion - Retrieve or create a "symbolic" memory region. 874218887Sdimconst SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) { 875218887Sdim return getSubRegion<SymbolicRegion>(sym, getUnknownRegion()); 876218887Sdim} 877218887Sdim 878239462Sdimconst SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) { 879239462Sdim return getSubRegion<SymbolicRegion>(Sym, getHeapRegion()); 880239462Sdim} 881239462Sdim 882218887Sdimconst FieldRegion* 883226633SdimMemRegionManager::getFieldRegion(const FieldDecl *d, 884218887Sdim const MemRegion* superRegion){ 885218887Sdim return getSubRegion<FieldRegion>(d, superRegion); 886218887Sdim} 887218887Sdim 888218887Sdimconst ObjCIvarRegion* 889226633SdimMemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d, 890218887Sdim const MemRegion* superRegion) { 891218887Sdim return getSubRegion<ObjCIvarRegion>(d, superRegion); 892218887Sdim} 893218887Sdim 894218887Sdimconst CXXTempObjectRegion* 895218887SdimMemRegionManager::getCXXTempObjectRegion(Expr const *E, 896218887Sdim LocationContext const *LC) { 897218887Sdim const StackFrameContext *SFC = LC->getCurrentStackFrame(); 898218887Sdim assert(SFC); 899218887Sdim return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC)); 900218887Sdim} 901218887Sdim 902249423Sdim/// Checks whether \p BaseClass is a valid virtual or direct non-virtual base 903249423Sdim/// class of the type of \p Super. 904249423Sdimstatic bool isValidBaseClass(const CXXRecordDecl *BaseClass, 905249423Sdim const TypedValueRegion *Super, 906249423Sdim bool IsVirtual) { 907249423Sdim BaseClass = BaseClass->getCanonicalDecl(); 908249423Sdim 909249423Sdim const CXXRecordDecl *Class = Super->getValueType()->getAsCXXRecordDecl(); 910249423Sdim if (!Class) 911249423Sdim return true; 912249423Sdim 913249423Sdim if (IsVirtual) 914249423Sdim return Class->isVirtuallyDerivedFrom(BaseClass); 915249423Sdim 916249423Sdim for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(), 917249423Sdim E = Class->bases_end(); 918249423Sdim I != E; ++I) { 919249423Sdim if (I->getType()->getAsCXXRecordDecl()->getCanonicalDecl() == BaseClass) 920249423Sdim return true; 921249423Sdim } 922249423Sdim 923249423Sdim return false; 924249423Sdim} 925249423Sdim 926218887Sdimconst CXXBaseObjectRegion * 927249423SdimMemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *RD, 928249423Sdim const MemRegion *Super, 929249423Sdim bool IsVirtual) { 930249423Sdim if (isa<TypedValueRegion>(Super)) { 931249423Sdim assert(isValidBaseClass(RD, dyn_cast<TypedValueRegion>(Super), IsVirtual)); 932249423Sdim (void)isValidBaseClass; 933239462Sdim 934249423Sdim if (IsVirtual) { 935249423Sdim // Virtual base regions should not be layered, since the layout rules 936249423Sdim // are different. 937249423Sdim while (const CXXBaseObjectRegion *Base = 938249423Sdim dyn_cast<CXXBaseObjectRegion>(Super)) { 939249423Sdim Super = Base->getSuperRegion(); 940239462Sdim } 941249423Sdim assert(Super && !isa<MemSpaceRegion>(Super)); 942239462Sdim } 943239462Sdim } 944239462Sdim 945249423Sdim return getSubRegion<CXXBaseObjectRegion>(RD, IsVirtual, Super); 946218887Sdim} 947218887Sdim 948218887Sdimconst CXXThisRegion* 949218887SdimMemRegionManager::getCXXThisRegion(QualType thisPointerTy, 950218887Sdim const LocationContext *LC) { 951218887Sdim const StackFrameContext *STC = LC->getCurrentStackFrame(); 952218887Sdim assert(STC); 953218887Sdim const PointerType *PT = thisPointerTy->getAs<PointerType>(); 954218887Sdim assert(PT); 955218887Sdim return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC)); 956218887Sdim} 957218887Sdim 958218887Sdimconst AllocaRegion* 959226633SdimMemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt, 960218887Sdim const LocationContext *LC) { 961218887Sdim const StackFrameContext *STC = LC->getCurrentStackFrame(); 962218887Sdim assert(STC); 963218887Sdim return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC)); 964218887Sdim} 965218887Sdim 966218887Sdimconst MemSpaceRegion *MemRegion::getMemorySpace() const { 967218887Sdim const MemRegion *R = this; 968218887Sdim const SubRegion* SR = dyn_cast<SubRegion>(this); 969218887Sdim 970218887Sdim while (SR) { 971218887Sdim R = SR->getSuperRegion(); 972218887Sdim SR = dyn_cast<SubRegion>(R); 973218887Sdim } 974218887Sdim 975218887Sdim return dyn_cast<MemSpaceRegion>(R); 976218887Sdim} 977218887Sdim 978218887Sdimbool MemRegion::hasStackStorage() const { 979218887Sdim return isa<StackSpaceRegion>(getMemorySpace()); 980218887Sdim} 981218887Sdim 982218887Sdimbool MemRegion::hasStackNonParametersStorage() const { 983218887Sdim return isa<StackLocalsSpaceRegion>(getMemorySpace()); 984218887Sdim} 985218887Sdim 986218887Sdimbool MemRegion::hasStackParametersStorage() const { 987218887Sdim return isa<StackArgumentsSpaceRegion>(getMemorySpace()); 988218887Sdim} 989218887Sdim 990218887Sdimbool MemRegion::hasGlobalsOrParametersStorage() const { 991218887Sdim const MemSpaceRegion *MS = getMemorySpace(); 992218887Sdim return isa<StackArgumentsSpaceRegion>(MS) || 993218887Sdim isa<GlobalsSpaceRegion>(MS); 994218887Sdim} 995218887Sdim 996218887Sdim// getBaseRegion strips away all elements and fields, and get the base region 997218887Sdim// of them. 998218887Sdimconst MemRegion *MemRegion::getBaseRegion() const { 999218887Sdim const MemRegion *R = this; 1000218887Sdim while (true) { 1001218887Sdim switch (R->getKind()) { 1002218887Sdim case MemRegion::ElementRegionKind: 1003218887Sdim case MemRegion::FieldRegionKind: 1004218887Sdim case MemRegion::ObjCIvarRegionKind: 1005218887Sdim case MemRegion::CXXBaseObjectRegionKind: 1006218887Sdim R = cast<SubRegion>(R)->getSuperRegion(); 1007218887Sdim continue; 1008218887Sdim default: 1009218887Sdim break; 1010218887Sdim } 1011218887Sdim break; 1012218887Sdim } 1013218887Sdim return R; 1014218887Sdim} 1015218887Sdim 1016243830Sdimbool MemRegion::isSubRegionOf(const MemRegion *R) const { 1017243830Sdim return false; 1018243830Sdim} 1019243830Sdim 1020218887Sdim//===----------------------------------------------------------------------===// 1021218887Sdim// View handling. 1022218887Sdim//===----------------------------------------------------------------------===// 1023218887Sdim 1024239462Sdimconst MemRegion *MemRegion::StripCasts(bool StripBaseCasts) const { 1025218887Sdim const MemRegion *R = this; 1026218887Sdim while (true) { 1027239462Sdim switch (R->getKind()) { 1028239462Sdim case ElementRegionKind: { 1029239462Sdim const ElementRegion *ER = cast<ElementRegion>(R); 1030239462Sdim if (!ER->getIndex().isZeroConstant()) 1031239462Sdim return R; 1032239462Sdim R = ER->getSuperRegion(); 1033239462Sdim break; 1034218887Sdim } 1035239462Sdim case CXXBaseObjectRegionKind: 1036239462Sdim if (!StripBaseCasts) 1037239462Sdim return R; 1038239462Sdim R = cast<CXXBaseObjectRegion>(R)->getSuperRegion(); 1039239462Sdim break; 1040239462Sdim default: 1041239462Sdim return R; 1042239462Sdim } 1043218887Sdim } 1044218887Sdim} 1045218887Sdim 1046218887Sdim// FIXME: Merge with the implementation of the same method in Store.cpp 1047218887Sdimstatic bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 1048218887Sdim if (const RecordType *RT = Ty->getAs<RecordType>()) { 1049218887Sdim const RecordDecl *D = RT->getDecl(); 1050218887Sdim if (!D->getDefinition()) 1051218887Sdim return false; 1052218887Sdim } 1053218887Sdim 1054218887Sdim return true; 1055218887Sdim} 1056218887Sdim 1057218887SdimRegionRawOffset ElementRegion::getAsArrayOffset() const { 1058218887Sdim CharUnits offset = CharUnits::Zero(); 1059218887Sdim const ElementRegion *ER = this; 1060218887Sdim const MemRegion *superR = NULL; 1061218887Sdim ASTContext &C = getContext(); 1062218887Sdim 1063218887Sdim // FIXME: Handle multi-dimensional arrays. 1064218887Sdim 1065218887Sdim while (ER) { 1066218887Sdim superR = ER->getSuperRegion(); 1067218887Sdim 1068218887Sdim // FIXME: generalize to symbolic offsets. 1069218887Sdim SVal index = ER->getIndex(); 1070249423Sdim if (Optional<nonloc::ConcreteInt> CI = index.getAs<nonloc::ConcreteInt>()) { 1071218887Sdim // Update the offset. 1072218887Sdim int64_t i = CI->getValue().getSExtValue(); 1073218887Sdim 1074218887Sdim if (i != 0) { 1075218887Sdim QualType elemType = ER->getElementType(); 1076218887Sdim 1077218887Sdim // If we are pointing to an incomplete type, go no further. 1078218887Sdim if (!IsCompleteType(C, elemType)) { 1079218887Sdim superR = ER; 1080218887Sdim break; 1081218887Sdim } 1082218887Sdim 1083218887Sdim CharUnits size = C.getTypeSizeInChars(elemType); 1084218887Sdim offset += (i * size); 1085218887Sdim } 1086218887Sdim 1087218887Sdim // Go to the next ElementRegion (if any). 1088218887Sdim ER = dyn_cast<ElementRegion>(superR); 1089218887Sdim continue; 1090218887Sdim } 1091218887Sdim 1092218887Sdim return NULL; 1093218887Sdim } 1094218887Sdim 1095218887Sdim assert(superR && "super region cannot be NULL"); 1096218887Sdim return RegionRawOffset(superR, offset); 1097218887Sdim} 1098218887Sdim 1099249423Sdim 1100249423Sdim/// Returns true if \p Base is an immediate base class of \p Child 1101249423Sdimstatic bool isImmediateBase(const CXXRecordDecl *Child, 1102249423Sdim const CXXRecordDecl *Base) { 1103249423Sdim // Note that we do NOT canonicalize the base class here, because 1104249423Sdim // ASTRecordLayout doesn't either. If that leads us down the wrong path, 1105249423Sdim // so be it; at least we won't crash. 1106249423Sdim for (CXXRecordDecl::base_class_const_iterator I = Child->bases_begin(), 1107249423Sdim E = Child->bases_end(); 1108249423Sdim I != E; ++I) { 1109249423Sdim if (I->getType()->getAsCXXRecordDecl() == Base) 1110249423Sdim return true; 1111249423Sdim } 1112249423Sdim 1113249423Sdim return false; 1114249423Sdim} 1115249423Sdim 1116218887SdimRegionOffset MemRegion::getAsOffset() const { 1117218887Sdim const MemRegion *R = this; 1118239462Sdim const MemRegion *SymbolicOffsetBase = 0; 1119218887Sdim int64_t Offset = 0; 1120218887Sdim 1121218887Sdim while (1) { 1122218887Sdim switch (R->getKind()) { 1123249423Sdim case GenericMemSpaceRegionKind: 1124249423Sdim case StackLocalsSpaceRegionKind: 1125249423Sdim case StackArgumentsSpaceRegionKind: 1126249423Sdim case HeapSpaceRegionKind: 1127249423Sdim case UnknownSpaceRegionKind: 1128249423Sdim case StaticGlobalSpaceRegionKind: 1129249423Sdim case GlobalInternalSpaceRegionKind: 1130249423Sdim case GlobalSystemSpaceRegionKind: 1131249423Sdim case GlobalImmutableSpaceRegionKind: 1132249423Sdim // Stores can bind directly to a region space to set a default value. 1133249423Sdim assert(Offset == 0 && !SymbolicOffsetBase); 1134249423Sdim goto Finish; 1135239462Sdim 1136249423Sdim case FunctionTextRegionKind: 1137249423Sdim case BlockTextRegionKind: 1138249423Sdim case BlockDataRegionKind: 1139249423Sdim // These will never have bindings, but may end up having values requested 1140249423Sdim // if the user does some strange casting. 1141249423Sdim if (Offset != 0) 1142249423Sdim SymbolicOffsetBase = R; 1143249423Sdim goto Finish; 1144249423Sdim 1145218887Sdim case SymbolicRegionKind: 1146218887Sdim case AllocaRegionKind: 1147218887Sdim case CompoundLiteralRegionKind: 1148218887Sdim case CXXThisRegionKind: 1149218887Sdim case StringRegionKind: 1150249423Sdim case ObjCStringRegionKind: 1151218887Sdim case VarRegionKind: 1152218887Sdim case CXXTempObjectRegionKind: 1153249423Sdim // Usual base regions. 1154218887Sdim goto Finish; 1155239462Sdim 1156239462Sdim case ObjCIvarRegionKind: 1157239462Sdim // This is a little strange, but it's a compromise between 1158239462Sdim // ObjCIvarRegions having unknown compile-time offsets (when using the 1159239462Sdim // non-fragile runtime) and yet still being distinct, non-overlapping 1160239462Sdim // regions. Thus we treat them as "like" base regions for the purposes 1161239462Sdim // of computing offsets. 1162239462Sdim goto Finish; 1163239462Sdim 1164239462Sdim case CXXBaseObjectRegionKind: { 1165239462Sdim const CXXBaseObjectRegion *BOR = cast<CXXBaseObjectRegion>(R); 1166239462Sdim R = BOR->getSuperRegion(); 1167239462Sdim 1168239462Sdim QualType Ty; 1169249423Sdim bool RootIsSymbolic = false; 1170239462Sdim if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) { 1171239462Sdim Ty = TVR->getDesugaredValueType(getContext()); 1172239462Sdim } else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 1173239462Sdim // If our base region is symbolic, we don't know what type it really is. 1174239462Sdim // Pretend the type of the symbol is the true dynamic type. 1175239462Sdim // (This will at least be self-consistent for the life of the symbol.) 1176243830Sdim Ty = SR->getSymbol()->getType()->getPointeeType(); 1177249423Sdim RootIsSymbolic = true; 1178239462Sdim } 1179239462Sdim 1180239462Sdim const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl(); 1181239462Sdim if (!Child) { 1182239462Sdim // We cannot compute the offset of the base class. 1183239462Sdim SymbolicOffsetBase = R; 1184239462Sdim } 1185239462Sdim 1186249423Sdim if (RootIsSymbolic) { 1187249423Sdim // Base layers on symbolic regions may not be type-correct. 1188249423Sdim // Double-check the inheritance here, and revert to a symbolic offset 1189249423Sdim // if it's invalid (e.g. due to a reinterpret_cast). 1190249423Sdim if (BOR->isVirtual()) { 1191249423Sdim if (!Child->isVirtuallyDerivedFrom(BOR->getDecl())) 1192249423Sdim SymbolicOffsetBase = R; 1193249423Sdim } else { 1194249423Sdim if (!isImmediateBase(Child, BOR->getDecl())) 1195249423Sdim SymbolicOffsetBase = R; 1196249423Sdim } 1197249423Sdim } 1198249423Sdim 1199239462Sdim // Don't bother calculating precise offsets if we already have a 1200239462Sdim // symbolic offset somewhere in the chain. 1201239462Sdim if (SymbolicOffsetBase) 1202239462Sdim continue; 1203239462Sdim 1204249423Sdim CharUnits BaseOffset; 1205239462Sdim const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child); 1206249423Sdim if (BOR->isVirtual()) 1207249423Sdim BaseOffset = Layout.getVBaseClassOffset(BOR->getDecl()); 1208239462Sdim else 1209249423Sdim BaseOffset = Layout.getBaseClassOffset(BOR->getDecl()); 1210239462Sdim 1211239462Sdim // The base offset is in chars, not in bits. 1212239462Sdim Offset += BaseOffset.getQuantity() * getContext().getCharWidth(); 1213239462Sdim break; 1214239462Sdim } 1215218887Sdim case ElementRegionKind: { 1216218887Sdim const ElementRegion *ER = cast<ElementRegion>(R); 1217239462Sdim R = ER->getSuperRegion(); 1218239462Sdim 1219218887Sdim QualType EleTy = ER->getValueType(); 1220239462Sdim if (!IsCompleteType(getContext(), EleTy)) { 1221239462Sdim // We cannot compute the offset of the base class. 1222239462Sdim SymbolicOffsetBase = R; 1223239462Sdim continue; 1224239462Sdim } 1225218887Sdim 1226218887Sdim SVal Index = ER->getIndex(); 1227249423Sdim if (Optional<nonloc::ConcreteInt> CI = 1228249423Sdim Index.getAs<nonloc::ConcreteInt>()) { 1229239462Sdim // Don't bother calculating precise offsets if we already have a 1230239462Sdim // symbolic offset somewhere in the chain. 1231239462Sdim if (SymbolicOffsetBase) 1232239462Sdim continue; 1233239462Sdim 1234218887Sdim int64_t i = CI->getValue().getSExtValue(); 1235239462Sdim // This type size is in bits. 1236239462Sdim Offset += i * getContext().getTypeSize(EleTy); 1237218887Sdim } else { 1238218887Sdim // We cannot compute offset for non-concrete index. 1239239462Sdim SymbolicOffsetBase = R; 1240218887Sdim } 1241218887Sdim break; 1242218887Sdim } 1243218887Sdim case FieldRegionKind: { 1244218887Sdim const FieldRegion *FR = cast<FieldRegion>(R); 1245239462Sdim R = FR->getSuperRegion(); 1246239462Sdim 1247218887Sdim const RecordDecl *RD = FR->getDecl()->getParent(); 1248243830Sdim if (RD->isUnion() || !RD->isCompleteDefinition()) { 1249218887Sdim // We cannot compute offset for incomplete type. 1250243830Sdim // For unions, we could treat everything as offset 0, but we'd rather 1251243830Sdim // treat each field as a symbolic offset so they aren't stored on top 1252243830Sdim // of each other, since we depend on things in typed regions actually 1253243830Sdim // matching their types. 1254239462Sdim SymbolicOffsetBase = R; 1255239462Sdim } 1256239462Sdim 1257239462Sdim // Don't bother calculating precise offsets if we already have a 1258239462Sdim // symbolic offset somewhere in the chain. 1259239462Sdim if (SymbolicOffsetBase) 1260239462Sdim continue; 1261239462Sdim 1262218887Sdim // Get the field number. 1263218887Sdim unsigned idx = 0; 1264218887Sdim for (RecordDecl::field_iterator FI = RD->field_begin(), 1265218887Sdim FE = RD->field_end(); FI != FE; ++FI, ++idx) 1266218887Sdim if (FR->getDecl() == *FI) 1267218887Sdim break; 1268218887Sdim 1269218887Sdim const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD); 1270218887Sdim // This is offset in bits. 1271218887Sdim Offset += Layout.getFieldOffset(idx); 1272218887Sdim break; 1273218887Sdim } 1274218887Sdim } 1275218887Sdim } 1276218887Sdim 1277218887Sdim Finish: 1278239462Sdim if (SymbolicOffsetBase) 1279239462Sdim return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic); 1280218887Sdim return RegionOffset(R, Offset); 1281218887Sdim} 1282218887Sdim 1283218887Sdim//===----------------------------------------------------------------------===// 1284218887Sdim// BlockDataRegion 1285218887Sdim//===----------------------------------------------------------------------===// 1286218887Sdim 1287249423Sdimstd::pair<const VarRegion *, const VarRegion *> 1288249423SdimBlockDataRegion::getCaptureRegions(const VarDecl *VD) { 1289249423Sdim MemRegionManager &MemMgr = *getMemRegionManager(); 1290249423Sdim const VarRegion *VR = 0; 1291249423Sdim const VarRegion *OriginalVR = 0; 1292249423Sdim 1293249423Sdim if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) { 1294249423Sdim VR = MemMgr.getVarRegion(VD, this); 1295249423Sdim OriginalVR = MemMgr.getVarRegion(VD, LC); 1296249423Sdim } 1297249423Sdim else { 1298249423Sdim if (LC) { 1299249423Sdim VR = MemMgr.getVarRegion(VD, LC); 1300249423Sdim OriginalVR = VR; 1301249423Sdim } 1302249423Sdim else { 1303249423Sdim VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion()); 1304249423Sdim OriginalVR = MemMgr.getVarRegion(VD, LC); 1305249423Sdim } 1306249423Sdim } 1307249423Sdim return std::make_pair(VR, OriginalVR); 1308249423Sdim} 1309249423Sdim 1310218887Sdimvoid BlockDataRegion::LazyInitializeReferencedVars() { 1311218887Sdim if (ReferencedVars) 1312218887Sdim return; 1313218887Sdim 1314234353Sdim AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext(); 1315234353Sdim AnalysisDeclContext::referenced_decls_iterator I, E; 1316218887Sdim llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl()); 1317218887Sdim 1318218887Sdim if (I == E) { 1319218887Sdim ReferencedVars = (void*) 0x1; 1320218887Sdim return; 1321218887Sdim } 1322218887Sdim 1323218887Sdim MemRegionManager &MemMgr = *getMemRegionManager(); 1324218887Sdim llvm::BumpPtrAllocator &A = MemMgr.getAllocator(); 1325218887Sdim BumpVectorContext BC(A); 1326218887Sdim 1327218887Sdim typedef BumpVector<const MemRegion*> VarVec; 1328218887Sdim VarVec *BV = (VarVec*) A.Allocate<VarVec>(); 1329218887Sdim new (BV) VarVec(BC, E - I); 1330239462Sdim VarVec *BVOriginal = (VarVec*) A.Allocate<VarVec>(); 1331239462Sdim new (BVOriginal) VarVec(BC, E - I); 1332218887Sdim 1333218887Sdim for ( ; I != E; ++I) { 1334218887Sdim const VarRegion *VR = 0; 1335239462Sdim const VarRegion *OriginalVR = 0; 1336249423Sdim llvm::tie(VR, OriginalVR) = getCaptureRegions(*I); 1337218887Sdim assert(VR); 1338239462Sdim assert(OriginalVR); 1339218887Sdim BV->push_back(VR, BC); 1340239462Sdim BVOriginal->push_back(OriginalVR, BC); 1341218887Sdim } 1342218887Sdim 1343218887Sdim ReferencedVars = BV; 1344239462Sdim OriginalVars = BVOriginal; 1345218887Sdim} 1346218887Sdim 1347218887SdimBlockDataRegion::referenced_vars_iterator 1348218887SdimBlockDataRegion::referenced_vars_begin() const { 1349218887Sdim const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars(); 1350218887Sdim 1351218887Sdim BumpVector<const MemRegion*> *Vec = 1352218887Sdim static_cast<BumpVector<const MemRegion*>*>(ReferencedVars); 1353218887Sdim 1354239462Sdim if (Vec == (void*) 0x1) 1355239462Sdim return BlockDataRegion::referenced_vars_iterator(0, 0); 1356239462Sdim 1357239462Sdim BumpVector<const MemRegion*> *VecOriginal = 1358239462Sdim static_cast<BumpVector<const MemRegion*>*>(OriginalVars); 1359239462Sdim 1360239462Sdim return BlockDataRegion::referenced_vars_iterator(Vec->begin(), 1361239462Sdim VecOriginal->begin()); 1362218887Sdim} 1363218887Sdim 1364218887SdimBlockDataRegion::referenced_vars_iterator 1365218887SdimBlockDataRegion::referenced_vars_end() const { 1366218887Sdim const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars(); 1367218887Sdim 1368218887Sdim BumpVector<const MemRegion*> *Vec = 1369218887Sdim static_cast<BumpVector<const MemRegion*>*>(ReferencedVars); 1370218887Sdim 1371239462Sdim if (Vec == (void*) 0x1) 1372239462Sdim return BlockDataRegion::referenced_vars_iterator(0, 0); 1373239462Sdim 1374239462Sdim BumpVector<const MemRegion*> *VecOriginal = 1375239462Sdim static_cast<BumpVector<const MemRegion*>*>(OriginalVars); 1376239462Sdim 1377239462Sdim return BlockDataRegion::referenced_vars_iterator(Vec->end(), 1378239462Sdim VecOriginal->end()); 1379218887Sdim} 1380249423Sdim 1381249423Sdimconst VarRegion *BlockDataRegion::getOriginalRegion(const VarRegion *R) const { 1382249423Sdim for (referenced_vars_iterator I = referenced_vars_begin(), 1383249423Sdim E = referenced_vars_end(); 1384249423Sdim I != E; ++I) { 1385249423Sdim if (I.getCapturedRegion() == R) 1386249423Sdim return I.getOriginalRegion(); 1387249423Sdim } 1388249423Sdim return 0; 1389249423Sdim} 1390