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