clang/lib/StaticAnalyzer/Core/MemRegion.cpp

   1 //===- MemRegion.cpp - Abstract memory regions for static analysis --------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines MemRegion and its subclasses.  MemRegion defines a
  10 //  partially-typed abstraction of memory useful for path-sensitive dataflow
  11 //  analyses.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  16 #include "clang/AST/ASTContext.h"
  17 #include "clang/AST/Attr.h"
  18 #include "clang/AST/CharUnits.h"
  19 #include "clang/AST/Decl.h"
  20 #include "clang/AST/DeclCXX.h"
  21 #include "clang/AST/DeclObjC.h"
  22 #include "clang/AST/Expr.h"
  23 #include "clang/AST/PrettyPrinter.h"
  24 #include "clang/AST/RecordLayout.h"
  25 #include "clang/AST/Type.h"
  26 #include "clang/Analysis/AnalysisDeclContext.h"
  27 #include "clang/Analysis/Support/BumpVector.h"
  28 #include "clang/Basic/IdentifierTable.h"
  29 #include "clang/Basic/LLVM.h"
  30 #include "clang/Basic/SourceManager.h"
  31 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
  32 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
  33 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  34 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  35 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
  36 #include "llvm/ADT/APInt.h"
  37 #include "llvm/ADT/FoldingSet.h"
  38 #include "llvm/ADT/PointerUnion.h"
  39 #include "llvm/ADT/SmallString.h"
  40 #include "llvm/ADT/StringRef.h"
  41 #include "llvm/ADT/Twine.h"
  42 #include "llvm/ADT/iterator_range.h"
  43 #include "llvm/Support/Allocator.h"
  44 #include "llvm/Support/Casting.h"
  45 #include "llvm/Support/CheckedArithmetic.h"
  46 #include "llvm/Support/Compiler.h"
  47 #include "llvm/Support/Debug.h"
  48 #include "llvm/Support/ErrorHandling.h"
  49 #include "llvm/Support/raw_ostream.h"
  50 #include <cassert>
  51 #include <cstdint>
  52 #include <functional>
  53 #include <iterator>
  54 #include <optional>
  55 #include <string>
  56 #include <tuple>
  57 #include <utility>
  58
  59 using namespace clang;
  60 using namespace ento;
  61
  62 #define DEBUG_TYPE "MemRegion"
  63
  64 //===----------------------------------------------------------------------===//
  65 // MemRegion Construction.
  66 //===----------------------------------------------------------------------===//
  67
  68 [[maybe_unused]] static bool isAReferenceTypedValueRegion(const MemRegion *R) {
  69   const auto *TyReg = llvm::dyn_cast<TypedValueRegion>(R);
  70   return TyReg && TyReg->getValueType()->isReferenceType();
  71 }
  72
  73 template <typename RegionTy, typename SuperTy, typename Arg1Ty>
  74 RegionTy* MemRegionManager::getSubRegion(const Arg1Ty arg1,
  75                                          const SuperTy *superRegion) {
  76   llvm::FoldingSetNodeID ID;
  77   RegionTy::ProfileRegion(ID, arg1, superRegion);
  78   void *InsertPos;
  79   auto *R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos));
  80
  81   if (!R) {
  82     R = new (A) RegionTy(arg1, superRegion);
  83     Regions.InsertNode(R, InsertPos);
  84     assert(!isAReferenceTypedValueRegion(superRegion));
  85   }
  86
  87   return R;
  88 }
  89
  90 template <typename RegionTy, typename SuperTy, typename Arg1Ty, typename Arg2Ty>
  91 RegionTy* MemRegionManager::getSubRegion(const Arg1Ty arg1, const Arg2Ty arg2,
  92                                          const SuperTy *superRegion) {
  93   llvm::FoldingSetNodeID ID;
  94   RegionTy::ProfileRegion(ID, arg1, arg2, superRegion);
  95   void *InsertPos;
  96   auto *R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos));
  97
  98   if (!R) {
  99     R = new (A) RegionTy(arg1, arg2, superRegion);
 100     Regions.InsertNode(R, InsertPos);
 101     assert(!isAReferenceTypedValueRegion(superRegion));
 102   }
 103
 104   return R;
 105 }
 106
 107 template <typename RegionTy, typename SuperTy,
 108           typename Arg1Ty, typename Arg2Ty, typename Arg3Ty>
 109 RegionTy* MemRegionManager::getSubRegion(const Arg1Ty arg1, const Arg2Ty arg2,
 110                                          const Arg3Ty arg3,
 111                                          const SuperTy *superRegion) {
 112   llvm::FoldingSetNodeID ID;
 113   RegionTy::ProfileRegion(ID, arg1, arg2, arg3, superRegion);
 114   void *InsertPos;
 115   auto *R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID, InsertPos));
 116
 117   if (!R) {
 118     R = new (A) RegionTy(arg1, arg2, arg3, superRegion);
 119     Regions.InsertNode(R, InsertPos);
 120     assert(!isAReferenceTypedValueRegion(superRegion));
 121   }
 122
 123   return R;
 124 }
 125
 126 //===----------------------------------------------------------------------===//
 127 // Object destruction.
 128 //===----------------------------------------------------------------------===//
 129
 130 MemRegion::~MemRegion() = default;
 131
 132 // All regions and their data are BumpPtrAllocated.  No need to call their
 133 // destructors.
 134 MemRegionManager::~MemRegionManager() = default;
 135
 136 //===----------------------------------------------------------------------===//
 137 // Basic methods.
 138 //===----------------------------------------------------------------------===//
 139
 140 bool SubRegion::isSubRegionOf(const MemRegion* R) const {
 141   const MemRegion* r = this;
 142   do {
 143     if (r == R)
 144       return true;
 145     if (const auto *sr = dyn_cast<SubRegion>(r))
 146       r = sr->getSuperRegion();
 147     else
 148       break;
 149   } while (r != nullptr);
 150   return false;
 151 }
 152
 153 MemRegionManager &SubRegion::getMemRegionManager() const {
 154   const SubRegion* r = this;
 155   do {
 156     const MemRegion *superRegion = r->getSuperRegion();
 157     if (const auto *sr = dyn_cast<SubRegion>(superRegion)) {
 158       r = sr;
 159       continue;
 160     }
 161     return superRegion->getMemRegionManager();
 162   } while (true);
 163 }
 164
 165 const StackFrameContext *VarRegion::getStackFrame() const {
 166   const auto *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
 167   return SSR ? SSR->getStackFrame() : nullptr;
 168 }
 169
 170 const StackFrameContext *
 171 CXXLifetimeExtendedObjectRegion::getStackFrame() const {
 172   const auto *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
 173   return SSR ? SSR->getStackFrame() : nullptr;
 174 }
 175
 176 const StackFrameContext *CXXTempObjectRegion::getStackFrame() const {
 177   assert(isa<StackSpaceRegion>(getMemorySpace()) &&
 178          "A temporary object can only be allocated on the stack");
 179   return cast<StackSpaceRegion>(getMemorySpace())->getStackFrame();
 180 }
 181
 182 ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const SubRegion *sReg)
 183     : DeclRegion(sReg, ObjCIvarRegionKind), IVD(ivd) {
 184   assert(IVD);
 185 }
 186
 187 const ObjCIvarDecl *ObjCIvarRegion::getDecl() const { return IVD; }
 188
 189 QualType ObjCIvarRegion::getValueType() const {
 190   return getDecl()->getType();
 191 }
 192
 193 QualType CXXBaseObjectRegion::getValueType() const {
 194   return QualType(getDecl()->getTypeForDecl(), 0);
 195 }
 196
 197 QualType CXXDerivedObjectRegion::getValueType() const {
 198   return QualType(getDecl()->getTypeForDecl(), 0);
 199 }
 200
 201 QualType ParamVarRegion::getValueType() const {
 202   assert(getDecl() &&
 203          "`ParamVarRegion` support functions without `Decl` not implemented"
 204          " yet.");
 205   return getDecl()->getType();
 206 }
 207
 208 const ParmVarDecl *ParamVarRegion::getDecl() const {
 209   const Decl *D = getStackFrame()->getDecl();
 210
 211   if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
 212     assert(Index < FD->param_size());
 213     return FD->parameters()[Index];
 214   } else if (const auto *BD = dyn_cast<BlockDecl>(D)) {
 215     assert(Index < BD->param_size());
 216     return BD->parameters()[Index];
 217   } else if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
 218     assert(Index < MD->param_size());
 219     return MD->parameters()[Index];
 220   } else if (const auto *CD = dyn_cast<CXXConstructorDecl>(D)) {
 221     assert(Index < CD->param_size());
 222     return CD->parameters()[Index];
 223   } else {
 224     llvm_unreachable("Unexpected Decl kind!");
 225   }
 226 }
 227
 228 //===----------------------------------------------------------------------===//
 229 // FoldingSet profiling.
 230 //===----------------------------------------------------------------------===//
 231
 232 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 233   ID.AddInteger(static_cast<unsigned>(getKind()));
 234 }
 235
 236 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 237   ID.AddInteger(static_cast<unsigned>(getKind()));
 238   ID.AddPointer(getStackFrame());
 239 }
 240
 241 void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 242   ID.AddInteger(static_cast<unsigned>(getKind()));
 243   ID.AddPointer(getCodeRegion());
 244 }
 245
 246 void StringRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 247                                  const StringLiteral *Str,
 248                                  const MemRegion *superRegion) {
 249   ID.AddInteger(static_cast<unsigned>(StringRegionKind));
 250   ID.AddPointer(Str);
 251   ID.AddPointer(superRegion);
 252 }
 253
 254 void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 255                                      const ObjCStringLiteral *Str,
 256                                      const MemRegion *superRegion) {
 257   ID.AddInteger(static_cast<unsigned>(ObjCStringRegionKind));
 258   ID.AddPointer(Str);
 259   ID.AddPointer(superRegion);
 260 }
 261
 262 void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 263                                  const Expr *Ex, unsigned cnt,
 264                                  const MemRegion *superRegion) {
 265   ID.AddInteger(static_cast<unsigned>(AllocaRegionKind));
 266   ID.AddPointer(Ex);
 267   ID.AddInteger(cnt);
 268   ID.AddPointer(superRegion);
 269 }
 270
 271 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 272   ProfileRegion(ID, Ex, Cnt, superRegion);
 273 }
 274
 275 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 276   CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
 277 }
 278
 279 void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 280                                           const CompoundLiteralExpr *CL,
 281                                           const MemRegion* superRegion) {
 282   ID.AddInteger(static_cast<unsigned>(CompoundLiteralRegionKind));
 283   ID.AddPointer(CL);
 284   ID.AddPointer(superRegion);
 285 }
 286
 287 void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 288                                   const PointerType *PT,
 289                                   const MemRegion *sRegion) {
 290   ID.AddInteger(static_cast<unsigned>(CXXThisRegionKind));
 291   ID.AddPointer(PT);
 292   ID.AddPointer(sRegion);
 293 }
 294
 295 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 296   CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
 297 }
 298
 299 void FieldRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 300   ProfileRegion(ID, getDecl(), superRegion);
 301 }
 302
 303 void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 304                                    const ObjCIvarDecl *ivd,
 305                                    const MemRegion* superRegion) {
 306   ID.AddInteger(static_cast<unsigned>(ObjCIvarRegionKind));
 307   ID.AddPointer(ivd);
 308   ID.AddPointer(superRegion);
 309 }
 310
 311 void ObjCIvarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 312   ProfileRegion(ID, getDecl(), superRegion);
 313 }
 314
 315 void NonParamVarRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 316                                       const VarDecl *VD,
 317                                       const MemRegion *superRegion) {
 318   ID.AddInteger(static_cast<unsigned>(NonParamVarRegionKind));
 319   ID.AddPointer(VD);
 320   ID.AddPointer(superRegion);
 321 }
 322
 323 void NonParamVarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 324   ProfileRegion(ID, getDecl(), superRegion);
 325 }
 326
 327 void ParamVarRegion::ProfileRegion(llvm::FoldingSetNodeID &ID, const Expr *OE,
 328                                    unsigned Idx, const MemRegion *SReg) {
 329   ID.AddInteger(static_cast<unsigned>(ParamVarRegionKind));
 330   ID.AddPointer(OE);
 331   ID.AddInteger(Idx);
 332   ID.AddPointer(SReg);
 333 }
 334
 335 void ParamVarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 336   ProfileRegion(ID, getOriginExpr(), getIndex(), superRegion);
 337 }
 338
 339 void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
 340                                    const MemRegion *sreg) {
 341   ID.AddInteger(static_cast<unsigned>(MemRegion::SymbolicRegionKind));
 342   ID.Add(sym);
 343   ID.AddPointer(sreg);
 344 }
 345
 346 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 347   SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
 348 }
 349
 350 void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 351                                   QualType ElementType, SVal Idx,
 352                                   const MemRegion* superRegion) {
 353   ID.AddInteger(MemRegion::ElementRegionKind);
 354   ID.Add(ElementType);
 355   ID.AddPointer(superRegion);
 356   Idx.Profile(ID);
 357 }
 358
 359 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 360   ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
 361 }
 362
 363 void FunctionCodeRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 364                                        const NamedDecl *FD,
 365                                        const MemRegion*) {
 366   ID.AddInteger(MemRegion::FunctionCodeRegionKind);
 367   ID.AddPointer(FD);
 368 }
 369
 370 void FunctionCodeRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 371   FunctionCodeRegion::ProfileRegion(ID, FD, superRegion);
 372 }
 373
 374 void BlockCodeRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 375                                     const BlockDecl *BD, CanQualType,
 376                                     const AnalysisDeclContext *AC,
 377                                     const MemRegion*) {
 378   ID.AddInteger(MemRegion::BlockCodeRegionKind);
 379   ID.AddPointer(BD);
 380 }
 381
 382 void BlockCodeRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 383   BlockCodeRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
 384 }
 385
 386 void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
 387                                     const BlockCodeRegion *BC,
 388                                     const LocationContext *LC,
 389                                     unsigned BlkCount,
 390                                     const MemRegion *sReg) {
 391   ID.AddInteger(MemRegion::BlockDataRegionKind);
 392   ID.AddPointer(BC);
 393   ID.AddPointer(LC);
 394   ID.AddInteger(BlkCount);
 395   ID.AddPointer(sReg);
 396 }
 397
 398 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
 399   BlockDataRegion::ProfileRegion(ID, BC, LC, BlockCount, getSuperRegion());
 400 }
 401
 402 void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 403                                         Expr const *Ex,
 404                                         const MemRegion *sReg) {
 405   ID.AddPointer(Ex);
 406   ID.AddPointer(sReg);
 407 }
 408
 409 void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 410   ProfileRegion(ID, Ex, getSuperRegion());
 411 }
 412
 413 void CXXLifetimeExtendedObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 414                                                     const Expr *E,
 415                                                     const ValueDecl *D,
 416                                                     const MemRegion *sReg) {
 417   ID.AddPointer(E);
 418   ID.AddPointer(D);
 419   ID.AddPointer(sReg);
 420 }
 421
 422 void CXXLifetimeExtendedObjectRegion::Profile(
 423     llvm::FoldingSetNodeID &ID) const {
 424   ProfileRegion(ID, Ex, ExD, getSuperRegion());
 425 }
 426
 427 void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 428                                         const CXXRecordDecl *RD,
 429                                         bool IsVirtual,
 430                                         const MemRegion *SReg) {
 431   ID.AddPointer(RD);
 432   ID.AddBoolean(IsVirtual);
 433   ID.AddPointer(SReg);
 434 }
 435
 436 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 437   ProfileRegion(ID, getDecl(), isVirtual(), superRegion);
 438 }
 439
 440 void CXXDerivedObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
 441                                            const CXXRecordDecl *RD,
 442                                            const MemRegion *SReg) {
 443   ID.AddPointer(RD);
 444   ID.AddPointer(SReg);
 445 }
 446
 447 void CXXDerivedObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
 448   ProfileRegion(ID, getDecl(), superRegion);
 449 }
 450
 451 //===----------------------------------------------------------------------===//
 452 // Region anchors.
 453 //===----------------------------------------------------------------------===//
 454
 455 void GlobalsSpaceRegion::anchor() {}
 456
 457 void NonStaticGlobalSpaceRegion::anchor() {}
 458
 459 void StackSpaceRegion::anchor() {}
 460
 461 void TypedRegion::anchor() {}
 462
 463 void TypedValueRegion::anchor() {}
 464
 465 void CodeTextRegion::anchor() {}
 466
 467 void SubRegion::anchor() {}
 468
 469 //===----------------------------------------------------------------------===//
 470 // Region pretty-printing.
 471 //===----------------------------------------------------------------------===//
 472
 473 LLVM_DUMP_METHOD void MemRegion::dump() const {
 474   dumpToStream(llvm::errs());
 475 }
 476
 477 std::string MemRegion::getString() const {
 478   std::string s;
 479   llvm::raw_string_ostream os(s);
 480   dumpToStream(os);
 481   return s;
 482 }
 483
 484 void MemRegion::dumpToStream(raw_ostream &os) const {
 485   os << "<Unknown Region>";
 486 }
 487
 488 void AllocaRegion::dumpToStream(raw_ostream &os) const {
 489   os << "alloca{S" << Ex->getID(getContext()) << ',' << Cnt << '}';
 490 }
 491
 492 void FunctionCodeRegion::dumpToStream(raw_ostream &os) const {
 493   os << "code{" << getDecl()->getDeclName().getAsString() << '}';
 494 }
 495
 496 void BlockCodeRegion::dumpToStream(raw_ostream &os) const {
 497   os << "block_code{" << static_cast<const void *>(this) << '}';
 498 }
 499
 500 void BlockDataRegion::dumpToStream(raw_ostream &os) const {
 501   os << "block_data{" << BC;
 502   os << "; ";
 503   for (auto Var : referenced_vars())
 504     os << "(" << Var.getCapturedRegion() << "<-" << Var.getOriginalRegion()
 505        << ") ";
 506   os << '}';
 507 }
 508
 509 void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
 510   // FIXME: More elaborate pretty-printing.
 511   os << "{ S" << CL->getID(getContext()) <<  " }";
 512 }
 513
 514 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
 515   os << "temp_object{" << getValueType() << ", "
 516      << "S" << Ex->getID(getContext()) << '}';
 517 }
 518
 519 void CXXLifetimeExtendedObjectRegion::dumpToStream(raw_ostream &os) const {
 520   os << "lifetime_extended_object{" << getValueType() << ", ";
 521   if (const IdentifierInfo *ID = ExD->getIdentifier())
 522     os << ID->getName();
 523   else
 524     os << "D" << ExD->getID();
 525   os << ", "
 526      << "S" << Ex->getID(getContext()) << '}';
 527 }
 528
 529 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
 530   os << "Base{" << superRegion << ',' << getDecl()->getName() << '}';
 531 }
 532
 533 void CXXDerivedObjectRegion::dumpToStream(raw_ostream &os) const {
 534   os << "Derived{" << superRegion << ',' << getDecl()->getName() << '}';
 535 }
 536
 537 void CXXThisRegion::dumpToStream(raw_ostream &os) const {
 538   os << "this";
 539 }
 540
 541 void ElementRegion::dumpToStream(raw_ostream &os) const {
 542   os << "Element{" << superRegion << ',' << Index << ',' << getElementType()
 543      << '}';
 544 }
 545
 546 void FieldRegion::dumpToStream(raw_ostream &os) const {
 547   os << superRegion << "." << *getDecl();
 548 }
 549
 550 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
 551   os << "Ivar{" << superRegion << ',' << *getDecl() << '}';
 552 }
 553
 554 void StringRegion::dumpToStream(raw_ostream &os) const {
 555   assert(Str != nullptr && "Expecting non-null StringLiteral");
 556   Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts()));
 557 }
 558
 559 void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
 560   assert(Str != nullptr && "Expecting non-null ObjCStringLiteral");
 561   Str->printPretty(os, nullptr, PrintingPolicy(getContext().getLangOpts()));
 562 }
 563
 564 void SymbolicRegion::dumpToStream(raw_ostream &os) const {
 565   if (isa<HeapSpaceRegion>(getSuperRegion()))
 566     os << "Heap";
 567   os << "SymRegion{" << sym << '}';
 568 }
 569
 570 void NonParamVarRegion::dumpToStream(raw_ostream &os) const {
 571   if (const IdentifierInfo *ID = VD->getIdentifier())
 572     os << ID->getName();
 573   else
 574     os << "NonParamVarRegion{D" << VD->getID() << '}';
 575 }
 576
 577 LLVM_DUMP_METHOD void RegionRawOffset::dump() const {
 578   dumpToStream(llvm::errs());
 579 }
 580
 581 void RegionRawOffset::dumpToStream(raw_ostream &os) const {
 582   os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
 583 }
 584
 585 void CodeSpaceRegion::dumpToStream(raw_ostream &os) const {
 586   os << "CodeSpaceRegion";
 587 }
 588
 589 void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
 590   os << "StaticGlobalsMemSpace{" << CR << '}';
 591 }
 592
 593 void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
 594   os << "GlobalInternalSpaceRegion";
 595 }
 596
 597 void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
 598   os << "GlobalSystemSpaceRegion";
 599 }
 600
 601 void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
 602   os << "GlobalImmutableSpaceRegion";
 603 }
 604
 605 void HeapSpaceRegion::dumpToStream(raw_ostream &os) const {
 606   os << "HeapSpaceRegion";
 607 }
 608
 609 void UnknownSpaceRegion::dumpToStream(raw_ostream &os) const {
 610   os << "UnknownSpaceRegion";
 611 }
 612
 613 void StackArgumentsSpaceRegion::dumpToStream(raw_ostream &os) const {
 614   os << "StackArgumentsSpaceRegion";
 615 }
 616
 617 void StackLocalsSpaceRegion::dumpToStream(raw_ostream &os) const {
 618   os << "StackLocalsSpaceRegion";
 619 }
 620
 621 void ParamVarRegion::dumpToStream(raw_ostream &os) const {
 622   const ParmVarDecl *PVD = getDecl();
 623   assert(PVD &&
 624          "`ParamVarRegion` support functions without `Decl` not implemented"
 625          " yet.");
 626   if (const IdentifierInfo *ID = PVD->getIdentifier()) {
 627     os << ID->getName();
 628   } else {
 629     os << "ParamVarRegion{P" << PVD->getID() << '}';
 630   }
 631 }
 632
 633 bool MemRegion::canPrintPretty() const {
 634   return canPrintPrettyAsExpr();
 635 }
 636
 637 bool MemRegion::canPrintPrettyAsExpr() const {
 638   return false;
 639 }
 640
 641 StringRef MemRegion::getKindStr() const {
 642   switch (getKind()) {
 643 #define REGION(Id, Parent)                                                     \
 644   case Id##Kind:                                                               \
 645     return #Id;
 646 #include "clang/StaticAnalyzer/Core/PathSensitive/Regions.def"
 647 #undef REGION
 648   }
 649   llvm_unreachable("Unkown kind!");
 650 }
 651
 652 void MemRegion::printPretty(raw_ostream &os) const {
 653   assert(canPrintPretty() && "This region cannot be printed pretty.");
 654   os << "'";
 655   printPrettyAsExpr(os);
 656   os << "'";
 657 }
 658
 659 void MemRegion::printPrettyAsExpr(raw_ostream &) const {
 660   llvm_unreachable("This region cannot be printed pretty.");
 661 }
 662
 663 bool NonParamVarRegion::canPrintPrettyAsExpr() const { return true; }
 664
 665 void NonParamVarRegion::printPrettyAsExpr(raw_ostream &os) const {
 666   os << getDecl()->getName();
 667 }
 668
 669 bool ParamVarRegion::canPrintPrettyAsExpr() const { return true; }
 670
 671 void ParamVarRegion::printPrettyAsExpr(raw_ostream &os) const {
 672   assert(getDecl() &&
 673          "`ParamVarRegion` support functions without `Decl` not implemented"
 674          " yet.");
 675   os << getDecl()->getName();
 676 }
 677
 678 bool ObjCIvarRegion::canPrintPrettyAsExpr() const {
 679   return true;
 680 }
 681
 682 void ObjCIvarRegion::printPrettyAsExpr(raw_ostream &os) const {
 683   os << getDecl()->getName();
 684 }
 685
 686 bool FieldRegion::canPrintPretty() const {
 687   return true;
 688 }
 689
 690 bool FieldRegion::canPrintPrettyAsExpr() const {
 691   return superRegion->canPrintPrettyAsExpr();
 692 }
 693
 694 void FieldRegion::printPrettyAsExpr(raw_ostream &os) const {
 695   assert(canPrintPrettyAsExpr());
 696   superRegion->printPrettyAsExpr(os);
 697   os << "." << getDecl()->getName();
 698 }
 699
 700 void FieldRegion::printPretty(raw_ostream &os) const {
 701   if (canPrintPrettyAsExpr()) {
 702     os << "\'";
 703     printPrettyAsExpr(os);
 704     os << "'";
 705   } else {
 706     os << "field " << "\'" << getDecl()->getName() << "'";
 707   }
 708 }
 709
 710 bool CXXBaseObjectRegion::canPrintPrettyAsExpr() const {
 711   return superRegion->canPrintPrettyAsExpr();
 712 }
 713
 714 void CXXBaseObjectRegion::printPrettyAsExpr(raw_ostream &os) const {
 715   superRegion->printPrettyAsExpr(os);
 716 }
 717
 718 bool CXXDerivedObjectRegion::canPrintPrettyAsExpr() const {
 719   return superRegion->canPrintPrettyAsExpr();
 720 }
 721
 722 void CXXDerivedObjectRegion::printPrettyAsExpr(raw_ostream &os) const {
 723   superRegion->printPrettyAsExpr(os);
 724 }
 725
 726 std::string MemRegion::getDescriptiveName(bool UseQuotes) const {
 727   std::string VariableName;
 728   std::string ArrayIndices;
 729   const MemRegion *R = this;
 730   SmallString<50> buf;
 731   llvm::raw_svector_ostream os(buf);
 732
 733   // Enclose subject with single quotes if needed.
 734   auto QuoteIfNeeded = [UseQuotes](const Twine &Subject) -> std::string {
 735     if (UseQuotes)
 736       return ("'" + Subject + "'").str();
 737     return Subject.str();
 738   };
 739
 740   // Obtain array indices to add them to the variable name.
 741   const ElementRegion *ER = nullptr;
 742   while ((ER = R->getAs<ElementRegion>())) {
 743     // Index is a ConcreteInt.
 744     if (auto CI = ER->getIndex().getAs<nonloc::ConcreteInt>()) {
 745       llvm::SmallString<2> Idx;
 746       CI->getValue().toString(Idx);
 747       ArrayIndices = (llvm::Twine("[") + Idx.str() + "]" + ArrayIndices).str();
 748     }
 749     // Index is symbolic, but may have a descriptive name.
 750     else {
 751       auto SI = ER->getIndex().getAs<nonloc::SymbolVal>();
 752       if (!SI)
 753         return "";
 754
 755       const MemRegion *OR = SI->getAsSymbol()->getOriginRegion();
 756       if (!OR)
 757         return "";
 758
 759       std::string Idx = OR->getDescriptiveName(false);
 760       if (Idx.empty())
 761         return "";
 762
 763       ArrayIndices = (llvm::Twine("[") + Idx + "]" + ArrayIndices).str();
 764     }
 765     R = ER->getSuperRegion();
 766   }
 767
 768   // Get variable name.
 769   if (R) {
 770     // MemRegion can be pretty printed.
 771     if (R->canPrintPrettyAsExpr()) {
 772       R->printPrettyAsExpr(os);
 773       return QuoteIfNeeded(llvm::Twine(os.str()) + ArrayIndices);
 774     }
 775
 776     // FieldRegion may have ElementRegion as SuperRegion.
 777     if (const auto *FR = R->getAs<FieldRegion>()) {
 778       std::string Super = FR->getSuperRegion()->getDescriptiveName(false);
 779       if (Super.empty())
 780         return "";
 781       return QuoteIfNeeded(Super + "." + FR->getDecl()->getName());
 782     }
 783   }
 784
 785   return VariableName;
 786 }
 787
 788 SourceRange MemRegion::sourceRange() const {
 789   // Check for more specific regions first.
 790   if (auto *FR = dyn_cast<FieldRegion>(this)) {
 791     return FR->getDecl()->getSourceRange();
 792   }
 793
 794   if (auto *VR = dyn_cast<VarRegion>(this->getBaseRegion())) {
 795     return VR->getDecl()->getSourceRange();
 796   }
 797
 798   // Return invalid source range (can be checked by client).
 799   return {};
 800 }
 801
 802 //===----------------------------------------------------------------------===//
 803 // MemRegionManager methods.
 804 //===----------------------------------------------------------------------===//
 805
 806 DefinedOrUnknownSVal MemRegionManager::getStaticSize(const MemRegion *MR,
 807                                                      SValBuilder &SVB) const {
 808   const auto *SR = cast<SubRegion>(MR);
 809   SymbolManager &SymMgr = SVB.getSymbolManager();
 810
 811   switch (SR->getKind()) {
 812   case MemRegion::AllocaRegionKind:
 813   case MemRegion::SymbolicRegionKind:
 814     return nonloc::SymbolVal(SymMgr.getExtentSymbol(SR));
 815   case MemRegion::StringRegionKind:
 816     return SVB.makeIntVal(
 817         cast<StringRegion>(SR)->getStringLiteral()->getByteLength() + 1,
 818         SVB.getArrayIndexType());
 819   case MemRegion::CompoundLiteralRegionKind:
 820   case MemRegion::CXXBaseObjectRegionKind:
 821   case MemRegion::CXXDerivedObjectRegionKind:
 822   case MemRegion::CXXTempObjectRegionKind:
 823   case MemRegion::CXXLifetimeExtendedObjectRegionKind:
 824   case MemRegion::CXXThisRegionKind:
 825   case MemRegion::ObjCIvarRegionKind:
 826   case MemRegion::NonParamVarRegionKind:
 827   case MemRegion::ParamVarRegionKind:
 828   case MemRegion::ElementRegionKind:
 829   case MemRegion::ObjCStringRegionKind: {
 830     QualType Ty = cast<TypedValueRegion>(SR)->getDesugaredValueType(Ctx);
 831     if (isa<VariableArrayType>(Ty))
 832       return nonloc::SymbolVal(SymMgr.getExtentSymbol(SR));
 833
 834     if (Ty->isIncompleteType())
 835       return UnknownVal();
 836
 837     return getElementExtent(Ty, SVB);
 838   }
 839   case MemRegion::FieldRegionKind: {
 840     // Force callers to deal with bitfields explicitly.
 841     if (cast<FieldRegion>(SR)->getDecl()->isBitField())
 842       return UnknownVal();
 843
 844     QualType Ty = cast<TypedValueRegion>(SR)->getDesugaredValueType(Ctx);
 845     const DefinedOrUnknownSVal Size = getElementExtent(Ty, SVB);
 846
 847     // We currently don't model flexible array members (FAMs), which are:
 848     //  - int array[]; of IncompleteArrayType
 849     //  - int array[0]; of ConstantArrayType with size 0
 850     //  - int array[1]; of ConstantArrayType with size 1
 851     // https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
 852     const auto isFlexibleArrayMemberCandidate =
 853         [this](const ArrayType *AT) -> bool {
 854       if (!AT)
 855         return false;
 856
 857       auto IsIncompleteArray = [](const ArrayType *AT) {
 858         return isa<IncompleteArrayType>(AT);
 859       };
 860       auto IsArrayOfZero = [](const ArrayType *AT) {
 861         const auto *CAT = dyn_cast<ConstantArrayType>(AT);
 862         return CAT && CAT->isZeroSize();
 863       };
 864       auto IsArrayOfOne = [](const ArrayType *AT) {
 865         const auto *CAT = dyn_cast<ConstantArrayType>(AT);
 866         return CAT && CAT->getSize() == 1;
 867       };
 868
 869       using FAMKind = LangOptions::StrictFlexArraysLevelKind;
 870       const FAMKind StrictFlexArraysLevel =
 871           Ctx.getLangOpts().getStrictFlexArraysLevel();
 872
 873       // "Default": Any trailing array member is a FAM.
 874       // Since we cannot tell at this point if this array is a trailing member
 875       // or not, let's just do the same as for "OneZeroOrIncomplete".
 876       if (StrictFlexArraysLevel == FAMKind::Default)
 877         return IsArrayOfOne(AT) || IsArrayOfZero(AT) || IsIncompleteArray(AT);
 878
 879       if (StrictFlexArraysLevel == FAMKind::OneZeroOrIncomplete)
 880         return IsArrayOfOne(AT) || IsArrayOfZero(AT) || IsIncompleteArray(AT);
 881
 882       if (StrictFlexArraysLevel == FAMKind::ZeroOrIncomplete)
 883         return IsArrayOfZero(AT) || IsIncompleteArray(AT);
 884
 885       assert(StrictFlexArraysLevel == FAMKind::IncompleteOnly);
 886       return IsIncompleteArray(AT);
 887     };
 888
 889     if (isFlexibleArrayMemberCandidate(Ctx.getAsArrayType(Ty)))
 890       return UnknownVal();
 891
 892     return Size;
 893   }
 894     // FIXME: The following are being used in 'SimpleSValBuilder' and in
 895     // 'ArrayBoundChecker::checkLocation' because there is no symbol to
 896     // represent the regions more appropriately.
 897   case MemRegion::BlockDataRegionKind:
 898   case MemRegion::BlockCodeRegionKind:
 899   case MemRegion::FunctionCodeRegionKind:
 900     return nonloc::SymbolVal(SymMgr.getExtentSymbol(SR));
 901   default:
 902     llvm_unreachable("Unhandled region");
 903   }
 904 }
 905
 906 template <typename REG>
 907 const REG *MemRegionManager::LazyAllocate(REG*& region) {
 908   if (!region) {
 909     region = new (A) REG(*this);
 910   }
 911
 912   return region;
 913 }
 914
 915 template <typename REG, typename ARG>
 916 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
 917   if (!region) {
 918     region = new (A) REG(this, a);
 919   }
 920
 921   return region;
 922 }
 923
 924 const StackLocalsSpaceRegion*
 925 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
 926   assert(STC);
 927   StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
 928
 929   if (R)
 930     return R;
 931
 932   R = new (A) StackLocalsSpaceRegion(*this, STC);
 933   return R;
 934 }
 935
 936 const StackArgumentsSpaceRegion *
 937 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
 938   assert(STC);
 939   StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
 940
 941   if (R)
 942     return R;
 943
 944   R = new (A) StackArgumentsSpaceRegion(*this, STC);
 945   return R;
 946 }
 947
 948 const GlobalsSpaceRegion
 949 *MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
 950                                     const CodeTextRegion *CR) {
 951   if (!CR) {
 952     if (K == MemRegion::GlobalSystemSpaceRegionKind)
 953       return LazyAllocate(SystemGlobals);
 954     if (K == MemRegion::GlobalImmutableSpaceRegionKind)
 955       return LazyAllocate(ImmutableGlobals);
 956     assert(K == MemRegion::GlobalInternalSpaceRegionKind);
 957     return LazyAllocate(InternalGlobals);
 958   }
 959
 960   assert(K == MemRegion::StaticGlobalSpaceRegionKind);
 961   StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
 962   if (R)
 963     return R;
 964
 965   R = new (A) StaticGlobalSpaceRegion(*this, CR);
 966   return R;
 967 }
 968
 969 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
 970   return LazyAllocate(heap);
 971 }
 972
 973 const UnknownSpaceRegion *MemRegionManager::getUnknownRegion() {
 974   return LazyAllocate(unknown);
 975 }
 976
 977 const CodeSpaceRegion *MemRegionManager::getCodeRegion() {
 978   return LazyAllocate(code);
 979 }
 980
 981 //===----------------------------------------------------------------------===//
 982 // Constructing regions.
 983 //===----------------------------------------------------------------------===//
 984
 985 const StringRegion *MemRegionManager::getStringRegion(const StringLiteral *Str){
 986   return getSubRegion<StringRegion>(
 987       Str, cast<GlobalInternalSpaceRegion>(getGlobalsRegion()));
 988 }
 989
 990 const ObjCStringRegion *
 991 MemRegionManager::getObjCStringRegion(const ObjCStringLiteral *Str){
 992   return getSubRegion<ObjCStringRegion>(
 993       Str, cast<GlobalInternalSpaceRegion>(getGlobalsRegion()));
 994 }
 995
 996 /// Look through a chain of LocationContexts to either find the
 997 /// StackFrameContext that matches a DeclContext, or find a VarRegion
 998 /// for a variable captured by a block.
 999 static llvm::PointerUnion<const StackFrameContext *, const VarRegion *>
