1 //== AnalysisDeclContext.cpp - Analysis context for Path Sens analysis -*- C++ -*-//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines AnalysisDeclContext, a class that manages the analysis context
11 // data for path sensitive analysis.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/Analysis/AnalysisContext.h"
16 #include "BodyFarm.h"
17 #include "clang/AST/ASTContext.h"
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/DeclObjC.h"
20 #include "clang/AST/DeclTemplate.h"
21 #include "clang/AST/ParentMap.h"
22 #include "clang/AST/StmtVisitor.h"
23 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
24 #include "clang/Analysis/Analyses/LiveVariables.h"
25 #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
26 #include "clang/Analysis/CFG.h"
27 #include "clang/Analysis/CFGStmtMap.h"
28 #include "clang/Analysis/Support/BumpVector.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/Support/ErrorHandling.h"
31 #include "llvm/Support/SaveAndRestore.h"
32 #include "llvm/Support/raw_ostream.h"
33 
34 using namespace clang;
35 
36 typedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap;
37 
38 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
39                                          const Decl *d,
40                                          const CFG::BuildOptions &buildOptions)
41   : Manager(Mgr),
42     D(d),
43     cfgBuildOptions(buildOptions),
44     forcedBlkExprs(nullptr),
45     builtCFG(false),
46     builtCompleteCFG(false),
47     ReferencedBlockVars(nullptr),
48     ManagedAnalyses(nullptr)
49 {
50   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
51 }
52 
53 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
54                                          const Decl *d)
55 : Manager(Mgr),
56   D(d),
57   forcedBlkExprs(nullptr),
58   builtCFG(false),
59   builtCompleteCFG(false),
60   ReferencedBlockVars(nullptr),
61   ManagedAnalyses(nullptr)
62 {
63   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
64 }
65 
66 AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
67                                                        bool addImplicitDtors,
68                                                        bool addInitializers,
69                                                        bool addTemporaryDtors,
70                                                        bool synthesizeBodies,
71                                                        bool addStaticInitBranch,
72                                                        bool addCXXNewAllocator,
73                                                        CodeInjector *injector)
74   : Injector(injector), SynthesizeBodies(synthesizeBodies)
75 {
76   cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
77   cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
78   cfgBuildOptions.AddInitializers = addInitializers;
79   cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors;
80   cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch;
81   cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
82 }
83 
84 void AnalysisDeclContextManager::clear() {
85   llvm::DeleteContainerSeconds(Contexts);
86 }
87 
88 static BodyFarm &getBodyFarm(ASTContext &C, CodeInjector *injector = nullptr) {
89   static BodyFarm *BF = new BodyFarm(C, injector);
90   return *BF;
91 }
92 
93 Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const {
94   IsAutosynthesized = false;
95   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
96     Stmt *Body = FD->getBody();
97     if (!Body && Manager && Manager->synthesizeBodies()) {
98       Body = getBodyFarm(getASTContext(), Manager->Injector.get()).getBody(FD);
99       if (Body)
100         IsAutosynthesized = true;
101     }
102     return Body;
103   }
104   else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
105     Stmt *Body = MD->getBody();
106     if (!Body && Manager && Manager->synthesizeBodies()) {
107       Body = getBodyFarm(getASTContext(), Manager->Injector.get()).getBody(MD);
108       if (Body)
109         IsAutosynthesized = true;
110     }
111     return Body;
112   } else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D))
113     return BD->getBody();
114   else if (const FunctionTemplateDecl *FunTmpl
115            = dyn_cast_or_null<FunctionTemplateDecl>(D))
116     return FunTmpl->getTemplatedDecl()->getBody();
117 
118   llvm_unreachable("unknown code decl");
119 }
120 
121 Stmt *AnalysisDeclContext::getBody() const {
122   bool Tmp;
123   return getBody(Tmp);
124 }
125 
126 bool AnalysisDeclContext::isBodyAutosynthesized() const {
127   bool Tmp;
128   getBody(Tmp);
129   return Tmp;
130 }
131 
132 bool AnalysisDeclContext::isBodyAutosynthesizedFromModelFile() const {
133   bool Tmp;
134   Stmt *Body = getBody(Tmp);
135   return Tmp && Body->getLocStart().isValid();
136 }
137 
138 
139 const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const {
140   if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
141     return MD->getSelfDecl();
142   if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
143     // See if 'self' was captured by the block.
144     for (const auto &I : BD->captures()) {
145       const VarDecl *VD = I.getVariable();
146       if (VD->getName() == "self")
147         return dyn_cast<ImplicitParamDecl>(VD);
148     }
149   }
150 
151   return nullptr;
152 }
153 
154 void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) {
155   if (!forcedBlkExprs)
156     forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs();
157   // Default construct an entry for 'stmt'.
158   if (const Expr *e = dyn_cast<Expr>(stmt))
159     stmt = e->IgnoreParens();
160   (void) (*forcedBlkExprs)[stmt];
161 }
162 
163 const CFGBlock *
164 AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) {
165   assert(forcedBlkExprs);
166   if (const Expr *e = dyn_cast<Expr>(stmt))
167     stmt = e->IgnoreParens();
168   CFG::BuildOptions::ForcedBlkExprs::const_iterator itr =
169     forcedBlkExprs->find(stmt);
170   assert(itr != forcedBlkExprs->end());
171   return itr->second;
172 }
173 
174 /// Add each synthetic statement in the CFG to the parent map, using the
175 /// source statement's parent.
176 static void addParentsForSyntheticStmts(const CFG *TheCFG, ParentMap &PM) {
177   if (!TheCFG)
178     return;
179 
180   for (CFG::synthetic_stmt_iterator I = TheCFG->synthetic_stmt_begin(),
181                                     E = TheCFG->synthetic_stmt_end();
182        I != E; ++I) {
183     PM.setParent(I->first, PM.getParent(I->second));
184   }
185 }
186 
187 CFG *AnalysisDeclContext::getCFG() {
188   if (!cfgBuildOptions.PruneTriviallyFalseEdges)
189     return getUnoptimizedCFG();
190 
191   if (!builtCFG) {
192     cfg.reset(CFG::buildCFG(D, getBody(),
193                             &D->getASTContext(), cfgBuildOptions));
194     // Even when the cfg is not successfully built, we don't
195     // want to try building it again.
196     builtCFG = true;
197 
198     if (PM)
199       addParentsForSyntheticStmts(cfg.get(), *PM);
200 
201     // The Observer should only observe one build of the CFG.
202     getCFGBuildOptions().Observer = nullptr;
203   }
204   return cfg.get();
205 }
206 
207 CFG *AnalysisDeclContext::getUnoptimizedCFG() {
208   if (!builtCompleteCFG) {
209     SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges,
210                                   false);
211     completeCFG.reset(CFG::buildCFG(D, getBody(), &D->getASTContext(),
212                                     cfgBuildOptions));
213     // Even when the cfg is not successfully built, we don't
214     // want to try building it again.
215     builtCompleteCFG = true;
216 
217     if (PM)
218       addParentsForSyntheticStmts(completeCFG.get(), *PM);
219 
220     // The Observer should only observe one build of the CFG.
221     getCFGBuildOptions().Observer = nullptr;
222   }
223   return completeCFG.get();
224 }
225 
226 CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
227   if (cfgStmtMap)
228     return cfgStmtMap.get();
229 
230   if (CFG *c = getCFG()) {
231     cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
232     return cfgStmtMap.get();
233   }
234 
235   return nullptr;
236 }
237 
238 CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
239   if (CFA)
240     return CFA.get();
241 
242   if (CFG *c = getCFG()) {
243     CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
244     return CFA.get();
245   }
246 
247   return nullptr;
248 }
249 
250 void AnalysisDeclContext::dumpCFG(bool ShowColors) {
251     getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
252 }
253 
254 ParentMap &AnalysisDeclContext::getParentMap() {
255   if (!PM) {
256     PM.reset(new ParentMap(getBody()));
257     if (const CXXConstructorDecl *C = dyn_cast<CXXConstructorDecl>(getDecl())) {
258       for (const auto *I : C->inits()) {
259         PM->addStmt(I->getInit());
260       }
261     }
262     if (builtCFG)
263       addParentsForSyntheticStmts(getCFG(), *PM);
264     if (builtCompleteCFG)
265       addParentsForSyntheticStmts(getUnoptimizedCFG(), *PM);
266   }
267   return *PM;
268 }
269 
270 PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() {
271   if (!PCA)
272     PCA.reset(new PseudoConstantAnalysis(getBody()));
273   return PCA.get();
274 }
275 
276 AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) {
277   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
278     // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl
279     // that has the body.
280     FD->hasBody(FD);
281     D = FD;
282   }
283 
284   AnalysisDeclContext *&AC = Contexts[D];
285   if (!AC)
286     AC = new AnalysisDeclContext(this, D, cfgBuildOptions);
287   return AC;
288 }
289 
290 const StackFrameContext *
291 AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
292                                const CFGBlock *Blk, unsigned Idx) {
293   return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx);
294 }
295 
296 const BlockInvocationContext *
297 AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent,
298                                                const clang::BlockDecl *BD,
299                                                const void *ContextData) {
300   return getLocationContextManager().getBlockInvocationContext(this, parent,
301                                                                BD, ContextData);
302 }
303 
304 LocationContextManager & AnalysisDeclContext::getLocationContextManager() {
305   assert(Manager &&
306          "Cannot create LocationContexts without an AnalysisDeclContextManager!");
307   return Manager->getLocationContextManager();
308 }
309 
310 //===----------------------------------------------------------------------===//
311 // FoldingSet profiling.
312 //===----------------------------------------------------------------------===//
313 
314 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
315                                     ContextKind ck,
316                                     AnalysisDeclContext *ctx,
317                                     const LocationContext *parent,
318                                     const void *data) {
319   ID.AddInteger(ck);
320   ID.AddPointer(ctx);
321   ID.AddPointer(parent);
322   ID.AddPointer(data);
323 }
324 
325 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
326   Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
327 }
328 
329 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
330   Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
331 }
332 
333 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
334   Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData);
335 }
336 
337 //===----------------------------------------------------------------------===//
338 // LocationContext creation.
339 //===----------------------------------------------------------------------===//
340 
341 template <typename LOC, typename DATA>
342 const LOC*
343 LocationContextManager::getLocationContext(AnalysisDeclContext *ctx,
344                                            const LocationContext *parent,
345                                            const DATA *d) {
346   llvm::FoldingSetNodeID ID;
347   LOC::Profile(ID, ctx, parent, d);
348   void *InsertPos;
349 
350   LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
351 
352   if (!L) {
353     L = new LOC(ctx, parent, d);
354     Contexts.InsertNode(L, InsertPos);
355   }
356   return L;
357 }
358 
359 const StackFrameContext*
360 LocationContextManager::getStackFrame(AnalysisDeclContext *ctx,
361                                       const LocationContext *parent,
362                                       const Stmt *s,
363                                       const CFGBlock *blk, unsigned idx) {
364   llvm::FoldingSetNodeID ID;
365   StackFrameContext::Profile(ID, ctx, parent, s, blk, idx);
366   void *InsertPos;
367   StackFrameContext *L =
368    cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
369   if (!L) {
370     L = new StackFrameContext(ctx, parent, s, blk, idx);
371     Contexts.InsertNode(L, InsertPos);
372   }
373   return L;
374 }
375 
376 const ScopeContext *
377 LocationContextManager::getScope(AnalysisDeclContext *ctx,
378                                  const LocationContext *parent,
379                                  const Stmt *s) {
380   return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
381 }
382 
383 const BlockInvocationContext *
384 LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx,
385                                                   const LocationContext *parent,
386                                                   const BlockDecl *BD,
387                                                   const void *ContextData) {
388   llvm::FoldingSetNodeID ID;
389   BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData);
390   void *InsertPos;
391   BlockInvocationContext *L =
392     cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
393                                                                     InsertPos));
394   if (!L) {
395     L = new BlockInvocationContext(ctx, parent, BD, ContextData);
396     Contexts.InsertNode(L, InsertPos);
397   }
398   return L;
399 }
400 
401 //===----------------------------------------------------------------------===//
402 // LocationContext methods.
403 //===----------------------------------------------------------------------===//
404 
405 const StackFrameContext *LocationContext::getCurrentStackFrame() const {
406   const LocationContext *LC = this;
407   while (LC) {
408     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC))
409       return SFC;
410     LC = LC->getParent();
411   }
412   return nullptr;
413 }
414 
415 bool LocationContext::inTopFrame() const {
416   return getCurrentStackFrame()->inTopFrame();
417 }
418 
419 bool LocationContext::isParentOf(const LocationContext *LC) const {
420   do {
421     const LocationContext *Parent = LC->getParent();
422     if (Parent == this)
423       return true;
424     else
425       LC = Parent;
426   } while (LC);
427 
428   return false;
429 }
430 
431 void LocationContext::dumpStack(raw_ostream &OS, StringRef Indent) const {
432   ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
433   PrintingPolicy PP(Ctx.getLangOpts());
434   PP.TerseOutput = 1;
435 
436   unsigned Frame = 0;
437   for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
438     switch (LCtx->getKind()) {
439     case StackFrame:
440       OS << Indent << '#' << Frame++ << ' ';
441       cast<StackFrameContext>(LCtx)->getDecl()->print(OS, PP);
442       OS << '\n';
443       break;
444     case Scope:
445       OS << Indent << "    (scope)\n";
446       break;
447     case Block:
448       OS << Indent << "    (block context: "
449                    << cast<BlockInvocationContext>(LCtx)->getContextData()
450                    << ")\n";
451       break;
452     }
453   }
454 }
455 
456 LLVM_DUMP_METHOD void LocationContext::dumpStack() const {
457   dumpStack(llvm::errs());
458 }
459 
460 //===----------------------------------------------------------------------===//
461 // Lazily generated map to query the external variables referenced by a Block.
462 //===----------------------------------------------------------------------===//
463 
464 namespace {
465 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
466   BumpVector<const VarDecl*> &BEVals;
467   BumpVectorContext &BC;
468   llvm::SmallPtrSet<const VarDecl*, 4> Visited;
469   llvm::SmallPtrSet<const DeclContext*, 4> IgnoredContexts;
470 public:
471   FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
472                             BumpVectorContext &bc)
473   : BEVals(bevals), BC(bc) {}
474 
475   void VisitStmt(Stmt *S) {
476     for (Stmt::child_range I = S->children(); I; ++I)
477       if (Stmt *child = *I)
478         Visit(child);
479   }
480 
481   void VisitDeclRefExpr(DeclRefExpr *DR) {
482     // Non-local variables are also directly modified.
483     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
484       if (!VD->hasLocalStorage()) {
485         if (Visited.insert(VD))
486           BEVals.push_back(VD, BC);
487       }
488     }
489   }
490 
491   void VisitBlockExpr(BlockExpr *BR) {
492     // Blocks containing blocks can transitively capture more variables.
493     IgnoredContexts.insert(BR->getBlockDecl());
494     Visit(BR->getBlockDecl()->getBody());
495   }
496 
497   void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
498     for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
499          et = PE->semantics_end(); it != et; ++it) {
500       Expr *Semantic = *it;
501       if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
502         Semantic = OVE->getSourceExpr();
503       Visit(Semantic);
504     }
505   }
506 };
507 } // end anonymous namespace
508 
509 typedef BumpVector<const VarDecl*> DeclVec;
510 
511 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
512                                               void *&Vec,
513                                               llvm::BumpPtrAllocator &A) {
514   if (Vec)
515     return (DeclVec*) Vec;
516 
517   BumpVectorContext BC(A);
518   DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
519   new (BV) DeclVec(BC, 10);
520 
521   // Go through the capture list.
522   for (const auto &CI : BD->captures()) {
523     BV->push_back(CI.getVariable(), BC);
524   }
525 
526   // Find the referenced global/static variables.
527   FindBlockDeclRefExprsVals F(*BV, BC);
528   F.Visit(BD->getBody());
529 
530   Vec = BV;
531   return BV;
532 }
533 
534 std::pair<AnalysisDeclContext::referenced_decls_iterator,
535           AnalysisDeclContext::referenced_decls_iterator>
536 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
537   if (!ReferencedBlockVars)
538     ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
539 
540   DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
541   return std::make_pair(V->begin(), V->end());
542 }
543 
544 ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) {
545   if (!ManagedAnalyses)
546     ManagedAnalyses = new ManagedAnalysisMap();
547   ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
548   return (*M)[tag];
549 }
550 
551 //===----------------------------------------------------------------------===//
552 // Cleanup.
553 //===----------------------------------------------------------------------===//
554 
555 ManagedAnalysis::~ManagedAnalysis() {}
556 
557 AnalysisDeclContext::~AnalysisDeclContext() {
558   delete forcedBlkExprs;
559   delete ReferencedBlockVars;
560   // Release the managed analyses.
561   if (ManagedAnalyses) {
562     ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
563     llvm::DeleteContainerSeconds(*M);
564     delete M;
565   }
566 }
567 
568 AnalysisDeclContextManager::~AnalysisDeclContextManager() {
569   llvm::DeleteContainerSeconds(Contexts);
570 }
571 
572 LocationContext::~LocationContext() {}
573 
574 LocationContextManager::~LocationContextManager() {
575   clear();
576 }
577 
578 void LocationContextManager::clear() {
579   for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
580        E = Contexts.end(); I != E; ) {
581     LocationContext *LC = &*I;
582     ++I;
583     delete LC;
584   }
585 
586   Contexts.clear();
587 }
588 
589