MemRegion.cpp revision 6dc5c33fd4334ccf4a661c331f86e23829e51d55 
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/AST/Attr.h"
18#include "clang/AST/CharUnits.h"
19#include "clang/AST/DeclObjC.h"
20#include "clang/AST/RecordLayout.h"
21#include "clang/Analysis/AnalysisContext.h"
22#include "clang/Analysis/Support/BumpVector.h"
23#include "clang/Basic/SourceManager.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
25#include "llvm/Support/raw_ostream.h"
26
27using namespace clang;
28using namespace ento;
29
30//===----------------------------------------------------------------------===//
31// MemRegion Construction.
32//===----------------------------------------------------------------------===//
33
34template<typename RegionTy> struct MemRegionManagerTrait;
35
36template <typename RegionTy, typename A1>
37RegionTy* MemRegionManager::getRegion(const A1 a1) {
38
39  const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
40  MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
41
42  llvm::FoldingSetNodeID ID;
43  RegionTy::ProfileRegion(ID, a1, superRegion);
44  void *InsertPos;
45  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
46                                                                   InsertPos));
47
48  if (!R) {
49    R = (RegionTy*) A.Allocate<RegionTy>();
50    new (R) RegionTy(a1, superRegion);
51    Regions.InsertNode(R, InsertPos);
52  }
53
54  return R;
55}
56
57template <typename RegionTy, typename A1>
58RegionTy* MemRegionManager::getSubRegion(const A1 a1,
59                                         const MemRegion *superRegion) {
60  llvm::FoldingSetNodeID ID;
61  RegionTy::ProfileRegion(ID, a1, superRegion);
62  void *InsertPos;
63  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
64                                                                   InsertPos));
65
66  if (!R) {
67    R = (RegionTy*) A.Allocate<RegionTy>();
68    new (R) RegionTy(a1, superRegion);
69    Regions.InsertNode(R, InsertPos);
70  }
71
72  return R;
73}
74
75template <typename RegionTy, typename A1, typename A2>
76RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
77
78  const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
79  MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
80
81  llvm::FoldingSetNodeID ID;
82  RegionTy::ProfileRegion(ID, a1, a2, superRegion);
83  void *InsertPos;
84  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
85                                                                   InsertPos));
86
87  if (!R) {
88    R = (RegionTy*) A.Allocate<RegionTy>();
89    new (R) RegionTy(a1, a2, superRegion);
90    Regions.InsertNode(R, InsertPos);
91  }
92
93  return R;
94}
95
96template <typename RegionTy, typename A1, typename A2>
97RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
98                                         const MemRegion *superRegion) {
99
100  llvm::FoldingSetNodeID ID;
101  RegionTy::ProfileRegion(ID, a1, a2, superRegion);
102  void *InsertPos;
103  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
104                                                                   InsertPos));
105
106  if (!R) {
107    R = (RegionTy*) A.Allocate<RegionTy>();
108    new (R) RegionTy(a1, a2, superRegion);
109    Regions.InsertNode(R, InsertPos);
110  }
111
112  return R;
113}
114
115template <typename RegionTy, typename A1, typename A2, typename A3>
116RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3,
117                                         const MemRegion *superRegion) {
118
119  llvm::FoldingSetNodeID ID;
120  RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
121  void *InsertPos;
122  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
123                                                                   InsertPos));
124
125  if (!R) {
126    R = (RegionTy*) A.Allocate<RegionTy>();
127    new (R) RegionTy(a1, a2, a3, superRegion);
128    Regions.InsertNode(R, InsertPos);
129  }
130
131  return R;
132}
133
134//===----------------------------------------------------------------------===//
135// Object destruction.
136//===----------------------------------------------------------------------===//
137
138MemRegion::~MemRegion() {}
139
140MemRegionManager::~MemRegionManager() {
141  // All regions and their data are BumpPtrAllocated.  No need to call
142  // their destructors.
143}
144
145//===----------------------------------------------------------------------===//
146// Basic methods.
147//===----------------------------------------------------------------------===//
148
149bool SubRegion::isSubRegionOf(const MemRegion* R) const {
150  const MemRegion* r = getSuperRegion();
151  while (r != 0) {
152    if (r == R)
153      return true;
154    if (const SubRegion* sr = dyn_cast<SubRegion>(r))
155      r = sr->getSuperRegion();
156    else
157      break;
158  }
159  return false;
160}
161
162MemRegionManager* SubRegion::getMemRegionManager() const {
163  const SubRegion* r = this;
164  do {
165    const MemRegion *superRegion = r->getSuperRegion();
166    if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
167      r = sr;
168      continue;
169    }
170    return superRegion->getMemRegionManager();
171  } while (1);
172}
173
174const StackFrameContext *VarRegion::getStackFrame() const {
175  const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
176  return SSR ? SSR->getStackFrame() : NULL;
177}
178
179//===----------------------------------------------------------------------===//
180// Region extents.
181//===----------------------------------------------------------------------===//
182
183DefinedOrUnknownSVal TypedValueRegion::getExtent(SValBuilder &svalBuilder) const {
184  ASTContext &Ctx = svalBuilder.getContext();
185  QualType T = getDesugaredValueType(Ctx);
186
187  if (isa<VariableArrayType>(T))
188    return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
189  if (isa<IncompleteArrayType>(T))
190    return UnknownVal();
191
192  CharUnits size = Ctx.getTypeSizeInChars(T);
193  QualType sizeTy = svalBuilder.getArrayIndexType();
194  return svalBuilder.makeIntVal(size.getQuantity(), sizeTy);
195}
196
197DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const {
198  DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder);
199
200  // A zero-length array at the end of a struct often stands for dynamically-
201  // allocated extra memory.
202  if (Extent.isZeroConstant()) {
203    QualType T = getDesugaredValueType(svalBuilder.getContext());
204
205    if (isa<ConstantArrayType>(T))
206      return UnknownVal();
207  }
208
209  return Extent;
210}
211
212DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
213  return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
214}
215
216DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
217  return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
218}
219
220DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
221  return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
222                                svalBuilder.getArrayIndexType());
223}
224
225ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg)
226  : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
227
228const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
229  return cast<ObjCIvarDecl>(D);
230}
231
232QualType ObjCIvarRegion::getValueType() const {
233  return getDecl()->getType();
234}
235
236QualType CXXBaseObjectRegion::getValueType() const {
237  return QualType(getDecl()->getTypeForDecl(), 0);
238}
239
240//===----------------------------------------------------------------------===//
241// FoldingSet profiling.
242//===----------------------------------------------------------------------===//
243
244void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
245  ID.AddInteger((unsigned)getKind());
246}
247
248void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
249  ID.AddInteger((unsigned)getKind());
250  ID.AddPointer(getStackFrame());
251}
252
253void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
254  ID.AddInteger((unsigned)getKind());
255  ID.AddPointer(getCodeRegion());
256}
257
258void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
259                                 const StringLiteral* Str,
260                                 const MemRegion* superRegion) {
261  ID.AddInteger((unsigned) StringRegionKind);
262  ID.AddPointer(Str);
263  ID.AddPointer(superRegion);
264}
265
266void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
267                                     const ObjCStringLiteral* Str,
268                                     const MemRegion* superRegion) {
269  ID.AddInteger((unsigned) ObjCStringRegionKind);
270  ID.AddPointer(Str);
271  ID.AddPointer(superRegion);
272}
273
274void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
275                                 const Expr *Ex, unsigned cnt,
276                                 const MemRegion *superRegion) {
277  ID.AddInteger((unsigned) AllocaRegionKind);
278  ID.AddPointer(Ex);
279  ID.AddInteger(cnt);
280  ID.AddPointer(superRegion);
281}
282
283void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
284  ProfileRegion(ID, Ex, Cnt, superRegion);
285}
286
287void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
288  CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
289}
290
291void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
292                                          const CompoundLiteralExpr *CL,
293                                          const MemRegion* superRegion) {
294  ID.AddInteger((unsigned) CompoundLiteralRegionKind);
295  ID.AddPointer(CL);
296  ID.AddPointer(superRegion);
297}
298
299void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
300                                  const PointerType *PT,
301                                  const MemRegion *sRegion) {
302  ID.AddInteger((unsigned) CXXThisRegionKind);
303  ID.AddPointer(PT);
304  ID.AddPointer(sRegion);
305}
306
307void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
308  CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
309}
310
311void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
312                                   const ObjCIvarDecl *ivd,
313                                   const MemRegion* superRegion) {
314  DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
315}
316
317void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D,
318                               const MemRegion* superRegion, Kind k) {
319  ID.AddInteger((unsigned) k);
320  ID.AddPointer(D);
321  ID.AddPointer(superRegion);
322}
323
324void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
325  DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
326}
327
328void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
329  VarRegion::ProfileRegion(ID, getDecl(), superRegion);
330}
331
332void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
333                                   const MemRegion *sreg) {
334  ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind);
335  ID.Add(sym);
336  ID.AddPointer(sreg);
337}
338
339void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
340  SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
341}
342
343void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
344                                  QualType ElementType, SVal Idx,
345                                  const MemRegion* superRegion) {
346  ID.AddInteger(MemRegion::ElementRegionKind);
347  ID.Add(ElementType);
348  ID.AddPointer(superRegion);
349  Idx.Profile(ID);
350}
351
352void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
353  ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
354}
355
356void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
357                                       const NamedDecl *FD,
358                                       const MemRegion*) {
359  ID.AddInteger(MemRegion::FunctionTextRegionKind);
360  ID.AddPointer(FD);
361}
362
363void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
364  FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
365}
366
367void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
368                                    const BlockDecl *BD, CanQualType,
369                                    const AnalysisDeclContext *AC,
370                                    const MemRegion*) {
371  ID.AddInteger(MemRegion::BlockTextRegionKind);
372  ID.AddPointer(BD);
373}
374
375void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
376  BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
377}
378
379void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
380                                    const BlockTextRegion *BC,
381                                    const LocationContext *LC,
382                                    const MemRegion *sReg) {
383  ID.AddInteger(MemRegion::BlockDataRegionKind);
384  ID.AddPointer(BC);
385  ID.AddPointer(LC);
386  ID.AddPointer(sReg);
387}
388
389void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
390  BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
391}
392
393void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
394                                        Expr const *Ex,
395                                        const MemRegion *sReg) {
396  ID.AddPointer(Ex);
397  ID.AddPointer(sReg);
398}
399
400void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
401  ProfileRegion(ID, Ex, getSuperRegion());
402}
403
404void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
405                                        const CXXRecordDecl *RD,
406                                        bool IsVirtual,
407                                        const MemRegion *SReg) {
408  ID.AddPointer(RD);
409  ID.AddBoolean(IsVirtual);
410  ID.AddPointer(SReg);
411}
412
413void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
414  ProfileRegion(ID, getDecl(), isVirtual(), superRegion);
415}
416
417//===----------------------------------------------------------------------===//
418// Region anchors.
419//===----------------------------------------------------------------------===//
420
421void GlobalsSpaceRegion::anchor() { }
422void HeapSpaceRegion::anchor() { }
423void UnknownSpaceRegion::anchor() { }
424void StackLocalsSpaceRegion::anchor() { }
425void StackArgumentsSpaceRegion::anchor() { }
426void TypedRegion::anchor() { }
427void TypedValueRegion::anchor() { }
428void CodeTextRegion::anchor() { }
429void SubRegion::anchor() { }
430
431//===----------------------------------------------------------------------===//
432// Region pretty-printing.
433//===----------------------------------------------------------------------===//
434
435void MemRegion::dump() const {
436  dumpToStream(llvm::errs());
437}
438
439std::string MemRegion::getString() const {
440  std::string s;
441  llvm::raw_string_ostream os(s);
442  dumpToStream(os);
443  return os.str();
444}
445
446void MemRegion::dumpToStream(raw_ostream &os) const {
447  os << "<Unknown Region>";
448}
449
450void AllocaRegion::dumpToStream(raw_ostream &os) const {
451  os << "alloca{" << (const void*) Ex << ',' << Cnt << '}';
452}
453
454void FunctionTextRegion::dumpToStream(raw_ostream &os) const {
455  os << "code{" << getDecl()->getDeclName().getAsString() << '}';
456}
457
458void BlockTextRegion::dumpToStream(raw_ostream &os) const {
459  os << "block_code{" << (const void*) this << '}';
460}
461
462void BlockDataRegion::dumpToStream(raw_ostream &os) const {
463  os << "block_data{" << BC << '}';
464}
465
466void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
467  // FIXME: More elaborate pretty-printing.
468  os << "{ " << (const void*) CL <<  " }";
469}
470
471void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
472  os << "temp_object{" << getValueType().getAsString() << ','
473     << (const void*) Ex << '}';
474}
475
476void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
477  os << "base{" << superRegion << ',' << getDecl()->getName() << '}';
478}
479
480void CXXThisRegion::dumpToStream(raw_ostream &os) const {
481  os << "this";
482}
483
484void ElementRegion::dumpToStream(raw_ostream &os) const {
485  os << "element{" << superRegion << ','
486     << Index << ',' << getElementType().getAsString() << '}';
487}
488
489void FieldRegion::dumpToStream(raw_ostream &os) const {
490  os << superRegion << "->" << *getDecl();
491}
492
493void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
494  os << "ivar{" << superRegion << ',' << *getDecl() << '}';
495}
496
497void StringRegion::dumpToStream(raw_ostream &os) const {
498  Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
499}
500
501void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
502  Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
503}
504
505void SymbolicRegion::dumpToStream(raw_ostream &os) const {
506  os << "SymRegion{" << sym << '}';
507}
508
509void VarRegion::dumpToStream(raw_ostream &os) const {
510  os << *cast<VarDecl>(D);
511}
512
513void RegionRawOffset::dump() const {
514  dumpToStream(llvm::errs());
515}
516
517void RegionRawOffset::dumpToStream(raw_ostream &os) const {
518  os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
519}
520
521void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
522  os << "StaticGlobalsMemSpace{" << CR << '}';
523}
524
525void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
526  os << "GlobalInternalSpaceRegion";
527}
528
529void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
530  os << "GlobalSystemSpaceRegion";
531}
532
533void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
534  os << "GlobalImmutableSpaceRegion";
535}
536
537void HeapSpaceRegion::dumpToStream(raw_ostream &os) const {
538  os << "HeapSpaceRegion";
539}
540
541void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const {
542  os << "UnknownSpaceRegion";
543}
544
545void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const {
546  os << "StackArgumentsSpaceRegion";
547}
548
549void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const {
550  os << "StackLocalsSpaceRegion";
551}
552
553bool MemRegion::canPrintPretty() const {
554  return false;
555}
556
557void MemRegion::printPretty(raw_ostream &os) const {
558  return;
559}
560
561bool VarRegion::canPrintPretty() const {
562  return true;
563}
564
565void VarRegion::printPretty(raw_ostream &os) const {
566  os << getDecl()->getName();
567}
568
569bool ObjCIvarRegion::canPrintPretty() const {
570  return true;
571}
572
573void ObjCIvarRegion::printPretty(raw_ostream &os) const {
574  os << getDecl()->getName();
575}
576
577bool FieldRegion::canPrintPretty() const {
578  return superRegion->canPrintPretty();
579}
580
581void FieldRegion::printPretty(raw_ostream &os) const {
582  superRegion->printPretty(os);
583  os << "." << getDecl()->getName();
584}
585
586//===----------------------------------------------------------------------===//
587// MemRegionManager methods.
588//===----------------------------------------------------------------------===//
589
590template <typename REG>
591const REG *MemRegionManager::LazyAllocate(REG*& region) {
592  if (!region) {
593    region = (REG*) A.Allocate<REG>();
594    new (region) REG(this);
595  }
596
597  return region;
598}
599
600template <typename REG, typename ARG>
601const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
602  if (!region) {
603    region = (REG*) A.Allocate<REG>();
604    new (region) REG(this, a);
605  }
606
607  return region;
608}
609
610const StackLocalsSpaceRegion*
611MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
612  assert(STC);
613  StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
614
615  if (R)
616    return R;
617
618  R = A.Allocate<StackLocalsSpaceRegion>();
619  new (R) StackLocalsSpaceRegion(this, STC);
620  return R;
621}
622
623const StackArgumentsSpaceRegion *
624MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
625  assert(STC);
626  StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
627
628  if (R)
629    return R;
630
631  R = A.Allocate<StackArgumentsSpaceRegion>();
632  new (R) StackArgumentsSpaceRegion(this, STC);
633  return R;
634}
635
636const GlobalsSpaceRegion
637*MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
638                                    const CodeTextRegion *CR) {
639  if (!CR) {
640    if (K == MemRegion::GlobalSystemSpaceRegionKind)
641      return LazyAllocate(SystemGlobals);
642    if (K == MemRegion::GlobalImmutableSpaceRegionKind)
643      return LazyAllocate(ImmutableGlobals);
644    assert(K == MemRegion::GlobalInternalSpaceRegionKind);
645    return LazyAllocate(InternalGlobals);
646  }
647
648  assert(K == MemRegion::StaticGlobalSpaceRegionKind);
649  StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
650  if (R)
651    return R;
652
653  R = A.Allocate<StaticGlobalSpaceRegion>();
654  new (R) StaticGlobalSpaceRegion(this, CR);
655  return R;
656}
657
658const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
659  return LazyAllocate(heap);
660}
661
662const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
663  return LazyAllocate(unknown);
664}
665
666const MemSpaceRegion *MemRegionManager::getCodeRegion() {
667  return LazyAllocate(code);
668}
669
670//===----------------------------------------------------------------------===//
671// Constructing regions.
672//===----------------------------------------------------------------------===//
673const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
674  return getSubRegion<StringRegion>(Str, getGlobalsRegion());
675}
676
677const ObjCStringRegion *
678MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){
679  return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion());
680}
681
682/// Look through a chain of LocationContexts to either find the
683/// StackFrameContext that matches a DeclContext, or find a VarRegion
684/// for a variable captured by a block.
685static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
686getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
687                                      const DeclContext *DC,
688                                      const VarDecl *VD) {
689  while (LC) {
690    if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
691      if (cast<DeclContext>(SFC->getDecl()) == DC)
692        return SFC;
693    }
694    if (const BlockInvocationContext *BC =
695        dyn_cast<BlockInvocationContext>(LC)) {
696      const BlockDataRegion *BR =
697        static_cast<const BlockDataRegion*>(BC->getContextData());
698      // FIXME: This can be made more efficient.
699      for (BlockDataRegion::referenced_vars_iterator
700           I = BR->referenced_vars_begin(),
701           E = BR->referenced_vars_end(); I != E; ++I) {
702        if (const VarRegion *VR = dyn_cast<VarRegion>(I.getOriginalRegion()))
703          if (VR->getDecl() == VD)
704            return cast<VarRegion>(I.getCapturedRegion());
705      }
706    }
707
708    LC = LC->getParent();
709  }
710  return (const StackFrameContext*)0;
711}
712
713const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
714                                                const LocationContext *LC) {
715  const MemRegion *sReg = 0;
716
717  if (D->hasGlobalStorage() && !D->isStaticLocal()) {
718
719    // First handle the globals defined in system headers.
720    if (C.getSourceManager().isInSystemHeader(D->getLocation())) {
721      // Whitelist the system globals which often DO GET modified, assume the
722      // rest are immutable.
723      if (D->getName().find("errno") != StringRef::npos)
724        sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
725      else
726        sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
727
728    // Treat other globals as GlobalInternal unless they are constants.
729    } else {
730      QualType GQT = D->getType();
731      const Type *GT = GQT.getTypePtrOrNull();
732      // TODO: We could walk the complex types here and see if everything is
733      // constified.
734      if (GT && GQT.isConstQualified() && GT->isArithmeticType())
735        sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
736      else
737        sReg = getGlobalsRegion();
738    }
739
740  // Finally handle static locals.
741  } else {
742    // FIXME: Once we implement scope handling, we will need to properly lookup
743    // 'D' to the proper LocationContext.
744    const DeclContext *DC = D->getDeclContext();
745    llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V =
746      getStackOrCaptureRegionForDeclContext(LC, DC, D);
747
748    if (V.is<const VarRegion*>())
749      return V.get<const VarRegion*>();
750
751    const StackFrameContext *STC = V.get<const StackFrameContext*>();
752
753    if (!STC)
754      sReg = getUnknownRegion();
755    else {
756      if (D->hasLocalStorage()) {
757        sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
758               ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
759               : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
760      }
761      else {
762        assert(D->isStaticLocal());
763        const Decl *STCD = STC->getDecl();
764        if (isa<FunctionDecl>(STCD) || isa<ObjCMethodDecl>(STCD))
765          sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
766                                  getFunctionTextRegion(cast<NamedDecl>(STCD)));
767        else if (const BlockDecl *BD = dyn_cast<BlockDecl>(STCD)) {
768          const BlockTextRegion *BTR =
769            getBlockTextRegion(BD,
770                     C.getCanonicalType(BD->getSignatureAsWritten()->getType()),
771                     STC->getAnalysisDeclContext());
772          sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
773                                  BTR);
774        }
775        else {
776          sReg = getGlobalsRegion();
777        }
778      }
779    }
780  }
781
782  return getSubRegion<VarRegion>(D, sReg);
783}
784
785const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
786                                                const MemRegion *superR) {
787  return getSubRegion<VarRegion>(D, superR);
788}
789
790const BlockDataRegion *
791MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC,
792                                     const LocationContext *LC) {
793  const MemRegion *sReg = 0;
794  const BlockDecl *BD = BC->getDecl();
795  if (!BD->hasCaptures()) {
796    // This handles 'static' blocks.
797    sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
798  }
799  else {
800    if (LC) {
801      // FIXME: Once we implement scope handling, we want the parent region
802      // to be the scope.
803      const StackFrameContext *STC = LC->getCurrentStackFrame();
804      assert(STC);
805      sReg = getStackLocalsRegion(STC);
806    }
807    else {
808      // We allow 'LC' to be NULL for cases where want BlockDataRegions
809      // without context-sensitivity.
810      sReg = getUnknownRegion();
811    }
812  }
813
814  return getSubRegion<BlockDataRegion>(BC, LC, sReg);
815}
816
817const CompoundLiteralRegion*
818MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
819                                           const LocationContext *LC) {
820
821  const MemRegion *sReg = 0;
822
823  if (CL->isFileScope())
824    sReg = getGlobalsRegion();
825  else {
826    const StackFrameContext *STC = LC->getCurrentStackFrame();
827    assert(STC);
828    sReg = getStackLocalsRegion(STC);
829  }
830
831  return getSubRegion<CompoundLiteralRegion>(CL, sReg);
832}
833
834const ElementRegion*
835MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
836                                   const MemRegion* superRegion,
837                                   ASTContext &Ctx){
838
839  QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
840
841  llvm::FoldingSetNodeID ID;
842  ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
843
844  void *InsertPos;
845  MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
846  ElementRegion* R = cast_or_null<ElementRegion>(data);
847
848  if (!R) {
849    R = (ElementRegion*) A.Allocate<ElementRegion>();
850    new (R) ElementRegion(T, Idx, superRegion);
851    Regions.InsertNode(R, InsertPos);
852  }
853
854  return R;
855}
856
857const FunctionTextRegion *
858MemRegionManager::getFunctionTextRegion(const NamedDecl *FD) {
859  return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
860}
861
862const BlockTextRegion *
863MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
864                                     AnalysisDeclContext *AC) {
865  return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
866}
867
868
869/// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
870const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
871  return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
872}
873
874const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
875  return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
876}
877
878const FieldRegion*
879MemRegionManager::getFieldRegion(const FieldDecl *d,
880                                 const MemRegion* superRegion){
881  return getSubRegion<FieldRegion>(d, superRegion);
882}
883
884const ObjCIvarRegion*
885MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
886                                    const MemRegion* superRegion) {
887  return getSubRegion<ObjCIvarRegion>(d, superRegion);
888}
889
890const CXXTempObjectRegion*
891MemRegionManager::getCXXTempObjectRegion(Expr const *E,
892                                         LocationContext const *LC) {
893  const StackFrameContext *SFC = LC->getCurrentStackFrame();
894  assert(SFC);
895  return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
896}
897
898/// Checks whether \p BaseClass is a valid virtual or direct non-virtual base
899/// class of the type of \p Super.
900static bool isValidBaseClass(const CXXRecordDecl *BaseClass,
901                             const TypedValueRegion *Super,
902                             bool IsVirtual) {
903  BaseClass = BaseClass->getCanonicalDecl();
904
905  const CXXRecordDecl *Class = Super->getValueType()->getAsCXXRecordDecl();
906  if (!Class)
907    return true;
908
909  if (IsVirtual)
910    return Class->isVirtuallyDerivedFrom(BaseClass);
911
912  for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(),
913                                                E = Class->bases_end();
914       I != E; ++I) {
915    if (I->getType()->getAsCXXRecordDecl()->getCanonicalDecl() == BaseClass)
916      return true;
917  }
918
919  return false;
920}
921
922const CXXBaseObjectRegion *
923MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *RD,
924                                         const MemRegion *Super,
925                                         bool IsVirtual) {
926  if (isa<TypedValueRegion>(Super)) {
927    assert(isValidBaseClass(RD, dyn_cast<TypedValueRegion>(Super), IsVirtual));
928    (void)isValidBaseClass;
929
930    if (IsVirtual) {
931      // Virtual base regions should not be layered, since the layout rules
932      // are different.
933      while (const CXXBaseObjectRegion *Base =
934               dyn_cast<CXXBaseObjectRegion>(Super)) {
935        Super = Base->getSuperRegion();
936      }
937      assert(Super && !isa<MemSpaceRegion>(Super));
938    }
939  }
940
941  return getSubRegion<CXXBaseObjectRegion>(RD, IsVirtual, Super);
942}
943
944const CXXThisRegion*
945MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
946                                   const LocationContext *LC) {
947  const StackFrameContext *STC = LC->getCurrentStackFrame();
948  assert(STC);
949  const PointerType *PT = thisPointerTy->getAs<PointerType>();
950  assert(PT);
951  return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
952}
953
954const AllocaRegion*
955MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
956                                  const LocationContext *LC) {
957  const StackFrameContext *STC = LC->getCurrentStackFrame();
958  assert(STC);
959  return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
960}
961
962const MemSpaceRegion *MemRegion::getMemorySpace() const {
963  const MemRegion *R = this;
964  const SubRegion* SR = dyn_cast<SubRegion>(this);
965
966  while (SR) {
967    R = SR->getSuperRegion();
968    SR = dyn_cast<SubRegion>(R);
969  }
970
971  return dyn_cast<MemSpaceRegion>(R);
972}
973
974bool MemRegion::hasStackStorage() const {
975  return isa<StackSpaceRegion>(getMemorySpace());
976}
977
978bool MemRegion::hasStackNonParametersStorage() const {
979  return isa<StackLocalsSpaceRegion>(getMemorySpace());
980}
981
982bool MemRegion::hasStackParametersStorage() const {
983  return isa<StackArgumentsSpaceRegion>(getMemorySpace());
984}
985
986bool MemRegion::hasGlobalsOrParametersStorage() const {
987  const MemSpaceRegion *MS = getMemorySpace();
988  return isa<StackArgumentsSpaceRegion>(MS) ||
989         isa<GlobalsSpaceRegion>(MS);
990}
991
992// getBaseRegion strips away all elements and fields, and get the base region
993// of them.
994const MemRegion *MemRegion::getBaseRegion() const {
995  const MemRegion *R = this;
996  while (true) {
997    switch (R->getKind()) {
998      case MemRegion::ElementRegionKind:
999      case MemRegion::FieldRegionKind:
1000      case MemRegion::ObjCIvarRegionKind:
1001      case MemRegion::CXXBaseObjectRegionKind:
1002        R = cast<SubRegion>(R)->getSuperRegion();
1003        continue;
1004      default:
1005        break;
1006    }
1007    break;
1008  }
1009  return R;
1010}
1011
1012bool MemRegion::isSubRegionOf(const MemRegion *R) const {
1013  return false;
1014}
1015
1016//===----------------------------------------------------------------------===//
1017// View handling.
1018//===----------------------------------------------------------------------===//
1019
1020const MemRegion *MemRegion::StripCasts(bool StripBaseCasts) const {
1021  const MemRegion *R = this;
1022  while (true) {
1023    switch (R->getKind()) {
1024    case ElementRegionKind: {
1025      const ElementRegion *ER = cast<ElementRegion>(R);
1026      if (!ER->getIndex().isZeroConstant())
1027        return R;
1028      R = ER->getSuperRegion();
1029      break;
1030    }
1031    case CXXBaseObjectRegionKind:
1032      if (!StripBaseCasts)
1033        return R;
1034      R = cast<CXXBaseObjectRegion>(R)->getSuperRegion();
1035      break;
1036    default:
1037      return R;
1038    }
1039  }
1040}
1041
1042// FIXME: Merge with the implementation of the same method in Store.cpp
1043static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
1044  if (const RecordType *RT = Ty->getAs<RecordType>()) {
1045    const RecordDecl *D = RT->getDecl();
1046    if (!D->getDefinition())
1047      return false;
1048  }
1049
1050  return true;
1051}
1052
1053RegionRawOffset ElementRegion::getAsArrayOffset() const {
1054  CharUnits offset = CharUnits::Zero();
1055  const ElementRegion *ER = this;
1056  const MemRegion *superR = NULL;
1057  ASTContext &C = getContext();
1058
1059  // FIXME: Handle multi-dimensional arrays.
1060
1061  while (ER) {
1062    superR = ER->getSuperRegion();
1063
1064    // FIXME: generalize to symbolic offsets.
1065    SVal index = ER->getIndex();
1066    if (Optional<nonloc::ConcreteInt> CI = index.getAs<nonloc::ConcreteInt>()) {
1067      // Update the offset.
1068      int64_t i = CI->getValue().getSExtValue();
1069
1070      if (i != 0) {
1071        QualType elemType = ER->getElementType();
1072
1073        // If we are pointing to an incomplete type, go no further.
1074        if (!IsCompleteType(C, elemType)) {
1075          superR = ER;
1076          break;
1077        }
1078
1079        CharUnits size = C.getTypeSizeInChars(elemType);
1080        offset += (i * size);
1081      }
1082
1083      // Go to the next ElementRegion (if any).
1084      ER = dyn_cast<ElementRegion>(superR);
1085      continue;
1086    }
1087
1088    return NULL;
1089  }
1090
1091  assert(superR && "super region cannot be NULL");
1092  return RegionRawOffset(superR, offset);
1093}
1094
1095
1096/// Returns true if \p Base is an immediate base class of \p Child
1097static bool isImmediateBase(const CXXRecordDecl *Child,
1098                            const CXXRecordDecl *Base) {
1099  // Note that we do NOT canonicalize the base class here, because
1100  // ASTRecordLayout doesn't either. If that leads us down the wrong path,
1101  // so be it; at least we won't crash.
1102  for (CXXRecordDecl::base_class_const_iterator I = Child->bases_begin(),
1103                                                E = Child->bases_end();
1104       I != E; ++I) {
1105    if (I->getType()->getAsCXXRecordDecl() == Base)
1106      return true;
1107  }
1108
1109  return false;
1110}
1111
1112RegionOffset MemRegion::getAsOffset() const {
1113  const MemRegion *R = this;
1114  const MemRegion *SymbolicOffsetBase = 0;
1115  int64_t Offset = 0;
1116
1117  while (1) {
1118    switch (R->getKind()) {
1119    case GenericMemSpaceRegionKind:
1120    case StackLocalsSpaceRegionKind:
1121    case StackArgumentsSpaceRegionKind:
1122    case HeapSpaceRegionKind:
1123    case UnknownSpaceRegionKind:
1124    case StaticGlobalSpaceRegionKind:
1125    case GlobalInternalSpaceRegionKind:
1126    case GlobalSystemSpaceRegionKind:
1127    case GlobalImmutableSpaceRegionKind:
1128      // Stores can bind directly to a region space to set a default value.
1129      assert(Offset == 0 && !SymbolicOffsetBase);
1130      goto Finish;
1131
1132    case FunctionTextRegionKind:
1133    case BlockTextRegionKind:
1134    case BlockDataRegionKind:
1135      // These will never have bindings, but may end up having values requested
1136      // if the user does some strange casting.
1137      if (Offset != 0)
1138        SymbolicOffsetBase = R;
1139      goto Finish;
1140
1141    case SymbolicRegionKind:
1142    case AllocaRegionKind:
1143    case CompoundLiteralRegionKind:
1144    case CXXThisRegionKind:
1145    case StringRegionKind:
1146    case ObjCStringRegionKind:
1147    case VarRegionKind:
1148    case CXXTempObjectRegionKind:
1149      // Usual base regions.
1150      goto Finish;
1151
1152    case ObjCIvarRegionKind:
1153      // This is a little strange, but it's a compromise between
1154      // ObjCIvarRegions having unknown compile-time offsets (when using the
1155      // non-fragile runtime) and yet still being distinct, non-overlapping
1156      // regions. Thus we treat them as "like" base regions for the purposes
1157      // of computing offsets.
1158      goto Finish;
1159
1160    case CXXBaseObjectRegionKind: {
1161      const CXXBaseObjectRegion *BOR = cast<CXXBaseObjectRegion>(R);
1162      R = BOR->getSuperRegion();
1163
1164      QualType Ty;
1165      bool RootIsSymbolic = false;
1166      if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) {
1167        Ty = TVR->getDesugaredValueType(getContext());
1168      } else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
1169        // If our base region is symbolic, we don't know what type it really is.
1170        // Pretend the type of the symbol is the true dynamic type.
1171        // (This will at least be self-consistent for the life of the symbol.)
1172        Ty = SR->getSymbol()->getType()->getPointeeType();
1173        RootIsSymbolic = true;
1174      }
1175
1176      const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl();
1177      if (!Child) {
1178        // We cannot compute the offset of the base class.
1179        SymbolicOffsetBase = R;
1180      }
1181
1182      if (RootIsSymbolic) {
1183        // Base layers on symbolic regions may not be type-correct.
1184        // Double-check the inheritance here, and revert to a symbolic offset
1185        // if it's invalid (e.g. due to a reinterpret_cast).
1186        if (BOR->isVirtual()) {
1187          if (!Child->isVirtuallyDerivedFrom(BOR->getDecl()))
1188            SymbolicOffsetBase = R;
1189        } else {
1190          if (!isImmediateBase(Child, BOR->getDecl()))
1191            SymbolicOffsetBase = R;
1192        }
1193      }
1194
1195      // Don't bother calculating precise offsets if we already have a
1196      // symbolic offset somewhere in the chain.
1197      if (SymbolicOffsetBase)
1198        continue;
1199
1200      CharUnits BaseOffset;
1201      const ASTRecordLayout &Layout = getContext().getASTRecordLayout(Child);
1202      if (BOR->isVirtual())
1203        BaseOffset = Layout.getVBaseClassOffset(BOR->getDecl());
1204      else
1205        BaseOffset = Layout.getBaseClassOffset(BOR->getDecl());
1206
1207      // The base offset is in chars, not in bits.
1208      Offset += BaseOffset.getQuantity() * getContext().getCharWidth();
1209      break;
1210    }
1211    case ElementRegionKind: {
1212      const ElementRegion *ER = cast<ElementRegion>(R);
1213      R = ER->getSuperRegion();
1214
1215      QualType EleTy = ER->getValueType();
1216      if (!IsCompleteType(getContext(), EleTy)) {
1217        // We cannot compute the offset of the base class.
1218        SymbolicOffsetBase = R;
1219        continue;
1220      }
1221
1222      SVal Index = ER->getIndex();
1223      if (Optional<nonloc::ConcreteInt> CI =
1224              Index.getAs<nonloc::ConcreteInt>()) {
1225        // Don't bother calculating precise offsets if we already have a
1226        // symbolic offset somewhere in the chain.
1227        if (SymbolicOffsetBase)
1228          continue;
1229
1230        int64_t i = CI->getValue().getSExtValue();
1231        // This type size is in bits.
1232        Offset += i * getContext().getTypeSize(EleTy);
1233      } else {
1234        // We cannot compute offset for non-concrete index.
1235        SymbolicOffsetBase = R;
1236      }
1237      break;
1238    }
1239    case FieldRegionKind: {
1240      const FieldRegion *FR = cast<FieldRegion>(R);
1241      R = FR->getSuperRegion();
1242
1243      const RecordDecl *RD = FR->getDecl()->getParent();
1244      if (RD->isUnion() || !RD->isCompleteDefinition()) {
1245        // We cannot compute offset for incomplete type.
1246        // For unions, we could treat everything as offset 0, but we'd rather
1247        // treat each field as a symbolic offset so they aren't stored on top
1248        // of each other, since we depend on things in typed regions actually
1249        // matching their types.
1250        SymbolicOffsetBase = R;
1251      }
1252
1253      // Don't bother calculating precise offsets if we already have a
1254      // symbolic offset somewhere in the chain.
1255      if (SymbolicOffsetBase)
1256        continue;
1257
1258      // Get the field number.
1259      unsigned idx = 0;
1260      for (RecordDecl::field_iterator FI = RD->field_begin(),
1261             FE = RD->field_end(); FI != FE; ++FI, ++idx)
1262        if (FR->getDecl() == *FI)
1263          break;
1264
1265      const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
1266      // This is offset in bits.
1267      Offset += Layout.getFieldOffset(idx);
1268      break;
1269    }
1270    }
1271  }
1272
1273 Finish:
1274  if (SymbolicOffsetBase)
1275    return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic);
1276  return RegionOffset(R, Offset);
1277}
1278
1279//===----------------------------------------------------------------------===//
1280// BlockDataRegion
1281//===----------------------------------------------------------------------===//
1282
1283std::pair<const VarRegion *, const VarRegion *>
1284BlockDataRegion::getCaptureRegions(const VarDecl *VD) {
1285  MemRegionManager &MemMgr = *getMemRegionManager();
1286  const VarRegion *VR = 0;
1287  const VarRegion *OriginalVR = 0;
1288
1289  if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage()) {
1290    VR = MemMgr.getVarRegion(VD, this);
1291    OriginalVR = MemMgr.getVarRegion(VD, LC);
1292  }
1293  else {
1294    if (LC) {
1295      VR = MemMgr.getVarRegion(VD, LC);
1296      OriginalVR = VR;
1297    }
1298    else {
1299      VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
1300      OriginalVR = MemMgr.getVarRegion(VD, LC);
1301    }
1302  }
1303  return std::make_pair(VR, OriginalVR);
1304}
1305
1306void BlockDataRegion::LazyInitializeReferencedVars() {
1307  if (ReferencedVars)
1308    return;
1309
1310  AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1311  AnalysisDeclContext::referenced_decls_iterator I, E;
1312  llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
1313
1314  if (I == E) {
1315    ReferencedVars = (void*) 0x1;
1316    return;
1317  }
1318
1319  MemRegionManager &MemMgr = *getMemRegionManager();
1320  llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1321  BumpVectorContext BC(A);
1322
1323  typedef BumpVector<const MemRegion*> VarVec;
1324  VarVec *BV = (VarVec*) A.Allocate<VarVec>();
1325  new (BV) VarVec(BC, E - I);
1326  VarVec *BVOriginal = (VarVec*) A.Allocate<VarVec>();
1327  new (BVOriginal) VarVec(BC, E - I);
1328
1329  for ( ; I != E; ++I) {
1330    const VarRegion *VR = 0;
1331    const VarRegion *OriginalVR = 0;
1332    llvm::tie(VR, OriginalVR) = getCaptureRegions(*I);
1333    assert(VR);
1334    assert(OriginalVR);
1335    BV->push_back(VR, BC);
1336    BVOriginal->push_back(OriginalVR, BC);
1337  }
1338
1339  ReferencedVars = BV;
1340  OriginalVars = BVOriginal;
1341}
1342
1343BlockDataRegion::referenced_vars_iterator
1344BlockDataRegion::referenced_vars_begin() const {
1345  const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1346
1347  BumpVector<const MemRegion*> *Vec =
1348    static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1349
1350  if (Vec == (void*) 0x1)
1351    return BlockDataRegion::referenced_vars_iterator(0, 0);
1352
1353  BumpVector<const MemRegion*> *VecOriginal =
1354    static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1355
1356  return BlockDataRegion::referenced_vars_iterator(Vec->begin(),
1357                                                   VecOriginal->begin());
1358}
1359
1360BlockDataRegion::referenced_vars_iterator
1361BlockDataRegion::referenced_vars_end() const {
1362  const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1363
1364  BumpVector<const MemRegion*> *Vec =
1365    static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1366
1367  if (Vec == (void*) 0x1)
1368    return BlockDataRegion::referenced_vars_iterator(0, 0);
1369
1370  BumpVector<const MemRegion*> *VecOriginal =
1371    static_cast<BumpVector<const MemRegion*>*>(OriginalVars);
1372
1373  return BlockDataRegion::referenced_vars_iterator(Vec->end(),
1374                                                   VecOriginal->end());
1375}
1376
1377const VarRegion *BlockDataRegion::getOriginalRegion(const VarRegion *R) const {
1378  for (referenced_vars_iterator I = referenced_vars_begin(),
1379                                E = referenced_vars_end();
1380       I != E; ++I) {
1381    if (I.getCapturedRegion() == R)
1382      return I.getOriginalRegion();
1383  }
1384  return 0;
1385}
1386