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