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