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