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