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