contrib/llvm/tools/clang/include/clang/Analysis/AnalysisDeclContext.h

   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
 104   ASTContext &getASTContext() const { return D->getASTContext(); }
 105   const Decl *getDecl() const { return D; }
 106
 107   /// Return the AnalysisDeclContextManager (if any) that created
 108   /// this AnalysisDeclContext.
 109   AnalysisDeclContextManager *getManager() const {
 110     return Manager;
 111   }
 112
 113   /// Return the build options used to construct the CFG.
 114   CFG::BuildOptions &getCFGBuildOptions() {
 115     return cfgBuildOptions;
 116   }
 117
 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.
 126   bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; }
 127   bool getUseUnoptimizedCFG() const {
 128       return !cfgBuildOptions.PruneTriviallyFalseEdges;
 129   }
 130   bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; }
 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.
 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>
 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:
 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
 241   ContextKind getKind() const { return Kind; }
 242
 243   int64_t getID() const {
 244     return ID;
 245   }
 246
 247   AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; }
 248
 249   const LocationContext *getParent() const { return Parent; }
 250
 251   bool isParentOf(const LocationContext *LC) const;
 252
 253   const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); }
 254
 255   CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); }
 256
 257   template <typename T>
 258   T *getAnalysis() const {
 259     return getAnalysisDeclContext()->getAnalysis<T>();
 260   }
 261
 262   ParentMap &getParentMap() const {
 263     return getAnalysisDeclContext()->getParentMap();
 264   }
 265
 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
 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
 314   const Stmt *getCallSite() const { return CallSite; }
 315
 316   const CFGBlock *getCallSiteBlock() const { return Block; }
 317
 318   /// Return true if the current LocationContext has no caller context.
 319   bool inTopFrame() const override { return getParent() == nullptr;  }
 320
 321   unsigned getIndex() const { return Index; }
 322
 323   void Profile(llvm::FoldingSetNodeID &ID) override;
 324
 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
 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
 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
 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
 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
 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
 379   const BlockDecl *getBlockDecl() const { return BD; }
 380
 381   const void *getContextData() const { return ContextData; }
 382
 383   void Profile(llvm::FoldingSetNodeID &ID) override;
 384
 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
 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
 467   bool getUseUnoptimizedCFG() const {
 468     return !cfgBuildOptions.PruneTriviallyFalseEdges;
 469   }
 470
 471   CFG::BuildOptions &getCFGBuildOptions() {
 472     return cfgBuildOptions;
 473   }
 474
 475   /// Return true if faux bodies should be synthesized for well-known
 476   /// functions.
 477   bool synthesizeBodies() const { return SynthesizeBodies; }
 478
 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.
 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.
 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
 511   LocationContextManager &getLocationContextManager() {
 512     return LocContexts;
 513   }
 514 };
 515
 516 } // namespace clang
 517
 518 #endif // LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H