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