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