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/OwningPtr.h" 22#include "llvm/ADT/IntrusiveRefCntPtr.h" 23#include "llvm/ADT/FoldingSet.h" 24#include "llvm/ADT/PointerUnion.h" 25#include "llvm/ADT/DenseMap.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 *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 85 OwningPtr<LiveVariables> liveness; 86 OwningPtr<LiveVariables> relaxedLiveness; 87 OwningPtr<ParentMap> PM; 88 OwningPtr<PseudoConstantAnalysis> PCA; 89 OwningPtr<CFGReverseBlockReachabilityAnalysis> CFA; 90 91 llvm::BumpPtrAllocator A; 92 93 llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; 94 95 void *ManagedAnalyses; 96 97public: 98 AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 99 const Decl *D); 100 101 AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 102 const Decl *D, 103 const CFG::BuildOptions &BuildOptions); 104 105 ~AnalysisDeclContext(); 106 107 ASTContext &getASTContext() { return D->getASTContext(); } 108 const Decl *getDecl() const { return D; } 109 110 /// Return the build options used to construct the CFG. 111 CFG::BuildOptions &getCFGBuildOptions() { 112 return cfgBuildOptions; 113 } 114 115 const CFG::BuildOptions &getCFGBuildOptions() const { 116 return cfgBuildOptions; 117 } 118 119 /// getAddEHEdges - Return true iff we are adding exceptional edges from 120 /// callExprs. If this is false, then try/catch statements and blocks 121 /// reachable from them can appear to be dead in the CFG, analysis passes must 122 /// cope with that. 123 bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; } 124 bool getUseUnoptimizedCFG() const { 125 return !cfgBuildOptions.PruneTriviallyFalseEdges; 126 } 127 bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; } 128 bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; } 129 130 void registerForcedBlockExpression(const Stmt *stmt); 131 const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt); 132 133 Stmt *getBody() const; 134 CFG *getCFG(); 135 136 CFGStmtMap *getCFGStmtMap(); 137 138 CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis(); 139 140 /// Return a version of the CFG without any edges pruned. 141 CFG *getUnoptimizedCFG(); 142 143 void dumpCFG(bool ShowColors); 144 145 /// \brief Returns true if we have built a CFG for this analysis context. 146 /// Note that this doesn't correspond to whether or not a valid CFG exists, it 147 /// corresponds to whether we *attempted* to build one. 148 bool isCFGBuilt() const { return builtCFG; } 149 150 ParentMap &getParentMap(); 151 PseudoConstantAnalysis *getPseudoConstantAnalysis(); 152 153 typedef const VarDecl * const * referenced_decls_iterator; 154 155 std::pair<referenced_decls_iterator, referenced_decls_iterator> 156 getReferencedBlockVars(const BlockDecl *BD); 157 158 /// Return the ImplicitParamDecl* associated with 'self' if this 159 /// AnalysisDeclContext wraps an ObjCMethodDecl. Returns NULL otherwise. 160 const ImplicitParamDecl *getSelfDecl() const; 161 162 const StackFrameContext *getStackFrame(LocationContext const *Parent, 163 const Stmt *S, 164 const CFGBlock *Blk, 165 unsigned Idx); 166 167 const BlockInvocationContext * 168 getBlockInvocationContext(const LocationContext *parent, 169 const BlockDecl *BD, 170 const void *ContextData); 171 172 /// Return the specified analysis object, lazily running the analysis if 173 /// necessary. Return NULL if the analysis could not run. 174 template <typename T> 175 T *getAnalysis() { 176 const void *tag = T::getTag(); 177 ManagedAnalysis *&data = getAnalysisImpl(tag); 178 if (!data) { 179 data = T::create(*this); 180 } 181 return static_cast<T*>(data); 182 } 183private: 184 ManagedAnalysis *&getAnalysisImpl(const void* tag); 185 186 LocationContextManager &getLocationContextManager(); 187}; 188 189class LocationContext : public llvm::FoldingSetNode { 190public: 191 enum ContextKind { StackFrame, Scope, Block }; 192 193private: 194 ContextKind Kind; 195 196 // AnalysisDeclContext can't be const since some methods may modify its 197 // member. 198 AnalysisDeclContext *Ctx; 199 200 const LocationContext *Parent; 201 202protected: 203 LocationContext(ContextKind k, AnalysisDeclContext *ctx, 204 const LocationContext *parent) 205 : Kind(k), Ctx(ctx), Parent(parent) {} 206 207public: 208 virtual ~LocationContext(); 209 210 ContextKind getKind() const { return Kind; } 211 212 AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } 213 214 const LocationContext *getParent() const { return Parent; } 215 216 bool isParentOf(const LocationContext *LC) const; 217 218 const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); } 219 220 CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); } 221 222 template <typename T> 223 T *getAnalysis() const { 224 return getAnalysisDeclContext()->getAnalysis<T>(); 225 } 226 227 ParentMap &getParentMap() const { 228 return getAnalysisDeclContext()->getParentMap(); 229 } 230 231 const ImplicitParamDecl *getSelfDecl() const { 232 return Ctx->getSelfDecl(); 233 } 234 235 const StackFrameContext *getCurrentStackFrame() const; 236 237 virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; 238 239 static bool classof(const LocationContext*) { return true; } 240 241public: 242 static void ProfileCommon(llvm::FoldingSetNodeID &ID, 243 ContextKind ck, 244 AnalysisDeclContext *ctx, 245 const LocationContext *parent, 246 const void *data); 247}; 248 249class StackFrameContext : public LocationContext { 250 // The callsite where this stack frame is established. 251 const Stmt *CallSite; 252 253 // The parent block of the callsite. 254 const CFGBlock *Block; 255 256 // The index of the callsite in the CFGBlock. 257 unsigned Index; 258 259 friend class LocationContextManager; 260 StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, 261 const Stmt *s, const CFGBlock *blk, 262 unsigned idx) 263 : LocationContext(StackFrame, ctx, parent), CallSite(s), 264 Block(blk), Index(idx) {} 265 266public: 267 ~StackFrameContext() {} 268 269 const Stmt *getCallSite() const { return CallSite; } 270 271 const CFGBlock *getCallSiteBlock() const { return Block; } 272 273 unsigned getIndex() const { return Index; } 274 275 void Profile(llvm::FoldingSetNodeID &ID); 276 277 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 278 const LocationContext *parent, const Stmt *s, 279 const CFGBlock *blk, unsigned idx) { 280 ProfileCommon(ID, StackFrame, ctx, parent, s); 281 ID.AddPointer(blk); 282 ID.AddInteger(idx); 283 } 284 285 static bool classof(const LocationContext *Ctx) { 286 return Ctx->getKind() == StackFrame; 287 } 288}; 289 290class ScopeContext : public LocationContext { 291 const Stmt *Enter; 292 293 friend class LocationContextManager; 294 ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, 295 const Stmt *s) 296 : LocationContext(Scope, ctx, parent), Enter(s) {} 297 298public: 299 ~ScopeContext() {} 300 301 void Profile(llvm::FoldingSetNodeID &ID); 302 303 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 304 const LocationContext *parent, const Stmt *s) { 305 ProfileCommon(ID, Scope, ctx, parent, s); 306 } 307 308 static bool classof(const LocationContext *Ctx) { 309 return Ctx->getKind() == Scope; 310 } 311}; 312 313class BlockInvocationContext : public LocationContext { 314 const BlockDecl *BD; 315 316 // FIXME: Come up with a more type-safe way to model context-sensitivity. 317 const void *ContextData; 318 319 friend class LocationContextManager; 320 321 BlockInvocationContext(AnalysisDeclContext *ctx, 322 const LocationContext *parent, 323 const BlockDecl *bd, const void *contextData) 324 : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} 325 326public: 327 ~BlockInvocationContext() {} 328 329 const BlockDecl *getBlockDecl() const { return BD; } 330 331 const void *getContextData() const { return ContextData; } 332 333 void Profile(llvm::FoldingSetNodeID &ID); 334 335 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 336 const LocationContext *parent, const BlockDecl *bd, 337 const void *contextData) { 338 ProfileCommon(ID, Block, ctx, parent, bd); 339 ID.AddPointer(contextData); 340 } 341 342 static bool classof(const LocationContext *Ctx) { 343 return Ctx->getKind() == Block; 344 } 345}; 346 347class LocationContextManager { 348 llvm::FoldingSet<LocationContext> Contexts; 349public: 350 ~LocationContextManager(); 351 352 const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, 353 const LocationContext *parent, 354 const Stmt *s, 355 const CFGBlock *blk, unsigned idx); 356 357 const ScopeContext *getScope(AnalysisDeclContext *ctx, 358 const LocationContext *parent, 359 const Stmt *s); 360 361 const BlockInvocationContext * 362 getBlockInvocationContext(AnalysisDeclContext *ctx, 363 const LocationContext *parent, 364 const BlockDecl *BD, 365 const void *ContextData); 366 367 /// Discard all previously created LocationContext objects. 368 void clear(); 369private: 370 template <typename LOC, typename DATA> 371 const LOC *getLocationContext(AnalysisDeclContext *ctx, 372 const LocationContext *parent, 373 const DATA *d); 374}; 375 376class AnalysisDeclContextManager { 377 typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap; 378 379 ContextMap Contexts; 380 LocationContextManager LocContexts; 381 CFG::BuildOptions cfgBuildOptions; 382 383public: 384 AnalysisDeclContextManager(bool useUnoptimizedCFG = false, 385 bool addImplicitDtors = false, 386 bool addInitializers = false, 387 bool addTemporaryDtors = false); 388 389 ~AnalysisDeclContextManager(); 390 391 AnalysisDeclContext *getContext(const Decl *D); 392 393 bool getUseUnoptimizedCFG() const { 394 return !cfgBuildOptions.PruneTriviallyFalseEdges; 395 } 396 397 CFG::BuildOptions &getCFGBuildOptions() { 398 return cfgBuildOptions; 399 } 400 401 const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, 402 LocationContext const *Parent, 403 const Stmt *S, 404 const CFGBlock *Blk, 405 unsigned Idx) { 406 return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); 407 } 408 409 // Get the top level stack frame. 410 const StackFrameContext *getStackFrame(const Decl *D) { 411 return LocContexts.getStackFrame(getContext(D), 0, 0, 0, 0); 412 } 413 414 // Get a stack frame with parent. 415 StackFrameContext const *getStackFrame(const Decl *D, 416 LocationContext const *Parent, 417 const Stmt *S, 418 const CFGBlock *Blk, 419 unsigned Idx) { 420 return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); 421 } 422 423 /// Discard all previously created AnalysisDeclContexts. 424 void clear(); 425 426private: 427 friend class AnalysisDeclContext; 428 429 LocationContextManager &getLocationContextManager() { 430 return LocContexts; 431 } 432}; 433 434} // end clang namespace 435#endif 436