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