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 ManagedAnalysis *&data = getAnalysisImpl(tag);
195 if (!data) {
196 data = T::create(*this);
197 }
198 return static_cast<T *>(data);
199 }
200
201 /// \returns Whether the root namespace of \p D is the \c std C++ namespace.
202 static bool isInStdNamespace(const Decl *D);
203
204private:
205 ManagedAnalysis *&getAnalysisImpl(const void *tag);
206
207 LocationContextManager &getLocationContextManager();
208};
209
210/// It wraps the AnalysisDeclContext to represent both the call stack with
211/// the help of StackFrameContext and inside the function calls the
212/// BlockInvocationContext. It is needed for context sensitive analysis to
213/// model entering, leaving or inlining function calls.
214class LocationContext : public llvm::FoldingSetNode {
215public:
216 enum ContextKind { StackFrame, Block };
217
218private:
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 int64_t ID;
227
228protected:
229 LocationContext(ContextKind k, AnalysisDeclContext *ctx,
230 const LocationContext *parent, int64_t ID)
231 : Kind(k), Ctx(ctx), Parent(parent), ID(ID) {}
232
233public:
234 virtual ~LocationContext();
235
236 ContextKind getKind() const { return Kind; }
237
238 int64_t getID() const { return ID; }
239
240 AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; }
241
242 const LocationContext *getParent() const { return Parent; }
243
244 bool isParentOf(const LocationContext *LC) const;
245
246 const Decl *getDecl() const { return Ctx->getDecl(); }
247
248 CFG *getCFG() const { return Ctx->getCFG(); }
249
250 template <typename T> T *getAnalysis() const { return Ctx->getAnalysis<T>(); }
251
252 const ParentMap &getParentMap() const { return Ctx->getParentMap(); }
253
254 /// \copydoc AnalysisDeclContext::getSelfDecl()
255 const ImplicitParamDecl *getSelfDecl() const { return Ctx->getSelfDecl(); }
256
257 const StackFrameContext *getStackFrame() const;
258
259 /// \returns Whether the current LocationContext has no caller context.
260 virtual bool inTopFrame() const;
261
262 virtual void Profile(llvm::FoldingSetNodeID &ID) = 0;
263
264 /// Prints out the call stack.
265 ///
266 /// \param Out The out stream.
267 LLVM_DUMP_METHOD void dumpStack(raw_ostream &Out) const;
268
269 /// Prints out the call stack in \c json format.
270 ///
271 /// \param Out The out stream.
272 /// \param NL The newline.
273 /// \param Space The space count for indentation.
274 /// \param IsDot Whether the output format is \c dot.
275 /// \param printMoreInfoPerContext
276 /// A callback to print more information for each context, for example:
277 /// \code
278 /// [&](const LocationContext *LC) { LC->dump(); }
279 /// \endcode
280 void printJson(
281 raw_ostream &Out, const char *NL = "\n", unsigned int Space = 0,
282 bool IsDot = false,
283 std::function<void(const LocationContext *)> printMoreInfoPerContext =
284 [](const LocationContext *) {}) const;
285
286 LLVM_DUMP_METHOD void dump() const;
287
288 static void ProfileCommon(llvm::FoldingSetNodeID &ID, ContextKind ck,
289 AnalysisDeclContext *ctx,
290 const LocationContext *parent, const void *data);
291};
292
293/// It represents a stack frame of the call stack (based on CallEvent).
294class StackFrameContext : public LocationContext {
295 friend class LocationContextManager;
296
297 // The call site where this stack frame is established.
298 const Stmt *CallSite;
299
300 // The parent block of the call site.
301 const CFGBlock *Block;
302
303 // The number of times the 'Block' has been visited.
304 // It allows discriminating between stack frames of the same call that is
305 // called multiple times in a loop.
306 const unsigned BlockCount;
307
308 // The index of the call site in the CFGBlock.
309 const unsigned Index;
310
311 StackFrameContext(AnalysisDeclContext *ADC, const LocationContext *ParentLC,
312 const Stmt *S, const CFGBlock *Block, unsigned BlockCount,
313 unsigned Index, int64_t ID)
314 : LocationContext(StackFrame, ADC, ParentLC, ID), CallSite(S),
315 Block(Block), BlockCount(BlockCount), Index(Index) {}
316
317public:
318 ~StackFrameContext() override = default;
319
320 const Stmt *getCallSite() const { return CallSite; }
321
322 const CFGBlock *getCallSiteBlock() const { return Block; }
323
324 bool inTopFrame() const override { return getParent() == nullptr; }
325
326 unsigned getIndex() const { return Index; }
327
328 void Profile(llvm::FoldingSetNodeID &ID) override;
329
330 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ADC,
331 const LocationContext *ParentLC, const Stmt *S,
332 const CFGBlock *Block, unsigned BlockCount,
333 unsigned Index) {
334 ProfileCommon(ID, StackFrame, ADC, ParentLC, S);
335 ID.AddPointer(Block);
336 ID.AddInteger(BlockCount);
337 ID.AddInteger(Index);
338 }
339
340 static bool classof(const LocationContext *LC) {
341 return LC->getKind() == StackFrame;
342 }
343};
344
345/// It represents a block invocation (based on BlockCall).
346class BlockInvocationContext : public LocationContext {
347 friend class LocationContextManager;
348
349 const BlockDecl *BD;
350
351 // FIXME: Come up with a more type-safe way to model context-sensitivity.
352 const void *Data;
353
354 BlockInvocationContext(AnalysisDeclContext *ADC,
355 const LocationContext *ParentLC, const BlockDecl *BD,
356 const void *Data, int64_t ID)
357 : LocationContext(Block, ADC, ParentLC, ID), BD(BD), Data(Data) {}
358
359public:
360 ~BlockInvocationContext() override = default;
361
362 const BlockDecl *getBlockDecl() const { return BD; }
363
364 const void *getData() const { return Data; }
365
366 void Profile(llvm::FoldingSetNodeID &ID) override;
367
368 static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ADC,
369 const LocationContext *ParentLC, const BlockDecl *BD,
370 const void *Data) {
371 ProfileCommon(ID, Block, ADC, ParentLC, BD);
372 ID.AddPointer(Data);
373 }
374
375 static bool classof(const LocationContext *LC) {
376 return LC->getKind() == Block;
377 }
378};
379
380class LocationContextManager {
381 llvm::FoldingSet<LocationContext> Contexts;
382
383 // ID used for generating a new location context.
384 int64_t NewID = 0;
385
386public:
387 ~LocationContextManager();
388
389 /// Obtain a context of the call stack using its parent context.
390 ///
391 /// \param ADC The AnalysisDeclContext.
392 /// \param ParentLC The parent context of this newly created context.
393 /// \param S The call.
394 /// \param Block The basic block.
395 /// \param BlockCount The current count of entering into \p Blk.
396 /// \param Index The index of \p Blk.
397 /// \returns The context for \p D with parent context \p ParentLC.
398 const StackFrameContext *getStackFrame(AnalysisDeclContext *ADC,
399 const LocationContext *ParentLC,
400 const Stmt *S, const CFGBlock *Block,
401 unsigned BlockCount, unsigned Index);
402
403 /// Obtain a context of the block invocation using its parent context.
404 ///
405 /// \param ADC The AnalysisDeclContext.
406 /// \param ParentLC The parent context of this newly created context.
407 /// \param BD The BlockDecl.
408 /// \param Data The raw data to store as part of the context.
409 const BlockInvocationContext *
410 getBlockInvocationContext(AnalysisDeclContext *ADC,
411 const LocationContext *ParentLC,
412 const BlockDecl *BD, const void *Data);
413
414 /// Discard all previously created LocationContext objects.
415 void clear();
416};
417
418class AnalysisDeclContextManager {
419 using ContextMap =
420 llvm::DenseMap<const Decl *, std::unique_ptr<AnalysisDeclContext>>;
421
422 ContextMap Contexts;
423 LocationContextManager LocCtxMgr;
424 CFG::BuildOptions cfgBuildOptions;
425
426 // Pointer to an interface that can provide function bodies for
427 // declarations from external source.
428 std::unique_ptr<CodeInjector> Injector;
429
430 // A factory for creating and caching implementations for common
431 // methods during the analysis.
432 BodyFarm FunctionBodyFarm;
433
434 // Flag to indicate whether or not bodies should be synthesized
435 // for well-known functions.
436 bool SynthesizeBodies;
437
438public:
439 AnalysisDeclContextManager(
440 ASTContext &ASTCtx, bool useUnoptimizedCFG = false,
441 bool addImplicitDtors = false, bool addInitializers = false,
442 bool addTemporaryDtors = false, bool addLifetime = false,
443 bool addLoopExit = false, bool addScopes = false,
444 bool synthesizeBodies = false, bool addStaticInitBranches = false,
445 bool addCXXNewAllocator = true, bool addRichCXXConstructors = true,
446 bool markElidedCXXConstructors = true, bool addVirtualBaseBranches = true,
447 CodeInjector *injector = nullptr);
448
449 AnalysisDeclContext *getContext(const Decl *D);
450
451 bool getUseUnoptimizedCFG() const {
452 return !cfgBuildOptions.PruneTriviallyFalseEdges;
453 }
454
455 CFG::BuildOptions &getCFGBuildOptions() { return cfgBuildOptions; }
456
457 /// \returns Whether faux bodies should be synthesized for known functions.
458 bool synthesizeBodies() const { return SynthesizeBodies; }
459
460 /// Obtain the beginning context of the analysis.
461 ///
462 /// \returns The top level stack frame for \p D.
463 const StackFrameContext *getStackFrame(const Decl *D) {
464 return LocCtxMgr.getStackFrame(getContext(D), nullptr, nullptr, nullptr, 0,
465 0);
466 }
467
468 /// \copydoc LocationContextManager::getStackFrame()
469 const StackFrameContext *getStackFrame(AnalysisDeclContext *ADC,
470 const LocationContext *Parent,
471 const Stmt *S, const CFGBlock *Block,
472 unsigned BlockCount, unsigned Index) {
473 return LocCtxMgr.getStackFrame(ADC, Parent, S, Block, BlockCount, Index);
474 }
475
476 BodyFarm &getBodyFarm();
477
478 /// Discard all previously created AnalysisDeclContexts.
479 void clear();
480
481private:
482 friend class AnalysisDeclContext;
483
484 LocationContextManager &getLocationContextManager() { return LocCtxMgr; }
485};
486
487} // namespace clang
488
489#endif // LLVM_CLANG_ANALYSIS_ANALYSISDECLCONTEXT_H
490