AnalysisDeclContext.cpp revision 243830
1238106Sdes//== AnalysisDeclContext.cpp - Analysis context for Path Sens analysis -*- C++ -*-// 2238106Sdes// 3238106Sdes// The LLVM Compiler Infrastructure 4238106Sdes// 5238106Sdes// This file is distributed under the University of Illinois Open Source 6238106Sdes// License. See LICENSE.TXT for details. 7238106Sdes// 8238106Sdes//===----------------------------------------------------------------------===// 9238106Sdes// 10238106Sdes// This file defines AnalysisDeclContext, a class that manages the analysis context 11238106Sdes// data for path sensitive analysis. 12238106Sdes// 13238106Sdes//===----------------------------------------------------------------------===// 14238106Sdes 15238106Sdes#include "clang/AST/ASTContext.h" 16238106Sdes#include "clang/AST/Decl.h" 17238106Sdes#include "clang/AST/DeclObjC.h" 18238106Sdes#include "clang/AST/DeclTemplate.h" 19238106Sdes#include "clang/AST/ParentMap.h" 20238106Sdes#include "clang/AST/StmtVisitor.h" 21238106Sdes#include "clang/Analysis/Analyses/LiveVariables.h" 22238106Sdes#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" 23238106Sdes#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 24269257Sdes#include "clang/Analysis/AnalysisContext.h" 25269257Sdes#include "clang/Analysis/CFG.h" 26269257Sdes#include "clang/Analysis/CFGStmtMap.h" 27269257Sdes#include "clang/Analysis/Support/BumpVector.h" 28269257Sdes#include "llvm/Support/SaveAndRestore.h" 29269257Sdes#include "llvm/ADT/SmallPtrSet.h" 30269257Sdes#include "llvm/Support/ErrorHandling.h" 31269257Sdes 32269257Sdes#include "BodyFarm.h" 33269257Sdes 34238106Sdesusing namespace clang; 35238106Sdes 36238106Sdestypedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap; 37238106Sdes 38238106SdesAnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 39238106Sdes const Decl *d, 40238106Sdes const CFG::BuildOptions &buildOptions) 41238106Sdes : Manager(Mgr), 42238106Sdes D(d), 43238106Sdes cfgBuildOptions(buildOptions), 44238106Sdes forcedBlkExprs(0), 45238106Sdes builtCFG(false), 46238106Sdes builtCompleteCFG(false), 47238106Sdes ReferencedBlockVars(0), 48238106Sdes ManagedAnalyses(0) 49238106Sdes{ 50238106Sdes cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; 51238106Sdes} 52238106Sdes 53238106SdesAnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 54238106Sdes const Decl *d) 55238106Sdes: Manager(Mgr), 56238106Sdes D(d), 57238106Sdes forcedBlkExprs(0), 58238106Sdes builtCFG(false), 59238106Sdes builtCompleteCFG(false), 60238106Sdes ReferencedBlockVars(0), 61238106Sdes ManagedAnalyses(0) 62238106Sdes{ 63238106Sdes cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; 64238106Sdes} 65238106Sdes 66291767SdesAnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG, 67291767Sdes bool addImplicitDtors, 68269257Sdes bool addInitializers, 69238106Sdes bool addTemporaryDtors, 70238106Sdes bool synthesizeBodies) 71238106Sdes : SynthesizeBodies(synthesizeBodies) 72238106Sdes{ 73238106Sdes cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG; 74238106Sdes cfgBuildOptions.AddImplicitDtors = addImplicitDtors; 75238106Sdes cfgBuildOptions.AddInitializers = addInitializers; 76269257Sdes cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors; 77238106Sdes} 78269257Sdes 79291767Sdesvoid AnalysisDeclContextManager::clear() { 80291767Sdes for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 81238106Sdes delete I->second; 82238106Sdes Contexts.clear(); 83238106Sdes} 84238106Sdes 85238106Sdesstatic BodyFarm &getBodyFarm(ASTContext &C) { 86238106Sdes static BodyFarm *BF = new BodyFarm(C); 87238106Sdes return *BF; 88238106Sdes} 89238106Sdes 90238106SdesStmt *AnalysisDeclContext::getBody() const { 91238106Sdes if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 92238106Sdes Stmt *Body = FD->getBody(); 93238106Sdes if (!Body && Manager && Manager->synthesizeBodies()) 94238106Sdes return getBodyFarm(getASTContext()).getBody(FD); 95238106Sdes return Body; 96238106Sdes } 97238106Sdes else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) 98238106Sdes return MD->getBody(); 99238106Sdes else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) 100238106Sdes return BD->getBody(); 101238106Sdes else if (const FunctionTemplateDecl *FunTmpl 102238106Sdes = dyn_cast_or_null<FunctionTemplateDecl>(D)) 103238106Sdes return FunTmpl->getTemplatedDecl()->getBody(); 104238106Sdes 105238106Sdes llvm_unreachable("unknown code decl"); 106238106Sdes} 107238106Sdes 108238106Sdesconst ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const { 109238106Sdes if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) 110238106Sdes return MD->getSelfDecl(); 111238106Sdes if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { 112238106Sdes // See if 'self' was captured by the block. 113238106Sdes for (BlockDecl::capture_const_iterator it = BD->capture_begin(), 114238106Sdes et = BD->capture_end(); it != et; ++it) { 115238106Sdes const VarDecl *VD = it->getVariable(); 116238106Sdes if (VD->getName() == "self") 117238106Sdes return dyn_cast<ImplicitParamDecl>(VD); 118238106Sdes } 119238106Sdes } 120238106Sdes 121238106Sdes return NULL; 122238106Sdes} 123238106Sdes 124238106Sdesvoid AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) { 125238106Sdes if (!forcedBlkExprs) 126238106Sdes forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs(); 127238106Sdes // Default construct an entry for 'stmt'. 128238106Sdes if (const Expr *e = dyn_cast<Expr>(stmt)) 129238106Sdes stmt = e->IgnoreParens(); 130238106Sdes (void) (*forcedBlkExprs)[stmt]; 131238106Sdes} 132238106Sdes 133238106Sdesconst CFGBlock * 134238106SdesAnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) { 135238106Sdes assert(forcedBlkExprs); 136238106Sdes if (const Expr *e = dyn_cast<Expr>(stmt)) 137238106Sdes stmt = e->IgnoreParens(); 138238106Sdes CFG::BuildOptions::ForcedBlkExprs::const_iterator itr = 139238106Sdes forcedBlkExprs->find(stmt); 140238106Sdes assert(itr != forcedBlkExprs->end()); 141238106Sdes return itr->second; 142238106Sdes} 143238106Sdes 144269257SdesCFG *AnalysisDeclContext::getCFG() { 145238106Sdes if (!cfgBuildOptions.PruneTriviallyFalseEdges) 146238106Sdes return getUnoptimizedCFG(); 147238106Sdes 148238106Sdes if (!builtCFG) { 149238106Sdes cfg.reset(CFG::buildCFG(D, getBody(), 150238106Sdes &D->getASTContext(), cfgBuildOptions)); 151238106Sdes // Even when the cfg is not successfully built, we don't 152238106Sdes // want to try building it again. 153238106Sdes builtCFG = true; 154238106Sdes } 155238106Sdes return cfg.get(); 156238106Sdes} 157238106Sdes 158238106SdesCFG *AnalysisDeclContext::getUnoptimizedCFG() { 159238106Sdes if (!builtCompleteCFG) { 160238106Sdes SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges, 161238106Sdes false); 162238106Sdes completeCFG.reset(CFG::buildCFG(D, getBody(), &D->getASTContext(), 163238106Sdes cfgBuildOptions)); 164238106Sdes // Even when the cfg is not successfully built, we don't 165238106Sdes // want to try building it again. 166238106Sdes builtCompleteCFG = true; 167238106Sdes } 168238106Sdes return completeCFG.get(); 169238106Sdes} 170238106Sdes 171238106SdesCFGStmtMap *AnalysisDeclContext::getCFGStmtMap() { 172238106Sdes if (cfgStmtMap) 173238106Sdes return cfgStmtMap.get(); 174238106Sdes 175238106Sdes if (CFG *c = getCFG()) { 176238106Sdes cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap())); 177238106Sdes return cfgStmtMap.get(); 178238106Sdes } 179238106Sdes 180238106Sdes return 0; 181238106Sdes} 182238106Sdes 183238106SdesCFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() { 184238106Sdes if (CFA) 185238106Sdes return CFA.get(); 186238106Sdes 187238106Sdes if (CFG *c = getCFG()) { 188238106Sdes CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c)); 189238106Sdes return CFA.get(); 190238106Sdes } 191238106Sdes 192238106Sdes return 0; 193238106Sdes} 194238106Sdes 195238106Sdesvoid AnalysisDeclContext::dumpCFG(bool ShowColors) { 196238106Sdes getCFG()->dump(getASTContext().getLangOpts(), ShowColors); 197238106Sdes} 198238106Sdes 199238106SdesParentMap &AnalysisDeclContext::getParentMap() { 200238106Sdes if (!PM) { 201238106Sdes PM.reset(new ParentMap(getBody())); 202238106Sdes if (const CXXConstructorDecl *C = dyn_cast<CXXConstructorDecl>(getDecl())) { 203238106Sdes for (CXXConstructorDecl::init_const_iterator I = C->init_begin(), 204238106Sdes E = C->init_end(); 205238106Sdes I != E; ++I) { 206238106Sdes PM->addStmt((*I)->getInit()); 207238106Sdes } 208238106Sdes } 209238106Sdes } 210238106Sdes return *PM; 211238106Sdes} 212238106Sdes 213238106SdesPseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() { 214238106Sdes if (!PCA) 215238106Sdes PCA.reset(new PseudoConstantAnalysis(getBody())); 216238106Sdes return PCA.get(); 217238106Sdes} 218238106Sdes 219238106SdesAnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) { 220238106Sdes if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 221238106Sdes // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl 222238106Sdes // that has the body. 223238106Sdes FD->hasBody(FD); 224238106Sdes D = FD; 225238106Sdes } 226269257Sdes 227238106Sdes AnalysisDeclContext *&AC = Contexts[D]; 228238106Sdes if (!AC) 229238106Sdes AC = new AnalysisDeclContext(this, D, cfgBuildOptions); 230238106Sdes return AC; 231238106Sdes} 232238106Sdes 233238106Sdesconst StackFrameContext * 234238106SdesAnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, 235238106Sdes const CFGBlock *Blk, unsigned Idx) { 236269257Sdes return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx); 237238106Sdes} 238238106Sdes 239238106Sdesconst BlockInvocationContext * 240238106SdesAnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent, 241238106Sdes const clang::BlockDecl *BD, 242238106Sdes const void *ContextData) { 243238106Sdes return getLocationContextManager().getBlockInvocationContext(this, parent, 244238106Sdes BD, ContextData); 245238106Sdes} 246238106Sdes 247238106SdesLocationContextManager & AnalysisDeclContext::getLocationContextManager() { 248238106Sdes assert(Manager && 249238106Sdes "Cannot create LocationContexts without an AnalysisDeclContextManager!"); 250238106Sdes return Manager->getLocationContextManager(); 251238106Sdes} 252238106Sdes 253238106Sdes//===----------------------------------------------------------------------===// 254238106Sdes// FoldingSet profiling. 255238106Sdes//===----------------------------------------------------------------------===// 256238106Sdes 257238106Sdesvoid LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, 258238106Sdes ContextKind ck, 259238106Sdes AnalysisDeclContext *ctx, 260238106Sdes const LocationContext *parent, 261238106Sdes const void *data) { 262238106Sdes ID.AddInteger(ck); 263238106Sdes ID.AddPointer(ctx); 264238106Sdes ID.AddPointer(parent); 265238106Sdes ID.AddPointer(data); 266269257Sdes} 267238106Sdes 268238106Sdesvoid StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { 269238106Sdes Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); 270238106Sdes} 271238106Sdes 272238106Sdesvoid ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { 273238106Sdes Profile(ID, getAnalysisDeclContext(), getParent(), Enter); 274238106Sdes} 275238106Sdes 276238106Sdesvoid BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { 277269257Sdes Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData); 278238106Sdes} 279238106Sdes 280238106Sdes//===----------------------------------------------------------------------===// 281238106Sdes// LocationContext creation. 282238106Sdes//===----------------------------------------------------------------------===// 283238106Sdes 284238106Sdestemplate <typename LOC, typename DATA> 285238106Sdesconst LOC* 286238106SdesLocationContextManager::getLocationContext(AnalysisDeclContext *ctx, 287238106Sdes const LocationContext *parent, 288238106Sdes const DATA *d) { 289238106Sdes llvm::FoldingSetNodeID ID; 290238106Sdes LOC::Profile(ID, ctx, parent, d); 291238106Sdes void *InsertPos; 292238106Sdes 293269257Sdes LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); 294238106Sdes 295238106Sdes if (!L) { 296238106Sdes L = new LOC(ctx, parent, d); 297238106Sdes Contexts.InsertNode(L, InsertPos); 298238106Sdes } 299238106Sdes return L; 300238106Sdes} 301238106Sdes 302238106Sdesconst StackFrameContext* 303238106SdesLocationContextManager::getStackFrame(AnalysisDeclContext *ctx, 304 const LocationContext *parent, 305 const Stmt *s, 306 const CFGBlock *blk, unsigned idx) { 307 llvm::FoldingSetNodeID ID; 308 StackFrameContext::Profile(ID, ctx, parent, s, blk, idx); 309 void *InsertPos; 310 StackFrameContext *L = 311 cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); 312 if (!L) { 313 L = new StackFrameContext(ctx, parent, s, blk, idx); 314 Contexts.InsertNode(L, InsertPos); 315 } 316 return L; 317} 318 319const ScopeContext * 320LocationContextManager::getScope(AnalysisDeclContext *ctx, 321 const LocationContext *parent, 322 const Stmt *s) { 323 return getLocationContext<ScopeContext, Stmt>(ctx, parent, s); 324} 325 326const BlockInvocationContext * 327LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx, 328 const LocationContext *parent, 329 const BlockDecl *BD, 330 const void *ContextData) { 331 llvm::FoldingSetNodeID ID; 332 BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData); 333 void *InsertPos; 334 BlockInvocationContext *L = 335 cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID, 336 InsertPos)); 337 if (!L) { 338 L = new BlockInvocationContext(ctx, parent, BD, ContextData); 339 Contexts.InsertNode(L, InsertPos); 340 } 341 return L; 342} 343 344//===----------------------------------------------------------------------===// 345// LocationContext methods. 346//===----------------------------------------------------------------------===// 347 348const StackFrameContext *LocationContext::getCurrentStackFrame() const { 349 const LocationContext *LC = this; 350 while (LC) { 351 if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) 352 return SFC; 353 LC = LC->getParent(); 354 } 355 return NULL; 356} 357 358bool LocationContext::inTopFrame() const { 359 return getCurrentStackFrame()->inTopFrame(); 360} 361 362bool LocationContext::isParentOf(const LocationContext *LC) const { 363 do { 364 const LocationContext *Parent = LC->getParent(); 365 if (Parent == this) 366 return true; 367 else 368 LC = Parent; 369 } while (LC); 370 371 return false; 372} 373 374//===----------------------------------------------------------------------===// 375// Lazily generated map to query the external variables referenced by a Block. 376//===----------------------------------------------------------------------===// 377 378namespace { 379class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{ 380 BumpVector<const VarDecl*> &BEVals; 381 BumpVectorContext &BC; 382 llvm::SmallPtrSet<const VarDecl*, 4> Visited; 383 llvm::SmallPtrSet<const DeclContext*, 4> IgnoredContexts; 384public: 385 FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals, 386 BumpVectorContext &bc) 387 : BEVals(bevals), BC(bc) {} 388 389 bool IsTrackedDecl(const VarDecl *VD) { 390 const DeclContext *DC = VD->getDeclContext(); 391 return IgnoredContexts.count(DC) == 0; 392 } 393 394 void VisitStmt(Stmt *S) { 395 for (Stmt::child_range I = S->children(); I; ++I) 396 if (Stmt *child = *I) 397 Visit(child); 398 } 399 400 void VisitDeclRefExpr(DeclRefExpr *DR) { 401 // Non-local variables are also directly modified. 402 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 403 if (!VD->hasLocalStorage()) { 404 if (Visited.insert(VD)) 405 BEVals.push_back(VD, BC); 406 } else if (DR->refersToEnclosingLocal()) { 407 if (Visited.insert(VD) && IsTrackedDecl(VD)) 408 BEVals.push_back(VD, BC); 409 } 410 } 411 } 412 413 void VisitBlockExpr(BlockExpr *BR) { 414 // Blocks containing blocks can transitively capture more variables. 415 IgnoredContexts.insert(BR->getBlockDecl()); 416 Visit(BR->getBlockDecl()->getBody()); 417 } 418 419 void VisitPseudoObjectExpr(PseudoObjectExpr *PE) { 420 for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(), 421 et = PE->semantics_end(); it != et; ++it) { 422 Expr *Semantic = *it; 423 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic)) 424 Semantic = OVE->getSourceExpr(); 425 Visit(Semantic); 426 } 427 } 428}; 429} // end anonymous namespace 430 431typedef BumpVector<const VarDecl*> DeclVec; 432 433static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD, 434 void *&Vec, 435 llvm::BumpPtrAllocator &A) { 436 if (Vec) 437 return (DeclVec*) Vec; 438 439 BumpVectorContext BC(A); 440 DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>(); 441 new (BV) DeclVec(BC, 10); 442 443 // Find the referenced variables. 444 FindBlockDeclRefExprsVals F(*BV, BC); 445 F.Visit(BD->getBody()); 446 447 Vec = BV; 448 return BV; 449} 450 451std::pair<AnalysisDeclContext::referenced_decls_iterator, 452 AnalysisDeclContext::referenced_decls_iterator> 453AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) { 454 if (!ReferencedBlockVars) 455 ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>(); 456 457 DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A); 458 return std::make_pair(V->begin(), V->end()); 459} 460 461ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) { 462 if (!ManagedAnalyses) 463 ManagedAnalyses = new ManagedAnalysisMap(); 464 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; 465 return (*M)[tag]; 466} 467 468//===----------------------------------------------------------------------===// 469// Cleanup. 470//===----------------------------------------------------------------------===// 471 472ManagedAnalysis::~ManagedAnalysis() {} 473 474AnalysisDeclContext::~AnalysisDeclContext() { 475 delete forcedBlkExprs; 476 delete ReferencedBlockVars; 477 // Release the managed analyses. 478 if (ManagedAnalyses) { 479 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; 480 for (ManagedAnalysisMap::iterator I = M->begin(), E = M->end(); I!=E; ++I) 481 delete I->second; 482 delete M; 483 } 484} 485 486AnalysisDeclContextManager::~AnalysisDeclContextManager() { 487 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 488 delete I->second; 489} 490 491LocationContext::~LocationContext() {} 492 493LocationContextManager::~LocationContextManager() { 494 clear(); 495} 496 497void LocationContextManager::clear() { 498 for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(), 499 E = Contexts.end(); I != E; ) { 500 LocationContext *LC = &*I; 501 ++I; 502 delete LC; 503 } 504 505 Contexts.clear(); 506} 507 508