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 31 using namespace clang; 32 33 typedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap; 34 35 AnalysisDeclContext::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 52 AnalysisDeclContext::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 67 AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG, 68 bool addImplicitDtors, 69 bool addInitializers) { 70 cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG; 71 cfgBuildOptions.AddImplicitDtors = addImplicitDtors; 72 cfgBuildOptions.AddInitializers = addInitializers; 73 } 74 75 void AnalysisDeclContextManager::clear() { 76 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 77 delete I->second; 78 Contexts.clear(); 79 } 80 81 Stmt *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 95 const 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 111 void 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 120 const CFGBlock * 121 AnalysisDeclContext::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 131 CFG *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 145 CFG *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 158 CFGStmtMap *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 170 CFGReverseBlockReachabilityAnalysis *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 182 void AnalysisDeclContext::dumpCFG(bool ShowColors) { 183 getCFG()->dump(getASTContext().getLangOpts(), ShowColors); 184 } 185 186 ParentMap &AnalysisDeclContext::getParentMap() { 187 if (!PM) 188 PM.reset(new ParentMap(getBody())); 189 return *PM; 190 } 191 192 PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() { 193 if (!PCA) 194 PCA.reset(new PseudoConstantAnalysis(getBody())); 195 return PCA.get(); 196 } 197 198 AnalysisDeclContext *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 206 const StackFrameContext * 207 AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, 208 const CFGBlock *Blk, unsigned Idx) { 209 return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx); 210 } 211 212 LocationContextManager & AnalysisDeclContext::getLocationContextManager() { 213 assert(Manager && 214 "Cannot create LocationContexts without an AnalysisDeclContextManager!"); 215 return Manager->getLocationContextManager(); 216 } 217 218 //===----------------------------------------------------------------------===// 219 // FoldingSet profiling. 220 //===----------------------------------------------------------------------===// 221 222 void 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 233 void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { 234 Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); 235 } 236 237 void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { 238 Profile(ID, getAnalysisDeclContext(), getParent(), Enter); 239 } 240 241 void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { 242 Profile(ID, getAnalysisDeclContext(), getParent(), BD); 243 } 244 245 //===----------------------------------------------------------------------===// 246 // LocationContext creation. 247 //===----------------------------------------------------------------------===// 248 249 template <typename LOC, typename DATA> 250 const LOC* 251 LocationContextManager::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 267 const StackFrameContext* 268 LocationContextManager::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 284 const ScopeContext * 285 LocationContextManager::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 295 const 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 305 const StackFrameContext * 306 LocationContext::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 318 bool 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 334 namespace { 335 class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{ 336 BumpVector<const VarDecl*> &BEVals; 337 BumpVectorContext &BC; 338 llvm::SmallPtrSet<const VarDecl*, 4> Visited; 339 llvm::SmallPtrSet<const DeclContext*, 4> IgnoredContexts; 340 public: 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 if (Visited.insert(VD)) 361 BEVals.push_back(VD, BC); 362 } else if (DR->refersToEnclosingLocal()) { 363 if (Visited.insert(VD) && IsTrackedDecl(VD)) 364 BEVals.push_back(VD, BC); 365 } 366 } 367 } 368 369 void VisitBlockExpr(BlockExpr *BR) { 370 // Blocks containing blocks can transitively capture more variables. 371 IgnoredContexts.insert(BR->getBlockDecl()); 372 Visit(BR->getBlockDecl()->getBody()); 373 } 374 375 void VisitPseudoObjectExpr(PseudoObjectExpr *PE) { 376 for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(), 377 et = PE->semantics_end(); it != et; ++it) { 378 Expr *Semantic = *it; 379 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic)) 380 Semantic = OVE->getSourceExpr(); 381 Visit(Semantic); 382 } 383 } 384 }; 385 } // end anonymous namespace 386 387 typedef BumpVector<const VarDecl*> DeclVec; 388 389 static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD, 390 void *&Vec, 391 llvm::BumpPtrAllocator &A) { 392 if (Vec) 393 return (DeclVec*) Vec; 394 395 BumpVectorContext BC(A); 396 DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>(); 397 new (BV) DeclVec(BC, 10); 398 399 // Find the referenced variables. 400 FindBlockDeclRefExprsVals F(*BV, BC); 401 F.Visit(BD->getBody()); 402 403 Vec = BV; 404 return BV; 405 } 406 407 std::pair<AnalysisDeclContext::referenced_decls_iterator, 408 AnalysisDeclContext::referenced_decls_iterator> 409 AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) { 410 if (!ReferencedBlockVars) 411 ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>(); 412 413 DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A); 414 return std::make_pair(V->begin(), V->end()); 415 } 416 417 ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) { 418 if (!ManagedAnalyses) 419 ManagedAnalyses = new ManagedAnalysisMap(); 420 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; 421 return (*M)[tag]; 422 } 423 424 //===----------------------------------------------------------------------===// 425 // Cleanup. 426 //===----------------------------------------------------------------------===// 427 428 ManagedAnalysis::~ManagedAnalysis() {} 429 430 AnalysisDeclContext::~AnalysisDeclContext() { 431 delete forcedBlkExprs; 432 delete ReferencedBlockVars; 433 // Release the managed analyses. 434 if (ManagedAnalyses) { 435 ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; 436 for (ManagedAnalysisMap::iterator I = M->begin(), E = M->end(); I!=E; ++I) 437 delete I->second; 438 delete M; 439 } 440 } 441 442 AnalysisDeclContextManager::~AnalysisDeclContextManager() { 443 for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) 444 delete I->second; 445 } 446 447 LocationContext::~LocationContext() {} 448 449 LocationContextManager::~LocationContextManager() { 450 clear(); 451 } 452 453 void LocationContextManager::clear() { 454 for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(), 455 E = Contexts.end(); I != E; ) { 456 LocationContext *LC = &*I; 457 ++I; 458 delete LC; 459 } 460 461 Contexts.clear(); 462 } 463 464
