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/AST/Attr.h"
18 #include "clang/AST/CharUnits.h"
19 #include "clang/AST/DeclObjC.h"
20 #include "clang/AST/RecordLayout.h"
21 #include "clang/Analysis/AnalysisContext.h"
22 #include "clang/Analysis/Support/BumpVector.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
25 #include "llvm/Support/raw_ostream.h"
27 using namespace clang;
30 //===----------------------------------------------------------------------===//
31 // MemRegion Construction.
32 //===----------------------------------------------------------------------===//
34 template<typename RegionTy> struct MemRegionManagerTrait;
36 template <typename RegionTy, typename A1>
37 RegionTy* MemRegionManager::getRegion(const A1 a1) {
39 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
40 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
42 llvm::FoldingSetNodeID ID;
43 RegionTy::ProfileRegion(ID, a1, superRegion);
45 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
49 R = (RegionTy*) A.Allocate<RegionTy>();
50 new (R) RegionTy(a1, superRegion);
51 Regions.InsertNode(R, InsertPos);
57 template <typename RegionTy, typename A1>
58 RegionTy* MemRegionManager::getSubRegion(const A1 a1,
59 const MemRegion *superRegion) {
60 llvm::FoldingSetNodeID ID;
61 RegionTy::ProfileRegion(ID, a1, superRegion);
63 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
67 R = (RegionTy*) A.Allocate<RegionTy>();
68 new (R) RegionTy(a1, superRegion);
69 Regions.InsertNode(R, InsertPos);
75 template <typename RegionTy, typename A1, typename A2>
76 RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
78 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
79 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
81 llvm::FoldingSetNodeID ID;
82 RegionTy::ProfileRegion(ID, a1, a2, superRegion);
84 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
88 R = (RegionTy*) A.Allocate<RegionTy>();
89 new (R) RegionTy(a1, a2, superRegion);
90 Regions.InsertNode(R, InsertPos);
96 template <typename RegionTy, typename A1, typename A2>
97 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
98 const MemRegion *superRegion) {
100 llvm::FoldingSetNodeID ID;
101 RegionTy::ProfileRegion(ID, a1, a2, superRegion);
103 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
107 R = (RegionTy*) A.Allocate<RegionTy>();
108 new (R) RegionTy(a1, a2, superRegion);
109 Regions.InsertNode(R, InsertPos);
115 template <typename RegionTy, typename A1, typename A2, typename A3>
116 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3,
117 const MemRegion *superRegion) {
119 llvm::FoldingSetNodeID ID;
120 RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
122 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
126 R = (RegionTy*) A.Allocate<RegionTy>();
127 new (R) RegionTy(a1, a2, a3, superRegion);
128 Regions.InsertNode(R, InsertPos);
134 //===----------------------------------------------------------------------===//
135 // Object destruction.
136 //===----------------------------------------------------------------------===//
138 MemRegion::~MemRegion() {}
140 MemRegionManager::~MemRegionManager() {
141 // All regions and their data are BumpPtrAllocated. No need to call
142 // their destructors.
145 //===----------------------------------------------------------------------===//
147 //===----------------------------------------------------------------------===//
149 bool SubRegion::isSubRegionOf(const MemRegion* R) const {
150 const MemRegion* r = getSuperRegion();
154 if (const SubRegion* sr = dyn_cast<SubRegion>(r))
155 r = sr->getSuperRegion();
162 MemRegionManager* SubRegion::getMemRegionManager() const {
163 const SubRegion* r = this;
165 const MemRegion *superRegion = r->getSuperRegion();
166 if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
170 return superRegion->getMemRegionManager();
174 const StackFrameContext *VarRegion::getStackFrame() const {
175 const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
176 return SSR ? SSR->getStackFrame() : NULL;
179 //===----------------------------------------------------------------------===//
181 //===----------------------------------------------------------------------===//
183 DefinedOrUnknownSVal TypedValueRegion::getExtent(SValBuilder &svalBuilder) const {
184 ASTContext &Ctx = svalBuilder.getContext();
185 QualType T = getDesugaredValueType(Ctx);
187 if (isa<VariableArrayType>(T))
188 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
189 if (isa<IncompleteArrayType>(T))
192 CharUnits size = Ctx.getTypeSizeInChars(T);
193 QualType sizeTy = svalBuilder.getArrayIndexType();
194 return svalBuilder.makeIntVal(size.getQuantity(), sizeTy);
197 DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const {
198 // Force callers to deal with bitfields explicitly.
199 if (getDecl()->isBitField())
202 DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder);
204 // A zero-length array at the end of a struct often stands for dynamically-
205 // allocated extra memory.
206 if (Extent.isZeroConstant()) {
207 QualType T = getDesugaredValueType(svalBuilder.getContext());
209 if (isa<ConstantArrayType>(T))
216 DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
217 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
220 DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
221 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
224 DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
225 return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
226 svalBuilder.getArrayIndexType());
229 ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg)
230 : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
232 const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
233 return cast<ObjCIvarDecl>(D);
236 QualType ObjCIvarRegion::getValueType() const {
237 return getDecl()->getType();
240 QualType CXXBaseObjectRegion::getValueType() const {
241 return QualType(getDecl()->getTypeForDecl(), 0);
244 //===----------------------------------------------------------------------===//
245 // FoldingSet profiling.
246 //===----------------------------------------------------------------------===//
248 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
249 ID.AddInteger((unsigned)getKind());
252 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
253 ID.AddInteger((unsigned)getKind());
254 ID.AddPointer(getStackFrame());
257 void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
258 ID.AddInteger((unsigned)getKind());
259 ID.AddPointer(getCodeRegion());
262 void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
263 const StringLiteral* Str,
264 const MemRegion* superRegion) {
265 ID.AddInteger((unsigned) StringRegionKind);
267 ID.AddPointer(superRegion);
270 void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
271 const ObjCStringLiteral* Str,
272 const MemRegion* superRegion) {
273 ID.AddInteger((unsigned) ObjCStringRegionKind);
275 ID.AddPointer(superRegion);
278 void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
279 const Expr *Ex, unsigned cnt,
280 const MemRegion *superRegion) {
281 ID.AddInteger((unsigned) AllocaRegionKind);
284 ID.AddPointer(superRegion);
287 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
288 ProfileRegion(ID, Ex, Cnt, superRegion);
291 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
292 CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
295 void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
296 const CompoundLiteralExpr *CL,
297 const MemRegion* superRegion) {
298 ID.AddInteger((unsigned) CompoundLiteralRegionKind);
300 ID.AddPointer(superRegion);
303 void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
304 const PointerType *PT,
305 const MemRegion *sRegion) {
306 ID.AddInteger((unsigned) CXXThisRegionKind);
308 ID.AddPointer(sRegion);
311 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
312 CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
315 void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
316 const ObjCIvarDecl *ivd,
317 const MemRegion* superRegion) {
318 DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
321 void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D,
322 const MemRegion* superRegion, Kind k) {
323 ID.AddInteger((unsigned) k);
325 ID.AddPointer(superRegion);
328 void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
329 DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
332 void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
333 VarRegion::ProfileRegion(ID, getDecl(), superRegion);
336 void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
337 const MemRegion *sreg) {
338 ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind);
343 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
344 SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
347 void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
348 QualType ElementType, SVal Idx,
349 const MemRegion* superRegion) {
350 ID.AddInteger(MemRegion::ElementRegionKind);
352 ID.AddPointer(superRegion);
356 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
357 ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
360 void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
363 ID.AddInteger(MemRegion::FunctionTextRegionKind);
367 void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
368 FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
371 void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
372 const BlockDecl *BD, CanQualType,
373 const AnalysisDeclContext *AC,
375 ID.AddInteger(MemRegion::BlockTextRegionKind);
379 void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
380 BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
383 void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
384 const BlockTextRegion *BC,
385 const LocationContext *LC,
386 const MemRegion *sReg) {
387 ID.AddInteger(MemRegion::BlockDataRegionKind);
393 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
394 BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
397 void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
399 const MemRegion *sReg) {
404 void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
405 ProfileRegion(ID, Ex, getSuperRegion());
408 void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
409 const CXXRecordDecl *RD,
411 const MemRegion *SReg) {
413 ID.AddBoolean(IsVirtual);
417 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
418 ProfileRegion(ID, getDecl(), isVirtual(), superRegion);
421 //===----------------------------------------------------------------------===//
423 //===----------------------------------------------------------------------===//
425 void GlobalsSpaceRegion::anchor() { }
426 void HeapSpaceRegion::anchor() { }
427 void UnknownSpaceRegion::anchor() { }
428 void StackLocalsSpaceRegion::anchor() { }
429 void StackArgumentsSpaceRegion::anchor() { }
430 void TypedRegion::anchor() { }
431 void TypedValueRegion::anchor() { }
432 void CodeTextRegion::anchor() { }
433 void SubRegion::anchor() { }
435 //===----------------------------------------------------------------------===//
436 // Region pretty-printing.
437 //===----------------------------------------------------------------------===//
439 void MemRegion::dump() const {
440 dumpToStream(llvm::errs());
443 std::string MemRegion::getString() const {
445 llvm::raw_string_ostream os(s);
450 void MemRegion::dumpToStream(raw_ostream &os) const {
451 os << "<Unknown Region>";
454 void AllocaRegion::dumpToStream(raw_ostream &os) const {
455 os << "alloca{" << (const void*) Ex << ',' << Cnt << '}';
458 void FunctionTextRegion::dumpToStream(raw_ostream &os) const {
459 os << "code{" << getDecl()->getDeclName().getAsString() << '}';
462 void BlockTextRegion::dumpToStream(raw_ostream &os) const {
463 os << "block_code{" << (const void*) this << '}';
466 void BlockDataRegion::dumpToStream(raw_ostream &os) const {
467 os << "block_data{" << BC << '}';
470 void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
471 // FIXME: More elaborate pretty-printing.
472 os << "{ " << (const void*) CL << " }";
475 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
476 os << "temp_object{" << getValueType().getAsString() << ','
477 << (const void*) Ex << '}';
480 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
481 os << "base{" << superRegion << ',' << getDecl()->getName() << '}';
484 void CXXThisRegion::dumpToStream(raw_ostream &os) const {
488 void ElementRegion::dumpToStream(raw_ostream &os) const {
489 os << "element{" << superRegion << ','
490 << Index << ',' << getElementType().getAsString() << '}';
493 void FieldRegion::dumpToStream(raw_ostream &os) const {
494 os << superRegion << "->" << *getDecl();
497 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
498 os << "ivar{" << superRegion << ',' << *getDecl() << '}';
501 void StringRegion::dumpToStream(raw_ostream &os) const {
502 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
505 void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
506 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
509 void SymbolicRegion::dumpToStream(raw_ostream &os) const {
510 os << "SymRegion{" << sym << '}';
513 void VarRegion::dumpToStream(raw_ostream &os) const {
514 os << *cast<VarDecl>(D);
517 void RegionRawOffset::dump() const {
518 dumpToStream(llvm::errs());
521 void RegionRawOffset::dumpToStream(raw_ostream &os) const {
522 os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
525 void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
526 os << "StaticGlobalsMemSpace{" << CR << '}';
529 void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
530 os << "GlobalInternalSpaceRegion";
533 void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
534 os << "GlobalSystemSpaceRegion";
537 void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
538 os << "GlobalImmutableSpaceRegion";
541 void HeapSpaceRegion::dumpToStream(raw_ostream &os) const {
542 os << "HeapSpaceRegion";
545 void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const {
546 os << "UnknownSpaceRegion";
549 void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const {
550 os << "StackArgumentsSpaceRegion";
553 void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const {
554 os << "StackLocalsSpaceRegion";
557 bool MemRegion::canPrintPretty() const {
561 void MemRegion::printPretty(raw_ostream &os) const {
565 bool VarRegion::canPrintPretty() const {
569 void VarRegion::printPretty(raw_ostream &os) const {
570 os << getDecl()->getName();
573 bool ObjCIvarRegion::canPrintPretty() const {
577 void ObjCIvarRegion::printPretty(raw_ostream &os) const {
578 os << getDecl()->getName();
581 bool FieldRegion::canPrintPretty() const {
582 return superRegion->canPrintPretty();
585 void FieldRegion::printPretty(raw_ostream &os) const {
586 superRegion->printPretty(os);
587 os << "." << getDecl()->getName();
590 //===----------------------------------------------------------------------===//
591 // MemRegionManager methods.
592 //===----------------------------------------------------------------------===//
594 template <typename REG>
595 const REG *MemRegionManager::LazyAllocate(REG*& region) {
597 region = (REG*) A.Allocate<REG>();
598 new (region) REG(this);
604 template <typename REG, typename ARG>
605 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
607 region = (REG*) A.Allocate<REG>();
608 new (region) REG(this, a);
614 const StackLocalsSpaceRegion*
615 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
617 StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
622 R = A.Allocate<StackLocalsSpaceRegion>();
623 new (R) StackLocalsSpaceRegion(this, STC);
627 const StackArgumentsSpaceRegion *
628 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
630 StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
635 R = A.Allocate<StackArgumentsSpaceRegion>();
636 new (R) StackArgumentsSpaceRegion(this, STC);
640 const GlobalsSpaceRegion
641 *MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
642 const CodeTextRegion *CR) {
644 if (K == MemRegion::GlobalSystemSpaceRegionKind)
645 return LazyAllocate(SystemGlobals);
646 if (K == MemRegion::GlobalImmutableSpaceRegionKind)
647 return LazyAllocate(ImmutableGlobals);
648 assert(K == MemRegion::GlobalInternalSpaceRegionKind);
649 return LazyAllocate(InternalGlobals);
652 assert(K == MemRegion::StaticGlobalSpaceRegionKind);
653 StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
657 R = A.Allocate<StaticGlobalSpaceRegion>();
658 new (R) StaticGlobalSpaceRegion(this, CR);
662 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
663 return LazyAllocate(heap);
666 const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
667 return LazyAllocate(unknown);
670 const MemSpaceRegion *MemRegionManager::getCodeRegion() {
671 return LazyAllocate(code);
674 //===----------------------------------------------------------------------===//
675 // Constructing regions.
676 //===----------------------------------------------------------------------===//
677 const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
678 return getSubRegion<StringRegion>(Str, getGlobalsRegion());
681 const ObjCStringRegion *
682 MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){
683 return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion());
686 /// Look through a chain of LocationContexts to either find the
687 /// StackFrameContext that matches a DeclContext, or find a VarRegion
688 /// for a variable captured by a block.
689 static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
690 getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
691 const DeclContext *DC,
694 if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
695 if (cast<DeclContext>(SFC->getDecl()) == DC)
698 if (const BlockInvocationContext *BC =
699 dyn_cast<BlockInvocationContext>(LC)) {
700 const BlockDataRegion *BR =
701 static_cast<const BlockDataRegion*>(BC->getContextData());
702 // FIXME: This can be made more efficient.
703 for (BlockDataRegion::referenced_vars_iterator
704 I = BR->referenced_vars_begin(),
705 E = BR->referenced_vars_end(); I != E; ++I) {
706 if (const VarRegion *VR = dyn_cast<VarRegion>(I.getOriginalRegion()))
707 if (VR->getDecl() == VD)
708 return cast<VarRegion>(I.getCapturedRegion());
712 LC = LC->getParent();
714 return (const StackFrameContext*)0;
717 const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
718 const LocationContext *LC) {
719 const MemRegion *sReg = 0;
721 if (D->hasGlobalStorage() && !D->isStaticLocal()) {
723 // First handle the globals defined in system headers.
724 if (C.getSourceManager().isInSystemHeader(D->getLocation())) {
725 // Whitelist the system globals which often DO GET modified, assume the
726 // rest are immutable.
727 if (D->getName().find("errno") != StringRef::npos)
728 sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
730 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
732 // Treat other globals as GlobalInternal unless they are constants.
734 QualType GQT = D->getType();
735 const Type *GT = GQT.getTypePtrOrNull();
736 // TODO: We could walk the complex types here and see if everything is
738 if (GT && GQT.isConstQualified() && GT->isArithmeticType())
739 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
741 sReg = getGlobalsRegion();
744 // Finally handle static locals.
746 // FIXME: Once we implement scope handling, we will need to properly lookup
747 // 'D' to the proper LocationContext.
748 const DeclContext *DC = D->getDeclContext();
749 llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V =
750 getStackOrCaptureRegionForDeclContext(LC, DC, D);
752 if (V.is<const VarRegion*>())
753 return V.get<const VarRegion*>();
755 const StackFrameContext *STC = V.get<const StackFrameContext*>();
758 sReg = getUnknownRegion();
760 if (D->hasLocalStorage()) {
761 sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
762 ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
763 : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
766 assert(D->isStaticLocal());
767 const Decl *STCD = STC->getDecl();
768 if (isa<FunctionDecl>(STCD) || isa<ObjCMethodDecl>(STCD))
769 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
770 getFunctionTextRegion(cast<NamedDecl>(STCD)));
771 else if (const BlockDecl *BD = dyn_cast<BlockDecl>(STCD)) {
772 const BlockTextRegion *BTR =
773 getBlockTextRegion(BD,
774 C.getCanonicalType(BD->getSignatureAsWritten()->getType()),
775 STC->getAnalysisDeclContext());
776 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
780 sReg = getGlobalsRegion();
786 return getSubRegion<VarRegion>(D, sReg);
789 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
790 const MemRegion *superR) {
791 return getSubRegion<VarRegion>(D, superR);
794 const BlockDataRegion *
795 MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC,
796 const LocationContext *LC) {
797 const MemRegion *sReg = 0;
798 const BlockDecl *BD = BC->getDecl();
799 if (!BD->hasCaptures()) {
800 // This handles 'static' blocks.
801 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
805 // FIXME: Once we implement scope handling, we want the parent region
807 const StackFrameContext *STC = LC->getCurrentStackFrame();
809 sReg = getStackLocalsRegion(STC);
812 // We allow 'LC' to be NULL for cases where want BlockDataRegions
813 // without context-sensitivity.
814 sReg = getUnknownRegion();
818 return getSubRegion<BlockDataRegion>(BC, LC, sReg);
821 const CompoundLiteralRegion*
822 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
823 const LocationContext *LC) {
825 const MemRegion *sReg = 0;
827 if (CL->isFileScope())
828 sReg = getGlobalsRegion();
830 const StackFrameContext *STC = LC->getCurrentStackFrame();
832 sReg = getStackLocalsRegion(STC);
835 return getSubRegion<CompoundLiteralRegion>(CL, sReg);
839 MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
840 const MemRegion* superRegion,
843 QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
845 llvm::FoldingSetNodeID ID;
846 ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
849 MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
850 ElementRegion* R = cast_or_null<ElementRegion>(data);
853 R = (ElementRegion*) A.Allocate<ElementRegion>();
854 new (R) ElementRegion(T, Idx, superRegion);
855 Regions.InsertNode(R, InsertPos);
861 const FunctionTextRegion *
862 MemRegionManager::getFunctionTextRegion(const NamedDecl *FD) {
863 return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
866 const BlockTextRegion *
867 MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
868 AnalysisDeclContext *AC) {
869 return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
873 /// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
874 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
875 return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
878 const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
879 return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
883 MemRegionManager::getFieldRegion(const FieldDecl *d,
884 const MemRegion* superRegion){
885 return getSubRegion<FieldRegion>(d, superRegion);
888 const ObjCIvarRegion*
889 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
890 const MemRegion* superRegion) {
891 return getSubRegion<ObjCIvarRegion>(d, superRegion);
894 const CXXTempObjectRegion*
895 MemRegionManager::getCXXTempObjectRegion(Expr const *E,
896 LocationContext const *LC) {
897 const StackFrameContext *SFC = LC->getCurrentStackFrame();
899 return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
902 /// Checks whether \p BaseClass is a valid virtual or direct non-virtual base
903 /// class of the type of \p Super.
904 static bool isValidBaseClass(const CXXRecordDecl *BaseClass,
905 const TypedValueRegion *Super,
907 BaseClass = BaseClass->getCanonicalDecl();
909 const CXXRecordDecl *Class = Super->getValueType()->getAsCXXRecordDecl();
914 return Class->isVirtuallyDerivedFrom(BaseClass);
916 for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(),
917 E = Class->bases_end();
919 if (I->getType()->getAsCXXRecordDecl()->getCanonicalDecl() == BaseClass)
926 const CXXBaseObjectRegion *
927 MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *RD,
928 const MemRegion *Super,
930 if (isa<TypedValueRegion>(Super)) {
931 assert(isValidBaseClass(RD, dyn_cast<TypedValueRegion>(Super), IsVirtual));
932 (void)isValidBaseClass;
935 // Virtual base regions should not be layered, since the layout rules
937 while (const CXXBaseObjectRegion *Base =
938 dyn_cast<CXXBaseObjectRegion>(Super)) {
939 Super = Base->getSuperRegion();
941 assert(Super && !isa<MemSpaceRegion>(Super));
945 return getSubRegion<CXXBaseObjectRegion>(RD, IsVirtual, Super);
949 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
950 const LocationContext *LC) {
951 const StackFrameContext *STC = LC->getCurrentStackFrame();
953 const PointerType *PT = thisPointerTy->getAs<PointerType>();
955 return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
959 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
960 const LocationContext *LC) {
961 const StackFrameContext *STC = LC->getCurrentStackFrame();
963 return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
966 const MemSpaceRegion *MemRegion::getMemorySpace() const {
967 const MemRegion *R = this;
968 const SubRegion* SR = dyn_cast<SubRegion>(this);
971 R = SR->getSuperRegion();
972 SR = dyn_cast<SubRegion>(R);
975 return dyn_cast<MemSpaceRegion>(R);
978 bool MemRegion::hasStackStorage() const {
979 return isa<StackSpaceRegion>(getMemorySpace());
982 bool MemRegion::hasStackNonParametersStorage() const {
983 return isa<StackLocalsSpaceRegion>(getMemorySpace());
986 bool MemRegion::hasStackParametersStorage() const {
987 return isa<StackArgumentsSpaceRegion>(getMemorySpace());
990 bool MemRegion::hasGlobalsOrParametersStorage() const {
991 const MemSpaceRegion *MS = getMemorySpace();
992 return isa<StackArgumentsSpaceRegion>(MS) ||
993 isa<GlobalsSpaceRegion>(MS);
996 // getBaseRegion strips away all elements and fields, and get the base region
998 const MemRegion *MemRegion::getBaseRegion() const {
999 const MemRegion *R = this;
1001 switch (R->getKind()) {
1002 case MemRegion::ElementRegionKind:
1003 case MemRegion::FieldRegionKind:
1004 case MemRegion::ObjCIvarRegionKind:
1005 case MemRegion::CXXBaseObjectRegionKind:
1006 R = cast<SubRegion>(R)->getSuperRegion();
1016 bool MemRegion::isSubRegionOf(const MemRegion *R) const {
1020 //===----------------------------------------------------------------------===//
1022 //===----------------------------------------------------------------------===//
1024 const MemRegion *MemRegion::StripCasts(bool StripBaseCasts) const {
1025 const MemRegion *R = this;
1027 switch (R->getKind()) {
1028 case ElementRegionKind: {
1029 const ElementRegion *ER = cast<ElementRegion>(R);
1030 if (!ER->getIndex().isZeroConstant())
1032 R = ER->getSuperRegion();
1035 case CXXBaseObjectRegionKind:
1036 if (!StripBaseCasts)
1038 R = cast<CXXBaseObjectRegion>(R)->getSuperRegion();
1046 // FIXME: Merge with the implementation of the same method in Store.cpp
1047 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
1048 if (const RecordType *RT = Ty->getAs<RecordType>()) {
1049 const RecordDecl *D = RT->getDecl();
1050 if (!D->getDefinition())
1057 RegionRawOffset ElementRegion::getAsArrayOffset() const {
1058 CharUnits offset = CharUnits::Zero();
1059 const ElementRegion *ER = this;
1060 const MemRegion *superR = NULL;
1061 ASTContext &C = getContext();
1063 // FIXME: Handle multi-dimensional arrays.
1066 superR = ER->getSuperRegion();
1068 // FIXME: generalize to symbolic offsets.
1069 SVal index = ER->getIndex();
1070 if (Optional<nonloc::ConcreteInt> CI = index.getAs<nonloc::ConcreteInt>()) {
1071 // Update the offset.
1072 int64_t i = CI->getValue().getSExtValue();
1075 QualType elemType = ER->getElementType();
1077 // If we are pointing to an incomplete type, go no further.
1078 if (!IsCompleteType(C, elemType)) {
1083 CharUnits size = C.getTypeSizeInChars(elemType);
1084 offset += (i * size);
1087 // Go to the next ElementRegion (if any).
1088 ER = dyn_cast<ElementRegion>(superR);
1095 assert(superR && "super region cannot be NULL");
1096 return RegionRawOffset(superR, offset);
1100 /// Returns true if \p Base is an immediate base class of \p Child
1101 static bool isImmediateBase(const CXXRecordDecl *Child,
1102 const CXXRecordDecl *Base) {
1103 // Note that we do NOT canonicalize the base class here, because
1104 // ASTRecordLayout doesn't either. If that leads us down the wrong path,
1105 // so be it; at least we won't crash.
1106 for (CXXRecordDecl::base_class_const_iterator I = Child->bases_begin(),
1107 E = Child->bases_end();
1109 if (I->getType()->getAsCXXRecordDecl() == Base)
1116 RegionOffset MemRegion::getAsOffset() const {
1117 const MemRegion *R = this;
1118 const MemRegion *SymbolicOffsetBase = 0;
1122 switch (R->getKind()) {
1123 case GenericMemSpaceRegionKind:
1124 case StackLocalsSpaceRegionKind:
1125 case StackArgumentsSpaceRegionKind:
1126 case HeapSpaceRegionKind:
1127 case UnknownSpaceRegionKind:
1128 case StaticGlobalSpaceRegionKind:
1129 case GlobalInternalSpaceRegionKind:
1130 case GlobalSystemSpaceRegionKind:
1131 case GlobalImmutableSpaceRegionKind:
1132 // Stores can bind directly to a region space to set a default value.
1133 assert(Offset == 0 && !SymbolicOffsetBase);
1136 case FunctionTextRegionKind:
1137 case BlockTextRegionKind:
1138 case BlockDataRegionKind:
1139 // These will never have bindings, but may end up having values requested
1140 // if the user does some strange casting.
1142 SymbolicOffsetBase = R;
1145 case SymbolicRegionKind:
1146 case AllocaRegionKind:
1147 case CompoundLiteralRegionKind:
1148 case CXXThisRegionKind:
1149 case StringRegionKind:
1150 case ObjCStringRegionKind:
1152 case CXXTempObjectRegionKind:
1153 // Usual base regions.
1156 case ObjCIvarRegionKind:
1157 // This is a little strange, but it's a compromise between
1158 // ObjCIvarRegions having unknown compile-time offsets (when using the
1159 // non-fragile runtime) and yet still being distinct, non-overlapping
1160 // regions. Thus we treat them as "like" base regions for the purposes
1161 // of computing offsets.
1164 case CXXBaseObjectRegionKind: {
1165 const CXXBaseObjectRegion *BOR = cast<CXXBaseObjectRegion>(R);
1166 R = BOR->getSuperRegion();
1169 bool RootIsSymbolic = false;
1170 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) {
1171 Ty = TVR->getDesugaredValueType(getContext());
1172 } else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1173 // If our base region is symbolic, we don't know what type it really is.
1174 // Pretend the type of the symbol is the true dynamic type.
1175 // (This will at least be self-consistent for the life of the symbol.)
1176 Ty = SR->getSymbol()->getType()->getPointeeType();
1177 RootIsSymbolic = true;
1180 const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl();
1182 // We cannot compute the offset of the base class.
1183 SymbolicOffsetBase = R;
1186 if (RootIsSymbolic) {
1187 // Base layers on symbolic regions may not be type-correct.
1188 // Double-check the inheritance here, and revert to a symbolic offset
1189 // if it's invalid (e.g. due to a reinterpret_cast).
1190 if (BOR->isVirtual()) {
1191 if (!Child->isVirtuallyDerivedFrom(BOR->getDecl()))
1192 SymbolicOffsetBase = R;
1194 if (!isImmediateBase(Child, BOR->getDecl()))
1195 SymbolicOffsetBase = R;
1199 // Don't bother calculating precise offsets if we already have a
1200 // symbolic offset somewhere in the chain.
1201 if (SymbolicOffsetBase)
1204 CharUnits BaseOffset;
1205 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child);
1206 if (BOR->isVirtual())
1207 BaseOffset = Layout.getVBaseClassOffset(BOR->getDecl());
1209 BaseOffset = Layout.getBaseClassOffset(BOR->getDecl());
1211 // The base offset is in chars, not in bits.
1212 Offset += BaseOffset.getQuantity() * getContext().getCharWidth();
1215 case ElementRegionKind: {
1216 const ElementRegion *ER = cast<ElementRegion>(R);
1217 R = ER->getSuperRegion();
1219 QualType EleTy = ER->getValueType();
1220 if (!IsCompleteType(getContext(), EleTy)) {
1221 // We cannot compute the offset of the base class.
1222 SymbolicOffsetBase = R;
1226 SVal Index = ER->getIndex();
1227 if (Optional<nonloc::ConcreteInt> CI =
1228 Index.getAs<nonloc::ConcreteInt>()) {
1229 // Don't bother calculating precise offsets if we already have a
1230 // symbolic offset somewhere in the chain.
1231 if (SymbolicOffsetBase)
1234 int64_t i = CI->getValue().getSExtValue();
1235 // This type size is in bits.
1236 Offset += i * getContext().getTypeSize(EleTy);
1238 // We cannot compute offset for non-concrete index.
1239 SymbolicOffsetBase = R;
1243 case FieldRegionKind: {
1244 const FieldRegion *FR = cast<FieldRegion>(R);
1245 R = FR->getSuperRegion();
1247 const RecordDecl *RD = FR->getDecl()->getParent();
1248 if (RD->isUnion() || !RD->isCompleteDefinition()) {
1249 // We cannot compute offset for incomplete type.
1250 // For unions, we could treat everything as offset 0, but we'd rather
1251 // treat each field as a symbolic offset so they aren't stored on top
1252 // of each other, since we depend on things in typed regions actually
1253 // matching their types.
1254 SymbolicOffsetBase = R;
1257 // Don't bother calculating precise offsets if we already have a
1258 // symbolic offset somewhere in the chain.
1259 if (SymbolicOffsetBase)
1262 // Get the field number.
1264 for (RecordDecl::field_iterator FI = RD->field_begin(),
1265 FE = RD->field_end(); FI != FE; ++FI, ++idx)
1266 if (FR->getDecl() == *FI)
1269 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
1270 // This is offset in bits.
1271 Offset += Layout.getFieldOffset(idx);
1278 if (SymbolicOffsetBase)
1279 return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic);
1280 return RegionOffset(R, Offset);
1283 //===----------------------------------------------------------------------===//
1285 //===----------------------------------------------------------------------===//
1287 std::pair<const VarRegion *, const VarRegion *>
1288 BlockDataRegion::getCaptureRegions(const VarDecl *VD) {
1289 MemRegionManager &MemMgr = *getMemRegionManager();
1290 const VarRegion *VR = 0;
1291 const VarRegion *OriginalVR = 0;
1293 if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) {
1294 VR = MemMgr.getVarRegion(VD, this);
1295 OriginalVR = MemMgr.getVarRegion(VD, LC);
1299 VR = MemMgr.getVarRegion(VD, LC);
1303 VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
1304 OriginalVR = MemMgr.getVarRegion(VD, LC);
1307 return std::make_pair(VR, OriginalVR);
1310 void BlockDataRegion::LazyInitializeReferencedVars() {
1314 AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1315 AnalysisDeclContext::referenced_decls_iterator I, E;
1316 llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
1319 ReferencedVars = (void*) 0x1;
1323 MemRegionManager &MemMgr = *getMemRegionManager();
1324 llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1325 BumpVectorContext BC(A);
1327 typedef BumpVector<const MemRegion*> VarVec;
1328 VarVec *BV = (VarVec*) A.Allocate<VarVec>();
1329 new (BV) VarVec(BC, E - I);
1330 VarVec *BVOriginal = (VarVec*) A.Allocate<VarVec>();
1331 new (BVOriginal) VarVec(BC, E - I);
1333 for ( ; I != E; ++I) {
1334 const VarRegion *VR = 0;
1335 const VarRegion *OriginalVR = 0;
1336 llvm::tie(VR, OriginalVR) = getCaptureRegions(*I);
1339 BV->push_back(VR, BC);
1340 BVOriginal->push_back(OriginalVR, BC);
1343 ReferencedVars = BV;
1344 OriginalVars = BVOriginal;
1347 BlockDataRegion::referenced_vars_iterator
1348 BlockDataRegion::referenced_vars_begin() const {
1349 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1351 BumpVector<const MemRegion*> *Vec =
1352 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1354 if (Vec == (void*) 0x1)
1355 return BlockDataRegion::referenced_vars_iterator(0, 0);
1357 BumpVector<const MemRegion*> *VecOriginal =
1358 static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1360 return BlockDataRegion::referenced_vars_iterator(Vec->begin(),
1361 VecOriginal->begin());
1364 BlockDataRegion::referenced_vars_iterator
1365 BlockDataRegion::referenced_vars_end() const {
1366 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1368 BumpVector<const MemRegion*> *Vec =
1369 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1371 if (Vec == (void*) 0x1)
1372 return BlockDataRegion::referenced_vars_iterator(0, 0);
1374 BumpVector<const MemRegion*> *VecOriginal =
1375 static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1377 return BlockDataRegion::referenced_vars_iterator(Vec->end(),
1378 VecOriginal->end());
1381 const VarRegion *BlockDataRegion::getOriginalRegion(const VarRegion *R) const {
1382 for (referenced_vars_iterator I = referenced_vars_begin(),
1383 E = referenced_vars_end();
1385 if (I.getCapturedRegion() == R)
1386 return I.getOriginalRegion();