1// AnalysisDeclContext.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_ANALYSISDECLCONTEXT_H
16#define LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H
17
18#include "clang/AST/DeclBase.h"
19#include "clang/Analysis/BodyFarm.h"
20#include "clang/Analysis/CFG.h"
21#include "clang/Analysis/CodeInjector.h"
22#include "clang/Basic/LLVM.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/FoldingSet.h"
25#include "llvm/ADT/StringRef.h"
26#include "llvm/ADT/iterator_range.h"
27#include "llvm/Support/Allocator.h"
28#include <functional>
29#include <memory>
30
31namespace clang {
32
33class AnalysisDeclContextManager;
34class ASTContext;
35class BlockDecl;
36class BlockInvocationContext;
37class CFGReverseBlockReachabilityAnalysis;
38class CFGStmtMap;
39class ImplicitParamDecl;
40class LocationContext;
41class LocationContextManager;
42class ParentMap;
43class StackFrameContext;
44class Stmt;
45class VarDecl;
46
47/// The base class of a hierarchy of objects representing analyses tied
48/// to AnalysisDeclContext.
49class ManagedAnalysis {
50protected:
51 ManagedAnalysis() = default;
52
53public:
54 virtual ~ManagedAnalysis();
55
56 // Subclasses need to implement:
57 //
58 // static const void *getTag();
59 //
60 // Which returns a fixed pointer address to distinguish classes of
61 // analysis objects. They also need to implement:
62 //
63 // static [Derived*] create(AnalysisDeclContext &Ctx);
64 //
65 // which creates the analysis object given an AnalysisDeclContext.
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 std::unique_ptr<CFG> cfg, completeCFG;
78 std::unique_ptr<CFGStmtMap> cfgStmtMap;
79
80 CFG::BuildOptions cfgBuildOptions;
81 CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs = nullptr;
82
83 bool builtCFG = false;
84 bool builtCompleteCFG = false;
85 std::unique_ptr<ParentMap> PM;
86 std::unique_ptr<CFGReverseBlockReachabilityAnalysis> CFA;
87
88 llvm::BumpPtrAllocator A;
89
90 llvm::DenseMap<const BlockDecl *,void *> *ReferencedBlockVars = nullptr;
91
92 void *ManagedAnalyses = nullptr;
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 /// Get the body of the Declaration.
137 Stmt *getBody() const;
138
139 /// 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 /// 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 /// Checks if the body of the Decl is generated by the BodyFarm from a
152 /// model file.
153 ///
154 /// Note, the lookup is not free. We are going to call getBody behind
155 /// the scenes.
156 /// \sa getBody
157 bool isBodyAutosynthesizedFromModelFile() const;
158
159 CFG *getCFG();
160
161 CFGStmtMap *getCFGStmtMap();
162
163 CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis();
164
165 /// Return a version of the CFG without any edges pruned.
166 CFG *getUnoptimizedCFG();
167
168 void dumpCFG(bool ShowColors);
169
170 /// Returns true if we have built a CFG for this analysis context.
171 /// Note that this doesn't correspond to whether or not a valid CFG exists, it
172 /// corresponds to whether we *attempted* to build one.
173 bool isCFGBuilt() const { return builtCFG; }
174
175 ParentMap &getParentMap();
176
177 using referenced_decls_iterator = const VarDecl * const *;
178
179 llvm::iterator_range<referenced_decls_iterator>
180 getReferencedBlockVars(const BlockDecl *BD);
181
182 /// Return the ImplicitParamDecl* associated with 'self' if this
183 /// AnalysisDeclContext wraps an ObjCMethodDecl. Returns NULL otherwise.
184 const ImplicitParamDecl *getSelfDecl() const;
185
186 const StackFrameContext *getStackFrame(LocationContext const *Parent,
187 const Stmt *S,
188 const CFGBlock *Blk,
189 unsigned Idx);
190
191 const BlockInvocationContext *
192 getBlockInvocationContext(const LocationContext *parent,
193 const BlockDecl *BD,
194 const void *ContextData);
195
196 /// Return the specified analysis object, lazily running the analysis if
197 /// necessary. Return NULL if the analysis could not run.
198 template <typename T>
199 T *getAnalysis() {
200 const void *tag = T::getTag();
201 ManagedAnalysis *&data = getAnalysisImpl(tag);
202 if (!data) {
203 data = T::create(*this);
204 }
205 return static_cast<T *>(data);
206 }
207
208 /// Returns true if the root namespace of the given declaration is the 'std'
209 /// C++ namespace.
210 static bool isInStdNamespace(const Decl *D);
211
212private:
213 ManagedAnalysis *&getAnalysisImpl(const void* tag);
214
215 LocationContextManager &getLocationContextManager();
216};
217
218class LocationContext : public llvm::FoldingSetNode {
219public:
220 enum ContextKind { StackFrame, Scope, Block };
221
222private:
223 ContextKind Kind;
224
225 // AnalysisDeclContext can't be const since some methods may modify its
226 // member.
227 AnalysisDeclContext *Ctx;
228
229 const LocationContext *Parent;
230 int64_t ID;
231
232protected:
233 LocationContext(ContextKind k, AnalysisDeclContext *ctx,
234 const LocationContext *parent,
235 int64_t ID)
236 : Kind(k), Ctx(ctx), Parent(parent), ID(ID) {}
237
238public:
239 virtual ~LocationContext();
240
241 ContextKind getKind() const { return Kind; }
242
243 int64_t getID() const {
244 return ID;
245 }
246
247 AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; }
248
249 const LocationContext *getParent() const { return Parent; }
250
251 bool isParentOf(const LocationContext *LC) const;
252
253 const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); }
254
255 CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); }
256
257 template <typename T>
258 T *getAnalysis() const {
259 return getAnalysisDeclContext()->getAnalysis<T>();
260 }
261
262 ParentMap &getParentMap() const {
263 return getAnalysisDeclContext()->getParentMap();
264 }
265
266 const ImplicitParamDecl *getSelfDecl() const {
267 return Ctx->getSelfDecl();
268 }
269
270 const StackFrameContext *getStackFrame() const;
271
272 /// Return true if the current LocationContext has no caller context.
273 virtual bool inTopFrame() const;
274
275 virtual void Profile(llvm::FoldingSetNodeID &ID) = 0;
276
277 void dumpStack(
278 raw_ostream &OS, StringRef Indent = {}, const char *NL = "\n",
279 const char *Sep = "",
280 std::function<void(const LocationContext *)> printMoreInfoPerContext =
281 [](const LocationContext *) {}) const;
282 void dumpStack() const;
283
284public:
285 static void ProfileCommon(llvm::FoldingSetNodeID &ID,
286 ContextKind ck,
287 AnalysisDeclContext *ctx,
288 const LocationContext *parent,
289 const void *data);
290};
291
292class StackFrameContext : public LocationContext {
293 friend class LocationContextManager;
294
295 // The callsite where this stack frame is established.
296 const Stmt *CallSite;
297
298 // The parent block of the callsite.
299 const CFGBlock *Block;
300
301 // The index of the callsite in the CFGBlock.
302 unsigned Index;
303
304 StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent,
305 const Stmt *s, const CFGBlock *blk,
306 unsigned idx,
307 int64_t ID)
308 : LocationContext(StackFrame, ctx, parent, ID), CallSite(s),
309 Block(blk), Index(idx) {}
310
311public:
312 ~StackFrameContext() override = default;
313
314 const Stmt *getCallSite() const { return CallSite; }
315
316 const CFGBlock *getCallSiteBlock() const { return Block; }
317
318 /// Return true if the current LocationContext has no caller context.
319 bool inTopFrame() const override { return getParent() == nullptr; }
320
321 unsigned getIndex() const { return Index; }
322
323 void Profile(llvm::FoldingSetNodeID &ID) override;
324
325 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
326 const LocationContext *parent, const Stmt *s,
327 const CFGBlock *blk, unsigned idx) {
328 ProfileCommon(ID, StackFrame, ctx, parent, s);
329 ID.AddPointer(blk);
330 ID.AddInteger(idx);
331 }
332
333 static bool classof(const LocationContext *Ctx) {
334 return Ctx->getKind() == StackFrame;
335 }
336};
337
338class ScopeContext : public LocationContext {
339 friend class LocationContextManager;
340
341 const Stmt *Enter;
342
343 ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent,
344 const Stmt *s, int64_t ID)
345 : LocationContext(Scope, ctx, parent, ID), Enter(s) {}
346
347public:
348 ~ScopeContext() override = default;
349
350 void Profile(llvm::FoldingSetNodeID &ID) override;
351
352 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
353 const LocationContext *parent, const Stmt *s) {
354 ProfileCommon(ID, Scope, ctx, parent, s);
355 }
356
357 static bool classof(const LocationContext *Ctx) {
358 return Ctx->getKind() == Scope;
359 }
360};
361
362class BlockInvocationContext : public LocationContext {
363 friend class LocationContextManager;
364
365 const BlockDecl *BD;
366
367 // FIXME: Come up with a more type-safe way to model context-sensitivity.
368 const void *ContextData;
369
370 BlockInvocationContext(AnalysisDeclContext *ctx,
371 const LocationContext *parent, const BlockDecl *bd,
372 const void *contextData, int64_t ID)
373 : LocationContext(Block, ctx, parent, ID), BD(bd),
374 ContextData(contextData) {}
375
376public:
377 ~BlockInvocationContext() override = default;
378
379 const BlockDecl *getBlockDecl() const { return BD; }
380
381 const void *getContextData() const { return ContextData; }
382
383 void Profile(llvm::FoldingSetNodeID &ID) override;
384
385 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx,
386 const LocationContext *parent, const BlockDecl *bd,
387 const void *contextData) {
388 ProfileCommon(ID, Block, ctx, parent, bd);
389 ID.AddPointer(contextData);
390 }
391
392 static bool classof(const LocationContext *Ctx) {
393 return Ctx->getKind() == Block;
394 }
395};
396
397class LocationContextManager {
398 llvm::FoldingSet<LocationContext> Contexts;
399
400 /// ID used for generating a new location context.
401 int64_t NewID = 0;
402
403public:
404 ~LocationContextManager();
405
406 const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx,
407 const LocationContext *parent,
408 const Stmt *s,
409 const CFGBlock *blk, unsigned idx);
410
411 const ScopeContext *getScope(AnalysisDeclContext *ctx,
412 const LocationContext *parent,
413 const Stmt *s);
414
415 const BlockInvocationContext *
416 getBlockInvocationContext(AnalysisDeclContext *ctx,
417 const LocationContext *parent,
418 const BlockDecl *BD,
419 const void *ContextData);
420
421 /// Discard all previously created LocationContext objects.
422 void clear();
423private:
424 template <typename LOC, typename DATA>
425 const LOC *getLocationContext(AnalysisDeclContext *ctx,
426 const LocationContext *parent,
427 const DATA *d);
428};
429
430class AnalysisDeclContextManager {
431 using ContextMap =
432 llvm::DenseMap<const Decl *, std::unique_ptr<AnalysisDeclContext>>;
433
434 ContextMap Contexts;
435 LocationContextManager LocContexts;
436 CFG::BuildOptions cfgBuildOptions;
437
438 /// Pointer to an interface that can provide function bodies for
439 /// declarations from external source.
440 std::unique_ptr<CodeInjector> Injector;
441
442 /// A factory for creating and caching implementations for common
443 /// methods during the analysis.
444 BodyFarm FunctionBodyFarm;
445
446 /// Flag to indicate whether or not bodies should be synthesized
447 /// for well-known functions.
448 bool SynthesizeBodies;
449
450public:
451 AnalysisDeclContextManager(ASTContext &ASTCtx, bool useUnoptimizedCFG = false,
452 bool addImplicitDtors = false,
453 bool addInitializers = false,
454 bool addTemporaryDtors = false,
455 bool addLifetime = false,
456 bool addLoopExit = false,
457 bool addScopes = false,
458 bool synthesizeBodies = false,
459 bool addStaticInitBranches = false,
460 bool addCXXNewAllocator = true,
461 bool addRichCXXConstructors = true,
462 bool markElidedCXXConstructors = true,
463 CodeInjector *injector = nullptr);
464
465 AnalysisDeclContext *getContext(const Decl *D);
466
467 bool getUseUnoptimizedCFG() const {
468 return !cfgBuildOptions.PruneTriviallyFalseEdges;
469 }
470
471 CFG::BuildOptions &getCFGBuildOptions() {
472 return cfgBuildOptions;
473 }
474
475 /// Return true if faux bodies should be synthesized for well-known
476 /// functions.
477 bool synthesizeBodies() const { return SynthesizeBodies; }
478
479 const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx,
480 LocationContext const *Parent,
481 const Stmt *S,
482 const CFGBlock *Blk,
483 unsigned Idx) {
484 return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx);
485 }
486
487 // Get the top level stack frame.
488 const StackFrameContext *getStackFrame(const Decl *D) {
489 return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr,
490 0);
491 }
492
493 // Get a stack frame with parent.
494 StackFrameContext const *getStackFrame(const Decl *D,
495 LocationContext const *Parent,
496 const Stmt *S,
497 const CFGBlock *Blk,
498 unsigned Idx) {
499 return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx);
500 }
501
502 /// Get a reference to {@code BodyFarm} instance.
503 BodyFarm &getBodyFarm();
504
505 /// Discard all previously created AnalysisDeclContexts.
506 void clear();
507
508private:
509 friend class AnalysisDeclContext;
510
511 LocationContextManager &getLocationContextManager() {
512 return LocContexts;
513 }
514};
515
516} // namespace clang
517
518#endif // LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H
519