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