AnalysisContext.h revision e9aae62e8bca3abfc1dc36f67845444291171e13
1//=== AnalysisContext.h - 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 11// context data for path sensitive analysis. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CLANG_ANALYSIS_ANALYSISCONTEXT_H 16#define LLVM_CLANG_ANALYSIS_ANALYSISCONTEXT_H 17 18#include "clang/AST/Decl.h" 19#include "clang/AST/Expr.h" 20#include "clang/Analysis/CFG.h" 21#include "llvm/ADT/DenseMap.h" 22#include "llvm/ADT/FoldingSet.h" 23#include "llvm/ADT/IntrusiveRefCntPtr.h" 24#include "llvm/ADT/OwningPtr.h" 25#include "llvm/ADT/PointerUnion.h" 26#include "llvm/Support/Allocator.h" 27 28namespace clang { 29 30class Decl; 31class Stmt; 32class CFGReverseBlockReachabilityAnalysis; 33class CFGStmtMap; 34class LiveVariables; 35class ManagedAnalysis; 36class ParentMap; 37class PseudoConstantAnalysis; 38class ImplicitParamDecl; 39class LocationContextManager; 40class StackFrameContext; 41class BlockInvocationContext; 42class AnalysisDeclContextManager; 43class LocationContext; 44 45namespace idx { class TranslationUnit; } 46 47/// The base class of a hierarchy of objects representing analyses tied 48/// to AnalysisDeclContext. 49class ManagedAnalysis { 50protected: 51 ManagedAnalysis() {} 52public: 53 virtual ~ManagedAnalysis(); 54 55 // Subclasses need to implement: 56 // 57 // static const void *getTag(); 58 // 59 // Which returns a fixed pointer address to distinguish classes of 60 // analysis objects. They also need to implement: 61 // 62 // static [Derived*] create(AnalysisDeclContext &Ctx); 63 // 64 // which creates the analysis object given an AnalysisDeclContext. 65}; 66 67 68/// AnalysisDeclContext contains the context data for the function or method 69/// under analysis. 70class AnalysisDeclContext { 71 /// Backpoint to the AnalysisManager object that created this 72 /// AnalysisDeclContext. This may be null. 73 AnalysisDeclContextManager *Manager; 74 75 const Decl * const D; 76 77 OwningPtr<CFG> cfg, completeCFG; 78 OwningPtr<CFGStmtMap> cfgStmtMap; 79 80 CFG::BuildOptions cfgBuildOptions; 81 CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs; 82 83 bool builtCFG, builtCompleteCFG; 84 OwningPtr<ParentMap> PM; 85 OwningPtr<ParentMap> SemanticPM; 86 OwningPtr<PseudoConstantAnalysis> PCA; 87 OwningPtr<CFGReverseBlockReachabilityAnalysis> CFA; 88 89 llvm::BumpPtrAllocator A; 90 91 llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; 92 93 void *ManagedAnalyses; 94 95public: 96 AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 97 const Decl *D); 98 99 AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 100 const Decl *D, 101 const CFG::BuildOptions &BuildOptions); 102 103 ~AnalysisDeclContext(); 104 105 ASTContext &getASTContext() const { return D->getASTContext(); } 106 const Decl *getDecl() const { return D; } 107 108 /// Return the AnalysisDeclContextManager (if any) that created 109 /// this AnalysisDeclContext. 110 AnalysisDeclContextManager *getManager() const { 111 return Manager; 112 } 113 114 /// Return the build options used to construct the CFG. 115 CFG::BuildOptions &getCFGBuildOptions() { 116 return cfgBuildOptions; 117 } 118 119 const CFG::BuildOptions &getCFGBuildOptions() const { 120 return cfgBuildOptions; 121 } 122 123 /// getAddEHEdges - Return true iff we are adding exceptional edges from 124 /// callExprs. If this is false, then try/catch statements and blocks 125 /// reachable from them can appear to be dead in the CFG, analysis passes must 126 /// cope with that. 127 bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; } 128 bool getUseUnoptimizedCFG() const { 129 return !cfgBuildOptions.PruneTriviallyFalseEdges; 130 } 131 bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; } 132 bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; } 133 134 void registerForcedBlockExpression(const Stmt *stmt); 135 const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt); 136 137 /// \brief Get the body of the Declaration. 138 Stmt *getBody() const; 139 140 /// \brief Get the body of the Declaration. 141 /// \param[out] IsAutosynthesized Specifies if the body is auto-generated 142 /// by the BodyFarm. 143 Stmt *getBody(bool &IsAutosynthesized) const; 144 145 /// \brief Checks if the body of the Decl is generated by the BodyFarm. 146 /// 147 /// Note, the lookup is not free. We are going to call getBody behind 148 /// the scenes. 149 /// \sa getBody 150 bool isBodyAutosynthesized() const; 151 152 CFG *getCFG(); 153 154 CFGStmtMap *getCFGStmtMap(); 155 156 CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis(); 157 158 /// Return a version of the CFG without any edges pruned. 159 CFG *getUnoptimizedCFG(); 160 161 void dumpCFG(bool ShowColors); 162 163 /// \brief Returns true if we have built a CFG for this analysis context. 164 /// Note that this doesn't correspond to whether or not a valid CFG exists, it 165 /// corresponds to whether we *attempted* to build one. 166 bool isCFGBuilt() const { return builtCFG; } 167 168 ParentMap &getParentMap(); 169 170 ParentMap &getSemanticParentMap(); 171 172 PseudoConstantAnalysis *getPseudoConstantAnalysis(); 173 174 typedef const VarDecl * const * referenced_decls_iterator; 175 176 std::pair<referenced_decls_iterator, referenced_decls_iterator> 177 getReferencedBlockVars(const BlockDecl *BD); 178 179 /// Return the ImplicitParamDecl* associated with 'self' if this 180 /// AnalysisDeclContext wraps an ObjCMethodDecl. Returns NULL otherwise. 181 const ImplicitParamDecl *getSelfDecl() const; 182 183 const StackFrameContext *getStackFrame(LocationContext const *Parent, 184 const Stmt *S, 185 const CFGBlock *Blk, 186 unsigned Idx); 187 188 const BlockInvocationContext * 189 getBlockInvocationContext(const LocationContext *parent, 190 const BlockDecl *BD, 191 const void *ContextData); 192 193 /// Return the specified analysis object, lazily running the analysis if 194 /// necessary. Return NULL if the analysis could not run. 195 template <typename T> 196 T *getAnalysis() { 197 const void *tag = T::getTag(); 198 ManagedAnalysis *&data = getAnalysisImpl(tag); 199 if (!data) { 200 data = T::create(*this); 201 } 202 return static_cast<T*>(data); 203 } 204private: 205 ManagedAnalysis *&getAnalysisImpl(const void* tag); 206 207 LocationContextManager &getLocationContextManager(); 208}; 209 210class LocationContext : public llvm::FoldingSetNode { 211public: 212 enum ContextKind { StackFrame, Scope, Block }; 213 214private: 215 ContextKind Kind; 216 217 // AnalysisDeclContext can't be const since some methods may modify its 218 // member. 219 AnalysisDeclContext *Ctx; 220 221 const LocationContext *Parent; 222 223protected: 224 LocationContext(ContextKind k, AnalysisDeclContext *ctx, 225 const LocationContext *parent) 226 : Kind(k), Ctx(ctx), Parent(parent) {} 227 228public: 229 virtual ~LocationContext(); 230 231 ContextKind getKind() const { return Kind; } 232 233 AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } 234 235 const LocationContext *getParent() const { return Parent; } 236 237 bool isParentOf(const LocationContext *LC) const; 238 239 const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); } 240 241 CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); } 242 243 template <typename T> 244 T *getAnalysis() const { 245 return getAnalysisDeclContext()->getAnalysis<T>(); 246 } 247 248 ParentMap &getParentMap() const { 249 return getAnalysisDeclContext()->getParentMap(); 250 } 251 252 ParentMap &getSemanticParentMap() const { 253 return getAnalysisDeclContext()->getSemanticParentMap(); 254 } 255 256 const ImplicitParamDecl *getSelfDecl() const { 257 return Ctx->getSelfDecl(); 258 } 259 260 const StackFrameContext *getCurrentStackFrame() const; 261 262 /// Return true if the current LocationContext has no caller context. 263 virtual bool inTopFrame() const; 264 265 virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; 266 267 LLVM_ATTRIBUTE_USED void dumpStack() const; 268 269public: 270 static void ProfileCommon(llvm::FoldingSetNodeID &ID, 271 ContextKind ck, 272 AnalysisDeclContext *ctx, 273 const LocationContext *parent, 274 const void *data); 275}; 276 277class StackFrameContext : public LocationContext { 278 // The callsite where this stack frame is established. 279 const Stmt *CallSite; 280 281 // The parent block of the callsite. 282 const CFGBlock *Block; 283 284 // The index of the callsite in the CFGBlock. 285 unsigned Index; 286 287 friend class LocationContextManager; 288 StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, 289 const Stmt *s, const CFGBlock *blk, 290 unsigned idx) 291 : LocationContext(StackFrame, ctx, parent), CallSite(s), 292 Block(blk), Index(idx) {} 293 294public: 295 ~StackFrameContext() {} 296 297 const Stmt *getCallSite() const { return CallSite; } 298 299 const CFGBlock *getCallSiteBlock() const { return Block; } 300 301 /// Return true if the current LocationContext has no caller context. 302 virtual bool inTopFrame() const { return getParent() == 0; } 303 304 unsigned getIndex() const { return Index; } 305 306 void Profile(llvm::FoldingSetNodeID &ID); 307 308 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 309 const LocationContext *parent, const Stmt *s, 310 const CFGBlock *blk, unsigned idx) { 311 ProfileCommon(ID, StackFrame, ctx, parent, s); 312 ID.AddPointer(blk); 313 ID.AddInteger(idx); 314 } 315 316 static bool classof(const LocationContext *Ctx) { 317 return Ctx->getKind() == StackFrame; 318 } 319}; 320 321class ScopeContext : public LocationContext { 322 const Stmt *Enter; 323 324 friend class LocationContextManager; 325 ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, 326 const Stmt *s) 327 : LocationContext(Scope, ctx, parent), Enter(s) {} 328 329public: 330 ~ScopeContext() {} 331 332 void Profile(llvm::FoldingSetNodeID &ID); 333 334 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 335 const LocationContext *parent, const Stmt *s) { 336 ProfileCommon(ID, Scope, ctx, parent, s); 337 } 338 339 static bool classof(const LocationContext *Ctx) { 340 return Ctx->getKind() == Scope; 341 } 342}; 343 344class BlockInvocationContext : public LocationContext { 345 const BlockDecl *BD; 346 347 // FIXME: Come up with a more type-safe way to model context-sensitivity. 348 const void *ContextData; 349 350 friend class LocationContextManager; 351 352 BlockInvocationContext(AnalysisDeclContext *ctx, 353 const LocationContext *parent, 354 const BlockDecl *bd, const void *contextData) 355 : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} 356 357public: 358 ~BlockInvocationContext() {} 359 360 const BlockDecl *getBlockDecl() const { return BD; } 361 362 const void *getContextData() const { return ContextData; } 363 364 void Profile(llvm::FoldingSetNodeID &ID); 365 366 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 367 const LocationContext *parent, const BlockDecl *bd, 368 const void *contextData) { 369 ProfileCommon(ID, Block, ctx, parent, bd); 370 ID.AddPointer(contextData); 371 } 372 373 static bool classof(const LocationContext *Ctx) { 374 return Ctx->getKind() == Block; 375 } 376}; 377 378class LocationContextManager { 379 llvm::FoldingSet<LocationContext> Contexts; 380public: 381 ~LocationContextManager(); 382 383 const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, 384 const LocationContext *parent, 385 const Stmt *s, 386 const CFGBlock *blk, unsigned idx); 387 388 const ScopeContext *getScope(AnalysisDeclContext *ctx, 389 const LocationContext *parent, 390 const Stmt *s); 391 392 const BlockInvocationContext * 393 getBlockInvocationContext(AnalysisDeclContext *ctx, 394 const LocationContext *parent, 395 const BlockDecl *BD, 396 const void *ContextData); 397 398 /// Discard all previously created LocationContext objects. 399 void clear(); 400private: 401 template <typename LOC, typename DATA> 402 const LOC *getLocationContext(AnalysisDeclContext *ctx, 403 const LocationContext *parent, 404 const DATA *d); 405}; 406 407class AnalysisDeclContextManager { 408 typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap; 409 410 ContextMap Contexts; 411 LocationContextManager LocContexts; 412 CFG::BuildOptions cfgBuildOptions; 413 414 /// Flag to indicate whether or not bodies should be synthesized 415 /// for well-known functions. 416 bool SynthesizeBodies; 417 418public: 419 AnalysisDeclContextManager(bool useUnoptimizedCFG = false, 420 bool addImplicitDtors = false, 421 bool addInitializers = false, 422 bool addTemporaryDtors = false, 423 bool synthesizeBodies = false, 424 bool addStaticInitBranches = false); 425 426 ~AnalysisDeclContextManager(); 427 428 AnalysisDeclContext *getContext(const Decl *D); 429 430 bool getUseUnoptimizedCFG() const { 431 return !cfgBuildOptions.PruneTriviallyFalseEdges; 432 } 433 434 CFG::BuildOptions &getCFGBuildOptions() { 435 return cfgBuildOptions; 436 } 437 438 /// Return true if faux bodies should be synthesized for well-known 439 /// functions. 440 bool synthesizeBodies() const { return SynthesizeBodies; } 441 442 const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, 443 LocationContext const *Parent, 444 const Stmt *S, 445 const CFGBlock *Blk, 446 unsigned Idx) { 447 return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); 448 } 449 450 // Get the top level stack frame. 451 const StackFrameContext *getStackFrame(const Decl *D) { 452 return LocContexts.getStackFrame(getContext(D), 0, 0, 0, 0); 453 } 454 455 // Get a stack frame with parent. 456 StackFrameContext const *getStackFrame(const Decl *D, 457 LocationContext const *Parent, 458 const Stmt *S, 459 const CFGBlock *Blk, 460 unsigned Idx) { 461 return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); 462 } 463 464 /// Discard all previously created AnalysisDeclContexts. 465 void clear(); 466 467private: 468 friend class AnalysisDeclContext; 469 470 LocationContextManager &getLocationContextManager() { 471 return LocContexts; 472 } 473}; 474 475} // end clang namespace 476#endif 477