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