1203955Srdivacky//=== AnalysisContext.h - Analysis context for Path Sens analysis --*- C++ -*-// 2203955Srdivacky// 3203955Srdivacky// The LLVM Compiler Infrastructure 4203955Srdivacky// 5203955Srdivacky// This file is distributed under the University of Illinois Open Source 6203955Srdivacky// License. See LICENSE.TXT for details. 7203955Srdivacky// 8203955Srdivacky//===----------------------------------------------------------------------===// 9203955Srdivacky// 10235633Sdim// This file defines AnalysisDeclContext, a class that manages the analysis 11235633Sdim// context data for path sensitive analysis. 12203955Srdivacky// 13203955Srdivacky//===----------------------------------------------------------------------===// 14203955Srdivacky 15203955Srdivacky#ifndef LLVM_CLANG_ANALYSIS_ANALYSISCONTEXT_H 16203955Srdivacky#define LLVM_CLANG_ANALYSIS_ANALYSISCONTEXT_H 17203955Srdivacky 18203955Srdivacky#include "clang/AST/Decl.h" 19221345Sdim#include "clang/Analysis/CFG.h" 20252723Sdim#include "llvm/ADT/DenseMap.h" 21252723Sdim#include "llvm/ADT/FoldingSet.h" 22203955Srdivacky#include "llvm/ADT/OwningPtr.h" 23203955Srdivacky#include "llvm/Support/Allocator.h" 24203955Srdivacky 25203955Srdivackynamespace clang { 26203955Srdivacky 27203955Srdivackyclass Stmt; 28221345Sdimclass CFGReverseBlockReachabilityAnalysis; 29219077Sdimclass CFGStmtMap; 30203955Srdivackyclass LiveVariables; 31226890Sdimclass ManagedAnalysis; 32203955Srdivackyclass ParentMap; 33212904Sdimclass PseudoConstantAnalysis; 34203955Srdivackyclass LocationContextManager; 35203955Srdivackyclass StackFrameContext; 36245431Sdimclass BlockInvocationContext; 37235633Sdimclass AnalysisDeclContextManager; 38235633Sdimclass LocationContext; 39235633Sdim 40212904Sdimnamespace idx { class TranslationUnit; } 41212904Sdim 42226890Sdim/// The base class of a hierarchy of objects representing analyses tied 43235633Sdim/// to AnalysisDeclContext. 44226890Sdimclass ManagedAnalysis { 45226890Sdimprotected: 46226890Sdim ManagedAnalysis() {} 47226890Sdimpublic: 48226890Sdim virtual ~ManagedAnalysis(); 49235633Sdim 50226890Sdim // Subclasses need to implement: 51226890Sdim // 52226890Sdim // static const void *getTag(); 53226890Sdim // 54226890Sdim // Which returns a fixed pointer address to distinguish classes of 55226890Sdim // analysis objects. They also need to implement: 56226890Sdim // 57235633Sdim // static [Derived*] create(AnalysisDeclContext &Ctx); 58226890Sdim // 59235633Sdim // which creates the analysis object given an AnalysisDeclContext. 60226890Sdim}; 61235633Sdim 62235633Sdim 63235633Sdim/// AnalysisDeclContext contains the context data for the function or method 64235633Sdim/// under analysis. 65235633Sdimclass AnalysisDeclContext { 66235633Sdim /// Backpoint to the AnalysisManager object that created this 67235633Sdim /// AnalysisDeclContext. This may be null. 68235633Sdim AnalysisDeclContextManager *Manager; 69235633Sdim 70245431Sdim const Decl * const D; 71203955Srdivacky 72235633Sdim OwningPtr<CFG> cfg, completeCFG; 73235633Sdim OwningPtr<CFGStmtMap> cfgStmtMap; 74221345Sdim 75221345Sdim CFG::BuildOptions cfgBuildOptions; 76221345Sdim CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs; 77235633Sdim 78212904Sdim bool builtCFG, builtCompleteCFG; 79235633Sdim OwningPtr<ParentMap> PM; 80235633Sdim OwningPtr<PseudoConstantAnalysis> PCA; 81235633Sdim OwningPtr<CFGReverseBlockReachabilityAnalysis> CFA; 82221345Sdim 83221345Sdim llvm::BumpPtrAllocator A; 84221345Sdim 85203955Srdivacky llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; 86221345Sdim 87226890Sdim void *ManagedAnalyses; 88226890Sdim 89203955Srdivackypublic: 90235633Sdim AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 91245431Sdim const Decl *D); 92226890Sdim 93235633Sdim AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 94235633Sdim const Decl *D, 95235633Sdim const CFG::BuildOptions &BuildOptions); 96203955Srdivacky 97235633Sdim ~AnalysisDeclContext(); 98203955Srdivacky 99245431Sdim ASTContext &getASTContext() const { return D->getASTContext(); } 100212904Sdim const Decl *getDecl() const { return D; } 101212904Sdim 102245431Sdim /// Return the AnalysisDeclContextManager (if any) that created 103245431Sdim /// this AnalysisDeclContext. 104245431Sdim AnalysisDeclContextManager *getManager() const { 105245431Sdim return Manager; 106245431Sdim } 107245431Sdim 108226890Sdim /// Return the build options used to construct the CFG. 109226890Sdim CFG::BuildOptions &getCFGBuildOptions() { 110226890Sdim return cfgBuildOptions; 111226890Sdim } 112226890Sdim 113226890Sdim const CFG::BuildOptions &getCFGBuildOptions() const { 114226890Sdim return cfgBuildOptions; 115226890Sdim } 116235633Sdim 117203955Srdivacky /// getAddEHEdges - Return true iff we are adding exceptional edges from 118203955Srdivacky /// callExprs. If this is false, then try/catch statements and blocks 119203955Srdivacky /// reachable from them can appear to be dead in the CFG, analysis passes must 120203955Srdivacky /// cope with that. 121235633Sdim bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; } 122221345Sdim bool getUseUnoptimizedCFG() const { 123226890Sdim return !cfgBuildOptions.PruneTriviallyFalseEdges; 124221345Sdim } 125221345Sdim bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; } 126221345Sdim bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; } 127221345Sdim 128221345Sdim void registerForcedBlockExpression(const Stmt *stmt); 129221345Sdim const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt); 130235633Sdim 131252723Sdim /// \brief Get the body of the Declaration. 132226890Sdim Stmt *getBody() const; 133252723Sdim 134252723Sdim /// \brief Get the body of the Declaration. 135252723Sdim /// \param[out] IsAutosynthesized Specifies if the body is auto-generated 136252723Sdim /// by the BodyFarm. 137252723Sdim Stmt *getBody(bool &IsAutosynthesized) const; 138252723Sdim 139252723Sdim /// \brief Checks if the body of the Decl is generated by the BodyFarm. 140252723Sdim /// 141252723Sdim /// Note, the lookup is not free. We are going to call getBody behind 142252723Sdim /// the scenes. 143252723Sdim /// \sa getBody 144252723Sdim bool isBodyAutosynthesized() const; 145252723Sdim 146203955Srdivacky CFG *getCFG(); 147235633Sdim 148219077Sdim CFGStmtMap *getCFGStmtMap(); 149218893Sdim 150221345Sdim CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis(); 151235633Sdim 152212904Sdim /// Return a version of the CFG without any edges pruned. 153212904Sdim CFG *getUnoptimizedCFG(); 154212904Sdim 155235633Sdim void dumpCFG(bool ShowColors); 156218893Sdim 157224145Sdim /// \brief Returns true if we have built a CFG for this analysis context. 158224145Sdim /// Note that this doesn't correspond to whether or not a valid CFG exists, it 159224145Sdim /// corresponds to whether we *attempted* to build one. 160224145Sdim bool isCFGBuilt() const { return builtCFG; } 161224145Sdim 162203955Srdivacky ParentMap &getParentMap(); 163212904Sdim PseudoConstantAnalysis *getPseudoConstantAnalysis(); 164203955Srdivacky 165203955Srdivacky typedef const VarDecl * const * referenced_decls_iterator; 166203955Srdivacky 167203955Srdivacky std::pair<referenced_decls_iterator, referenced_decls_iterator> 168203955Srdivacky getReferencedBlockVars(const BlockDecl *BD); 169206084Srdivacky 170203955Srdivacky /// Return the ImplicitParamDecl* associated with 'self' if this 171235633Sdim /// AnalysisDeclContext wraps an ObjCMethodDecl. Returns NULL otherwise. 172203955Srdivacky const ImplicitParamDecl *getSelfDecl() const; 173235633Sdim 174235633Sdim const StackFrameContext *getStackFrame(LocationContext const *Parent, 175235633Sdim const Stmt *S, 176235633Sdim const CFGBlock *Blk, 177235633Sdim unsigned Idx); 178245431Sdim 179245431Sdim const BlockInvocationContext * 180245431Sdim getBlockInvocationContext(const LocationContext *parent, 181245431Sdim const BlockDecl *BD, 182245431Sdim const void *ContextData); 183235633Sdim 184226890Sdim /// Return the specified analysis object, lazily running the analysis if 185226890Sdim /// necessary. Return NULL if the analysis could not run. 186226890Sdim template <typename T> 187226890Sdim T *getAnalysis() { 188226890Sdim const void *tag = T::getTag(); 189226890Sdim ManagedAnalysis *&data = getAnalysisImpl(tag); 190226890Sdim if (!data) { 191226890Sdim data = T::create(*this); 192226890Sdim } 193226890Sdim return static_cast<T*>(data); 194226890Sdim } 195226890Sdimprivate: 196226890Sdim ManagedAnalysis *&getAnalysisImpl(const void* tag); 197203955Srdivacky 198235633Sdim LocationContextManager &getLocationContextManager(); 199203955Srdivacky}; 200203955Srdivacky 201203955Srdivackyclass LocationContext : public llvm::FoldingSetNode { 202203955Srdivackypublic: 203203955Srdivacky enum ContextKind { StackFrame, Scope, Block }; 204203955Srdivacky 205203955Srdivackyprivate: 206203955Srdivacky ContextKind Kind; 207212904Sdim 208235633Sdim // AnalysisDeclContext can't be const since some methods may modify its 209235633Sdim // member. 210235633Sdim AnalysisDeclContext *Ctx; 211212904Sdim 212203955Srdivacky const LocationContext *Parent; 213203955Srdivacky 214203955Srdivackyprotected: 215235633Sdim LocationContext(ContextKind k, AnalysisDeclContext *ctx, 216203955Srdivacky const LocationContext *parent) 217203955Srdivacky : Kind(k), Ctx(ctx), Parent(parent) {} 218203955Srdivacky 219203955Srdivackypublic: 220203955Srdivacky virtual ~LocationContext(); 221206084Srdivacky 222203955Srdivacky ContextKind getKind() const { return Kind; } 223203955Srdivacky 224235633Sdim AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } 225203955Srdivacky 226203955Srdivacky const LocationContext *getParent() const { return Parent; } 227203955Srdivacky 228204643Srdivacky bool isParentOf(const LocationContext *LC) const; 229204643Srdivacky 230235633Sdim const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); } 231203955Srdivacky 232235633Sdim CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); } 233203955Srdivacky 234226890Sdim template <typename T> 235226890Sdim T *getAnalysis() const { 236235633Sdim return getAnalysisDeclContext()->getAnalysis<T>(); 237203955Srdivacky } 238203955Srdivacky 239206084Srdivacky ParentMap &getParentMap() const { 240235633Sdim return getAnalysisDeclContext()->getParentMap(); 241203955Srdivacky } 242203955Srdivacky 243203955Srdivacky const ImplicitParamDecl *getSelfDecl() const { 244203955Srdivacky return Ctx->getSelfDecl(); 245203955Srdivacky } 246206084Srdivacky 247203955Srdivacky const StackFrameContext *getCurrentStackFrame() const; 248203955Srdivacky 249245431Sdim /// Return true if the current LocationContext has no caller context. 250245431Sdim virtual bool inTopFrame() const; 251245431Sdim 252203955Srdivacky virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; 253203955Srdivacky 254263509Sdim void dumpStack(raw_ostream &OS, StringRef Indent = "") const; 255252723Sdim LLVM_ATTRIBUTE_USED void dumpStack() const; 256252723Sdim 257203955Srdivackypublic: 258203955Srdivacky static void ProfileCommon(llvm::FoldingSetNodeID &ID, 259203955Srdivacky ContextKind ck, 260235633Sdim AnalysisDeclContext *ctx, 261203955Srdivacky const LocationContext *parent, 262226890Sdim const void *data); 263203955Srdivacky}; 264203955Srdivacky 265203955Srdivackyclass StackFrameContext : public LocationContext { 266203955Srdivacky // The callsite where this stack frame is established. 267203955Srdivacky const Stmt *CallSite; 268203955Srdivacky 269203955Srdivacky // The parent block of the callsite. 270203955Srdivacky const CFGBlock *Block; 271203955Srdivacky 272203955Srdivacky // The index of the callsite in the CFGBlock. 273203955Srdivacky unsigned Index; 274203955Srdivacky 275203955Srdivacky friend class LocationContextManager; 276235633Sdim StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, 277235633Sdim const Stmt *s, const CFGBlock *blk, 278218893Sdim unsigned idx) 279218893Sdim : LocationContext(StackFrame, ctx, parent), CallSite(s), 280218893Sdim Block(blk), Index(idx) {} 281203955Srdivacky 282203955Srdivackypublic: 283203955Srdivacky ~StackFrameContext() {} 284203955Srdivacky 285203955Srdivacky const Stmt *getCallSite() const { return CallSite; } 286203955Srdivacky 287203955Srdivacky const CFGBlock *getCallSiteBlock() const { return Block; } 288203955Srdivacky 289245431Sdim /// Return true if the current LocationContext has no caller context. 290245431Sdim virtual bool inTopFrame() const { return getParent() == 0; } 291245431Sdim 292203955Srdivacky unsigned getIndex() const { return Index; } 293203955Srdivacky 294203955Srdivacky void Profile(llvm::FoldingSetNodeID &ID); 295206084Srdivacky 296235633Sdim static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 297206084Srdivacky const LocationContext *parent, const Stmt *s, 298203955Srdivacky const CFGBlock *blk, unsigned idx) { 299203955Srdivacky ProfileCommon(ID, StackFrame, ctx, parent, s); 300203955Srdivacky ID.AddPointer(blk); 301203955Srdivacky ID.AddInteger(idx); 302203955Srdivacky } 303203955Srdivacky 304226890Sdim static bool classof(const LocationContext *Ctx) { 305203955Srdivacky return Ctx->getKind() == StackFrame; 306203955Srdivacky } 307203955Srdivacky}; 308203955Srdivacky 309203955Srdivackyclass ScopeContext : public LocationContext { 310203955Srdivacky const Stmt *Enter; 311206084Srdivacky 312203955Srdivacky friend class LocationContextManager; 313235633Sdim ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, 314203955Srdivacky const Stmt *s) 315203955Srdivacky : LocationContext(Scope, ctx, parent), Enter(s) {} 316203955Srdivacky 317203955Srdivackypublic: 318203955Srdivacky ~ScopeContext() {} 319203955Srdivacky 320203955Srdivacky void Profile(llvm::FoldingSetNodeID &ID); 321203955Srdivacky 322235633Sdim static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 323203955Srdivacky const LocationContext *parent, const Stmt *s) { 324203955Srdivacky ProfileCommon(ID, Scope, ctx, parent, s); 325203955Srdivacky } 326203955Srdivacky 327226890Sdim static bool classof(const LocationContext *Ctx) { 328203955Srdivacky return Ctx->getKind() == Scope; 329203955Srdivacky } 330203955Srdivacky}; 331203955Srdivacky 332203955Srdivackyclass BlockInvocationContext : public LocationContext { 333203955Srdivacky const BlockDecl *BD; 334245431Sdim 335245431Sdim // FIXME: Come up with a more type-safe way to model context-sensitivity. 336245431Sdim const void *ContextData; 337203955Srdivacky 338203955Srdivacky friend class LocationContextManager; 339203955Srdivacky 340235633Sdim BlockInvocationContext(AnalysisDeclContext *ctx, 341235633Sdim const LocationContext *parent, 342245431Sdim const BlockDecl *bd, const void *contextData) 343245431Sdim : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} 344203955Srdivacky 345203955Srdivackypublic: 346203955Srdivacky ~BlockInvocationContext() {} 347203955Srdivacky 348203955Srdivacky const BlockDecl *getBlockDecl() const { return BD; } 349245431Sdim 350245431Sdim const void *getContextData() const { return ContextData; } 351203955Srdivacky 352203955Srdivacky void Profile(llvm::FoldingSetNodeID &ID); 353203955Srdivacky 354235633Sdim static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 355245431Sdim const LocationContext *parent, const BlockDecl *bd, 356245431Sdim const void *contextData) { 357203955Srdivacky ProfileCommon(ID, Block, ctx, parent, bd); 358245431Sdim ID.AddPointer(contextData); 359203955Srdivacky } 360206084Srdivacky 361226890Sdim static bool classof(const LocationContext *Ctx) { 362203955Srdivacky return Ctx->getKind() == Block; 363203955Srdivacky } 364203955Srdivacky}; 365203955Srdivacky 366203955Srdivackyclass LocationContextManager { 367203955Srdivacky llvm::FoldingSet<LocationContext> Contexts; 368203955Srdivackypublic: 369203955Srdivacky ~LocationContextManager(); 370206084Srdivacky 371235633Sdim const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, 372203955Srdivacky const LocationContext *parent, 373218893Sdim const Stmt *s, 374218893Sdim const CFGBlock *blk, unsigned idx); 375203955Srdivacky 376235633Sdim const ScopeContext *getScope(AnalysisDeclContext *ctx, 377203955Srdivacky const LocationContext *parent, 378203955Srdivacky const Stmt *s); 379245431Sdim 380245431Sdim const BlockInvocationContext * 381245431Sdim getBlockInvocationContext(AnalysisDeclContext *ctx, 382245431Sdim const LocationContext *parent, 383245431Sdim const BlockDecl *BD, 384245431Sdim const void *ContextData); 385206084Srdivacky 386203955Srdivacky /// Discard all previously created LocationContext objects. 387203955Srdivacky void clear(); 388203955Srdivackyprivate: 389203955Srdivacky template <typename LOC, typename DATA> 390235633Sdim const LOC *getLocationContext(AnalysisDeclContext *ctx, 391203955Srdivacky const LocationContext *parent, 392203955Srdivacky const DATA *d); 393203955Srdivacky}; 394203955Srdivacky 395235633Sdimclass AnalysisDeclContextManager { 396235633Sdim typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap; 397235633Sdim 398235633Sdim ContextMap Contexts; 399235633Sdim LocationContextManager LocContexts; 400235633Sdim CFG::BuildOptions cfgBuildOptions; 401245431Sdim 402245431Sdim /// Flag to indicate whether or not bodies should be synthesized 403245431Sdim /// for well-known functions. 404245431Sdim bool SynthesizeBodies; 405235633Sdim 406235633Sdimpublic: 407235633Sdim AnalysisDeclContextManager(bool useUnoptimizedCFG = false, 408245431Sdim bool addImplicitDtors = false, 409245431Sdim bool addInitializers = false, 410245431Sdim bool addTemporaryDtors = false, 411252723Sdim bool synthesizeBodies = false, 412252723Sdim bool addStaticInitBranches = false); 413235633Sdim 414235633Sdim ~AnalysisDeclContextManager(); 415235633Sdim 416245431Sdim AnalysisDeclContext *getContext(const Decl *D); 417235633Sdim 418235633Sdim bool getUseUnoptimizedCFG() const { 419235633Sdim return !cfgBuildOptions.PruneTriviallyFalseEdges; 420235633Sdim } 421235633Sdim 422235633Sdim CFG::BuildOptions &getCFGBuildOptions() { 423235633Sdim return cfgBuildOptions; 424235633Sdim } 425245431Sdim 426245431Sdim /// Return true if faux bodies should be synthesized for well-known 427245431Sdim /// functions. 428245431Sdim bool synthesizeBodies() const { return SynthesizeBodies; } 429235633Sdim 430235633Sdim const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, 431235633Sdim LocationContext const *Parent, 432235633Sdim const Stmt *S, 433235633Sdim const CFGBlock *Blk, 434235633Sdim unsigned Idx) { 435235633Sdim return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); 436235633Sdim } 437235633Sdim 438235633Sdim // Get the top level stack frame. 439245431Sdim const StackFrameContext *getStackFrame(const Decl *D) { 440245431Sdim return LocContexts.getStackFrame(getContext(D), 0, 0, 0, 0); 441235633Sdim } 442235633Sdim 443235633Sdim // Get a stack frame with parent. 444235633Sdim StackFrameContext const *getStackFrame(const Decl *D, 445235633Sdim LocationContext const *Parent, 446235633Sdim const Stmt *S, 447235633Sdim const CFGBlock *Blk, 448235633Sdim unsigned Idx) { 449235633Sdim return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); 450235633Sdim } 451235633Sdim 452235633Sdim /// Discard all previously created AnalysisDeclContexts. 453235633Sdim void clear(); 454235633Sdim 455235633Sdimprivate: 456235633Sdim friend class AnalysisDeclContext; 457235633Sdim 458235633Sdim LocationContextManager &getLocationContextManager() { 459235633Sdim return LocContexts; 460235633Sdim } 461235633Sdim}; 462235633Sdim 463203955Srdivacky} // end clang namespace 464203955Srdivacky#endif 465