AnalysisContext.h revision f3477c13eeaf11b32a41f181398fb5deffd0dd73
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 242 static bool classof(const LocationContext*) { return true; } 243 244public: 245 static void ProfileCommon(llvm::FoldingSetNodeID &ID, 246 ContextKind ck, 247 AnalysisDeclContext *ctx, 248 const LocationContext *parent, 249 const void *data); 250}; 251 252class StackFrameContext : public LocationContext { 253 // The callsite where this stack frame is established. 254 const Stmt *CallSite; 255 256 // The parent block of the callsite. 257 const CFGBlock *Block; 258 259 // The index of the callsite in the CFGBlock. 260 unsigned Index; 261 262 friend class LocationContextManager; 263 StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, 264 const Stmt *s, const CFGBlock *blk, 265 unsigned idx) 266 : LocationContext(StackFrame, ctx, parent), CallSite(s), 267 Block(blk), Index(idx) {} 268 269public: 270 ~StackFrameContext() {} 271 272 const Stmt *getCallSite() const { return CallSite; } 273 274 const CFGBlock *getCallSiteBlock() const { return Block; } 275 276 unsigned getIndex() const { return Index; } 277 278 void Profile(llvm::FoldingSetNodeID &ID); 279 280 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 281 const LocationContext *parent, const Stmt *s, 282 const CFGBlock *blk, unsigned idx) { 283 ProfileCommon(ID, StackFrame, ctx, parent, s); 284 ID.AddPointer(blk); 285 ID.AddInteger(idx); 286 } 287 288 static bool classof(const LocationContext *Ctx) { 289 return Ctx->getKind() == StackFrame; 290 } 291}; 292 293class ScopeContext : public LocationContext { 294 const Stmt *Enter; 295 296 friend class LocationContextManager; 297 ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, 298 const Stmt *s) 299 : LocationContext(Scope, ctx, parent), Enter(s) {} 300 301public: 302 ~ScopeContext() {} 303 304 void Profile(llvm::FoldingSetNodeID &ID); 305 306 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 307 const LocationContext *parent, const Stmt *s) { 308 ProfileCommon(ID, Scope, ctx, parent, s); 309 } 310 311 static bool classof(const LocationContext *Ctx) { 312 return Ctx->getKind() == Scope; 313 } 314}; 315 316class BlockInvocationContext : public LocationContext { 317 const BlockDecl *BD; 318 319 // FIXME: Come up with a more type-safe way to model context-sensitivity. 320 const void *ContextData; 321 322 friend class LocationContextManager; 323 324 BlockInvocationContext(AnalysisDeclContext *ctx, 325 const LocationContext *parent, 326 const BlockDecl *bd, const void *contextData) 327 : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} 328 329public: 330 ~BlockInvocationContext() {} 331 332 const BlockDecl *getBlockDecl() const { return BD; } 333 334 const void *getContextData() const { return ContextData; } 335 336 void Profile(llvm::FoldingSetNodeID &ID); 337 338 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 339 const LocationContext *parent, const BlockDecl *bd, 340 const void *contextData) { 341 ProfileCommon(ID, Block, ctx, parent, bd); 342 ID.AddPointer(contextData); 343 } 344 345 static bool classof(const LocationContext *Ctx) { 346 return Ctx->getKind() == Block; 347 } 348}; 349 350class LocationContextManager { 351 llvm::FoldingSet<LocationContext> Contexts; 352public: 353 ~LocationContextManager(); 354 355 const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, 356 const LocationContext *parent, 357 const Stmt *s, 358 const CFGBlock *blk, unsigned idx); 359 360 const ScopeContext *getScope(AnalysisDeclContext *ctx, 361 const LocationContext *parent, 362 const Stmt *s); 363 364 const BlockInvocationContext * 365 getBlockInvocationContext(AnalysisDeclContext *ctx, 366 const LocationContext *parent, 367 const BlockDecl *BD, 368 const void *ContextData); 369 370 /// Discard all previously created LocationContext objects. 371 void clear(); 372private: 373 template <typename LOC, typename DATA> 374 const LOC *getLocationContext(AnalysisDeclContext *ctx, 375 const LocationContext *parent, 376 const DATA *d); 377}; 378 379class AnalysisDeclContextManager { 380 typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap; 381 382 ContextMap Contexts; 383 LocationContextManager LocContexts; 384 CFG::BuildOptions cfgBuildOptions; 385 386 /// Flag to indicate whether or not bodies should be synthesized 387 /// for well-known functions. 388 bool SynthesizeBodies; 389 390public: 391 AnalysisDeclContextManager(bool useUnoptimizedCFG = false, 392 bool addImplicitDtors = false, 393 bool addInitializers = false, 394 bool addTemporaryDtors = false, 395 bool synthesizeBodies = false); 396 397 ~AnalysisDeclContextManager(); 398 399 AnalysisDeclContext *getContext(const Decl *D); 400 401 bool getUseUnoptimizedCFG() const { 402 return !cfgBuildOptions.PruneTriviallyFalseEdges; 403 } 404 405 CFG::BuildOptions &getCFGBuildOptions() { 406 return cfgBuildOptions; 407 } 408 409 /// Return true if faux bodies should be synthesized for well-known 410 /// functions. 411 bool synthesizeBodies() const { return SynthesizeBodies; } 412 413 const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, 414 LocationContext const *Parent, 415 const Stmt *S, 416 const CFGBlock *Blk, 417 unsigned Idx) { 418 return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); 419 } 420 421 // Get the top level stack frame. 422 const StackFrameContext *getStackFrame(const Decl *D) { 423 return LocContexts.getStackFrame(getContext(D), 0, 0, 0, 0); 424 } 425 426 // Get a stack frame with parent. 427 StackFrameContext const *getStackFrame(const Decl *D, 428 LocationContext const *Parent, 429 const Stmt *S, 430 const CFGBlock *Blk, 431 unsigned Idx) { 432 return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); 433 } 434 435 /// Discard all previously created AnalysisDeclContexts. 436 void clear(); 437 438private: 439 friend class AnalysisDeclContext; 440 441 LocationContextManager &getLocationContextManager() { 442 return LocContexts; 443 } 444}; 445 446} // end clang namespace 447#endif 448