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