LLVM  17.0.0git
TinyPtrVector.h
Go to the documentation of this file.
1 //===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- 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 #ifndef LLVM_ADT_TINYPTRVECTOR_H
10 #define LLVM_ADT_TINYPTRVECTOR_H
11 
12 #include "llvm/ADT/ArrayRef.h"
13 #include "llvm/ADT/PointerUnion.h"
14 #include "llvm/ADT/SmallVector.h"
15 #include <cassert>
16 #include <cstddef>
17 #include <iterator>
18 #include <type_traits>
19 
20 namespace llvm {
21 
22 /// TinyPtrVector - This class is specialized for cases where there are
23 /// normally 0 or 1 element in a vector, but is general enough to go beyond that
24 /// when required.
25 ///
26 /// NOTE: This container doesn't allow you to store a null pointer into it.
27 ///
28 template <typename EltTy>
30 public:
32  using value_type = typename VecTy::value_type;
33  // EltTy must be the first pointer type so that is<EltTy> is true for the
34  // default-constructed PtrUnion. This allows an empty TinyPtrVector to
35  // naturally vend a begin/end iterator of type EltTy* without an additional
36  // check for the empty state.
38 
39 private:
40  PtrUnion Val;
41 
42 public:
43  TinyPtrVector() = default;
44 
46  if (VecTy *V = Val.template dyn_cast<VecTy*>())
47  delete V;
48  }
49 
50  TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
51  if (VecTy *V = Val.template dyn_cast<VecTy*>())
52  Val = new VecTy(*V);
53  }
54 
56  if (this == &RHS)
57  return *this;
58  if (RHS.empty()) {
59  this->clear();
60  return *this;
61  }
62 
63  // Try to squeeze into the single slot. If it won't fit, allocate a copied
64  // vector.
65  if (Val.template is<EltTy>()) {
66  if (RHS.size() == 1)
67  Val = RHS.front();
68  else
69  Val = new VecTy(*RHS.Val.template get<VecTy*>());
70  return *this;
71  }
72 
73  // If we have a full vector allocated, try to re-use it.
74  if (RHS.Val.template is<EltTy>()) {
75  Val.template get<VecTy*>()->clear();
76  Val.template get<VecTy*>()->push_back(RHS.front());
77  } else {
78  *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>();
79  }
80  return *this;
81  }
82 
84  RHS.Val = (EltTy)nullptr;
85  }
86 
88  if (this == &RHS)
89  return *this;
90  if (RHS.empty()) {
91  this->clear();
92  return *this;
93  }
94 
95  // If this vector has been allocated on the heap, re-use it if cheap. If it
96  // would require more copying, just delete it and we'll steal the other
97  // side.
98  if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
99  if (RHS.Val.template is<EltTy>()) {
100  V->clear();
101  V->push_back(RHS.front());
102  RHS.Val = EltTy();
103  return *this;
104  }
105  delete V;
106  }
107 
108  Val = RHS.Val;
109  RHS.Val = EltTy();
110  return *this;
111  }
112 
113  TinyPtrVector(std::initializer_list<EltTy> IL)
114  : Val(IL.size() == 0
115  ? PtrUnion()
116  : IL.size() == 1 ? PtrUnion(*IL.begin())
117  : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
118 
119  /// Constructor from an ArrayRef.
120  ///
121  /// This also is a constructor for individual array elements due to the single
122  /// element constructor for ArrayRef.
124  : Val(Elts.empty()
125  ? PtrUnion()
126  : Elts.size() == 1
127  ? PtrUnion(Elts[0])
128  : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
129 
130  TinyPtrVector(size_t Count, EltTy Value)
131  : Val(Count == 0 ? PtrUnion()
132  : Count == 1 ? PtrUnion(Value)
133  : PtrUnion(new VecTy(Count, Value))) {}
134 
135  // implicit conversion operator to ArrayRef.
136  operator ArrayRef<EltTy>() const {
137  if (Val.isNull())
138  return std::nullopt;
139  if (Val.template is<EltTy>())
140  return *Val.getAddrOfPtr1();
141  return *Val.template get<VecTy*>();
142  }
143 
144  // implicit conversion operator to MutableArrayRef.
146  if (Val.isNull())
147  return std::nullopt;
148  if (Val.template is<EltTy>())
149  return *Val.getAddrOfPtr1();
150  return *Val.template get<VecTy*>();
151  }
152 
153  // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
154  template <
155  typename U,
156  std::enable_if_t<std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
157  bool> = false>
158  operator ArrayRef<U>() const {
159  return operator ArrayRef<EltTy>();
160  }
161 
162  bool empty() const {
163  // This vector can be empty if it contains no element, or if it
164  // contains a pointer to an empty vector.
165  if (Val.isNull()) return true;
166  if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
167  return Vec->empty();
168  return false;
169  }
170 
171  unsigned size() const {
172  if (empty())
173  return 0;
174  if (Val.template is<EltTy>())
175  return 1;
176  return Val.template get<VecTy*>()->size();
177  }
178 
179  using iterator = EltTy *;
180  using const_iterator = const EltTy *;
181  using reverse_iterator = std::reverse_iterator<iterator>;
182  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
183 
185  if (Val.template is<EltTy>())
186  return Val.getAddrOfPtr1();
187 
188  return Val.template get<VecTy *>()->begin();
189  }
190 
192  if (Val.template is<EltTy>())
193  return begin() + (Val.isNull() ? 0 : 1);
194 
195  return Val.template get<VecTy *>()->end();
196  }
197 
199  return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
200  }
201 
202  const_iterator end() const {
203  return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
204  }
205 
208 
210  return const_reverse_iterator(end());
211  }
212 
214  return const_reverse_iterator(begin());
215  }
216 
217  EltTy operator[](unsigned i) const {
218  assert(!Val.isNull() && "can't index into an empty vector");
219  if (Val.template is<EltTy>()) {
220  assert(i == 0 && "tinyvector index out of range");
221  return Val.template get<EltTy>();
222  }
223 
224  assert(i < Val.template get<VecTy*>()->size() &&
225  "tinyvector index out of range");
226  return (*Val.template get<VecTy*>())[i];
227  }
228 
229  EltTy front() const {
230  assert(!empty() && "vector empty");
231  if (Val.template is<EltTy>())
232  return Val.template get<EltTy>();
233  return Val.template get<VecTy*>()->front();
234  }
235 
236  EltTy back() const {
237  assert(!empty() && "vector empty");
238  if (Val.template is<EltTy>())
239  return Val.template get<EltTy>();
240  return Val.template get<VecTy*>()->back();
241  }
242 
243  void push_back(EltTy NewVal) {
244  // If we have nothing, add something.
245  if (Val.isNull()) {
246  Val = NewVal;
247  assert(!Val.isNull() && "Can't add a null value");
248  return;
249  }
250 
251  // If we have a single value, convert to a vector.
252  if (Val.template is<EltTy>()) {
253  EltTy V = Val.template get<EltTy>();
254  Val = new VecTy();
255  Val.template get<VecTy*>()->push_back(V);
256  }
257 
258  // Add the new value, we know we have a vector.
259  Val.template get<VecTy*>()->push_back(NewVal);
260  }
261 
262  void pop_back() {
263  // If we have a single value, convert to empty.
264  if (Val.template is<EltTy>())
265  Val = (EltTy)nullptr;
266  else if (VecTy *Vec = Val.template get<VecTy*>())
267  Vec->pop_back();
268  }
269 
270  void clear() {
271  // If we have a single value, convert to empty.
272  if (Val.template is<EltTy>()) {
273  Val = EltTy();
274  } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
275  // If we have a vector form, just clear it.
276  Vec->clear();
277  }
278  // Otherwise, we're already empty.
279  }
280 
282  assert(I >= begin() && "Iterator to erase is out of bounds.");
283  assert(I < end() && "Erasing at past-the-end iterator.");
284 
285  // If we have a single value, convert to empty.
286  if (Val.template is<EltTy>()) {
287  if (I == begin())
288  Val = EltTy();
289  } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
290  // multiple items in a vector; just do the erase, there is no
291  // benefit to collapsing back to a pointer
292  return Vec->erase(I);
293  }
294  return end();
295  }
296 
298  assert(S >= begin() && "Range to erase is out of bounds.");
299  assert(S <= E && "Trying to erase invalid range.");
300  assert(E <= end() && "Trying to erase past the end.");
301 
302  if (Val.template is<EltTy>()) {
303  if (S == begin() && S != E)
304  Val = EltTy();
305  } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
306  return Vec->erase(S, E);
307  }
308  return end();
309  }
310 
311  iterator insert(iterator I, const EltTy &Elt) {
312  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
313  assert(I <= this->end() && "Inserting past the end of the vector.");
314  if (I == end()) {
315  push_back(Elt);
316  return std::prev(end());
317  }
318  assert(!Val.isNull() && "Null value with non-end insert iterator.");
319  if (Val.template is<EltTy>()) {
320  EltTy V = Val.template get<EltTy>();
321  assert(I == begin());
322  Val = Elt;
323  push_back(V);
324  return begin();
325  }
326 
327  return Val.template get<VecTy*>()->insert(I, Elt);
328  }
329 
330  template<typename ItTy>
332  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
333  assert(I <= this->end() && "Inserting past the end of the vector.");
334  if (From == To)
335  return I;
336 
337  // If we have a single value, convert to a vector.
338  ptrdiff_t Offset = I - begin();
339  if (Val.isNull()) {
340  if (std::next(From) == To) {
341  Val = *From;
342  return begin();
343  }
344 
345  Val = new VecTy();
346  } else if (Val.template is<EltTy>()) {
347  EltTy V = Val.template get<EltTy>();
348  Val = new VecTy();
349  Val.template get<VecTy*>()->push_back(V);
350  }
351  return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
352  }
353 };
354 
355 } // end namespace llvm
356 
357 #endif // LLVM_ADT_TINYPTRVECTOR_H
i
i
Definition: README.txt:29
llvm::TinyPtrVector::TinyPtrVector
TinyPtrVector(std::initializer_list< EltTy > IL)
Definition: TinyPtrVector.h:113
llvm::TinyPtrVector::begin
const_iterator begin() const
Definition: TinyPtrVector.h:198
llvm::PointerUnion::isNull
bool isNull() const
Test if the pointer held in the union is null, regardless of which type it is.
Definition: PointerUnion.h:142
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::TinyPtrVector::rend
reverse_iterator rend()
Definition: TinyPtrVector.h:207
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::TinyPtrVector::erase
iterator erase(iterator S, iterator E)
Definition: TinyPtrVector.h:297
llvm::TinyPtrVector::pop_back
void pop_back()
Definition: TinyPtrVector.h:262
llvm::TinyPtrVector::front
EltTy front() const
Definition: TinyPtrVector.h:229
llvm::TinyPtrVector::begin
iterator begin()
Definition: TinyPtrVector.h:184
llvm::TinyPtrVector::rend
const_reverse_iterator rend() const
Definition: TinyPtrVector.h:213
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::TinyPtrVector::operator=
TinyPtrVector & operator=(TinyPtrVector &&RHS)
Definition: TinyPtrVector.h:87
llvm::TinyPtrVector::VecTy
SmallVector< EltTy, 4 > VecTy
Definition: TinyPtrVector.h:31
new
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj * new
Definition: README.txt:125
llvm::TinyPtrVector::insert
iterator insert(iterator I, const EltTy &Elt)
Definition: TinyPtrVector.h:311
llvm::TinyPtrVector< llvm::VPValue * >::reverse_iterator
std::reverse_iterator< iterator > reverse_iterator
Definition: TinyPtrVector.h:181
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:27
ptrdiff_t
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
ItTy
llvm::TinyPtrVector::rbegin
const_reverse_iterator rbegin() const
Definition: TinyPtrVector.h:209
llvm::TinyPtrVector::push_back
void push_back(EltTy NewVal)
Definition: TinyPtrVector.h:243
llvm::TinyPtrVector::TinyPtrVector
TinyPtrVector(ArrayRef< EltTy > Elts)
Constructor from an ArrayRef.
Definition: TinyPtrVector.h:123
llvm::TinyPtrVector::erase
iterator erase(iterator I)
Definition: TinyPtrVector.h:281
llvm::VPValue
Definition: VPlanValue.h:44
llvm::TinyPtrVector< llvm::VPValue * >::value_type
typename VecTy::value_type value_type
Definition: TinyPtrVector.h:32
llvm::TinyPtrVector::insert
iterator insert(iterator I, ItTy From, ItTy To)
Definition: TinyPtrVector.h:331
llvm::TinyPtrVector::rbegin
reverse_iterator rbegin()
Definition: TinyPtrVector.h:206
llvm::TinyPtrVector::operator=
TinyPtrVector & operator=(const TinyPtrVector &RHS)
Definition: TinyPtrVector.h:55
llvm::TinyPtrVector::end
const_iterator end() const
Definition: TinyPtrVector.h:202
llvm::TinyPtrVector::TinyPtrVector
TinyPtrVector()=default
llvm::TinyPtrVector::clear
void clear()
Definition: TinyPtrVector.h:270
llvm::TinyPtrVector::TinyPtrVector
TinyPtrVector(size_t Count, EltTy Value)
Definition: TinyPtrVector.h:130
I
#define I(x, y, z)
Definition: MD5.cpp:58
ArrayRef.h
llvm::TinyPtrVector::back
EltTy back() const
Definition: TinyPtrVector.h:236
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::TinyPtrVector::TinyPtrVector
TinyPtrVector(TinyPtrVector &&RHS)
Definition: TinyPtrVector.h:83
PointerUnion.h
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::TinyPtrVector::size
unsigned size() const
Definition: TinyPtrVector.h:171
llvm::Offset
@ Offset
Definition: DWP.cpp:406
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::PointerUnion< llvm::VPValue *, VecTy * >
llvm::TinyPtrVector::~TinyPtrVector
~TinyPtrVector()
Definition: TinyPtrVector.h:45
llvm::TinyPtrVector::operator[]
EltTy operator[](unsigned i) const
Definition: TinyPtrVector.h:217
llvm::PointerUnion::getAddrOfPtr1
const First * getAddrOfPtr1() const
If the union is set to the first pointer type get an address pointing to it.
Definition: PointerUnion.h:168
llvm::TinyPtrVector::empty
bool empty() const
Definition: TinyPtrVector.h:162
SmallVector.h
llvm::TinyPtrVector::end
iterator end()
Definition: TinyPtrVector.h:191
llvm::TinyPtrVector< llvm::VPValue * >::const_reverse_iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: TinyPtrVector.h:182
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::TinyPtrVector
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:29
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::TinyPtrVector::TinyPtrVector
TinyPtrVector(const TinyPtrVector &RHS)
Definition: TinyPtrVector.h:50