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