contrib/llvm-project/clang/lib/Analysis/AnalysisDeclContext.cpp

   1 //===- AnalysisDeclContext.cpp - Analysis context for Path Sens 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 AnalysisDeclContext, a class that manages the analysis
  10 // context data for path sensitive analysis.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Analysis/AnalysisDeclContext.h"
  15 #include "clang/AST/ASTContext.h"
  16 #include "clang/AST/Decl.h"
  17 #include "clang/AST/DeclBase.h"
  18 #include "clang/AST/DeclCXX.h"
  19 #include "clang/AST/DeclObjC.h"
  20 #include "clang/AST/DeclTemplate.h"
  21 #include "clang/AST/Expr.h"
  22 #include "clang/AST/LambdaCapture.h"
  23 #include "clang/AST/ParentMap.h"
  24 #include "clang/AST/PrettyPrinter.h"
  25 #include "clang/AST/Stmt.h"
  26 #include "clang/AST/StmtCXX.h"
  27 #include "clang/AST/StmtVisitor.h"
  28 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
  29 #include "clang/Analysis/BodyFarm.h"
  30 #include "clang/Analysis/CFG.h"
  31 #include "clang/Analysis/CFGStmtMap.h"
  32 #include "clang/Analysis/Support/BumpVector.h"
  33 #include "clang/Basic/JsonSupport.h"
  34 #include "clang/Basic/LLVM.h"
  35 #include "clang/Basic/SourceLocation.h"
  36 #include "clang/Basic/SourceManager.h"
  37 #include "llvm/ADT/DenseMap.h"
  38 #include "llvm/ADT/FoldingSet.h"
  39 #include "llvm/ADT/STLExtras.h"
  40 #include "llvm/ADT/SmallPtrSet.h"
  41 #include "llvm/ADT/iterator_range.h"
  42 #include "llvm/Support/Allocator.h"
  43 #include "llvm/Support/Casting.h"
  44 #include "llvm/Support/Compiler.h"
  45 #include "llvm/Support/ErrorHandling.h"
  46 #include "llvm/Support/SaveAndRestore.h"
  47 #include "llvm/Support/raw_ostream.h"
  48 #include <cassert>
  49 #include <memory>
  50
  51 using namespace clang;
  52
  53 using ManagedAnalysisMap = llvm::DenseMap<const void *, ManagedAnalysis *>;
  54
  55 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
  56                                          const Decl *d,
  57                                          const CFG::BuildOptions &buildOptions)
  58     : Manager(Mgr), D(d), cfgBuildOptions(buildOptions) {
  59   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
  60 }
  61
  62 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
  63                                          const Decl *d)
  64     : Manager(Mgr), D(d) {
  65   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
  66 }
  67
  68 AnalysisDeclContextManager::AnalysisDeclContextManager(
  69     ASTContext &ASTCtx, bool useUnoptimizedCFG, bool addImplicitDtors,
  70     bool addInitializers, bool addTemporaryDtors, bool addLifetime,
  71     bool addLoopExit, bool addScopes, bool synthesizeBodies,
  72     bool addStaticInitBranch, bool addCXXNewAllocator,
  73     bool addRichCXXConstructors, bool markElidedCXXConstructors,
  74     bool addVirtualBaseBranches, CodeInjector *injector)
  75     : Injector(injector), FunctionBodyFarm(ASTCtx, injector),
  76       SynthesizeBodies(synthesizeBodies) {
  77   cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
  78   cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
  79   cfgBuildOptions.AddInitializers = addInitializers;
  80   cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors;
  81   cfgBuildOptions.AddLifetime = addLifetime;
  82   cfgBuildOptions.AddLoopExit = addLoopExit;
  83   cfgBuildOptions.AddScopes = addScopes;
  84   cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch;
  85   cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
  86   cfgBuildOptions.AddRichCXXConstructors = addRichCXXConstructors;
  87   cfgBuildOptions.MarkElidedCXXConstructors = markElidedCXXConstructors;
  88   cfgBuildOptions.AddVirtualBaseBranches = addVirtualBaseBranches;
  89 }
  90
  91 void AnalysisDeclContextManager::clear() { Contexts.clear(); }
  92
  93 Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const {
  94   IsAutosynthesized = false;
  95   if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
  96     Stmt *Body = FD->getBody();
  97     if (auto *CoroBody = dyn_cast_or_null<CoroutineBodyStmt>(Body))
  98       Body = CoroBody->getBody();
  99     if (Manager && Manager->synthesizeBodies()) {
 100       Stmt *SynthesizedBody = Manager->getBodyFarm().getBody(FD);
 101       if (SynthesizedBody) {
 102         Body = SynthesizedBody;
 103         IsAutosynthesized = true;
 104       }
 105     }
 106     return Body;
 107   }
 108   else if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
 109     Stmt *Body = MD->getBody();
 110     if (Manager && Manager->synthesizeBodies()) {
 111       Stmt *SynthesizedBody = Manager->getBodyFarm().getBody(MD);
 112       if (SynthesizedBody) {
 113         Body = SynthesizedBody;
 114         IsAutosynthesized = true;
 115       }
 116     }
 117     return Body;
 118   } else if (const auto *BD = dyn_cast<BlockDecl>(D))
 119     return BD->getBody();
 120   else if (const auto *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
 121     return FunTmpl->getTemplatedDecl()->getBody();
 122
 123   llvm_unreachable("unknown code decl");
 124 }
 125
 126 Stmt *AnalysisDeclContext::getBody() const {
 127   bool Tmp;
 128   return getBody(Tmp);
 129 }
 130
 131 bool AnalysisDeclContext::isBodyAutosynthesized() const {
 132   bool Tmp;
 133   getBody(Tmp);
 134   return Tmp;
 135 }
 136
 137 bool AnalysisDeclContext::isBodyAutosynthesizedFromModelFile() const {
 138   bool Tmp;
 139   Stmt *Body = getBody(Tmp);
 140   return Tmp && Body->getBeginLoc().isValid();
 141 }
 142
 143 /// Returns true if \param VD is an Objective-C implicit 'self' parameter.
 144 static bool isSelfDecl(const VarDecl *VD) {
 145   return isa<ImplicitParamDecl>(VD) && VD->getName() == "self";
 146 }
 147
 148 const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const {
 149   if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
 150     return MD->getSelfDecl();
 151   if (const auto *BD = dyn_cast<BlockDecl>(D)) {
 152     // See if 'self' was captured by the block.
 153     for (const auto &I : BD->captures()) {
 154       const VarDecl *VD = I.getVariable();
 155       if (isSelfDecl(VD))
 156         return dyn_cast<ImplicitParamDecl>(VD);
 157     }
 158   }
 159
 160   auto *CXXMethod = dyn_cast<CXXMethodDecl>(D);
 161   if (!CXXMethod)
 162     return nullptr;
 163
 164   const CXXRecordDecl *parent = CXXMethod->getParent();
 165   if (!parent->isLambda())
 166     return nullptr;
 167
 168   for (const auto &LC : parent->captures()) {
 169     if (!LC.capturesVariable())
 170       continue;
 171
 172     VarDecl *VD = LC.getCapturedVar();
 173     if (isSelfDecl(VD))
 174       return dyn_cast<ImplicitParamDecl>(VD);
 175   }
 176
 177   return nullptr;
 178 }
 179
 180 void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) {
 181   if (!forcedBlkExprs)
 182     forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs();
 183   // Default construct an entry for 'stmt'.
 184   if (const auto *e = dyn_cast<Expr>(stmt))
 185     stmt = e->IgnoreParens();
 186   (void) (*forcedBlkExprs)[stmt];
 187 }
 188
 189 const CFGBlock *
 190 AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) {
 191   assert(forcedBlkExprs);
 192   if (const auto *e = dyn_cast<Expr>(stmt))
 193     stmt = e->IgnoreParens();
 194   CFG::BuildOptions::ForcedBlkExprs::const_iterator itr =
 195     forcedBlkExprs->find(stmt);
 196   assert(itr != forcedBlkExprs->end());
 197   return itr->second;
 198 }
 199
 200 /// Add each synthetic statement in the CFG to the parent map, using the
 201 /// source statement's parent.
 202 static void addParentsForSyntheticStmts(const CFG *TheCFG, ParentMap &PM) {
 203   if (!TheCFG)
 204     return;
 205
 206   for (CFG::synthetic_stmt_iterator I = TheCFG->synthetic_stmt_begin(),
 207                                     E = TheCFG->synthetic_stmt_end();
 208        I != E; ++I) {
 209     PM.setParent(I->first, PM.getParent(I->second));
 210   }
 211 }
 212
 213 CFG *AnalysisDeclContext::getCFG() {
 214   if (!cfgBuildOptions.PruneTriviallyFalseEdges)
 215     return getUnoptimizedCFG();
 216
 217   if (!builtCFG) {
 218     cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
 219     // Even when the cfg is not successfully built, we don't
 220     // want to try building it again.
 221     builtCFG = true;
 222
 223     if (PM)
 224       addParentsForSyntheticStmts(cfg.get(), *PM);
 225
 226     // The Observer should only observe one build of the CFG.
 227     getCFGBuildOptions().Observer = nullptr;
 228   }
 229   return cfg.get();
 230 }
 231
 232 CFG *AnalysisDeclContext::getUnoptimizedCFG() {
 233   if (!builtCompleteCFG) {
 234     SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges,
 235                                   false);
 236     completeCFG =
 237         CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
 238     // Even when the cfg is not successfully built, we don't
 239     // want to try building it again.
 240     builtCompleteCFG = true;
 241
 242     if (PM)
 243       addParentsForSyntheticStmts(completeCFG.get(), *PM);
 244
 245     // The Observer should only observe one build of the CFG.
 246     getCFGBuildOptions().Observer = nullptr;
 247   }
 248   return completeCFG.get();
 249 }
 250
 251 CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
 252   if (cfgStmtMap)
 253     return cfgStmtMap.get();
 254
 255   if (CFG *c = getCFG()) {
 256     cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
 257     return cfgStmtMap.get();
 258   }
 259
 260   return nullptr;
 261 }
 262
 263 CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
 264   if (CFA)
 265     return CFA.get();
 266
 267   if (CFG *c = getCFG()) {
 268     CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
 269     return CFA.get();
 270   }
 271
 272   return nullptr;
 273 }
 274
 275 void AnalysisDeclContext::dumpCFG(bool ShowColors) {
 276   getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
 277 }
 278
 279 ParentMap &AnalysisDeclContext::getParentMap() {
 280   if (!PM) {
 281     PM.reset(new ParentMap(getBody()));
 282     if (const auto *C = dyn_cast<CXXConstructorDecl>(getDecl())) {
 283       for (const auto *I : C->inits()) {
 284         PM->addStmt(I->getInit());
 285       }
 286     }
 287     if (builtCFG)
 288       addParentsForSyntheticStmts(getCFG(), *PM);
 289     if (builtCompleteCFG)
 290       addParentsForSyntheticStmts(getUnoptimizedCFG(), *PM);
 291   }
 292   return *PM;
 293 }
 294
 295 AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) {
 296   if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
 297     // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl
 298     // that has the body.
 299     FD->hasBody(FD);
 300     D = FD;
 301   }
 302
 303   std::unique_ptr<AnalysisDeclContext> &AC = Contexts[D];
 304   if (!AC)
 305     AC = std::make_unique<AnalysisDeclContext>(this, D, cfgBuildOptions);
 306   return AC.get();
 307 }
 308
 309 BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; }
 310
 311 const StackFrameContext *
 312 AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
 313                                    const CFGBlock *Blk, unsigned BlockCount,
 314                                    unsigned Idx) {
 315   return getLocationContextManager().getStackFrame(this, Parent, S, Blk,
 316                                                    BlockCount, Idx);
 317 }
 318
 319 const BlockInvocationContext *
 320 AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent,
 321                                                const BlockDecl *BD,
 322                                                const void *ContextData) {
 323   return getLocationContextManager().getBlockInvocationContext(this, parent,
 324                                                                BD, ContextData);
 325 }
 326
 327 bool AnalysisDeclContext::isInStdNamespace(const Decl *D) {
 328   const DeclContext *DC = D->getDeclContext()->getEnclosingNamespaceContext();
 329   const auto *ND = dyn_cast<NamespaceDecl>(DC);
 330   if (!ND)
 331     return false;
 332
 333   while (const DeclContext *Parent = ND->getParent()) {
 334     if (!isa<NamespaceDecl>(Parent))
 335       break;
 336     ND = cast<NamespaceDecl>(Parent);
 337   }
 338
 339   return ND->isStdNamespace();
 340 }
 341
 342 LocationContextManager &AnalysisDeclContext::getLocationContextManager() {
 343   assert(Manager &&
 344          "Cannot create LocationContexts without an AnalysisDeclContextManager!");
 345   return Manager->getLocationContextManager();
 346 }
 347
 348 //===----------------------------------------------------------------------===//
 349 // FoldingSet profiling.
 350 //===----------------------------------------------------------------------===//
 351
 352 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
 353                                     ContextKind ck,
 354                                     AnalysisDeclContext *ctx,
 355                                     const LocationContext *parent,
 356                                     const void *data) {
 357   ID.AddInteger(ck);
 358   ID.AddPointer(ctx);
 359   ID.AddPointer(parent);
 360   ID.AddPointer(data);
 361 }
 362
 363 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
 364   Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block,
 365           BlockCount, Index);
 366 }
 367
 368 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
 369   Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
 370 }
 371
 372 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
 373   Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData);
 374 }
 375
 376 //===----------------------------------------------------------------------===//
 377 // LocationContext creation.
 378 //===----------------------------------------------------------------------===//
 379
 380 template <typename LOC, typename DATA>
 381 const LOC*
 382 LocationContextManager::getLocationContext(AnalysisDeclContext *ctx,
 383                                            const LocationContext *parent,
 384                                            const DATA *d) {
 385   llvm::FoldingSetNodeID ID;
 386   LOC::Profile(ID, ctx, parent, d);
 387   void *InsertPos;
 388
 389   LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
 390
 391   if (!L) {
 392     L = new LOC(ctx, parent, d, ++NewID);
 393     Contexts.InsertNode(L, InsertPos);
 394   }
 395   return L;
 396 }
 397
 398 const StackFrameContext *LocationContextManager::getStackFrame(
 399     AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s,
 400     const CFGBlock *blk, unsigned blockCount, unsigned idx) {
 401   llvm::FoldingSetNodeID ID;
 402   StackFrameContext::Profile(ID, ctx, parent, s, blk, blockCount, idx);
 403   void *InsertPos;
 404   auto *L =
 405    cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
 406   if (!L) {
 407     L = new StackFrameContext(ctx, parent, s, blk, blockCount, idx, ++NewID);
 408     Contexts.InsertNode(L, InsertPos);
 409   }
 410   return L;
 411 }
 412
 413 const ScopeContext *
 414 LocationContextManager::getScope(AnalysisDeclContext *ctx,
 415                                  const LocationContext *parent,
 416                                  const Stmt *s) {
 417   return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
 418 }
 419
 420 const BlockInvocationContext *
 421 LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx,
 422                                                   const LocationContext *parent,
 423                                                   const BlockDecl *BD,
 424                                                   const void *ContextData) {
 425   llvm::FoldingSetNodeID ID;
 426   BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData);
 427   void *InsertPos;
 428   auto *L =
 429     cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
 430                                                                     InsertPos));
 431   if (!L) {
 432     L = new BlockInvocationContext(ctx, parent, BD, ContextData, ++NewID);
 433     Contexts.InsertNode(L, InsertPos);
 434   }
 435   return L;
 436 }
 437
 438 //===----------------------------------------------------------------------===//
 439 // LocationContext methods.
 440 //===----------------------------------------------------------------------===//
 441
 442 const StackFrameContext *LocationContext::getStackFrame() const {
 443   const LocationContext *LC = this;
 444   while (LC) {
 445     if (const auto *SFC = dyn_cast<StackFrameContext>(LC))
 446       return SFC;
 447     LC = LC->getParent();
 448   }
 449   return nullptr;
 450 }
 451
 452 bool LocationContext::inTopFrame() const {
 453   return getStackFrame()->inTopFrame();
 454 }
 455
 456 bool LocationContext::isParentOf(const LocationContext *LC) const {
 457   do {
 458     const LocationContext *Parent = LC->getParent();
 459     if (Parent == this)
 460       return true;
 461     else
 462       LC = Parent;
 463   } while (LC);
 464
 465   return false;
 466 }
 467
 468 static void printLocation(raw_ostream &Out, const SourceManager &SM,
 469                           SourceLocation Loc) {
 470   if (Loc.isFileID() && SM.isInMainFile(Loc))
 471     Out << SM.getExpansionLineNumber(Loc);
 472   else
 473     Loc.print(Out, SM);
 474 }
 475
 476 void LocationContext::dumpStack(raw_ostream &Out, const char *NL,
 477                                 std::function<void(const LocationContext *)>
 478                                     printMoreInfoPerContext) const {
 479   ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
 480   PrintingPolicy PP(Ctx.getLangOpts());
 481   PP.TerseOutput = 1;
 482
 483   const SourceManager &SM =
 484       getAnalysisDeclContext()->getASTContext().getSourceManager();
 485
 486   unsigned Frame = 0;
 487   for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
 488     switch (LCtx->getKind()) {
 489     case StackFrame:
 490       Out << "\t#" << Frame << ' ';
 491       ++Frame;
 492       if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
 493         Out << "Calling " << D->getQualifiedNameAsString();
 494       else
 495         Out << "Calling anonymous code";
 496       if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
 497         Out << " at line ";
 498         printLocation(Out, SM, S->getBeginLoc());
 499       }
 500       break;
 501     case Scope:
 502       Out << "Entering scope";
 503       break;
 504     case Block:
 505       Out << "Invoking block";
 506       if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
 507         Out << " defined at line ";
 508         printLocation(Out, SM, D->getBeginLoc());
 509       }
 510       break;
 511     }
 512     Out << NL;
 513
 514     printMoreInfoPerContext(LCtx);
 515   }
 516 }
 517
 518 void LocationContext::printJson(raw_ostream &Out, const char *NL,
 519                                 unsigned int Space, bool IsDot,
 520                                 std::function<void(const LocationContext *)>
 521                                     printMoreInfoPerContext) const {
 522   ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
 523   PrintingPolicy PP(Ctx.getLangOpts());
 524   PP.TerseOutput = 1;
 525
 526   const SourceManager &SM =
 527       getAnalysisDeclContext()->getASTContext().getSourceManager();
 528
 529   unsigned Frame = 0;
 530   for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
 531     Indent(Out, Space, IsDot)
 532         << "{ \"lctx_id\": " << LCtx->getID() << ", \"location_context\": \"";
 533     switch (LCtx->getKind()) {
 534     case StackFrame:
 535       Out << '#' << Frame << " Call\", \"calling\": \"";
 536       ++Frame;
 537       if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
 538         Out << D->getQualifiedNameAsString();
 539       else
 540         Out << "anonymous code";
 541
 542       Out << "\", \"location\": ";
 543       if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
 544         printSourceLocationAsJson(Out, S->getBeginLoc(), SM);
 545       } else {
 546         Out << "null";
 547       }
 548
 549       Out << ", \"items\": ";
 550       break;
 551     case Scope:
 552       Out << "Entering scope\" ";
 553       break;
 554     case Block:
 555       Out << "Invoking block\" ";
 556       if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
 557         Out << ", \"location\": ";
 558         printSourceLocationAsJson(Out, D->getBeginLoc(), SM);
 559         Out << ' ';
 560       }
 561       break;
 562     }
 563
 564     printMoreInfoPerContext(LCtx);
 565
 566     Out << '}';
 567     if (LCtx->getParent())
 568       Out << ',';
 569     Out << NL;
 570   }
 571 }
 572
 573 LLVM_DUMP_METHOD void LocationContext::dump() const { printJson(llvm::errs()); }
 574
 575 //===----------------------------------------------------------------------===//
 576 // Lazily generated map to query the external variables referenced by a Block.
 577 //===----------------------------------------------------------------------===//
 578
 579 namespace {
 580
 581 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
 582   BumpVector<const VarDecl *> &BEVals;
 583   BumpVectorContext &BC;
 584   llvm::SmallPtrSet<const VarDecl *, 4> Visited;
 585   llvm::SmallPtrSet<const DeclContext *, 4> IgnoredContexts;
 586
 587 public:
 588   FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
 589                             BumpVectorContext &bc)
 590       : BEVals(bevals), BC(bc) {}
 591
 592   void VisitStmt(Stmt *S) {
 593     for (auto *Child : S->children())
 594       if (Child)
 595         Visit(Child);
 596   }
 597
 598   void VisitDeclRefExpr(DeclRefExpr *DR) {
 599     // Non-local variables are also directly modified.
 600     if (const auto *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 601       if (!VD->hasLocalStorage()) {
 602         if (Visited.insert(VD).second)
 603           BEVals.push_back(VD, BC);
 604       }
 605     }
 606   }
 607
 608   void VisitBlockExpr(BlockExpr *BR) {
 609     // Blocks containing blocks can transitively capture more variables.
 610     IgnoredContexts.insert(BR->getBlockDecl());
 611     Visit(BR->getBlockDecl()->getBody());
 612   }
 613
 614   void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
 615     for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
 616          et = PE->semantics_end(); it != et; ++it) {
 617       Expr *Semantic = *it;
 618       if (auto *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
 619         Semantic = OVE->getSourceExpr();
 620       Visit(Semantic);
 621     }
 622   }
 623 };
 624
 625 } // namespace
 626
 627 using DeclVec = BumpVector<const VarDecl *>;
 628
 629 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
 630                                               void *&Vec,
 631                                               llvm::BumpPtrAllocator &A) {
 632   if (Vec)
 633     return (DeclVec*) Vec;
 634
 635   BumpVectorContext BC(A);
 636   DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
 637   new (BV) DeclVec(BC, 10);
 638
 639   // Go through the capture list.
 640   for (const auto &CI : BD->captures()) {
 641     BV->push_back(CI.getVariable(), BC);
 642   }
 643
 644   // Find the referenced global/static variables.
 645   FindBlockDeclRefExprsVals F(*BV, BC);
 646   F.Visit(BD->getBody());
 647
 648   Vec = BV;
 649   return BV;
 650 }
 651
 652 llvm::iterator_range<AnalysisDeclContext::referenced_decls_iterator>
 653 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
 654   if (!ReferencedBlockVars)
 655     ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
 656
 657   const DeclVec *V =
 658       LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
 659   return llvm::make_range(V->begin(), V->end());
 660 }
 661
 662 ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) {
 663   if (!ManagedAnalyses)
 664     ManagedAnalyses = new ManagedAnalysisMap();
 665   ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
 666   return (*M)[tag];
 667 }
 668
 669 //===----------------------------------------------------------------------===//
 670 // Cleanup.
 671 //===----------------------------------------------------------------------===//
 672
 673 ManagedAnalysis::~ManagedAnalysis() = default;
 674
 675 AnalysisDeclContext::~AnalysisDeclContext() {
 676   delete forcedBlkExprs;
 677   delete ReferencedBlockVars;
 678   // Release the managed analyses.
 679   if (ManagedAnalyses) {
 680     ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
 681     llvm::DeleteContainerSeconds(*M);
 682     delete M;
 683   }
 684 }
 685
 686 LocationContext::~LocationContext() = default;
 687
 688 LocationContextManager::~LocationContextManager() {
 689   clear();
 690 }
 691
 692 void LocationContextManager::clear() {
 693   for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
 694        E = Contexts.end(); I != E; ) {
 695     LocationContext *LC = &*I;
 696     ++I;
 697     delete LC;
 698   }
 699   Contexts.clear();
 700 }