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