AnalysisDeclContext.cpp revision 8e026045edf1319aed16adfe55524ff9e755c452 
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
31using namespace clang;
32
33typedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap;
34
35AnalysisDeclContext::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
52AnalysisDeclContext::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
67AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
68                                               bool addImplicitDtors,
69                                               bool addInitializers) {
70  cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
71  cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
72  cfgBuildOptions.AddInitializers = addInitializers;
73}
74
75void AnalysisDeclContextManager::clear() {
76  for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I)
77    delete I->second;
78  Contexts.clear();
79}
80
81Stmt *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
95const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const {
96  if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
97    return MD->getSelfDecl();
98
99  return NULL;
100}
101
102void 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
111const CFGBlock *
112AnalysisDeclContext::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
122CFG *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
136CFG *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
149CFGStmtMap *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
161CFGReverseBlockReachabilityAnalysis *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
173void AnalysisDeclContext::dumpCFG() {
174    getCFG()->dump(getASTContext().getLangOptions());
175}
176
177ParentMap &AnalysisDeclContext::getParentMap() {
178  if (!PM)
179    PM.reset(new ParentMap(getBody()));
180  return *PM;
181}
182
183PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() {
184  if (!PCA)
185    PCA.reset(new PseudoConstantAnalysis(getBody()));
186  return PCA.get();
187}
188
189AnalysisDeclContext *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
197const StackFrameContext *
198AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
199                               const CFGBlock *Blk, unsigned Idx) {
200  return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx);
201}
202
203LocationContextManager & AnalysisDeclContext::getLocationContextManager() {
204  assert(Manager &&
205         "Cannot create LocationContexts without an AnalysisDeclContextManager!");
206  return Manager->getLocationContextManager();
207}
208
209//===----------------------------------------------------------------------===//
210// FoldingSet profiling.
211//===----------------------------------------------------------------------===//
212
213void 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
224void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
225  Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
226}
227
228void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
229  Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
230}
231
232void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
233  Profile(ID, getAnalysisDeclContext(), getParent(), BD);
234}
235
236//===----------------------------------------------------------------------===//
237// LocationContext creation.
238//===----------------------------------------------------------------------===//
239
240template <typename LOC, typename DATA>
241const LOC*
242LocationContextManager::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
258const StackFrameContext*
259LocationContextManager::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
275const ScopeContext *
276LocationContextManager::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
286const 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
296const StackFrameContext *
297LocationContext::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
309bool 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
325namespace {
326class 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;
331public:
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
378typedef BumpVector<const VarDecl*> DeclVec;
379
380static 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
398std::pair<AnalysisDeclContext::referenced_decls_iterator,
399          AnalysisDeclContext::referenced_decls_iterator>
400AnalysisDeclContext::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
408ManagedAnalysis *&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
419ManagedAnalysis::~ManagedAnalysis() {}
420
421AnalysisDeclContext::~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
433AnalysisDeclContextManager::~AnalysisDeclContextManager() {
434  for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I)
435    delete I->second;
436}
437
438LocationContext::~LocationContext() {}
439
440LocationContextManager::~LocationContextManager() {
441  clear();
442}
443
444void 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