AnalysisDeclContext.cpp revision ac7cc2d37e82181e73fcc265c1d0a619d18b7605
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 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(0), 45 builtCFG(false), 46 builtCompleteCFG(false), 47 ReferencedBlockVars(0), 48 ManagedAnalyses(0) 49{ 50 cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; 51} 52 53AnalysisDeclContext::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 66AnalysisDeclContextManager::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 81void AnalysisDeclContextManager::clear() { 82 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 83 delete I->second; 84 Contexts.clear(); 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 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 113Stmt *AnalysisDeclContext::getBody() const { 114 bool Tmp; 115 return getBody(Tmp); 116} 117 118bool AnalysisDeclContext::isBodyAutosynthesized() const { 119 bool Tmp; 120 getBody(Tmp); 121 return Tmp; 122} 123 124const 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 140void 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 149const CFGBlock * 150AnalysisDeclContext::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. 162static 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 173CFG *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 190CFG *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 206CFGStmtMap *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 218CFGReverseBlockReachabilityAnalysis *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 230void AnalysisDeclContext::dumpCFG(bool ShowColors) { 231 getCFG()->dump(getASTContext().getLangOpts(), ShowColors); 232} 233 234ParentMap &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 252PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() { 253 if (!PCA) 254 PCA.reset(new PseudoConstantAnalysis(getBody())); 255 return PCA.get(); 256} 257 258AnalysisDeclContext *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 272const StackFrameContext * 273AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, 274 const CFGBlock *Blk, unsigned Idx) { 275 return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx); 276} 277 278const BlockInvocationContext * 279AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent, 280 const clang::BlockDecl *BD, 281 const void *ContextData) { 282 return getLocationContextManager().getBlockInvocationContext(this, parent, 283 BD, ContextData); 284} 285 286LocationContextManager & AnalysisDeclContext::getLocationContextManager() { 287 assert(Manager && 288 "Cannot create LocationContexts without an AnalysisDeclContextManager!"); 289 return Manager->getLocationContextManager(); 290} 291 292//===----------------------------------------------------------------------===// 293// FoldingSet profiling. 294//===----------------------------------------------------------------------===// 295 296void 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 307void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { 308 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); 309} 310 311void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { 312 Profile(ID, getAnalysisDeclContext(), getParent(), Enter); 313} 314 315void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { 316 Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData); 317} 318 319//===----------------------------------------------------------------------===// 320// LocationContext creation. 321//===----------------------------------------------------------------------===// 322 323template <typename LOC, typename DATA> 324const LOC* 325LocationContextManager::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 341const StackFrameContext* 342LocationContextManager::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 358const ScopeContext * 359LocationContextManager::getScope(AnalysisDeclContext *ctx, 360 const LocationContext *parent, 361 const Stmt *s) { 362 return getLocationContext<ScopeContext, Stmt>(ctx, parent, s); 363} 364 365const BlockInvocationContext * 366LocationContextManager::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 387const 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 397bool LocationContext::inTopFrame() const { 398 return getCurrentStackFrame()->inTopFrame(); 399} 400 401bool 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 413void 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 438void 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 446namespace { 447class 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; 452public: 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 496typedef BumpVector<const VarDecl*> DeclVec; 497 498static 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 522std::pair<AnalysisDeclContext::referenced_decls_iterator, 523 AnalysisDeclContext::referenced_decls_iterator> 524AnalysisDeclContext::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 532ManagedAnalysis *&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 543ManagedAnalysis::~ManagedAnalysis() {} 544 545AnalysisDeclContext::~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 557AnalysisDeclContextManager::~AnalysisDeclContextManager() { 558 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 559 delete I->second; 560} 561 562LocationContext::~LocationContext() {} 563 564LocationContextManager::~LocationContextManager() { 565 clear(); 566} 567 568void 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 579