MemRegion.cpp revision 99ba9e3bd70671f3441fb974895f226a83ce0e66 
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/RecordLayout.h"
22#include "llvm/Support/raw_ostream.h"
23
24using namespace clang;
25using namespace ento;
26
27//===----------------------------------------------------------------------===//
28// MemRegion Construction.
29//===----------------------------------------------------------------------===//
30
31template<typename RegionTy> struct MemRegionManagerTrait;
32
33template <typename RegionTy, typename A1>
34RegionTy* MemRegionManager::getRegion(const A1 a1) {
35
36  const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
37  MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
38
39  llvm::FoldingSetNodeID ID;
40  RegionTy::ProfileRegion(ID, a1, superRegion);
41  void *InsertPos;
42  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
43                                                                   InsertPos));
44
45  if (!R) {
46    R = (RegionTy*) A.Allocate<RegionTy>();
47    new (R) RegionTy(a1, superRegion);
48    Regions.InsertNode(R, InsertPos);
49  }
50
51  return R;
52}
53
54template <typename RegionTy, typename A1>
55RegionTy* MemRegionManager::getSubRegion(const A1 a1,
56                                         const MemRegion *superRegion) {
57  llvm::FoldingSetNodeID ID;
58  RegionTy::ProfileRegion(ID, a1, superRegion);
59  void *InsertPos;
60  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
61                                                                   InsertPos));
62
63  if (!R) {
64    R = (RegionTy*) A.Allocate<RegionTy>();
65    new (R) RegionTy(a1, superRegion);
66    Regions.InsertNode(R, InsertPos);
67  }
68
69  return R;
70}
71
72template <typename RegionTy, typename A1, typename A2>
73RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
74
75  const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
76  MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
77
78  llvm::FoldingSetNodeID ID;
79  RegionTy::ProfileRegion(ID, a1, a2, superRegion);
80  void *InsertPos;
81  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
82                                                                   InsertPos));
83
84  if (!R) {
85    R = (RegionTy*) A.Allocate<RegionTy>();
86    new (R) RegionTy(a1, a2, superRegion);
87    Regions.InsertNode(R, InsertPos);
88  }
89
90  return R;
91}
92
93template <typename RegionTy, typename A1, typename A2>
94RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
95                                         const MemRegion *superRegion) {
96
97  llvm::FoldingSetNodeID ID;
98  RegionTy::ProfileRegion(ID, a1, a2, superRegion);
99  void *InsertPos;
100  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
101                                                                   InsertPos));
102
103  if (!R) {
104    R = (RegionTy*) A.Allocate<RegionTy>();
105    new (R) RegionTy(a1, a2, superRegion);
106    Regions.InsertNode(R, InsertPos);
107  }
108
109  return R;
110}
111
112template <typename RegionTy, typename A1, typename A2, typename A3>
113RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3,
114                                         const MemRegion *superRegion) {
115
116  llvm::FoldingSetNodeID ID;
117  RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
118  void *InsertPos;
119  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
120                                                                   InsertPos));
121
122  if (!R) {
123    R = (RegionTy*) A.Allocate<RegionTy>();
124    new (R) RegionTy(a1, a2, a3, superRegion);
125    Regions.InsertNode(R, InsertPos);
126  }
127
128  return R;
129}
130
131//===----------------------------------------------------------------------===//
132// Object destruction.
133//===----------------------------------------------------------------------===//
134
135MemRegion::~MemRegion() {}
136
137MemRegionManager::~MemRegionManager() {
138  // All regions and their data are BumpPtrAllocated.  No need to call
139  // their destructors.
140}
141
142//===----------------------------------------------------------------------===//
143// Basic methods.
144//===----------------------------------------------------------------------===//
145
146bool SubRegion::isSubRegionOf(const MemRegion* R) const {
147  const MemRegion* r = getSuperRegion();
148  while (r != 0) {
149    if (r == R)
150      return true;
151    if (const SubRegion* sr = dyn_cast<SubRegion>(r))
152      r = sr->getSuperRegion();
153    else
154      break;
155  }
156  return false;
157}
158
159MemRegionManager* SubRegion::getMemRegionManager() const {
160  const SubRegion* r = this;
161  do {
162    const MemRegion *superRegion = r->getSuperRegion();
163    if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
164      r = sr;
165      continue;
166    }
167    return superRegion->getMemRegionManager();
168  } while (1);
169}
170
171const StackFrameContext *VarRegion::getStackFrame() const {
172  const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
173  return SSR ? SSR->getStackFrame() : NULL;
174}
175
176//===----------------------------------------------------------------------===//
177// Region extents.
178//===----------------------------------------------------------------------===//
179
180DefinedOrUnknownSVal DeclRegion::getExtent(SValBuilder &svalBuilder) const {
181  ASTContext &Ctx = svalBuilder.getContext();
182  QualType T = getDesugaredValueType(Ctx);
183
184  if (isa<VariableArrayType>(T))
185    return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
186  if (isa<IncompleteArrayType>(T))
187    return UnknownVal();
188
189  CharUnits size = Ctx.getTypeSizeInChars(T);
190  QualType sizeTy = svalBuilder.getArrayIndexType();
191  return svalBuilder.makeIntVal(size.getQuantity(), sizeTy);
192}
193
194DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const {
195  DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder);
196
197  // A zero-length array at the end of a struct often stands for dynamically-
198  // allocated extra memory.
199  if (Extent.isZeroConstant()) {
200    QualType T = getDesugaredValueType(svalBuilder.getContext());
201
202    if (isa<ConstantArrayType>(T))
203      return UnknownVal();
204  }
205
206  return Extent;
207}
208
209DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
210  return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
211}
212
213DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
214  return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
215}
216
217DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
218  return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
219                                svalBuilder.getArrayIndexType());
220}
221
222QualType CXXBaseObjectRegion::getValueType() const {
223  return QualType(decl->getTypeForDecl(), 0);
224}
225
226//===----------------------------------------------------------------------===//
227// FoldingSet profiling.
228//===----------------------------------------------------------------------===//
229
230void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
231  ID.AddInteger((unsigned)getKind());
232}
233
234void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
235  ID.AddInteger((unsigned)getKind());
236  ID.AddPointer(getStackFrame());
237}
238
239void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
240  ID.AddInteger((unsigned)getKind());
241  ID.AddPointer(getCodeRegion());
242}
243
244void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
245                                 const StringLiteral* Str,
246                                 const MemRegion* superRegion) {
247  ID.AddInteger((unsigned) StringRegionKind);
248  ID.AddPointer(Str);
249  ID.AddPointer(superRegion);
250}
251
252void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
253                                 const Expr *Ex, unsigned cnt,
254                                 const MemRegion *) {
255  ID.AddInteger((unsigned) AllocaRegionKind);
256  ID.AddPointer(Ex);
257  ID.AddInteger(cnt);
258}
259
260void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
261  ProfileRegion(ID, Ex, Cnt, superRegion);
262}
263
264void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
265  CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
266}
267
268void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
269                                          const CompoundLiteralExpr *CL,
270                                          const MemRegion* superRegion) {
271  ID.AddInteger((unsigned) CompoundLiteralRegionKind);
272  ID.AddPointer(CL);
273  ID.AddPointer(superRegion);
274}
275
276void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
277                                  const PointerType *PT,
278                                  const MemRegion *sRegion) {
279  ID.AddInteger((unsigned) CXXThisRegionKind);
280  ID.AddPointer(PT);
281  ID.AddPointer(sRegion);
282}
283
284void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
285  CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
286}
287
288void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D,
289                               const MemRegion* superRegion, Kind k) {
290  ID.AddInteger((unsigned) k);
291  ID.AddPointer(D);
292  ID.AddPointer(superRegion);
293}
294
295void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
296  DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
297}
298
299void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
300  VarRegion::ProfileRegion(ID, getDecl(), superRegion);
301}
302
303void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
304                                   const MemRegion *sreg) {
305  ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind);
306  ID.Add(sym);
307  ID.AddPointer(sreg);
308}
309
310void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
311  SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
312}
313
314void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
315                                  QualType ElementType, SVal Idx,
316                                  const MemRegion* superRegion) {
317  ID.AddInteger(MemRegion::ElementRegionKind);
318  ID.Add(ElementType);
319  ID.AddPointer(superRegion);
320  Idx.Profile(ID);
321}
322
323void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
324  ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
325}
326
327void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
328                                       const FunctionDecl *FD,
329                                       const MemRegion*) {
330  ID.AddInteger(MemRegion::FunctionTextRegionKind);
331  ID.AddPointer(FD);
332}
333
334void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
335  FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
336}
337
338void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
339                                    const BlockDecl *BD, CanQualType,
340                                    const AnalysisDeclContext *AC,
341                                    const MemRegion*) {
342  ID.AddInteger(MemRegion::BlockTextRegionKind);
343  ID.AddPointer(BD);
344}
345
346void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
347  BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
348}
349
350void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
351                                    const BlockTextRegion *BC,
352                                    const LocationContext *LC,
353                                    const MemRegion *sReg) {
354  ID.AddInteger(MemRegion::BlockDataRegionKind);
355  ID.AddPointer(BC);
356  ID.AddPointer(LC);
357  ID.AddPointer(sReg);
358}
359
360void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
361  BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
362}
363
364void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
365                                        Expr const *Ex,
366                                        const MemRegion *sReg) {
367  ID.AddPointer(Ex);
368  ID.AddPointer(sReg);
369}
370
371void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
372  ProfileRegion(ID, Ex, getSuperRegion());
373}
374
375void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
376                                        const CXXRecordDecl *decl,
377                                        const MemRegion *sReg) {
378  ID.AddPointer(decl);
379  ID.AddPointer(sReg);
380}
381
382void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
383  ProfileRegion(ID, decl, superRegion);
384}
385
386//===----------------------------------------------------------------------===//
387// Region anchors.
388//===----------------------------------------------------------------------===//
389
390void GlobalsSpaceRegion::anchor() { }
391void HeapSpaceRegion::anchor() { }
392void UnknownSpaceRegion::anchor() { }
393void StackLocalsSpaceRegion::anchor() { }
394void StackArgumentsSpaceRegion::anchor() { }
395void TypedRegion::anchor() { }
396void TypedValueRegion::anchor() { }
397void CodeTextRegion::anchor() { }
398void SubRegion::anchor() { }
399
400//===----------------------------------------------------------------------===//
401// Region pretty-printing.
402//===----------------------------------------------------------------------===//
403
404void MemRegion::dump() const {
405  dumpToStream(llvm::errs());
406}
407
408std::string MemRegion::getString() const {
409  std::string s;
410  llvm::raw_string_ostream os(s);
411  dumpToStream(os);
412  return os.str();
413}
414
415void MemRegion::dumpToStream(raw_ostream &os) const {
416  os << "<Unknown Region>";
417}
418
419void AllocaRegion::dumpToStream(raw_ostream &os) const {
420  os << "alloca{" << (void*) Ex << ',' << Cnt << '}';
421}
422
423void FunctionTextRegion::dumpToStream(raw_ostream &os) const {
424  os << "code{" << getDecl()->getDeclName().getAsString() << '}';
425}
426
427void BlockTextRegion::dumpToStream(raw_ostream &os) const {
428  os << "block_code{" << (void*) this << '}';
429}
430
431void BlockDataRegion::dumpToStream(raw_ostream &os) const {
432  os << "block_data{" << BC << '}';
433}
434
435void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
436  // FIXME: More elaborate pretty-printing.
437  os << "{ " << (void*) CL <<  " }";
438}
439
440void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
441  os << "temp_object{" << getValueType().getAsString() << ','
442     << (void*) Ex << '}';
443}
444
445void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
446  os << "base " << decl->getName();
447}
448
449void CXXThisRegion::dumpToStream(raw_ostream &os) const {
450  os << "this";
451}
452
453void ElementRegion::dumpToStream(raw_ostream &os) const {
454  os << "element{" << superRegion << ','
455     << Index << ',' << getElementType().getAsString() << '}';
456}
457
458void FieldRegion::dumpToStream(raw_ostream &os) const {
459  os << superRegion << "->" << *getDecl();
460}
461
462void NonStaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
463  os << "NonStaticGlobalSpaceRegion";
464}
465
466void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
467  os << "ivar{" << superRegion << ',' << *getDecl() << '}';
468}
469
470void StringRegion::dumpToStream(raw_ostream &os) const {
471  Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOptions()));
472}
473
474void SymbolicRegion::dumpToStream(raw_ostream &os) const {
475  os << "SymRegion{" << sym << '}';
476}
477
478void VarRegion::dumpToStream(raw_ostream &os) const {
479  os << *cast<VarDecl>(D);
480}
481
482void RegionRawOffset::dump() const {
483  dumpToStream(llvm::errs());
484}
485
486void RegionRawOffset::dumpToStream(raw_ostream &os) const {
487  os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
488}
489
490void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
491  os << "StaticGlobalsMemSpace{" << CR << '}';
492}
493
494//===----------------------------------------------------------------------===//
495// MemRegionManager methods.
496//===----------------------------------------------------------------------===//
497
498template <typename REG>
499const REG *MemRegionManager::LazyAllocate(REG*& region) {
500  if (!region) {
501    region = (REG*) A.Allocate<REG>();
502    new (region) REG(this);
503  }
504
505  return region;
506}
507
508template <typename REG, typename ARG>
509const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
510  if (!region) {
511    region = (REG*) A.Allocate<REG>();
512    new (region) REG(this, a);
513  }
514
515  return region;
516}
517
518const StackLocalsSpaceRegion*
519MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
520  assert(STC);
521  StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
522
523  if (R)
524    return R;
525
526  R = A.Allocate<StackLocalsSpaceRegion>();
527  new (R) StackLocalsSpaceRegion(this, STC);
528  return R;
529}
530
531const StackArgumentsSpaceRegion *
532MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
533  assert(STC);
534  StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
535
536  if (R)
537    return R;
538
539  R = A.Allocate<StackArgumentsSpaceRegion>();
540  new (R) StackArgumentsSpaceRegion(this, STC);
541  return R;
542}
543
544const GlobalsSpaceRegion
545*MemRegionManager::getGlobalsRegion(const CodeTextRegion *CR) {
546  if (!CR)
547    return LazyAllocate(globals);
548
549  StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
550  if (R)
551    return R;
552
553  R = A.Allocate<StaticGlobalSpaceRegion>();
554  new (R) StaticGlobalSpaceRegion(this, CR);
555  return R;
556}
557
558const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
559  return LazyAllocate(heap);
560}
561
562const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
563  return LazyAllocate(unknown);
564}
565
566const MemSpaceRegion *MemRegionManager::getCodeRegion() {
567  return LazyAllocate(code);
568}
569
570//===----------------------------------------------------------------------===//
571// Constructing regions.
572//===----------------------------------------------------------------------===//
573
574const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
575  return getSubRegion<StringRegion>(Str, getGlobalsRegion());
576}
577
578const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
579                                                const LocationContext *LC) {
580  const MemRegion *sReg = 0;
581
582  if (D->hasGlobalStorage() && !D->isStaticLocal())
583    sReg = getGlobalsRegion();
584  else {
585    // FIXME: Once we implement scope handling, we will need to properly lookup
586    // 'D' to the proper LocationContext.
587    const DeclContext *DC = D->getDeclContext();
588    const StackFrameContext *STC = LC->getStackFrameForDeclContext(DC);
589
590    if (!STC)
591      sReg = getUnknownRegion();
592    else {
593      if (D->hasLocalStorage()) {
594        sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
595               ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
596               : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
597      }
598      else {
599        assert(D->isStaticLocal());
600        const Decl *D = STC->getDecl();
601        if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
602          sReg = getGlobalsRegion(getFunctionTextRegion(FD));
603        else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
604          const BlockTextRegion *BTR =
605            getBlockTextRegion(BD,
606                     C.getCanonicalType(BD->getSignatureAsWritten()->getType()),
607                     STC->getAnalysisDeclContext());
608          sReg = getGlobalsRegion(BTR);
609        }
610        else {
611          // FIXME: For ObjC-methods, we need a new CodeTextRegion.  For now
612          // just use the main global memspace.
613          sReg = getGlobalsRegion();
614        }
615      }
616    }
617  }
618
619  return getSubRegion<VarRegion>(D, sReg);
620}
621
622const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
623                                                const MemRegion *superR) {
624  return getSubRegion<VarRegion>(D, superR);
625}
626
627const BlockDataRegion *
628MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC,
629                                     const LocationContext *LC) {
630  const MemRegion *sReg = 0;
631
632  if (LC) {
633    // FIXME: Once we implement scope handling, we want the parent region
634    // to be the scope.
635    const StackFrameContext *STC = LC->getCurrentStackFrame();
636    assert(STC);
637    sReg = getStackLocalsRegion(STC);
638  }
639  else {
640    // We allow 'LC' to be NULL for cases where want BlockDataRegions
641    // without context-sensitivity.
642    sReg = getUnknownRegion();
643  }
644
645  return getSubRegion<BlockDataRegion>(BC, LC, sReg);
646}
647
648const CompoundLiteralRegion*
649MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
650                                           const LocationContext *LC) {
651
652  const MemRegion *sReg = 0;
653
654  if (CL->isFileScope())
655    sReg = getGlobalsRegion();
656  else {
657    const StackFrameContext *STC = LC->getCurrentStackFrame();
658    assert(STC);
659    sReg = getStackLocalsRegion(STC);
660  }
661
662  return getSubRegion<CompoundLiteralRegion>(CL, sReg);
663}
664
665const ElementRegion*
666MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
667                                   const MemRegion* superRegion,
668                                   ASTContext &Ctx){
669
670  QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
671
672  llvm::FoldingSetNodeID ID;
673  ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
674
675  void *InsertPos;
676  MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
677  ElementRegion* R = cast_or_null<ElementRegion>(data);
678
679  if (!R) {
680    R = (ElementRegion*) A.Allocate<ElementRegion>();
681    new (R) ElementRegion(T, Idx, superRegion);
682    Regions.InsertNode(R, InsertPos);
683  }
684
685  return R;
686}
687
688const FunctionTextRegion *
689MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) {
690  return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
691}
692
693const BlockTextRegion *
694MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
695                                     AnalysisDeclContext *AC) {
696  return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
697}
698
699
700/// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
701const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
702  return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
703}
704
705const FieldRegion*
706MemRegionManager::getFieldRegion(const FieldDecl *d,
707                                 const MemRegion* superRegion){
708  return getSubRegion<FieldRegion>(d, superRegion);
709}
710
711const ObjCIvarRegion*
712MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
713                                    const MemRegion* superRegion) {
714  return getSubRegion<ObjCIvarRegion>(d, superRegion);
715}
716
717const CXXTempObjectRegion*
718MemRegionManager::getCXXTempObjectRegion(Expr const *E,
719                                         LocationContext const *LC) {
720  const StackFrameContext *SFC = LC->getCurrentStackFrame();
721  assert(SFC);
722  return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
723}
724
725const CXXBaseObjectRegion *
726MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *decl,
727                                         const MemRegion *superRegion) {
728  return getSubRegion<CXXBaseObjectRegion>(decl, superRegion);
729}
730
731const CXXThisRegion*
732MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
733                                   const LocationContext *LC) {
734  const StackFrameContext *STC = LC->getCurrentStackFrame();
735  assert(STC);
736  const PointerType *PT = thisPointerTy->getAs<PointerType>();
737  assert(PT);
738  return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
739}
740
741const AllocaRegion*
742MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
743                                  const LocationContext *LC) {
744  const StackFrameContext *STC = LC->getCurrentStackFrame();
745  assert(STC);
746  return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
747}
748
749const MemSpaceRegion *MemRegion::getMemorySpace() const {
750  const MemRegion *R = this;
751  const SubRegion* SR = dyn_cast<SubRegion>(this);
752
753  while (SR) {
754    R = SR->getSuperRegion();
755    SR = dyn_cast<SubRegion>(R);
756  }
757
758  return dyn_cast<MemSpaceRegion>(R);
759}
760
761bool MemRegion::hasStackStorage() const {
762  return isa<StackSpaceRegion>(getMemorySpace());
763}
764
765bool MemRegion::hasStackNonParametersStorage() const {
766  return isa<StackLocalsSpaceRegion>(getMemorySpace());
767}
768
769bool MemRegion::hasStackParametersStorage() const {
770  return isa<StackArgumentsSpaceRegion>(getMemorySpace());
771}
772
773bool MemRegion::hasGlobalsOrParametersStorage() const {
774  const MemSpaceRegion *MS = getMemorySpace();
775  return isa<StackArgumentsSpaceRegion>(MS) ||
776         isa<GlobalsSpaceRegion>(MS);
777}
778
779// getBaseRegion strips away all elements and fields, and get the base region
780// of them.
781const MemRegion *MemRegion::getBaseRegion() const {
782  const MemRegion *R = this;
783  while (true) {
784    switch (R->getKind()) {
785      case MemRegion::ElementRegionKind:
786      case MemRegion::FieldRegionKind:
787      case MemRegion::ObjCIvarRegionKind:
788      case MemRegion::CXXBaseObjectRegionKind:
789        R = cast<SubRegion>(R)->getSuperRegion();
790        continue;
791      default:
792        break;
793    }
794    break;
795  }
796  return R;
797}
798
799//===----------------------------------------------------------------------===//
800// View handling.
801//===----------------------------------------------------------------------===//
802
803const MemRegion *MemRegion::StripCasts() const {
804  const MemRegion *R = this;
805  while (true) {
806    if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
807      // FIXME: generalize.  Essentially we want to strip away ElementRegions
808      // that were layered on a symbolic region because of casts.  We only
809      // want to strip away ElementRegions, however, where the index is 0.
810      SVal index = ER->getIndex();
811      if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
812        if (CI->getValue().getSExtValue() == 0) {
813          R = ER->getSuperRegion();
814          continue;
815        }
816      }
817    }
818    break;
819  }
820  return R;
821}
822
823// FIXME: Merge with the implementation of the same method in Store.cpp
824static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
825  if (const RecordType *RT = Ty->getAs<RecordType>()) {
826    const RecordDecl *D = RT->getDecl();
827    if (!D->getDefinition())
828      return false;
829  }
830
831  return true;
832}
833
834RegionRawOffset ElementRegion::getAsArrayOffset() const {
835  CharUnits offset = CharUnits::Zero();
836  const ElementRegion *ER = this;
837  const MemRegion *superR = NULL;
838  ASTContext &C = getContext();
839
840  // FIXME: Handle multi-dimensional arrays.
841
842  while (ER) {
843    superR = ER->getSuperRegion();
844
845    // FIXME: generalize to symbolic offsets.
846    SVal index = ER->getIndex();
847    if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
848      // Update the offset.
849      int64_t i = CI->getValue().getSExtValue();
850
851      if (i != 0) {
852        QualType elemType = ER->getElementType();
853
854        // If we are pointing to an incomplete type, go no further.
855        if (!IsCompleteType(C, elemType)) {
856          superR = ER;
857          break;
858        }
859
860        CharUnits size = C.getTypeSizeInChars(elemType);
861        offset += (i * size);
862      }
863
864      // Go to the next ElementRegion (if any).
865      ER = dyn_cast<ElementRegion>(superR);
866      continue;
867    }
868
869    return NULL;
870  }
871
872  assert(superR && "super region cannot be NULL");
873  return RegionRawOffset(superR, offset);
874}
875
876RegionOffset MemRegion::getAsOffset() const {
877  const MemRegion *R = this;
878  int64_t Offset = 0;
879
880  while (1) {
881    switch (R->getKind()) {
882    default:
883      return RegionOffset(0);
884    case SymbolicRegionKind:
885    case AllocaRegionKind:
886    case CompoundLiteralRegionKind:
887    case CXXThisRegionKind:
888    case StringRegionKind:
889    case VarRegionKind:
890    case CXXTempObjectRegionKind:
891      goto Finish;
892    case ElementRegionKind: {
893      const ElementRegion *ER = cast<ElementRegion>(R);
894      QualType EleTy = ER->getValueType();
895
896      if (!IsCompleteType(getContext(), EleTy))
897        return RegionOffset(0);
898
899      SVal Index = ER->getIndex();
900      if (const nonloc::ConcreteInt *CI=dyn_cast<nonloc::ConcreteInt>(&Index)) {
901        int64_t i = CI->getValue().getSExtValue();
902        CharUnits Size = getContext().getTypeSizeInChars(EleTy);
903        Offset += i * Size.getQuantity() * 8;
904      } else {
905        // We cannot compute offset for non-concrete index.
906        return RegionOffset(0);
907      }
908      R = ER->getSuperRegion();
909      break;
910    }
911    case FieldRegionKind: {
912      const FieldRegion *FR = cast<FieldRegion>(R);
913      const RecordDecl *RD = FR->getDecl()->getParent();
914      if (!RD->isCompleteDefinition())
915        // We cannot compute offset for incomplete type.
916        return RegionOffset(0);
917      // Get the field number.
918      unsigned idx = 0;
919      for (RecordDecl::field_iterator FI = RD->field_begin(),
920             FE = RD->field_end(); FI != FE; ++FI, ++idx)
921        if (FR->getDecl() == *FI)
922          break;
923
924      const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
925      // This is offset in bits.
926      Offset += Layout.getFieldOffset(idx);
927      R = FR->getSuperRegion();
928      break;
929    }
930    }
931  }
932
933 Finish:
934  return RegionOffset(R, Offset);
935}
936
937//===----------------------------------------------------------------------===//
938// BlockDataRegion
939//===----------------------------------------------------------------------===//
940
941void BlockDataRegion::LazyInitializeReferencedVars() {
942  if (ReferencedVars)
943    return;
944
945  AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
946  AnalysisDeclContext::referenced_decls_iterator I, E;
947  llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
948
949  if (I == E) {
950    ReferencedVars = (void*) 0x1;
951    return;
952  }
953
954  MemRegionManager &MemMgr = *getMemRegionManager();
955  llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
956  BumpVectorContext BC(A);
957
958  typedef BumpVector<const MemRegion*> VarVec;
959  VarVec *BV = (VarVec*) A.Allocate<VarVec>();
960  new (BV) VarVec(BC, E - I);
961
962  for ( ; I != E; ++I) {
963    const VarDecl *VD = *I;
964    const VarRegion *VR = 0;
965
966    if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage())
967      VR = MemMgr.getVarRegion(VD, this);
968    else {
969      if (LC)
970        VR = MemMgr.getVarRegion(VD, LC);
971      else {
972        VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
973      }
974    }
975
976    assert(VR);
977    BV->push_back(VR, BC);
978  }
979
980  ReferencedVars = BV;
981}
982
983BlockDataRegion::referenced_vars_iterator
984BlockDataRegion::referenced_vars_begin() const {
985  const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
986
987  BumpVector<const MemRegion*> *Vec =
988    static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
989
990  return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ?
991                                                   NULL : Vec->begin());
992}
993
994BlockDataRegion::referenced_vars_iterator
995BlockDataRegion::referenced_vars_end() const {
996  const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
997
998  BumpVector<const MemRegion*> *Vec =
999    static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1000
1001  return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ?
1002                                                   NULL : Vec->end());
1003}
1004