1 //===- AnalysisDeclContext.cpp - Analysis context for Path Sens analysis --===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines AnalysisDeclContext, a class that manages the analysis
10 // context data for path sensitive analysis.
12 //===----------------------------------------------------------------------===//
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"
51 using namespace clang;
53 using ManagedAnalysisMap = llvm::DenseMap<const void *, ManagedAnalysis *>;
55 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
57 const CFG::BuildOptions &buildOptions)
58 : Manager(Mgr), D(d), cfgBuildOptions(buildOptions) {
59 cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
62 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
64 : Manager(Mgr), D(d) {
65 cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
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;
91 void AnalysisDeclContextManager::clear() { Contexts.clear(); }
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;
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;
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();
123 llvm_unreachable("unknown code decl");
126 Stmt *AnalysisDeclContext::getBody() const {
131 bool AnalysisDeclContext::isBodyAutosynthesized() const {
137 bool AnalysisDeclContext::isBodyAutosynthesizedFromModelFile() const {
139 Stmt *Body = getBody(Tmp);
140 return Tmp && Body->getBeginLoc().isValid();
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";
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();
156 return dyn_cast<ImplicitParamDecl>(VD);
160 auto *CXXMethod = dyn_cast<CXXMethodDecl>(D);
164 const CXXRecordDecl *parent = CXXMethod->getParent();
165 if (!parent->isLambda())
168 for (const auto &LC : parent->captures()) {
169 if (!LC.capturesVariable())
172 VarDecl *VD = LC.getCapturedVar();
174 return dyn_cast<ImplicitParamDecl>(VD);
180 void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) {
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];
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());
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) {
206 for (CFG::synthetic_stmt_iterator I = TheCFG->synthetic_stmt_begin(),
207 E = TheCFG->synthetic_stmt_end();
209 PM.setParent(I->first, PM.getParent(I->second));
213 CFG *AnalysisDeclContext::getCFG() {
214 if (!cfgBuildOptions.PruneTriviallyFalseEdges)
215 return getUnoptimizedCFG();
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.
224 addParentsForSyntheticStmts(cfg.get(), *PM);
226 // The Observer should only observe one build of the CFG.
227 getCFGBuildOptions().Observer = nullptr;
232 CFG *AnalysisDeclContext::getUnoptimizedCFG() {
233 if (!builtCompleteCFG) {
234 SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges,
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;
243 addParentsForSyntheticStmts(completeCFG.get(), *PM);
245 // The Observer should only observe one build of the CFG.
246 getCFGBuildOptions().Observer = nullptr;
248 return completeCFG.get();
251 CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
253 return cfgStmtMap.get();
255 if (CFG *c = getCFG()) {
256 cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
257 return cfgStmtMap.get();
263 CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
267 if (CFG *c = getCFG()) {
268 CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
275 void AnalysisDeclContext::dumpCFG(bool ShowColors) {
276 getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
279 ParentMap &AnalysisDeclContext::getParentMap() {
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());
288 addParentsForSyntheticStmts(getCFG(), *PM);
289 if (builtCompleteCFG)
290 addParentsForSyntheticStmts(getUnoptimizedCFG(), *PM);
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.
303 std::unique_ptr<AnalysisDeclContext> &AC = Contexts[D];
305 AC = llvm::make_unique<AnalysisDeclContext>(this, D, cfgBuildOptions);
309 BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; }
311 const StackFrameContext *
312 AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
313 const CFGBlock *Blk, unsigned Idx) {
314 return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx);
317 const BlockInvocationContext *
318 AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent,
320 const void *ContextData) {
321 return getLocationContextManager().getBlockInvocationContext(this, parent,
325 bool AnalysisDeclContext::isInStdNamespace(const Decl *D) {
326 const DeclContext *DC = D->getDeclContext()->getEnclosingNamespaceContext();
327 const auto *ND = dyn_cast<NamespaceDecl>(DC);
331 while (const DeclContext *Parent = ND->getParent()) {
332 if (!isa<NamespaceDecl>(Parent))
334 ND = cast<NamespaceDecl>(Parent);
337 return ND->isStdNamespace();
340 LocationContextManager &AnalysisDeclContext::getLocationContextManager() {
342 "Cannot create LocationContexts without an AnalysisDeclContextManager!");
343 return Manager->getLocationContextManager();
346 //===----------------------------------------------------------------------===//
347 // FoldingSet profiling.
348 //===----------------------------------------------------------------------===//
350 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
352 AnalysisDeclContext *ctx,
353 const LocationContext *parent,
357 ID.AddPointer(parent);
361 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
362 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
365 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
366 Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
369 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
370 Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData);
373 //===----------------------------------------------------------------------===//
374 // LocationContext creation.
375 //===----------------------------------------------------------------------===//
377 template <typename LOC, typename DATA>
379 LocationContextManager::getLocationContext(AnalysisDeclContext *ctx,
380 const LocationContext *parent,
382 llvm::FoldingSetNodeID ID;
383 LOC::Profile(ID, ctx, parent, d);
386 LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
389 L = new LOC(ctx, parent, d, ++NewID);
390 Contexts.InsertNode(L, InsertPos);
395 const StackFrameContext*
396 LocationContextManager::getStackFrame(AnalysisDeclContext *ctx,
397 const LocationContext *parent,
399 const CFGBlock *blk, unsigned idx) {
400 llvm::FoldingSetNodeID ID;
401 StackFrameContext::Profile(ID, ctx, parent, s, blk, idx);
404 cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
406 L = new StackFrameContext(ctx, parent, s, blk, idx, ++NewID);
407 Contexts.InsertNode(L, InsertPos);
413 LocationContextManager::getScope(AnalysisDeclContext *ctx,
414 const LocationContext *parent,
416 return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
419 const BlockInvocationContext *
420 LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx,
421 const LocationContext *parent,
423 const void *ContextData) {
424 llvm::FoldingSetNodeID ID;
425 BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData);
428 cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
431 L = new BlockInvocationContext(ctx, parent, BD, ContextData, ++NewID);
432 Contexts.InsertNode(L, InsertPos);
437 //===----------------------------------------------------------------------===//
438 // LocationContext methods.
439 //===----------------------------------------------------------------------===//
441 const StackFrameContext *LocationContext::getStackFrame() const {
442 const LocationContext *LC = this;
444 if (const auto *SFC = dyn_cast<StackFrameContext>(LC))
446 LC = LC->getParent();
451 bool LocationContext::inTopFrame() const {
452 return getStackFrame()->inTopFrame();
455 bool LocationContext::isParentOf(const LocationContext *LC) const {
457 const LocationContext *Parent = LC->getParent();
467 static void printLocation(raw_ostream &Out, const SourceManager &SM,
468 SourceLocation Loc) {
469 if (Loc.isFileID() && SM.isInMainFile(Loc))
470 Out << SM.getExpansionLineNumber(Loc);
475 void LocationContext::dumpStack(raw_ostream &Out, const char *NL,
476 std::function<void(const LocationContext *)>
477 printMoreInfoPerContext) const {
478 ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
479 PrintingPolicy PP(Ctx.getLangOpts());
482 const SourceManager &SM =
483 getAnalysisDeclContext()->getASTContext().getSourceManager();
486 for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
487 switch (LCtx->getKind()) {
489 Out << "\t#" << Frame << ' ';
491 if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
492 Out << "Calling " << D->getQualifiedNameAsString();
494 Out << "Calling anonymous code";
495 if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
497 printLocation(Out, SM, S->getBeginLoc());
501 Out << "Entering scope";
504 Out << "Invoking block";
505 if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
506 Out << " defined at line ";
507 printLocation(Out, SM, D->getBeginLoc());
513 printMoreInfoPerContext(LCtx);
517 void LocationContext::printJson(raw_ostream &Out, const char *NL,
518 unsigned int Space, bool IsDot,
519 std::function<void(const LocationContext *)>
520 printMoreInfoPerContext) const {
521 ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
522 PrintingPolicy PP(Ctx.getLangOpts());
525 const SourceManager &SM =
526 getAnalysisDeclContext()->getASTContext().getSourceManager();
529 for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
530 Indent(Out, Space, IsDot)
531 << "{ \"lctx_id\": " << LCtx->getID() << ", \"location_context\": \"";
532 switch (LCtx->getKind()) {
534 Out << '#' << Frame << " Call\", \"calling\": \"";
536 if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
537 Out << D->getQualifiedNameAsString();
539 Out << "anonymous code";
541 Out << "\", \"location\": ";
542 if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
543 printSourceLocationAsJson(Out, S->getBeginLoc(), SM);
548 Out << ", \"items\": ";
551 Out << "Entering scope\" ";
554 Out << "Invoking block\" ";
555 if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
556 Out << ", \"location\": ";
557 printSourceLocationAsJson(Out, D->getBeginLoc(), SM);
563 printMoreInfoPerContext(LCtx);
566 if (LCtx->getParent())
572 LLVM_DUMP_METHOD void LocationContext::dump() const { printJson(llvm::errs()); }
574 //===----------------------------------------------------------------------===//
575 // Lazily generated map to query the external variables referenced by a Block.
576 //===----------------------------------------------------------------------===//
580 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
581 BumpVector<const VarDecl *> &BEVals;
582 BumpVectorContext &BC;
583 llvm::SmallPtrSet<const VarDecl *, 4> Visited;
584 llvm::SmallPtrSet<const DeclContext *, 4> IgnoredContexts;
587 FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
588 BumpVectorContext &bc)
589 : BEVals(bevals), BC(bc) {}
591 void VisitStmt(Stmt *S) {
592 for (auto *Child : S->children())
597 void VisitDeclRefExpr(DeclRefExpr *DR) {
598 // Non-local variables are also directly modified.
599 if (const auto *VD = dyn_cast<VarDecl>(DR->getDecl())) {
600 if (!VD->hasLocalStorage()) {
601 if (Visited.insert(VD).second)
602 BEVals.push_back(VD, BC);
607 void VisitBlockExpr(BlockExpr *BR) {
608 // Blocks containing blocks can transitively capture more variables.
609 IgnoredContexts.insert(BR->getBlockDecl());
610 Visit(BR->getBlockDecl()->getBody());
613 void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
614 for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
615 et = PE->semantics_end(); it != et; ++it) {
616 Expr *Semantic = *it;
617 if (auto *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
618 Semantic = OVE->getSourceExpr();
626 using DeclVec = BumpVector<const VarDecl *>;
628 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
630 llvm::BumpPtrAllocator &A) {
632 return (DeclVec*) Vec;
634 BumpVectorContext BC(A);
635 DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
636 new (BV) DeclVec(BC, 10);
638 // Go through the capture list.
639 for (const auto &CI : BD->captures()) {
640 BV->push_back(CI.getVariable(), BC);
643 // Find the referenced global/static variables.
644 FindBlockDeclRefExprsVals F(*BV, BC);
645 F.Visit(BD->getBody());
651 llvm::iterator_range<AnalysisDeclContext::referenced_decls_iterator>
652 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
653 if (!ReferencedBlockVars)
654 ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
657 LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
658 return llvm::make_range(V->begin(), V->end());
661 ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) {
662 if (!ManagedAnalyses)
663 ManagedAnalyses = new ManagedAnalysisMap();
664 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
668 //===----------------------------------------------------------------------===//
670 //===----------------------------------------------------------------------===//
672 ManagedAnalysis::~ManagedAnalysis() = default;
674 AnalysisDeclContext::~AnalysisDeclContext() {
675 delete forcedBlkExprs;
676 delete ReferencedBlockVars;
677 // Release the managed analyses.
678 if (ManagedAnalyses) {
679 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
680 llvm::DeleteContainerSeconds(*M);
685 LocationContext::~LocationContext() = default;
687 LocationContextManager::~LocationContextManager() {
691 void LocationContextManager::clear() {
692 for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
693 E = Contexts.end(); I != E; ) {
694 LocationContext *LC = &*I;