AnalysisDeclContext.cpp revision 176edba5311f6eff0cad2631449885ddf4fbc9ea
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 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 84void AnalysisDeclContextManager::clear() { 85 llvm::DeleteContainerSeconds(Contexts); 86} 87 88static BodyFarm &getBodyFarm(ASTContext &C, CodeInjector *injector = nullptr) { 89 static BodyFarm *BF = new BodyFarm(C, injector); 90 return *BF; 91} 92 93Stmt *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 121Stmt *AnalysisDeclContext::getBody() const { 122 bool Tmp; 123 return getBody(Tmp); 124} 125 126bool AnalysisDeclContext::isBodyAutosynthesized() const { 127 bool Tmp; 128 getBody(Tmp); 129 return Tmp; 130} 131 132bool AnalysisDeclContext::isBodyAutosynthesizedFromModelFile() const { 133 bool Tmp; 134 Stmt *Body = getBody(Tmp); 135 return Tmp && Body->getLocStart().isValid(); 136} 137 138 139const 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 154void 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 163const CFGBlock * 164AnalysisDeclContext::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. 176static 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 187CFG *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 206CFG *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 225CFGStmtMap *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 237CFGReverseBlockReachabilityAnalysis *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 249void AnalysisDeclContext::dumpCFG(bool ShowColors) { 250 getCFG()->dump(getASTContext().getLangOpts(), ShowColors); 251} 252 253ParentMap &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 269PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() { 270 if (!PCA) 271 PCA.reset(new PseudoConstantAnalysis(getBody())); 272 return PCA.get(); 273} 274 275AnalysisDeclContext *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 289const StackFrameContext * 290AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, 291 const CFGBlock *Blk, unsigned Idx) { 292 return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx); 293} 294 295const BlockInvocationContext * 296AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent, 297 const clang::BlockDecl *BD, 298 const void *ContextData) { 299 return getLocationContextManager().getBlockInvocationContext(this, parent, 300 BD, ContextData); 301} 302 303LocationContextManager & AnalysisDeclContext::getLocationContextManager() { 304 assert(Manager && 305 "Cannot create LocationContexts without an AnalysisDeclContextManager!"); 306 return Manager->getLocationContextManager(); 307} 308 309//===----------------------------------------------------------------------===// 310// FoldingSet profiling. 311//===----------------------------------------------------------------------===// 312 313void 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 324void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { 325 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); 326} 327 328void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { 329 Profile(ID, getAnalysisDeclContext(), getParent(), Enter); 330} 331 332void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { 333 Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData); 334} 335 336//===----------------------------------------------------------------------===// 337// LocationContext creation. 338//===----------------------------------------------------------------------===// 339 340template <typename LOC, typename DATA> 341const LOC* 342LocationContextManager::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 358const StackFrameContext* 359LocationContextManager::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 375const ScopeContext * 376LocationContextManager::getScope(AnalysisDeclContext *ctx, 377 const LocationContext *parent, 378 const Stmt *s) { 379 return getLocationContext<ScopeContext, Stmt>(ctx, parent, s); 380} 381 382const BlockInvocationContext * 383LocationContextManager::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 404const 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 414bool LocationContext::inTopFrame() const { 415 return getCurrentStackFrame()->inTopFrame(); 416} 417 418bool 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 430void 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 455LLVM_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 463namespace { 464class 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; 469public: 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 508typedef BumpVector<const VarDecl*> DeclVec; 509 510static 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 533std::pair<AnalysisDeclContext::referenced_decls_iterator, 534 AnalysisDeclContext::referenced_decls_iterator> 535AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) { 536 if (!ReferencedBlockVars) 537 ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>(); 538 539 DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A); 540 return std::make_pair(V->begin(), V->end()); 541} 542 543ManagedAnalysis *&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 554ManagedAnalysis::~ManagedAnalysis() {} 555 556AnalysisDeclContext::~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 567AnalysisDeclContextManager::~AnalysisDeclContextManager() { 568 llvm::DeleteContainerSeconds(Contexts); 569} 570 571LocationContext::~LocationContext() {} 572 573LocationContextManager::~LocationContextManager() { 574 clear(); 575} 576 577void 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