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