1 | //===----- llvm/Analysis/CaptureTracking.h - Pointer capture ----*- 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 contains routines that help determine which pointers are captured. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_ANALYSIS_CAPTURETRACKING_H |
14 | #define LLVM_ANALYSIS_CAPTURETRACKING_H |
15 | |
16 | #include "llvm/ADT/DenseMap.h" |
17 | #include "llvm/ADT/STLFunctionalExtras.h" |
18 | |
19 | namespace llvm { |
20 | |
21 | class Value; |
22 | class Use; |
23 | class DataLayout; |
24 | class Instruction; |
25 | class DominatorTree; |
26 | class LoopInfo; |
27 | class Function; |
28 | |
29 | /// getDefaultMaxUsesToExploreForCaptureTracking - Return default value of |
30 | /// the maximal number of uses to explore before giving up. It is used by |
31 | /// PointerMayBeCaptured family analysis. |
32 | unsigned getDefaultMaxUsesToExploreForCaptureTracking(); |
33 | |
34 | /// PointerMayBeCaptured - Return true if this pointer value may be captured |
35 | /// by the enclosing function (which is required to exist). This routine can |
36 | /// be expensive, so consider caching the results. The boolean ReturnCaptures |
37 | /// specifies whether returning the value (or part of it) from the function |
38 | /// counts as capturing it or not. The boolean StoreCaptures specified |
39 | /// whether storing the value (or part of it) into memory anywhere |
40 | /// automatically counts as capturing it or not. |
41 | /// MaxUsesToExplore specifies how many uses the analysis should explore for |
42 | /// one value before giving up due too "too many uses". If MaxUsesToExplore |
43 | /// is zero, a default value is assumed. |
44 | bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, |
45 | bool StoreCaptures, unsigned MaxUsesToExplore = 0); |
46 | |
47 | /// PointerMayBeCapturedBefore - Return true if this pointer value may be |
48 | /// captured by the enclosing function (which is required to exist). If a |
49 | /// DominatorTree is provided, only captures which happen before the given |
50 | /// instruction are considered. This routine can be expensive, so consider |
51 | /// caching the results. The boolean ReturnCaptures specifies whether |
52 | /// returning the value (or part of it) from the function counts as capturing |
53 | /// it or not. The boolean StoreCaptures specified whether storing the value |
54 | /// (or part of it) into memory anywhere automatically counts as capturing it |
55 | /// or not. Captures by the provided instruction are considered if the |
56 | /// final parameter is true. |
57 | /// MaxUsesToExplore specifies how many uses the analysis should explore for |
58 | /// one value before giving up due too "too many uses". If MaxUsesToExplore |
59 | /// is zero, a default value is assumed. |
60 | bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, |
61 | bool StoreCaptures, const Instruction *I, |
62 | const DominatorTree *DT, |
63 | bool IncludeI = false, |
64 | unsigned MaxUsesToExplore = 0, |
65 | const LoopInfo *LI = nullptr); |
66 | |
67 | // Returns the 'earliest' instruction that captures \p V in \F. An instruction |
68 | // A is considered earlier than instruction B, if A dominates B. If 2 escapes |
69 | // do not dominate each other, the terminator of the common dominator is |
70 | // chosen. If not all uses can be analyzed, the earliest escape is set to |
71 | // the first instruction in the function entry block. If \p V does not escape, |
72 | // nullptr is returned. Note that the caller of the function has to ensure |
73 | // that the instruction the result value is compared against is not in a |
74 | // cycle. |
75 | Instruction *FindEarliestCapture(const Value *V, Function &F, |
76 | bool ReturnCaptures, bool StoreCaptures, |
77 | const DominatorTree &DT, |
78 | unsigned MaxUsesToExplore = 0); |
79 | |
80 | /// This callback is used in conjunction with PointerMayBeCaptured. In |
81 | /// addition to the interface here, you'll need to provide your own getters |
82 | /// to see whether anything was captured. |
83 | struct CaptureTracker { |
84 | virtual ~CaptureTracker(); |
85 | |
86 | /// tooManyUses - The depth of traversal has breached a limit. There may be |
87 | /// capturing instructions that will not be passed into captured(). |
88 | virtual void tooManyUses() = 0; |
89 | |
90 | /// shouldExplore - This is the use of a value derived from the pointer. |
91 | /// To prune the search (ie., assume that none of its users could possibly |
92 | /// capture) return false. To search it, return true. |
93 | /// |
94 | /// U->getUser() is always an Instruction. |
95 | virtual bool shouldExplore(const Use *U); |
96 | |
97 | /// captured - Information about the pointer was captured by the user of |
98 | /// use U. Return true to stop the traversal or false to continue looking |
99 | /// for more capturing instructions. |
100 | virtual bool captured(const Use *U) = 0; |
101 | |
102 | /// isDereferenceableOrNull - Overload to allow clients with additional |
103 | /// knowledge about pointer dereferenceability to provide it and thereby |
104 | /// avoid conservative responses when a pointer is compared to null. |
105 | virtual bool isDereferenceableOrNull(Value *O, const DataLayout &DL); |
106 | }; |
107 | |
108 | /// Types of use capture kinds, see \p DetermineUseCaptureKind. |
109 | enum class UseCaptureKind { |
110 | NO_CAPTURE, |
111 | MAY_CAPTURE, |
112 | PASSTHROUGH, |
113 | }; |
114 | |
115 | /// Determine what kind of capture behaviour \p U may exhibit. |
116 | /// |
117 | /// A use can be no-capture, a use can potentially capture, or a use can be |
118 | /// passthrough such that the uses of the user or \p U should be inspected. |
119 | /// The \p IsDereferenceableOrNull callback is used to rule out capturing for |
120 | /// certain comparisons. |
121 | UseCaptureKind |
122 | DetermineUseCaptureKind(const Use &U, |
123 | llvm::function_ref<bool(Value *, const DataLayout &)> |
124 | IsDereferenceableOrNull); |
125 | |
126 | /// PointerMayBeCaptured - Visit the value and the values derived from it and |
127 | /// find values which appear to be capturing the pointer value. This feeds |
128 | /// results into and is controlled by the CaptureTracker object. |
129 | /// MaxUsesToExplore specifies how many uses the analysis should explore for |
130 | /// one value before giving up due too "too many uses". If MaxUsesToExplore |
131 | /// is zero, a default value is assumed. |
132 | void PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker, |
133 | unsigned MaxUsesToExplore = 0); |
134 | |
135 | /// Returns true if the pointer is to a function-local object that never |
136 | /// escapes from the function. |
137 | bool isNonEscapingLocalObject( |
138 | const Value *V, |
139 | SmallDenseMap<const Value *, bool, 8> *IsCapturedCache = nullptr); |
140 | } // end namespace llvm |
141 | |
142 | #endif |
143 | |