1 //===- AnalysisDeclContext.cpp - Analysis context for Path Sens analysis --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines AnalysisDeclContext, a class that manages the analysis
11 // context data for path sensitive analysis.
13 //===----------------------------------------------------------------------===//
15 #include "clang/Analysis/AnalysisDeclContext.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/Decl.h"
18 #include "clang/AST/DeclBase.h"
19 #include "clang/AST/DeclCXX.h"
20 #include "clang/AST/DeclObjC.h"
21 #include "clang/AST/DeclTemplate.h"
22 #include "clang/AST/Expr.h"
23 #include "clang/AST/LambdaCapture.h"
24 #include "clang/AST/ParentMap.h"
25 #include "clang/AST/PrettyPrinter.h"
26 #include "clang/AST/Stmt.h"
27 #include "clang/AST/StmtCXX.h"
28 #include "clang/AST/StmtVisitor.h"
29 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
30 #include "clang/Analysis/BodyFarm.h"
31 #include "clang/Analysis/CFG.h"
32 #include "clang/Analysis/CFGStmtMap.h"
33 #include "clang/Analysis/Support/BumpVector.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 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;
90 void AnalysisDeclContextManager::clear() { Contexts.clear(); }
92 Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const {
93 IsAutosynthesized = false;
94 if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
95 Stmt *Body = FD->getBody();
96 if (auto *CoroBody = dyn_cast_or_null<CoroutineBodyStmt>(Body))
97 Body = CoroBody->getBody();
98 if (Manager && Manager->synthesizeBodies()) {
99 Stmt *SynthesizedBody = Manager->getBodyFarm().getBody(FD);
100 if (SynthesizedBody) {
101 Body = SynthesizedBody;
102 IsAutosynthesized = true;
107 else if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
108 Stmt *Body = MD->getBody();
109 if (Manager && Manager->synthesizeBodies()) {
110 Stmt *SynthesizedBody = Manager->getBodyFarm().getBody(MD);
111 if (SynthesizedBody) {
112 Body = SynthesizedBody;
113 IsAutosynthesized = true;
117 } else if (const auto *BD = dyn_cast<BlockDecl>(D))
118 return BD->getBody();
119 else if (const auto *FunTmpl = dyn_cast_or_null<FunctionTemplateDecl>(D))
120 return FunTmpl->getTemplatedDecl()->getBody();
122 llvm_unreachable("unknown code decl");
125 Stmt *AnalysisDeclContext::getBody() const {
130 bool AnalysisDeclContext::isBodyAutosynthesized() const {
136 bool AnalysisDeclContext::isBodyAutosynthesizedFromModelFile() const {
138 Stmt *Body = getBody(Tmp);
139 return Tmp && Body->getBeginLoc().isValid();
142 /// Returns true if \param VD is an Objective-C implicit 'self' parameter.
143 static bool isSelfDecl(const VarDecl *VD) {
144 return isa<ImplicitParamDecl>(VD) && VD->getName() == "self";
147 const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const {
148 if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
149 return MD->getSelfDecl();
150 if (const auto *BD = dyn_cast<BlockDecl>(D)) {
151 // See if 'self' was captured by the block.
152 for (const auto &I : BD->captures()) {
153 const VarDecl *VD = I.getVariable();
155 return dyn_cast<ImplicitParamDecl>(VD);
159 auto *CXXMethod = dyn_cast<CXXMethodDecl>(D);
163 const CXXRecordDecl *parent = CXXMethod->getParent();
164 if (!parent->isLambda())
167 for (const auto &LC : parent->captures()) {
168 if (!LC.capturesVariable())
171 VarDecl *VD = LC.getCapturedVar();
173 return dyn_cast<ImplicitParamDecl>(VD);
179 void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) {
181 forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs();
182 // Default construct an entry for 'stmt'.
183 if (const auto *e = dyn_cast<Expr>(stmt))
184 stmt = e->IgnoreParens();
185 (void) (*forcedBlkExprs)[stmt];
189 AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) {
190 assert(forcedBlkExprs);
191 if (const auto *e = dyn_cast<Expr>(stmt))
192 stmt = e->IgnoreParens();
193 CFG::BuildOptions::ForcedBlkExprs::const_iterator itr =
194 forcedBlkExprs->find(stmt);
195 assert(itr != forcedBlkExprs->end());
199 /// Add each synthetic statement in the CFG to the parent map, using the
200 /// source statement's parent.
201 static void addParentsForSyntheticStmts(const CFG *TheCFG, ParentMap &PM) {
205 for (CFG::synthetic_stmt_iterator I = TheCFG->synthetic_stmt_begin(),
206 E = TheCFG->synthetic_stmt_end();
208 PM.setParent(I->first, PM.getParent(I->second));
212 CFG *AnalysisDeclContext::getCFG() {
213 if (!cfgBuildOptions.PruneTriviallyFalseEdges)
214 return getUnoptimizedCFG();
217 cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), cfgBuildOptions);
218 // Even when the cfg is not successfully built, we don't
219 // want to try building it again.
223 addParentsForSyntheticStmts(cfg.get(), *PM);
225 // The Observer should only observe one build of the CFG.
226 getCFGBuildOptions().Observer = nullptr;
231 CFG *AnalysisDeclContext::getUnoptimizedCFG() {
232 if (!builtCompleteCFG) {
233 SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges,
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;
242 addParentsForSyntheticStmts(completeCFG.get(), *PM);
244 // The Observer should only observe one build of the CFG.
245 getCFGBuildOptions().Observer = nullptr;
247 return completeCFG.get();
250 CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
252 return cfgStmtMap.get();
254 if (CFG *c = getCFG()) {
255 cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
256 return cfgStmtMap.get();
262 CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
266 if (CFG *c = getCFG()) {
267 CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
274 void AnalysisDeclContext::dumpCFG(bool ShowColors) {
275 getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
278 ParentMap &AnalysisDeclContext::getParentMap() {
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());
287 addParentsForSyntheticStmts(getCFG(), *PM);
288 if (builtCompleteCFG)
289 addParentsForSyntheticStmts(getUnoptimizedCFG(), *PM);
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.
302 std::unique_ptr<AnalysisDeclContext> &AC = Contexts[D];
304 AC = llvm::make_unique<AnalysisDeclContext>(this, D, cfgBuildOptions);
308 BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; }
310 const StackFrameContext *
311 AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
312 const CFGBlock *Blk, unsigned Idx) {
313 return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx);
316 const BlockInvocationContext *
317 AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent,
319 const void *ContextData) {
320 return getLocationContextManager().getBlockInvocationContext(this, parent,
324 bool AnalysisDeclContext::isInStdNamespace(const Decl *D) {
325 const DeclContext *DC = D->getDeclContext()->getEnclosingNamespaceContext();
326 const auto *ND = dyn_cast<NamespaceDecl>(DC);
330 while (const DeclContext *Parent = ND->getParent()) {
331 if (!isa<NamespaceDecl>(Parent))
333 ND = cast<NamespaceDecl>(Parent);
336 return ND->isStdNamespace();
339 LocationContextManager &AnalysisDeclContext::getLocationContextManager() {
341 "Cannot create LocationContexts without an AnalysisDeclContextManager!");
342 return Manager->getLocationContextManager();
345 //===----------------------------------------------------------------------===//
346 // FoldingSet profiling.
347 //===----------------------------------------------------------------------===//
349 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
351 AnalysisDeclContext *ctx,
352 const LocationContext *parent,
356 ID.AddPointer(parent);
360 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
361 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
364 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
365 Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
368 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
369 Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData);
372 //===----------------------------------------------------------------------===//
373 // LocationContext creation.
374 //===----------------------------------------------------------------------===//
376 template <typename LOC, typename DATA>
378 LocationContextManager::getLocationContext(AnalysisDeclContext *ctx,
379 const LocationContext *parent,
381 llvm::FoldingSetNodeID ID;
382 LOC::Profile(ID, ctx, parent, d);
385 LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
388 L = new LOC(ctx, parent, d, ++NewID);
389 Contexts.InsertNode(L, InsertPos);
394 const StackFrameContext*
395 LocationContextManager::getStackFrame(AnalysisDeclContext *ctx,
396 const LocationContext *parent,
398 const CFGBlock *blk, unsigned idx) {
399 llvm::FoldingSetNodeID ID;
400 StackFrameContext::Profile(ID, ctx, parent, s, blk, idx);
403 cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
405 L = new StackFrameContext(ctx, parent, s, blk, idx, ++NewID);
406 Contexts.InsertNode(L, InsertPos);
412 LocationContextManager::getScope(AnalysisDeclContext *ctx,
413 const LocationContext *parent,
415 return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
418 const BlockInvocationContext *
419 LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx,
420 const LocationContext *parent,
422 const void *ContextData) {
423 llvm::FoldingSetNodeID ID;
424 BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData);
427 cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
430 L = new BlockInvocationContext(ctx, parent, BD, ContextData, ++NewID);
431 Contexts.InsertNode(L, InsertPos);
436 //===----------------------------------------------------------------------===//
437 // LocationContext methods.
438 //===----------------------------------------------------------------------===//
440 const StackFrameContext *LocationContext::getStackFrame() const {
441 const LocationContext *LC = this;
443 if (const auto *SFC = dyn_cast<StackFrameContext>(LC))
445 LC = LC->getParent();
450 bool LocationContext::inTopFrame() const {
451 return getStackFrame()->inTopFrame();
454 bool LocationContext::isParentOf(const LocationContext *LC) const {
456 const LocationContext *Parent = LC->getParent();
466 static void printLocation(raw_ostream &OS, const SourceManager &SM,
467 SourceLocation SLoc) {
468 if (SLoc.isFileID() && SM.isInMainFile(SLoc))
469 OS << "line " << SM.getExpansionLineNumber(SLoc);
474 void LocationContext::dumpStack(
475 raw_ostream &OS, StringRef Indent, const char *NL, const char *Sep,
476 std::function<void(const LocationContext *)> printMoreInfoPerContext) const {
477 ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
478 PrintingPolicy PP(Ctx.getLangOpts());
481 const SourceManager &SM =
482 getAnalysisDeclContext()->getASTContext().getSourceManager();
485 for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
486 switch (LCtx->getKind()) {
488 OS << Indent << '#' << Frame << ' ';
490 if (const auto *D = dyn_cast<NamedDecl>(LCtx->getDecl()))
491 OS << "Calling " << D->getQualifiedNameAsString();
493 OS << "Calling anonymous code";
494 if (const Stmt *S = cast<StackFrameContext>(LCtx)->getCallSite()) {
496 printLocation(OS, SM, S->getBeginLoc());
500 OS << "Entering scope";
503 OS << "Invoking block";
504 if (const Decl *D = cast<BlockInvocationContext>(LCtx)->getDecl()) {
505 OS << " defined at ";
506 printLocation(OS, SM, D->getBeginLoc());
512 printMoreInfoPerContext(LCtx);
516 LLVM_DUMP_METHOD void LocationContext::dumpStack() const {
517 dumpStack(llvm::errs());
520 //===----------------------------------------------------------------------===//
521 // Lazily generated map to query the external variables referenced by a Block.
522 //===----------------------------------------------------------------------===//
526 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
527 BumpVector<const VarDecl *> &BEVals;
528 BumpVectorContext &BC;
529 llvm::SmallPtrSet<const VarDecl *, 4> Visited;
530 llvm::SmallPtrSet<const DeclContext *, 4> IgnoredContexts;
533 FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
534 BumpVectorContext &bc)
535 : BEVals(bevals), BC(bc) {}
537 void VisitStmt(Stmt *S) {
538 for (auto *Child : S->children())
543 void VisitDeclRefExpr(DeclRefExpr *DR) {
544 // Non-local variables are also directly modified.
545 if (const auto *VD = dyn_cast<VarDecl>(DR->getDecl())) {
546 if (!VD->hasLocalStorage()) {
547 if (Visited.insert(VD).second)
548 BEVals.push_back(VD, BC);
553 void VisitBlockExpr(BlockExpr *BR) {
554 // Blocks containing blocks can transitively capture more variables.
555 IgnoredContexts.insert(BR->getBlockDecl());
556 Visit(BR->getBlockDecl()->getBody());
559 void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
560 for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
561 et = PE->semantics_end(); it != et; ++it) {
562 Expr *Semantic = *it;
563 if (auto *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
564 Semantic = OVE->getSourceExpr();
572 using DeclVec = BumpVector<const VarDecl *>;
574 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
576 llvm::BumpPtrAllocator &A) {
578 return (DeclVec*) Vec;
580 BumpVectorContext BC(A);
581 DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
582 new (BV) DeclVec(BC, 10);
584 // Go through the capture list.
585 for (const auto &CI : BD->captures()) {
586 BV->push_back(CI.getVariable(), BC);
589 // Find the referenced global/static variables.
590 FindBlockDeclRefExprsVals F(*BV, BC);
591 F.Visit(BD->getBody());
597 llvm::iterator_range<AnalysisDeclContext::referenced_decls_iterator>
598 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
599 if (!ReferencedBlockVars)
600 ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
603 LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
604 return llvm::make_range(V->begin(), V->end());
607 ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) {
608 if (!ManagedAnalyses)
609 ManagedAnalyses = new ManagedAnalysisMap();
610 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
614 //===----------------------------------------------------------------------===//
616 //===----------------------------------------------------------------------===//
618 ManagedAnalysis::~ManagedAnalysis() = default;
620 AnalysisDeclContext::~AnalysisDeclContext() {
621 delete forcedBlkExprs;
622 delete ReferencedBlockVars;
623 // Release the managed analyses.
624 if (ManagedAnalyses) {
625 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
626 llvm::DeleteContainerSeconds(*M);
631 LocationContext::~LocationContext() = default;
633 LocationContextManager::~LocationContextManager() {
637 void LocationContextManager::clear() {
638 for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
639 E = Contexts.end(); I != E; ) {
640 LocationContext *LC = &*I;