AnalysisContext.h revision ba243b59a1074e0962f6abfa3bb9aa984eac1245
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  // FIXME: remove.
96  llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars;
97
98  void *ManagedAnalyses;
99
100public:
101  AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
102                  const Decl *D,
103                  idx::TranslationUnit *TU);
104
105  AnalysisDeclContext(AnalysisDeclContextManager *Mgr,
106                  const Decl *D,
107                  idx::TranslationUnit *TU,
108                  const CFG::BuildOptions &BuildOptions);
109
110  ~AnalysisDeclContext();
111
112  ASTContext &getASTContext() { return D->getASTContext(); }
113  const Decl *getDecl() const { return D; }
114
115  idx::TranslationUnit *getTranslationUnit() const { return TU; }
116
117  /// Return the build options used to construct the CFG.
118  CFG::BuildOptions &getCFGBuildOptions() {
119    return cfgBuildOptions;
120  }
121
122  const CFG::BuildOptions &getCFGBuildOptions() const {
123    return cfgBuildOptions;
124  }
125
126  /// getAddEHEdges - Return true iff we are adding exceptional edges from
127  /// callExprs.  If this is false, then try/catch statements and blocks
128  /// reachable from them can appear to be dead in the CFG, analysis passes must
129  /// cope with that.
130  bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; }
131  bool getUseUnoptimizedCFG() const {
132      return !cfgBuildOptions.PruneTriviallyFalseEdges;
133  }
134  bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; }
135  bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; }
136
137  void registerForcedBlockExpression(const Stmt *stmt);
138  const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt);
139
140  Stmt *getBody() const;
141  CFG *getCFG();
142
143  CFGStmtMap *getCFGStmtMap();
144
145  CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis();
146
147  /// Return a version of the CFG without any edges pruned.
148  CFG *getUnoptimizedCFG();
149
150  void dumpCFG();
151
152  /// \brief Returns true if we have built a CFG for this analysis context.
153  /// Note that this doesn't correspond to whether or not a valid CFG exists, it
154  /// corresponds to whether we *attempted* to build one.
155  bool isCFGBuilt() const { return builtCFG; }
156
157  ParentMap &getParentMap();
158  PseudoConstantAnalysis *getPseudoConstantAnalysis();
159
160  typedef const VarDecl * const * referenced_decls_iterator;
161
162  std::pair<referenced_decls_iterator, referenced_decls_iterator>
163    getReferencedBlockVars(const BlockDecl *BD);
164
165  /// Return the ImplicitParamDecl* associated with 'self' if this
166  /// AnalysisDeclContext wraps an ObjCMethodDecl.  Returns NULL otherwise.
167  const ImplicitParamDecl *getSelfDecl() const;
168
169  const StackFrameContext *getStackFrame(LocationContext const *Parent,
170                                         const Stmt *S,
171                                         const CFGBlock *Blk,
172                                         unsigned Idx);
173
174  /// Return the specified analysis object, lazily running the analysis if
175  /// necessary.  Return NULL if the analysis could not run.
176  template <typename T>
177  T *getAnalysis() {
178    const void *tag = T::getTag();
179    ManagedAnalysis *&data = getAnalysisImpl(tag);
180    if (!data) {
181      data = T::create(*this);
182    }
183    return static_cast<T*>(data);
184  }
185private:
186  ManagedAnalysis *&getAnalysisImpl(const void* tag);
187
188  LocationContextManager &getLocationContextManager();
189};
190
191class LocationContext : public llvm::FoldingSetNode {
192public:
193  enum ContextKind { StackFrame, Scope, Block };
194
195private:
196  ContextKind Kind;
197
198  // AnalysisDeclContext can't be const since some methods may modify its
199  // member.
200  AnalysisDeclContext *Ctx;
201
202  const LocationContext *Parent;
203
204protected:
205  LocationContext(ContextKind k, AnalysisDeclContext *ctx,
206                  const LocationContext *parent)
207    : Kind(k), Ctx(ctx), Parent(parent) {}
208
209public:
210  virtual ~LocationContext();
211
212  ContextKind getKind() const { return Kind; }
213
214  AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; }
215
216  idx::TranslationUnit *getTranslationUnit() const {
217    return Ctx->getTranslationUnit();
218  }
219
220  const LocationContext *getParent() const { return Parent; }
221
222  bool isParentOf(const LocationContext *LC) const;
223
224  const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); }
225
226  CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); }
227
228  template <typename T>
229  T *getAnalysis() const {
230    return getAnalysisDeclContext()->getAnalysis<T>();
231  }
232
233  ParentMap &getParentMap() const {
234    return getAnalysisDeclContext()->getParentMap();
235  }
236
237  const ImplicitParamDecl *getSelfDecl() const {
238    return Ctx->getSelfDecl();
239  }
240
241  const StackFrameContext *getCurrentStackFrame() const;
242  const StackFrameContext *
243    getStackFrameForDeclContext(const DeclContext *DC) const;
244
245  virtual void Profile(llvm::FoldingSetNodeID &ID) = 0;
246
247  static bool classof(const LocationContext*) { return true; }
248
249public:
250  static void ProfileCommon(llvm::FoldingSetNodeID &ID,
251                            ContextKind ck,
252                            AnalysisDeclContext *ctx,
253                            const LocationContext *parent,
254                            const void *data);
255};
256
257class StackFrameContext : public LocationContext {
258  // The callsite where this stack frame is established.
259  const Stmt *CallSite;
260
261  // The parent block of the callsite.
262  const CFGBlock *Block;
263
264  // The index of the callsite in the CFGBlock.
265  unsigned Index;
266
267  friend class LocationContextManager;
268  StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent,
269                    const Stmt *s, const CFGBlock *blk,
270                    unsigned idx)
271    : LocationContext(StackFrame, ctx, parent), CallSite(s),
272      Block(blk), Index(idx) {}
273
274public:
275  ~StackFrameContext() {}
276
277  const Stmt *getCallSite() const { return CallSite; }
278
279  const CFGBlock *getCallSiteBlock() const { return Block; }
280
281  unsigned getIndex() const { return Index; }
282
283  void Profile(llvm::FoldingSetNodeID &ID);
284
285  static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
286                      const LocationContext *parent, const Stmt *s,
287                      const CFGBlock *blk, unsigned idx) {
288    ProfileCommon(ID, StackFrame, ctx, parent, s);
289    ID.AddPointer(blk);
290    ID.AddInteger(idx);
291  }
292
293  static bool classof(const LocationContext *Ctx) {
294    return Ctx->getKind() == StackFrame;
295  }
296};
297
298class ScopeContext : public LocationContext {
299  const Stmt *Enter;
300
301  friend class LocationContextManager;
302  ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent,
303               const Stmt *s)
304    : LocationContext(Scope, ctx, parent), Enter(s) {}
305
306public:
307  ~ScopeContext() {}
308
309  void Profile(llvm::FoldingSetNodeID &ID);
310
311  static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
312                      const LocationContext *parent, const Stmt *s) {
313    ProfileCommon(ID, Scope, ctx, parent, s);
314  }
315
316  static bool classof(const LocationContext *Ctx) {
317    return Ctx->getKind() == Scope;
318  }
319};
320
321class BlockInvocationContext : public LocationContext {
322  // FIXME: Add back context-sensivity (we don't want libAnalysis to know
323  //  about MemRegion).
324  const BlockDecl *BD;
325
326  friend class LocationContextManager;
327
328  BlockInvocationContext(AnalysisDeclContext *ctx,
329                         const LocationContext *parent,
330                         const BlockDecl *bd)
331    : LocationContext(Block, ctx, parent), BD(bd) {}
332
333public:
334  ~BlockInvocationContext() {}
335
336  const BlockDecl *getBlockDecl() const { return BD; }
337
338  void Profile(llvm::FoldingSetNodeID &ID);
339
340  static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
341                      const LocationContext *parent, const BlockDecl *bd) {
342    ProfileCommon(ID, Block, ctx, parent, bd);
343  }
344
345  static bool classof(const LocationContext *Ctx) {
346    return Ctx->getKind() == Block;
347  }
348};
349
350class LocationContextManager {
351  llvm::FoldingSet<LocationContext> Contexts;
352public:
353  ~LocationContextManager();
354
355  const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx,
356                                         const LocationContext *parent,
357                                         const Stmt *s,
358                                         const CFGBlock *blk, unsigned idx);
359
360  const ScopeContext *getScope(AnalysisDeclContext *ctx,
361                               const LocationContext *parent,
362                               const Stmt *s);
363
364  /// Discard all previously created LocationContext objects.
365  void clear();
366private:
367  template <typename LOC, typename DATA>
368  const LOC *getLocationContext(AnalysisDeclContext *ctx,
369                                const LocationContext *parent,
370                                const DATA *d);
371};
372
373class AnalysisDeclContextManager {
374  typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap;
375
376  ContextMap Contexts;
377  LocationContextManager LocContexts;
378  CFG::BuildOptions cfgBuildOptions;
379
380public:
381  AnalysisDeclContextManager(bool useUnoptimizedCFG = false,
382                         bool addImplicitDtors = false,
383                         bool addInitializers = false);
384
385  ~AnalysisDeclContextManager();
386
387  AnalysisDeclContext *getContext(const Decl *D, idx::TranslationUnit *TU = 0);
388
389  bool getUseUnoptimizedCFG() const {
390    return !cfgBuildOptions.PruneTriviallyFalseEdges;
391  }
392
393  CFG::BuildOptions &getCFGBuildOptions() {
394    return cfgBuildOptions;
395  }
396
397  const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx,
398                                         LocationContext const *Parent,
399                                         const Stmt *S,
400                                         const CFGBlock *Blk,
401                                         unsigned Idx) {
402    return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx);
403  }
404
405  // Get the top level stack frame.
406  const StackFrameContext *getStackFrame(Decl const *D,
407                                         idx::TranslationUnit *TU) {
408    return LocContexts.getStackFrame(getContext(D, TU), 0, 0, 0, 0);
409  }
410
411  // Get a stack frame with parent.
412  StackFrameContext const *getStackFrame(const Decl *D,
413                                         LocationContext const *Parent,
414                                         const Stmt *S,
415                                         const CFGBlock *Blk,
416                                         unsigned Idx) {
417    return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx);
418  }
419
420
421  /// Discard all previously created AnalysisDeclContexts.
422  void clear();
423
424private:
425  friend class AnalysisDeclContext;
426
427  LocationContextManager &getLocationContextManager() {
428    return LocContexts;
429  }
430};
431
432} // end clang namespace
433#endif
434