LLVM  10.0.0svn
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"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include "llvm/IR/CallSite.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/DerivedTypes.h"
32 #include "llvm/IR/InstVisitor.h"
33 #include "llvm/IR/Instruction.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/Intrinsics.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Use.h"
39 #include "llvm/IR/User.h"
40 #include "llvm/Support/Casting.h"
41 #include <algorithm>
42 #include <cassert>
43 #include <type_traits>
44 
45 namespace llvm {
46 
47 namespace detail {
48 
49 /// Implementation of non-dependent functionality for \c PtrUseVisitor.
50 ///
51 /// See \c PtrUseVisitor for the public interface and detailed comments about
52 /// usage. This class is just a helper base class which is not templated and
53 /// contains all common code to be shared between different instantiations of
54 /// PtrUseVisitor.
56 public:
57  /// This class provides information about the result of a visit.
58  ///
59  /// After walking all the users (recursively) of a pointer, the basic
60  /// infrastructure records some commonly useful information such as escape
61  /// analysis and whether the visit completed or aborted early.
62  class PtrInfo {
63  public:
64  PtrInfo() : AbortedInfo(nullptr, false), EscapedInfo(nullptr, false) {}
65 
66  /// Reset the pointer info, clearing all state.
67  void reset() {
68  AbortedInfo.setPointer(nullptr);
69  AbortedInfo.setInt(false);
70  EscapedInfo.setPointer(nullptr);
71  EscapedInfo.setInt(false);
72  }
73 
74  /// Did we abort the visit early?
75  bool isAborted() const { return AbortedInfo.getInt(); }
76 
77  /// Is the pointer escaped at some point?
78  bool isEscaped() const { return EscapedInfo.getInt(); }
79 
80  /// Get the instruction causing the visit to abort.
81  /// \returns a pointer to the instruction causing the abort if one is
82  /// available; otherwise returns null.
83  Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); }
84 
85  /// Get the instruction causing the pointer to escape.
86  /// \returns a pointer to the instruction which escapes the pointer if one
87  /// is available; otherwise returns null.
88  Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); }
89 
90  /// Mark the visit as aborted. Intended for use in a void return.
91  /// \param I The instruction which caused the visit to abort, if available.
92  void setAborted(Instruction *I = nullptr) {
93  AbortedInfo.setInt(true);
94  AbortedInfo.setPointer(I);
95  }
96 
97  /// Mark the pointer as escaped. Intended for use in a void return.
98  /// \param I The instruction which escapes the pointer, if available.
99  void setEscaped(Instruction *I = nullptr) {
100  EscapedInfo.setInt(true);
101  EscapedInfo.setPointer(I);
102  }
103 
104  /// Mark the pointer as escaped, and the visit as aborted. Intended
105  /// for use in a void return.
106  /// \param I The instruction which both escapes the pointer and aborts the
107  /// visit, if available.
108  void setEscapedAndAborted(Instruction *I = nullptr) {
109  setEscaped(I);
110  setAborted(I);
111  }
112 
113  private:
114  PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo;
115  };
116 
117 protected:
118  const DataLayout &DL;
119 
120  /// \name Visitation infrastructure
121  /// @{
122 
123  /// The info collected about the pointer being visited thus far.
125 
126  /// A struct of the data needed to visit a particular use.
127  ///
128  /// This is used to maintain a worklist fo to-visit uses. This is used to
129  /// make the visit be iterative rather than recursive.
130  struct UseToVisit {
132 
135  };
136 
137  /// The worklist of to-visit uses.
139 
140  /// A set of visited uses to break cycles in unreachable code.
142 
143  /// @}
144 
145  /// \name Per-visit state
146  /// This state is reset for each instruction visited.
147  /// @{
148 
149  /// The use currently being visited.
150  Use *U;
151 
152  /// True if we have a known constant offset for the use currently
153  /// being visited.
155 
156  /// The constant offset of the use if that is known.
158 
159  /// @}
160 
161  /// Note that the constructor is protected because this class must be a base
162  /// class, we can't create instances directly of this class.
163  PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {}
164 
165  /// Enqueue the users of this instruction in the visit worklist.
166  ///
167  /// This will visit the users with the same offset of the current visit
168  /// (including an unknown offset if that is the current state).
169  void enqueueUsers(Instruction &I);
170 
171  /// Walk the operands of a GEP and adjust the offset as appropriate.
172  ///
173  /// This routine does the heavy lifting of the pointer walk by computing
174  /// offsets and looking through GEPs.
176 };
177 
178 } // end namespace detail
179 
180 /// A base class for visitors over the uses of a pointer value.
181 ///
182 /// Once constructed, a user can call \c visit on a pointer value, and this
183 /// will walk its uses and visit each instruction using an InstVisitor. It also
184 /// provides visit methods which will recurse through any pointer-to-pointer
185 /// transformations such as GEPs and bitcasts.
186 ///
187 /// During the visit, the current Use* being visited is available to the
188 /// subclass, as well as the current offset from the original base pointer if
189 /// known.
190 ///
191 /// The recursive visit of uses is accomplished with a worklist, so the only
192 /// ordering guarantee is that an instruction is visited before any uses of it
193 /// are visited. Note that this does *not* mean before any of its users are
194 /// visited! This is because users can be visited multiple times due to
195 /// multiple, different uses of pointers derived from the same base.
196 ///
197 /// A particular Use will only be visited once, but a User may be visited
198 /// multiple times, once per Use. This visits may notably have different
199 /// offsets.
200 ///
201 /// All visit methods on the underlying InstVisitor return a boolean. This
202 /// return short-circuits the visit, stopping it immediately.
203 ///
204 /// FIXME: Generalize this for all values rather than just instructions.
205 template <typename DerivedT>
206 class PtrUseVisitor : protected InstVisitor<DerivedT>,
208  friend class InstVisitor<DerivedT>;
209 
210  using Base = InstVisitor<DerivedT>;
211 
212 public:
214  static_assert(std::is_base_of<PtrUseVisitor, DerivedT>::value,
215  "Must pass the derived type to this template!");
216  }
217 
218  /// Recursively visit the uses of the given pointer.
219  /// \returns An info struct about the pointer. See \c PtrInfo for details.
221  // This must be a pointer type. Get an integer type suitable to hold
222  // offsets on this pointer.
223  // FIXME: Support a vector of pointers.
224  assert(I.getType()->isPointerTy());
225  IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType()));
226  IsOffsetKnown = true;
227  Offset = APInt(IntPtrTy->getBitWidth(), 0);
228  PI.reset();
229 
230  // Enqueue the uses of this pointer.
231  enqueueUsers(I);
232 
233  // Visit all the uses off the worklist until it is empty.
234  while (!Worklist.empty()) {
235  UseToVisit ToVisit = Worklist.pop_back_val();
236  U = ToVisit.UseAndIsOffsetKnown.getPointer();
238  if (IsOffsetKnown)
239  Offset = std::move(ToVisit.Offset);
240 
241  Instruction *I = cast<Instruction>(U->getUser());
242  static_cast<DerivedT*>(this)->visit(I);
243  if (PI.isAborted())
244  break;
245  }
246  return PI;
247  }
248 
249 protected:
251  if (SI.getValueOperand() == U->get())
252  PI.setEscaped(&SI);
253  }
254 
256  enqueueUsers(BC);
257  }
258 
260  enqueueUsers(ASC);
261  }
262 
264  PI.setEscaped(&I);
265  }
266 
268  if (GEPI.use_empty())
269  return;
270 
271  // If we can't walk the GEP, clear the offset.
272  if (!adjustOffsetForGEP(GEPI)) {
273  IsOffsetKnown = false;
274  Offset = APInt();
275  }
276 
277  // Enqueue the users now that the offset has been adjusted.
278  enqueueUsers(GEPI);
279  }
280 
281  // No-op intrinsics which we know don't escape the pointer to logic in
282  // some other function.
286  switch (II.getIntrinsicID()) {
287  default:
288  return Base::visitIntrinsicInst(II);
289 
290  case Intrinsic::lifetime_start:
291  case Intrinsic::lifetime_end:
292  return; // No-op intrinsics.
293  }
294  }
295 
296  // Generically, arguments to calls and invokes escape the pointer to some
297  // other function. Mark that.
300  Base::visitCallSite(CS);
301  }
302 };
303 
304 } // end namespace llvm
305 
306 #endif // LLVM_ANALYSIS_PTRUSEVISITOR_H
Value * getValueOperand()
Definition: Instructions.h:417
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:112
void setEscaped(Instruction *I=nullptr)
Mark the pointer as escaped.
Definition: PtrUseVisitor.h:99
Base class for instruction visitors.
Definition: InstVisitor.h:80
void visitCallSite(CallSite CS)
void visitMemIntrinsic(MemIntrinsic &I)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PointerTy getPointer() const
Use * U
The use currently being visited.
SmallPtrSet< Use *, 8 > VisitedUses
A set of visited uses to break cycles in unreachable code.
Implementation of non-dependent functionality for PtrUseVisitor.
Definition: PtrUseVisitor.h:55
This class provides information about the result of a visit.
Definition: PtrUseVisitor.h:62
Instruction * getAbortingInst() const
Get the instruction causing the visit to abort.
Definition: PtrUseVisitor.h:83
PtrUseVisitor(const DataLayout &DL)
This defines the Use class.
void visitBitCastInst(BitCastInst &BC)
This class represents a conversion between pointers from one address space to another.
bool IsOffsetKnown
True if we have a known constant offset for the use currently being visited.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
bool isAborted() const
Did we abort the visit early?
Definition: PtrUseVisitor.h:75
void visitStoreInst(StoreInst &SI)
PtrUseVisitorBase(const DataLayout &DL)
Note that the constructor is protected because this class must be a base class, we can&#39;t create insta...
This file implements a class to represent arbitrary precision integral constant values and operations...
This class represents a cast from a pointer to an integer.
A struct of the data needed to visit a particular use.
InstrTy * getInstruction() const
Definition: CallSite.h:96
A base class for visitors over the uses of a pointer value.
SmallVector< UseToVisit, 8 > Worklist
The worklist of to-visit uses.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void setAborted(Instruction *I=nullptr)
Mark the visit as aborted.
Definition: PtrUseVisitor.h:92
IntType getInt() const
This class represents a no-op cast from one type to another.
An instruction for storing to memory.
Definition: Instructions.h:325
void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I)
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:883
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space...
Definition: DataLayout.cpp:769
PointerIntPair - This class implements a pair of a pointer and small integer.
void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC)
void enqueueUsers(Instruction &I)
Enqueue the users of this instruction in the visit worklist.
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
Class to represent integer types.
Definition: DerivedTypes.h:40
PtrInfo PI
The info collected about the pointer being visited thus far.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:50
bool adjustOffsetForGEP(GetElementPtrInst &GEPI)
Walk the operands of a GEP and adjust the offset as appropriate.
This is the common base class for memset/memcpy/memmove.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
This is the common base class for debug info intrinsics.
Definition: IntrinsicInst.h:66
void setEscapedAndAborted(Instruction *I=nullptr)
Mark the pointer as escaped, and the visit as aborted.
void visitGetElementPtrInst(GetElementPtrInst &GEPI)
Class for arbitrary precision integers.
Definition: APInt.h:69
void visitIntrinsicInst(IntrinsicInst &II)
void visitPtrToIntInst(PtrToIntInst &I)
#define I(x, y, z)
Definition: MD5.cpp:58
Instruction * getEscapingInst() const
Get the instruction causing the pointer to escape.
Definition: PtrUseVisitor.h:88
void reset()
Reset the pointer info, clearing all state.
Definition: PtrUseVisitor.h:67
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
APInt Offset
The constant offset of the use if that is known.
PtrInfo visitPtr(Instruction &I)
Recursively visit the uses of the given pointer.
bool use_empty() const
Definition: Value.h:342
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
bool isEscaped() const
Is the pointer escaped at some point?
Definition: PtrUseVisitor.h:78