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