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/AST/Decl.h"
16 #include "clang/AST/DeclObjC.h"
17 #include "clang/AST/DeclTemplate.h"
18 #include "clang/AST/ParentMap.h"
19 #include "clang/AST/StmtVisitor.h"
20 #include "clang/Analysis/Analyses/LiveVariables.h"
21 #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
22 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
23 #include "clang/Analysis/AnalysisContext.h"
24 #include "clang/Analysis/CFG.h"
25 #include "clang/Analysis/CFGStmtMap.h"
26 #include "clang/Analysis/Support/BumpVector.h"
27 #include "clang/Analysis/Support/SaveAndRestore.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/Support/ErrorHandling.h"
30 
31 using namespace clang;
32 
33 typedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap;
34 
35 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
36                                  const Decl *d,
37                                  idx::TranslationUnit *tu,
38                                  const CFG::BuildOptions &buildOptions)
39   : Manager(Mgr),
40     D(d),
41     TU(tu),
42     cfgBuildOptions(buildOptions),
43     forcedBlkExprs(0),
44     builtCFG(false),
45     builtCompleteCFG(false),
46     ReferencedBlockVars(0),
47     ManagedAnalyses(0)
48 {
49   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
50 }
51 
52 AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
53                                  const Decl *d,
54                                  idx::TranslationUnit *tu)
55 : Manager(Mgr),
56   D(d),
57   TU(tu),
58   forcedBlkExprs(0),
59   builtCFG(false),
60   builtCompleteCFG(false),
61   ReferencedBlockVars(0),
62   ManagedAnalyses(0)
63 {
64   cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
65 }
66 
67 AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
68                                                bool addImplicitDtors,
69                                                bool addInitializers) {
70   cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
71   cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
72   cfgBuildOptions.AddInitializers = addInitializers;
73 }
74 
75 void AnalysisDeclContextManager::clear() {
76   for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I)
77     delete I->second;
78   Contexts.clear();
79 }
80 
81 Stmt *AnalysisDeclContext::getBody() const {
82   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
83     return FD->getBody();
84   else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
85     return MD->getBody();
86   else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D))
87     return BD->getBody();
88   else if (const FunctionTemplateDecl *FunTmpl
89            = dyn_cast_or_null<FunctionTemplateDecl>(D))
90     return FunTmpl->getTemplatedDecl()->getBody();
91 
92   llvm_unreachable("unknown code decl");
93 }
94 
95 const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const {
96   if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
97     return MD->getSelfDecl();
98 
99   return NULL;
100 }
101 
102 void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) {
103   if (!forcedBlkExprs)
104     forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs();
105   // Default construct an entry for 'stmt'.
106   if (const Expr *e = dyn_cast<Expr>(stmt))
107     stmt = e->IgnoreParens();
108   (void) (*forcedBlkExprs)[stmt];
109 }
110 
111 const CFGBlock *
112 AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) {
113   assert(forcedBlkExprs);
114   if (const Expr *e = dyn_cast<Expr>(stmt))
115     stmt = e->IgnoreParens();
116   CFG::BuildOptions::ForcedBlkExprs::const_iterator itr =
117     forcedBlkExprs->find(stmt);
118   assert(itr != forcedBlkExprs->end());
119   return itr->second;
120 }
121 
122 CFG *AnalysisDeclContext::getCFG() {
123   if (!cfgBuildOptions.PruneTriviallyFalseEdges)
124     return getUnoptimizedCFG();
125 
126   if (!builtCFG) {
127     cfg.reset(CFG::buildCFG(D, getBody(),
128                             &D->getASTContext(), cfgBuildOptions));
129     // Even when the cfg is not successfully built, we don't
130     // want to try building it again.
131     builtCFG = true;
132   }
133   return cfg.get();
134 }
135 
136 CFG *AnalysisDeclContext::getUnoptimizedCFG() {
137   if (!builtCompleteCFG) {
138     SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges,
139                                   false);
140     completeCFG.reset(CFG::buildCFG(D, getBody(), &D->getASTContext(),
141                                     cfgBuildOptions));
142     // Even when the cfg is not successfully built, we don't
143     // want to try building it again.
144     builtCompleteCFG = true;
145   }
146   return completeCFG.get();
147 }
148 
149 CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
150   if (cfgStmtMap)
151     return cfgStmtMap.get();
152 
153   if (CFG *c = getCFG()) {
154     cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
155     return cfgStmtMap.get();
156   }
157 
158   return 0;
159 }
160 
161 CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
162   if (CFA)
163     return CFA.get();
164 
165   if (CFG *c = getCFG()) {
166     CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
167     return CFA.get();
168   }
169 
170   return 0;
171 }
172 
173 void AnalysisDeclContext::dumpCFG() {
174     getCFG()->dump(getASTContext().getLangOptions());
175 }
176 
177 ParentMap &AnalysisDeclContext::getParentMap() {
178   if (!PM)
179     PM.reset(new ParentMap(getBody()));
180   return *PM;
181 }
182 
183 PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() {
184   if (!PCA)
185     PCA.reset(new PseudoConstantAnalysis(getBody()));
186   return PCA.get();
187 }
188 
189 AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D,
190                                                     idx::TranslationUnit *TU) {
191   AnalysisDeclContext *&AC = Contexts[D];
192   if (!AC)
193     AC = new AnalysisDeclContext(this, D, TU, cfgBuildOptions);
194   return AC;
195 }
196 
197 const StackFrameContext *
198 AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
199                                const CFGBlock *Blk, unsigned Idx) {
200   return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx);
201 }
202 
203 LocationContextManager & AnalysisDeclContext::getLocationContextManager() {
204   assert(Manager &&
205          "Cannot create LocationContexts without an AnalysisDeclContextManager!");
206   return Manager->getLocationContextManager();
207 }
208 
209 //===----------------------------------------------------------------------===//
210 // FoldingSet profiling.
211 //===----------------------------------------------------------------------===//
212 
213 void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
214                                     ContextKind ck,
215                                     AnalysisDeclContext *ctx,
216                                     const LocationContext *parent,
217                                     const void *data) {
218   ID.AddInteger(ck);
219   ID.AddPointer(ctx);
220   ID.AddPointer(parent);
221   ID.AddPointer(data);
222 }
223 
224 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
225   Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
226 }
227 
228 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
229   Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
230 }
231 
232 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
233   Profile(ID, getAnalysisDeclContext(), getParent(), BD);
234 }
235 
236 //===----------------------------------------------------------------------===//
237 // LocationContext creation.
238 //===----------------------------------------------------------------------===//
239 
240 template <typename LOC, typename DATA>
241 const LOC*
242 LocationContextManager::getLocationContext(AnalysisDeclContext *ctx,
243                                            const LocationContext *parent,
244                                            const DATA *d) {
245   llvm::FoldingSetNodeID ID;
246   LOC::Profile(ID, ctx, parent, d);
247   void *InsertPos;
248 
249   LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
250 
251   if (!L) {
252     L = new LOC(ctx, parent, d);
253     Contexts.InsertNode(L, InsertPos);
254   }
255   return L;
256 }
257 
258 const StackFrameContext*
259 LocationContextManager::getStackFrame(AnalysisDeclContext *ctx,
260                                       const LocationContext *parent,
261                                       const Stmt *s,
262                                       const CFGBlock *blk, unsigned idx) {
263   llvm::FoldingSetNodeID ID;
264   StackFrameContext::Profile(ID, ctx, parent, s, blk, idx);
265   void *InsertPos;
266   StackFrameContext *L =
267    cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
268   if (!L) {
269     L = new StackFrameContext(ctx, parent, s, blk, idx);
270     Contexts.InsertNode(L, InsertPos);
271   }
272   return L;
273 }
274 
275 const ScopeContext *
276 LocationContextManager::getScope(AnalysisDeclContext *ctx,
277                                  const LocationContext *parent,
278                                  const Stmt *s) {
279   return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
280 }
281 
282 //===----------------------------------------------------------------------===//
283 // LocationContext methods.
284 //===----------------------------------------------------------------------===//
285 
286 const StackFrameContext *LocationContext::getCurrentStackFrame() const {
287   const LocationContext *LC = this;
288   while (LC) {
289     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC))
290       return SFC;
291     LC = LC->getParent();
292   }
293   return NULL;
294 }
295 
296 const StackFrameContext *
297 LocationContext::getStackFrameForDeclContext(const DeclContext *DC) const {
298   const LocationContext *LC = this;
299   while (LC) {
300     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) {
301       if (cast<DeclContext>(SFC->getDecl()) == DC)
302         return SFC;
303     }
304     LC = LC->getParent();
305   }
306   return NULL;
307 }
308 
309 bool LocationContext::isParentOf(const LocationContext *LC) const {
310   do {
311     const LocationContext *Parent = LC->getParent();
312     if (Parent == this)
313       return true;
314     else
315       LC = Parent;
316   } while (LC);
317 
318   return false;
319 }
320 
321 //===----------------------------------------------------------------------===//
322 // Lazily generated map to query the external variables referenced by a Block.
323 //===----------------------------------------------------------------------===//
324 
325 namespace {
326 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
327   BumpVector<const VarDecl*> &BEVals;
328   BumpVectorContext &BC;
329   llvm::DenseMap<const VarDecl*, unsigned> Visited;
330   llvm::SmallSet<const DeclContext*, 4> IgnoredContexts;
331 public:
332   FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
333                             BumpVectorContext &bc)
334   : BEVals(bevals), BC(bc) {}
335 
336   bool IsTrackedDecl(const VarDecl *VD) {
337     const DeclContext *DC = VD->getDeclContext();
338     return IgnoredContexts.count(DC) == 0;
339   }
340 
341   void VisitStmt(Stmt *S) {
342     for (Stmt::child_range I = S->children(); I; ++I)
343       if (Stmt *child = *I)
344         Visit(child);
345   }
346 
347   void VisitDeclRefExpr(const DeclRefExpr *DR) {
348     // Non-local variables are also directly modified.
349     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
350       if (!VD->hasLocalStorage()) {
351         unsigned &flag = Visited[VD];
352         if (!flag) {
353           flag = 1;
354           BEVals.push_back(VD, BC);
355         }
356       }
357   }
358 
359   void VisitBlockDeclRefExpr(BlockDeclRefExpr *DR) {
360     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
361       unsigned &flag = Visited[VD];
362       if (!flag) {
363         flag = 1;
364         if (IsTrackedDecl(VD))
365           BEVals.push_back(VD, BC);
366       }
367     }
368   }
369 
370   void VisitBlockExpr(BlockExpr *BR) {
371     // Blocks containing blocks can transitively capture more variables.
372     IgnoredContexts.insert(BR->getBlockDecl());
373     Visit(BR->getBlockDecl()->getBody());
374   }
375 };
376 } // end anonymous namespace
377 
378 typedef BumpVector<const VarDecl*> DeclVec;
379 
380 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
381                                               void *&Vec,
382                                               llvm::BumpPtrAllocator &A) {
383   if (Vec)
384     return (DeclVec*) Vec;
385 
386   BumpVectorContext BC(A);
387   DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
388   new (BV) DeclVec(BC, 10);
389 
390   // Find the referenced variables.
391   FindBlockDeclRefExprsVals F(*BV, BC);
392   F.Visit(BD->getBody());
393 
394   Vec = BV;
395   return BV;
396 }
397 
398 std::pair<AnalysisDeclContext::referenced_decls_iterator,
399           AnalysisDeclContext::referenced_decls_iterator>
400 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
401   if (!ReferencedBlockVars)
402     ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
403 
404   DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
405   return std::make_pair(V->begin(), V->end());
406 }
407 
408 ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) {
409   if (!ManagedAnalyses)
410     ManagedAnalyses = new ManagedAnalysisMap();
411   ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
412   return (*M)[tag];
413 }
414 
415 //===----------------------------------------------------------------------===//
416 // Cleanup.
417 //===----------------------------------------------------------------------===//
418 
419 ManagedAnalysis::~ManagedAnalysis() {}
420 
421 AnalysisDeclContext::~AnalysisDeclContext() {
422   delete forcedBlkExprs;
423   delete ReferencedBlockVars;
424   // Release the managed analyses.
425   if (ManagedAnalyses) {
426     ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
427     for (ManagedAnalysisMap::iterator I = M->begin(), E = M->end(); I!=E; ++I)
428       delete I->second;
429     delete M;
430   }
431 }
432 
433 AnalysisDeclContextManager::~AnalysisDeclContextManager() {
434   for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I)
435     delete I->second;
436 }
437 
438 LocationContext::~LocationContext() {}
439 
440 LocationContextManager::~LocationContextManager() {
441   clear();
442 }
443 
444 void LocationContextManager::clear() {
445   for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
446        E = Contexts.end(); I != E; ) {
447     LocationContext *LC = &*I;
448     ++I;
449     delete LC;
450   }
451 
452   Contexts.clear();
453 }
454 
455