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