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