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