lib/Checker/MemRegion.cpp

   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/Analysis/AnalysisContext.h"
  17 #include "clang/Checker/PathSensitive/MemRegion.h"
  18 #include "clang/AST/CharUnits.h"
  19 #include "clang/AST/StmtVisitor.h"
  20 #include "llvm/Support/raw_ostream.h"
  21
  22 using namespace clang;
  23
  24 //===----------------------------------------------------------------------===//
  25 // MemRegion Construction.
  26 //===----------------------------------------------------------------------===//
  27
  28 template<typename RegionTy> struct MemRegionManagerTrait;
  29
  30 template <typename RegionTy, typename A1>
  31 RegionTy* MemRegionManager::getRegion(const A1 a1) {
  32
  33   const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
  34   MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
  35
  36   llvm::FoldingSetNodeID ID;
  37   RegionTy::ProfileRegion(ID, a1, superRegion);
  38   void* InsertPos;
  39   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
  40                                                                    InsertPos));
  41
  42   if (!R) {
  43     R = (RegionTy*) A.Allocate<RegionTy>();
  44     new (R) RegionTy(a1, superRegion);
  45     Regions.InsertNode(R, InsertPos);
  46   }
  47
  48   return R;
  49 }
  50
  51 template <typename RegionTy, typename A1>
  52 RegionTy* MemRegionManager::getSubRegion(const A1 a1,
  53                                          const MemRegion *superRegion) {
  54   llvm::FoldingSetNodeID ID;
  55   RegionTy::ProfileRegion(ID, a1, superRegion);
  56   void* InsertPos;
  57   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
  58                                                                    InsertPos));
  59
  60   if (!R) {
  61     R = (RegionTy*) A.Allocate<RegionTy>();
  62     new (R) RegionTy(a1, superRegion);
  63     Regions.InsertNode(R, InsertPos);
  64   }
  65
  66   return R;
  67 }
  68
  69 template <typename RegionTy, typename A1, typename A2>
  70 RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
  71
  72   const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
  73   MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
  74
  75   llvm::FoldingSetNodeID ID;
  76   RegionTy::ProfileRegion(ID, a1, a2, superRegion);
  77   void* InsertPos;
  78   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
  79                                                                    InsertPos));
  80
  81   if (!R) {
  82     R = (RegionTy*) A.Allocate<RegionTy>();
  83     new (R) RegionTy(a1, a2, superRegion);
  84     Regions.InsertNode(R, InsertPos);
  85   }
  86
  87   return R;
  88 }
  89
  90 template <typename RegionTy, typename A1, typename A2>
  91 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
  92                                          const MemRegion *superRegion) {
  93
  94   llvm::FoldingSetNodeID ID;
  95   RegionTy::ProfileRegion(ID, a1, a2, superRegion);
  96   void* InsertPos;
  97   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
  98                                                                    InsertPos));
  99
 100   if (!R) {
 101     R = (RegionTy*) A.Allocate<RegionTy>();
 102     new (R) RegionTy(a1, a2, superRegion);
 103     Regions.InsertNode(R, InsertPos);
 104   }
 105
 106   return R;
 107 }
 108
 109 template <typename RegionTy, typename A1, typename A2, typename A3>
 110 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3,
 111                                          const MemRegion *superRegion) {
 112
 113   llvm::FoldingSetNodeID ID;
 114   RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
 115   void* InsertPos;
 116   RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
 117                                                                    InsertPos));
 118
 119   if (!R) {
 120     R = (RegionTy*) A.Allocate<RegionTy>();
 121     new (R) RegionTy(a1, a2, a3, superRegion);
 122     Regions.InsertNode(R, InsertPos);
 123   }
 124
 125   return R;
 126 }
 127
 128 //===----------------------------------------------------------------------===//
 129 // Object destruction.
 130 //===----------------------------------------------------------------------===//
 131
 132 MemRegion::~MemRegion() {}
 133
 134 MemRegionManager::~MemRegionManager() {
 135   // All regions and their data are BumpPtrAllocated.  No need to call
 136   // their destructors.
 137 }
 138
 139 //===----------------------------------------------------------------------===//
 140 // Basic methods.
 141 //===----------------------------------------------------------------------===//
 142
 143 bool SubRegion::isSubRegionOf(const MemRegion* R) const {
 144   const MemRegion* r = getSuperRegion();
 145   while (r != 0) {
 146     if (r == R)
 147       return true;
 148     if (const SubRegion* sr = dyn_cast<SubRegion>(r))
 149       r = sr->getSuperRegion();
 150     else
 151       break;
 152   }
 153   return false;
 154 }
 155
 156 MemRegionManager* SubRegion::getMemRegionManager() const {
 157   const SubRegion* r = this;
 158   do {
 159     const MemRegion *superRegion = r->getSuperRegion();
 160     if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
 161       r = sr;
 162       continue;
 163     }
 164     return superRegion->getMemRegionManager();
 165   } while (1);
 166 }
 167
 168 const StackFrameContext *VarRegion::getStackFrame() const {
 169   const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
 170   return SSR ? SSR->getStackFrame() : NULL;
 171 }
 172
 173 //===----------------------------------------------------------------------===//
 174 // FoldingSet profiling.
 175 //===----------------------------------------------------------------------===//
 176
 177 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 178   ID.AddInteger((unsigned)getKind());
 179 }
 180
 181 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 182   ID.AddInteger((unsigned)getKind());
 183   ID.AddPointer(getStackFrame());
 184 }
 185
 186 void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 187                                  const StringLiteral* Str,
 188                                  const MemRegion* superRegion) {
 189   ID.AddInteger((unsigned) StringRegionKind);
 190   ID.AddPointer(Str);
 191   ID.AddPointer(superRegion);
 192 }
 193
 194 void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 195                                  const Expr* Ex, unsigned cnt,
 196                                  const MemRegion *) {
 197   ID.AddInteger((unsigned) AllocaRegionKind);
 198   ID.AddPointer(Ex);
 199   ID.AddInteger(cnt);
 200 }
 201
 202 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 203   ProfileRegion(ID, Ex, Cnt, superRegion);
 204 }
 205
 206 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 207   CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
 208 }
 209
 210 void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 211                                           const CompoundLiteralExpr* CL,
 212                                           const MemRegion* superRegion) {
 213   ID.AddInteger((unsigned) CompoundLiteralRegionKind);
 214   ID.AddPointer(CL);
 215   ID.AddPointer(superRegion);
 216 }
 217
 218 void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 219                                   const PointerType *PT,
 220                                   const MemRegion *sRegion) {
 221   ID.AddInteger((unsigned) CXXThisRegionKind);
 222   ID.AddPointer(PT);
 223   ID.AddPointer(sRegion);
 224 }
 225
 226 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 227   CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
 228 }
 229
 230 void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D,
 231                                const MemRegion* superRegion, Kind k) {
 232   ID.AddInteger((unsigned) k);
 233   ID.AddPointer(D);
 234   ID.AddPointer(superRegion);
 235 }
 236
 237 void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 238   DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
 239 }
 240
 241 void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 242   VarRegion::ProfileRegion(ID, getDecl(), superRegion);
 243 }
 244
 245 void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
 246                                    const MemRegion *sreg) {
 247   ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind);
 248   ID.Add(sym);
 249   ID.AddPointer(sreg);
 250 }
 251
 252 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 253   SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
 254 }
 255
 256 void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 257                                   QualType ElementType, SVal Idx,
 258                                   const MemRegion* superRegion) {
 259   ID.AddInteger(MemRegion::ElementRegionKind);
 260   ID.Add(ElementType);
 261   ID.AddPointer(superRegion);
 262   Idx.Profile(ID);
 263 }
 264
 265 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 266   ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
 267 }
 268
 269 void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 270                                        const FunctionDecl *FD,
 271                                        const MemRegion*) {
 272   ID.AddInteger(MemRegion::FunctionTextRegionKind);
 273   ID.AddPointer(FD);
 274 }
 275
 276 void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 277   FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
 278 }
 279
 280 void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 281                                     const BlockDecl *BD, CanQualType,
 282                                     const AnalysisContext *AC,
 283                                     const MemRegion*) {
 284   ID.AddInteger(MemRegion::BlockTextRegionKind);
 285   ID.AddPointer(BD);
 286 }
 287
 288 void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 289   BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
 290 }
 291
 292 void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 293                                     const BlockTextRegion *BC,
 294                                     const LocationContext *LC,
 295                                     const MemRegion *sReg) {
 296   ID.AddInteger(MemRegion::BlockDataRegionKind);
 297   ID.AddPointer(BC);
 298   ID.AddPointer(LC);
 299   ID.AddPointer(sReg);
 300 }
 301
 302 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 303   BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
 304 }
 305
 306 void CXXObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 307                                     Expr const *Ex,
 308                                     const MemRegion *sReg) {
 309   ID.AddPointer(Ex);
 310   ID.AddPointer(sReg);
 311 }
 312
 313 void CXXObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 314   ProfileRegion(ID, Ex, getSuperRegion());
 315 }
 316
 317 //===----------------------------------------------------------------------===//
 318 // Region pretty-printing.
 319 //===----------------------------------------------------------------------===//
 320
 321 void MemRegion::dump() const {
 322   dumpToStream(llvm::errs());
 323 }
 324
 325 std::string MemRegion::getString() const {
 326   std::string s;
 327   llvm::raw_string_ostream os(s);
 328   dumpToStream(os);
 329   return os.str();
 330 }
 331
 332 void MemRegion::dumpToStream(llvm::raw_ostream& os) const {
 333   os << "<Unknown Region>";
 334 }
 335
 336 void AllocaRegion::dumpToStream(llvm::raw_ostream& os) const {
 337   os << "alloca{" << (void*) Ex << ',' << Cnt << '}';
 338 }
 339
 340 void FunctionTextRegion::dumpToStream(llvm::raw_ostream& os) const {
 341   os << "code{" << getDecl()->getDeclName().getAsString() << '}';
 342 }
 343
 344 void BlockTextRegion::dumpToStream(llvm::raw_ostream& os) const {
 345   os << "block_code{" << (void*) this << '}';
 346 }
 347
 348 void BlockDataRegion::dumpToStream(llvm::raw_ostream& os) const {
 349   os << "block_data{" << BC << '}';
 350 }
 351
 352
 353 void CompoundLiteralRegion::dumpToStream(llvm::raw_ostream& os) const {
 354   // FIXME: More elaborate pretty-printing.
 355   os << "{ " << (void*) CL <<  " }";
 356 }
 357
 358 void CXXThisRegion::dumpToStream(llvm::raw_ostream &os) const {
 359   os << "this";
 360 }
 361
 362 void ElementRegion::dumpToStream(llvm::raw_ostream& os) const {
 363   os << "element{" << superRegion << ','
 364      << Index << ',' << getElementType().getAsString() << '}';
 365 }
 366
 367 void FieldRegion::dumpToStream(llvm::raw_ostream& os) const {
 368   os << superRegion << "->" << getDecl()->getNameAsString();
 369 }
 370
 371 void ObjCIvarRegion::dumpToStream(llvm::raw_ostream& os) const {
 372   os << "ivar{" << superRegion << ',' << getDecl()->getNameAsString() << '}';
 373 }
 374
 375 void StringRegion::dumpToStream(llvm::raw_ostream& os) const {
 376   Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOptions()));
 377 }
 378
 379 void SymbolicRegion::dumpToStream(llvm::raw_ostream& os) const {
 380   os << "SymRegion{" << sym << '}';
 381 }
 382
 383 void VarRegion::dumpToStream(llvm::raw_ostream& os) const {
 384   os << cast<VarDecl>(D)->getNameAsString();
 385 }
 386
 387 void RegionRawOffset::dump() const {
 388   dumpToStream(llvm::errs());
 389 }
 390
 391 void RegionRawOffset::dumpToStream(llvm::raw_ostream& os) const {
 392   os << "raw_offset{" << getRegion() << ',' << getByteOffset() << '}';
 393 }
 394
 395 //===----------------------------------------------------------------------===//
 396 // MemRegionManager methods.
 397 //===----------------------------------------------------------------------===//
 398
 399 template <typename REG>
 400 const REG *MemRegionManager::LazyAllocate(REG*& region) {
 401   if (!region) {
 402     region = (REG*) A.Allocate<REG>();
 403     new (region) REG(this);
 404   }
 405
 406   return region;
 407 }
 408
 409 template <typename REG, typename ARG>
 410 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
 411   if (!region) {
 412     region = (REG*) A.Allocate<REG>();
 413     new (region) REG(this, a);
 414   }
 415
 416   return region;
 417 }
 418
 419 const StackLocalsSpaceRegion*
 420 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
 421   assert(STC);
 422   if (STC == cachedStackLocalsFrame)
 423     return cachedStackLocalsRegion;
 424   cachedStackLocalsFrame = STC;
 425   return LazyAllocate(cachedStackLocalsRegion, STC);
 426 }
 427
 428 const StackArgumentsSpaceRegion *
 429 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
 430   assert(STC);
 431   if (STC == cachedStackArgumentsFrame)
 432     return cachedStackArgumentsRegion;
 433
 434   cachedStackArgumentsFrame = STC;
 435   return LazyAllocate(cachedStackArgumentsRegion, STC);
 436 }
 437
 438 const GlobalsSpaceRegion *MemRegionManager::getGlobalsRegion() {
 439   return LazyAllocate(globals);
 440 }
 441
 442 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
 443   return LazyAllocate(heap);
 444 }
 445
 446 const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
 447   return LazyAllocate(unknown);
 448 }
 449
 450 const MemSpaceRegion *MemRegionManager::getCodeRegion() {
 451   return LazyAllocate(code);
 452 }
 453
 454 //===----------------------------------------------------------------------===//
 455 // Constructing regions.
 456 //===----------------------------------------------------------------------===//
 457
 458 const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str) {
 459   return getSubRegion<StringRegion>(Str, getGlobalsRegion());
 460 }
 461
 462 const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
 463                                                 const LocationContext *LC) {
 464   const MemRegion *sReg = 0;
 465
 466   if (D->hasLocalStorage()) {
 467     // FIXME: Once we implement scope handling, we will need to properly lookup
 468     // 'D' to the proper LocationContext.
 469     const DeclContext *DC = D->getDeclContext();
 470     const StackFrameContext *STC = LC->getStackFrameForDeclContext(DC);
 471
 472     if (!STC)
 473       sReg = getUnknownRegion();
 474     else {
 475       sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
 476             ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
 477             : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
 478     }
 479   }
 480   else {
 481     sReg = getGlobalsRegion();
 482   }
 483
 484   return getSubRegion<VarRegion>(D, sReg);
 485 }
 486
 487 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
 488                                                 const MemRegion *superR) {
 489   return getSubRegion<VarRegion>(D, superR);
 490 }
 491
 492 const BlockDataRegion *
 493 MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC,
 494                                      const LocationContext *LC) {
 495   const MemRegion *sReg = 0;
 496
 497   if (LC) {
 498     // FIXME: Once we implement scope handling, we want the parent region
 499     // to be the scope.
 500     const StackFrameContext *STC = LC->getCurrentStackFrame();
 501     assert(STC);
 502     sReg = getStackLocalsRegion(STC);
 503   }
 504   else {
 505     // We allow 'LC' to be NULL for cases where want BlockDataRegions
 506     // without context-sensitivity.
 507     sReg = getUnknownRegion();
 508   }
 509
 510   return getSubRegion<BlockDataRegion>(BC, LC, sReg);
 511 }
 512
 513 const CompoundLiteralRegion*
 514 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr* CL,
 515                                            const LocationContext *LC) {
 516
 517   const MemRegion *sReg = 0;
 518
 519   if (CL->isFileScope())
 520     sReg = getGlobalsRegion();
 521   else {
 522     const StackFrameContext *STC = LC->getCurrentStackFrame();
 523     assert(STC);
 524     sReg = getStackLocalsRegion(STC);
 525   }
 526
 527   return getSubRegion<CompoundLiteralRegion>(CL, sReg);
 528 }
 529
 530 const ElementRegion*
 531 MemRegionManager::getElementRegion(QualType elementType, SVal Idx,
 532                                    const MemRegion* superRegion,
 533                                    ASTContext& Ctx){
 534
 535   QualType T = Ctx.getCanonicalType(elementType);
 536
 537   llvm::FoldingSetNodeID ID;
 538   ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
 539
 540   void* InsertPos;
 541   MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
 542   ElementRegion* R = cast_or_null<ElementRegion>(data);
 543
 544   if (!R) {
 545     R = (ElementRegion*) A.Allocate<ElementRegion>();
 546     new (R) ElementRegion(T, Idx, superRegion);
 547     Regions.InsertNode(R, InsertPos);
 548   }
 549
 550   return R;
 551 }
 552
 553 const FunctionTextRegion *
 554 MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) {
 555   return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
 556 }
 557
 558 const BlockTextRegion *
 559 MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
 560                                      AnalysisContext *AC) {
 561   return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
 562 }
 563
 564
 565 /// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
 566 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
 567   return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
 568 }
 569
 570 const FieldRegion*
 571 MemRegionManager::getFieldRegion(const FieldDecl* d,
 572                                  const MemRegion* superRegion){
 573   return getSubRegion<FieldRegion>(d, superRegion);
 574 }
 575
 576 const ObjCIvarRegion*
 577 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl* d,
 578                                     const MemRegion* superRegion) {
 579   return getSubRegion<ObjCIvarRegion>(d, superRegion);
 580 }
 581
 582 const CXXObjectRegion*
 583 MemRegionManager::getCXXObjectRegion(Expr const *E,
 584                                      LocationContext const *LC) {
 585   const StackFrameContext *SFC = LC->getCurrentStackFrame();
 586   assert(SFC);
 587   return getSubRegion<CXXObjectRegion>(E, getStackLocalsRegion(SFC));
 588 }
 589
 590 const CXXThisRegion*
 591 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
 592                                    const LocationContext *LC) {
 593   const StackFrameContext *STC = LC->getCurrentStackFrame();
 594   assert(STC);
 595   const PointerType *PT = thisPointerTy->getAs<PointerType>();
 596   assert(PT);
 597   return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
 598 }
 599
 600 const AllocaRegion*
 601 MemRegionManager::getAllocaRegion(const Expr* E, unsigned cnt,
 602                                   const LocationContext *LC) {
 603   const StackFrameContext *STC = LC->getCurrentStackFrame();
 604   assert(STC);
 605   return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
 606 }
 607
 608 const MemSpaceRegion *MemRegion::getMemorySpace() const {
 609   const MemRegion *R = this;
 610   const SubRegion* SR = dyn_cast<SubRegion>(this);
 611
 612   while (SR) {
 613     R = SR->getSuperRegion();
 614     SR = dyn_cast<SubRegion>(R);
 615   }
 616
 617   return dyn_cast<MemSpaceRegion>(R);
 618 }
 619
 620 bool MemRegion::hasStackStorage() const {
 621   return isa<StackSpaceRegion>(getMemorySpace());
 622 }
 623
 624 bool MemRegion::hasStackNonParametersStorage() const {
 625   return isa<StackLocalsSpaceRegion>(getMemorySpace());
 626 }
 627
 628 bool MemRegion::hasStackParametersStorage() const {
 629   return isa<StackArgumentsSpaceRegion>(getMemorySpace());
 630 }
 631
 632 bool MemRegion::hasGlobalsOrParametersStorage() const {
 633   const MemSpaceRegion *MS = getMemorySpace();
 634   return isa<StackArgumentsSpaceRegion>(MS) ||
 635          isa<GlobalsSpaceRegion>(MS);
 636 }
 637
 638 // getBaseRegion strips away all elements and fields, and get the base region
 639 // of them.
 640 const MemRegion *MemRegion::getBaseRegion() const {
 641   const MemRegion *R = this;
 642   while (true) {
 643     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
 644       R = ER->getSuperRegion();
 645       continue;
 646     }
 647     if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
 648       R = FR->getSuperRegion();
 649       continue;
 650     }
 651     break;
 652   }
 653   return R;
 654 }
 655
 656 //===----------------------------------------------------------------------===//
 657 // View handling.
 658 //===----------------------------------------------------------------------===//
 659
 660 const MemRegion *MemRegion::StripCasts() const {
 661   const MemRegion *R = this;
 662   while (true) {
 663     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
 664       // FIXME: generalize.  Essentially we want to strip away ElementRegions
 665       // that were layered on a symbolic region because of casts.  We only
 666       // want to strip away ElementRegions, however, where the index is 0.
 667       SVal index = ER->getIndex();
 668       if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
 669         if (CI->getValue().getSExtValue() == 0) {
 670           R = ER->getSuperRegion();
 671           continue;
 672         }
 673       }
 674     }
 675     break;
 676   }
 677   return R;
 678 }
 679
 680 // FIXME: Merge with the implementation of the same method in Store.cpp
 681 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
 682   if (const RecordType *RT = Ty->getAs<RecordType>()) {
 683     const RecordDecl *D = RT->getDecl();
 684     if (!D->getDefinition())
 685       return false;
 686   }
 687
 688   return true;
 689 }
 690
 691 RegionRawOffset ElementRegion::getAsRawOffset() const {
 692   CharUnits offset = CharUnits::Zero();
 693   const ElementRegion *ER = this;
 694   const MemRegion *superR = NULL;
 695   ASTContext &C = getContext();
 696
 697   // FIXME: Handle multi-dimensional arrays.
 698
 699   while (ER) {
 700     superR = ER->getSuperRegion();
 701
 702     // FIXME: generalize to symbolic offsets.
 703     SVal index = ER->getIndex();
 704     if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
 705       // Update the offset.
 706       int64_t i = CI->getValue().getSExtValue();
 707
 708       if (i != 0) {
 709         QualType elemType = ER->getElementType();
 710
 711         // If we are pointing to an incomplete type, go no further.
 712         if (!IsCompleteType(C, elemType)) {
 713           superR = ER;
 714           break;
 715         }
 716
 717         CharUnits size = C.getTypeSizeInChars(elemType);
 718         offset += (i * size);
 719       }
 720
 721       // Go to the next ElementRegion (if any).
 722       ER = dyn_cast<ElementRegion>(superR);
 723       continue;
 724     }
 725
 726     return NULL;
 727   }
 728
 729   assert(superR && "super region cannot be NULL");
 730   return RegionRawOffset(superR, offset.getQuantity());
 731 }
 732
 733 //===----------------------------------------------------------------------===//
 734 // BlockDataRegion
 735 //===----------------------------------------------------------------------===//
 736
 737 void BlockDataRegion::LazyInitializeReferencedVars() {
 738   if (ReferencedVars)
 739     return;
 740
 741   AnalysisContext *AC = getCodeRegion()->getAnalysisContext();
 742   AnalysisContext::referenced_decls_iterator I, E;
 743   llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
 744
 745   if (I == E) {
 746     ReferencedVars = (void*) 0x1;
 747     return;
 748   }
 749
 750   MemRegionManager &MemMgr = *getMemRegionManager();
 751   llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
 752   BumpVectorContext BC(A);
 753
 754   typedef BumpVector<const MemRegion*> VarVec;
 755   VarVec *BV = (VarVec*) A.Allocate<VarVec>();
 756   new (BV) VarVec(BC, E - I);
 757
 758   for ( ; I != E; ++I) {
 759     const VarDecl *VD = *I;
 760     const VarRegion *VR = 0;
 761
 762     if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage())
 763       VR = MemMgr.getVarRegion(VD, this);
 764     else {
 765       if (LC)
 766         VR = MemMgr.getVarRegion(VD, LC);
 767       else {
 768         VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
 769       }
 770     }
 771
 772     assert(VR);
 773     BV->push_back(VR, BC);
 774   }
 775
 776   ReferencedVars = BV;
 777 }
 778
 779 BlockDataRegion::referenced_vars_iterator
 780 BlockDataRegion::referenced_vars_begin() const {
 781   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
 782
 783   BumpVector<const MemRegion*> *Vec =
 784     static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
 785
 786   return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ?
 787                                                    NULL : Vec->begin());
 788 }
 789
 790 BlockDataRegion::referenced_vars_iterator
 791 BlockDataRegion::referenced_vars_end() const {
 792   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
 793
 794   BumpVector<const MemRegion*> *Vec =
 795     static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
 796
 797   return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ?
 798                                                    NULL : Vec->end());
 799 }