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