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