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