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/AST/Expr.h"
  20 #include "clang/Analysis/CFG.h"
  21 #include "llvm/ADT/OwningPtr.h"
  22 #include "llvm/ADT/IntrusiveRefCntPtr.h"
  23 #include "llvm/ADT/FoldingSet.h"
  24 #include "llvm/ADT/PointerUnion.h"
  25 #include "llvm/ADT/DenseMap.h"
  26 #include "llvm/Support/Allocator.h"
  27
  28 namespace clang {
  29
  30 class Decl;
  31 class Stmt;
  32 class CFGReverseBlockReachabilityAnalysis;
  33 class CFGStmtMap;
  34 class LiveVariables;
  35 class ManagedAnalysis;
  36 class ParentMap;
  37 class PseudoConstantAnalysis;
  38 class ImplicitParamDecl;
  39 class LocationContextManager;
  40 class StackFrameContext;
  41 class BlockInvocationContext;
  42 class AnalysisDeclContextManager;
  43 class LocationContext;
  44
  45 namespace idx { class TranslationUnit; }
  46
  47 /// The base class of a hierarchy of objects representing analyses tied
  48 /// to AnalysisDeclContext.
  49 class ManagedAnalysis {
  50 protected:
  51   ManagedAnalysis() {}
  52 public:
  53   virtual ~ManagedAnalysis();
  54
  55   // Subclasses need to implement:
  56   //
  57   //  static const void *getTag();
  58   //
  59   // Which returns a fixed pointer address to distinguish classes of
  60   // analysis objects.  They also need to implement:
  61   //
  62   //  static [Derived*] create(AnalysisDeclContext &Ctx);
  63   //
  64   // which creates the analysis object given an AnalysisDeclContext.
  65 };
  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   OwningPtr<CFG> cfg, completeCFG;
  78   OwningPtr<CFGStmtMap> cfgStmtMap;
  79
  80   CFG::BuildOptions cfgBuildOptions;
  81   CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs;
  82
  83   bool builtCFG, builtCompleteCFG;
  84   OwningPtr<ParentMap> PM;
  85   OwningPtr<PseudoConstantAnalysis> PCA;
  86   OwningPtr<CFGReverseBlockReachabilityAnalysis> CFA;
  87
  88   llvm::BumpPtrAllocator A;
  89
  90   llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars;
  91
  92   void *ManagedAnalyses;
  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   Stmt *getBody() const;
 137   CFG *getCFG();
 138
 139   CFGStmtMap *getCFGStmtMap();
 140
 141   CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis();
 142
 143   /// Return a version of the CFG without any edges pruned.
 144   CFG *getUnoptimizedCFG();
 145
 146   void dumpCFG(bool ShowColors);
 147
 148   /// \brief Returns true if we have built a CFG for this analysis context.
 149   /// Note that this doesn't correspond to whether or not a valid CFG exists, it
 150   /// corresponds to whether we *attempted* to build one.
 151   bool isCFGBuilt() const { return builtCFG; }
 152
 153   ParentMap &getParentMap();
 154   PseudoConstantAnalysis *getPseudoConstantAnalysis();
 155
 156   typedef const VarDecl * const * referenced_decls_iterator;
 157
 158   std::pair<referenced_decls_iterator, referenced_decls_iterator>
 159     getReferencedBlockVars(const BlockDecl *BD);
 160
 161   /// Return the ImplicitParamDecl* associated with 'self' if this
 162   /// AnalysisDeclContext wraps an ObjCMethodDecl.  Returns NULL otherwise.
 163   const ImplicitParamDecl *getSelfDecl() const;
 164
 165   const StackFrameContext *getStackFrame(LocationContext const *Parent,
 166                                          const Stmt *S,
 167                                          const CFGBlock *Blk,
 168                                          unsigned Idx);
 169
 170   const BlockInvocationContext *
 171   getBlockInvocationContext(const LocationContext *parent,
 172                             const BlockDecl *BD,
 173                             const void *ContextData);
 174
 175   /// Return the specified analysis object, lazily running the analysis if
 176   /// necessary.  Return NULL if the analysis could not run.
 177   template <typename T>
 178   T *getAnalysis() {
 179     const void *tag = T::getTag();
 180     ManagedAnalysis *&data = getAnalysisImpl(tag);
 181     if (!data) {
 182       data = T::create(*this);
 183     }
 184     return static_cast<T*>(data);
 185   }
 186 private:
 187   ManagedAnalysis *&getAnalysisImpl(const void* tag);
 188
 189   LocationContextManager &getLocationContextManager();
 190 };
 191
 192 class LocationContext : public llvm::FoldingSetNode {
 193 public:
 194   enum ContextKind { StackFrame, Scope, Block };
 195
 196 private:
 197   ContextKind Kind;
 198
 199   // AnalysisDeclContext can't be const since some methods may modify its
 200   // member.
 201   AnalysisDeclContext *Ctx;
 202
 203   const LocationContext *Parent;
 204
 205 protected:
 206   LocationContext(ContextKind k, AnalysisDeclContext *ctx,
 207                   const LocationContext *parent)
 208     : Kind(k), Ctx(ctx), Parent(parent) {}
 209
 210 public:
 211   virtual ~LocationContext();
 212
 213   ContextKind getKind() const { return Kind; }
 214
 215   AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; }
 216
 217   const LocationContext *getParent() const { return Parent; }
 218
 219   bool isParentOf(const LocationContext *LC) const;
 220
 221   const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); }
 222
 223   CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); }
 224
 225   template <typename T>
 226   T *getAnalysis() const {
 227     return getAnalysisDeclContext()->getAnalysis<T>();
 228   }
 229
 230   ParentMap &getParentMap() const {
 231     return getAnalysisDeclContext()->getParentMap();
 232   }
 233
 234   const ImplicitParamDecl *getSelfDecl() const {
 235     return Ctx->getSelfDecl();
 236   }
 237
 238   const StackFrameContext *getCurrentStackFrame() const;
 239
 240   /// Return true if the current LocationContext has no caller context.
 241   virtual bool inTopFrame() const;
 242
 243   virtual void Profile(llvm::FoldingSetNodeID &ID) = 0;
 244
 245 public:
 246   static void ProfileCommon(llvm::FoldingSetNodeID &ID,
 247                             ContextKind ck,
 248                             AnalysisDeclContext *ctx,
 249                             const LocationContext *parent,
 250                             const void *data);
 251 };
 252
 253 class StackFrameContext : public LocationContext {
 254   // The callsite where this stack frame is established.
 255   const Stmt *CallSite;
 256
 257   // The parent block of the callsite.
 258   const CFGBlock *Block;
 259
 260   // The index of the callsite in the CFGBlock.
 261   unsigned Index;
 262
 263   friend class LocationContextManager;
 264   StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent,
 265                     const Stmt *s, const CFGBlock *blk,
 266                     unsigned idx)
 267     : LocationContext(StackFrame, ctx, parent), CallSite(s),
 268       Block(blk), Index(idx) {}
 269
 270 public:
 271   ~StackFrameContext() {}
 272
 273   const Stmt *getCallSite() const { return CallSite; }
 274
 275   const CFGBlock *getCallSiteBlock() const { return Block; }
 276
 277   /// Return true if the current LocationContext has no caller context.
 278   virtual bool inTopFrame() const { return getParent() == 0;  }
 279
 280   unsigned getIndex() const { return Index; }
 281
 282   void Profile(llvm::FoldingSetNodeID &ID);
 283
 284   static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
 285                       const LocationContext *parent, const Stmt *s,
 286                       const CFGBlock *blk, unsigned idx) {
 287     ProfileCommon(ID, StackFrame, ctx, parent, s);
 288     ID.AddPointer(blk);
 289     ID.AddInteger(idx);
 290   }
 291
 292   static bool classof(const LocationContext *Ctx) {
 293     return Ctx->getKind() == StackFrame;
 294   }
 295 };
 296
 297 class ScopeContext : public LocationContext {
 298   const Stmt *Enter;
 299
 300   friend class LocationContextManager;
 301   ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent,
 302                const Stmt *s)
 303     : LocationContext(Scope, ctx, parent), Enter(s) {}
 304
 305 public:
 306   ~ScopeContext() {}
 307
 308   void Profile(llvm::FoldingSetNodeID &ID);
 309
 310   static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
 311                       const LocationContext *parent, const Stmt *s) {
 312     ProfileCommon(ID, Scope, ctx, parent, s);
 313   }
 314
 315   static bool classof(const LocationContext *Ctx) {
 316     return Ctx->getKind() == Scope;
 317   }
 318 };
 319
 320 class BlockInvocationContext : public LocationContext {
 321   const BlockDecl *BD;
 322
 323   // FIXME: Come up with a more type-safe way to model context-sensitivity.
 324   const void *ContextData;
 325
 326   friend class LocationContextManager;
 327
 328   BlockInvocationContext(AnalysisDeclContext *ctx,
 329                          const LocationContext *parent,
 330                          const BlockDecl *bd, const void *contextData)
 331     : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {}
 332
 333 public:
 334   ~BlockInvocationContext() {}
 335
 336   const BlockDecl *getBlockDecl() const { return BD; }
 337
 338   const void *getContextData() const { return ContextData; }
 339
 340   void Profile(llvm::FoldingSetNodeID &ID);
 341
 342   static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
 343                       const LocationContext *parent, const BlockDecl *bd,
 344                       const void *contextData) {
 345     ProfileCommon(ID, Block, ctx, parent, bd);
 346     ID.AddPointer(contextData);
 347   }
 348
 349   static bool classof(const LocationContext *Ctx) {
 350     return Ctx->getKind() == Block;
 351   }
 352 };
 353
 354 class LocationContextManager {
 355   llvm::FoldingSet<LocationContext> Contexts;
 356 public:
 357   ~LocationContextManager();
 358
 359   const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx,
 360                                          const LocationContext *parent,
 361                                          const Stmt *s,
 362                                          const CFGBlock *blk, unsigned idx);
 363
 364   const ScopeContext *getScope(AnalysisDeclContext *ctx,
 365                                const LocationContext *parent,
 366                                const Stmt *s);
 367
 368   const BlockInvocationContext *
 369   getBlockInvocationContext(AnalysisDeclContext *ctx,
 370                             const LocationContext *parent,
 371                             const BlockDecl *BD,
 372                             const void *ContextData);
 373
 374   /// Discard all previously created LocationContext objects.
 375   void clear();
 376 private:
 377   template <typename LOC, typename DATA>
 378   const LOC *getLocationContext(AnalysisDeclContext *ctx,
 379                                 const LocationContext *parent,
 380                                 const DATA *d);
 381 };
 382
 383 class AnalysisDeclContextManager {
 384   typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap;
 385
 386   ContextMap Contexts;
 387   LocationContextManager LocContexts;
 388   CFG::BuildOptions cfgBuildOptions;
 389
 390   /// Flag to indicate whether or not bodies should be synthesized
 391   /// for well-known functions.
 392   bool SynthesizeBodies;
 393
 394 public:
 395   AnalysisDeclContextManager(bool useUnoptimizedCFG = false,
 396                              bool addImplicitDtors = false,
 397                              bool addInitializers = false,
 398                              bool addTemporaryDtors = false,
 399                              bool synthesizeBodies = false);
 400
 401   ~AnalysisDeclContextManager();
 402
 403   AnalysisDeclContext *getContext(const Decl *D);
 404
 405   bool getUseUnoptimizedCFG() const {
 406     return !cfgBuildOptions.PruneTriviallyFalseEdges;
 407   }
 408
 409   CFG::BuildOptions &getCFGBuildOptions() {
 410     return cfgBuildOptions;
 411   }
 412
 413   /// Return true if faux bodies should be synthesized for well-known
 414   /// functions.
 415   bool synthesizeBodies() const { return SynthesizeBodies; }
 416
 417   const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx,
 418                                          LocationContext const *Parent,
 419                                          const Stmt *S,
 420                                          const CFGBlock *Blk,
 421                                          unsigned Idx) {
 422     return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx);
 423   }
 424
 425   // Get the top level stack frame.
 426   const StackFrameContext *getStackFrame(const Decl *D) {
 427     return LocContexts.getStackFrame(getContext(D), 0, 0, 0, 0);
 428   }
 429
 430   // Get a stack frame with parent.
 431   StackFrameContext const *getStackFrame(const Decl *D,
 432                                          LocationContext const *Parent,
 433                                          const Stmt *S,
 434                                          const CFGBlock *Blk,
 435                                          unsigned Idx) {
 436     return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx);
 437   }
 438
 439   /// Discard all previously created AnalysisDeclContexts.
 440   void clear();
 441
 442 private:
 443   friend class AnalysisDeclContext;
 444
 445   LocationContextManager &getLocationContextManager() {
 446     return LocContexts;
 447   }
 448 };
 449
 450 } // end clang namespace
 451 #endif