contrib/llvm/tools/clang/lib/Analysis/AnalysisDeclContext.cpp

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