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