1000 getStackOrCaptureRegionForDeclContext(const LocationContext *LC,
1001                                       const DeclContext *DC,
1002                                       const VarDecl *VD) {
1003   while (LC) {
1004     if (const auto *SFC = dyn_cast<StackFrameContext>(LC)) {
1005       if (cast<DeclContext>(SFC->getDecl()) == DC)
1006         return SFC;
1007     }
1008     if (const auto *BC = dyn_cast<BlockInvocationContext>(LC)) {
1009       const auto *BR = static_cast<const BlockDataRegion *>(BC->getData());
1010       // FIXME: This can be made more efficient.
1011       for (auto Var : BR->referenced_vars()) {
1012         const TypedValueRegion *OrigR = Var.getOriginalRegion();
1013         if (const auto *VR = dyn_cast<VarRegion>(OrigR)) {
1014           if (VR->getDecl() == VD)
1015             return cast<VarRegion>(Var.getCapturedRegion());
1016         }
1017       }
1018     }
1019
1020     LC = LC->getParent();
1021   }
1022   return (const StackFrameContext *)nullptr;
1023 }
1024
1025 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
1026                                                 const LocationContext *LC) {
1027   const auto *PVD = dyn_cast<ParmVarDecl>(D);
1028   if (PVD) {
1029     unsigned Index = PVD->getFunctionScopeIndex();
1030     const StackFrameContext *SFC = LC->getStackFrame();
1031     const Stmt *CallSite = SFC->getCallSite();
1032     if (CallSite) {
1033       const Decl *D = SFC->getDecl();
1034       if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
1035         if (Index < FD->param_size() && FD->parameters()[Index] == PVD)
1036           return getSubRegion<ParamVarRegion>(cast<Expr>(CallSite), Index,
1037                                               getStackArgumentsRegion(SFC));
1038       } else if (const auto *BD = dyn_cast<BlockDecl>(D)) {
1039         if (Index < BD->param_size() && BD->parameters()[Index] == PVD)
1040           return getSubRegion<ParamVarRegion>(cast<Expr>(CallSite), Index,
1041                                               getStackArgumentsRegion(SFC));
1042       } else {
1043         return getSubRegion<ParamVarRegion>(cast<Expr>(CallSite), Index,
1044                                             getStackArgumentsRegion(SFC));
1045       }
1046     }
1047   }
1048
1049   D = D->getCanonicalDecl();
1050   const MemRegion *sReg = nullptr;
1051
1052   if (D->hasGlobalStorage() && !D->isStaticLocal()) {
1053     QualType Ty = D->getType();
1054     assert(!Ty.isNull());
1055     if (Ty.isConstQualified()) {
1056       sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
1057     } else if (Ctx.getSourceManager().isInSystemHeader(D->getLocation())) {
1058       sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
1059     } else {
1060       sReg = getGlobalsRegion(MemRegion::GlobalInternalSpaceRegionKind);
1061     }
1062
1063   // Finally handle static locals.
1064   } else {
1065     // FIXME: Once we implement scope handling, we will need to properly lookup
1066     // 'D' to the proper LocationContext.
1067     const DeclContext *DC = D->getDeclContext();
1068     llvm::PointerUnion<const StackFrameContext *, const VarRegion *> V =
1069       getStackOrCaptureRegionForDeclContext(LC, DC, D);
1070
1071     if (const auto *VR = dyn_cast_if_present<const VarRegion *>(V))
1072       return VR;
1073
1074     const auto *STC = cast<const StackFrameContext *>(V);
1075
1076     if (!STC) {
1077       // FIXME: Assign a more sensible memory space to static locals
1078       // we see from within blocks that we analyze as top-level declarations.
1079       sReg = getUnknownRegion();
1080     } else {
1081       if (D->hasLocalStorage()) {
1082         sReg =
1083             isa<ParmVarDecl, ImplicitParamDecl>(D)
1084                 ? static_cast<const MemRegion *>(getStackArgumentsRegion(STC))
1085                 : static_cast<const MemRegion *>(getStackLocalsRegion(STC));
1086       }
1087       else {
1088         assert(D->isStaticLocal());
1089         const Decl *STCD = STC->getDecl();
1090         if (isa<FunctionDecl, ObjCMethodDecl>(STCD))
1091           sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
1092                                   getFunctionCodeRegion(cast<NamedDecl>(STCD)));
1093         else if (const auto *BD = dyn_cast<BlockDecl>(STCD)) {
1094           // FIXME: The fallback type here is totally bogus -- though it should
1095           // never be queried, it will prevent uniquing with the real
1096           // BlockCodeRegion. Ideally we'd fix the AST so that we always had a
1097           // signature.
1098           QualType T;
1099           if (const TypeSourceInfo *TSI = BD->getSignatureAsWritten())
1100             T = TSI->getType();
1101           if (T.isNull())
1102             T = getContext().VoidTy;
1103           if (!T->getAs<FunctionType>()) {
1104             FunctionProtoType::ExtProtoInfo Ext;
1105             T = getContext().getFunctionType(T, {}, Ext);
1106           }
1107           T = getContext().getBlockPointerType(T);
1108
1109           const BlockCodeRegion *BTR =
1110             getBlockCodeRegion(BD, Ctx.getCanonicalType(T),
1111                                STC->getAnalysisDeclContext());
1112           sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
1113                                   BTR);
1114         }
1115         else {
1116           sReg = getGlobalsRegion();
1117         }
1118       }
1119     }
1120   }
1121
1122   return getNonParamVarRegion(D, sReg);
1123 }
1124
1125 const NonParamVarRegion *
1126 MemRegionManager::getNonParamVarRegion(const VarDecl *D,
1127                                        const MemRegion *superR) {
1128   // Prefer the definition over the canonical decl as the canonical form.
1129   D = D->getCanonicalDecl();
1130   if (const VarDecl *Def = D->getDefinition())
1131     D = Def;
1132   return getSubRegion<NonParamVarRegion>(D, superR);
1133 }
1134
1135 const ParamVarRegion *
1136 MemRegionManager::getParamVarRegion(const Expr *OriginExpr, unsigned Index,
1137                                     const LocationContext *LC) {
1138   const StackFrameContext *SFC = LC->getStackFrame();
1139   assert(SFC);
1140   return getSubRegion<ParamVarRegion>(OriginExpr, Index,
1141                                       getStackArgumentsRegion(SFC));
1142 }
1143
1144 const BlockDataRegion *
1145 MemRegionManager::getBlockDataRegion(const BlockCodeRegion *BC,
1146                                      const LocationContext *LC,
1147                                      unsigned blockCount) {
1148   const MemSpaceRegion *sReg = nullptr;
1149   const BlockDecl *BD = BC->getDecl();
1150   if (!BD->hasCaptures()) {
1151     // This handles 'static' blocks.
1152     sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
1153   }
1154   else {
1155     bool IsArcManagedBlock = Ctx.getLangOpts().ObjCAutoRefCount;
1156
1157     // ARC managed blocks can be initialized on stack or directly in heap
1158     // depending on the implementations.  So we initialize them with
1159     // UnknownRegion.
1160     if (!IsArcManagedBlock && LC) {
1161       // FIXME: Once we implement scope handling, we want the parent region
1162       // to be the scope.
1163       const StackFrameContext *STC = LC->getStackFrame();
1164       assert(STC);
1165       sReg = getStackLocalsRegion(STC);
1166     } else {
1167       // We allow 'LC' to be NULL for cases where want BlockDataRegions
1168       // without context-sensitivity.
1169       sReg = getUnknownRegion();
1170     }
1171   }
1172
1173   return getSubRegion<BlockDataRegion>(BC, LC, blockCount, sReg);
1174 }
1175
1176 const CompoundLiteralRegion*
1177 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
1178                                            const LocationContext *LC) {
1179   const MemSpaceRegion *sReg = nullptr;
1180
1181   if (CL->isFileScope())
1182     sReg = getGlobalsRegion();
1183   else {
1184     const StackFrameContext *STC = LC->getStackFrame();
1185     assert(STC);
1186     sReg = getStackLocalsRegion(STC);
1187   }
1188
1189   return getSubRegion<CompoundLiteralRegion>(CL, sReg);
1190 }
1191
1192 const ElementRegion *
1193 MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
1194                                    const SubRegion *superRegion,
1195                                    const ASTContext &Ctx) {
1196   QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
1197
1198   llvm::FoldingSetNodeID ID;
1199   ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
1200
1201   void *InsertPos;
1202   MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
1203   auto *R = cast_or_null<ElementRegion>(data);
1204
1205   if (!R) {
1206     R = new (A) ElementRegion(T, Idx, superRegion);
1207     Regions.InsertNode(R, InsertPos);
1208   }
1209
1210   return R;
1211 }
1212
1213 const FunctionCodeRegion *
1214 MemRegionManager::getFunctionCodeRegion(const NamedDecl *FD) {
1215   // To think: should we canonicalize the declaration here?
1216   return getSubRegion<FunctionCodeRegion>(FD, getCodeRegion());
1217 }
1218
1219 const BlockCodeRegion *
1220 MemRegionManager::getBlockCodeRegion(const BlockDecl *BD, CanQualType locTy,
1221                                      AnalysisDeclContext *AC) {
1222   return getSubRegion<BlockCodeRegion>(BD, locTy, AC, getCodeRegion());
1223 }
1224
1225 const SymbolicRegion *
1226 MemRegionManager::getSymbolicRegion(SymbolRef sym,
1227                                     const MemSpaceRegion *MemSpace) {
1228   if (MemSpace == nullptr)
1229     MemSpace = getUnknownRegion();
1230   return getSubRegion<SymbolicRegion>(sym, MemSpace);
1231 }
1232
1233 const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) {
1234   return getSubRegion<SymbolicRegion>(Sym, getHeapRegion());
1235 }
1236
1237 const FieldRegion*
1238 MemRegionManager::getFieldRegion(const FieldDecl *d,
1239                                  const SubRegion* superRegion){
1240   return getSubRegion<FieldRegion>(d, superRegion);
1241 }
1242
1243 const ObjCIvarRegion*
1244 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
1245                                     const SubRegion* superRegion) {
1246   return getSubRegion<ObjCIvarRegion>(d, superRegion);
1247 }
1248
1249 const CXXTempObjectRegion*
1250 MemRegionManager::getCXXTempObjectRegion(Expr const *E,
1251                                          LocationContext const *LC) {
1252   const StackFrameContext *SFC = LC->getStackFrame();
1253   assert(SFC);
1254   return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
1255 }
1256
1257 const CXXLifetimeExtendedObjectRegion *
1258 MemRegionManager::getCXXLifetimeExtendedObjectRegion(
1259     const Expr *Ex, const ValueDecl *VD, const LocationContext *LC) {
1260   const StackFrameContext *SFC = LC->getStackFrame();
1261   assert(SFC);
1262   return getSubRegion<CXXLifetimeExtendedObjectRegion>(
1263       Ex, VD, getStackLocalsRegion(SFC));
1264 }
1265
1266 const CXXLifetimeExtendedObjectRegion *
1267 MemRegionManager::getCXXStaticLifetimeExtendedObjectRegion(
1268     const Expr *Ex, const ValueDecl *VD) {
1269   return getSubRegion<CXXLifetimeExtendedObjectRegion>(
1270       Ex, VD,
1271       getGlobalsRegion(MemRegion::GlobalInternalSpaceRegionKind, nullptr));
1272 }
1273
1274 /// Checks whether \p BaseClass is a valid virtual or direct non-virtual base
1275 /// class of the type of \p Super.
1276 static bool isValidBaseClass(const CXXRecordDecl *BaseClass,
1277                              const TypedValueRegion *Super,
1278                              bool IsVirtual) {
1279   BaseClass = BaseClass->getCanonicalDecl();
1280
1281   const CXXRecordDecl *Class = Super->getValueType()->getAsCXXRecordDecl();
1282   if (!Class)
1283     return true;
1284
1285   if (IsVirtual)
1286     return Class->isVirtuallyDerivedFrom(BaseClass);
1287
1288   for (const auto &I : Class->bases()) {
1289     if (I.getType()->getAsCXXRecordDecl()->getCanonicalDecl() == BaseClass)
1290       return true;
1291   }
1292
1293   return false;
1294 }
1295
1296 const CXXBaseObjectRegion *
1297 MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *RD,
1298                                          const SubRegion *Super,
1299                                          bool IsVirtual) {
1300   if (isa<TypedValueRegion>(Super)) {
1301     assert(isValidBaseClass(RD, cast<TypedValueRegion>(Super), IsVirtual));
1302     (void)&isValidBaseClass;
1303
1304     if (IsVirtual) {
1305       // Virtual base regions should not be layered, since the layout rules
1306       // are different.
1307       while (const auto *Base = dyn_cast<CXXBaseObjectRegion>(Super))
1308         Super = cast<SubRegion>(Base->getSuperRegion());
1309       assert(Super && !isa<MemSpaceRegion>(Super));
1310     }
1311   }
1312
1313   return getSubRegion<CXXBaseObjectRegion>(RD, IsVirtual, Super);
1314 }
1315
1316 const CXXDerivedObjectRegion *
1317 MemRegionManager::getCXXDerivedObjectRegion(const CXXRecordDecl *RD,
1318                                             const SubRegion *Super) {
1319   return getSubRegion<CXXDerivedObjectRegion>(RD, Super);
1320 }
1321
1322 const CXXThisRegion*
1323 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
1324                                    const LocationContext *LC) {
1325   const auto *PT = thisPointerTy->getAs<PointerType>();
1326   assert(PT);
1327   // Inside the body of the operator() of a lambda a this expr might refer to an
1328   // object in one of the parent location contexts.
1329   const auto *D = dyn_cast<CXXMethodDecl>(LC->getDecl());
1330   // FIXME: when operator() of lambda is analyzed as a top level function and
1331   // 'this' refers to a this to the enclosing scope, there is no right region to
1332   // return.
1333   while (!LC->inTopFrame() && (!D || D->isStatic() ||
1334                                PT != D->getThisType()->getAs<PointerType>())) {
1335     LC = LC->getParent();
1336     D = dyn_cast<CXXMethodDecl>(LC->getDecl());
1337   }
1338   const StackFrameContext *STC = LC->getStackFrame();
1339   assert(STC);
1340   return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
1341 }
1342
1343 const AllocaRegion*
1344 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
1345                                   const LocationContext *LC) {
1346   const StackFrameContext *STC = LC->getStackFrame();
1347   assert(STC);
1348   return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
1349 }
1350
1351 const MemSpaceRegion *MemRegion::getMemorySpace() const {
1352   const MemRegion *R = this;
1353   const auto *SR = dyn_cast<SubRegion>(this);
1354
1355   while (SR) {
1356     R = SR->getSuperRegion();
1357     SR = dyn_cast<SubRegion>(R);
1358   }
1359
1360   return cast<MemSpaceRegion>(R);
1361 }
1362
1363 bool MemRegion::hasStackStorage() const {
1364   return isa<StackSpaceRegion>(getMemorySpace());
1365 }
1366
1367 bool MemRegion::hasStackNonParametersStorage() const {
1368   return isa<StackLocalsSpaceRegion>(getMemorySpace());
1369 }
1370
1371 bool MemRegion::hasStackParametersStorage() const {
1372   return isa<StackArgumentsSpaceRegion>(getMemorySpace());
1373 }
1374
1375 // Strips away all elements and fields.
1376 // Returns the base region of them.
1377 const MemRegion *MemRegion::getBaseRegion() const {
1378   const MemRegion *R = this;
1379   while (true) {
1380     switch (R->getKind()) {
1381       case MemRegion::ElementRegionKind:
1382       case MemRegion::FieldRegionKind:
1383       case MemRegion::ObjCIvarRegionKind:
1384       case MemRegion::CXXBaseObjectRegionKind:
1385       case MemRegion::CXXDerivedObjectRegionKind:
1386         R = cast<SubRegion>(R)->getSuperRegion();
1387         continue;
1388       default:
1389         break;
1390     }
1391     break;
1392   }
1393   return R;
1394 }
1395
1396 // Returns the region of the root class of a C++ class hierarchy.
1397 const MemRegion *MemRegion::getMostDerivedObjectRegion() const {
1398   const MemRegion *R = this;
1399   while (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R))
1400     R = BR->getSuperRegion();
1401   return R;
1402 }
1403
1404 bool MemRegion::isSubRegionOf(const MemRegion *) const {
1405   return false;
1406 }
1407
1408 //===----------------------------------------------------------------------===//
1409 // View handling.
1410 //===----------------------------------------------------------------------===//
1411
1412 const MemRegion *MemRegion::StripCasts(bool StripBaseAndDerivedCasts) const {
1413   const MemRegion *R = this;
1414   while (true) {
1415     switch (R->getKind()) {
1416     case ElementRegionKind: {
1417       const auto *ER = cast<ElementRegion>(R);
1418       if (!ER->getIndex().isZeroConstant())
1419         return R;
1420       R = ER->getSuperRegion();
1421       break;
1422     }
1423     case CXXBaseObjectRegionKind:
1424     case CXXDerivedObjectRegionKind:
1425       if (!StripBaseAndDerivedCasts)
1426         return R;
1427       R = cast<TypedValueRegion>(R)->getSuperRegion();
1428       break;
1429     default:
1430       return R;
1431     }
1432   }
1433 }
1434
1435 const SymbolicRegion *MemRegion::getSymbolicBase() const {
1436   const auto *SubR = dyn_cast<SubRegion>(this);
1437
1438   while (SubR) {
1439     if (const auto *SymR = dyn_cast<SymbolicRegion>(SubR))
1440       return SymR;
1441     SubR = dyn_cast<SubRegion>(SubR->getSuperRegion());
1442   }
1443   return nullptr;
1444 }
1445
1446 RegionRawOffset ElementRegion::getAsArrayOffset() const {
1447   int64_t offset = 0;
1448   const ElementRegion *ER = this;
1449   const MemRegion *superR = nullptr;
1450   ASTContext &C = getContext();
1451
1452   // FIXME: Handle multi-dimensional arrays.
1453
1454   while (ER) {
1455     superR = ER->getSuperRegion();
1456
1457     // FIXME: generalize to symbolic offsets.
1458     SVal index = ER->getIndex();
1459     if (auto CI = index.getAs<nonloc::ConcreteInt>()) {
1460       // Update the offset.
1461       int64_t i = CI->getValue().getSExtValue();
1462
1463       if (i != 0) {
1464         QualType elemType = ER->getElementType();
1465
1466         // If we are pointing to an incomplete type, go no further.
1467         if (elemType->isIncompleteType()) {
1468           superR = ER;
1469           break;
1470         }
1471
1472         int64_t size = C.getTypeSizeInChars(elemType).getQuantity();
1473         if (auto NewOffset = llvm::checkedMulAdd(i, size, offset)) {
1474           offset = *NewOffset;
1475         } else {
1476           LLVM_DEBUG(llvm::dbgs() << "MemRegion::getAsArrayOffset: "
1477                                   << "offset overflowing, returning unknown\n");
1478
1479           return nullptr;
1480         }
1481       }
1482
1483       // Go to the next ElementRegion (if any).
1484       ER = dyn_cast<ElementRegion>(superR);
1485       continue;
1486     }
1487
1488     return nullptr;
1489   }
1490
1491   assert(superR && "super region cannot be NULL");
1492   return RegionRawOffset(superR, CharUnits::fromQuantity(offset));
1493 }
1494
1495 /// Returns true if \p Base is an immediate base class of \p Child
1496 static bool isImmediateBase(const CXXRecordDecl *Child,
1497                             const CXXRecordDecl *Base) {
1498   assert(Child && "Child must not be null");
1499   // Note that we do NOT canonicalize the base class here, because
1500   // ASTRecordLayout doesn't either. If that leads us down the wrong path,
1501   // so be it; at least we won't crash.
1502   for (const auto &I : Child->bases()) {
1503     if (I.getType()->getAsCXXRecordDecl() == Base)
1504       return true;
1505   }
1506
1507   return false;
1508 }
1509
1510 static RegionOffset calculateOffset(const MemRegion *R) {
1511   const MemRegion *SymbolicOffsetBase = nullptr;
1512   int64_t Offset = 0;
1513
1514   while (true) {
1515     switch (R->getKind()) {
1516     case MemRegion::CodeSpaceRegionKind:
1517     case MemRegion::StackLocalsSpaceRegionKind:
1518     case MemRegion::StackArgumentsSpaceRegionKind:
1519     case MemRegion::HeapSpaceRegionKind:
1520     case MemRegion::UnknownSpaceRegionKind:
1521     case MemRegion::StaticGlobalSpaceRegionKind:
1522     case MemRegion::GlobalInternalSpaceRegionKind:
1523     case MemRegion::GlobalSystemSpaceRegionKind:
1524     case MemRegion::GlobalImmutableSpaceRegionKind:
1525       // Stores can bind directly to a region space to set a default value.
1526       assert(Offset == 0 && !SymbolicOffsetBase);
1527       goto Finish;
1528
1529     case MemRegion::FunctionCodeRegionKind:
1530     case MemRegion::BlockCodeRegionKind:
1531     case MemRegion::BlockDataRegionKind:
1532       // These will never have bindings, but may end up having values requested
1533       // if the user does some strange casting.
1534       if (Offset != 0)
1535         SymbolicOffsetBase = R;
1536       goto Finish;
1537
1538     case MemRegion::SymbolicRegionKind:
1539     case MemRegion::AllocaRegionKind:
1540     case MemRegion::CompoundLiteralRegionKind:
1541     case MemRegion::CXXThisRegionKind:
1542     case MemRegion::StringRegionKind:
1543     case MemRegion::ObjCStringRegionKind:
1544     case MemRegion::NonParamVarRegionKind:
1545     case MemRegion::ParamVarRegionKind:
1546     case MemRegion::CXXTempObjectRegionKind:
1547     case MemRegion::CXXLifetimeExtendedObjectRegionKind:
1548       // Usual base regions.
1549       goto Finish;
1550
1551     case MemRegion::ObjCIvarRegionKind:
1552       // This is a little strange, but it's a compromise between
1553       // ObjCIvarRegions having unknown compile-time offsets (when using the
1554       // non-fragile runtime) and yet still being distinct, non-overlapping
1555       // regions. Thus we treat them as "like" base regions for the purposes
1556       // of computing offsets.
1557       goto Finish;
1558
1559     case MemRegion::CXXBaseObjectRegionKind: {
1560       const auto *BOR = cast<CXXBaseObjectRegion>(R);
1561       R = BOR->getSuperRegion();
1562
1563       QualType Ty;
1564       bool RootIsSymbolic = false;
1565       if (const auto *TVR = dyn_cast<TypedValueRegion>(R)) {
1566         Ty = TVR->getDesugaredValueType(R->getContext());
1567       } else if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
1568         // If our base region is symbolic, we don't know what type it really is.
1569         // Pretend the type of the symbol is the true dynamic type.
1570         // (This will at least be self-consistent for the life of the symbol.)
1571         Ty = SR->getPointeeStaticType();
1572         RootIsSymbolic = true;
1573       }
1574
1575       const CXXRecordDecl *Child = Ty->getAsCXXRecordDecl();
1576       if (!Child) {
1577         // We cannot compute the offset of the base class.
1578         SymbolicOffsetBase = R;
1579       } else {
1580         if (RootIsSymbolic) {
1581           // Base layers on symbolic regions may not be type-correct.
1582           // Double-check the inheritance here, and revert to a symbolic offset
1583           // if it's invalid (e.g. due to a reinterpret_cast).
1584           if (BOR->isVirtual()) {
1585             if (!Child->isVirtuallyDerivedFrom(BOR->getDecl()))
1586               SymbolicOffsetBase = R;
1587           } else {
1588             if (!isImmediateBase(Child, BOR->getDecl()))
1589               SymbolicOffsetBase = R;
1590           }
1591         }
1592       }
1593
1594       // Don't bother calculating precise offsets if we already have a
1595       // symbolic offset somewhere in the chain.
1596       if (SymbolicOffsetBase)
1597         continue;
1598
1599       CharUnits BaseOffset;
1600       const ASTRecordLayout &Layout = R->getContext().getASTRecordLayout(Child);
1601       if (BOR->isVirtual())
1602         BaseOffset = Layout.getVBaseClassOffset(BOR->getDecl());
1603       else
1604         BaseOffset = Layout.getBaseClassOffset(BOR->getDecl());
1605
1606       // The base offset is in chars, not in bits.
1607       Offset += BaseOffset.getQuantity() * R->getContext().getCharWidth();
1608       break;
1609     }
1610
1611     case MemRegion::CXXDerivedObjectRegionKind: {
1612       // TODO: Store the base type in the CXXDerivedObjectRegion and use it.
1613       goto Finish;
1614     }
1615
1616     case MemRegion::ElementRegionKind: {
1617       const auto *ER = cast<ElementRegion>(R);
1618       R = ER->getSuperRegion();
1619
1620       QualType EleTy = ER->getValueType();
1621       if (EleTy->isIncompleteType()) {
1622         // We cannot compute the offset of the base class.
1623         SymbolicOffsetBase = R;
1624         continue;
1625       }
1626
1627       SVal Index = ER->getIndex();
1628       if (std::optional<nonloc::ConcreteInt> CI =
1629               Index.getAs<nonloc::ConcreteInt>()) {
1630         // Don't bother calculating precise offsets if we already have a
1631         // symbolic offset somewhere in the chain.
1632         if (SymbolicOffsetBase)
1633           continue;
1634
1635         int64_t i = CI->getValue().getSExtValue();
1636         // This type size is in bits.
1637         Offset += i * R->getContext().getTypeSize(EleTy);
1638       } else {
1639         // We cannot compute offset for non-concrete index.
1640         SymbolicOffsetBase = R;
1641       }
1642       break;
1643     }
1644     case MemRegion::FieldRegionKind: {
1645       const auto *FR = cast<FieldRegion>(R);
1646       R = FR->getSuperRegion();
1647       assert(R);
1648
1649       const RecordDecl *RD = FR->getDecl()->getParent();
1650       if (RD->isUnion() || !RD->isCompleteDefinition()) {
1651         // We cannot compute offset for incomplete type.
1652         // For unions, we could treat everything as offset 0, but we'd rather
1653         // treat each field as a symbolic offset so they aren't stored on top
1654         // of each other, since we depend on things in typed regions actually
1655         // matching their types.
1656         SymbolicOffsetBase = R;
1657       }
1658
1659       // Don't bother calculating precise offsets if we already have a
1660       // symbolic offset somewhere in the chain.
1661       if (SymbolicOffsetBase)
1662         continue;
1663
1664       // Get the field number.
1665       unsigned idx = 0;
1666       for (RecordDecl::field_iterator FI = RD->field_begin(),
1667              FE = RD->field_end(); FI != FE; ++FI, ++idx) {
1668         if (FR->getDecl() == *FI)
1669           break;
1670       }
1671       const ASTRecordLayout &Layout = R->getContext().getASTRecordLayout(RD);
1672       // This is offset in bits.
1673       Offset += Layout.getFieldOffset(idx);
1674       break;
1675     }
1676     }
1677   }
1678
1679  Finish:
1680   if (SymbolicOffsetBase)
1681     return RegionOffset(SymbolicOffsetBase, RegionOffset::Symbolic);
1682   return RegionOffset(R, Offset);
1683 }
1684
1685 RegionOffset MemRegion::getAsOffset() const {
1686   if (!cachedOffset)
1687     cachedOffset = calculateOffset(this);
1688   return *cachedOffset;
1689 }
1690
1691 //===----------------------------------------------------------------------===//
1692 // BlockDataRegion
1693 //===----------------------------------------------------------------------===//
1694
1695 std::pair<const VarRegion *, const VarRegion *>
1696 BlockDataRegion::getCaptureRegions(const VarDecl *VD) {
1697   MemRegionManager &MemMgr = getMemRegionManager();
1698   const VarRegion *VR = nullptr;
1699   const VarRegion *OriginalVR = nullptr;
1700
1701   if (!VD->hasAttr<BlocksAttr>() && VD->hasLocalStorage()) {
1702     VR = MemMgr.getNonParamVarRegion(VD, this);
1703     OriginalVR = MemMgr.getVarRegion(VD, LC);
1704   }
1705   else {
1706     if (LC) {
1707       VR = MemMgr.getVarRegion(VD, LC);
1708       OriginalVR = VR;
1709     }
1710     else {
1711       VR = MemMgr.getNonParamVarRegion(VD, MemMgr.getUnknownRegion());
1712       OriginalVR = MemMgr.getVarRegion(VD, LC);
1713     }
1714   }
1715   return std::make_pair(VR, OriginalVR);
1716 }
1717
1718 void BlockDataRegion::LazyInitializeReferencedVars() {
1719   if (ReferencedVars)
1720     return;
1721
1722   AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1723   const auto &ReferencedBlockVars = AC->getReferencedBlockVars(BC->getDecl());
1724   auto NumBlockVars =
1725       std::distance(ReferencedBlockVars.begin(), ReferencedBlockVars.end());
1726
1727   if (NumBlockVars == 0) {
1728     ReferencedVars = (void*) 0x1;
1729     return;
1730   }
1731
1732   MemRegionManager &MemMgr = getMemRegionManager();
1733   llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1734   BumpVectorContext BC(A);
1735
1736   using VarVec = BumpVector<const MemRegion *>;
1737
1738   auto *BV = new (A) VarVec(BC, NumBlockVars);
1739   auto *BVOriginal = new (A) VarVec(BC, NumBlockVars);
1740
1741   for (const auto *VD : ReferencedBlockVars) {
1742     const VarRegion *VR = nullptr;
1743     const VarRegion *OriginalVR = nullptr;
1744     std::tie(VR, OriginalVR) = getCaptureRegions(VD);
1745     assert(VR);
1746     assert(OriginalVR);
1747     BV->push_back(VR, BC);
1748     BVOriginal->push_back(OriginalVR, BC);
1749   }
1750
1751   ReferencedVars = BV;
1752   OriginalVars = BVOriginal;
1753 }
1754
1755 BlockDataRegion::referenced_vars_iterator
1756 BlockDataRegion::referenced_vars_begin() const {
1757   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1758
1759   auto *Vec = static_cast<BumpVector<const MemRegion *> *>(ReferencedVars);
1760
1761   if (Vec == (void*) 0x1)
1762     return BlockDataRegion::referenced_vars_iterator(nullptr, nullptr);
1763
1764   auto *VecOriginal =
1765       static_cast<BumpVector<const MemRegion *> *>(OriginalVars);
1766
1767   return BlockDataRegion::referenced_vars_iterator(Vec->begin(),
1768                                                    VecOriginal->begin());
1769 }
1770
1771 BlockDataRegion::referenced_vars_iterator
1772 BlockDataRegion::referenced_vars_end() const {
1773   const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1774
1775   auto *Vec = static_cast<BumpVector<const MemRegion *> *>(ReferencedVars);
1776
1777   if (Vec == (void*) 0x1)
1778     return BlockDataRegion::referenced_vars_iterator(nullptr, nullptr);
1779
1780   auto *VecOriginal =
1781       static_cast<BumpVector<const MemRegion *> *>(OriginalVars);
1782
1783   return BlockDataRegion::referenced_vars_iterator(Vec->end(),
1784                                                    VecOriginal->end());
1785 }
1786
1787 llvm::iterator_range<BlockDataRegion::referenced_vars_iterator>
1788 BlockDataRegion::referenced_vars() const {
1789   return llvm::make_range(referenced_vars_begin(), referenced_vars_end());
1790 }
1791
1792 const VarRegion *BlockDataRegion::getOriginalRegion(const VarRegion *R) const {
1793   for (const auto &I : referenced_vars()) {
1794     if (I.getCapturedRegion() == R)
1795       return I.getOriginalRegion();
1796   }
1797   return nullptr;
1798 }
1799
1800 //===----------------------------------------------------------------------===//
1801 // RegionAndSymbolInvalidationTraits
1802 //===----------------------------------------------------------------------===//
1803
1804 void RegionAndSymbolInvalidationTraits::setTrait(SymbolRef Sym,
1805                                                  InvalidationKinds IK) {
1806   SymTraitsMap[Sym] |= IK;
1807 }
1808
1809 void RegionAndSymbolInvalidationTraits::setTrait(const MemRegion *MR,
1810                                                  InvalidationKinds IK) {
1811   assert(MR);
1812   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
1813     setTrait(SR->getSymbol(), IK);
1814   else
1815     MRTraitsMap[MR] |= IK;
1816 }
1817
1818 bool RegionAndSymbolInvalidationTraits::hasTrait(SymbolRef Sym,
1819                                                  InvalidationKinds IK) const {
1820   const_symbol_iterator I = SymTraitsMap.find(Sym);
1821   if (I != SymTraitsMap.end())
1822     return I->second & IK;
1823
1824   return false;
1825 }
1826
1827 bool RegionAndSymbolInvalidationTraits::hasTrait(const MemRegion *MR,
1828                                                  InvalidationKinds IK) const {
1829   if (!MR)
1830     return false;
1831
1832   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
1833     return hasTrait(SR->getSymbol(), IK);
1834
1835   const_region_iterator I = MRTraitsMap.find(MR);
1836   if (I != MRTraitsMap.end())
1837     return I->second & IK;
1838
1839   return false;
1840 }