Add the clang library to the repo (with some of my changes, too).

1 files changed, 1101 insertions, 0 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp
new file mode 100644
index 0000000..ed94c79
--- /dev/null
+++ b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp
@@ -0,0 +1,1101 @@
+//== MemRegion.cpp - Abstract memory regions for static analysis --*- C++ -*--//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines MemRegion and its subclasses.  MemRegion defines a
+//  partially-typed abstraction of memory useful for path-sensitive dataflow
+//  analyses.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/Analysis/Support/BumpVector.h"
+#include "clang/AST/CharUnits.h"
+#include "clang/AST/DeclObjC.h"
+#include "clang/AST/RecordLayout.h"
+#include "clang/Basic/SourceManager.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace clang;
+using namespace ento;
+
+//===----------------------------------------------------------------------===//
+// MemRegion Construction.
+//===----------------------------------------------------------------------===//
+
+template<typename RegionTy> struct MemRegionManagerTrait;
+
+template <typename RegionTy, typename A1>
+RegionTy* MemRegionManager::getRegion(const A1 a1) {
+
+  const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
+  MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
+
+  llvm::FoldingSetNodeID ID;
+  RegionTy::ProfileRegion(ID, a1, superRegion);
+  void *InsertPos;
+  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
+                                                                   InsertPos));
+
+  if (!R) {
+    R = (RegionTy*) A.Allocate<RegionTy>();
+    new (R) RegionTy(a1, superRegion);
+    Regions.InsertNode(R, InsertPos);
+  }
+
+  return R;
+}
+
+template <typename RegionTy, typename A1>
+RegionTy* MemRegionManager::getSubRegion(const A1 a1,
+                                         const MemRegion *superRegion) {
+  llvm::FoldingSetNodeID ID;
+  RegionTy::ProfileRegion(ID, a1, superRegion);
+  void *InsertPos;
+  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
+                                                                   InsertPos));
+
+  if (!R) {
+    R = (RegionTy*) A.Allocate<RegionTy>();
+    new (R) RegionTy(a1, superRegion);
+    Regions.InsertNode(R, InsertPos);
+  }
+
+  return R;
+}
+
+template <typename RegionTy, typename A1, typename A2>
+RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
+
+  const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
+  MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
+
+  llvm::FoldingSetNodeID ID;
+  RegionTy::ProfileRegion(ID, a1, a2, superRegion);
+  void *InsertPos;
+  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
+                                                                   InsertPos));
+
+  if (!R) {
+    R = (RegionTy*) A.Allocate<RegionTy>();
+    new (R) RegionTy(a1, a2, superRegion);
+    Regions.InsertNode(R, InsertPos);
+  }
+
+  return R;
+}
+
+template <typename RegionTy, typename A1, typename A2>
+RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
+                                         const MemRegion *superRegion) {
+
+  llvm::FoldingSetNodeID ID;
+  RegionTy::ProfileRegion(ID, a1, a2, superRegion);
+  void *InsertPos;
+  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
+                                                                   InsertPos));
+
+  if (!R) {
+    R = (RegionTy*) A.Allocate<RegionTy>();
+    new (R) RegionTy(a1, a2, superRegion);
+    Regions.InsertNode(R, InsertPos);
+  }
+
+  return R;
+}
+
+template <typename RegionTy, typename A1, typename A2, typename A3>
+RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3,
+                                         const MemRegion *superRegion) {
+
+  llvm::FoldingSetNodeID ID;
+  RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
+  void *InsertPos;
+  RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
+                                                                   InsertPos));
+
+  if (!R) {
+    R = (RegionTy*) A.Allocate<RegionTy>();
+    new (R) RegionTy(a1, a2, a3, superRegion);
+    Regions.InsertNode(R, InsertPos);
+  }
+
+  return R;
+}
+
+//===----------------------------------------------------------------------===//
+// Object destruction.
+//===----------------------------------------------------------------------===//
+
+MemRegion::~MemRegion() {}
+
+MemRegionManager::~MemRegionManager() {
+  // All regions and their data are BumpPtrAllocated.  No need to call
+  // their destructors.
+}
+
+//===----------------------------------------------------------------------===//
+// Basic methods.
+//===----------------------------------------------------------------------===//
+
+bool SubRegion::isSubRegionOf(const MemRegion* R) const {
+  const MemRegion* r = getSuperRegion();
+  while (r != 0) {
+    if (r == R)
+      return true;
+    if (const SubRegion* sr = dyn_cast<SubRegion>(r))
+      r = sr->getSuperRegion();
+    else
+      break;
+  }
+  return false;
+}
+
+MemRegionManager* SubRegion::getMemRegionManager() const {
+  const SubRegion* r = this;
+  do {
+    const MemRegion *superRegion = r->getSuperRegion();
+    if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
+      r = sr;
+      continue;
+    }
+    return superRegion->getMemRegionManager();
+  } while (1);
+}
+
+const StackFrameContext *VarRegion::getStackFrame() const {
+  const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
+  return SSR ? SSR->getStackFrame() : NULL;
+}
+
+//===----------------------------------------------------------------------===//
+// Region extents.
+//===----------------------------------------------------------------------===//
+
+DefinedOrUnknownSVal DeclRegion::getExtent(SValBuilder &svalBuilder) const {
+  ASTContext &Ctx = svalBuilder.getContext();
+  QualType T = getDesugaredValueType(Ctx);
+
+  if (isa<VariableArrayType>(T))
+    return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
+  if (isa<IncompleteArrayType>(T))
+    return UnknownVal();
+
+  CharUnits size = Ctx.getTypeSizeInChars(T);
+  QualType sizeTy = svalBuilder.getArrayIndexType();
+  return svalBuilder.makeIntVal(size.getQuantity(), sizeTy);
+}
+
+DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const {
+  DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder);
+
+  // A zero-length array at the end of a struct often stands for dynamically-
+  // allocated extra memory.
+  if (Extent.isZeroConstant()) {
+    QualType T = getDesugaredValueType(svalBuilder.getContext());
+
+    if (isa<ConstantArrayType>(T))
+      return UnknownVal();
+  }
+
+  return Extent;
+}
+
+DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
+  return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
+}
+
+DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
+  return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
+}
+
+DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
+  return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
+                                svalBuilder.getArrayIndexType());
+}
+
+ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg)
+  : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
+
+const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
+  return cast<ObjCIvarDecl>(D);
+}
+
+QualType ObjCIvarRegion::getValueType() const {
+  return getDecl()->getType();
+}
+
+QualType CXXBaseObjectRegion::getValueType() const {
+  return QualType(decl->getTypeForDecl(), 0);
+}
+
+//===----------------------------------------------------------------------===//
+// FoldingSet profiling.
+//===----------------------------------------------------------------------===//
+
+void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  ID.AddInteger((unsigned)getKind());
+}
+
+void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
+  ID.AddInteger((unsigned)getKind());
+  ID.AddPointer(getStackFrame());
+}
+
+void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
+  ID.AddInteger((unsigned)getKind());
+  ID.AddPointer(getCodeRegion());
+}
+
+void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                 const StringLiteral* Str,
+                                 const MemRegion* superRegion) {
+  ID.AddInteger((unsigned) StringRegionKind);
+  ID.AddPointer(Str);
+  ID.AddPointer(superRegion);
+}
+
+void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                     const ObjCStringLiteral* Str,
+                                     const MemRegion* superRegion) {
+  ID.AddInteger((unsigned) ObjCStringRegionKind);
+  ID.AddPointer(Str);
+  ID.AddPointer(superRegion);
+}
+
+void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                 const Expr *Ex, unsigned cnt,
+                                 const MemRegion *) {
+  ID.AddInteger((unsigned) AllocaRegionKind);
+  ID.AddPointer(Ex);
+  ID.AddInteger(cnt);
+}
+
+void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  ProfileRegion(ID, Ex, Cnt, superRegion);
+}
+
+void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
+}
+
+void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                          const CompoundLiteralExpr *CL,
+                                          const MemRegion* superRegion) {
+  ID.AddInteger((unsigned) CompoundLiteralRegionKind);
+  ID.AddPointer(CL);
+  ID.AddPointer(superRegion);
+}
+
+void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
+                                  const PointerType *PT,
+                                  const MemRegion *sRegion) {
+  ID.AddInteger((unsigned) CXXThisRegionKind);
+  ID.AddPointer(PT);
+  ID.AddPointer(sRegion);
+}
+
+void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
+  CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
+}
+
+void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                   const ObjCIvarDecl *ivd,
+                                   const MemRegion* superRegion) {
+  DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
+}
+
+void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D,
+                               const MemRegion* superRegion, Kind k) {
+  ID.AddInteger((unsigned) k);
+  ID.AddPointer(D);
+  ID.AddPointer(superRegion);
+}
+
+void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
+}
+
+void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
+  VarRegion::ProfileRegion(ID, getDecl(), superRegion);
+}
+
+void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
+                                   const MemRegion *sreg) {
+  ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind);
+  ID.Add(sym);
+  ID.AddPointer(sreg);
+}
+
+void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
+}
+
+void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                  QualType ElementType, SVal Idx,
+                                  const MemRegion* superRegion) {
+  ID.AddInteger(MemRegion::ElementRegionKind);
+  ID.Add(ElementType);
+  ID.AddPointer(superRegion);
+  Idx.Profile(ID);
+}
+
+void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
+}
+
+void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                       const FunctionDecl *FD,
+                                       const MemRegion*) {
+  ID.AddInteger(MemRegion::FunctionTextRegionKind);
+  ID.AddPointer(FD);
+}
+
+void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
+}
+
+void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                    const BlockDecl *BD, CanQualType,
+                                    const AnalysisDeclContext *AC,
+                                    const MemRegion*) {
+  ID.AddInteger(MemRegion::BlockTextRegionKind);
+  ID.AddPointer(BD);
+}
+
+void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
+}
+
+void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
+                                    const BlockTextRegion *BC,
+                                    const LocationContext *LC,
+                                    const MemRegion *sReg) {
+  ID.AddInteger(MemRegion::BlockDataRegionKind);
+  ID.AddPointer(BC);
+  ID.AddPointer(LC);
+  ID.AddPointer(sReg);
+}
+
+void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
+  BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
+}
+
+void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
+                                        Expr const *Ex,
+                                        const MemRegion *sReg) {
+  ID.AddPointer(Ex);
+  ID.AddPointer(sReg);
+}
+
+void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
+  ProfileRegion(ID, Ex, getSuperRegion());
+}
+
+void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
+                                        const CXXRecordDecl *decl,
+                                        const MemRegion *sReg) {
+  ID.AddPointer(decl);
+  ID.AddPointer(sReg);
+}
+
+void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
+  ProfileRegion(ID, decl, superRegion);
+}
+
+//===----------------------------------------------------------------------===//
+// Region anchors.
+//===----------------------------------------------------------------------===//
+
+void GlobalsSpaceRegion::anchor() { }
+void HeapSpaceRegion::anchor() { }
+void UnknownSpaceRegion::anchor() { }
+void StackLocalsSpaceRegion::anchor() { }
+void StackArgumentsSpaceRegion::anchor() { }
+void TypedRegion::anchor() { }
+void TypedValueRegion::anchor() { }
+void CodeTextRegion::anchor() { }
+void SubRegion::anchor() { }
+
+//===----------------------------------------------------------------------===//
+// Region pretty-printing.
+//===----------------------------------------------------------------------===//
+
+void MemRegion::dump() const {
+  dumpToStream(llvm::errs());
+}
+
+std::string MemRegion::getString() const {
+  std::string s;
+  llvm::raw_string_ostream os(s);
+  dumpToStream(os);
+  return os.str();
+}
+
+void MemRegion::dumpToStream(raw_ostream &os) const {
+  os << "<Unknown Region>";
+}
+
+void AllocaRegion::dumpToStream(raw_ostream &os) const {
+  os << "alloca{" << (void*) Ex << ',' << Cnt << '}';
+}
+
+void FunctionTextRegion::dumpToStream(raw_ostream &os) const {
+  os << "code{" << getDecl()->getDeclName().getAsString() << '}';
+}
+
+void BlockTextRegion::dumpToStream(raw_ostream &os) const {
+  os << "block_code{" << (void*) this << '}';
+}
+
+void BlockDataRegion::dumpToStream(raw_ostream &os) const {
+  os << "block_data{" << BC << '}';
+}
+
+void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
+  // FIXME: More elaborate pretty-printing.
+  os << "{ " << (void*) CL <<  " }";
+}
+
+void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
+  os << "temp_object{" << getValueType().getAsString() << ','
+     << (void*) Ex << '}';
+}
+
+void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
+  os << "base " << decl->getName();
+}
+
+void CXXThisRegion::dumpToStream(raw_ostream &os) const {
+  os << "this";
+}
+
+void ElementRegion::dumpToStream(raw_ostream &os) const {
+  os << "element{" << superRegion << ','
+     << Index << ',' << getElementType().getAsString() << '}';
+}
+
+void FieldRegion::dumpToStream(raw_ostream &os) const {
+  os << superRegion << "->" << *getDecl();
+}
+
+void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
+  os << "ivar{" << superRegion << ',' << *getDecl() << '}';
+}
+
+void StringRegion::dumpToStream(raw_ostream &os) const {
+  Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
+}
+
+void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
+  Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
+}
+
+void SymbolicRegion::dumpToStream(raw_ostream &os) const {
+  os << "SymRegion{" << sym << '}';
+}
+
+void VarRegion::dumpToStream(raw_ostream &os) const {
+  os << *cast<VarDecl>(D);
+}
+
+void RegionRawOffset::dump() const {
+  dumpToStream(llvm::errs());
+}
+
+void RegionRawOffset::dumpToStream(raw_ostream &os) const {
+  os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
+}
+
+void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
+  os << "StaticGlobalsMemSpace{" << CR << '}';
+}
+
+void NonStaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
+  os << "NonStaticGlobalSpaceRegion";
+}
+
+void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
+  os << "GlobalInternalSpaceRegion";
+}
+
+void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
+  os << "GlobalSystemSpaceRegion";
+}
+
+void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
+  os << "GlobalImmutableSpaceRegion";
+}
+
+void MemRegion::dumpPretty(raw_ostream &os) const {
+  return;
+}
+
+void VarRegion::dumpPretty(raw_ostream &os) const {
+  os << getDecl()->getName();
+}
+
+void FieldRegion::dumpPretty(raw_ostream &os) const {
+  superRegion->dumpPretty(os);
+  os << "->" << getDecl();
+}
+
+//===----------------------------------------------------------------------===//
+// MemRegionManager methods.
+//===----------------------------------------------------------------------===//
+
+template <typename REG>
+const REG *MemRegionManager::LazyAllocate(REG*& region) {
+  if (!region) {
+    region = (REG*) A.Allocate<REG>();
+    new (region) REG(this);
+  }
+
+  return region;
+}
+
+template <typename REG, typename ARG>
+const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
+  if (!region) {
+    region = (REG*) A.Allocate<REG>();
+    new (region) REG(this, a);
+  }
+
+  return region;
+}
+
+const StackLocalsSpaceRegion*
+MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
+  assert(STC);
+  StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
+
+  if (R)
+    return R;
+
+  R = A.Allocate<StackLocalsSpaceRegion>();
+  new (R) StackLocalsSpaceRegion(this, STC);
+  return R;
+}
+
+const StackArgumentsSpaceRegion *
+MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
+  assert(STC);
+  StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
+
+  if (R)
+    return R;
+
+  R = A.Allocate<StackArgumentsSpaceRegion>();
+  new (R) StackArgumentsSpaceRegion(this, STC);
+  return R;
+}
+
+const GlobalsSpaceRegion
+*MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
+                                    const CodeTextRegion *CR) {
+  if (!CR) {
+    if (K == MemRegion::GlobalSystemSpaceRegionKind)
+      return LazyAllocate(SystemGlobals);
+    if (K == MemRegion::GlobalImmutableSpaceRegionKind)
+      return LazyAllocate(ImmutableGlobals);
+    assert(K == MemRegion::GlobalInternalSpaceRegionKind);
+    return LazyAllocate(InternalGlobals);
+  }
+
+  assert(K == MemRegion::StaticGlobalSpaceRegionKind);
+  StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
+  if (R)
+    return R;
+
+  R = A.Allocate<StaticGlobalSpaceRegion>();
+  new (R) StaticGlobalSpaceRegion(this, CR);
+  return R;
+}
+
+const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
+  return LazyAllocate(heap);
+}
+
+const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
+  return LazyAllocate(unknown);
+}
+
+const MemSpaceRegion *MemRegionManager::getCodeRegion() {
+  return LazyAllocate(code);
+}
+
+//===----------------------------------------------------------------------===//
+// Constructing regions.
+//===----------------------------------------------------------------------===//
+const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
+  return getSubRegion<StringRegion>(Str, getGlobalsRegion());
+}
+
+const ObjCStringRegion *
+MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){
+  return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion());
+}
+
+const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
+                                                const LocationContext *LC) {
+  const MemRegion *sReg = 0;
+
+  if (D->hasGlobalStorage() && !D->isStaticLocal()) {
+
+    // First handle the globals defined in system headers.
+    if (C.getSourceManager().isInSystemHeader(D->getLocation())) {
+      // Whitelist the system globals which often DO GET modified, assume the
+      // rest are immutable.
+      if (D->getName().find("errno") != StringRef::npos)
+        sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
+      else
+        sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
+
+    // Treat other globals as GlobalInternal unless they are constants.
+    } else {
+      QualType GQT = D->getType();
+      const Type *GT = GQT.getTypePtrOrNull();
+      // TODO: We could walk the complex types here and see if everything is
+      // constified.
+      if (GT && GQT.isConstQualified() && GT->isArithmeticType())
+        sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
+      else
+        sReg = getGlobalsRegion();
+    }
+  
+  // Finally handle static locals.  
+  } else {
+    // FIXME: Once we implement scope handling, we will need to properly lookup
+    // 'D' to the proper LocationContext.
+    const DeclContext *DC = D->getDeclContext();
+    const StackFrameContext *STC = LC->getStackFrameForDeclContext(DC);
+
+    if (!STC)
+      sReg = getUnknownRegion();
+    else {
+      if (D->hasLocalStorage()) {
+        sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
+               ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
+               : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
+      }
+      else {
+        assert(D->isStaticLocal());
+        const Decl *D = STC->getDecl();
+        if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
+          sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
+                                  getFunctionTextRegion(FD));
+        else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
+          const BlockTextRegion *BTR =
+            getBlockTextRegion(BD,
+                     C.getCanonicalType(BD->getSignatureAsWritten()->getType()),
+                     STC->getAnalysisDeclContext());
+          sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
+                                  BTR);
+        }
+        else {
+          // FIXME: For ObjC-methods, we need a new CodeTextRegion.  For now
+          // just use the main global memspace.
+          sReg = getGlobalsRegion();
+        }
+      }
+    }
+  }
+
+  return getSubRegion<VarRegion>(D, sReg);
+}
+
+const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
+                                                const MemRegion *superR) {
+  return getSubRegion<VarRegion>(D, superR);
+}
+
+const BlockDataRegion *
+MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC,
+                                     const LocationContext *LC) {
+  const MemRegion *sReg = 0;
+  const BlockDecl *BD = BC->getDecl();
+  if (!BD->hasCaptures()) {
+    // This handles 'static' blocks.
+    sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
+  }
+  else {
+    if (LC) {
+      // FIXME: Once we implement scope handling, we want the parent region
+      // to be the scope.
+      const StackFrameContext *STC = LC->getCurrentStackFrame();
+      assert(STC);
+      sReg = getStackLocalsRegion(STC);
+    }
+    else {
+      // We allow 'LC' to be NULL for cases where want BlockDataRegions
+      // without context-sensitivity.
+      sReg = getUnknownRegion();
+    }
+  }
+
+  return getSubRegion<BlockDataRegion>(BC, LC, sReg);
+}
+
+const CompoundLiteralRegion*
+MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
+                                           const LocationContext *LC) {
+
+  const MemRegion *sReg = 0;
+
+  if (CL->isFileScope())
+    sReg = getGlobalsRegion();
+  else {
+    const StackFrameContext *STC = LC->getCurrentStackFrame();
+    assert(STC);
+    sReg = getStackLocalsRegion(STC);
+  }
+
+  return getSubRegion<CompoundLiteralRegion>(CL, sReg);
+}
+
+const ElementRegion*
+MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
+                                   const MemRegion* superRegion,
+                                   ASTContext &Ctx){
+
+  QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
+
+  llvm::FoldingSetNodeID ID;
+  ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
+
+  void *InsertPos;
+  MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
+  ElementRegion* R = cast_or_null<ElementRegion>(data);
+
+  if (!R) {
+    R = (ElementRegion*) A.Allocate<ElementRegion>();
+    new (R) ElementRegion(T, Idx, superRegion);
+    Regions.InsertNode(R, InsertPos);
+  }
+
+  return R;
+}
+
+const FunctionTextRegion *
+MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) {
+  return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
+}
+
+const BlockTextRegion *
+MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
+                                     AnalysisDeclContext *AC) {
+  return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
+}
+
+
+/// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
+const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
+  return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
+}
+
+const FieldRegion*
+MemRegionManager::getFieldRegion(const FieldDecl *d,
+                                 const MemRegion* superRegion){
+  return getSubRegion<FieldRegion>(d, superRegion);
+}
+
+const ObjCIvarRegion*
+MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
+                                    const MemRegion* superRegion) {
+  return getSubRegion<ObjCIvarRegion>(d, superRegion);
+}
+
+const CXXTempObjectRegion*
+MemRegionManager::getCXXTempObjectRegion(Expr const *E,
+                                         LocationContext const *LC) {
+  const StackFrameContext *SFC = LC->getCurrentStackFrame();
+  assert(SFC);
+  return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
+}
+
+const CXXBaseObjectRegion *
+MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *decl,
+                                         const MemRegion *superRegion) {
+  return getSubRegion<CXXBaseObjectRegion>(decl, superRegion);
+}
+
+const CXXThisRegion*
+MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
+                                   const LocationContext *LC) {
+  const StackFrameContext *STC = LC->getCurrentStackFrame();
+  assert(STC);
+  const PointerType *PT = thisPointerTy->getAs<PointerType>();
+  assert(PT);
+  return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
+}
+
+const AllocaRegion*
+MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
+                                  const LocationContext *LC) {
+  const StackFrameContext *STC = LC->getCurrentStackFrame();
+  assert(STC);
+  return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
+}
+
+const MemSpaceRegion *MemRegion::getMemorySpace() const {
+  const MemRegion *R = this;
+  const SubRegion* SR = dyn_cast<SubRegion>(this);
+
+  while (SR) {
+    R = SR->getSuperRegion();
+    SR = dyn_cast<SubRegion>(R);
+  }
+
+  return dyn_cast<MemSpaceRegion>(R);
+}
+
+bool MemRegion::hasStackStorage() const {
+  return isa<StackSpaceRegion>(getMemorySpace());
+}
+
+bool MemRegion::hasStackNonParametersStorage() const {
+  return isa<StackLocalsSpaceRegion>(getMemorySpace());
+}
+
+bool MemRegion::hasStackParametersStorage() const {
+  return isa<StackArgumentsSpaceRegion>(getMemorySpace());
+}
+
+bool MemRegion::hasGlobalsOrParametersStorage() const {
+  const MemSpaceRegion *MS = getMemorySpace();
+  return isa<StackArgumentsSpaceRegion>(MS) ||
+         isa<GlobalsSpaceRegion>(MS);
+}
+
+// getBaseRegion strips away all elements and fields, and get the base region
+// of them.
+const MemRegion *MemRegion::getBaseRegion() const {
+  const MemRegion *R = this;
+  while (true) {
+    switch (R->getKind()) {
+      case MemRegion::ElementRegionKind:
+      case MemRegion::FieldRegionKind:
+      case MemRegion::ObjCIvarRegionKind:
+      case MemRegion::CXXBaseObjectRegionKind:
+        R = cast<SubRegion>(R)->getSuperRegion();
+        continue;
+      default:
+        break;
+    }
+    break;
+  }
+  return R;
+}
+
+//===----------------------------------------------------------------------===//
+// View handling.
+//===----------------------------------------------------------------------===//
+
+const MemRegion *MemRegion::StripCasts() const {
+  const MemRegion *R = this;
+  while (true) {
+    if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
+      // FIXME: generalize.  Essentially we want to strip away ElementRegions
+      // that were layered on a symbolic region because of casts.  We only
+      // want to strip away ElementRegions, however, where the index is 0.
+      SVal index = ER->getIndex();
+      if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
+        if (CI->getValue().getSExtValue() == 0) {
+          R = ER->getSuperRegion();
+          continue;
+        }
+      }
+    }
+    break;
+  }
+  return R;
+}
+
+// FIXME: Merge with the implementation of the same method in Store.cpp
+static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
+  if (const RecordType *RT = Ty->getAs<RecordType>()) {
+    const RecordDecl *D = RT->getDecl();
+    if (!D->getDefinition())
+      return false;
+  }
+
+  return true;
+}
+
+RegionRawOffset ElementRegion::getAsArrayOffset() const {
+  CharUnits offset = CharUnits::Zero();
+  const ElementRegion *ER = this;
+  const MemRegion *superR = NULL;
+  ASTContext &C = getContext();
+
+  // FIXME: Handle multi-dimensional arrays.
+
+  while (ER) {
+    superR = ER->getSuperRegion();
+
+    // FIXME: generalize to symbolic offsets.
+    SVal index = ER->getIndex();
+    if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
+      // Update the offset.
+      int64_t i = CI->getValue().getSExtValue();
+
+      if (i != 0) {
+        QualType elemType = ER->getElementType();
+
+        // If we are pointing to an incomplete type, go no further.
+        if (!IsCompleteType(C, elemType)) {
+          superR = ER;
+          break;
+        }
+
+        CharUnits size = C.getTypeSizeInChars(elemType);
+        offset += (i * size);
+      }
+
+      // Go to the next ElementRegion (if any).
+      ER = dyn_cast<ElementRegion>(superR);
+      continue;
+    }
+
+    return NULL;
+  }
+
+  assert(superR && "super region cannot be NULL");
+  return RegionRawOffset(superR, offset);
+}
+
+RegionOffset MemRegion::getAsOffset() const {
+  const MemRegion *R = this;
+  int64_t Offset = 0;
+
+  while (1) {
+    switch (R->getKind()) {
+    default:
+      return RegionOffset(0);
+    case SymbolicRegionKind:
+    case AllocaRegionKind:
+    case CompoundLiteralRegionKind:
+    case CXXThisRegionKind:
+    case StringRegionKind:
+    case VarRegionKind:
+    case CXXTempObjectRegionKind:
+      goto Finish;
+    case ElementRegionKind: {
+      const ElementRegion *ER = cast<ElementRegion>(R);
+      QualType EleTy = ER->getValueType();
+
+      if (!IsCompleteType(getContext(), EleTy))
+        return RegionOffset(0);
+
+      SVal Index = ER->getIndex();
+      if (const nonloc::ConcreteInt *CI=dyn_cast<nonloc::ConcreteInt>(&Index)) {
+        int64_t i = CI->getValue().getSExtValue();
+        CharUnits Size = getContext().getTypeSizeInChars(EleTy);
+        Offset += i * Size.getQuantity() * 8;
+      } else {
+        // We cannot compute offset for non-concrete index.
+        return RegionOffset(0);
+      }
+      R = ER->getSuperRegion();
+      break;
+    }
+    case FieldRegionKind: {
+      const FieldRegion *FR = cast<FieldRegion>(R);
+      const RecordDecl *RD = FR->getDecl()->getParent();
+      if (!RD->isCompleteDefinition())
+        // We cannot compute offset for incomplete type.
+        return RegionOffset(0);
+      // Get the field number.
+      unsigned idx = 0;
+      for (RecordDecl::field_iterator FI = RD->field_begin(), 
+             FE = RD->field_end(); FI != FE; ++FI, ++idx)
+        if (FR->getDecl() == *FI)
+          break;
+
+      const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
+      // This is offset in bits.
+      Offset += Layout.getFieldOffset(idx);
+      R = FR->getSuperRegion();
+      break;
+    }
+    }
+  }
+
+ Finish:
+  return RegionOffset(R, Offset);
+}
+
+//===----------------------------------------------------------------------===//
+// BlockDataRegion
+//===----------------------------------------------------------------------===//
+
+void BlockDataRegion::LazyInitializeReferencedVars() {
+  if (ReferencedVars)
+    return;
+
+  AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
+  AnalysisDeclContext::referenced_decls_iterator I, E;
+  llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
+
+  if (I == E) {
+    ReferencedVars = (void*) 0x1;
+    return;
+  }
+
+  MemRegionManager &MemMgr = *getMemRegionManager();
+  llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
+  BumpVectorContext BC(A);
+
+  typedef BumpVector<const MemRegion*> VarVec;
+  VarVec *BV = (VarVec*) A.Allocate<VarVec>();
+  new (BV) VarVec(BC, E - I);
+
+  for ( ; I != E; ++I) {
+    const VarDecl *VD = *I;
+    const VarRegion *VR = 0;
+
+    if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage())
+      VR = MemMgr.getVarRegion(VD, this);
+    else {
+      if (LC)
+        VR = MemMgr.getVarRegion(VD, LC);
+      else {
+        VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
+      }
+    }
+
+    assert(VR);
+    BV->push_back(VR, BC);
+  }
+
+  ReferencedVars = BV;
+}
+
+BlockDataRegion::referenced_vars_iterator
+BlockDataRegion::referenced_vars_begin() const {
+  const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
+
+  BumpVector<const MemRegion*> *Vec =
+    static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
+
+  return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ?
+                                                   NULL : Vec->begin());
+}
+
+BlockDataRegion::referenced_vars_iterator
+BlockDataRegion::referenced_vars_end() const {
+  const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
+
+  BumpVector<const MemRegion*> *Vec =
+    static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
+
+  return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ?
+                                                   NULL : Vec->end());
+}