xref: /freebsd/contrib/llvm-project/clang/lib/Analysis/AnalysisDeclContext.cpp (revision 5956d97f4b3204318ceb6aa9c77bd0bc6ea87a41) 
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 *, std::unique_ptr<ManagedAnalysis>>;
54 
55 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *ADCMgr,
56                                          const Decl *D,
57                                          const CFG::BuildOptions &Options)
58     : ADCMgr(ADCMgr), D(D), cfgBuildOptions(Options) {
59   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
60 }
61 
62 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *ADCMgr,
63                                          const Decl *D)
64     : ADCMgr(ADCMgr), 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 (ADCMgr && ADCMgr->synthesizeBodies()) {
100       Stmt *SynthesizedBody = ADCMgr->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 (ADCMgr && ADCMgr->synthesizeBodies()) {
111       Stmt *SynthesizedBody = ADCMgr->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(const LocationContext *ParentLC,
313                                    const Stmt *S, const CFGBlock *Blk,
314                                    unsigned BlockCount, unsigned Index) {
315   return getLocationContextManager().getStackFrame(this, ParentLC, S, Blk,
316                                                    BlockCount, Index);
317 }
318 
319 const BlockInvocationContext *AnalysisDeclContext::getBlockInvocationContext(
320     const LocationContext *ParentLC, const BlockDecl *BD, const void *Data) {
321   return getLocationContextManager().getBlockInvocationContext(this, ParentLC,
322                                                                BD, Data);
323 }
324 
325 bool AnalysisDeclContext::isInStdNamespace(const Decl *D) {
326   const DeclContext *DC = D->getDeclContext()->getEnclosingNamespaceContext();
327   const auto *ND = dyn_cast<NamespaceDecl>(DC);
328   if (!ND)
329     return false;
330 
331   while (const DeclContext *Parent = ND->getParent()) {
332     if (!isa<NamespaceDecl>(Parent))
333       break;
334     ND = cast<NamespaceDecl>(Parent);
335   }
336 
337   return ND->isStdNamespace();
338 }
339 
340 std::string AnalysisDeclContext::getFunctionName(const Decl *D) {
341   std::string Str;
342   llvm::raw_string_ostream OS(Str);
343   const ASTContext &Ctx = D->getASTContext();
344 
345   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
346     OS << FD->getQualifiedNameAsString();
347 
348     // In C++, there are overloads.
349 
350     if (Ctx.getLangOpts().CPlusPlus) {
351       OS << '(';
352       for (const auto &P : FD->parameters()) {
353         if (P != *FD->param_begin())
354           OS << ", ";
355         OS << P->getType().getAsString();
356       }
357       OS << ')';
358     }
359 
360   } else if (isa<BlockDecl>(D)) {
361     PresumedLoc Loc = Ctx.getSourceManager().getPresumedLoc(D->getLocation());
362 
363     if (Loc.isValid()) {
364       OS << "block (line: " << Loc.getLine() << ", col: " << Loc.getColumn()
365          << ')';
366     }
367 
368   } else if (const ObjCMethodDecl *OMD = dyn_cast<ObjCMethodDecl>(D)) {
369 
370     // FIXME: copy-pasted from CGDebugInfo.cpp.
371     OS << (OMD->isInstanceMethod() ? '-' : '+') << '[';
372     const DeclContext *DC = OMD->getDeclContext();
373     if (const auto *OID = dyn_cast<ObjCImplementationDecl>(DC)) {
374       OS << OID->getName();
375     } else if (const auto *OID = dyn_cast<ObjCInterfaceDecl>(DC)) {
376       OS << OID->getName();
377     } else if (const auto *OC = dyn_cast<ObjCCategoryDecl>(DC)) {
378       if (OC->IsClassExtension()) {
379         OS << OC->getClassInterface()->getName();
380       } else {
381         OS << OC->getIdentifier()->getNameStart() << '('
382            << OC->getIdentifier()->getNameStart() << ')';
383       }
384     } else if (const auto *OCD = dyn_cast<ObjCCategoryImplDecl>(DC)) {
385       OS << OCD->getClassInterface()->getName() << '(' << OCD->getName() << ')';
386     }
387     OS << ' ' << OMD->getSelector().getAsString() << ']';
388   }
389 
390   return Str;
391 }
392 
393 LocationContextManager &AnalysisDeclContext::getLocationContextManager() {
394   assert(
395       ADCMgr &&
396       "Cannot create LocationContexts without an AnalysisDeclContextManager!");
397   return ADCMgr->getLocationContextManager();
398 }
399 
400 //===----------------------------------------------------------------------===//
401 // FoldingSet profiling.
402 //===----------------------------------------------------------------------===//
403 
404 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
405                                     ContextKind ck,
406                                     AnalysisDeclContext *ctx,
407                                     const LocationContext *parent,
408                                     const void *data) {
409   ID.AddInteger(ck);
410   ID.AddPointer(ctx);
411   ID.AddPointer(parent);
412   ID.AddPointer(data);
413 }
414 
415 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
416   Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block,
417           BlockCount, Index);
418 }
419 
420 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
421   Profile(ID, getAnalysisDeclContext(), getParent(), BD, Data);
422 }
423 
424 //===----------------------------------------------------------------------===//
425 // LocationContext creation.
426 //===----------------------------------------------------------------------===//
427 
428 const StackFrameContext *LocationContextManager::getStackFrame(
429     AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s,
430     const CFGBlock *blk, unsigned blockCount, unsigned idx) {
431   llvm::FoldingSetNodeID ID;
432   StackFrameContext::Profile(ID, ctx, parent, s, blk, blockCount, idx);
433   void *InsertPos;
434   auto *L =
435    cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
436   if (!L) {
437     L = new StackFrameContext(ctx, parent, s, blk, blockCount, idx, ++NewID);
438     Contexts.InsertNode(L, InsertPos);
439   }
440   return L;
441 }
442 
443 const BlockInvocationContext *LocationContextManager::getBlockInvocationContext(
444     AnalysisDeclContext *ADC, const LocationContext *ParentLC,
445     const BlockDecl *BD, const void *Data) {
446   llvm::FoldingSetNodeID ID;
447   BlockInvocationContext::Profile(ID, ADC, ParentLC, BD, Data);
448   void *InsertPos;
449   auto *L =
450     cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
451                                                                     InsertPos));
452   if (!L) {
453     L = new BlockInvocationContext(ADC, ParentLC, BD, Data, ++NewID);
454     Contexts.InsertNode(L, InsertPos);
455   }
456   return L;
457 }
458 
459 //===----------------------------------------------------------------------===//
460 // LocationContext methods.
461 //===----------------------------------------------------------------------===//
462 
463 const StackFrameContext *LocationContext::getStackFrame() const {
464   const LocationContext *LC = this;
465   while (LC) {
466     if (const auto *SFC = dyn_cast<StackFrameContext>(LC))
467       return SFC;
468     LC = LC->getParent();
469   }
470   return nullptr;
471 }
472 
473 bool LocationContext::inTopFrame() const {
474   return getStackFrame()->inTopFrame();
475 }
476 
477 bool LocationContext::isParentOf(const LocationContext *LC) const {
478   do {
479     const LocationContext *Parent = LC->getParent();
480     if (Parent == this)
481       return true;
482     else
483       LC = Parent;
484   } while (LC);
485 
486   return false;
487 }
488 
489 static void printLocation(raw_ostream &Out, const SourceManager &SM,
490                           SourceLocation Loc) {
491   if (Loc.isFileID() && SM.isInMainFile(Loc))
492     Out << SM.getExpansionLineNumber(Loc);
493   else
494     Loc.print(Out, SM);
495 }
496 
497 void LocationContext::dumpStack(raw_ostream &Out) const {
498   ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
499   PrintingPolicy PP(Ctx.getLangOpts());
500   PP.TerseOutput = 1;
501 
502   const SourceManager &SM =
503       getAnalysisDeclContext()->getASTContext().getSourceManager();
504 
505   unsigned Frame = 0;
506   for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
507     switch (LCtx->getKind()) {
508     case StackFrame:
509       Out << "\t#" << Frame << ' ';
510       ++Frame;
511       if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
512         Out << "Calling " << AnalysisDeclContext::getFunctionName(D);
513       else
514         Out << "Calling anonymous code";
515       if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
516         Out << " at line ";
517         printLocation(Out, SM, S->getBeginLoc());
518       }
519       break;
520     case Block:
521       Out << "Invoking block";
522       if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
523         Out << " defined at line ";
524         printLocation(Out, SM, D->getBeginLoc());
525       }
526       break;
527     }
528     Out << '\n';
529   }
530 }
531 
532 void LocationContext::printJson(raw_ostream &Out, const char *NL,
533                                 unsigned int Space, bool IsDot,
534                                 std::function<void(const LocationContext *)>
535                                     printMoreInfoPerContext) const {
536   ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
537   PrintingPolicy PP(Ctx.getLangOpts());
538   PP.TerseOutput = 1;
539 
540   const SourceManager &SM =
541       getAnalysisDeclContext()->getASTContext().getSourceManager();
542 
543   unsigned Frame = 0;
544   for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
545     Indent(Out, Space, IsDot)
546         << "{ \"lctx_id\": " << LCtx->getID() << ", \"location_context\": \"";
547     switch (LCtx->getKind()) {
548     case StackFrame:
549       Out << '#' << Frame << " Call\", \"calling\": \"";
550       ++Frame;
551       if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
552         Out << D->getQualifiedNameAsString();
553       else
554         Out << "anonymous code";
555 
556       Out << "\", \"location\": ";
557       if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
558         printSourceLocationAsJson(Out, S->getBeginLoc(), SM);
559       } else {
560         Out << "null";
561       }
562 
563       Out << ", \"items\": ";
564       break;
565     case Block:
566       Out << "Invoking block\" ";
567       if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
568         Out << ", \"location\": ";
569         printSourceLocationAsJson(Out, D->getBeginLoc(), SM);
570         Out << ' ';
571       }
572       break;
573     }
574 
575     printMoreInfoPerContext(LCtx);
576 
577     Out << '}';
578     if (LCtx->getParent())
579       Out << ',';
580     Out << NL;
581   }
582 }
583 
584 LLVM_DUMP_METHOD void LocationContext::dump() const { printJson(llvm::errs()); }
585 
586 //===----------------------------------------------------------------------===//
587 // Lazily generated map to query the external variables referenced by a Block.
588 //===----------------------------------------------------------------------===//
589 
590 namespace {
591 
592 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
593   BumpVector<const VarDecl *> &BEVals;
594   BumpVectorContext &BC;
595   llvm::SmallPtrSet<const VarDecl *, 4> Visited;
596   llvm::SmallPtrSet<const DeclContext *, 4> IgnoredContexts;
597 
598 public:
599   FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
600                             BumpVectorContext &bc)
601       : BEVals(bevals), BC(bc) {}
602 
603   void VisitStmt(Stmt *S) {
604     for (auto *Child : S->children())
605       if (Child)
606         Visit(Child);
607   }
608 
609   void VisitDeclRefExpr(DeclRefExpr *DR) {
610     // Non-local variables are also directly modified.
611     if (const auto *VD = dyn_cast<VarDecl>(DR->getDecl())) {
612       if (!VD->hasLocalStorage()) {
613         if (Visited.insert(VD).second)
614           BEVals.push_back(VD, BC);
615       }
616     }
617   }
618 
619   void VisitBlockExpr(BlockExpr *BR) {
620     // Blocks containing blocks can transitively capture more variables.
621     IgnoredContexts.insert(BR->getBlockDecl());
622     Visit(BR->getBlockDecl()->getBody());
623   }
624 
625   void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
626     for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
627          et = PE->semantics_end(); it != et; ++it) {
628       Expr *Semantic = *it;
629       if (auto *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
630         Semantic = OVE->getSourceExpr();
631       Visit(Semantic);
632     }
633   }
634 };
635 
636 } // namespace
637 
638 using DeclVec = BumpVector<const VarDecl *>;
639 
640 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
641                                               void *&Vec,
642                                               llvm::BumpPtrAllocator &A) {
643   if (Vec)
644     return (DeclVec*) Vec;
645 
646   BumpVectorContext BC(A);
647   DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
648   new (BV) DeclVec(BC, 10);
649 
650   // Go through the capture list.
651   for (const auto &CI : BD->captures()) {
652     BV->push_back(CI.getVariable(), BC);
653   }
654 
655   // Find the referenced global/static variables.
656   FindBlockDeclRefExprsVals F(*BV, BC);
657   F.Visit(BD->getBody());
658 
659   Vec = BV;
660   return BV;
661 }
662 
663 llvm::iterator_range<AnalysisDeclContext::referenced_decls_iterator>
664 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
665   if (!ReferencedBlockVars)
666     ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
667 
668   const DeclVec *V =
669       LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
670   return llvm::make_range(V->begin(), V->end());
671 }
672 
673 std::unique_ptr<ManagedAnalysis> &AnalysisDeclContext::getAnalysisImpl(const void *tag) {
674   if (!ManagedAnalyses)
675     ManagedAnalyses = new ManagedAnalysisMap();
676   ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
677   return (*M)[tag];
678 }
679 
680 //===----------------------------------------------------------------------===//
681 // Cleanup.
682 //===----------------------------------------------------------------------===//
683 
684 ManagedAnalysis::~ManagedAnalysis() = default;
685 
686 AnalysisDeclContext::~AnalysisDeclContext() {
687   delete forcedBlkExprs;
688   delete ReferencedBlockVars;
689   delete (ManagedAnalysisMap*) ManagedAnalyses;
690 }
691 
692 LocationContext::~LocationContext() = default;
693 
694 LocationContextManager::~LocationContextManager() {
695   clear();
696 }
697 
698 void LocationContextManager::clear() {
699   for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
700        E = Contexts.end(); I != E; ) {
701     LocationContext *LC = &*I;
702     ++I;
703     delete LC;
704   }
705   Contexts.clear();
706 }
707