include/clang/Analysis/AnalysisContext.h

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