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