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