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