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