MemRegion.cpp revision 31ba6135375433b617a8587ea6cc836a014ebd86 
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
26using namespace clang;
27using namespace ento;
28
29//===----------------------------------------------------------------------===//
30// MemRegion Construction.
31//===----------------------------------------------------------------------===//
32
33template<typename RegionTy> struct MemRegionManagerTrait;
34
35template <typename RegionTy, typename A1>
36RegionTy* 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
56template <typename RegionTy, typename A1>
57RegionTy* 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
74template <typename RegionTy, typename A1, typename A2>
75RegionTy* 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
95template <typename RegionTy, typename A1, typename A2>
96RegionTy* 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
114template <typename RegionTy, typename A1, typename A2, typename A3>
115RegionTy* 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
137MemRegion::~MemRegion() {}
138
139MemRegionManager::~MemRegionManager() {
140  // All regions and their data are BumpPtrAllocated.  No need to call
141  // their destructors.
142}
143
144//===----------------------------------------------------------------------===//
145// Basic methods.
146//===----------------------------------------------------------------------===//
147
148bool 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
161MemRegionManager* 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
173const 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
182DefinedOrUnknownSVal TypedValueRegion::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
196DefinedOrUnknownSVal 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
211DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
212  return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
213}
214
215DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
216  return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
217}
218
219DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
220  return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
221                                svalBuilder.getArrayIndexType());
222}
223
224ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg)
225  : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
226
227const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
228  return cast<ObjCIvarDecl>(D);
229}
230
231QualType ObjCIvarRegion::getValueType() const {
232  return getDecl()->getType();
233}
234
235QualType CXXBaseObjectRegion::getValueType() const {
236  return QualType(decl->getTypeForDecl(), 0);
237}
238
239//===----------------------------------------------------------------------===//
240// FoldingSet profiling.
241//===----------------------------------------------------------------------===//
242
243void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
244  ID.AddInteger((unsigned)getKind());
245}
246
247void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
248  ID.AddInteger((unsigned)getKind());
249  ID.AddPointer(getStackFrame());
250}
251
252void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
253  ID.AddInteger((unsigned)getKind());
254  ID.AddPointer(getCodeRegion());
255}
256
257void 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
265void 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
273void 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
281void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
282  ProfileRegion(ID, Ex, Cnt, superRegion);
283}
284
285void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
286  CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
287}
288
289void 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
297void 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
305void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
306  CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
307}
308
309void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
310                                   const ObjCIvarDecl *ivd,
311                                   const MemRegion* superRegion) {
312  DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
313}
314
315void 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
322void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
323  DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
324}
325
326void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
327  VarRegion::ProfileRegion(ID, getDecl(), superRegion);
328}
329
330void 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
337void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
338  SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
339}
340
341void 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
350void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
351  ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
352}
353
354void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
355                                       const FunctionDecl *FD,
356                                       const MemRegion*) {
357  ID.AddInteger(MemRegion::FunctionTextRegionKind);
358  ID.AddPointer(FD);
359}
360
361void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
362  FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
363}
364
365void 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
373void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
374  BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
375}
376
377void 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
387void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
388  BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
389}
390
391void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
392                                        Expr const *Ex,
393                                        const MemRegion *sReg) {
394  ID.AddPointer(Ex);
395  ID.AddPointer(sReg);
396}
397
398void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
399  ProfileRegion(ID, Ex, getSuperRegion());
400}
401
402void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
403                                        const CXXRecordDecl *decl,
404                                        const MemRegion *sReg) {
405  ID.AddPointer(decl);
406  ID.AddPointer(sReg);
407}
408
409void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
410  ProfileRegion(ID, decl, superRegion);
411}
412
413//===----------------------------------------------------------------------===//
414// Region anchors.
415//===----------------------------------------------------------------------===//
416
417void GlobalsSpaceRegion::anchor() { }
418void HeapSpaceRegion::anchor() { }
419void UnknownSpaceRegion::anchor() { }
420void StackLocalsSpaceRegion::anchor() { }
421void StackArgumentsSpaceRegion::anchor() { }
422void TypedRegion::anchor() { }
423void TypedValueRegion::anchor() { }
424void CodeTextRegion::anchor() { }
425void SubRegion::anchor() { }
426
427//===----------------------------------------------------------------------===//
428// Region pretty-printing.
429//===----------------------------------------------------------------------===//
430
431void MemRegion::dump() const {
432  dumpToStream(llvm::errs());
433}
434
435std::string MemRegion::getString() const {
436  std::string s;
437  llvm::raw_string_ostream os(s);
438  dumpToStream(os);
439  return os.str();
440}
441
442void MemRegion::dumpToStream(raw_ostream &os) const {
443  os << "<Unknown Region>";
444}
445
446void AllocaRegion::dumpToStream(raw_ostream &os) const {
447  os << "alloca{" << (const void*) Ex << ',' << Cnt << '}';
448}
449
450void FunctionTextRegion::dumpToStream(raw_ostream &os) const {
451  os << "code{" << getDecl()->getDeclName().getAsString() << '}';
452}
453
454void BlockTextRegion::dumpToStream(raw_ostream &os) const {
455  os << "block_code{" << (const void*) this << '}';
456}
457
458void BlockDataRegion::dumpToStream(raw_ostream &os) const {
459  os << "block_data{" << BC << '}';
460}
461
462void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
463  // FIXME: More elaborate pretty-printing.
464  os << "{ " << (const void*) CL <<  " }";
465}
466
467void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
468  os << "temp_object{" << getValueType().getAsString() << ','
469     << (const void*) Ex << '}';
470}
471
472void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
473  os << "base{" << superRegion << ',' << decl->getName() << '}';
474}
475
476void CXXThisRegion::dumpToStream(raw_ostream &os) const {
477  os << "this";
478}
479
480void ElementRegion::dumpToStream(raw_ostream &os) const {
481  os << "element{" << superRegion << ','
482     << Index << ',' << getElementType().getAsString() << '}';
483}
484
485void FieldRegion::dumpToStream(raw_ostream &os) const {
486  os << superRegion << "->" << *getDecl();
487}
488
489void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
490  os << "ivar{" << superRegion << ',' << *getDecl() << '}';
491}
492
493void StringRegion::dumpToStream(raw_ostream &os) const {
494  Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
495}
496
497void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
498  Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
499}
500
501void SymbolicRegion::dumpToStream(raw_ostream &os) const {
502  os << "SymRegion{" << sym << '}';
503}
504
505void VarRegion::dumpToStream(raw_ostream &os) const {
506  os << *cast<VarDecl>(D);
507}
508
509void RegionRawOffset::dump() const {
510  dumpToStream(llvm::errs());
511}
512
513void RegionRawOffset::dumpToStream(raw_ostream &os) const {
514  os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
515}
516
517void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
518  os << "StaticGlobalsMemSpace{" << CR << '}';
519}
520
521void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
522  os << "GlobalInternalSpaceRegion";
523}
524
525void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
526  os << "GlobalSystemSpaceRegion";
527}
528
529void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
530  os << "GlobalImmutableSpaceRegion";
531}
532
533void HeapSpaceRegion::dumpToStream(raw_ostream &os) const {
534  os << "HeapSpaceRegion";
535}
536
537void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const {
538  os << "UnknownSpaceRegion";
539}
540
541void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const {
542  os << "StackArgumentsSpaceRegion";
543}
544
545void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const {
546  os << "StackLocalsSpaceRegion";
547}
548
549bool MemRegion::canPrintPretty() const {
550  return false;
551}
552
553void MemRegion::printPretty(raw_ostream &os) const {
554  return;
555}
556
557bool VarRegion::canPrintPretty() const {
558  return true;
559}
560
561void VarRegion::printPretty(raw_ostream &os) const {
562  os << getDecl()->getName();
563}
564
565bool FieldRegion::canPrintPretty() const {
566  return superRegion->canPrintPretty();
567}
568
569void FieldRegion::printPretty(raw_ostream &os) const {
570  superRegion->printPretty(os);
571  os << "." << getDecl()->getName();
572}
573
574//===----------------------------------------------------------------------===//
575// MemRegionManager methods.
576//===----------------------------------------------------------------------===//
577
578template <typename REG>
579const REG *MemRegionManager::LazyAllocate(REG*& region) {
580  if (!region) {
581    region = (REG*) A.Allocate<REG>();
582    new (region) REG(this);
583  }
584
585  return region;
586}
587
588template <typename REG, typename ARG>
589const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
590  if (!region) {
591    region = (REG*) A.Allocate<REG>();
592    new (region) REG(this, a);
593  }
594
595  return region;
596}
597
598const StackLocalsSpaceRegion*
599MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
600  assert(STC);
601  StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
602
603  if (R)
604    return R;
605
606  R = A.Allocate<StackLocalsSpaceRegion>();
607  new (R) StackLocalsSpaceRegion(this, STC);
608  return R;
609}
610
611const StackArgumentsSpaceRegion *
612MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
613  assert(STC);
614  StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
615
616  if (R)
617    return R;
618
619  R = A.Allocate<StackArgumentsSpaceRegion>();
620  new (R) StackArgumentsSpaceRegion(this, STC);
621  return R;
622}
623
624const GlobalsSpaceRegion
625*MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
626                                    const CodeTextRegion *CR) {
627  if (!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);
634  }
635
636  assert(K == MemRegion::StaticGlobalSpaceRegionKind);
637  StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
638  if (R)
639    return R;
640
641  R = A.Allocate<StaticGlobalSpaceRegion>();
642  new (R) StaticGlobalSpaceRegion(this, CR);
643  return R;
644}
645
646const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
647  return LazyAllocate(heap);
648}
649
650const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
651  return LazyAllocate(unknown);
652}
653
654const MemSpaceRegion *MemRegionManager::getCodeRegion() {
655  return LazyAllocate(code);
656}
657
658//===----------------------------------------------------------------------===//
659// Constructing regions.
660//===----------------------------------------------------------------------===//
661const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
662  return getSubRegion<StringRegion>(Str, getGlobalsRegion());
663}
664
665const ObjCStringRegion *
666MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){
667  return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion());
668}
669
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.
673static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
674getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
675                                      const DeclContext *DC,
676                                      const VarDecl *VD) {
677  while (LC) {
678    if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
679      if (cast<DeclContext>(SFC->getDecl()) == DC)
680        return SFC;
681    }
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());
693      }
694    }
695
696    LC = LC->getParent();
697  }
698  return (const StackFrameContext*)0;
699}
700
701const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
702                                                const LocationContext *LC) {
703  const MemRegion *sReg = 0;
704
705  if (D->hasGlobalStorage() && !D->isStaticLocal()) {
706
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);
713      else
714        sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
715
716    // Treat other globals as GlobalInternal unless they are constants.
717    } else {
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
721      // constified.
722      if (GT && GQT.isConstQualified() && GT->isArithmeticType())
723        sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
724      else
725        sReg = getGlobalsRegion();
726    }
727
728  // Finally handle static locals.
729  } else {
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);
735
736    if (V.is<const VarRegion*>())
737      return V.get<const VarRegion*>();
738
739    const StackFrameContext *STC = V.get<const StackFrameContext*>();
740
741    if (!STC)
742      sReg = getUnknownRegion();
743    else {
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));
748      }
749      else {
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,
761                                  BTR);
762        }
763        else {
764          // FIXME: For ObjC-methods, we need a new CodeTextRegion.  For now
765          // just use the main global memspace.
766          sReg = getGlobalsRegion();
767        }
768      }
769    }
770  }
771
772  return getSubRegion<VarRegion>(D, sReg);
773}
774
775const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
776                                                const MemRegion *superR) {
777  return getSubRegion<VarRegion>(D, superR);
778}
779
780const BlockDataRegion *
781MemRegionManager::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);
788  }
789  else {
790    if (LC) {
791      // FIXME: Once we implement scope handling, we want the parent region
792      // to be the scope.
793      const StackFrameContext *STC = LC->getCurrentStackFrame();
794      assert(STC);
795      sReg = getStackLocalsRegion(STC);
796    }
797    else {
798      // We allow 'LC' to be NULL for cases where want BlockDataRegions
799      // without context-sensitivity.
800      sReg = getUnknownRegion();
801    }
802  }
803
804  return getSubRegion<BlockDataRegion>(BC, LC, sReg);
805}
806
807const CompoundLiteralRegion*
808MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
809                                           const LocationContext *LC) {
810
811  const MemRegion *sReg = 0;
812
813  if (CL->isFileScope())
814    sReg = getGlobalsRegion();
815  else {
816    const StackFrameContext *STC = LC->getCurrentStackFrame();
817    assert(STC);
818    sReg = getStackLocalsRegion(STC);
819  }
820
821  return getSubRegion<CompoundLiteralRegion>(CL, sReg);
822}
823
824const ElementRegion*
825MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
826                                   const MemRegion* superRegion,
827                                   ASTContext &Ctx){
828
829  QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
830
831  llvm::FoldingSetNodeID ID;
832  ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
833
834  void *InsertPos;
835  MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
836  ElementRegion* R = cast_or_null<ElementRegion>(data);
837
838  if (!R) {
839    R = (ElementRegion*) A.Allocate<ElementRegion>();
840    new (R) ElementRegion(T, Idx, superRegion);
841    Regions.InsertNode(R, InsertPos);
842  }
843
844  return R;
845}
846
847const FunctionTextRegion *
848MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) {
849  return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
850}
851
852const BlockTextRegion *
853MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
854                                     AnalysisDeclContext *AC) {
855  return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
856}
857
858
859/// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
860const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
861  return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
862}
863
864const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
865  return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
866}
867
868const FieldRegion*
869MemRegionManager::getFieldRegion(const FieldDecl *d,
870                                 const MemRegion* superRegion){
871  return getSubRegion<FieldRegion>(d, superRegion);
872}
873
874const ObjCIvarRegion*
875MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
876                                    const MemRegion* superRegion) {
877  return getSubRegion<ObjCIvarRegion>(d, superRegion);
878}
879
880const CXXTempObjectRegion*
881MemRegionManager::getCXXTempObjectRegion(Expr const *E,
882                                         LocationContext const *LC) {
883  const StackFrameContext *SFC = LC->getCurrentStackFrame();
884  assert(SFC);
885  return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
886}
887
888const CXXBaseObjectRegion *
889MemRegionManager::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
896        // are different.
897        while (const CXXBaseObjectRegion *Base =
898                 dyn_cast<CXXBaseObjectRegion>(superRegion)) {
899          superRegion = Base->getSuperRegion();
900        }
901        assert(superRegion && !isa<MemSpaceRegion>(superRegion));
902
903      } else {
904        // Non-virtual bases should always be direct bases.
905#ifndef NDEBUG
906        bool FoundBase = false;
907        for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(),
908                                                      E = Class->bases_end();
909             I != E; ++I) {
910          if (I->getType()->getAsCXXRecordDecl() == decl) {
911            FoundBase = true;
912            break;
913          }
914        }
915
916        assert(FoundBase && "Not a direct base class of this region");
917#endif
918      }
919    }
920  }
921
922  return getSubRegion<CXXBaseObjectRegion>(decl, superRegion);
923}
924
925const CXXThisRegion*
926MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
927                                   const LocationContext *LC) {
928  const StackFrameContext *STC = LC->getCurrentStackFrame();
929  assert(STC);
930  const PointerType *PT = thisPointerTy->getAs<PointerType>();
931  assert(PT);
932  return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
933}
934
935const AllocaRegion*
936MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
937                                  const LocationContext *LC) {
938  const StackFrameContext *STC = LC->getCurrentStackFrame();
939  assert(STC);
940  return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
941}
942
943const MemSpaceRegion *MemRegion::getMemorySpace() const {
944  const MemRegion *R = this;
945  const SubRegion* SR = dyn_cast<SubRegion>(this);
946
947  while (SR) {
948    R = SR->getSuperRegion();
949    SR = dyn_cast<SubRegion>(R);
950  }
951
952  return dyn_cast<MemSpaceRegion>(R);
953}
954
955bool MemRegion::hasStackStorage() const {
956  return isa<StackSpaceRegion>(getMemorySpace());
957}
958
959bool MemRegion::hasStackNonParametersStorage() const {
960  return isa<StackLocalsSpaceRegion>(getMemorySpace());
961}
962
963bool MemRegion::hasStackParametersStorage() const {
964  return isa<StackArgumentsSpaceRegion>(getMemorySpace());
965}
966
967bool MemRegion::hasGlobalsOrParametersStorage() const {
968  const MemSpaceRegion *MS = getMemorySpace();
969  return isa<StackArgumentsSpaceRegion>(MS) ||
970         isa<GlobalsSpaceRegion>(MS);
971}
972
973// getBaseRegion strips away all elements and fields, and get the base region
974// of them.
975const MemRegion *MemRegion::getBaseRegion() const {
976  const MemRegion *R = this;
977  while (true) {
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();
984        continue;
985      default:
986        break;
987    }
988    break;
989  }
990  return R;
991}
992
993//===----------------------------------------------------------------------===//
994// View handling.
995//===----------------------------------------------------------------------===//
996
997const MemRegion *MemRegion::StripCasts(bool StripBaseCasts) const {
998  const MemRegion *R = this;
999  while (true) {
1000    switch (R->getKind()) {
1001    case ElementRegionKind: {
1002      const ElementRegion *ER = cast<ElementRegion>(R);
1003      if (!ER->getIndex().isZeroConstant())
1004        return R;
1005      R = ER->getSuperRegion();
1006      break;
1007    }
1008    case CXXBaseObjectRegionKind:
1009      if (!StripBaseCasts)
1010        return R;
1011      R = cast<CXXBaseObjectRegion>(R)->getSuperRegion();
1012      break;
1013    default:
1014      return R;
1015    }
1016  }
1017}
1018
1019// FIXME: Merge with the implementation of the same method in Store.cpp
1020static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
1021  if (const RecordType *RT = Ty->getAs<RecordType>()) {
1022    const RecordDecl *D = RT->getDecl();
1023    if (!D->getDefinition())
1024      return false;
1025  }
1026
1027  return true;
1028}
1029
1030RegionRawOffset ElementRegion::getAsArrayOffset() const {
1031  CharUnits offset = CharUnits::Zero();
1032  const ElementRegion *ER = this;
1033  const MemRegion *superR = NULL;
1034  ASTContext &C = getContext();
1035
1036  // FIXME: Handle multi-dimensional arrays.
1037
1038  while (ER) {
1039    superR = ER->getSuperRegion();
1040
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();
1046
1047      if (i != 0) {
1048        QualType elemType = ER->getElementType();
1049
1050        // If we are pointing to an incomplete type, go no further.
1051        if (!IsCompleteType(C, elemType)) {
1052          superR = ER;
1053          break;
1054        }
1055
1056        CharUnits size = C.getTypeSizeInChars(elemType);
1057        offset += (i * size);
1058      }
1059
1060      // Go to the next ElementRegion (if any).
1061      ER = dyn_cast<ElementRegion>(superR);
1062      continue;
1063    }
1064
1065    return NULL;
1066  }
1067
1068  assert(superR && "super region cannot be NULL");
1069  return RegionRawOffset(superR, offset);
1070}
1071
1072RegionOffset MemRegion::getAsOffset() const {
1073  const MemRegion *R = this;
1074  const MemRegion *SymbolicOffsetBase = 0;
1075  int64_t Offset = 0;
1076
1077  while (1) {
1078    switch (R->getKind()) {
1079    default:
1080      return RegionOffset(R, RegionOffset::Symbolic);
1081
1082    case SymbolicRegionKind:
1083    case AllocaRegionKind:
1084    case CompoundLiteralRegionKind:
1085    case CXXThisRegionKind:
1086    case StringRegionKind:
1087    case VarRegionKind:
1088    case CXXTempObjectRegionKind:
1089      goto Finish;
1090
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.
1097      goto Finish;
1098
1099    case CXXBaseObjectRegionKind: {
1100      const CXXBaseObjectRegion *BOR = cast<CXXBaseObjectRegion>(R);
1101      R = BOR->getSuperRegion();
1102
1103      QualType Ty;
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();
1111      }
1112
1113      const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl();
1114      if (!Child) {
1115        // We cannot compute the offset of the base class.
1116        SymbolicOffsetBase = R;
1117      }
1118
1119      // Don't bother calculating precise offsets if we already have a
1120      // symbolic offset somewhere in the chain.
1121      if (SymbolicOffsetBase)
1122        continue;
1123
1124      const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child);
1125
1126      CharUnits BaseOffset;
1127      const CXXRecordDecl *Base = BOR->getDecl();
1128      if (Child->isVirtuallyDerivedFrom(Base))
1129        BaseOffset = Layout.getVBaseClassOffset(Base);
1130      else
1131        BaseOffset = Layout.getBaseClassOffset(Base);
1132
1133      // The base offset is in chars, not in bits.
1134      Offset += BaseOffset.getQuantity() * getContext().getCharWidth();
1135      break;
1136    }
1137    case ElementRegionKind: {
1138      const ElementRegion *ER = cast<ElementRegion>(R);
1139      R = ER->getSuperRegion();
1140
1141      QualType EleTy = ER->getValueType();
1142      if (!IsCompleteType(getContext(), EleTy)) {
1143        // We cannot compute the offset of the base class.
1144        SymbolicOffsetBase = R;
1145        continue;
1146      }
1147
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)
1153          continue;
1154
1155        int64_t i = CI->getValue().getSExtValue();
1156        // This type size is in bits.
1157        Offset += i * getContext().getTypeSize(EleTy);
1158      } else {
1159        // We cannot compute offset for non-concrete index.
1160        SymbolicOffsetBase = R;
1161      }
1162      break;
1163    }
1164    case FieldRegionKind: {
1165      const FieldRegion *FR = cast<FieldRegion>(R);
1166      R = FR->getSuperRegion();
1167
1168      const RecordDecl *RD = FR->getDecl()->getParent();
1169      if (!RD->isCompleteDefinition()) {
1170        // We cannot compute offset for incomplete type.
1171        SymbolicOffsetBase = R;
1172      }
1173
1174      // Don't bother calculating precise offsets if we already have a
1175      // symbolic offset somewhere in the chain.
1176      if (SymbolicOffsetBase)
1177        continue;
1178
1179      // Get the field number.
1180      unsigned idx = 0;
1181      for (RecordDecl::field_iterator FI = RD->field_begin(),
1182             FE = RD->field_end(); FI != FE; ++FI, ++idx)
1183        if (FR->getDecl() == *FI)
1184          break;
1185
1186      const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
1187      // This is offset in bits.
1188      Offset += Layout.getFieldOffset(idx);
1189      break;
1190    }
1191    }
1192  }
1193
1194 Finish:
1195  if (SymbolicOffsetBase)
1196    return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic);
1197  return RegionOffset(R, Offset);
1198}
1199
1200//===----------------------------------------------------------------------===//
1201// BlockDataRegion
1202//===----------------------------------------------------------------------===//
1203
1204void BlockDataRegion::LazyInitializeReferencedVars() {
1205  if (ReferencedVars)
1206    return;
1207
1208  AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1209  AnalysisDeclContext::referenced_decls_iterator I, E;
1210  llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
1211
1212  if (I == E) {
1213    ReferencedVars = (void*) 0x1;
1214    return;
1215  }
1216
1217  MemRegionManager &MemMgr = *getMemRegionManager();
1218  llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1219  BumpVectorContext BC(A);
1220
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);
1226
1227  for ( ; I != E; ++I) {
1228    const VarDecl *VD = *I;
1229    const VarRegion *VR = 0;
1230    const VarRegion *OriginalVR = 0;
1231
1232    if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) {
1233      VR = MemMgr.getVarRegion(VD, this);
1234      OriginalVR = MemMgr.getVarRegion(VD, LC);
1235    }
1236    else {
1237      if (LC) {
1238        VR = MemMgr.getVarRegion(VD, LC);
1239        OriginalVR = VR;
1240      }
1241      else {
1242        VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
1243        OriginalVR = MemMgr.getVarRegion(VD, LC);
1244      }
1245    }
1246
1247    assert(VR);
1248    assert(OriginalVR);
1249    BV->push_back(VR, BC);
1250    BVOriginal->push_back(OriginalVR, BC);
1251  }
1252
1253  ReferencedVars = BV;
1254  OriginalVars = BVOriginal;
1255}
1256
1257BlockDataRegion::referenced_vars_iterator
1258BlockDataRegion::referenced_vars_begin() const {
1259  const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1260
1261  BumpVector<const MemRegion*> *Vec =
1262    static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1263
1264  if (Vec == (void*) 0x1)
1265    return BlockDataRegion::referenced_vars_iterator(0, 0);
1266
1267  BumpVector<const MemRegion*> *VecOriginal =
1268    static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1269
1270  return BlockDataRegion::referenced_vars_iterator(Vec->begin(),
1271                                                   VecOriginal->begin());
1272}
1273
1274BlockDataRegion::referenced_vars_iterator
1275BlockDataRegion::referenced_vars_end() const {
1276  const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1277
1278  BumpVector<const MemRegion*> *Vec =
1279    static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1280
1281  if (Vec == (void*) 0x1)
1282    return BlockDataRegion::referenced_vars_iterator(0, 0);
1283
1284  BumpVector<const MemRegion*> *VecOriginal =
1285    static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1286
1287  return BlockDataRegion::referenced_vars_iterator(Vec->end(),
1288                                                   VecOriginal->end());
1289}
1290