1 //== MemRegion.cpp - Abstract memory regions for static analysis --*- C++ -*--//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines MemRegion and its subclasses.  MemRegion defines a
11 //  partially-typed abstraction of memory useful for path-sensitive dataflow
12 //  analyses.
13 //
14 //===----------------------------------------------------------------------===//
15 
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"
25 
26 using namespace clang;
27 using namespace ento;
28 
29 //===----------------------------------------------------------------------===//
30 // MemRegion Construction.
31 //===----------------------------------------------------------------------===//
32 
33 template<typename RegionTy> struct MemRegionManagerTrait;
34 
35 template <typename RegionTy, typename A1>
36 RegionTy* MemRegionManager::getRegion(const A1 a1) {
37 
38   const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
39   MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
40 
41   llvm::FoldingSetNodeID ID;
42   RegionTy::ProfileRegion(ID, a1, superRegion);
43   void *InsertPos;
44   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
45                                                                    InsertPos));
46 
47   if (!R) {
48     R = (RegionTy*) A.Allocate<RegionTy>();
49     new (R) RegionTy(a1, superRegion);
50     Regions.InsertNode(R, InsertPos);
51   }
52 
53   return R;
54 }
55 
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);
61   void *InsertPos;
62   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
63                                                                    InsertPos));
64 
65   if (!R) {
66     R = (RegionTy*) A.Allocate<RegionTy>();
67     new (R) RegionTy(a1, superRegion);
68     Regions.InsertNode(R, InsertPos);
69   }
70 
71   return R;
72 }
73 
74 template <typename RegionTy, typename A1, typename A2>
75 RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
76 
77   const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
78   MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
79 
80   llvm::FoldingSetNodeID ID;
81   RegionTy::ProfileRegion(ID, a1, a2, superRegion);
82   void *InsertPos;
83   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
84                                                                    InsertPos));
85 
86   if (!R) {
87     R = (RegionTy*) A.Allocate<RegionTy>();
88     new (R) RegionTy(a1, a2, superRegion);
89     Regions.InsertNode(R, InsertPos);
90   }
91 
92   return R;
93 }
94 
95 template <typename RegionTy, typename A1, typename A2>
96 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
97                                          const MemRegion *superRegion) {
98 
99   llvm::FoldingSetNodeID ID;
100   RegionTy::ProfileRegion(ID, a1, a2, superRegion);
101   void *InsertPos;
102   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
103                                                                    InsertPos));
104 
105   if (!R) {
106     R = (RegionTy*) A.Allocate<RegionTy>();
107     new (R) RegionTy(a1, a2, superRegion);
108     Regions.InsertNode(R, InsertPos);
109   }
110 
111   return R;
112 }
113 
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) {
117 
118   llvm::FoldingSetNodeID ID;
119   RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
120   void *InsertPos;
121   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
122                                                                    InsertPos));
123 
124   if (!R) {
125     R = (RegionTy*) A.Allocate<RegionTy>();
126     new (R) RegionTy(a1, a2, a3, superRegion);
127     Regions.InsertNode(R, InsertPos);
128   }
129 
130   return R;
131 }
132 
133 //===----------------------------------------------------------------------===//
134 // Object destruction.
135 //===----------------------------------------------------------------------===//
136 
137 MemRegion::~MemRegion() {}
138 
139 MemRegionManager::~MemRegionManager() {
140   // All regions and their data are BumpPtrAllocated.  No need to call
141   // their destructors.
142 }
143 
144 //===----------------------------------------------------------------------===//
145 // Basic methods.
146 //===----------------------------------------------------------------------===//
147 
148 bool SubRegion::isSubRegionOf(const MemRegion* R) const {
149   const MemRegion* r = getSuperRegion();
150   while (r != 0) {
151     if (r == R)
152       return true;
153     if (const SubRegion* sr = dyn_cast<SubRegion>(r))
154       r = sr->getSuperRegion();
155     else
156       break;
157   }
158   return false;
159 }
160 
161 MemRegionManager* SubRegion::getMemRegionManager() const {
162   const SubRegion* r = this;
163   do {
164     const MemRegion *superRegion = r->getSuperRegion();
165     if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
166       r = sr;
167       continue;
168     }
169     return superRegion->getMemRegionManager();
170   } while (1);
171 }
172 
173 const StackFrameContext *VarRegion::getStackFrame() const {
174   const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
175   return SSR ? SSR->getStackFrame() : NULL;
176 }
177 
178 //===----------------------------------------------------------------------===//
179 // Region extents.
180 //===----------------------------------------------------------------------===//
181 
182 DefinedOrUnknownSVal DeclRegion::getExtent(SValBuilder &svalBuilder) const {
183   ASTContext &Ctx = svalBuilder.getContext();
184   QualType T = getDesugaredValueType(Ctx);
185 
186   if (isa<VariableArrayType>(T))
187     return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
188   if (isa<IncompleteArrayType>(T))
189     return UnknownVal();
190 
191   CharUnits size = Ctx.getTypeSizeInChars(T);
192   QualType sizeTy = svalBuilder.getArrayIndexType();
193   return svalBuilder.makeIntVal(size.getQuantity(), sizeTy);
194 }
195 
196 DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const {
197   DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder);
198 
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());
203 
204     if (isa<ConstantArrayType>(T))
205       return UnknownVal();
206   }
207 
208   return Extent;
209 }
210 
211 DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
212   return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
213 }
214 
215 DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
216   return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
217 }
218 
219 DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
220   return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
221                                 svalBuilder.getArrayIndexType());
222 }
223 
224 ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg)
225   : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
226 
227 const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
228   return cast<ObjCIvarDecl>(D);
229 }
230 
231 QualType ObjCIvarRegion::getValueType() const {
232   return getDecl()->getType();
233 }
234 
235 QualType CXXBaseObjectRegion::getValueType() const {
236   return QualType(decl->getTypeForDecl(), 0);
237 }
238 
239 //===----------------------------------------------------------------------===//
240 // FoldingSet profiling.
241 //===----------------------------------------------------------------------===//
242 
243 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
244   ID.AddInteger((unsigned)getKind());
245 }
246 
247 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
248   ID.AddInteger((unsigned)getKind());
249   ID.AddPointer(getStackFrame());
250 }
251 
252 void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
253   ID.AddInteger((unsigned)getKind());
254   ID.AddPointer(getCodeRegion());
255 }
256 
257 void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
258                                  const StringLiteral* Str,
259                                  const MemRegion* superRegion) {
260   ID.AddInteger((unsigned) StringRegionKind);
261   ID.AddPointer(Str);
262   ID.AddPointer(superRegion);
263 }
264 
265 void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
266                                      const ObjCStringLiteral* Str,
267                                      const MemRegion* superRegion) {
268   ID.AddInteger((unsigned) ObjCStringRegionKind);
269   ID.AddPointer(Str);
270   ID.AddPointer(superRegion);
271 }
272 
273 void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
274                                  const Expr *Ex, unsigned cnt,
275                                  const MemRegion *) {
276   ID.AddInteger((unsigned) AllocaRegionKind);
277   ID.AddPointer(Ex);
278   ID.AddInteger(cnt);
279 }
280 
281 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
282   ProfileRegion(ID, Ex, Cnt, superRegion);
283 }
284 
285 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
286   CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
287 }
288 
289 void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
290                                           const CompoundLiteralExpr *CL,
291                                           const MemRegion* superRegion) {
292   ID.AddInteger((unsigned) CompoundLiteralRegionKind);
293   ID.AddPointer(CL);
294   ID.AddPointer(superRegion);
295 }
296 
297 void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
298                                   const PointerType *PT,
299                                   const MemRegion *sRegion) {
300   ID.AddInteger((unsigned) CXXThisRegionKind);
301   ID.AddPointer(PT);
302   ID.AddPointer(sRegion);
303 }
304 
305 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
306   CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
307 }
308 
309 void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
310                                    const ObjCIvarDecl *ivd,
311                                    const MemRegion* superRegion) {
312   DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
313 }
314 
315 void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D,
316                                const MemRegion* superRegion, Kind k) {
317   ID.AddInteger((unsigned) k);
318   ID.AddPointer(D);
319   ID.AddPointer(superRegion);
320 }
321 
322 void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
323   DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
324 }
325 
326 void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
327   VarRegion::ProfileRegion(ID, getDecl(), superRegion);
328 }
329 
330 void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
331                                    const MemRegion *sreg) {
332   ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind);
333   ID.Add(sym);
334   ID.AddPointer(sreg);
335 }
336 
337 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
338   SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
339 }
340 
341 void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
342                                   QualType ElementType, SVal Idx,
343                                   const MemRegion* superRegion) {
344   ID.AddInteger(MemRegion::ElementRegionKind);
345   ID.Add(ElementType);
346   ID.AddPointer(superRegion);
347   Idx.Profile(ID);
348 }
349 
350 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
351   ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
352 }
353 
354 void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
355                                        const FunctionDecl *FD,
356                                        const MemRegion*) {
357   ID.AddInteger(MemRegion::FunctionTextRegionKind);
358   ID.AddPointer(FD);
359 }
360 
361 void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
362   FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
363 }
364 
365 void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
366                                     const BlockDecl *BD, CanQualType,
367                                     const AnalysisDeclContext *AC,
368                                     const MemRegion*) {
369   ID.AddInteger(MemRegion::BlockTextRegionKind);
370   ID.AddPointer(BD);
371 }
372 
373 void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
374   BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
375 }
376 
377 void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
378                                     const BlockTextRegion *BC,
379                                     const LocationContext *LC,
380                                     const MemRegion *sReg) {
381   ID.AddInteger(MemRegion::BlockDataRegionKind);
382   ID.AddPointer(BC);
383   ID.AddPointer(LC);
384   ID.AddPointer(sReg);
385 }
386 
387 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
388   BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
389 }
390 
391 void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
392                                         Expr const *Ex,
393                                         const MemRegion *sReg) {
394   ID.AddPointer(Ex);
395   ID.AddPointer(sReg);
396 }
397 
398 void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
399   ProfileRegion(ID, Ex, getSuperRegion());
400 }
401 
402 void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
403                                         const CXXRecordDecl *decl,
404                                         const MemRegion *sReg) {
405   ID.AddPointer(decl);
406   ID.AddPointer(sReg);
407 }
408 
409 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
410   ProfileRegion(ID, decl, superRegion);
411 }
412 
413 //===----------------------------------------------------------------------===//
414 // Region anchors.
415 //===----------------------------------------------------------------------===//
416 
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() { }
426 
427 //===----------------------------------------------------------------------===//
428 // Region pretty-printing.
429 //===----------------------------------------------------------------------===//
430 
431 void MemRegion::dump() const {
432   dumpToStream(llvm::errs());
433 }
434 
435 std::string MemRegion::getString() const {
436   std::string s;
437   llvm::raw_string_ostream os(s);
438   dumpToStream(os);
439   return os.str();
440 }
441 
442 void MemRegion::dumpToStream(raw_ostream &os) const {
443   os << "<Unknown Region>";
444 }
445 
446 void AllocaRegion::dumpToStream(raw_ostream &os) const {
447   os << "alloca{" << (void*) Ex << ',' << Cnt << '}';
448 }
449 
450 void FunctionTextRegion::dumpToStream(raw_ostream &os) const {
451   os << "code{" << getDecl()->getDeclName().getAsString() << '}';
452 }
453 
454 void BlockTextRegion::dumpToStream(raw_ostream &os) const {
455   os << "block_code{" << (void*) this << '}';
456 }
457 
458 void BlockDataRegion::dumpToStream(raw_ostream &os) const {
459   os << "block_data{" << BC << '}';
460 }
461 
462 void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
463   // FIXME: More elaborate pretty-printing.
464   os << "{ " << (void*) CL <<  " }";
465 }
466 
467 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
468   os << "temp_object{" << getValueType().getAsString() << ','
469      << (void*) Ex << '}';
470 }
471 
472 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
473   os << "base " << decl->getName();
474 }
475 
476 void CXXThisRegion::dumpToStream(raw_ostream &os) const {
477   os << "this";
478 }
479 
480 void ElementRegion::dumpToStream(raw_ostream &os) const {
481   os << "element{" << superRegion << ','
482      << Index << ',' << getElementType().getAsString() << '}';
483 }
484 
485 void FieldRegion::dumpToStream(raw_ostream &os) const {
486   os << superRegion << "->" << *getDecl();
487 }
488 
489 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
490   os << "ivar{" << superRegion << ',' << *getDecl() << '}';
491 }
492 
493 void StringRegion::dumpToStream(raw_ostream &os) const {
494   Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
495 }
496 
497 void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
498   Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
499 }
500 
501 void SymbolicRegion::dumpToStream(raw_ostream &os) const {
502   os << "SymRegion{" << sym << '}';
503 }
504 
505 void VarRegion::dumpToStream(raw_ostream &os) const {
506   os << *cast<VarDecl>(D);
507 }
508 
509 void RegionRawOffset::dump() const {
510   dumpToStream(llvm::errs());
511 }
512 
513 void RegionRawOffset::dumpToStream(raw_ostream &os) const {
514   os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
515 }
516 
517 void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
518   os << "StaticGlobalsMemSpace{" << CR << '}';
519 }
520 
521 void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
522   os << "GlobalInternalSpaceRegion";
523 }
524 
525 void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
526   os << "GlobalSystemSpaceRegion";
527 }
528 
529 void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
530   os << "GlobalImmutableSpaceRegion";
531 }
532 
533 void HeapSpaceRegion::dumpToStream(raw_ostream &os) const {
534   os << "HeapSpaceRegion";
535 }
536 
537 void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const {
538   os << "UnknownSpaceRegion";
539 }
540 
541 void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const {
542   os << "StackArgumentsSpaceRegion";
543 }
544 
545 void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const {
546   os << "StackLocalsSpaceRegion";
547 }
548 
549 void MemRegion::dumpPretty(raw_ostream &os) const {
550   return;
551 }
552 
553 void VarRegion::dumpPretty(raw_ostream &os) const {
554   os << getDecl()->getName();
555 }
556 
557 void FieldRegion::dumpPretty(raw_ostream &os) const {
558   superRegion->dumpPretty(os);
559   os << "->" << getDecl();
560 }
561 
562 //===----------------------------------------------------------------------===//
563 // MemRegionManager methods.
564 //===----------------------------------------------------------------------===//
565 
566 template <typename REG>
567 const REG *MemRegionManager::LazyAllocate(REG*& region) {
568   if (!region) {
569     region = (REG*) A.Allocate<REG>();
570     new (region) REG(this);
571   }
572 
573   return region;
574 }
575 
576 template <typename REG, typename ARG>
577 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
578   if (!region) {
579     region = (REG*) A.Allocate<REG>();
580     new (region) REG(this, a);
581   }
582 
583   return region;
584 }
585 
586 const StackLocalsSpaceRegion*
587 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
588   assert(STC);
589   StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
590 
591   if (R)
592     return R;
593 
594   R = A.Allocate<StackLocalsSpaceRegion>();
595   new (R) StackLocalsSpaceRegion(this, STC);
596   return R;
597 }
598 
599 const StackArgumentsSpaceRegion *
600 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
601   assert(STC);
602   StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
603 
604   if (R)
605     return R;
606 
607   R = A.Allocate<StackArgumentsSpaceRegion>();
608   new (R) StackArgumentsSpaceRegion(this, STC);
609   return R;
610 }
611 
612 const GlobalsSpaceRegion
613 *MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
614                                     const CodeTextRegion *CR) {
615   if (!CR) {
616     if (K == MemRegion::GlobalSystemSpaceRegionKind)
617       return LazyAllocate(SystemGlobals);
618     if (K == MemRegion::GlobalImmutableSpaceRegionKind)
619       return LazyAllocate(ImmutableGlobals);
620     assert(K == MemRegion::GlobalInternalSpaceRegionKind);
621     return LazyAllocate(InternalGlobals);
622   }
623 
624   assert(K == MemRegion::StaticGlobalSpaceRegionKind);
625   StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
626   if (R)
627     return R;
628 
629   R = A.Allocate<StaticGlobalSpaceRegion>();
630   new (R) StaticGlobalSpaceRegion(this, CR);
631   return R;
632 }
633 
634 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
635   return LazyAllocate(heap);
636 }
637 
638 const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
639   return LazyAllocate(unknown);
640 }
641 
642 const MemSpaceRegion *MemRegionManager::getCodeRegion() {
643   return LazyAllocate(code);
644 }
645 
646 //===----------------------------------------------------------------------===//
647 // Constructing regions.
648 //===----------------------------------------------------------------------===//
649 const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
650   return getSubRegion<StringRegion>(Str, getGlobalsRegion());
651 }
652 
653 const ObjCStringRegion *
654 MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){
655   return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion());
656 }
657 
658 /// Look through a chain of LocationContexts to either find the
659 /// StackFrameContext that matches a DeclContext, or find a VarRegion
660 /// for a variable captured by a block.
661 static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
662 getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
663                                       const DeclContext *DC,
664                                       const VarDecl *VD) {
665   while (LC) {
666     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
667       if (cast<DeclContext>(SFC->getDecl()) == DC)
668         return SFC;
669     }
670     if (const BlockInvocationContext *BC =
671         dyn_cast<BlockInvocationContext>(LC)) {
672       const BlockDataRegion *BR =
673         static_cast<const BlockDataRegion*>(BC->getContextData());
674       // FIXME: This can be made more efficient.
675       for (BlockDataRegion::referenced_vars_iterator
676            I = BR->referenced_vars_begin(),
677            E = BR->referenced_vars_end(); I != E; ++I) {
678         if (const VarRegion *VR = dyn_cast<VarRegion>(I.getOriginalRegion()))
679           if (VR->getDecl() == VD)
680             return cast<VarRegion>(I.getCapturedRegion());
681       }
682     }
683 
684     LC = LC->getParent();
685   }
686   return (const StackFrameContext*)0;
687 }
688 
689 const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
690                                                 const LocationContext *LC) {
691   const MemRegion *sReg = 0;
692 
693   if (D->hasGlobalStorage() && !D->isStaticLocal()) {
694 
695     // First handle the globals defined in system headers.
696     if (C.getSourceManager().isInSystemHeader(D->getLocation())) {
697       // Whitelist the system globals which often DO GET modified, assume the
698       // rest are immutable.
699       if (D->getName().find("errno") != StringRef::npos)
700         sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
701       else
702         sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
703 
704     // Treat other globals as GlobalInternal unless they are constants.
705     } else {
706       QualType GQT = D->getType();
707       const Type *GT = GQT.getTypePtrOrNull();
708       // TODO: We could walk the complex types here and see if everything is
709       // constified.
710       if (GT && GQT.isConstQualified() && GT->isArithmeticType())
711         sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
712       else
713         sReg = getGlobalsRegion();
714     }
715 
716   // Finally handle static locals.
717   } else {
718     // FIXME: Once we implement scope handling, we will need to properly lookup
719     // 'D' to the proper LocationContext.
720     const DeclContext *DC = D->getDeclContext();
721     llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V =
722       getStackOrCaptureRegionForDeclContext(LC, DC, D);
723 
724     if (V.is<const VarRegion*>())
725       return V.get<const VarRegion*>();
726 
727     const StackFrameContext *STC = V.get<const StackFrameContext*>();
728 
729     if (!STC)
730       sReg = getUnknownRegion();
731     else {
732       if (D->hasLocalStorage()) {
733         sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
734                ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
735                : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
736       }
737       else {
738         assert(D->isStaticLocal());
739         const Decl *D = STC->getDecl();
740         if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
741           sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
742                                   getFunctionTextRegion(FD));
743         else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
744           const BlockTextRegion *BTR =
745             getBlockTextRegion(BD,
746                      C.getCanonicalType(BD->getSignatureAsWritten()->getType()),
747                      STC->getAnalysisDeclContext());
748           sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
749                                   BTR);
750         }
751         else {
752           // FIXME: For ObjC-methods, we need a new CodeTextRegion.  For now
753           // just use the main global memspace.
754           sReg = getGlobalsRegion();
755         }
756       }
757     }
758   }
759 
760   return getSubRegion<VarRegion>(D, sReg);
761 }
762 
763 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
764                                                 const MemRegion *superR) {
765   return getSubRegion<VarRegion>(D, superR);
766 }
767 
768 const BlockDataRegion *
769 MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC,
770                                      const LocationContext *LC) {
771   const MemRegion *sReg = 0;
772   const BlockDecl *BD = BC->getDecl();
773   if (!BD->hasCaptures()) {
774     // This handles 'static' blocks.
775     sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
776   }
777   else {
778     if (LC) {
779       // FIXME: Once we implement scope handling, we want the parent region
780       // to be the scope.
781       const StackFrameContext *STC = LC->getCurrentStackFrame();
782       assert(STC);
783       sReg = getStackLocalsRegion(STC);
784     }
785     else {
786       // We allow 'LC' to be NULL for cases where want BlockDataRegions
787       // without context-sensitivity.
788       sReg = getUnknownRegion();
789     }
790   }
791 
792   return getSubRegion<BlockDataRegion>(BC, LC, sReg);
793 }
794 
795 const CompoundLiteralRegion*
796 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
797                                            const LocationContext *LC) {
798 
799   const MemRegion *sReg = 0;
800 
801   if (CL->isFileScope())
802     sReg = getGlobalsRegion();
803   else {
804     const StackFrameContext *STC = LC->getCurrentStackFrame();
805     assert(STC);
806     sReg = getStackLocalsRegion(STC);
807   }
808 
809   return getSubRegion<CompoundLiteralRegion>(CL, sReg);
810 }
811 
812 const ElementRegion*
813 MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
814                                    const MemRegion* superRegion,
815                                    ASTContext &Ctx){
816 
817   QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
818 
819   llvm::FoldingSetNodeID ID;
820   ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
821 
822   void *InsertPos;
823   MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
824   ElementRegion* R = cast_or_null<ElementRegion>(data);
825 
826   if (!R) {
827     R = (ElementRegion*) A.Allocate<ElementRegion>();
828     new (R) ElementRegion(T, Idx, superRegion);
829     Regions.InsertNode(R, InsertPos);
830   }
831 
832   return R;
833 }
834 
835 const FunctionTextRegion *
836 MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) {
837   return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
838 }
839 
840 const BlockTextRegion *
841 MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
842                                      AnalysisDeclContext *AC) {
843   return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
844 }
845 
846 
847 /// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
848 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
849   return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
850 }
851 
852 const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
853   return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
854 }
855 
856 const FieldRegion*
857 MemRegionManager::getFieldRegion(const FieldDecl *d,
858                                  const MemRegion* superRegion){
859   return getSubRegion<FieldRegion>(d, superRegion);
860 }
861 
862 const ObjCIvarRegion*
863 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
864                                     const MemRegion* superRegion) {
865   return getSubRegion<ObjCIvarRegion>(d, superRegion);
866 }
867 
868 const CXXTempObjectRegion*
869 MemRegionManager::getCXXTempObjectRegion(Expr const *E,
870                                          LocationContext const *LC) {
871   const StackFrameContext *SFC = LC->getCurrentStackFrame();
872   assert(SFC);
873   return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
874 }
875 
876 const CXXBaseObjectRegion *
877 MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *decl,
878                                          const MemRegion *superRegion) {
879   return getSubRegion<CXXBaseObjectRegion>(decl, superRegion);
880 }
881 
882 const CXXThisRegion*
883 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
884                                    const LocationContext *LC) {
885   const StackFrameContext *STC = LC->getCurrentStackFrame();
886   assert(STC);
887   const PointerType *PT = thisPointerTy->getAs<PointerType>();
888   assert(PT);
889   return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
890 }
891 
892 const AllocaRegion*
893 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
894                                   const LocationContext *LC) {
895   const StackFrameContext *STC = LC->getCurrentStackFrame();
896   assert(STC);
897   return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
898 }
899 
900 const MemSpaceRegion *MemRegion::getMemorySpace() const {
901   const MemRegion *R = this;
902   const SubRegion* SR = dyn_cast<SubRegion>(this);
903 
904   while (SR) {
905     R = SR->getSuperRegion();
906     SR = dyn_cast<SubRegion>(R);
907   }
908 
909   return dyn_cast<MemSpaceRegion>(R);
910 }
911 
912 bool MemRegion::hasStackStorage() const {
913   return isa<StackSpaceRegion>(getMemorySpace());
914 }
915 
916 bool MemRegion::hasStackNonParametersStorage() const {
917   return isa<StackLocalsSpaceRegion>(getMemorySpace());
918 }
919 
920 bool MemRegion::hasStackParametersStorage() const {
921   return isa<StackArgumentsSpaceRegion>(getMemorySpace());
922 }
923 
924 bool MemRegion::hasGlobalsOrParametersStorage() const {
925   const MemSpaceRegion *MS = getMemorySpace();
926   return isa<StackArgumentsSpaceRegion>(MS) ||
927          isa<GlobalsSpaceRegion>(MS);
928 }
929 
930 // getBaseRegion strips away all elements and fields, and get the base region
931 // of them.
932 const MemRegion *MemRegion::getBaseRegion() const {
933   const MemRegion *R = this;
934   while (true) {
935     switch (R->getKind()) {
936       case MemRegion::ElementRegionKind:
937       case MemRegion::FieldRegionKind:
938       case MemRegion::ObjCIvarRegionKind:
939       case MemRegion::CXXBaseObjectRegionKind:
940         R = cast<SubRegion>(R)->getSuperRegion();
941         continue;
942       default:
943         break;
944     }
945     break;
946   }
947   return R;
948 }
949 
950 //===----------------------------------------------------------------------===//
951 // View handling.
952 //===----------------------------------------------------------------------===//
953 
954 const MemRegion *MemRegion::StripCasts() const {
955   const MemRegion *R = this;
956   while (true) {
957     switch (R->getKind()) {
958     case ElementRegionKind: {
959       const ElementRegion *ER = cast<ElementRegion>(R);
960       if (!ER->getIndex().isZeroConstant())
961         return R;
962       R = ER->getSuperRegion();
963       break;
964     }
965     case CXXBaseObjectRegionKind:
966       R = cast<CXXBaseObjectRegion>(R)->getSuperRegion();
967       break;
968     default:
969       return R;
970     }
971   }
972 }
973 
974 // FIXME: Merge with the implementation of the same method in Store.cpp
975 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
976   if (const RecordType *RT = Ty->getAs<RecordType>()) {
977     const RecordDecl *D = RT->getDecl();
978     if (!D->getDefinition())
979       return false;
980   }
981 
982   return true;
983 }
984 
985 RegionRawOffset ElementRegion::getAsArrayOffset() const {
986   CharUnits offset = CharUnits::Zero();
987   const ElementRegion *ER = this;
988   const MemRegion *superR = NULL;
989   ASTContext &C = getContext();
990 
991   // FIXME: Handle multi-dimensional arrays.
992 
993   while (ER) {
994     superR = ER->getSuperRegion();
995 
996     // FIXME: generalize to symbolic offsets.
997     SVal index = ER->getIndex();
998     if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
999       // Update the offset.
1000       int64_t i = CI->getValue().getSExtValue();
1001 
1002       if (i != 0) {
1003         QualType elemType = ER->getElementType();
1004 
1005         // If we are pointing to an incomplete type, go no further.
1006         if (!IsCompleteType(C, elemType)) {
1007           superR = ER;
1008           break;
1009         }
1010 
1011         CharUnits size = C.getTypeSizeInChars(elemType);
1012         offset += (i * size);
1013       }
1014 
1015       // Go to the next ElementRegion (if any).
1016       ER = dyn_cast<ElementRegion>(superR);
1017       continue;
1018     }
1019 
1020     return NULL;
1021   }
1022 
1023   assert(superR && "super region cannot be NULL");
1024   return RegionRawOffset(superR, offset);
1025 }
1026 
1027 RegionOffset MemRegion::getAsOffset() const {
1028   const MemRegion *R = this;
1029   int64_t Offset = 0;
1030 
1031   while (1) {
1032     switch (R->getKind()) {
1033     default:
1034       return RegionOffset(0);
1035     case SymbolicRegionKind:
1036     case AllocaRegionKind:
1037     case CompoundLiteralRegionKind:
1038     case CXXThisRegionKind:
1039     case StringRegionKind:
1040     case VarRegionKind:
1041     case CXXTempObjectRegionKind:
1042       goto Finish;
1043     case ElementRegionKind: {
1044       const ElementRegion *ER = cast<ElementRegion>(R);
1045       QualType EleTy = ER->getValueType();
1046 
1047       if (!IsCompleteType(getContext(), EleTy))
1048         return RegionOffset(0);
1049 
1050       SVal Index = ER->getIndex();
1051       if (const nonloc::ConcreteInt *CI=dyn_cast<nonloc::ConcreteInt>(&Index)) {
1052         int64_t i = CI->getValue().getSExtValue();
1053         CharUnits Size = getContext().getTypeSizeInChars(EleTy);
1054         Offset += i * Size.getQuantity() * 8;
1055       } else {
1056         // We cannot compute offset for non-concrete index.
1057         return RegionOffset(0);
1058       }
1059       R = ER->getSuperRegion();
1060       break;
1061     }
1062     case FieldRegionKind: {
1063       const FieldRegion *FR = cast<FieldRegion>(R);
1064       const RecordDecl *RD = FR->getDecl()->getParent();
1065       if (!RD->isCompleteDefinition())
1066         // We cannot compute offset for incomplete type.
1067         return RegionOffset(0);
1068       // Get the field number.
1069       unsigned idx = 0;
1070       for (RecordDecl::field_iterator FI = RD->field_begin(),
1071              FE = RD->field_end(); FI != FE; ++FI, ++idx)
1072         if (FR->getDecl() == *FI)
1073           break;
1074 
1075       const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
1076       // This is offset in bits.
1077       Offset += Layout.getFieldOffset(idx);
1078       R = FR->getSuperRegion();
1079       break;
1080     }
1081     }
1082   }
1083 
1084  Finish:
1085   return RegionOffset(R, Offset);
1086 }
1087 
1088 //===----------------------------------------------------------------------===//
1089 // BlockDataRegion
1090 //===----------------------------------------------------------------------===//
1091 
1092 void BlockDataRegion::LazyInitializeReferencedVars() {
1093   if (ReferencedVars)
1094     return;
1095 
1096   AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1097   AnalysisDeclContext::referenced_decls_iterator I, E;
1098   llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
1099 
1100   if (I == E) {
1101     ReferencedVars = (void*) 0x1;
1102     return;
1103   }
1104 
1105   MemRegionManager &MemMgr = *getMemRegionManager();
1106   llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1107   BumpVectorContext BC(A);
1108 
1109   typedef BumpVector<const MemRegion*> VarVec;
1110   VarVec *BV = (VarVec*) A.Allocate<VarVec>();
1111   new (BV) VarVec(BC, E - I);
1112   VarVec *BVOriginal = (VarVec*) A.Allocate<VarVec>();
1113   new (BVOriginal) VarVec(BC, E - I);
1114 
1115   for ( ; I != E; ++I) {
1116     const VarDecl *VD = *I;
1117     const VarRegion *VR = 0;
1118     const VarRegion *OriginalVR = 0;
1119 
1120     if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) {
1121       VR = MemMgr.getVarRegion(VD, this);
1122       OriginalVR = MemMgr.getVarRegion(VD, LC);
1123     }
1124     else {
1125       if (LC) {
1126         VR = MemMgr.getVarRegion(VD, LC);
1127         OriginalVR = VR;
1128       }
1129       else {
1130         VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
1131         OriginalVR = MemMgr.getVarRegion(VD, LC);
1132       }
1133     }
1134 
1135     assert(VR);
1136     assert(OriginalVR);
1137     BV->push_back(VR, BC);
1138     BVOriginal->push_back(OriginalVR, BC);
1139   }
1140 
1141   ReferencedVars = BV;
1142   OriginalVars = BVOriginal;
1143 }
1144 
1145 BlockDataRegion::referenced_vars_iterator
1146 BlockDataRegion::referenced_vars_begin() const {
1147   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1148 
1149   BumpVector<const MemRegion*> *Vec =
1150     static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1151 
1152   if (Vec == (void*) 0x1)
1153     return BlockDataRegion::referenced_vars_iterator(0, 0);
1154 
1155   BumpVector<const MemRegion*> *VecOriginal =
1156     static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1157 
1158   return BlockDataRegion::referenced_vars_iterator(Vec->begin(),
1159                                                    VecOriginal->begin());
1160 }
1161 
1162 BlockDataRegion::referenced_vars_iterator
1163 BlockDataRegion::referenced_vars_end() const {
1164   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1165 
1166   BumpVector<const MemRegion*> *Vec =
1167     static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1168 
1169   if (Vec == (void*) 0x1)
1170     return BlockDataRegion::referenced_vars_iterator(0, 0);
1171 
1172   BumpVector<const MemRegion*> *VecOriginal =
1173     static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1174 
1175   return BlockDataRegion::referenced_vars_iterator(Vec->end(),
1176                                                    VecOriginal->end());
1177 }
1178