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// 10234353Sdim// This file defines AnalysisDeclContext, a class that manages the analysis 11234353Sdim// 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" 20249423Sdim#include "llvm/ADT/DenseMap.h" 21249423Sdim#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; 31226633Sdimclass ManagedAnalysis; 32203955Srdivackyclass ParentMap; 33212904Sdimclass PseudoConstantAnalysis; 34203955Srdivackyclass LocationContextManager; 35203955Srdivackyclass StackFrameContext; 36239462Sdimclass BlockInvocationContext; 37234353Sdimclass AnalysisDeclContextManager; 38234353Sdimclass LocationContext; 39234353Sdim 40212904Sdimnamespace idx { class TranslationUnit; } 41212904Sdim 42226633Sdim/// The base class of a hierarchy of objects representing analyses tied 43234353Sdim/// to AnalysisDeclContext. 44226633Sdimclass ManagedAnalysis { 45226633Sdimprotected: 46226633Sdim ManagedAnalysis() {} 47226633Sdimpublic: 48226633Sdim virtual ~ManagedAnalysis(); 49234353Sdim 50226633Sdim // Subclasses need to implement: 51226633Sdim // 52226633Sdim // static const void *getTag(); 53226633Sdim // 54226633Sdim // Which returns a fixed pointer address to distinguish classes of 55226633Sdim // analysis objects. They also need to implement: 56226633Sdim // 57234353Sdim // static [Derived*] create(AnalysisDeclContext &Ctx); 58226633Sdim // 59234353Sdim // which creates the analysis object given an AnalysisDeclContext. 60226633Sdim}; 61234353Sdim 62234353Sdim 63234353Sdim/// AnalysisDeclContext contains the context data for the function or method 64234353Sdim/// under analysis. 65234353Sdimclass AnalysisDeclContext { 66234353Sdim /// Backpoint to the AnalysisManager object that created this 67234353Sdim /// AnalysisDeclContext. This may be null. 68234353Sdim AnalysisDeclContextManager *Manager; 69234353Sdim 70243830Sdim const Decl * const D; 71203955Srdivacky 72234353Sdim OwningPtr<CFG> cfg, completeCFG; 73234353Sdim OwningPtr<CFGStmtMap> cfgStmtMap; 74221345Sdim 75221345Sdim CFG::BuildOptions cfgBuildOptions; 76221345Sdim CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs; 77234353Sdim 78212904Sdim bool builtCFG, builtCompleteCFG; 79234353Sdim OwningPtr<ParentMap> PM; 80234353Sdim OwningPtr<PseudoConstantAnalysis> PCA; 81234353Sdim OwningPtr<CFGReverseBlockReachabilityAnalysis> CFA; 82221345Sdim 83221345Sdim llvm::BumpPtrAllocator A; 84221345Sdim 85203955Srdivacky llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; 86221345Sdim 87226633Sdim void *ManagedAnalyses; 88226633Sdim 89203955Srdivackypublic: 90234353Sdim AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 91239462Sdim const Decl *D); 92226633Sdim 93234353Sdim AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 94234353Sdim const Decl *D, 95234353Sdim const CFG::BuildOptions &BuildOptions); 96203955Srdivacky 97234353Sdim ~AnalysisDeclContext(); 98203955Srdivacky 99243830Sdim ASTContext &getASTContext() const { return D->getASTContext(); } 100212904Sdim const Decl *getDecl() const { return D; } 101212904Sdim 102243830Sdim /// Return the AnalysisDeclContextManager (if any) that created 103243830Sdim /// this AnalysisDeclContext. 104243830Sdim AnalysisDeclContextManager *getManager() const { 105243830Sdim return Manager; 106243830Sdim } 107243830Sdim 108226633Sdim /// Return the build options used to construct the CFG. 109226633Sdim CFG::BuildOptions &getCFGBuildOptions() { 110226633Sdim return cfgBuildOptions; 111226633Sdim } 112226633Sdim 113226633Sdim const CFG::BuildOptions &getCFGBuildOptions() const { 114226633Sdim return cfgBuildOptions; 115226633Sdim } 116234353Sdim 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. 121234353Sdim bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; } 122221345Sdim bool getUseUnoptimizedCFG() const { 123226633Sdim 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); 130234353Sdim 131249423Sdim /// \brief Get the body of the Declaration. 132226633Sdim Stmt *getBody() const; 133249423Sdim 134249423Sdim /// \brief Get the body of the Declaration. 135249423Sdim /// \param[out] IsAutosynthesized Specifies if the body is auto-generated 136249423Sdim /// by the BodyFarm. 137249423Sdim Stmt *getBody(bool &IsAutosynthesized) const; 138249423Sdim 139249423Sdim /// \brief Checks if the body of the Decl is generated by the BodyFarm. 140249423Sdim /// 141249423Sdim /// Note, the lookup is not free. We are going to call getBody behind 142249423Sdim /// the scenes. 143249423Sdim /// \sa getBody 144249423Sdim bool isBodyAutosynthesized() const; 145249423Sdim 146203955Srdivacky CFG *getCFG(); 147234353Sdim 148219077Sdim CFGStmtMap *getCFGStmtMap(); 149218893Sdim 150221345Sdim CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis(); 151234353Sdim 152212904Sdim /// Return a version of the CFG without any edges pruned. 153212904Sdim CFG *getUnoptimizedCFG(); 154212904Sdim 155234353Sdim 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 171234353Sdim /// AnalysisDeclContext wraps an ObjCMethodDecl. Returns NULL otherwise. 172203955Srdivacky const ImplicitParamDecl *getSelfDecl() const; 173234353Sdim 174234353Sdim const StackFrameContext *getStackFrame(LocationContext const *Parent, 175234353Sdim const Stmt *S, 176234353Sdim const CFGBlock *Blk, 177234353Sdim unsigned Idx); 178239462Sdim 179239462Sdim const BlockInvocationContext * 180239462Sdim getBlockInvocationContext(const LocationContext *parent, 181239462Sdim const BlockDecl *BD, 182239462Sdim const void *ContextData); 183234353Sdim 184226633Sdim /// Return the specified analysis object, lazily running the analysis if 185226633Sdim /// necessary. Return NULL if the analysis could not run. 186226633Sdim template <typename T> 187226633Sdim T *getAnalysis() { 188226633Sdim const void *tag = T::getTag(); 189226633Sdim ManagedAnalysis *&data = getAnalysisImpl(tag); 190226633Sdim if (!data) { 191226633Sdim data = T::create(*this); 192226633Sdim } 193226633Sdim return static_cast<T*>(data); 194226633Sdim } 195226633Sdimprivate: 196226633Sdim ManagedAnalysis *&getAnalysisImpl(const void* tag); 197203955Srdivacky 198234353Sdim LocationContextManager &getLocationContextManager(); 199203955Srdivacky}; 200203955Srdivacky 201203955Srdivackyclass LocationContext : public llvm::FoldingSetNode { 202203955Srdivackypublic: 203203955Srdivacky enum ContextKind { StackFrame, Scope, Block }; 204203955Srdivacky 205203955Srdivackyprivate: 206203955Srdivacky ContextKind Kind; 207212904Sdim 208234353Sdim // AnalysisDeclContext can't be const since some methods may modify its 209234353Sdim // member. 210234353Sdim AnalysisDeclContext *Ctx; 211212904Sdim 212203955Srdivacky const LocationContext *Parent; 213203955Srdivacky 214203955Srdivackyprotected: 215234353Sdim 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 224234353Sdim AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } 225203955Srdivacky 226203955Srdivacky const LocationContext *getParent() const { return Parent; } 227203955Srdivacky 228204643Srdivacky bool isParentOf(const LocationContext *LC) const; 229204643Srdivacky 230234353Sdim const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); } 231203955Srdivacky 232234353Sdim CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); } 233203955Srdivacky 234226633Sdim template <typename T> 235226633Sdim T *getAnalysis() const { 236234353Sdim return getAnalysisDeclContext()->getAnalysis<T>(); 237203955Srdivacky } 238203955Srdivacky 239206084Srdivacky ParentMap &getParentMap() const { 240234353Sdim return getAnalysisDeclContext()->getParentMap(); 241203955Srdivacky } 242203955Srdivacky 243203955Srdivacky const ImplicitParamDecl *getSelfDecl() const { 244203955Srdivacky return Ctx->getSelfDecl(); 245203955Srdivacky } 246206084Srdivacky 247203955Srdivacky const StackFrameContext *getCurrentStackFrame() const; 248203955Srdivacky 249243830Sdim /// Return true if the current LocationContext has no caller context. 250243830Sdim virtual bool inTopFrame() const; 251243830Sdim 252203955Srdivacky virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; 253203955Srdivacky 254263508Sdim void dumpStack(raw_ostream &OS, StringRef Indent = "") const; 255249423Sdim LLVM_ATTRIBUTE_USED void dumpStack() const; 256249423Sdim 257203955Srdivackypublic: 258203955Srdivacky static void ProfileCommon(llvm::FoldingSetNodeID &ID, 259203955Srdivacky ContextKind ck, 260234353Sdim AnalysisDeclContext *ctx, 261203955Srdivacky const LocationContext *parent, 262226633Sdim 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; 276234353Sdim StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, 277234353Sdim 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 289243830Sdim /// Return true if the current LocationContext has no caller context. 290243830Sdim virtual bool inTopFrame() const { return getParent() == 0; } 291243830Sdim 292203955Srdivacky unsigned getIndex() const { return Index; } 293203955Srdivacky 294203955Srdivacky void Profile(llvm::FoldingSetNodeID &ID); 295206084Srdivacky 296234353Sdim 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 304226633Sdim 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; 313234353Sdim 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 322234353Sdim static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 323203955Srdivacky const LocationContext *parent, const Stmt *s) { 324203955Srdivacky ProfileCommon(ID, Scope, ctx, parent, s); 325203955Srdivacky } 326203955Srdivacky 327226633Sdim static bool classof(const LocationContext *Ctx) { 328203955Srdivacky return Ctx->getKind() == Scope; 329203955Srdivacky } 330203955Srdivacky}; 331203955Srdivacky 332203955Srdivackyclass BlockInvocationContext : public LocationContext { 333203955Srdivacky const BlockDecl *BD; 334239462Sdim 335239462Sdim // FIXME: Come up with a more type-safe way to model context-sensitivity. 336239462Sdim const void *ContextData; 337203955Srdivacky 338203955Srdivacky friend class LocationContextManager; 339203955Srdivacky 340234353Sdim BlockInvocationContext(AnalysisDeclContext *ctx, 341234353Sdim const LocationContext *parent, 342239462Sdim const BlockDecl *bd, const void *contextData) 343239462Sdim : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} 344203955Srdivacky 345203955Srdivackypublic: 346203955Srdivacky ~BlockInvocationContext() {} 347203955Srdivacky 348203955Srdivacky const BlockDecl *getBlockDecl() const { return BD; } 349239462Sdim 350239462Sdim const void *getContextData() const { return ContextData; } 351203955Srdivacky 352203955Srdivacky void Profile(llvm::FoldingSetNodeID &ID); 353203955Srdivacky 354234353Sdim static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 355239462Sdim const LocationContext *parent, const BlockDecl *bd, 356239462Sdim const void *contextData) { 357203955Srdivacky ProfileCommon(ID, Block, ctx, parent, bd); 358239462Sdim ID.AddPointer(contextData); 359203955Srdivacky } 360206084Srdivacky 361226633Sdim 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 371234353Sdim const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, 372203955Srdivacky const LocationContext *parent, 373218893Sdim const Stmt *s, 374218893Sdim const CFGBlock *blk, unsigned idx); 375203955Srdivacky 376234353Sdim const ScopeContext *getScope(AnalysisDeclContext *ctx, 377203955Srdivacky const LocationContext *parent, 378203955Srdivacky const Stmt *s); 379239462Sdim 380239462Sdim const BlockInvocationContext * 381239462Sdim getBlockInvocationContext(AnalysisDeclContext *ctx, 382239462Sdim const LocationContext *parent, 383239462Sdim const BlockDecl *BD, 384239462Sdim const void *ContextData); 385206084Srdivacky 386203955Srdivacky /// Discard all previously created LocationContext objects. 387203955Srdivacky void clear(); 388203955Srdivackyprivate: 389203955Srdivacky template <typename LOC, typename DATA> 390234353Sdim const LOC *getLocationContext(AnalysisDeclContext *ctx, 391203955Srdivacky const LocationContext *parent, 392203955Srdivacky const DATA *d); 393203955Srdivacky}; 394203955Srdivacky 395234353Sdimclass AnalysisDeclContextManager { 396234353Sdim typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap; 397234353Sdim 398234353Sdim ContextMap Contexts; 399234353Sdim LocationContextManager LocContexts; 400234353Sdim CFG::BuildOptions cfgBuildOptions; 401243830Sdim 402243830Sdim /// Flag to indicate whether or not bodies should be synthesized 403243830Sdim /// for well-known functions. 404243830Sdim bool SynthesizeBodies; 405234353Sdim 406234353Sdimpublic: 407234353Sdim AnalysisDeclContextManager(bool useUnoptimizedCFG = false, 408243830Sdim bool addImplicitDtors = false, 409243830Sdim bool addInitializers = false, 410243830Sdim bool addTemporaryDtors = false, 411249423Sdim bool synthesizeBodies = false, 412249423Sdim bool addStaticInitBranches = false); 413234353Sdim 414234353Sdim ~AnalysisDeclContextManager(); 415234353Sdim 416239462Sdim AnalysisDeclContext *getContext(const Decl *D); 417234353Sdim 418234353Sdim bool getUseUnoptimizedCFG() const { 419234353Sdim return !cfgBuildOptions.PruneTriviallyFalseEdges; 420234353Sdim } 421234353Sdim 422234353Sdim CFG::BuildOptions &getCFGBuildOptions() { 423234353Sdim return cfgBuildOptions; 424234353Sdim } 425243830Sdim 426243830Sdim /// Return true if faux bodies should be synthesized for well-known 427243830Sdim /// functions. 428243830Sdim bool synthesizeBodies() const { return SynthesizeBodies; } 429234353Sdim 430234353Sdim const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, 431234353Sdim LocationContext const *Parent, 432234353Sdim const Stmt *S, 433234353Sdim const CFGBlock *Blk, 434234353Sdim unsigned Idx) { 435234353Sdim return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); 436234353Sdim } 437234353Sdim 438234353Sdim // Get the top level stack frame. 439239462Sdim const StackFrameContext *getStackFrame(const Decl *D) { 440239462Sdim return LocContexts.getStackFrame(getContext(D), 0, 0, 0, 0); 441234353Sdim } 442234353Sdim 443234353Sdim // Get a stack frame with parent. 444234353Sdim StackFrameContext const *getStackFrame(const Decl *D, 445234353Sdim LocationContext const *Parent, 446234353Sdim const Stmt *S, 447234353Sdim const CFGBlock *Blk, 448234353Sdim unsigned Idx) { 449234353Sdim return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); 450234353Sdim } 451234353Sdim 452234353Sdim /// Discard all previously created AnalysisDeclContexts. 453234353Sdim void clear(); 454234353Sdim 455234353Sdimprivate: 456234353Sdim friend class AnalysisDeclContext; 457234353Sdim 458234353Sdim LocationContextManager &getLocationContextManager() { 459234353Sdim return LocContexts; 460234353Sdim } 461234353Sdim}; 462234353Sdim 463203955Srdivacky} // end clang namespace 464203955Srdivacky#endif 465