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