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