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