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