AnalysisDeclContext.h revision 360784
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 30namespace clang { 31 32class AnalysisDeclContextManager; 33class ASTContext; 34class BlockDecl; 35class BlockInvocationContext; 36class CFGReverseBlockReachabilityAnalysis; 37class CFGStmtMap; 38class ImplicitParamDecl; 39class LocationContext; 40class LocationContextManager; 41class ParentMap; 42class StackFrameContext; 43class Stmt; 44class VarDecl; 45 46/// The base class of a hierarchy of objects representing analyses tied 47/// to AnalysisDeclContext. 48class ManagedAnalysis { 49protected: 50 ManagedAnalysis() = default; 51 52public: 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. 69class 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 93public: 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, const CFGBlock *Blk, 187 unsigned BlockCount, unsigned Idx); 188 189 const BlockInvocationContext * 190 getBlockInvocationContext(const LocationContext *parent, 191 const BlockDecl *BD, 192 const void *ContextData); 193 194 /// Return the specified analysis object, lazily running the analysis if 195 /// necessary. Return NULL if the analysis could not run. 196 template <typename T> 197 T *getAnalysis() { 198 const void *tag = T::getTag(); 199 ManagedAnalysis *&data = getAnalysisImpl(tag); 200 if (!data) { 201 data = T::create(*this); 202 } 203 return static_cast<T *>(data); 204 } 205 206 /// Returns true if the root namespace of the given declaration is the 'std' 207 /// C++ namespace. 208 static bool isInStdNamespace(const Decl *D); 209 210private: 211 ManagedAnalysis *&getAnalysisImpl(const void* tag); 212 213 LocationContextManager &getLocationContextManager(); 214}; 215 216class LocationContext : public llvm::FoldingSetNode { 217public: 218 enum ContextKind { StackFrame, Scope, Block }; 219 220private: 221 ContextKind Kind; 222 223 // AnalysisDeclContext can't be const since some methods may modify its 224 // member. 225 AnalysisDeclContext *Ctx; 226 227 const LocationContext *Parent; 228 int64_t ID; 229 230protected: 231 LocationContext(ContextKind k, AnalysisDeclContext *ctx, 232 const LocationContext *parent, 233 int64_t ID) 234 : Kind(k), Ctx(ctx), Parent(parent), ID(ID) {} 235 236public: 237 virtual ~LocationContext(); 238 239 ContextKind getKind() const { return Kind; } 240 241 int64_t getID() const { 242 return ID; 243 } 244 245 AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } 246 247 const LocationContext *getParent() const { return Parent; } 248 249 bool isParentOf(const LocationContext *LC) const; 250 251 const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); } 252 253 CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); } 254 255 template <typename T> 256 T *getAnalysis() const { 257 return getAnalysisDeclContext()->getAnalysis<T>(); 258 } 259 260 const ParentMap &getParentMap() const { 261 return getAnalysisDeclContext()->getParentMap(); 262 } 263 264 const ImplicitParamDecl *getSelfDecl() const { 265 return Ctx->getSelfDecl(); 266 } 267 268 const StackFrameContext *getStackFrame() const; 269 270 /// Return true if the current LocationContext has no caller context. 271 virtual bool inTopFrame() const; 272 273 virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; 274 275 void dumpStack( 276 raw_ostream &Out, const char *NL = "\n", 277 std::function<void(const LocationContext *)> printMoreInfoPerContext = 278 [](const LocationContext *) {}) const; 279 280 void printJson( 281 raw_ostream &Out, const char *NL = "\n", unsigned int Space = 0, 282 bool IsDot = false, 283 std::function<void(const LocationContext *)> printMoreInfoPerContext = 284 [](const LocationContext *) {}) const; 285 286 void dump() const; 287 288public: 289 static void ProfileCommon(llvm::FoldingSetNodeID &ID, 290 ContextKind ck, 291 AnalysisDeclContext *ctx, 292 const LocationContext *parent, 293 const void *data); 294}; 295 296class StackFrameContext : public LocationContext { 297 friend class LocationContextManager; 298 299 // The callsite where this stack frame is established. 300 const Stmt *CallSite; 301 302 // The parent block of the callsite. 303 const CFGBlock *Block; 304 305 // The number of times the 'Block' has been visited. 306 // It allows discriminating between stack frames of the same call that is 307 // called multiple times in a loop. 308 const unsigned BlockCount; 309 310 // The index of the callsite in the CFGBlock. 311 const unsigned Index; 312 313 StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, 314 const Stmt *s, const CFGBlock *blk, unsigned blockCount, 315 unsigned idx, int64_t ID) 316 : LocationContext(StackFrame, ctx, parent, ID), CallSite(s), Block(blk), 317 BlockCount(blockCount), Index(idx) {} 318 319public: 320 ~StackFrameContext() override = default; 321 322 const Stmt *getCallSite() const { return CallSite; } 323 324 const CFGBlock *getCallSiteBlock() const { return Block; } 325 326 /// Return true if the current LocationContext has no caller context. 327 bool inTopFrame() const override { return getParent() == nullptr; } 328 329 unsigned getIndex() const { return Index; } 330 331 void Profile(llvm::FoldingSetNodeID &ID) override; 332 333 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 334 const LocationContext *parent, const Stmt *s, 335 const CFGBlock *blk, unsigned blockCount, unsigned idx) { 336 ProfileCommon(ID, StackFrame, ctx, parent, s); 337 ID.AddPointer(blk); 338 ID.AddInteger(blockCount); 339 ID.AddInteger(idx); 340 } 341 342 static bool classof(const LocationContext *Ctx) { 343 return Ctx->getKind() == StackFrame; 344 } 345}; 346 347class ScopeContext : public LocationContext { 348 friend class LocationContextManager; 349 350 const Stmt *Enter; 351 352 ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, 353 const Stmt *s, int64_t ID) 354 : LocationContext(Scope, ctx, parent, ID), Enter(s) {} 355 356public: 357 ~ScopeContext() override = default; 358 359 void Profile(llvm::FoldingSetNodeID &ID) override; 360 361 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 362 const LocationContext *parent, const Stmt *s) { 363 ProfileCommon(ID, Scope, ctx, parent, s); 364 } 365 366 static bool classof(const LocationContext *Ctx) { 367 return Ctx->getKind() == Scope; 368 } 369}; 370 371class BlockInvocationContext : public LocationContext { 372 friend class LocationContextManager; 373 374 const BlockDecl *BD; 375 376 // FIXME: Come up with a more type-safe way to model context-sensitivity. 377 const void *ContextData; 378 379 BlockInvocationContext(AnalysisDeclContext *ctx, 380 const LocationContext *parent, const BlockDecl *bd, 381 const void *contextData, int64_t ID) 382 : LocationContext(Block, ctx, parent, ID), BD(bd), 383 ContextData(contextData) {} 384 385public: 386 ~BlockInvocationContext() override = default; 387 388 const BlockDecl *getBlockDecl() const { return BD; } 389 390 const void *getContextData() const { return ContextData; } 391 392 void Profile(llvm::FoldingSetNodeID &ID) override; 393 394 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, 395 const LocationContext *parent, const BlockDecl *bd, 396 const void *contextData) { 397 ProfileCommon(ID, Block, ctx, parent, bd); 398 ID.AddPointer(contextData); 399 } 400 401 static bool classof(const LocationContext *Ctx) { 402 return Ctx->getKind() == Block; 403 } 404}; 405 406class LocationContextManager { 407 llvm::FoldingSet<LocationContext> Contexts; 408 409 /// ID used for generating a new location context. 410 int64_t NewID = 0; 411 412public: 413 ~LocationContextManager(); 414 415 const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, 416 const LocationContext *parent, 417 const Stmt *s, const CFGBlock *blk, 418 unsigned blockCount, unsigned idx); 419 420 const ScopeContext *getScope(AnalysisDeclContext *ctx, 421 const LocationContext *parent, 422 const Stmt *s); 423 424 const BlockInvocationContext * 425 getBlockInvocationContext(AnalysisDeclContext *ctx, 426 const LocationContext *parent, 427 const BlockDecl *BD, 428 const void *ContextData); 429 430 /// Discard all previously created LocationContext objects. 431 void clear(); 432private: 433 template <typename LOC, typename DATA> 434 const LOC *getLocationContext(AnalysisDeclContext *ctx, 435 const LocationContext *parent, 436 const DATA *d); 437}; 438 439class AnalysisDeclContextManager { 440 using ContextMap = 441 llvm::DenseMap<const Decl *, std::unique_ptr<AnalysisDeclContext>>; 442 443 ContextMap Contexts; 444 LocationContextManager LocContexts; 445 CFG::BuildOptions cfgBuildOptions; 446 447 /// Pointer to an interface that can provide function bodies for 448 /// declarations from external source. 449 std::unique_ptr<CodeInjector> Injector; 450 451 /// A factory for creating and caching implementations for common 452 /// methods during the analysis. 453 BodyFarm FunctionBodyFarm; 454 455 /// Flag to indicate whether or not bodies should be synthesized 456 /// for well-known functions. 457 bool SynthesizeBodies; 458 459public: 460 AnalysisDeclContextManager(ASTContext &ASTCtx, bool useUnoptimizedCFG = false, 461 bool addImplicitDtors = false, 462 bool addInitializers = false, 463 bool addTemporaryDtors = false, 464 bool addLifetime = false, 465 bool addLoopExit = false, 466 bool addScopes = false, 467 bool synthesizeBodies = false, 468 bool addStaticInitBranches = false, 469 bool addCXXNewAllocator = true, 470 bool addRichCXXConstructors = true, 471 bool markElidedCXXConstructors = true, 472 bool addVirtualBaseBranches = true, 473 CodeInjector *injector = nullptr); 474 475 AnalysisDeclContext *getContext(const Decl *D); 476 477 bool getUseUnoptimizedCFG() const { 478 return !cfgBuildOptions.PruneTriviallyFalseEdges; 479 } 480 481 CFG::BuildOptions &getCFGBuildOptions() { 482 return cfgBuildOptions; 483 } 484 485 /// Return true if faux bodies should be synthesized for well-known 486 /// functions. 487 bool synthesizeBodies() const { return SynthesizeBodies; } 488 489 const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, 490 const LocationContext *Parent, 491 const Stmt *S, const CFGBlock *Blk, 492 unsigned BlockCount, unsigned Idx) { 493 return LocContexts.getStackFrame(Ctx, Parent, S, Blk, BlockCount, Idx); 494 } 495 496 // Get the top level stack frame. 497 const StackFrameContext *getStackFrame(const Decl *D) { 498 return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr, 499 0, 0); 500 } 501 502 // Get a stack frame with parent. 503 StackFrameContext const *getStackFrame(const Decl *D, 504 const LocationContext *Parent, 505 const Stmt *S, const CFGBlock *Blk, 506 unsigned BlockCount, unsigned Idx) { 507 return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, BlockCount, 508 Idx); 509 } 510 511 /// Get a reference to {@code BodyFarm} instance. 512 BodyFarm &getBodyFarm(); 513 514 /// Discard all previously created AnalysisDeclContexts. 515 void clear(); 516 517private: 518 friend class AnalysisDeclContext; 519 520 LocationContextManager &getLocationContextManager() { 521 return LocContexts; 522 } 523}; 524 525} // namespace clang 526 527#endif // LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H 528