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