LLVM 19.0.0git
PtrUseVisitor.h
Go to the documentation of this file.
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"
30#include "llvm/IR/InstVisitor.h"
32#include <cassert>
33#include <type_traits>
34
35namespace llvm {
36class DataLayout;
37class Use;
38
39namespace 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.
48public:
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.
101 setEscaped(I);
102 setAborted(I);
103 }
104
105 private:
106 PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo;
107 };
108
109protected:
111
112 /// \name Visitation infrastructure
113 /// @{
114
115 /// The info collected about the pointer being visited thus far.
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 {
124
127 };
128
129 /// The worklist of to-visit uses.
131
132 /// A set of visited uses to break cycles in unreachable code.
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.
143
144 /// True if we have a known constant offset for the use currently
145 /// being visited.
147
148 /// The constant offset of the use if that is known.
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.
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).
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.
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.
197template <typename DerivedT>
198class PtrUseVisitor : protected InstVisitor<DerivedT>,
200 friend class InstVisitor<DerivedT>;
201
203
204public:
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.
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.
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();
230 if (IsOffsetKnown)
231 Offset = std::move(ToVisit.Offset);
232
233 Instruction *I = cast<Instruction>(U->getUser());
234 static_cast<DerivedT*>(this)->visit(I);
235 if (PI.isAborted())
236 break;
237 }
238 return PI;
239 }
240
241protected:
243 if (SI.getValueOperand() == U->get())
244 PI.setEscaped(&SI);
245 }
246
248 enqueueUsers(BC);
249 }
250
252 enqueueUsers(ASC);
253 }
254
256 PI.setEscaped(&I);
257 }
258
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(GEPI);
271 }
272
273 // No-op intrinsics which we know don't escape the pointer to logic in
274 // some other function.
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.
291 PI.setEscaped(&CB);
293 }
294};
295
296} // end namespace llvm
297
298#endif // LLVM_ANALYSIS_PTRUSEVISITOR_H
This file implements a class to represent arbitrary precision integral constant values and operations...
#define I(x, y, z)
Definition: MD5.cpp:58
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Class for arbitrary precision integers.
Definition: APInt.h:76
This class represents a conversion between pointers from one address space to another.
This class represents a no-op cast from one type to another.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1455
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
Definition: DataLayout.cpp:905
This is the common base class for debug info intrinsics.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:973
Base class for instruction visitors.
Definition: InstVisitor.h:78
void visitCallBase(CallBase &I)
Definition: InstVisitor.h:267
void visitIntrinsicInst(IntrinsicInst &I)
Definition: InstVisitor.h:219
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:87
Class to represent integer types.
Definition: DerivedTypes.h:40
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:72
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:54
This is the common base class for memset/memcpy/memmove.
PointerIntPair - This class implements a pair of a pointer and small integer.
IntType getInt() const
PointerTy getPointer() const
This class represents a cast from a pointer to an integer.
A base class for visitors over the uses of a pointer value.
void visitCallBase(CallBase &CB)
void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I)
PtrInfo visitPtr(Instruction &I)
Recursively visit the uses of the given pointer.
PtrUseVisitor(const DataLayout &DL)
void visitGetElementPtrInst(GetElementPtrInst &GEPI)
void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC)
void visitBitCastInst(BitCastInst &BC)
void visitStoreInst(StoreInst &SI)
void visitIntrinsicInst(IntrinsicInst &II)
void visitPtrToIntInst(PtrToIntInst &I)
void visitMemIntrinsic(MemIntrinsic &I)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
An instruction for storing to memory.
Definition: Instructions.h:317
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
bool use_empty() const
Definition: Value.h:344
This class provides information about the result of a visit.
Definition: PtrUseVisitor.h:54
void setEscaped(Instruction *I=nullptr)
Mark the pointer as escaped.
Definition: PtrUseVisitor.h:91
Instruction * getAbortingInst() const
Get the instruction causing the visit to abort.
Definition: PtrUseVisitor.h:75
Instruction * getEscapingInst() const
Get the instruction causing the pointer to escape.
Definition: PtrUseVisitor.h:80
bool isEscaped() const
Is the pointer escaped at some point?
Definition: PtrUseVisitor.h:70
void reset()
Reset the pointer info, clearing all state.
Definition: PtrUseVisitor.h:59
bool isAborted() const
Did we abort the visit early?
Definition: PtrUseVisitor.h:67
void setEscapedAndAborted(Instruction *I=nullptr)
Mark the pointer as escaped, and the visit as aborted.
void setAborted(Instruction *I=nullptr)
Mark the visit as aborted.
Definition: PtrUseVisitor.h:84
Implementation of non-dependent functionality for PtrUseVisitor.
Definition: PtrUseVisitor.h:47
APInt Offset
The constant offset of the use if that is known.
PtrUseVisitorBase(const DataLayout &DL)
Note that the constructor is protected because this class must be a base class, we can't create insta...
void enqueueUsers(Instruction &I)
Enqueue the users of this instruction in the visit worklist.
SmallVector< UseToVisit, 8 > Worklist
The worklist of to-visit uses.
bool IsOffsetKnown
True if we have a known constant offset for the use currently being visited.
bool adjustOffsetForGEP(GetElementPtrInst &GEPI)
Walk the operands of a GEP and adjust the offset as appropriate.
PtrInfo PI
The info collected about the pointer being visited thus far.
Use * U
The use currently being visited.
SmallPtrSet< Use *, 8 > VisitedUses
A set of visited uses to break cycles in unreachable code.
NodeAddr< UseNode * > Use
Definition: RDFGraph.h:385
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A struct of the data needed to visit a particular use.