1 //===- PtrUseVisitor.h - InstVisitors over a pointers uses ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
16 /// These can be used, for example, to quickly analyze the uses of an alloca,
17 /// global variable, or function argument.
19 /// FIXME: Provide a variant which doesn't track offsets and is cheaper.
21 //===----------------------------------------------------------------------===//
23 #ifndef LLVM_ANALYSIS_PTRUSEVISITOR_H
24 #define LLVM_ANALYSIS_PTRUSEVISITOR_H
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"
44 #include <type_traits>
50 /// \brief Implementation of non-dependent functionality for \c PtrUseVisitor.
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
56 class PtrUseVisitorBase {
58 /// \brief This class provides information about the result of a visit.
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.
65 PtrInfo() : AbortedInfo(nullptr, false), EscapedInfo(nullptr, false) {}
67 /// \brief Reset the pointer info, clearing all state.
69 AbortedInfo.setPointer(nullptr);
70 AbortedInfo.setInt(false);
71 EscapedInfo.setPointer(nullptr);
72 EscapedInfo.setInt(false);
75 /// \brief Did we abort the visit early?
76 bool isAborted() const { return AbortedInfo.getInt(); }
78 /// \brief Is the pointer escaped at some point?
79 bool isEscaped() const { return EscapedInfo.getInt(); }
81 /// \brief 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(); }
86 /// \brief 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(); }
91 /// \brief 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);
98 /// \brief 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);
105 /// \brief 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) {
115 PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo;
119 const DataLayout &DL;
121 /// \name Visitation infrastructure
124 /// \brief The info collected about the pointer being visited thus far.
127 /// \brief A struct of the data needed to visit a particular use.
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.
132 using UseAndIsOffsetKnownPair = PointerIntPair<Use *, 1, bool>;
134 UseAndIsOffsetKnownPair UseAndIsOffsetKnown;
138 /// \brief The worklist of to-visit uses.
139 SmallVector<UseToVisit, 8> Worklist;
141 /// \brief A set of visited uses to break cycles in unreachable code.
142 SmallPtrSet<Use *, 8> VisitedUses;
146 /// \name Per-visit state
147 /// This state is reset for each instruction visited.
150 /// \brief The use currently being visited.
153 /// \brief True if we have a known constant offset for the use currently
157 /// \brief The constant offset of the use if that is known.
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 PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {}
166 /// \brief Enqueue the users of this instruction in the visit worklist.
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);
172 /// \brief Walk the operands of a GEP and adjust the offset as appropriate.
174 /// This routine does the heavy lifting of the pointer walk by computing
175 /// offsets and looking through GEPs.
176 bool adjustOffsetForGEP(GetElementPtrInst &GEPI);
179 } // end namespace detail
181 /// \brief A base class for visitors over the uses of a pointer value.
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.
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
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.
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
202 /// All visit methods on the underlying InstVisitor return a boolean. This
203 /// return short-circuits the visit, stopping it immediately.
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>;
211 using Base = InstVisitor<DerivedT>;
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!");
219 /// \brief Recursively visit the uses of the given pointer.
220 /// \returns An info struct about the pointer. See \c PtrInfo for details.
221 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 IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType()));
227 IsOffsetKnown = true;
228 Offset = APInt(IntPtrTy->getBitWidth(), 0);
231 // Enqueue the uses of this pointer.
234 // Visit all the uses off the worklist until it is empty.
235 while (!Worklist.empty()) {
236 UseToVisit ToVisit = Worklist.pop_back_val();
237 U = ToVisit.UseAndIsOffsetKnown.getPointer();
238 IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt();
240 Offset = std::move(ToVisit.Offset);
242 Instruction *I = cast<Instruction>(U->getUser());
243 static_cast<DerivedT*>(this)->visit(I);
251 void visitStoreInst(StoreInst &SI) {
252 if (SI.getValueOperand() == U->get())
256 void visitBitCastInst(BitCastInst &BC) {
260 void visitPtrToIntInst(PtrToIntInst &I) {
264 void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
265 if (GEPI.use_empty())
268 // If we can't walk the GEP, clear the offset.
269 if (!adjustOffsetForGEP(GEPI)) {
270 IsOffsetKnown = false;
274 // Enqueue the users now that the offset has been adjusted.
278 // No-op intrinsics which we know don't escape the pointer to to logic in
279 // some other function.
280 void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {}
281 void visitMemIntrinsic(MemIntrinsic &I) {}
282 void visitIntrinsicInst(IntrinsicInst &II) {
283 switch (II.getIntrinsicID()) {
285 return Base::visitIntrinsicInst(II);
287 case Intrinsic::lifetime_start:
288 case Intrinsic::lifetime_end:
289 return; // No-op intrinsics.
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);
301 } // end namespace llvm
303 #endif // LLVM_ANALYSIS_PTRUSEVISITOR_H