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/Analysis/CFG.h" 20 #include "clang/Analysis/CodeInjector.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/FoldingSet.h" 23 #include "llvm/Support/Allocator.h" 24 #include <memory> 25 26 namespace clang { 27 28 class Stmt; 29 class CFGReverseBlockReachabilityAnalysis; 30 class CFGStmtMap; 31 class LiveVariables; 32 class ManagedAnalysis; 33 class ParentMap; 34 class PseudoConstantAnalysis; 35 class LocationContextManager; 36 class StackFrameContext; 37 class BlockInvocationContext; 38 class AnalysisDeclContextManager; 39 class LocationContext; 40 41 namespace idx { class TranslationUnit; } 42 43 /// The base class of a hierarchy of objects representing analyses tied 44 /// to AnalysisDeclContext. 45 class ManagedAnalysis { 46 protected: ManagedAnalysis()47 ManagedAnalysis() {} 48 public: 49 virtual ~ManagedAnalysis(); 50 51 // Subclasses need to implement: 52 // 53 // static const void *getTag(); 54 // 55 // Which returns a fixed pointer address to distinguish classes of 56 // analysis objects. They also need to implement: 57 // 58 // static [Derived*] create(AnalysisDeclContext &Ctx); 59 // 60 // which creates the analysis object given an AnalysisDeclContext. 61 }; 62 63 64 /// AnalysisDeclContext contains the context data for the function or method 65 /// under analysis. 66 class AnalysisDeclContext { 67 /// Backpoint to the AnalysisManager object that created this 68 /// AnalysisDeclContext. This may be null. 69 AnalysisDeclContextManager *Manager; 70 71 const Decl * const D; 72 73 std::unique_ptr<CFG> cfg, completeCFG; 74 std::unique_ptr<CFGStmtMap> cfgStmtMap; 75 76 CFG::BuildOptions cfgBuildOptions; 77 CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs; 78 79 bool builtCFG, builtCompleteCFG; 80 std::unique_ptr<ParentMap> PM; 81 std::unique_ptr<PseudoConstantAnalysis> PCA; 82 std::unique_ptr<CFGReverseBlockReachabilityAnalysis> CFA; 83 84 llvm::BumpPtrAllocator A; 85 86 llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; 87 88 void *ManagedAnalyses; 89 90 public: 91 AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 92 const Decl *D); 93 94 AnalysisDeclContext(AnalysisDeclContextManager *Mgr, 95 const Decl *D, 96 const CFG::BuildOptions &BuildOptions); 97 98 ~AnalysisDeclContext(); 99 getASTContext()100 ASTContext &getASTContext() const { return D->getASTContext(); } getDecl()101 const Decl *getDecl() const { return D; } 102 103 /// Return the AnalysisDeclContextManager (if any) that created 104 /// this AnalysisDeclContext. getManager()105 AnalysisDeclContextManager *getManager() const { 106 return Manager; 107 } 108 109 /// Return the build options used to construct the CFG. getCFGBuildOptions()110 CFG::BuildOptions &getCFGBuildOptions() { 111 return cfgBuildOptions; 112 } 113 getCFGBuildOptions()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. getAddEHEdges()122 bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; } getUseUnoptimizedCFG()123 bool getUseUnoptimizedCFG() const { 124 return !cfgBuildOptions.PruneTriviallyFalseEdges; 125 } getAddImplicitDtors()126 bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; } getAddInitializers()127 bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; } 128 129 void registerForcedBlockExpression(const Stmt *stmt); 130 const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt); 131 132 /// \brief Get the body of the Declaration. 133 Stmt *getBody() const; 134 135 /// \brief Get the body of the Declaration. 136 /// \param[out] IsAutosynthesized Specifies if the body is auto-generated 137 /// by the BodyFarm. 138 Stmt *getBody(bool &IsAutosynthesized) const; 139 140 /// \brief Checks if the body of the Decl is generated by the BodyFarm. 141 /// 142 /// Note, the lookup is not free. We are going to call getBody behind 143 /// the scenes. 144 /// \sa getBody 145 bool isBodyAutosynthesized() const; 146 147 /// \brief Checks if the body of the Decl is generated by the BodyFarm from a 148 /// model file. 149 /// 150 /// Note, the lookup is not free. We are going to call getBody behind 151 /// the scenes. 152 /// \sa getBody 153 bool isBodyAutosynthesizedFromModelFile() const; 154 155 CFG *getCFG(); 156 157 CFGStmtMap *getCFGStmtMap(); 158 159 CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis(); 160 161 /// Return a version of the CFG without any edges pruned. 162 CFG *getUnoptimizedCFG(); 163 164 void dumpCFG(bool ShowColors); 165 166 /// \brief Returns true if we have built a CFG for this analysis context. 167 /// Note that this doesn't correspond to whether or not a valid CFG exists, it 168 /// corresponds to whether we *attempted* to build one. isCFGBuilt()169 bool isCFGBuilt() const { return builtCFG; } 170 171 ParentMap &getParentMap(); 172 PseudoConstantAnalysis *getPseudoConstantAnalysis(); 173 174 typedef const VarDecl * const * referenced_decls_iterator; 175 176 llvm::iterator_range<referenced_decls_iterator> 177 getReferencedBlockVars(const BlockDecl *BD); 178 179 /// Return the ImplicitParamDecl* associated with 'self' if this 180 /// AnalysisDeclContext wraps an ObjCMethodDecl. Returns NULL otherwise. 181 const ImplicitParamDecl *getSelfDecl() const; 182 183 const StackFrameContext *getStackFrame(LocationContext const *Parent, 184 const Stmt *S, 185 const CFGBlock *Blk, 186 unsigned Idx); 187 188 const BlockInvocationContext * 189 getBlockInvocationContext(const LocationContext *parent, 190 const BlockDecl *BD, 191 const void *ContextData); 192 193 /// Return the specified analysis object, lazily running the analysis if 194 /// necessary. Return NULL if the analysis could not run. 195 template <typename T> getAnalysis()196 T *getAnalysis() { 197 const void *tag = T::getTag(); 198 ManagedAnalysis *&data = getAnalysisImpl(tag); 199 if (!data) { 200 data = T::create(*this); 201 } 202 return static_cast<T*>(data); 203 } 204 205 /// Returns true if the root namespace of the given declaration is the 'std' 206 /// C++ namespace. 207 static bool isInStdNamespace(const Decl *D); 208 private: 209 ManagedAnalysis *&getAnalysisImpl(const void* tag); 210 211 LocationContextManager &getLocationContextManager(); 212 }; 213 214 class LocationContext : public llvm::FoldingSetNode { 215 public: 216 enum ContextKind { StackFrame, Scope, Block }; 217 218 private: 219 ContextKind Kind; 220 221 // AnalysisDeclContext can't be const since some methods may modify its 222 // member. 223 AnalysisDeclContext *Ctx; 224 225 const LocationContext *Parent; 226 227 protected: LocationContext(ContextKind k,AnalysisDeclContext * ctx,const LocationContext * parent)228 LocationContext(ContextKind k, AnalysisDeclContext *ctx, 229 const LocationContext *parent) 230 : Kind(k), Ctx(ctx), Parent(parent) {} 231 232 public: 233 virtual ~LocationContext(); 234 getKind()235 ContextKind getKind() const { return Kind; } 236 getAnalysisDeclContext()237 AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } 238 getParent()239 const LocationContext *getParent() const { return Parent; } 240 241 bool isParentOf(const LocationContext *LC) const; 242 getDecl()243 const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); } 244 getCFG()245 CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); } 246 247 template <typename T> getAnalysis()248 T *getAnalysis() const { 249 return getAnalysisDeclContext()->getAnalysis<T>(); 250 } 251 getParentMap()252 ParentMap &getParentMap() const { 253 return getAnalysisDeclContext()->getParentMap(); 254 } 255 getSelfDecl()256 const ImplicitParamDecl *getSelfDecl() const { 257 return Ctx->getSelfDecl(); 258 } 259 260 const StackFrameContext *getCurrentStackFrame() const; 261 262 /// Return true if the current LocationContext has no caller context. 263 virtual bool inTopFrame() const; 264 265 virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; 266 267 void dumpStack(raw_ostream &OS, StringRef Indent = "") const; 268 void dumpStack() const; 269 270 public: 271 static void ProfileCommon(llvm::FoldingSetNodeID &ID, 272 ContextKind ck, 273 AnalysisDeclContext *ctx, 274 const LocationContext *parent, 275 const void *data); 276 }; 277 278 class StackFrameContext : public LocationContext { 279 // The callsite where this stack frame is established. 280 const Stmt *CallSite; 281 282 // The parent block of the callsite. 283 const CFGBlock *Block; 284 285 // The index of the callsite in the CFGBlock. 286 unsigned Index; 287 288 friend class LocationContextManager; StackFrameContext(AnalysisDeclContext * ctx,const LocationContext * parent,const Stmt * s,const CFGBlock * blk,unsigned idx)289 StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, 290 const Stmt *s, const CFGBlock *blk, 291 unsigned idx) 292 : LocationContext(StackFrame, ctx, parent), CallSite(s), 293 Block(blk), Index(idx) {} 294 295 public: ~StackFrameContext()296 ~StackFrameContext() override {} 297 getCallSite()298 const Stmt *getCallSite() const { return CallSite; } 299 getCallSiteBlock()300 const CFGBlock *getCallSiteBlock() const { return Block; } 301 302 /// Return true if the current LocationContext has no caller context. inTopFrame()303 bool inTopFrame() const override { return getParent() == nullptr; } 304 getIndex()305 unsigned getIndex() const { return Index; } 306 307 void Profile(llvm::FoldingSetNodeID &ID) override; 308 Profile(llvm::FoldingSetNodeID & ID,AnalysisDeclContext * ctx,const LocationContext * parent,const Stmt * s,const CFGBlock * blk,unsigned idx)309 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 310 const LocationContext *parent, const Stmt *s, 311 const CFGBlock *blk, unsigned idx) { 312 ProfileCommon(ID, StackFrame, ctx, parent, s); 313 ID.AddPointer(blk); 314 ID.AddInteger(idx); 315 } 316 classof(const LocationContext * Ctx)317 static bool classof(const LocationContext *Ctx) { 318 return Ctx->getKind() == StackFrame; 319 } 320 }; 321 322 class ScopeContext : public LocationContext { 323 const Stmt *Enter; 324 325 friend class LocationContextManager; ScopeContext(AnalysisDeclContext * ctx,const LocationContext * parent,const Stmt * s)326 ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, 327 const Stmt *s) 328 : LocationContext(Scope, ctx, parent), Enter(s) {} 329 330 public: ~ScopeContext()331 ~ScopeContext() override {} 332 333 void Profile(llvm::FoldingSetNodeID &ID) override; 334 Profile(llvm::FoldingSetNodeID & ID,AnalysisDeclContext * ctx,const LocationContext * parent,const Stmt * s)335 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 336 const LocationContext *parent, const Stmt *s) { 337 ProfileCommon(ID, Scope, ctx, parent, s); 338 } 339 classof(const LocationContext * Ctx)340 static bool classof(const LocationContext *Ctx) { 341 return Ctx->getKind() == Scope; 342 } 343 }; 344 345 class BlockInvocationContext : public LocationContext { 346 const BlockDecl *BD; 347 348 // FIXME: Come up with a more type-safe way to model context-sensitivity. 349 const void *ContextData; 350 351 friend class LocationContextManager; 352 BlockInvocationContext(AnalysisDeclContext * ctx,const LocationContext * parent,const BlockDecl * bd,const void * contextData)353 BlockInvocationContext(AnalysisDeclContext *ctx, 354 const LocationContext *parent, 355 const BlockDecl *bd, const void *contextData) 356 : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} 357 358 public: ~BlockInvocationContext()359 ~BlockInvocationContext() override {} 360 getBlockDecl()361 const BlockDecl *getBlockDecl() const { return BD; } 362 getContextData()363 const void *getContextData() const { return ContextData; } 364 365 void Profile(llvm::FoldingSetNodeID &ID) override; 366 Profile(llvm::FoldingSetNodeID & ID,AnalysisDeclContext * ctx,const LocationContext * parent,const BlockDecl * bd,const void * contextData)367 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 368 const LocationContext *parent, const BlockDecl *bd, 369 const void *contextData) { 370 ProfileCommon(ID, Block, ctx, parent, bd); 371 ID.AddPointer(contextData); 372 } 373 classof(const LocationContext * Ctx)374 static bool classof(const LocationContext *Ctx) { 375 return Ctx->getKind() == Block; 376 } 377 }; 378 379 class LocationContextManager { 380 llvm::FoldingSet<LocationContext> Contexts; 381 public: 382 ~LocationContextManager(); 383 384 const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, 385 const LocationContext *parent, 386 const Stmt *s, 387 const CFGBlock *blk, unsigned idx); 388 389 const ScopeContext *getScope(AnalysisDeclContext *ctx, 390 const LocationContext *parent, 391 const Stmt *s); 392 393 const BlockInvocationContext * 394 getBlockInvocationContext(AnalysisDeclContext *ctx, 395 const LocationContext *parent, 396 const BlockDecl *BD, 397 const void *ContextData); 398 399 /// Discard all previously created LocationContext objects. 400 void clear(); 401 private: 402 template <typename LOC, typename DATA> 403 const LOC *getLocationContext(AnalysisDeclContext *ctx, 404 const LocationContext *parent, 405 const DATA *d); 406 }; 407 408 class AnalysisDeclContextManager { 409 typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap; 410 411 ContextMap Contexts; 412 LocationContextManager LocContexts; 413 CFG::BuildOptions cfgBuildOptions; 414 415 /// Pointer to an interface that can provide function bodies for 416 /// declarations from external source. 417 std::unique_ptr<CodeInjector> Injector; 418 419 /// Flag to indicate whether or not bodies should be synthesized 420 /// for well-known functions. 421 bool SynthesizeBodies; 422 423 public: 424 AnalysisDeclContextManager(bool useUnoptimizedCFG = false, 425 bool addImplicitDtors = false, 426 bool addInitializers = false, 427 bool addTemporaryDtors = false, 428 bool synthesizeBodies = false, 429 bool addStaticInitBranches = false, 430 bool addCXXNewAllocator = true, 431 CodeInjector* injector = nullptr); 432 433 ~AnalysisDeclContextManager(); 434 435 AnalysisDeclContext *getContext(const Decl *D); 436 getUseUnoptimizedCFG()437 bool getUseUnoptimizedCFG() const { 438 return !cfgBuildOptions.PruneTriviallyFalseEdges; 439 } 440 getCFGBuildOptions()441 CFG::BuildOptions &getCFGBuildOptions() { 442 return cfgBuildOptions; 443 } 444 445 /// Return true if faux bodies should be synthesized for well-known 446 /// functions. synthesizeBodies()447 bool synthesizeBodies() const { return SynthesizeBodies; } 448 getStackFrame(AnalysisDeclContext * Ctx,LocationContext const * Parent,const Stmt * S,const CFGBlock * Blk,unsigned Idx)449 const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, 450 LocationContext const *Parent, 451 const Stmt *S, 452 const CFGBlock *Blk, 453 unsigned Idx) { 454 return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); 455 } 456 457 // Get the top level stack frame. getStackFrame(const Decl * D)458 const StackFrameContext *getStackFrame(const Decl *D) { 459 return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr, 460 0); 461 } 462 463 // Get a stack frame with parent. getStackFrame(const Decl * D,LocationContext const * Parent,const Stmt * S,const CFGBlock * Blk,unsigned Idx)464 StackFrameContext const *getStackFrame(const Decl *D, 465 LocationContext const *Parent, 466 const Stmt *S, 467 const CFGBlock *Blk, 468 unsigned Idx) { 469 return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); 470 } 471 472 /// Discard all previously created AnalysisDeclContexts. 473 void clear(); 474 475 private: 476 friend class AnalysisDeclContext; 477 getLocationContextManager()478 LocationContextManager &getLocationContextManager() { 479 return LocContexts; 480 } 481 }; 482 483 } // end clang namespace 484 #endif 485