1 //== MemRegion.cpp - Abstract memory regions for static analysis --*- C++ -*--//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines MemRegion and its subclasses. MemRegion defines a
11 // partially-typed abstraction of memory useful for path-sensitive dataflow
14 //===----------------------------------------------------------------------===//
16 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
18 #include "clang/Analysis/AnalysisContext.h"
19 #include "clang/Analysis/Support/BumpVector.h"
20 #include "clang/AST/CharUnits.h"
21 #include "clang/AST/DeclObjC.h"
22 #include "clang/AST/RecordLayout.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "llvm/Support/raw_ostream.h"
26 using namespace clang;
29 //===----------------------------------------------------------------------===//
30 // MemRegion Construction.
31 //===----------------------------------------------------------------------===//
33 template<typename RegionTy> struct MemRegionManagerTrait;
35 template <typename RegionTy, typename A1>
36 RegionTy* MemRegionManager::getRegion(const A1 a1) {
38 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
39 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
41 llvm::FoldingSetNodeID ID;
42 RegionTy::ProfileRegion(ID, a1, superRegion);
44 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
48 R = (RegionTy*) A.Allocate<RegionTy>();
49 new (R) RegionTy(a1, superRegion);
50 Regions.InsertNode(R, InsertPos);
56 template <typename RegionTy, typename A1>
57 RegionTy* MemRegionManager::getSubRegion(const A1 a1,
58 const MemRegion *superRegion) {
59 llvm::FoldingSetNodeID ID;
60 RegionTy::ProfileRegion(ID, a1, superRegion);
62 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
66 R = (RegionTy*) A.Allocate<RegionTy>();
67 new (R) RegionTy(a1, superRegion);
68 Regions.InsertNode(R, InsertPos);
74 template <typename RegionTy, typename A1, typename A2>
75 RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
77 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
78 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
80 llvm::FoldingSetNodeID ID;
81 RegionTy::ProfileRegion(ID, a1, a2, superRegion);
83 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
87 R = (RegionTy*) A.Allocate<RegionTy>();
88 new (R) RegionTy(a1, a2, superRegion);
89 Regions.InsertNode(R, InsertPos);
95 template <typename RegionTy, typename A1, typename A2>
96 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
97 const MemRegion *superRegion) {
99 llvm::FoldingSetNodeID ID;
100 RegionTy::ProfileRegion(ID, a1, a2, superRegion);
102 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
106 R = (RegionTy*) A.Allocate<RegionTy>();
107 new (R) RegionTy(a1, a2, superRegion);
108 Regions.InsertNode(R, InsertPos);
114 template <typename RegionTy, typename A1, typename A2, typename A3>
115 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3,
116 const MemRegion *superRegion) {
118 llvm::FoldingSetNodeID ID;
119 RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
121 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
125 R = (RegionTy*) A.Allocate<RegionTy>();
126 new (R) RegionTy(a1, a2, a3, superRegion);
127 Regions.InsertNode(R, InsertPos);
133 //===----------------------------------------------------------------------===//
134 // Object destruction.
135 //===----------------------------------------------------------------------===//
137 MemRegion::~MemRegion() {}
139 MemRegionManager::~MemRegionManager() {
140 // All regions and their data are BumpPtrAllocated. No need to call
141 // their destructors.
144 //===----------------------------------------------------------------------===//
146 //===----------------------------------------------------------------------===//
148 bool SubRegion::isSubRegionOf(const MemRegion* R) const {
149 const MemRegion* r = getSuperRegion();
153 if (const SubRegion* sr = dyn_cast<SubRegion>(r))
154 r = sr->getSuperRegion();
161 MemRegionManager* SubRegion::getMemRegionManager() const {
162 const SubRegion* r = this;
164 const MemRegion *superRegion = r->getSuperRegion();
165 if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
169 return superRegion->getMemRegionManager();
173 const StackFrameContext *VarRegion::getStackFrame() const {
174 const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
175 return SSR ? SSR->getStackFrame() : NULL;
178 //===----------------------------------------------------------------------===//
180 //===----------------------------------------------------------------------===//
182 DefinedOrUnknownSVal TypedValueRegion::getExtent(SValBuilder &svalBuilder) const {
183 ASTContext &Ctx = svalBuilder.getContext();
184 QualType T = getDesugaredValueType(Ctx);
186 if (isa<VariableArrayType>(T))
187 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
188 if (isa<IncompleteArrayType>(T))
191 CharUnits size = Ctx.getTypeSizeInChars(T);
192 QualType sizeTy = svalBuilder.getArrayIndexType();
193 return svalBuilder.makeIntVal(size.getQuantity(), sizeTy);
196 DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const {
197 DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder);
199 // A zero-length array at the end of a struct often stands for dynamically-
200 // allocated extra memory.
201 if (Extent.isZeroConstant()) {
202 QualType T = getDesugaredValueType(svalBuilder.getContext());
204 if (isa<ConstantArrayType>(T))
211 DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
212 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
215 DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
216 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
219 DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
220 return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
221 svalBuilder.getArrayIndexType());
224 ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg)
225 : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
227 const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
228 return cast<ObjCIvarDecl>(D);
231 QualType ObjCIvarRegion::getValueType() const {
232 return getDecl()->getType();
235 QualType CXXBaseObjectRegion::getValueType() const {
236 return QualType(decl->getTypeForDecl(), 0);
239 //===----------------------------------------------------------------------===//
240 // FoldingSet profiling.
241 //===----------------------------------------------------------------------===//
243 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
244 ID.AddInteger((unsigned)getKind());
247 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
248 ID.AddInteger((unsigned)getKind());
249 ID.AddPointer(getStackFrame());
252 void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
253 ID.AddInteger((unsigned)getKind());
254 ID.AddPointer(getCodeRegion());
257 void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
258 const StringLiteral* Str,
259 const MemRegion* superRegion) {
260 ID.AddInteger((unsigned) StringRegionKind);
262 ID.AddPointer(superRegion);
265 void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
266 const ObjCStringLiteral* Str,
267 const MemRegion* superRegion) {
268 ID.AddInteger((unsigned) ObjCStringRegionKind);
270 ID.AddPointer(superRegion);
273 void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
274 const Expr *Ex, unsigned cnt,
276 ID.AddInteger((unsigned) AllocaRegionKind);
281 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
282 ProfileRegion(ID, Ex, Cnt, superRegion);
285 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
286 CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
289 void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
290 const CompoundLiteralExpr *CL,
291 const MemRegion* superRegion) {
292 ID.AddInteger((unsigned) CompoundLiteralRegionKind);
294 ID.AddPointer(superRegion);
297 void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
298 const PointerType *PT,
299 const MemRegion *sRegion) {
300 ID.AddInteger((unsigned) CXXThisRegionKind);
302 ID.AddPointer(sRegion);
305 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
306 CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
309 void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
310 const ObjCIvarDecl *ivd,
311 const MemRegion* superRegion) {
312 DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
315 void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D,
316 const MemRegion* superRegion, Kind k) {
317 ID.AddInteger((unsigned) k);
319 ID.AddPointer(superRegion);
322 void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
323 DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
326 void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
327 VarRegion::ProfileRegion(ID, getDecl(), superRegion);
330 void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
331 const MemRegion *sreg) {
332 ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind);
337 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
338 SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
341 void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
342 QualType ElementType, SVal Idx,
343 const MemRegion* superRegion) {
344 ID.AddInteger(MemRegion::ElementRegionKind);
346 ID.AddPointer(superRegion);
350 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
351 ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
354 void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
355 const FunctionDecl *FD,
357 ID.AddInteger(MemRegion::FunctionTextRegionKind);
361 void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
362 FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
365 void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
366 const BlockDecl *BD, CanQualType,
367 const AnalysisDeclContext *AC,
369 ID.AddInteger(MemRegion::BlockTextRegionKind);
373 void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
374 BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
377 void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
378 const BlockTextRegion *BC,
379 const LocationContext *LC,
380 const MemRegion *sReg) {
381 ID.AddInteger(MemRegion::BlockDataRegionKind);
387 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
388 BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
391 void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
393 const MemRegion *sReg) {
398 void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
399 ProfileRegion(ID, Ex, getSuperRegion());
402 void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
403 const CXXRecordDecl *decl,
404 const MemRegion *sReg) {
409 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
410 ProfileRegion(ID, decl, superRegion);
413 //===----------------------------------------------------------------------===//
415 //===----------------------------------------------------------------------===//
417 void GlobalsSpaceRegion::anchor() { }
418 void HeapSpaceRegion::anchor() { }
419 void UnknownSpaceRegion::anchor() { }
420 void StackLocalsSpaceRegion::anchor() { }
421 void StackArgumentsSpaceRegion::anchor() { }
422 void TypedRegion::anchor() { }
423 void TypedValueRegion::anchor() { }
424 void CodeTextRegion::anchor() { }
425 void SubRegion::anchor() { }
427 //===----------------------------------------------------------------------===//
428 // Region pretty-printing.
429 //===----------------------------------------------------------------------===//
431 void MemRegion::dump() const {
432 dumpToStream(llvm::errs());
435 std::string MemRegion::getString() const {
437 llvm::raw_string_ostream os(s);
442 void MemRegion::dumpToStream(raw_ostream &os) const {
443 os << "<Unknown Region>";
446 void AllocaRegion::dumpToStream(raw_ostream &os) const {
447 os << "alloca{" << (void*) Ex << ',' << Cnt << '}';
450 void FunctionTextRegion::dumpToStream(raw_ostream &os) const {
451 os << "code{" << getDecl()->getDeclName().getAsString() << '}';
454 void BlockTextRegion::dumpToStream(raw_ostream &os) const {
455 os << "block_code{" << (void*) this << '}';
458 void BlockDataRegion::dumpToStream(raw_ostream &os) const {
459 os << "block_data{" << BC << '}';
462 void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
463 // FIXME: More elaborate pretty-printing.
464 os << "{ " << (void*) CL << " }";
467 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
468 os << "temp_object{" << getValueType().getAsString() << ','
469 << (void*) Ex << '}';
472 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
473 os << "base{" << superRegion << ',' << decl->getName() << '}';
476 void CXXThisRegion::dumpToStream(raw_ostream &os) const {
480 void ElementRegion::dumpToStream(raw_ostream &os) const {
481 os << "element{" << superRegion << ','
482 << Index << ',' << getElementType().getAsString() << '}';
485 void FieldRegion::dumpToStream(raw_ostream &os) const {
486 os << superRegion << "->" << *getDecl();
489 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
490 os << "ivar{" << superRegion << ',' << *getDecl() << '}';
493 void StringRegion::dumpToStream(raw_ostream &os) const {
494 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
497 void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
498 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
501 void SymbolicRegion::dumpToStream(raw_ostream &os) const {
502 os << "SymRegion{" << sym << '}';
505 void VarRegion::dumpToStream(raw_ostream &os) const {
506 os << *cast<VarDecl>(D);
509 void RegionRawOffset::dump() const {
510 dumpToStream(llvm::errs());
513 void RegionRawOffset::dumpToStream(raw_ostream &os) const {
514 os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
517 void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
518 os << "StaticGlobalsMemSpace{" << CR << '}';
521 void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
522 os << "GlobalInternalSpaceRegion";
525 void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
526 os << "GlobalSystemSpaceRegion";
529 void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
530 os << "GlobalImmutableSpaceRegion";
533 void HeapSpaceRegion::dumpToStream(raw_ostream &os) const {
534 os << "HeapSpaceRegion";
537 void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const {
538 os << "UnknownSpaceRegion";
541 void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const {
542 os << "StackArgumentsSpaceRegion";
545 void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const {
546 os << "StackLocalsSpaceRegion";
549 bool MemRegion::canPrintPretty() const {
553 void MemRegion::printPretty(raw_ostream &os) const {
557 bool VarRegion::canPrintPretty() const {
561 void VarRegion::printPretty(raw_ostream &os) const {
562 os << getDecl()->getName();
565 bool FieldRegion::canPrintPretty() const {
566 return superRegion->canPrintPretty();
569 void FieldRegion::printPretty(raw_ostream &os) const {
570 superRegion->printPretty(os);
571 os << "." << getDecl()->getName();
574 //===----------------------------------------------------------------------===//
575 // MemRegionManager methods.
576 //===----------------------------------------------------------------------===//
578 template <typename REG>
579 const REG *MemRegionManager::LazyAllocate(REG*& region) {
581 region = (REG*) A.Allocate<REG>();
582 new (region) REG(this);
588 template <typename REG, typename ARG>
589 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
591 region = (REG*) A.Allocate<REG>();
592 new (region) REG(this, a);
598 const StackLocalsSpaceRegion*
599 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
601 StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
606 R = A.Allocate<StackLocalsSpaceRegion>();
607 new (R) StackLocalsSpaceRegion(this, STC);
611 const StackArgumentsSpaceRegion *
612 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
614 StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
619 R = A.Allocate<StackArgumentsSpaceRegion>();
620 new (R) StackArgumentsSpaceRegion(this, STC);
624 const GlobalsSpaceRegion
625 *MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
626 const CodeTextRegion *CR) {
628 if (K == MemRegion::GlobalSystemSpaceRegionKind)
629 return LazyAllocate(SystemGlobals);
630 if (K == MemRegion::GlobalImmutableSpaceRegionKind)
631 return LazyAllocate(ImmutableGlobals);
632 assert(K == MemRegion::GlobalInternalSpaceRegionKind);
633 return LazyAllocate(InternalGlobals);
636 assert(K == MemRegion::StaticGlobalSpaceRegionKind);
637 StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
641 R = A.Allocate<StaticGlobalSpaceRegion>();
642 new (R) StaticGlobalSpaceRegion(this, CR);
646 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
647 return LazyAllocate(heap);
650 const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
651 return LazyAllocate(unknown);
654 const MemSpaceRegion *MemRegionManager::getCodeRegion() {
655 return LazyAllocate(code);
658 //===----------------------------------------------------------------------===//
659 // Constructing regions.
660 //===----------------------------------------------------------------------===//
661 const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
662 return getSubRegion<StringRegion>(Str, getGlobalsRegion());
665 const ObjCStringRegion *
666 MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){
667 return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion());
670 /// Look through a chain of LocationContexts to either find the
671 /// StackFrameContext that matches a DeclContext, or find a VarRegion
672 /// for a variable captured by a block.
673 static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
674 getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
675 const DeclContext *DC,
678 if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
679 if (cast<DeclContext>(SFC->getDecl()) == DC)
682 if (const BlockInvocationContext *BC =
683 dyn_cast<BlockInvocationContext>(LC)) {
684 const BlockDataRegion *BR =
685 static_cast<const BlockDataRegion*>(BC->getContextData());
686 // FIXME: This can be made more efficient.
687 for (BlockDataRegion::referenced_vars_iterator
688 I = BR->referenced_vars_begin(),
689 E = BR->referenced_vars_end(); I != E; ++I) {
690 if (const VarRegion *VR = dyn_cast<VarRegion>(I.getOriginalRegion()))
691 if (VR->getDecl() == VD)
692 return cast<VarRegion>(I.getCapturedRegion());
696 LC = LC->getParent();
698 return (const StackFrameContext*)0;
701 const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
702 const LocationContext *LC) {
703 const MemRegion *sReg = 0;
705 if (D->hasGlobalStorage() && !D->isStaticLocal()) {
707 // First handle the globals defined in system headers.
708 if (C.getSourceManager().isInSystemHeader(D->getLocation())) {
709 // Whitelist the system globals which often DO GET modified, assume the
710 // rest are immutable.
711 if (D->getName().find("errno") != StringRef::npos)
712 sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
714 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
716 // Treat other globals as GlobalInternal unless they are constants.
718 QualType GQT = D->getType();
719 const Type *GT = GQT.getTypePtrOrNull();
720 // TODO: We could walk the complex types here and see if everything is
722 if (GT && GQT.isConstQualified() && GT->isArithmeticType())
723 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
725 sReg = getGlobalsRegion();
728 // Finally handle static locals.
730 // FIXME: Once we implement scope handling, we will need to properly lookup
731 // 'D' to the proper LocationContext.
732 const DeclContext *DC = D->getDeclContext();
733 llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V =
734 getStackOrCaptureRegionForDeclContext(LC, DC, D);
736 if (V.is<const VarRegion*>())
737 return V.get<const VarRegion*>();
739 const StackFrameContext *STC = V.get<const StackFrameContext*>();
742 sReg = getUnknownRegion();
744 if (D->hasLocalStorage()) {
745 sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
746 ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
747 : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
750 assert(D->isStaticLocal());
751 const Decl *D = STC->getDecl();
752 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
753 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
754 getFunctionTextRegion(FD));
755 else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
756 const BlockTextRegion *BTR =
757 getBlockTextRegion(BD,
758 C.getCanonicalType(BD->getSignatureAsWritten()->getType()),
759 STC->getAnalysisDeclContext());
760 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
764 // FIXME: For ObjC-methods, we need a new CodeTextRegion. For now
765 // just use the main global memspace.
766 sReg = getGlobalsRegion();
772 return getSubRegion<VarRegion>(D, sReg);
775 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
776 const MemRegion *superR) {
777 return getSubRegion<VarRegion>(D, superR);
780 const BlockDataRegion *
781 MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC,
782 const LocationContext *LC) {
783 const MemRegion *sReg = 0;
784 const BlockDecl *BD = BC->getDecl();
785 if (!BD->hasCaptures()) {
786 // This handles 'static' blocks.
787 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
791 // FIXME: Once we implement scope handling, we want the parent region
793 const StackFrameContext *STC = LC->getCurrentStackFrame();
795 sReg = getStackLocalsRegion(STC);
798 // We allow 'LC' to be NULL for cases where want BlockDataRegions
799 // without context-sensitivity.
800 sReg = getUnknownRegion();
804 return getSubRegion<BlockDataRegion>(BC, LC, sReg);
807 const CompoundLiteralRegion*
808 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
809 const LocationContext *LC) {
811 const MemRegion *sReg = 0;
813 if (CL->isFileScope())
814 sReg = getGlobalsRegion();
816 const StackFrameContext *STC = LC->getCurrentStackFrame();
818 sReg = getStackLocalsRegion(STC);
821 return getSubRegion<CompoundLiteralRegion>(CL, sReg);
825 MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
826 const MemRegion* superRegion,
829 QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
831 llvm::FoldingSetNodeID ID;
832 ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
835 MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
836 ElementRegion* R = cast_or_null<ElementRegion>(data);
839 R = (ElementRegion*) A.Allocate<ElementRegion>();
840 new (R) ElementRegion(T, Idx, superRegion);
841 Regions.InsertNode(R, InsertPos);
847 const FunctionTextRegion *
848 MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) {
849 return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
852 const BlockTextRegion *
853 MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
854 AnalysisDeclContext *AC) {
855 return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
859 /// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
860 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
861 return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
864 const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
865 return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
869 MemRegionManager::getFieldRegion(const FieldDecl *d,
870 const MemRegion* superRegion){
871 return getSubRegion<FieldRegion>(d, superRegion);
874 const ObjCIvarRegion*
875 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
876 const MemRegion* superRegion) {
877 return getSubRegion<ObjCIvarRegion>(d, superRegion);
880 const CXXTempObjectRegion*
881 MemRegionManager::getCXXTempObjectRegion(Expr const *E,
882 LocationContext const *LC) {
883 const StackFrameContext *SFC = LC->getCurrentStackFrame();
885 return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
888 const CXXBaseObjectRegion *
889 MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *decl,
890 const MemRegion *superRegion) {
891 // Check that the base class is actually a direct base of this region.
892 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(superRegion)) {
893 if (const CXXRecordDecl *Class = TVR->getValueType()->getAsCXXRecordDecl()){
894 if (Class->isVirtuallyDerivedFrom(decl)) {
895 // Virtual base regions should not be layered, since the layout rules
897 while (const CXXBaseObjectRegion *Base =
898 dyn_cast<CXXBaseObjectRegion>(superRegion)) {
899 superRegion = Base->getSuperRegion();
901 assert(superRegion && !isa<MemSpaceRegion>(superRegion));
904 // Non-virtual bases should always be direct bases.
906 bool FoundBase = false;
907 for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(),
908 E = Class->bases_end();
910 if (I->getType()->getAsCXXRecordDecl() == decl) {
916 assert(FoundBase && "Not a direct base class of this region");
922 return getSubRegion<CXXBaseObjectRegion>(decl, superRegion);
926 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
927 const LocationContext *LC) {
928 const StackFrameContext *STC = LC->getCurrentStackFrame();
930 const PointerType *PT = thisPointerTy->getAs<PointerType>();
932 return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
936 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
937 const LocationContext *LC) {
938 const StackFrameContext *STC = LC->getCurrentStackFrame();
940 return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
943 const MemSpaceRegion *MemRegion::getMemorySpace() const {
944 const MemRegion *R = this;
945 const SubRegion* SR = dyn_cast<SubRegion>(this);
948 R = SR->getSuperRegion();
949 SR = dyn_cast<SubRegion>(R);
952 return dyn_cast<MemSpaceRegion>(R);
955 bool MemRegion::hasStackStorage() const {
956 return isa<StackSpaceRegion>(getMemorySpace());
959 bool MemRegion::hasStackNonParametersStorage() const {
960 return isa<StackLocalsSpaceRegion>(getMemorySpace());
963 bool MemRegion::hasStackParametersStorage() const {
964 return isa<StackArgumentsSpaceRegion>(getMemorySpace());
967 bool MemRegion::hasGlobalsOrParametersStorage() const {
968 const MemSpaceRegion *MS = getMemorySpace();
969 return isa<StackArgumentsSpaceRegion>(MS) ||
970 isa<GlobalsSpaceRegion>(MS);
973 // getBaseRegion strips away all elements and fields, and get the base region
975 const MemRegion *MemRegion::getBaseRegion() const {
976 const MemRegion *R = this;
978 switch (R->getKind()) {
979 case MemRegion::ElementRegionKind:
980 case MemRegion::FieldRegionKind:
981 case MemRegion::ObjCIvarRegionKind:
982 case MemRegion::CXXBaseObjectRegionKind:
983 R = cast<SubRegion>(R)->getSuperRegion();
993 //===----------------------------------------------------------------------===//
995 //===----------------------------------------------------------------------===//
997 const MemRegion *MemRegion::StripCasts(bool StripBaseCasts) const {
998 const MemRegion *R = this;
1000 switch (R->getKind()) {
1001 case ElementRegionKind: {
1002 const ElementRegion *ER = cast<ElementRegion>(R);
1003 if (!ER->getIndex().isZeroConstant())
1005 R = ER->getSuperRegion();
1008 case CXXBaseObjectRegionKind:
1009 if (!StripBaseCasts)
1011 R = cast<CXXBaseObjectRegion>(R)->getSuperRegion();
1019 // FIXME: Merge with the implementation of the same method in Store.cpp
1020 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
1021 if (const RecordType *RT = Ty->getAs<RecordType>()) {
1022 const RecordDecl *D = RT->getDecl();
1023 if (!D->getDefinition())
1030 RegionRawOffset ElementRegion::getAsArrayOffset() const {
1031 CharUnits offset = CharUnits::Zero();
1032 const ElementRegion *ER = this;
1033 const MemRegion *superR = NULL;
1034 ASTContext &C = getContext();
1036 // FIXME: Handle multi-dimensional arrays.
1039 superR = ER->getSuperRegion();
1041 // FIXME: generalize to symbolic offsets.
1042 SVal index = ER->getIndex();
1043 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
1044 // Update the offset.
1045 int64_t i = CI->getValue().getSExtValue();
1048 QualType elemType = ER->getElementType();
1050 // If we are pointing to an incomplete type, go no further.
1051 if (!IsCompleteType(C, elemType)) {
1056 CharUnits size = C.getTypeSizeInChars(elemType);
1057 offset += (i * size);
1060 // Go to the next ElementRegion (if any).
1061 ER = dyn_cast<ElementRegion>(superR);
1068 assert(superR && "super region cannot be NULL");
1069 return RegionRawOffset(superR, offset);
1072 RegionOffset MemRegion::getAsOffset() const {
1073 const MemRegion *R = this;
1074 const MemRegion *SymbolicOffsetBase = 0;
1078 switch (R->getKind()) {
1080 return RegionOffset(R, RegionOffset::Symbolic);
1082 case SymbolicRegionKind:
1083 case AllocaRegionKind:
1084 case CompoundLiteralRegionKind:
1085 case CXXThisRegionKind:
1086 case StringRegionKind:
1088 case CXXTempObjectRegionKind:
1091 case ObjCIvarRegionKind:
1092 // This is a little strange, but it's a compromise between
1093 // ObjCIvarRegions having unknown compile-time offsets (when using the
1094 // non-fragile runtime) and yet still being distinct, non-overlapping
1095 // regions. Thus we treat them as "like" base regions for the purposes
1096 // of computing offsets.
1099 case CXXBaseObjectRegionKind: {
1100 const CXXBaseObjectRegion *BOR = cast<CXXBaseObjectRegion>(R);
1101 R = BOR->getSuperRegion();
1104 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) {
1105 Ty = TVR->getDesugaredValueType(getContext());
1106 } else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1107 // If our base region is symbolic, we don't know what type it really is.
1108 // Pretend the type of the symbol is the true dynamic type.
1109 // (This will at least be self-consistent for the life of the symbol.)
1110 Ty = SR->getSymbol()->getType(getContext())->getPointeeType();
1113 const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl();
1115 // We cannot compute the offset of the base class.
1116 SymbolicOffsetBase = R;
1119 // Don't bother calculating precise offsets if we already have a
1120 // symbolic offset somewhere in the chain.
1121 if (SymbolicOffsetBase)
1124 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child);
1126 CharUnits BaseOffset;
1127 const CXXRecordDecl *Base = BOR->getDecl();
1128 if (Child->isVirtuallyDerivedFrom(Base))
1129 BaseOffset = Layout.getVBaseClassOffset(Base);
1131 BaseOffset = Layout.getBaseClassOffset(Base);
1133 // The base offset is in chars, not in bits.
1134 Offset += BaseOffset.getQuantity() * getContext().getCharWidth();
1137 case ElementRegionKind: {
1138 const ElementRegion *ER = cast<ElementRegion>(R);
1139 R = ER->getSuperRegion();
1141 QualType EleTy = ER->getValueType();
1142 if (!IsCompleteType(getContext(), EleTy)) {
1143 // We cannot compute the offset of the base class.
1144 SymbolicOffsetBase = R;
1148 SVal Index = ER->getIndex();
1149 if (const nonloc::ConcreteInt *CI=dyn_cast<nonloc::ConcreteInt>(&Index)) {
1150 // Don't bother calculating precise offsets if we already have a
1151 // symbolic offset somewhere in the chain.
1152 if (SymbolicOffsetBase)
1155 int64_t i = CI->getValue().getSExtValue();
1156 // This type size is in bits.
1157 Offset += i * getContext().getTypeSize(EleTy);
1159 // We cannot compute offset for non-concrete index.
1160 SymbolicOffsetBase = R;
1164 case FieldRegionKind: {
1165 const FieldRegion *FR = cast<FieldRegion>(R);
1166 R = FR->getSuperRegion();
1168 const RecordDecl *RD = FR->getDecl()->getParent();
1169 if (!RD->isCompleteDefinition()) {
1170 // We cannot compute offset for incomplete type.
1171 SymbolicOffsetBase = R;
1174 // Don't bother calculating precise offsets if we already have a
1175 // symbolic offset somewhere in the chain.
1176 if (SymbolicOffsetBase)
1179 // Get the field number.
1181 for (RecordDecl::field_iterator FI = RD->field_begin(),
1182 FE = RD->field_end(); FI != FE; ++FI, ++idx)
1183 if (FR->getDecl() == *FI)
1186 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
1187 // This is offset in bits.
1188 Offset += Layout.getFieldOffset(idx);
1195 if (SymbolicOffsetBase)
1196 return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic);
1197 return RegionOffset(R, Offset);
1200 //===----------------------------------------------------------------------===//
1202 //===----------------------------------------------------------------------===//
1204 void BlockDataRegion::LazyInitializeReferencedVars() {
1208 AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1209 AnalysisDeclContext::referenced_decls_iterator I, E;
1210 llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
1213 ReferencedVars = (void*) 0x1;
1217 MemRegionManager &MemMgr = *getMemRegionManager();
1218 llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1219 BumpVectorContext BC(A);
1221 typedef BumpVector<const MemRegion*> VarVec;
1222 VarVec *BV = (VarVec*) A.Allocate<VarVec>();
1223 new (BV) VarVec(BC, E - I);
1224 VarVec *BVOriginal = (VarVec*) A.Allocate<VarVec>();
1225 new (BVOriginal) VarVec(BC, E - I);
1227 for ( ; I != E; ++I) {
1228 const VarDecl *VD = *I;
1229 const VarRegion *VR = 0;
1230 const VarRegion *OriginalVR = 0;
1232 if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) {
1233 VR = MemMgr.getVarRegion(VD, this);
1234 OriginalVR = MemMgr.getVarRegion(VD, LC);
1238 VR = MemMgr.getVarRegion(VD, LC);
1242 VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
1243 OriginalVR = MemMgr.getVarRegion(VD, LC);
1249 BV->push_back(VR, BC);
1250 BVOriginal->push_back(OriginalVR, BC);
1253 ReferencedVars = BV;
1254 OriginalVars = BVOriginal;
1257 BlockDataRegion::referenced_vars_iterator
1258 BlockDataRegion::referenced_vars_begin() const {
1259 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1261 BumpVector<const MemRegion*> *Vec =
1262 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1264 if (Vec == (void*) 0x1)
1265 return BlockDataRegion::referenced_vars_iterator(0, 0);
1267 BumpVector<const MemRegion*> *VecOriginal =
1268 static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1270 return BlockDataRegion::referenced_vars_iterator(Vec->begin(),
1271 VecOriginal->begin());
1274 BlockDataRegion::referenced_vars_iterator
1275 BlockDataRegion::referenced_vars_end() const {
1276 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1278 BumpVector<const MemRegion*> *Vec =
1279 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1281 if (Vec == (void*) 0x1)
1282 return BlockDataRegion::referenced_vars_iterator(0, 0);
1284 BumpVector<const MemRegion*> *VecOriginal =
1285 static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1287 return BlockDataRegion::referenced_vars_iterator(Vec->end(),
1288 VecOriginal->end());