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