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 *, std::unique_ptr<ManagedAnalysis>>;
55 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *ADCMgr,
57 const CFG::BuildOptions &Options)
58 : ADCMgr(ADCMgr), D(D), cfgBuildOptions(Options) {
59 cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
62 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *ADCMgr,
64 : ADCMgr(ADCMgr), 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 (ADCMgr && ADCMgr->synthesizeBodies()) {
100 Stmt *SynthesizedBody = ADCMgr->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 (ADCMgr && ADCMgr->synthesizeBodies()) {
111 Stmt *SynthesizedBody = ADCMgr->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 = std::make_unique<AnalysisDeclContext>(this, D, cfgBuildOptions);
309 BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; }
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,
319 const BlockInvocationContext *AnalysisDeclContext::getBlockInvocationContext(
320 const LocationContext *ParentLC, const BlockDecl *BD, const void *Data) {
321 return getLocationContextManager().getBlockInvocationContext(this, ParentLC,
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() {
343 "Cannot create LocationContexts without an AnalysisDeclContextManager!");
344 return ADCMgr->getLocationContextManager();
347 //===----------------------------------------------------------------------===//
348 // FoldingSet profiling.
349 //===----------------------------------------------------------------------===//
351 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
353 AnalysisDeclContext *ctx,
354 const LocationContext *parent,
358 ID.AddPointer(parent);
362 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
363 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block,
367 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
368 Profile(ID, getAnalysisDeclContext(), getParent(), BD, Data);
371 //===----------------------------------------------------------------------===//
372 // LocationContext creation.
373 //===----------------------------------------------------------------------===//
375 const StackFrameContext *LocationContextManager::getStackFrame(
376 AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s,
377 const CFGBlock *blk, unsigned blockCount, unsigned idx) {
378 llvm::FoldingSetNodeID ID;
379 StackFrameContext::Profile(ID, ctx, parent, s, blk, blockCount, idx);
382 cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
384 L = new StackFrameContext(ctx, parent, s, blk, blockCount, idx, ++NewID);
385 Contexts.InsertNode(L, InsertPos);
390 const BlockInvocationContext *LocationContextManager::getBlockInvocationContext(
391 AnalysisDeclContext *ADC, const LocationContext *ParentLC,
392 const BlockDecl *BD, const void *Data) {
393 llvm::FoldingSetNodeID ID;
394 BlockInvocationContext::Profile(ID, ADC, ParentLC, BD, Data);
397 cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
400 L = new BlockInvocationContext(ADC, ParentLC, BD, Data, ++NewID);
401 Contexts.InsertNode(L, InsertPos);
406 //===----------------------------------------------------------------------===//
407 // LocationContext methods.
408 //===----------------------------------------------------------------------===//
410 const StackFrameContext *LocationContext::getStackFrame() const {
411 const LocationContext *LC = this;
413 if (const auto *SFC = dyn_cast<StackFrameContext>(LC))
415 LC = LC->getParent();
420 bool LocationContext::inTopFrame() const {
421 return getStackFrame()->inTopFrame();
424 bool LocationContext::isParentOf(const LocationContext *LC) const {
426 const LocationContext *Parent = LC->getParent();
436 static void printLocation(raw_ostream &Out, const SourceManager &SM,
437 SourceLocation Loc) {
438 if (Loc.isFileID() && SM.isInMainFile(Loc))
439 Out << SM.getExpansionLineNumber(Loc);
444 void LocationContext::dumpStack(raw_ostream &Out) const {
445 ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
446 PrintingPolicy PP(Ctx.getLangOpts());
449 const SourceManager &SM =
450 getAnalysisDeclContext()->getASTContext().getSourceManager();
453 for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
454 switch (LCtx->getKind()) {
456 Out << "\t#" << Frame << ' ';
458 if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
459 Out << "Calling " << D->getQualifiedNameAsString();
461 Out << "Calling anonymous code";
462 if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
464 printLocation(Out, SM, S->getBeginLoc());
468 Out << "Invoking block";
469 if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
470 Out << " defined at line ";
471 printLocation(Out, SM, D->getBeginLoc());
479 void LocationContext::printJson(raw_ostream &Out, const char *NL,
480 unsigned int Space, bool IsDot,
481 std::function<void(const LocationContext *)>
482 printMoreInfoPerContext) const {
483 ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
484 PrintingPolicy PP(Ctx.getLangOpts());
487 const SourceManager &SM =
488 getAnalysisDeclContext()->getASTContext().getSourceManager();
491 for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
492 Indent(Out, Space, IsDot)
493 << "{ \"lctx_id\": " << LCtx->getID() << ", \"location_context\": \"";
494 switch (LCtx->getKind()) {
496 Out << '#' << Frame << " Call\", \"calling\": \"";
498 if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
499 Out << D->getQualifiedNameAsString();
501 Out << "anonymous code";
503 Out << "\", \"location\": ";
504 if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
505 printSourceLocationAsJson(Out, S->getBeginLoc(), SM);
510 Out << ", \"items\": ";
513 Out << "Invoking block\" ";
514 if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
515 Out << ", \"location\": ";
516 printSourceLocationAsJson(Out, D->getBeginLoc(), SM);
522 printMoreInfoPerContext(LCtx);
525 if (LCtx->getParent())
531 LLVM_DUMP_METHOD void LocationContext::dump() const { printJson(llvm::errs()); }
533 //===----------------------------------------------------------------------===//
534 // Lazily generated map to query the external variables referenced by a Block.
535 //===----------------------------------------------------------------------===//
539 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
540 BumpVector<const VarDecl *> &BEVals;
541 BumpVectorContext &BC;
542 llvm::SmallPtrSet<const VarDecl *, 4> Visited;
543 llvm::SmallPtrSet<const DeclContext *, 4> IgnoredContexts;
546 FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
547 BumpVectorContext &bc)
548 : BEVals(bevals), BC(bc) {}
550 void VisitStmt(Stmt *S) {
551 for (auto *Child : S->children())
556 void VisitDeclRefExpr(DeclRefExpr *DR) {
557 // Non-local variables are also directly modified.
558 if (const auto *VD = dyn_cast<VarDecl>(DR->getDecl())) {
559 if (!VD->hasLocalStorage()) {
560 if (Visited.insert(VD).second)
561 BEVals.push_back(VD, BC);
566 void VisitBlockExpr(BlockExpr *BR) {
567 // Blocks containing blocks can transitively capture more variables.
568 IgnoredContexts.insert(BR->getBlockDecl());
569 Visit(BR->getBlockDecl()->getBody());
572 void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
573 for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
574 et = PE->semantics_end(); it != et; ++it) {
575 Expr *Semantic = *it;
576 if (auto *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
577 Semantic = OVE->getSourceExpr();
585 using DeclVec = BumpVector<const VarDecl *>;
587 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
589 llvm::BumpPtrAllocator &A) {
591 return (DeclVec*) Vec;
593 BumpVectorContext BC(A);
594 DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
595 new (BV) DeclVec(BC, 10);
597 // Go through the capture list.
598 for (const auto &CI : BD->captures()) {
599 BV->push_back(CI.getVariable(), BC);
602 // Find the referenced global/static variables.
603 FindBlockDeclRefExprsVals F(*BV, BC);
604 F.Visit(BD->getBody());
610 llvm::iterator_range<AnalysisDeclContext::referenced_decls_iterator>
611 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
612 if (!ReferencedBlockVars)
613 ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
616 LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
617 return llvm::make_range(V->begin(), V->end());
620 std::unique_ptr<ManagedAnalysis> &AnalysisDeclContext::getAnalysisImpl(const void *tag) {
621 if (!ManagedAnalyses)
622 ManagedAnalyses = new ManagedAnalysisMap();
623 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
627 //===----------------------------------------------------------------------===//
629 //===----------------------------------------------------------------------===//
631 ManagedAnalysis::~ManagedAnalysis() = default;
633 AnalysisDeclContext::~AnalysisDeclContext() {
634 delete forcedBlkExprs;
635 delete ReferencedBlockVars;
636 delete (ManagedAnalysisMap*) ManagedAnalyses;
639 LocationContext::~LocationContext() = default;
641 LocationContextManager::~LocationContextManager() {
645 void LocationContextManager::clear() {
646 for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
647 E = Contexts.end(); I != E; ) {
648 LocationContext *LC = &*I;