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