AnalysisDeclContext.cpp revision 6bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89 
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(nullptr),
45    builtCFG(false),
46    builtCompleteCFG(false),
47    ReferencedBlockVars(nullptr),
48    ManagedAnalyses(nullptr)
49{
50  cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs;
51}
52
53AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
54                                         const Decl *d)
55: Manager(Mgr),
56  D(d),
57  forcedBlkExprs(nullptr),
58  builtCFG(false),
59  builtCompleteCFG(false),
60  ReferencedBlockVars(nullptr),
61  ManagedAnalyses(nullptr)
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 nullptr;
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    // The Observer should only observe one build of the CFG.
194    getCFGBuildOptions().Observer = nullptr;
195  }
196  return cfg.get();
197}
198
199CFG *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    // The Observer should only observe one build of the CFG.
213    getCFGBuildOptions().Observer = nullptr;
214  }
215  return completeCFG.get();
216}
217
218CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() {
219  if (cfgStmtMap)
220    return cfgStmtMap.get();
221
222  if (CFG *c = getCFG()) {
223    cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap()));
224    return cfgStmtMap.get();
225  }
226
227  return nullptr;
228}
229
230CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() {
231  if (CFA)
232    return CFA.get();
233
234  if (CFG *c = getCFG()) {
235    CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c));
236    return CFA.get();
237  }
238
239  return nullptr;
240}
241
242void AnalysisDeclContext::dumpCFG(bool ShowColors) {
243    getCFG()->dump(getASTContext().getLangOpts(), ShowColors);
244}
245
246ParentMap &AnalysisDeclContext::getParentMap() {
247  if (!PM) {
248    PM.reset(new ParentMap(getBody()));
249    if (const CXXConstructorDecl *C = dyn_cast<CXXConstructorDecl>(getDecl())) {
250      for (const auto *I : C->inits()) {
251        PM->addStmt(I->getInit());
252      }
253    }
254    if (builtCFG)
255      addParentsForSyntheticStmts(getCFG(), *PM);
256    if (builtCompleteCFG)
257      addParentsForSyntheticStmts(getUnoptimizedCFG(), *PM);
258  }
259  return *PM;
260}
261
262PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() {
263  if (!PCA)
264    PCA.reset(new PseudoConstantAnalysis(getBody()));
265  return PCA.get();
266}
267
268AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) {
269  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
270    // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl
271    // that has the body.
272    FD->hasBody(FD);
273    D = FD;
274  }
275
276  AnalysisDeclContext *&AC = Contexts[D];
277  if (!AC)
278    AC = new AnalysisDeclContext(this, D, cfgBuildOptions);
279  return AC;
280}
281
282const StackFrameContext *
283AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S,
284                               const CFGBlock *Blk, unsigned Idx) {
285  return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx);
286}
287
288const BlockInvocationContext *
289AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent,
290                                               const clang::BlockDecl *BD,
291                                               const void *ContextData) {
292  return getLocationContextManager().getBlockInvocationContext(this, parent,
293                                                               BD, ContextData);
294}
295
296LocationContextManager & AnalysisDeclContext::getLocationContextManager() {
297  assert(Manager &&
298         "Cannot create LocationContexts without an AnalysisDeclContextManager!");
299  return Manager->getLocationContextManager();
300}
301
302//===----------------------------------------------------------------------===//
303// FoldingSet profiling.
304//===----------------------------------------------------------------------===//
305
306void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID,
307                                    ContextKind ck,
308                                    AnalysisDeclContext *ctx,
309                                    const LocationContext *parent,
310                                    const void *data) {
311  ID.AddInteger(ck);
312  ID.AddPointer(ctx);
313  ID.AddPointer(parent);
314  ID.AddPointer(data);
315}
316
317void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) {
318  Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index);
319}
320
321void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) {
322  Profile(ID, getAnalysisDeclContext(), getParent(), Enter);
323}
324
325void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) {
326  Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData);
327}
328
329//===----------------------------------------------------------------------===//
330// LocationContext creation.
331//===----------------------------------------------------------------------===//
332
333template <typename LOC, typename DATA>
334const LOC*
335LocationContextManager::getLocationContext(AnalysisDeclContext *ctx,
336                                           const LocationContext *parent,
337                                           const DATA *d) {
338  llvm::FoldingSetNodeID ID;
339  LOC::Profile(ID, ctx, parent, d);
340  void *InsertPos;
341
342  LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
343
344  if (!L) {
345    L = new LOC(ctx, parent, d);
346    Contexts.InsertNode(L, InsertPos);
347  }
348  return L;
349}
350
351const StackFrameContext*
352LocationContextManager::getStackFrame(AnalysisDeclContext *ctx,
353                                      const LocationContext *parent,
354                                      const Stmt *s,
355                                      const CFGBlock *blk, unsigned idx) {
356  llvm::FoldingSetNodeID ID;
357  StackFrameContext::Profile(ID, ctx, parent, s, blk, idx);
358  void *InsertPos;
359  StackFrameContext *L =
360   cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos));
361  if (!L) {
362    L = new StackFrameContext(ctx, parent, s, blk, idx);
363    Contexts.InsertNode(L, InsertPos);
364  }
365  return L;
366}
367
368const ScopeContext *
369LocationContextManager::getScope(AnalysisDeclContext *ctx,
370                                 const LocationContext *parent,
371                                 const Stmt *s) {
372  return getLocationContext<ScopeContext, Stmt>(ctx, parent, s);
373}
374
375const BlockInvocationContext *
376LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx,
377                                                  const LocationContext *parent,
378                                                  const BlockDecl *BD,
379                                                  const void *ContextData) {
380  llvm::FoldingSetNodeID ID;
381  BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData);
382  void *InsertPos;
383  BlockInvocationContext *L =
384    cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID,
385                                                                    InsertPos));
386  if (!L) {
387    L = new BlockInvocationContext(ctx, parent, BD, ContextData);
388    Contexts.InsertNode(L, InsertPos);
389  }
390  return L;
391}
392
393//===----------------------------------------------------------------------===//
394// LocationContext methods.
395//===----------------------------------------------------------------------===//
396
397const StackFrameContext *LocationContext::getCurrentStackFrame() const {
398  const LocationContext *LC = this;
399  while (LC) {
400    if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC))
401      return SFC;
402    LC = LC->getParent();
403  }
404  return nullptr;
405}
406
407bool LocationContext::inTopFrame() const {
408  return getCurrentStackFrame()->inTopFrame();
409}
410
411bool LocationContext::isParentOf(const LocationContext *LC) const {
412  do {
413    const LocationContext *Parent = LC->getParent();
414    if (Parent == this)
415      return true;
416    else
417      LC = Parent;
418  } while (LC);
419
420  return false;
421}
422
423void LocationContext::dumpStack(raw_ostream &OS, StringRef Indent) const {
424  ASTContext &Ctx = getAnalysisDeclContext()->getASTContext();
425  PrintingPolicy PP(Ctx.getLangOpts());
426  PP.TerseOutput = 1;
427
428  unsigned Frame = 0;
429  for (const LocationContext *LCtx = this; LCtx; LCtx = LCtx->getParent()) {
430    switch (LCtx->getKind()) {
431    case StackFrame:
432      OS << Indent << '#' << Frame++ << ' ';
433      cast<StackFrameContext>(LCtx)->getDecl()->print(OS, PP);
434      OS << '\n';
435      break;
436    case Scope:
437      OS << Indent << "    (scope)\n";
438      break;
439    case Block:
440      OS << Indent << "    (block context: "
441                   << cast<BlockInvocationContext>(LCtx)->getContextData()
442                   << ")\n";
443      break;
444    }
445  }
446}
447
448LLVM_DUMP_METHOD void LocationContext::dumpStack() const {
449  dumpStack(llvm::errs());
450}
451
452//===----------------------------------------------------------------------===//
453// Lazily generated map to query the external variables referenced by a Block.
454//===----------------------------------------------------------------------===//
455
456namespace {
457class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{
458  BumpVector<const VarDecl*> &BEVals;
459  BumpVectorContext &BC;
460  llvm::SmallPtrSet<const VarDecl*, 4> Visited;
461  llvm::SmallPtrSet<const DeclContext*, 4> IgnoredContexts;
462public:
463  FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals,
464                            BumpVectorContext &bc)
465  : BEVals(bevals), BC(bc) {}
466
467  void VisitStmt(Stmt *S) {
468    for (Stmt::child_range I = S->children(); I; ++I)
469      if (Stmt *child = *I)
470        Visit(child);
471  }
472
473  void VisitDeclRefExpr(DeclRefExpr *DR) {
474    // Non-local variables are also directly modified.
475    if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
476      if (!VD->hasLocalStorage()) {
477        if (Visited.insert(VD))
478          BEVals.push_back(VD, BC);
479      }
480    }
481  }
482
483  void VisitBlockExpr(BlockExpr *BR) {
484    // Blocks containing blocks can transitively capture more variables.
485    IgnoredContexts.insert(BR->getBlockDecl());
486    Visit(BR->getBlockDecl()->getBody());
487  }
488
489  void VisitPseudoObjectExpr(PseudoObjectExpr *PE) {
490    for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(),
491         et = PE->semantics_end(); it != et; ++it) {
492      Expr *Semantic = *it;
493      if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
494        Semantic = OVE->getSourceExpr();
495      Visit(Semantic);
496    }
497  }
498};
499} // end anonymous namespace
500
501typedef BumpVector<const VarDecl*> DeclVec;
502
503static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD,
504                                              void *&Vec,
505                                              llvm::BumpPtrAllocator &A) {
506  if (Vec)
507    return (DeclVec*) Vec;
508
509  BumpVectorContext BC(A);
510  DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>();
511  new (BV) DeclVec(BC, 10);
512
513  // Go through the capture list.
514  for (const auto &CI : BD->captures()) {
515    BV->push_back(CI.getVariable(), BC);
516  }
517
518  // Find the referenced global/static variables.
519  FindBlockDeclRefExprsVals F(*BV, BC);
520  F.Visit(BD->getBody());
521
522  Vec = BV;
523  return BV;
524}
525
526std::pair<AnalysisDeclContext::referenced_decls_iterator,
527          AnalysisDeclContext::referenced_decls_iterator>
528AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) {
529  if (!ReferencedBlockVars)
530    ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>();
531
532  DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A);
533  return std::make_pair(V->begin(), V->end());
534}
535
536ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) {
537  if (!ManagedAnalyses)
538    ManagedAnalyses = new ManagedAnalysisMap();
539  ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
540  return (*M)[tag];
541}
542
543//===----------------------------------------------------------------------===//
544// Cleanup.
545//===----------------------------------------------------------------------===//
546
547ManagedAnalysis::~ManagedAnalysis() {}
548
549AnalysisDeclContext::~AnalysisDeclContext() {
550  delete forcedBlkExprs;
551  delete ReferencedBlockVars;
552  // Release the managed analyses.
553  if (ManagedAnalyses) {
554    ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses;
555    llvm::DeleteContainerSeconds(*M);
556    delete M;
557  }
558}
559
560AnalysisDeclContextManager::~AnalysisDeclContextManager() {
561  llvm::DeleteContainerSeconds(Contexts);
562}
563
564LocationContext::~LocationContext() {}
565
566LocationContextManager::~LocationContextManager() {
567  clear();
568}
569
570void LocationContextManager::clear() {
571  for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(),
572       E = Contexts.end(); I != E; ) {
573    LocationContext *LC = &*I;
574    ++I;
575    delete LC;
576  }
577
578  Contexts.clear();
579}
580
581