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