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