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