AnalysisDeclContext.cpp revision d200187bd27f9ad68699693a6e57f9ee3ff260fa
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 207LocationContextManager & AnalysisDeclContext::getLocationContextManager() { 208 assert(Manager && 209 "Cannot create LocationContexts without an AnalysisDeclContextManager!"); 210 return Manager->getLocationContextManager(); 211} 212 213//===----------------------------------------------------------------------===// 214// FoldingSet profiling. 215//===----------------------------------------------------------------------===// 216 217void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, 218 ContextKind ck, 219 AnalysisDeclContext *ctx, 220 const LocationContext *parent, 221 const void *data) { 222 ID.AddInteger(ck); 223 ID.AddPointer(ctx); 224 ID.AddPointer(parent); 225 ID.AddPointer(data); 226} 227 228void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { 229 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); 230} 231 232void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { 233 Profile(ID, getAnalysisDeclContext(), getParent(), Enter); 234} 235 236void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { 237 Profile(ID, getAnalysisDeclContext(), getParent(), BD); 238} 239 240//===----------------------------------------------------------------------===// 241// LocationContext creation. 242//===----------------------------------------------------------------------===// 243 244template <typename LOC, typename DATA> 245const LOC* 246LocationContextManager::getLocationContext(AnalysisDeclContext *ctx, 247 const LocationContext *parent, 248 const DATA *d) { 249 llvm::FoldingSetNodeID ID; 250 LOC::Profile(ID, ctx, parent, d); 251 void *InsertPos; 252 253 LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); 254 255 if (!L) { 256 L = new LOC(ctx, parent, d); 257 Contexts.InsertNode(L, InsertPos); 258 } 259 return L; 260} 261 262const StackFrameContext* 263LocationContextManager::getStackFrame(AnalysisDeclContext *ctx, 264 const LocationContext *parent, 265 const Stmt *s, 266 const CFGBlock *blk, unsigned idx) { 267 llvm::FoldingSetNodeID ID; 268 StackFrameContext::Profile(ID, ctx, parent, s, blk, idx); 269 void *InsertPos; 270 StackFrameContext *L = 271 cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); 272 if (!L) { 273 L = new StackFrameContext(ctx, parent, s, blk, idx); 274 Contexts.InsertNode(L, InsertPos); 275 } 276 return L; 277} 278 279const ScopeContext * 280LocationContextManager::getScope(AnalysisDeclContext *ctx, 281 const LocationContext *parent, 282 const Stmt *s) { 283 return getLocationContext<ScopeContext, Stmt>(ctx, parent, s); 284} 285 286//===----------------------------------------------------------------------===// 287// LocationContext methods. 288//===----------------------------------------------------------------------===// 289 290const StackFrameContext *LocationContext::getCurrentStackFrame() const { 291 const LocationContext *LC = this; 292 while (LC) { 293 if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) 294 return SFC; 295 LC = LC->getParent(); 296 } 297 return NULL; 298} 299 300const StackFrameContext * 301LocationContext::getStackFrameForDeclContext(const DeclContext *DC) const { 302 const LocationContext *LC = this; 303 while (LC) { 304 if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) { 305 if (cast<DeclContext>(SFC->getDecl()) == DC) 306 return SFC; 307 } 308 LC = LC->getParent(); 309 } 310 return NULL; 311} 312 313bool LocationContext::isParentOf(const LocationContext *LC) const { 314 do { 315 const LocationContext *Parent = LC->getParent(); 316 if (Parent == this) 317 return true; 318 else 319 LC = Parent; 320 } while (LC); 321 322 return false; 323} 324 325//===----------------------------------------------------------------------===// 326// Lazily generated map to query the external variables referenced by a Block. 327//===----------------------------------------------------------------------===// 328 329namespace { 330class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{ 331 BumpVector<const VarDecl*> &BEVals; 332 BumpVectorContext &BC; 333 llvm::SmallPtrSet<const VarDecl*, 4> Visited; 334 llvm::SmallPtrSet<const DeclContext*, 4> IgnoredContexts; 335public: 336 FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals, 337 BumpVectorContext &bc) 338 : BEVals(bevals), BC(bc) {} 339 340 bool IsTrackedDecl(const VarDecl *VD) { 341 const DeclContext *DC = VD->getDeclContext(); 342 return IgnoredContexts.count(DC) == 0; 343 } 344 345 void VisitStmt(Stmt *S) { 346 for (Stmt::child_range I = S->children(); I; ++I) 347 if (Stmt *child = *I) 348 Visit(child); 349 } 350 351 void VisitDeclRefExpr(DeclRefExpr *DR) { 352 // Non-local variables are also directly modified. 353 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 354 if (!VD->hasLocalStorage()) { 355 if (Visited.insert(VD)) 356 BEVals.push_back(VD, BC); 357 } else if (DR->refersToEnclosingLocal()) { 358 if (Visited.insert(VD) && IsTrackedDecl(VD)) 359 BEVals.push_back(VD, BC); 360 } 361 } 362 } 363 364 void VisitBlockExpr(BlockExpr *BR) { 365 // Blocks containing blocks can transitively capture more variables. 366 IgnoredContexts.insert(BR->getBlockDecl()); 367 Visit(BR->getBlockDecl()->getBody()); 368 } 369 370 void VisitPseudoObjectExpr(PseudoObjectExpr *PE) { 371 for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(), 372 et = PE->semantics_end(); it != et; ++it) { 373 Expr *Semantic = *it; 374 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic)) 375 Semantic = OVE->getSourceExpr(); 376 Visit(Semantic); 377 } 378 } 379}; 380} // end anonymous namespace 381 382typedef BumpVector<const VarDecl*> DeclVec; 383 384static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD, 385 void *&Vec, 386 llvm::BumpPtrAllocator &A) { 387 if (Vec) 388 return (DeclVec*) Vec; 389 390 BumpVectorContext BC(A); 391 DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>(); 392 new (BV) DeclVec(BC, 10); 393 394 // Find the referenced variables. 395 FindBlockDeclRefExprsVals F(*BV, BC); 396 F.Visit(BD->getBody()); 397 398 Vec = BV; 399 return BV; 400} 401 402std::pair<AnalysisDeclContext::referenced_decls_iterator, 403 AnalysisDeclContext::referenced_decls_iterator> 404AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) { 405 if (!ReferencedBlockVars) 406 ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>(); 407 408 DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A); 409 return std::make_pair(V->begin(), V->end()); 410} 411 412ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) { 413 if (!ManagedAnalyses) 414 ManagedAnalyses = new ManagedAnalysisMap(); 415 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; 416 return (*M)[tag]; 417} 418 419//===----------------------------------------------------------------------===// 420// Cleanup. 421//===----------------------------------------------------------------------===// 422 423ManagedAnalysis::~ManagedAnalysis() {} 424 425AnalysisDeclContext::~AnalysisDeclContext() { 426 delete forcedBlkExprs; 427 delete ReferencedBlockVars; 428 // Release the managed analyses. 429 if (ManagedAnalyses) { 430 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; 431 for (ManagedAnalysisMap::iterator I = M->begin(), E = M->end(); I!=E; ++I) 432 delete I->second; 433 delete M; 434 } 435} 436 437AnalysisDeclContextManager::~AnalysisDeclContextManager() { 438 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 439 delete I->second; 440} 441 442LocationContext::~LocationContext() {} 443 444LocationContextManager::~LocationContextManager() { 445 clear(); 446} 447 448void LocationContextManager::clear() { 449 for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(), 450 E = Contexts.end(); I != E; ) { 451 LocationContext *LC = &*I; 452 ++I; 453 delete LC; 454 } 455 456 Contexts.clear(); 457} 458 459