contrib/llvm/tools/clang/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 private:
 205   ManagedAnalysis *&getAnalysisImpl(const void* tag);
 206
 207   LocationContextManager &getLocationContextManager();
 208 };
 209
 210 class LocationContext : public llvm::FoldingSetNode {
 211 public:
 212   enum ContextKind { StackFrame, Scope, Block };
 213
 214 private:
 215   ContextKind Kind;
 216
 217   // AnalysisDeclContext can't be const since some methods may modify its
 218   // member.
 219   AnalysisDeclContext *Ctx;
 220
 221   const LocationContext *Parent;
 222
 223 protected:
 224   LocationContext(ContextKind k, AnalysisDeclContext *ctx,
 225                   const LocationContext *parent)
 226     : Kind(k), Ctx(ctx), Parent(parent) {}
 227
 228 public:
 229   virtual ~LocationContext();
 230
 231   ContextKind getKind() const { return Kind; }
 232
 233   AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; }
 234
 235   const LocationContext *getParent() const { return Parent; }
 236
 237   bool isParentOf(const LocationContext *LC) const;
 238
 239   const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); }
 240
 241   CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); }
 242
 243   template <typename T>
 244   T *getAnalysis() const {
 245     return getAnalysisDeclContext()->getAnalysis<T>();
 246   }
 247
 248   ParentMap &getParentMap() const {
 249     return getAnalysisDeclContext()->getParentMap();
 250   }
 251
 252   const ImplicitParamDecl *getSelfDecl() const {
 253     return Ctx->getSelfDecl();
 254   }
 255
 256   const StackFrameContext *getCurrentStackFrame() const;
 257
 258   /// Return true if the current LocationContext has no caller context.
 259   virtual bool inTopFrame() const;
 260
 261   virtual void Profile(llvm::FoldingSetNodeID &ID) = 0;
 262
 263   void dumpStack(raw_ostream &OS, StringRef Indent = "") const;
 264   void dumpStack() const;
 265
 266 public:
 267   static void ProfileCommon(llvm::FoldingSetNodeID &ID,
 268                             ContextKind ck,
 269                             AnalysisDeclContext *ctx,
 270                             const LocationContext *parent,
 271                             const void *data);
 272 };
 273
 274 class StackFrameContext : public LocationContext {
 275   // The callsite where this stack frame is established.
 276   const Stmt *CallSite;
 277
 278   // The parent block of the callsite.
 279   const CFGBlock *Block;
 280
 281   // The index of the callsite in the CFGBlock.
 282   unsigned Index;
 283
 284   friend class LocationContextManager;
 285   StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent,
 286                     const Stmt *s, const CFGBlock *blk,
 287                     unsigned idx)
 288     : LocationContext(StackFrame, ctx, parent), CallSite(s),
 289       Block(blk), Index(idx) {}
 290
 291 public:
 292   ~StackFrameContext() override {}
 293
 294   const Stmt *getCallSite() const { return CallSite; }
 295
 296   const CFGBlock *getCallSiteBlock() const { return Block; }
 297
 298   /// Return true if the current LocationContext has no caller context.
 299   bool inTopFrame() const override { return getParent() == nullptr;  }
 300
 301   unsigned getIndex() const { return Index; }
 302
 303   void Profile(llvm::FoldingSetNodeID &ID) override;
 304
 305   static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
 306                       const LocationContext *parent, const Stmt *s,
 307                       const CFGBlock *blk, unsigned idx) {
 308     ProfileCommon(ID, StackFrame, ctx, parent, s);
 309     ID.AddPointer(blk);
 310     ID.AddInteger(idx);
 311   }
 312
 313   static bool classof(const LocationContext *Ctx) {
 314     return Ctx->getKind() == StackFrame;
 315   }
 316 };
 317
 318 class ScopeContext : public LocationContext {
 319   const Stmt *Enter;
 320
 321   friend class LocationContextManager;
 322   ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent,
 323                const Stmt *s)
 324     : LocationContext(Scope, ctx, parent), Enter(s) {}
 325
 326 public:
 327   ~ScopeContext() override {}
 328
 329   void Profile(llvm::FoldingSetNodeID &ID) override;
 330
 331   static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
 332                       const LocationContext *parent, const Stmt *s) {
 333     ProfileCommon(ID, Scope, ctx, parent, s);
 334   }
 335
 336   static bool classof(const LocationContext *Ctx) {
 337     return Ctx->getKind() == Scope;
 338   }
 339 };
 340
 341 class BlockInvocationContext : public LocationContext {
 342   const BlockDecl *BD;
 343
 344   // FIXME: Come up with a more type-safe way to model context-sensitivity.
 345   const void *ContextData;
 346
 347   friend class LocationContextManager;
 348
 349   BlockInvocationContext(AnalysisDeclContext *ctx,
 350                          const LocationContext *parent,
 351                          const BlockDecl *bd, const void *contextData)
 352     : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {}
 353
 354 public:
 355   ~BlockInvocationContext() override {}
 356
 357   const BlockDecl *getBlockDecl() const { return BD; }
 358
 359   const void *getContextData() const { return ContextData; }
 360
 361   void Profile(llvm::FoldingSetNodeID &ID) override;
 362
 363   static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
 364                       const LocationContext *parent, const BlockDecl *bd,
 365                       const void *contextData) {
 366     ProfileCommon(ID, Block, ctx, parent, bd);
 367     ID.AddPointer(contextData);
 368   }
 369
 370   static bool classof(const LocationContext *Ctx) {
 371     return Ctx->getKind() == Block;
 372   }
 373 };
 374
 375 class LocationContextManager {
 376   llvm::FoldingSet<LocationContext> Contexts;
 377 public:
 378   ~LocationContextManager();
 379
 380   const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx,
 381                                          const LocationContext *parent,
 382                                          const Stmt *s,
 383                                          const CFGBlock *blk, unsigned idx);
 384
 385   const ScopeContext *getScope(AnalysisDeclContext *ctx,
 386                                const LocationContext *parent,
 387                                const Stmt *s);
 388
 389   const BlockInvocationContext *
 390   getBlockInvocationContext(AnalysisDeclContext *ctx,
 391                             const LocationContext *parent,
 392                             const BlockDecl *BD,
 393                             const void *ContextData);
 394
 395   /// Discard all previously created LocationContext objects.
 396   void clear();
 397 private:
 398   template <typename LOC, typename DATA>
 399   const LOC *getLocationContext(AnalysisDeclContext *ctx,
 400                                 const LocationContext *parent,
 401                                 const DATA *d);
 402 };
 403
 404 class AnalysisDeclContextManager {
 405   typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap;
 406
 407   ContextMap Contexts;
 408   LocationContextManager LocContexts;
 409   CFG::BuildOptions cfgBuildOptions;
 410
 411   /// Pointer to an interface that can provide function bodies for
 412   /// declarations from external source.
 413   std::unique_ptr<CodeInjector> Injector;
 414
 415   /// Flag to indicate whether or not bodies should be synthesized
 416   /// for well-known functions.
 417   bool SynthesizeBodies;
 418
 419 public:
 420   AnalysisDeclContextManager(bool useUnoptimizedCFG = false,
 421                              bool addImplicitDtors = false,
 422                              bool addInitializers = false,
 423                              bool addTemporaryDtors = false,
 424                              bool synthesizeBodies = false,
 425                              bool addStaticInitBranches = false,
 426                              bool addCXXNewAllocator = true,
 427                              CodeInjector* injector = nullptr);
 428
 429   ~AnalysisDeclContextManager();
 430
 431   AnalysisDeclContext *getContext(const Decl *D);
 432
 433   bool getUseUnoptimizedCFG() const {
 434     return !cfgBuildOptions.PruneTriviallyFalseEdges;
 435   }
 436
 437   CFG::BuildOptions &getCFGBuildOptions() {
 438     return cfgBuildOptions;
 439   }
 440
 441   /// Return true if faux bodies should be synthesized for well-known
 442   /// functions.
 443   bool synthesizeBodies() const { return SynthesizeBodies; }
 444
 445   const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx,
 446                                          LocationContext const *Parent,
 447                                          const Stmt *S,
 448                                          const CFGBlock *Blk,
 449                                          unsigned Idx) {
 450     return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx);
 451   }
 452
 453   // Get the top level stack frame.
 454   const StackFrameContext *getStackFrame(const Decl *D) {
 455     return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr,
 456                                      0);
 457   }
 458
 459   // Get a stack frame with parent.
 460   StackFrameContext const *getStackFrame(const Decl *D,
 461                                          LocationContext const *Parent,
 462                                          const Stmt *S,
 463                                          const CFGBlock *Blk,
 464                                          unsigned Idx) {
 465     return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx);
 466   }
 467
 468   /// Discard all previously created AnalysisDeclContexts.
 469   void clear();
 470
 471 private:
 472   friend class AnalysisDeclContext;
 473
 474   LocationContextManager &getLocationContextManager() {
 475     return LocContexts;
 476   }
 477 };
 478
 479 } // end clang namespace
 480 #endif