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