LLVM  16.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/DerivedTypes.h"
30 #include "llvm/IR/InstVisitor.h"
31 #include "llvm/IR/IntrinsicInst.h"
32 #include <cassert>
33 #include <type_traits>
34 
35 namespace llvm {
36 class DataLayout;
37 class Use;
38 
39 namespace 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.
48 public:
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.
100  void setEscapedAndAborted(Instruction *I = nullptr) {
101  setEscaped(I);
102  setAborted(I);
103  }
104 
105  private:
106  PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo;
107  };
108 
109 protected:
110  const DataLayout &DL;
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.
142  Use *U;
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).
161  void enqueueUsers(Instruction &I);
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.
197 template <typename DerivedT>
198 class PtrUseVisitor : protected InstVisitor<DerivedT>,
200  friend class InstVisitor<DerivedT>;
201 
202  using Base = InstVisitor<DerivedT>;
203 
204 public:
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.
223  enqueueUsers(I);
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 
241 protected:
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
llvm::detail::PtrUseVisitorBase::enqueueUsers
void enqueueUsers(Instruction &I)
Enqueue the users of this instruction in the visit worklist.
Definition: PtrUseVisitor.cpp:20
llvm::detail::PtrUseVisitorBase::DL
const DataLayout & DL
Definition: PtrUseVisitor.h:110
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
IntrinsicInst.h
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:53
llvm::PtrUseVisitor::visitDbgInfoIntrinsic
void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I)
Definition: PtrUseVisitor.h:275
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5255
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::InstVisitor< DerivedT >::visitIntrinsicInst
void visitIntrinsicInst(IntrinsicInst &I)
Definition: InstVisitor.h:219
llvm::detail::PtrUseVisitorBase::PtrInfo::PtrInfo
PtrInfo()
Definition: PtrUseVisitor.h:56
llvm::InstVisitor< DerivedT >::visitCallBase
void visitCallBase(CallBase &I)
Definition: InstVisitor.h:267
APInt.h
llvm::DataLayout::getIndexType
Type * getIndexType(Type *PtrTy) const
Returns the type of a GEP index.
Definition: DataLayout.cpp:869
llvm::detail::PtrUseVisitorBase::UseToVisit
A struct of the data needed to visit a particular use.
Definition: PtrUseVisitor.h:122
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:1041
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::PtrUseVisitor::PtrUseVisitor
PtrUseVisitor(const DataLayout &DL)
Definition: PtrUseVisitor.h:205
PointerIntPair.h
llvm::detail::PtrUseVisitorBase::VisitedUses
SmallPtrSet< Use *, 8 > VisitedUses
A set of visited uses to break cycles in unreachable code.
Definition: PtrUseVisitor.h:133
llvm::AddrSpaceCastInst
This class represents a conversion between pointers from one address space to another.
Definition: Instructions.h:5295
llvm::PtrUseVisitor::visitGetElementPtrInst
void visitGetElementPtrInst(GetElementPtrInst &GEPI)
Definition: PtrUseVisitor.h:259
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:155
llvm::detail::PtrUseVisitorBase::IsOffsetKnown
bool IsOffsetKnown
True if we have a known constant offset for the use currently being visited.
Definition: PtrUseVisitor.h:146
llvm::detail::PtrUseVisitorBase::PtrInfo::setAborted
void setAborted(Instruction *I=nullptr)
Mark the visit as aborted.
Definition: PtrUseVisitor.h:84
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::detail::PtrUseVisitorBase::PI
PtrInfo PI
The info collected about the pointer being visited thus far.
Definition: PtrUseVisitor.h:116
false
Definition: StackSlotColoring.cpp:141
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::detail::PtrUseVisitorBase::UseToVisit::Offset
APInt Offset
Definition: PtrUseVisitor.h:126
llvm::Instruction
Definition: Instruction.h:42
SmallPtrSet.h
llvm::detail::PtrUseVisitorBase::UseToVisit::UseAndIsOffsetKnown
UseAndIsOffsetKnownPair UseAndIsOffsetKnown
Definition: PtrUseVisitor.h:125
llvm::DbgInfoIntrinsic
This is the common base class for debug info intrinsics.
Definition: IntrinsicInst.h:166
llvm::detail::PtrUseVisitorBase::PtrInfo::isAborted
bool isAborted() const
Did we abort the visit early?
Definition: PtrUseVisitor.h:67
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::PtrUseVisitor::visitMemIntrinsic
void visitMemIntrinsic(MemIntrinsic &I)
Definition: PtrUseVisitor.h:276
llvm::PointerIntPair::getPointer
PointerTy getPointer() const
Definition: PointerIntPair.h:60
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
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:32
llvm::detail::PtrUseVisitorBase::PtrInfo::getEscapingInst
Instruction * getEscapingInst() const
Get the instruction causing the pointer to escape.
Definition: PtrUseVisitor.h:80
llvm::detail::PtrUseVisitorBase::PtrInfo
This class provides information about the result of a visit.
Definition: PtrUseVisitor.h:54
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::PointerIntPair::getInt
IntType getInt() const
Definition: PointerIntPair.h:62
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:87
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
InstVisitor.h
llvm::PtrUseVisitor
A base class for visitors over the uses of a pointer value.
Definition: PtrUseVisitor.h:198
llvm::detail::PtrUseVisitorBase::PtrInfo::isEscaped
bool isEscaped() const
Is the pointer escaped at some point?
Definition: PtrUseVisitor.h:70
llvm::PtrToIntInst
This class represents a cast from a pointer to an integer.
Definition: Instructions.h:5204
llvm::PtrUseVisitor::visitCallBase
void visitCallBase(CallBase &CB)
Definition: PtrUseVisitor.h:290
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:78
llvm::detail::PtrUseVisitorBase::Offset
APInt Offset
The constant offset of the use if that is known.
Definition: PtrUseVisitor.h:149
llvm::PtrUseVisitor::visitAddrSpaceCastInst
void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC)
Definition: PtrUseVisitor.h:251
llvm::detail::PtrUseVisitorBase::PtrInfo::getAbortingInst
Instruction * getAbortingInst() const
Get the instruction causing the visit to abort.
Definition: PtrUseVisitor.h:75
llvm::detail::PtrUseVisitorBase::PtrInfo::setEscapedAndAborted
void setEscapedAndAborted(Instruction *I=nullptr)
Mark the pointer as escaped, and the visit as aborted.
Definition: PtrUseVisitor.h:100
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:46
llvm::PtrUseVisitor::visitPtr
PtrInfo visitPtr(Instruction &I)
Recursively visit the uses of the given pointer.
Definition: PtrUseVisitor.h:212
SmallVector.h
llvm::detail::PtrUseVisitorBase::U
Use * U
The use currently being visited.
Definition: PtrUseVisitor.h:142
llvm::detail::PtrUseVisitorBase::PtrInfo::reset
void reset()
Reset the pointer info, clearing all state.
Definition: PtrUseVisitor.h:59
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:91
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
DerivedTypes.h
llvm::detail::PtrUseVisitorBase
Implementation of non-dependent functionality for PtrUseVisitor.
Definition: PtrUseVisitor.h:47
llvm::PtrUseVisitor::visitStoreInst
void visitStoreInst(StoreInst &SI)
Definition: PtrUseVisitor.h:242
llvm::PtrUseVisitor::visitIntrinsicInst
void visitIntrinsicInst(IntrinsicInst &II)
Definition: PtrUseVisitor.h:277
llvm::PtrUseVisitor::visitPtrToIntInst
void visitPtrToIntInst(PtrToIntInst &I)
Definition: PtrUseVisitor.h:255
llvm::detail::PtrUseVisitorBase::Worklist
SmallVector< UseToVisit, 8 > Worklist
The worklist of to-visit uses.
Definition: PtrUseVisitor.h:130
llvm::PtrUseVisitor::visitBitCastInst
void visitBitCastInst(BitCastInst &BC)
Definition: PtrUseVisitor.h:247
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43