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