AnalysisDeclContext.cpp revision 453cb859a3c8dcafe79ae840dfc35ff8eae1b4b3
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 33using namespace clang; 34 35typedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap; 36 37AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 38 const Decl *d, 39 const CFG::BuildOptions &buildOptions) 40 : Manager(Mgr), 41 D(d), 42 cfgBuildOptions(buildOptions), 43 forcedBlkExprs(0), 44 builtCFG(false), 45 builtCompleteCFG(false), 46 ReferencedBlockVars(0), 47 ManagedAnalyses(0) 48{ 49 cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; 50} 51 52AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 53 const Decl *d) 54: Manager(Mgr), 55 D(d), 56 forcedBlkExprs(0), 57 builtCFG(false), 58 builtCompleteCFG(false), 59 ReferencedBlockVars(0), 60 ManagedAnalyses(0) 61{ 62 cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; 63} 64 65AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG, 66 bool addImplicitDtors, 67 bool addInitializers, 68 bool addTemporaryDtors, 69 bool synthesizeBodies) 70 : SynthesizeBodies(synthesizeBodies) 71{ 72 cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG; 73 cfgBuildOptions.AddImplicitDtors = addImplicitDtors; 74 cfgBuildOptions.AddInitializers = addInitializers; 75 cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors; 76} 77 78void AnalysisDeclContextManager::clear() { 79 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 80 delete I->second; 81 Contexts.clear(); 82} 83 84static BodyFarm &getBodyFarm(ASTContext &C) { 85 static BodyFarm *BF = new BodyFarm(C); 86 return *BF; 87} 88 89Stmt *AnalysisDeclContext::getBody(bool &IsAutosynthesized) const { 90 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 91 Stmt *Body = FD->getBody(); 92 if (!Body && Manager && Manager->synthesizeBodies()) { 93 IsAutosynthesized = true; 94 return getBodyFarm(getASTContext()).getBody(FD); 95 } 96 return Body; 97 } 98 else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) 99 return MD->getBody(); 100 else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) 101 return BD->getBody(); 102 else if (const FunctionTemplateDecl *FunTmpl 103 = dyn_cast_or_null<FunctionTemplateDecl>(D)) 104 return FunTmpl->getTemplatedDecl()->getBody(); 105 106 llvm_unreachable("unknown code decl"); 107} 108 109Stmt *AnalysisDeclContext::getBody() const { 110 bool Tmp; 111 return getBody(Tmp); 112} 113 114bool AnalysisDeclContext::isBodyAutosynthesized() const { 115 bool Tmp; 116 getBody(Tmp); 117 return Tmp; 118} 119 120const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const { 121 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) 122 return MD->getSelfDecl(); 123 if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { 124 // See if 'self' was captured by the block. 125 for (BlockDecl::capture_const_iterator it = BD->capture_begin(), 126 et = BD->capture_end(); it != et; ++it) { 127 const VarDecl *VD = it->getVariable(); 128 if (VD->getName() == "self") 129 return dyn_cast<ImplicitParamDecl>(VD); 130 } 131 } 132 133 return NULL; 134} 135 136void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) { 137 if (!forcedBlkExprs) 138 forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs(); 139 // Default construct an entry for 'stmt'. 140 if (const Expr *e = dyn_cast<Expr>(stmt)) 141 stmt = e->IgnoreParens(); 142 (void) (*forcedBlkExprs)[stmt]; 143} 144 145const CFGBlock * 146AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) { 147 assert(forcedBlkExprs); 148 if (const Expr *e = dyn_cast<Expr>(stmt)) 149 stmt = e->IgnoreParens(); 150 CFG::BuildOptions::ForcedBlkExprs::const_iterator itr = 151 forcedBlkExprs->find(stmt); 152 assert(itr != forcedBlkExprs->end()); 153 return itr->second; 154} 155 156CFG *AnalysisDeclContext::getCFG() { 157 if (!cfgBuildOptions.PruneTriviallyFalseEdges) 158 return getUnoptimizedCFG(); 159 160 if (!builtCFG) { 161 cfg.reset(CFG::buildCFG(D, getBody(), 162 &D->getASTContext(), cfgBuildOptions)); 163 // Even when the cfg is not successfully built, we don't 164 // want to try building it again. 165 builtCFG = true; 166 } 167 return cfg.get(); 168} 169 170CFG *AnalysisDeclContext::getUnoptimizedCFG() { 171 if (!builtCompleteCFG) { 172 SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges, 173 false); 174 completeCFG.reset(CFG::buildCFG(D, getBody(), &D->getASTContext(), 175 cfgBuildOptions)); 176 // Even when the cfg is not successfully built, we don't 177 // want to try building it again. 178 builtCompleteCFG = true; 179 } 180 return completeCFG.get(); 181} 182 183CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() { 184 if (cfgStmtMap) 185 return cfgStmtMap.get(); 186 187 if (CFG *c = getCFG()) { 188 cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap())); 189 return cfgStmtMap.get(); 190 } 191 192 return 0; 193} 194 195CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() { 196 if (CFA) 197 return CFA.get(); 198 199 if (CFG *c = getCFG()) { 200 CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c)); 201 return CFA.get(); 202 } 203 204 return 0; 205} 206 207void AnalysisDeclContext::dumpCFG(bool ShowColors) { 208 getCFG()->dump(getASTContext().getLangOpts(), ShowColors); 209} 210 211ParentMap &AnalysisDeclContext::getParentMap() { 212 if (!PM) { 213 PM.reset(new ParentMap(getBody())); 214 if (const CXXConstructorDecl *C = dyn_cast<CXXConstructorDecl>(getDecl())) { 215 for (CXXConstructorDecl::init_const_iterator I = C->init_begin(), 216 E = C->init_end(); 217 I != E; ++I) { 218 PM->addStmt((*I)->getInit()); 219 } 220 } 221 } 222 return *PM; 223} 224 225PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() { 226 if (!PCA) 227 PCA.reset(new PseudoConstantAnalysis(getBody())); 228 return PCA.get(); 229} 230 231AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) { 232 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 233 // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl 234 // that has the body. 235 FD->hasBody(FD); 236 D = FD; 237 } 238 239 AnalysisDeclContext *&AC = Contexts[D]; 240 if (!AC) 241 AC = new AnalysisDeclContext(this, D, cfgBuildOptions); 242 return AC; 243} 244 245const StackFrameContext * 246AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, 247 const CFGBlock *Blk, unsigned Idx) { 248 return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx); 249} 250 251const BlockInvocationContext * 252AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent, 253 const clang::BlockDecl *BD, 254 const void *ContextData) { 255 return getLocationContextManager().getBlockInvocationContext(this, parent, 256 BD, ContextData); 257} 258 259LocationContextManager & AnalysisDeclContext::getLocationContextManager() { 260 assert(Manager && 261 "Cannot create LocationContexts without an AnalysisDeclContextManager!"); 262 return Manager->getLocationContextManager(); 263} 264 265//===----------------------------------------------------------------------===// 266// FoldingSet profiling. 267//===----------------------------------------------------------------------===// 268 269void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, 270 ContextKind ck, 271 AnalysisDeclContext *ctx, 272 const LocationContext *parent, 273 const void *data) { 274 ID.AddInteger(ck); 275 ID.AddPointer(ctx); 276 ID.AddPointer(parent); 277 ID.AddPointer(data); 278} 279 280void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { 281 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); 282} 283 284void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { 285 Profile(ID, getAnalysisDeclContext(), getParent(), Enter); 286} 287 288void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { 289 Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData); 290} 291 292//===----------------------------------------------------------------------===// 293// LocationContext creation. 294//===----------------------------------------------------------------------===// 295 296template <typename LOC, typename DATA> 297const LOC* 298LocationContextManager::getLocationContext(AnalysisDeclContext *ctx, 299 const LocationContext *parent, 300 const DATA *d) { 301 llvm::FoldingSetNodeID ID; 302 LOC::Profile(ID, ctx, parent, d); 303 void *InsertPos; 304 305 LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); 306 307 if (!L) { 308 L = new LOC(ctx, parent, d); 309 Contexts.InsertNode(L, InsertPos); 310 } 311 return L; 312} 313 314const StackFrameContext* 315LocationContextManager::getStackFrame(AnalysisDeclContext *ctx, 316 const LocationContext *parent, 317 const Stmt *s, 318 const CFGBlock *blk, unsigned idx) { 319 llvm::FoldingSetNodeID ID; 320 StackFrameContext::Profile(ID, ctx, parent, s, blk, idx); 321 void *InsertPos; 322 StackFrameContext *L = 323 cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); 324 if (!L) { 325 L = new StackFrameContext(ctx, parent, s, blk, idx); 326 Contexts.InsertNode(L, InsertPos); 327 } 328 return L; 329} 330 331const ScopeContext * 332LocationContextManager::getScope(AnalysisDeclContext *ctx, 333 const LocationContext *parent, 334 const Stmt *s) { 335 return getLocationContext<ScopeContext, Stmt>(ctx, parent, s); 336} 337 338const BlockInvocationContext * 339LocationContextManager::getBlockInvocationContext(AnalysisDeclContext *ctx, 340 const LocationContext *parent, 341 const BlockDecl *BD, 342 const void *ContextData) { 343 llvm::FoldingSetNodeID ID; 344 BlockInvocationContext::Profile(ID, ctx, parent, BD, ContextData); 345 void *InsertPos; 346 BlockInvocationContext *L = 347 cast_or_null<BlockInvocationContext>(Contexts.FindNodeOrInsertPos(ID, 348 InsertPos)); 349 if (!L) { 350 L = new BlockInvocationContext(ctx, parent, BD, ContextData); 351 Contexts.InsertNode(L, InsertPos); 352 } 353 return L; 354} 355 356//===----------------------------------------------------------------------===// 357// LocationContext methods. 358//===----------------------------------------------------------------------===// 359 360const StackFrameContext *LocationContext::getCurrentStackFrame() const { 361 const LocationContext *LC = this; 362 while (LC) { 363 if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) 364 return SFC; 365 LC = LC->getParent(); 366 } 367 return NULL; 368} 369 370bool LocationContext::inTopFrame() const { 371 return getCurrentStackFrame()->inTopFrame(); 372} 373 374bool LocationContext::isParentOf(const LocationContext *LC) const { 375 do { 376 const LocationContext *Parent = LC->getParent(); 377 if (Parent == this) 378 return true; 379 else 380 LC = Parent; 381 } while (LC); 382 383 return false; 384} 385 386//===----------------------------------------------------------------------===// 387// Lazily generated map to query the external variables referenced by a Block. 388//===----------------------------------------------------------------------===// 389 390namespace { 391class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{ 392 BumpVector<const VarDecl*> &BEVals; 393 BumpVectorContext &BC; 394 llvm::SmallPtrSet<const VarDecl*, 4> Visited; 395 llvm::SmallPtrSet<const DeclContext*, 4> IgnoredContexts; 396public: 397 FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals, 398 BumpVectorContext &bc) 399 : BEVals(bevals), BC(bc) {} 400 401 bool IsTrackedDecl(const VarDecl *VD) { 402 const DeclContext *DC = VD->getDeclContext(); 403 return IgnoredContexts.count(DC) == 0; 404 } 405 406 void VisitStmt(Stmt *S) { 407 for (Stmt::child_range I = S->children(); I; ++I) 408 if (Stmt *child = *I) 409 Visit(child); 410 } 411 412 void VisitDeclRefExpr(DeclRefExpr *DR) { 413 // Non-local variables are also directly modified. 414 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 415 if (!VD->hasLocalStorage()) { 416 if (Visited.insert(VD)) 417 BEVals.push_back(VD, BC); 418 } 419 } 420 } 421 422 void VisitBlockExpr(BlockExpr *BR) { 423 // Blocks containing blocks can transitively capture more variables. 424 IgnoredContexts.insert(BR->getBlockDecl()); 425 Visit(BR->getBlockDecl()->getBody()); 426 } 427 428 void VisitPseudoObjectExpr(PseudoObjectExpr *PE) { 429 for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(), 430 et = PE->semantics_end(); it != et; ++it) { 431 Expr *Semantic = *it; 432 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic)) 433 Semantic = OVE->getSourceExpr(); 434 Visit(Semantic); 435 } 436 } 437}; 438} // end anonymous namespace 439 440typedef BumpVector<const VarDecl*> DeclVec; 441 442static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD, 443 void *&Vec, 444 llvm::BumpPtrAllocator &A) { 445 if (Vec) 446 return (DeclVec*) Vec; 447 448 BumpVectorContext BC(A); 449 DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>(); 450 new (BV) DeclVec(BC, 10); 451 452 // Go through the capture list. 453 for (BlockDecl::capture_const_iterator CI = BD->capture_begin(), 454 CE = BD->capture_end(); CI != CE; ++CI) { 455 BV->push_back(CI->getVariable(), BC); 456 } 457 458 // Find the referenced global/static variables. 459 FindBlockDeclRefExprsVals F(*BV, BC); 460 F.Visit(BD->getBody()); 461 462 Vec = BV; 463 return BV; 464} 465 466std::pair<AnalysisDeclContext::referenced_decls_iterator, 467 AnalysisDeclContext::referenced_decls_iterator> 468AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) { 469 if (!ReferencedBlockVars) 470 ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>(); 471 472 DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A); 473 return std::make_pair(V->begin(), V->end()); 474} 475 476ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) { 477 if (!ManagedAnalyses) 478 ManagedAnalyses = new ManagedAnalysisMap(); 479 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; 480 return (*M)[tag]; 481} 482 483//===----------------------------------------------------------------------===// 484// Cleanup. 485//===----------------------------------------------------------------------===// 486 487ManagedAnalysis::~ManagedAnalysis() {} 488 489AnalysisDeclContext::~AnalysisDeclContext() { 490 delete forcedBlkExprs; 491 delete ReferencedBlockVars; 492 // Release the managed analyses. 493 if (ManagedAnalyses) { 494 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; 495 for (ManagedAnalysisMap::iterator I = M->begin(), E = M->end(); I!=E; ++I) 496 delete I->second; 497 delete M; 498 } 499} 500 501AnalysisDeclContextManager::~AnalysisDeclContextManager() { 502 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 503 delete I->second; 504} 505 506LocationContext::~LocationContext() {} 507 508LocationContextManager::~LocationContextManager() { 509 clear(); 510} 511 512void LocationContextManager::clear() { 513 for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(), 514 E = Contexts.end(); I != E; ) { 515 LocationContext *LC = &*I; 516 ++I; 517 delete LC; 518 } 519 520 Contexts.clear(); 521} 522 523