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