1 | //===- PtrUseVisitor.h - InstVisitors over a pointers uses ------*- 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 provides a collection of visitors which walk the (instruction) |
11 | /// uses of a pointer. These visitors all provide the same essential behavior |
12 | /// as an InstVisitor with similar template-based flexibility and |
13 | /// implementation strategies. |
14 | /// |
15 | /// These can be used, for example, to quickly analyze the uses of an alloca, |
16 | /// global variable, or function argument. |
17 | /// |
18 | /// FIXME: Provide a variant which doesn't track offsets and is cheaper. |
19 | // |
20 | //===----------------------------------------------------------------------===// |
21 | |
22 | #ifndef LLVM_ANALYSIS_PTRUSEVISITOR_H |
23 | #define LLVM_ANALYSIS_PTRUSEVISITOR_H |
24 | |
25 | #include "llvm/ADT/APInt.h" |
26 | #include "llvm/ADT/PointerIntPair.h" |
27 | #include "llvm/ADT/SmallPtrSet.h" |
28 | #include "llvm/ADT/SmallVector.h" |
29 | #include "llvm/IR/DerivedTypes.h" |
30 | #include "llvm/IR/InstVisitor.h" |
31 | #include "llvm/IR/IntrinsicInst.h" |
32 | #include <cassert> |
33 | #include <type_traits> |
34 | |
35 | namespace llvm { |
36 | class DataLayout; |
37 | class Use; |
38 | |
39 | namespace detail { |
40 | |
41 | /// Implementation of non-dependent functionality for \c PtrUseVisitor. |
42 | /// |
43 | /// See \c PtrUseVisitor for the public interface and detailed comments about |
44 | /// usage. This class is just a helper base class which is not templated and |
45 | /// contains all common code to be shared between different instantiations of |
46 | /// PtrUseVisitor. |
47 | class PtrUseVisitorBase { |
48 | public: |
49 | /// This class provides information about the result of a visit. |
50 | /// |
51 | /// After walking all the users (recursively) of a pointer, the basic |
52 | /// infrastructure records some commonly useful information such as escape |
53 | /// analysis and whether the visit completed or aborted early. |
54 | class PtrInfo { |
55 | public: |
56 | PtrInfo() : AbortedInfo(nullptr, false), EscapedInfo(nullptr, false) {} |
57 | |
58 | /// Reset the pointer info, clearing all state. |
59 | void reset() { |
60 | AbortedInfo.setPointer(nullptr); |
61 | AbortedInfo.setInt(false); |
62 | EscapedInfo.setPointer(nullptr); |
63 | EscapedInfo.setInt(false); |
64 | } |
65 | |
66 | /// Did we abort the visit early? |
67 | bool isAborted() const { return AbortedInfo.getInt(); } |
68 | |
69 | /// Is the pointer escaped at some point? |
70 | bool isEscaped() const { return EscapedInfo.getInt(); } |
71 | |
72 | /// Get the instruction causing the visit to abort. |
73 | /// \returns a pointer to the instruction causing the abort if one is |
74 | /// available; otherwise returns null. |
75 | Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); } |
76 | |
77 | /// Get the instruction causing the pointer to escape. |
78 | /// \returns a pointer to the instruction which escapes the pointer if one |
79 | /// is available; otherwise returns null. |
80 | Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); } |
81 | |
82 | /// Mark the visit as aborted. Intended for use in a void return. |
83 | /// \param I The instruction which caused the visit to abort, if available. |
84 | void setAborted(Instruction *I = nullptr) { |
85 | AbortedInfo.setInt(true); |
86 | AbortedInfo.setPointer(I); |
87 | } |
88 | |
89 | /// Mark the pointer as escaped. Intended for use in a void return. |
90 | /// \param I The instruction which escapes the pointer, if available. |
91 | void setEscaped(Instruction *I = nullptr) { |
92 | EscapedInfo.setInt(true); |
93 | EscapedInfo.setPointer(I); |
94 | } |
95 | |
96 | /// Mark the pointer as escaped, and the visit as aborted. Intended |
97 | /// for use in a void return. |
98 | /// \param I The instruction which both escapes the pointer and aborts the |
99 | /// visit, if available. |
100 | void setEscapedAndAborted(Instruction *I = nullptr) { |
101 | setEscaped(I); |
102 | setAborted(I); |
103 | } |
104 | |
105 | private: |
106 | PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo; |
107 | }; |
108 | |
109 | protected: |
110 | const DataLayout &DL; |
111 | |
112 | /// \name Visitation infrastructure |
113 | /// @{ |
114 | |
115 | /// The info collected about the pointer being visited thus far. |
116 | PtrInfo PI; |
117 | |
118 | /// A struct of the data needed to visit a particular use. |
119 | /// |
120 | /// This is used to maintain a worklist fo to-visit uses. This is used to |
121 | /// make the visit be iterative rather than recursive. |
122 | struct UseToVisit { |
123 | using UseAndIsOffsetKnownPair = PointerIntPair<Use *, 1, bool>; |
124 | |
125 | UseAndIsOffsetKnownPair UseAndIsOffsetKnown; |
126 | APInt Offset; |
127 | }; |
128 | |
129 | /// The worklist of to-visit uses. |
130 | SmallVector<UseToVisit, 8> Worklist; |
131 | |
132 | /// A set of visited uses to break cycles in unreachable code. |
133 | SmallPtrSet<Use *, 8> VisitedUses; |
134 | |
135 | /// @} |
136 | |
137 | /// \name Per-visit state |
138 | /// This state is reset for each instruction visited. |
139 | /// @{ |
140 | |
141 | /// The use currently being visited. |
142 | Use *U; |
143 | |
144 | /// True if we have a known constant offset for the use currently |
145 | /// being visited. |
146 | bool IsOffsetKnown; |
147 | |
148 | /// The constant offset of the use if that is known. |
149 | APInt Offset; |
150 | |
151 | /// @} |
152 | |
153 | /// Note that the constructor is protected because this class must be a base |
154 | /// class, we can't create instances directly of this class. |
155 | PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {} |
156 | |
157 | /// Enqueue the users of this instruction in the visit worklist. |
158 | /// |
159 | /// This will visit the users with the same offset of the current visit |
160 | /// (including an unknown offset if that is the current state). |
161 | void enqueueUsers(Instruction &I); |
162 | |
163 | /// Walk the operands of a GEP and adjust the offset as appropriate. |
164 | /// |
165 | /// This routine does the heavy lifting of the pointer walk by computing |
166 | /// offsets and looking through GEPs. |
167 | bool adjustOffsetForGEP(GetElementPtrInst &GEPI); |
168 | }; |
169 | |
170 | } // end namespace detail |
171 | |
172 | /// A base class for visitors over the uses of a pointer value. |
173 | /// |
174 | /// Once constructed, a user can call \c visit on a pointer value, and this |
175 | /// will walk its uses and visit each instruction using an InstVisitor. It also |
176 | /// provides visit methods which will recurse through any pointer-to-pointer |
177 | /// transformations such as GEPs and bitcasts. |
178 | /// |
179 | /// During the visit, the current Use* being visited is available to the |
180 | /// subclass, as well as the current offset from the original base pointer if |
181 | /// known. |
182 | /// |
183 | /// The recursive visit of uses is accomplished with a worklist, so the only |
184 | /// ordering guarantee is that an instruction is visited before any uses of it |
185 | /// are visited. Note that this does *not* mean before any of its users are |
186 | /// visited! This is because users can be visited multiple times due to |
187 | /// multiple, different uses of pointers derived from the same base. |
188 | /// |
189 | /// A particular Use will only be visited once, but a User may be visited |
190 | /// multiple times, once per Use. This visits may notably have different |
191 | /// offsets. |
192 | /// |
193 | /// All visit methods on the underlying InstVisitor return a boolean. This |
194 | /// return short-circuits the visit, stopping it immediately. |
195 | /// |
196 | /// FIXME: Generalize this for all values rather than just instructions. |
197 | template <typename DerivedT> |
198 | class PtrUseVisitor : protected InstVisitor<DerivedT>, |
199 | public detail::PtrUseVisitorBase { |
200 | friend class InstVisitor<DerivedT>; |
201 | |
202 | using Base = InstVisitor<DerivedT>; |
203 | |
204 | public: |
205 | PtrUseVisitor(const DataLayout &DL) : PtrUseVisitorBase(DL) { |
206 | static_assert(std::is_base_of<PtrUseVisitor, DerivedT>::value, |
207 | "Must pass the derived type to this template!" ); |
208 | } |
209 | |
210 | /// Recursively visit the uses of the given pointer. |
211 | /// \returns An info struct about the pointer. See \c PtrInfo for details. |
212 | PtrInfo visitPtr(Instruction &I) { |
213 | // This must be a pointer type. Get an integer type suitable to hold |
214 | // offsets on this pointer. |
215 | // FIXME: Support a vector of pointers. |
216 | assert(I.getType()->isPointerTy()); |
217 | IntegerType *IntIdxTy = cast<IntegerType>(DL.getIndexType(I.getType())); |
218 | IsOffsetKnown = true; |
219 | Offset = APInt(IntIdxTy->getBitWidth(), 0); |
220 | PI.reset(); |
221 | |
222 | // Enqueue the uses of this pointer. |
223 | enqueueUsers(I); |
224 | |
225 | // Visit all the uses off the worklist until it is empty. |
226 | while (!Worklist.empty()) { |
227 | UseToVisit ToVisit = Worklist.pop_back_val(); |
228 | U = ToVisit.UseAndIsOffsetKnown.getPointer(); |
229 | IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt(); |
230 | if (IsOffsetKnown) |
231 | Offset = std::move(ToVisit.Offset); |
232 | |
233 | Instruction *I = cast<Instruction>(Val: U->getUser()); |
234 | static_cast<DerivedT*>(this)->visit(I); |
235 | if (PI.isAborted()) |
236 | break; |
237 | } |
238 | return PI; |
239 | } |
240 | |
241 | protected: |
242 | void visitStoreInst(StoreInst &SI) { |
243 | if (SI.getValueOperand() == U->get()) |
244 | PI.setEscaped(&SI); |
245 | } |
246 | |
247 | void visitBitCastInst(BitCastInst &BC) { |
248 | enqueueUsers(I&: BC); |
249 | } |
250 | |
251 | void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) { |
252 | enqueueUsers(I&: ASC); |
253 | } |
254 | |
255 | void visitPtrToIntInst(PtrToIntInst &I) { |
256 | PI.setEscaped(&I); |
257 | } |
258 | |
259 | void visitGetElementPtrInst(GetElementPtrInst &GEPI) { |
260 | if (GEPI.use_empty()) |
261 | return; |
262 | |
263 | // If we can't walk the GEP, clear the offset. |
264 | if (!adjustOffsetForGEP(GEPI)) { |
265 | IsOffsetKnown = false; |
266 | Offset = APInt(); |
267 | } |
268 | |
269 | // Enqueue the users now that the offset has been adjusted. |
270 | enqueueUsers(I&: GEPI); |
271 | } |
272 | |
273 | // No-op intrinsics which we know don't escape the pointer to logic in |
274 | // some other function. |
275 | void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {} |
276 | void visitMemIntrinsic(MemIntrinsic &I) {} |
277 | void visitIntrinsicInst(IntrinsicInst &II) { |
278 | switch (II.getIntrinsicID()) { |
279 | default: |
280 | return Base::visitIntrinsicInst(II); |
281 | |
282 | case Intrinsic::lifetime_start: |
283 | case Intrinsic::lifetime_end: |
284 | return; // No-op intrinsics. |
285 | } |
286 | } |
287 | |
288 | // Generically, arguments to calls and invokes escape the pointer to some |
289 | // other function. Mark that. |
290 | void visitCallBase(CallBase &CB) { |
291 | PI.setEscaped(&CB); |
292 | Base::visitCallBase(CB); |
293 | } |
294 | }; |
295 | |
296 | } // end namespace llvm |
297 | |
298 | #endif // LLVM_ANALYSIS_PTRUSEVISITOR_H |
299 | |