AnalysisDeclContext.cpp revision fadcd5d5bbe1bfc1c6b8d819cc2242f780a49fec
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/AST/ASTContext.h" 16#include "clang/AST/Decl.h" 17#include "clang/AST/DeclObjC.h" 18#include "clang/AST/DeclTemplate.h" 19#include "clang/AST/ParentMap.h" 20#include "clang/AST/StmtVisitor.h" 21#include "clang/Analysis/Analyses/LiveVariables.h" 22#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" 23#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 24#include "clang/Analysis/AnalysisContext.h" 25#include "clang/Analysis/CFG.h" 26#include "clang/Analysis/CFGStmtMap.h" 27#include "clang/Analysis/Support/BumpVector.h" 28#include "llvm/Support/SaveAndRestore.h" 29#include "llvm/ADT/SmallPtrSet.h" 30#include "llvm/Support/ErrorHandling.h" 31 32#include "BodyFarm.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 : SynthesizeBodies(synthesizeBodies) 72{ 73 cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG; 74 cfgBuildOptions.AddImplicitDtors = addImplicitDtors; 75 cfgBuildOptions.AddInitializers = addInitializers; 76 cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors; 77} 78 79void AnalysisDeclContextManager::clear() { 80 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 81 delete I->second; 82 Contexts.clear(); 83} 84 85static BodyFarm &getBodyFarm(ASTContext &C) { 86 static BodyFarm *BF = new BodyFarm(C); 87 return *BF; 88} 89 90Stmt *AnalysisDeclContext::getBody() const { 91 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 92 Stmt *Body = FD->getBody(); 93 if (!Body && Manager && Manager->synthesizeBodies()) 94 return getBodyFarm(getASTContext()).getBody(FD); 95 return Body; 96 } 97 else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) 98 return MD->getBody(); 99 else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) 100 return BD->getBody(); 101 else if (const FunctionTemplateDecl *FunTmpl 102 = dyn_cast_or_null<FunctionTemplateDecl>(D)) 103 return FunTmpl->getTemplatedDecl()->getBody(); 104 105 llvm_unreachable("unknown code decl"); 106} 107 108const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const { 109 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) 110 return MD->getSelfDecl(); 111 if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { 112 // See if 'self' was captured by the block. 113 for (BlockDecl::capture_const_iterator it = BD->capture_begin(), 114 et = BD->capture_end(); it != et; ++it) { 115 const VarDecl *VD = it->getVariable(); 116 if (VD->getName() == "self") 117 return dyn_cast<ImplicitParamDecl>(VD); 118 } 119 } 120 121 return NULL; 122} 123 124void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) { 125 if (!forcedBlkExprs) 126 forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs(); 127 // Default construct an entry for 'stmt'. 128 if (const Expr *e = dyn_cast<Expr>(stmt)) 129 stmt = e->IgnoreParens(); 130 (void) (*forcedBlkExprs)[stmt]; 131} 132 133const CFGBlock * 134AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) { 135 assert(forcedBlkExprs); 136 if (const Expr *e = dyn_cast<Expr>(stmt)) 137 stmt = e->IgnoreParens(); 138 CFG::BuildOptions::ForcedBlkExprs::const_iterator itr = 139 forcedBlkExprs->find(stmt); 140 assert(itr != forcedBlkExprs->end()); 141 return itr->second; 142} 143 144CFG *AnalysisDeclContext::getCFG() { 145 if (!cfgBuildOptions.PruneTriviallyFalseEdges) 146 return getUnoptimizedCFG(); 147 148 if (!builtCFG) { 149 cfg.reset(CFG::buildCFG(D, getBody(), 150 &D->getASTContext(), cfgBuildOptions)); 151 // Even when the cfg is not successfully built, we don't 152 // want to try building it again. 153 builtCFG = true; 154 } 155 return cfg.get(); 156} 157 158CFG *AnalysisDeclContext::getUnoptimizedCFG() { 159 if (!builtCompleteCFG) { 160 SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges, 161 false); 162 completeCFG.reset(CFG::buildCFG(D, getBody(), &D->getASTContext(), 163 cfgBuildOptions)); 164 // Even when the cfg is not successfully built, we don't 165 // want to try building it again. 166 builtCompleteCFG = true; 167 } 168 return completeCFG.get(); 169} 170 171CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() { 172 if (cfgStmtMap) 173 return cfgStmtMap.get(); 174 175 if (CFG *c = getCFG()) { 176 cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap())); 177 return cfgStmtMap.get(); 178 } 179 180 return 0; 181} 182 183CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() { 184 if (CFA) 185 return CFA.get(); 186 187 if (CFG *c = getCFG()) { 188 CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c)); 189 return CFA.get(); 190 } 191 192 return 0; 193} 194 195void AnalysisDeclContext::dumpCFG(bool ShowColors) { 196 getCFG()->dump(getASTContext().getLangOpts(), ShowColors); 197} 198 199ParentMap &AnalysisDeclContext::getParentMap() { 200 if (!PM) { 201 PM.reset(new ParentMap(getBody())); 202 if (const CXXConstructorDecl *C = dyn_cast<CXXConstructorDecl>(getDecl())) { 203 for (CXXConstructorDecl::init_const_iterator I = C->init_begin(), 204 E = C->init_end(); 205 I != E; ++I) { 206 PM->addStmt((*I)->getInit()); 207 } 208 } 209 } 210 return *PM; 211} 212 213PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() { 214 if (!PCA) 215 PCA.reset(new PseudoConstantAnalysis(getBody())); 216 return PCA.get(); 217} 218 219AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) { 220 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 221 // Calling 'hasBody' replaces 'FD' in place with the FunctionDecl 222 // that has the body. 223 FD->hasBody(FD); 224 D = FD; 225 } 226 227 AnalysisDeclContext *&AC = Contexts[D]; 228 if (!AC) 229 AC = new AnalysisDeclContext(this, D, cfgBuildOptions); 230 return AC; 231} 232 233const StackFrameContext * 234AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, 235 const CFGBlock *Blk, unsigned Idx) { 236 return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx); 237} 238 239const BlockInvocationContext * 240AnalysisDeclContext::getBlockInvocationContext(const LocationContext *parent, 241 const clang::BlockDecl *BD, 242 const void *ContextData) { 243 return getLocationContextManager().getBlockInvocationContext(this, parent, 244 BD, ContextData); 245} 246 247LocationContextManager & AnalysisDeclContext::getLocationContextManager() { 248 assert(Manager && 249 "Cannot create LocationContexts without an AnalysisDeclContextManager!"); 250 return Manager->getLocationContextManager(); 251} 252 253//===----------------------------------------------------------------------===// 254// FoldingSet profiling. 255//===----------------------------------------------------------------------===// 256 257void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, 258 ContextKind ck, 259 AnalysisDeclContext *ctx, 260 const LocationContext *parent, 261 const void *data) { 262 ID.AddInteger(ck); 263 ID.AddPointer(ctx); 264 ID.AddPointer(parent); 265 ID.AddPointer(data); 266} 267 268void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { 269 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); 270} 271 272void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { 273 Profile(ID, getAnalysisDeclContext(), getParent(), Enter); 274} 275 276void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { 277 Profile(ID, getAnalysisDeclContext(), getParent(), BD, ContextData); 278} 279 280//===----------------------------------------------------------------------===// 281// LocationContext creation. 282//===----------------------------------------------------------------------===// 283 284template <typename LOC, typename DATA> 285const LOC* 286LocationContextManager::getLocationContext(AnalysisDeclContext *ctx, 287 const LocationContext *parent, 288 const DATA *d) { 289 llvm::FoldingSetNodeID ID; 290 LOC::Profile(ID, ctx, parent, d); 291 void *InsertPos; 292 293 LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); 294 295 if (!L) { 296 L = new LOC(ctx, parent, d); 297 Contexts.InsertNode(L, InsertPos); 298 } 299 return L; 300} 301 302const StackFrameContext* 303LocationContextManager::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