LLVM  14.0.0git
SmallVector.h
Go to the documentation of this file.
1 //===- llvm/ADT/SmallVector.h - 'Normally small' 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 // This file defines the SmallVector class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_SMALLVECTOR_H
14 #define LLVM_ADT_SMALLVECTOR_H
15 
17 #include "llvm/Support/Compiler.h"
19 #include <algorithm>
20 #include <cassert>
21 #include <cstddef>
22 #include <cstdlib>
23 #include <cstring>
24 #include <functional>
25 #include <initializer_list>
26 #include <iterator>
27 #include <limits>
28 #include <memory>
29 #include <new>
30 #include <type_traits>
31 #include <utility>
32 
33 namespace llvm {
34 
35 /// This is all the stuff common to all SmallVectors.
36 ///
37 /// The template parameter specifies the type which should be used to hold the
38 /// Size and Capacity of the SmallVector, so it can be adjusted.
39 /// Using 32 bit size is desirable to shrink the size of the SmallVector.
40 /// Using 64 bit size is desirable for cases like SmallVector<char>, where a
41 /// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
42 /// buffering bitcode output - which can exceed 4GB.
43 template <class Size_T> class SmallVectorBase {
44 protected:
45  void *BeginX;
46  Size_T Size = 0, Capacity;
47 
48  /// The maximum value of the Size_T used.
49  static constexpr size_t SizeTypeMax() {
51  }
52 
53  SmallVectorBase() = delete;
54  SmallVectorBase(void *FirstEl, size_t TotalCapacity)
55  : BeginX(FirstEl), Capacity(TotalCapacity) {}
56 
57  /// This is a helper for \a grow() that's out of line to reduce code
58  /// duplication. This function will report a fatal error if it can't grow at
59  /// least to \p MinSize.
60  void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
61 
62  /// This is an implementation of the grow() method which only works
63  /// on POD-like data types and is out of line to reduce code duplication.
64  /// This function will report a fatal error if it cannot increase capacity.
65  void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
66 
67 public:
68  size_t size() const { return Size; }
69  size_t capacity() const { return Capacity; }
70 
71  LLVM_NODISCARD bool empty() const { return !Size; }
72 
73 protected:
74  /// Set the array size to \p N, which the current array must have enough
75  /// capacity for.
76  ///
77  /// This does not construct or destroy any elements in the vector.
78  void set_size(size_t N) {
79  assert(N <= capacity());
80  Size = N;
81  }
82 };
83 
84 template <class T>
85 using SmallVectorSizeType =
86  typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
88 
89 /// Figure out the offset of the first element.
90 template <class T, typename = void> struct SmallVectorAlignmentAndSize {
91  alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
93  alignas(T) char FirstEl[sizeof(T)];
94 };
95 
96 /// This is the part of SmallVectorTemplateBase which does not depend on whether
97 /// the type T is a POD. The extra dummy template argument is used by ArrayRef
98 /// to avoid unnecessarily requiring T to be complete.
99 template <typename T, typename = void>
101  : public SmallVectorBase<SmallVectorSizeType<T>> {
103 
104  /// Find the address of the first element. For this pointer math to be valid
105  /// with small-size of 0 for T with lots of alignment, it's important that
106  /// SmallVectorStorage is properly-aligned even for small-size of 0.
107  void *getFirstEl() const {
108  return const_cast<void *>(reinterpret_cast<const void *>(
109  reinterpret_cast<const char *>(this) +
111  }
112  // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
113 
114 protected:
115  SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
116 
117  void grow_pod(size_t MinSize, size_t TSize) {
118  Base::grow_pod(getFirstEl(), MinSize, TSize);
119  }
120 
121  /// Return true if this is a smallvector which has not had dynamic
122  /// memory allocated for it.
123  bool isSmall() const { return this->BeginX == getFirstEl(); }
124 
125  /// Put this vector in a state of being small.
126  void resetToSmall() {
127  this->BeginX = getFirstEl();
128  this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
129  }
130 
131  /// Return true if V is an internal reference to the given range.
132  bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
133  // Use std::less to avoid UB.
134  std::less<> LessThan;
135  return !LessThan(V, First) && LessThan(V, Last);
136  }
137 
138  /// Return true if V is an internal reference to this vector.
139  bool isReferenceToStorage(const void *V) const {
140  return isReferenceToRange(V, this->begin(), this->end());
141  }
142 
143  /// Return true if First and Last form a valid (possibly empty) range in this
144  /// vector's storage.
145  bool isRangeInStorage(const void *First, const void *Last) const {
146  // Use std::less to avoid UB.
147  std::less<> LessThan;
148  return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
149  !LessThan(this->end(), Last);
150  }
151 
152  /// Return true unless Elt will be invalidated by resizing the vector to
153  /// NewSize.
154  bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
155  // Past the end.
157  return true;
158 
159  // Return false if Elt will be destroyed by shrinking.
160  if (NewSize <= this->size())
161  return Elt < this->begin() + NewSize;
162 
163  // Return false if we need to grow.
164  return NewSize <= this->capacity();
165  }
166 
167  /// Check whether Elt will be invalidated by resizing the vector to NewSize.
168  void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
169  assert(isSafeToReferenceAfterResize(Elt, NewSize) &&
170  "Attempting to reference an element of the vector in an operation "
171  "that invalidates it");
172  }
173 
174  /// Check whether Elt will be invalidated by increasing the size of the
175  /// vector by N.
176  void assertSafeToAdd(const void *Elt, size_t N = 1) {
177  this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
178  }
179 
180  /// Check whether any part of the range will be invalidated by clearing.
181  void assertSafeToReferenceAfterClear(const T *From, const T *To) {
182  if (From == To)
183  return;
184  this->assertSafeToReferenceAfterResize(From, 0);
185  this->assertSafeToReferenceAfterResize(To - 1, 0);
186  }
187  template <
188  class ItTy,
189  std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
190  bool> = false>
192 
193  /// Check whether any part of the range will be invalidated by growing.
194  void assertSafeToAddRange(const T *From, const T *To) {
195  if (From == To)
196  return;
197  this->assertSafeToAdd(From, To - From);
198  this->assertSafeToAdd(To - 1, To - From);
199  }
200  template <
201  class ItTy,
202  std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
203  bool> = false>
205 
206  /// Reserve enough space to add one element, and return the updated element
207  /// pointer in case it was a reference to the storage.
208  template <class U>
209  static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
210  size_t N) {
211  size_t NewSize = This->size() + N;
212  if (LLVM_LIKELY(NewSize <= This->capacity()))
213  return &Elt;
214 
215  bool ReferencesStorage = false;
216  int64_t Index = -1;
217  if (!U::TakesParamByValue) {
218  if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
219  ReferencesStorage = true;
220  Index = &Elt - This->begin();
221  }
222  }
223  This->grow(NewSize);
224  return ReferencesStorage ? This->begin() + Index : &Elt;
225  }
226 
227 public:
228  using size_type = size_t;
230  using value_type = T;
231  using iterator = T *;
232  using const_iterator = const T *;
233 
234  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
235  using reverse_iterator = std::reverse_iterator<iterator>;
236 
237  using reference = T &;
238  using const_reference = const T &;
239  using pointer = T *;
240  using const_pointer = const T *;
241 
242  using Base::capacity;
243  using Base::empty;
244  using Base::size;
245 
246  // forward iterator creation methods.
247  iterator begin() { return (iterator)this->BeginX; }
248  const_iterator begin() const { return (const_iterator)this->BeginX; }
249  iterator end() { return begin() + size(); }
250  const_iterator end() const { return begin() + size(); }
251 
252  // reverse iterator creation methods.
257 
258  size_type size_in_bytes() const { return size() * sizeof(T); }
259  size_type max_size() const {
260  return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
261  }
262 
263  size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
264 
265  /// Return a pointer to the vector's buffer, even if empty().
266  pointer data() { return pointer(begin()); }
267  /// Return a pointer to the vector's buffer, even if empty().
268  const_pointer data() const { return const_pointer(begin()); }
269 
271  assert(idx < size());
272  return begin()[idx];
273  }
275  assert(idx < size());
276  return begin()[idx];
277  }
278 
280  assert(!empty());
281  return begin()[0];
282  }
284  assert(!empty());
285  return begin()[0];
286  }
287 
289  assert(!empty());
290  return end()[-1];
291  }
293  assert(!empty());
294  return end()[-1];
295  }
296 };
297 
298 /// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
299 /// method implementations that are designed to work with non-trivial T's.
300 ///
301 /// We approximate is_trivially_copyable with trivial move/copy construction and
302 /// trivial destruction. While the standard doesn't specify that you're allowed
303 /// copy these types with memcpy, there is no way for the type to observe this.
304 /// This catches the important case of std::pair<POD, POD>, which is not
305 /// trivially assignable.
306 template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
307  (is_trivially_move_constructible<T>::value) &&
308  std::is_trivially_destructible<T>::value>
311 
312 protected:
313  static constexpr bool TakesParamByValue = false;
314  using ValueParamT = const T &;
315 
317 
318  static void destroy_range(T *S, T *E) {
319  while (S != E) {
320  --E;
321  E->~T();
322  }
323  }
324 
325  /// Move the range [I, E) into the uninitialized memory starting with "Dest",
326  /// constructing elements as needed.
327  template<typename It1, typename It2>
328  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
329  std::uninitialized_copy(std::make_move_iterator(I),
330  std::make_move_iterator(E), Dest);
331  }
332 
333  /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
334  /// constructing elements as needed.
335  template<typename It1, typename It2>
336  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
337  std::uninitialized_copy(I, E, Dest);
338  }
339 
340  /// Grow the allocated memory (without initializing new elements), doubling
341  /// the size of the allocated memory. Guarantees space for at least one more
342  /// element, or MinSize more elements if specified.
343  void grow(size_t MinSize = 0);
344 
345  /// Create a new allocation big enough for \p MinSize and pass back its size
346  /// in \p NewCapacity. This is the first section of \a grow().
347  T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
348  return static_cast<T *>(
350  MinSize, sizeof(T), NewCapacity));
351  }
352 
353  /// Move existing elements over to the new allocation \p NewElts, the middle
354  /// section of \a grow().
355  void moveElementsForGrow(T *NewElts);
356 
357  /// Transfer ownership of the allocation, finishing up \a grow().
358  void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
359 
360  /// Reserve enough space to add one element, and return the updated element
361  /// pointer in case it was a reference to the storage.
362  const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
363  return this->reserveForParamAndGetAddressImpl(this, Elt, N);
364  }
365 
366  /// Reserve enough space to add one element, and return the updated element
367  /// pointer in case it was a reference to the storage.
368  T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
369  return const_cast<T *>(
370  this->reserveForParamAndGetAddressImpl(this, Elt, N));
371  }
372 
373  static T &&forward_value_param(T &&V) { return std::move(V); }
374  static const T &forward_value_param(const T &V) { return V; }
375 
376  void growAndAssign(size_t NumElts, const T &Elt) {
377  // Grow manually in case Elt is an internal reference.
378  size_t NewCapacity;
379  T *NewElts = mallocForGrow(NumElts, NewCapacity);
380  std::uninitialized_fill_n(NewElts, NumElts, Elt);
381  this->destroy_range(this->begin(), this->end());
382  takeAllocationForGrow(NewElts, NewCapacity);
383  this->set_size(NumElts);
384  }
385 
386  template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
387  // Grow manually in case one of Args is an internal reference.
388  size_t NewCapacity;
389  T *NewElts = mallocForGrow(0, NewCapacity);
390  ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
391  moveElementsForGrow(NewElts);
392  takeAllocationForGrow(NewElts, NewCapacity);
393  this->set_size(this->size() + 1);
394  return this->back();
395  }
396 
397 public:
398  void push_back(const T &Elt) {
399  const T *EltPtr = reserveForParamAndGetAddress(Elt);
400  ::new ((void *)this->end()) T(*EltPtr);
401  this->set_size(this->size() + 1);
402  }
403 
404  void push_back(T &&Elt) {
405  T *EltPtr = reserveForParamAndGetAddress(Elt);
406  ::new ((void *)this->end()) T(::std::move(*EltPtr));
407  this->set_size(this->size() + 1);
408  }
409 
410  void pop_back() {
411  this->set_size(this->size() - 1);
412  this->end()->~T();
413  }
414 };
415 
416 // Define this out-of-line to dissuade the C++ compiler from inlining it.
417 template <typename T, bool TriviallyCopyable>
419  size_t NewCapacity;
420  T *NewElts = mallocForGrow(MinSize, NewCapacity);
421  moveElementsForGrow(NewElts);
422  takeAllocationForGrow(NewElts, NewCapacity);
423 }
424 
425 // Define this out-of-line to dissuade the C++ compiler from inlining it.
426 template <typename T, bool TriviallyCopyable>
428  T *NewElts) {
429  // Move the elements over.
430  this->uninitialized_move(this->begin(), this->end(), NewElts);
431 
432  // Destroy the original elements.
433  destroy_range(this->begin(), this->end());
434 }
435 
436 // Define this out-of-line to dissuade the C++ compiler from inlining it.
437 template <typename T, bool TriviallyCopyable>
439  T *NewElts, size_t NewCapacity) {
440  // If this wasn't grown from the inline copy, deallocate the old space.
441  if (!this->isSmall())
442  free(this->begin());
443 
444  this->BeginX = NewElts;
445  this->Capacity = NewCapacity;
446 }
447 
448 /// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
449 /// method implementations that are designed to work with trivially copyable
450 /// T's. This allows using memcpy in place of copy/move construction and
451 /// skipping destruction.
452 template <typename T>
455 
456 protected:
457  /// True if it's cheap enough to take parameters by value. Doing so avoids
458  /// overhead related to mitigations for reference invalidation.
459  static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
460 
461  /// Either const T& or T, depending on whether it's cheap enough to take
462  /// parameters by value.
463  using ValueParamT =
465 
467 
468  // No need to do a destroy loop for POD's.
469  static void destroy_range(T *, T *) {}
470 
471  /// Move the range [I, E) onto the uninitialized memory
472  /// starting with "Dest", constructing elements into it as needed.
473  template<typename It1, typename It2>
474  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
475  // Just do a copy.
476  uninitialized_copy(I, E, Dest);
477  }
478 
479  /// Copy the range [I, E) onto the uninitialized memory
480  /// starting with "Dest", constructing elements into it as needed.
481  template<typename It1, typename It2>
482  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
483  // Arbitrary iterator types; just use the basic implementation.
484  std::uninitialized_copy(I, E, Dest);
485  }
486 
487  /// Copy the range [I, E) onto the uninitialized memory
488  /// starting with "Dest", constructing elements into it as needed.
489  template <typename T1, typename T2>
490  static void uninitialized_copy(
491  T1 *I, T1 *E, T2 *Dest,
492  std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
493  T2>::value> * = nullptr) {
494  // Use memcpy for PODs iterated by pointers (which includes SmallVector
495  // iterators): std::uninitialized_copy optimizes to memmove, but we can
496  // use memcpy here. Note that I and E are iterators and thus might be
497  // invalid for memcpy if they are equal.
498  if (I != E)
499  memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
500  }
501 
502  /// Double the size of the allocated memory, guaranteeing space for at
503  /// least one more element or MinSize if specified.
504  void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
505 
506  /// Reserve enough space to add one element, and return the updated element
507  /// pointer in case it was a reference to the storage.
508  const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
509  return this->reserveForParamAndGetAddressImpl(this, Elt, N);
510  }
511 
512  /// Reserve enough space to add one element, and return the updated element
513  /// pointer in case it was a reference to the storage.
514  T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
515  return const_cast<T *>(
516  this->reserveForParamAndGetAddressImpl(this, Elt, N));
517  }
518 
519  /// Copy \p V or return a reference, depending on \a ValueParamT.
521 
522  void growAndAssign(size_t NumElts, T Elt) {
523  // Elt has been copied in case it's an internal reference, side-stepping
524  // reference invalidation problems without losing the realloc optimization.
525  this->set_size(0);
526  this->grow(NumElts);
527  std::uninitialized_fill_n(this->begin(), NumElts, Elt);
528  this->set_size(NumElts);
529  }
530 
531  template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
532  // Use push_back with a copy in case Args has an internal reference,
533  // side-stepping reference invalidation problems without losing the realloc
534  // optimization.
535  push_back(T(std::forward<ArgTypes>(Args)...));
536  return this->back();
537  }
538 
539 public:
540  void push_back(ValueParamT Elt) {
541  const T *EltPtr = reserveForParamAndGetAddress(Elt);
542  memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
543  this->set_size(this->size() + 1);
544  }
545 
546  void pop_back() { this->set_size(this->size() - 1); }
547 };
548 
549 /// This class consists of common code factored out of the SmallVector class to
550 /// reduce code duplication based on the SmallVector 'N' template parameter.
551 template <typename T>
552 class SmallVectorImpl : public SmallVectorTemplateBase<T> {
553  using SuperClass = SmallVectorTemplateBase<T>;
554 
555 public:
556  using iterator = typename SuperClass::iterator;
560 
561 protected:
564 
565  // Default ctor - Initialize to empty.
566  explicit SmallVectorImpl(unsigned N)
568 
569 public:
570  SmallVectorImpl(const SmallVectorImpl &) = delete;
571 
573  // Subclass has already destructed this vector's elements.
574  // If this wasn't grown from the inline copy, deallocate the old space.
575  if (!this->isSmall())
576  free(this->begin());
577  }
578 
579  void clear() {
580  this->destroy_range(this->begin(), this->end());
581  this->Size = 0;
582  }
583 
584 private:
585  // Make set_size() private to avoid misuse in subclasses.
586  using SuperClass::set_size;
587 
588  template <bool ForOverwrite> void resizeImpl(size_type N) {
589  if (N == this->size())
590  return;
591 
592  if (N < this->size()) {
593  this->truncate(N);
594  return;
595  }
596 
597  this->reserve(N);
598  for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
599  if (ForOverwrite)
600  new (&*I) T;
601  else
602  new (&*I) T();
603  this->set_size(N);
604  }
605 
606 public:
607  void resize(size_type N) { resizeImpl<false>(N); }
608 
609  /// Like resize, but \ref T is POD, the new values won't be initialized.
610  void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
611 
612  /// Like resize, but requires that \p N is less than \a size().
614  assert(this->size() >= N && "Cannot increase size with truncate");
615  this->destroy_range(this->begin() + N, this->end());
616  this->set_size(N);
617  }
618 
620  if (N == this->size())
621  return;
622 
623  if (N < this->size()) {
624  this->truncate(N);
625  return;
626  }
627 
628  // N > this->size(). Defer to append.
629  this->append(N - this->size(), NV);
630  }
631 
633  if (this->capacity() < N)
634  this->grow(N);
635  }
636 
637  void pop_back_n(size_type NumItems) {
638  assert(this->size() >= NumItems);
639  truncate(this->size() - NumItems);
640  }
641 
643  T Result = ::std::move(this->back());
644  this->pop_back();
645  return Result;
646  }
647 
648  void swap(SmallVectorImpl &RHS);
649 
650  /// Add the specified range to the end of the SmallVector.
651  template <typename in_iter,
652  typename = std::enable_if_t<std::is_convertible<
653  typename std::iterator_traits<in_iter>::iterator_category,
654  std::input_iterator_tag>::value>>
655  void append(in_iter in_start, in_iter in_end) {
656  this->assertSafeToAddRange(in_start, in_end);
657  size_type NumInputs = std::distance(in_start, in_end);
658  this->reserve(this->size() + NumInputs);
659  this->uninitialized_copy(in_start, in_end, this->end());
660  this->set_size(this->size() + NumInputs);
661  }
662 
663  /// Append \p NumInputs copies of \p Elt to the end.
664  void append(size_type NumInputs, ValueParamT Elt) {
665  const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
666  std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
667  this->set_size(this->size() + NumInputs);
668  }
669 
670  void append(std::initializer_list<T> IL) {
671  append(IL.begin(), IL.end());
672  }
673 
674  void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
675 
676  void assign(size_type NumElts, ValueParamT Elt) {
677  // Note that Elt could be an internal reference.
678  if (NumElts > this->capacity()) {
679  this->growAndAssign(NumElts, Elt);
680  return;
681  }
682 
683  // Assign over existing elements.
684  std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
685  if (NumElts > this->size())
686  std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
687  else if (NumElts < this->size())
688  this->destroy_range(this->begin() + NumElts, this->end());
689  this->set_size(NumElts);
690  }
691 
692  // FIXME: Consider assigning over existing elements, rather than clearing &
693  // re-initializing them - for all assign(...) variants.
694 
695  template <typename in_iter,
696  typename = std::enable_if_t<std::is_convertible<
697  typename std::iterator_traits<in_iter>::iterator_category,
698  std::input_iterator_tag>::value>>
699  void assign(in_iter in_start, in_iter in_end) {
700  this->assertSafeToReferenceAfterClear(in_start, in_end);
701  clear();
702  append(in_start, in_end);
703  }
704 
705  void assign(std::initializer_list<T> IL) {
706  clear();
707  append(IL);
708  }
709 
710  void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
711 
713  // Just cast away constness because this is a non-const member function.
714  iterator I = const_cast<iterator>(CI);
715 
716  assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.");
717 
718  iterator N = I;
719  // Shift all elts down one.
720  std::move(I+1, this->end(), I);
721  // Drop the last elt.
722  this->pop_back();
723  return(N);
724  }
725 
727  // Just cast away constness because this is a non-const member function.
728  iterator S = const_cast<iterator>(CS);
729  iterator E = const_cast<iterator>(CE);
730 
731  assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.");
732 
733  iterator N = S;
734  // Shift all elts down.
735  iterator I = std::move(E, this->end(), S);
736  // Drop the last elts.
737  this->destroy_range(I, this->end());
738  this->set_size(I - this->begin());
739  return(N);
740  }
741 
742 private:
743  template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
744  // Callers ensure that ArgType is derived from T.
745  static_assert(
746  std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
747  T>::value,
748  "ArgType must be derived from T!");
749 
750  if (I == this->end()) { // Important special case for empty vector.
751  this->push_back(::std::forward<ArgType>(Elt));
752  return this->end()-1;
753  }
754 
755  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
756 
757  // Grow if necessary.
758  size_t Index = I - this->begin();
759  std::remove_reference_t<ArgType> *EltPtr =
760  this->reserveForParamAndGetAddress(Elt);
761  I = this->begin() + Index;
762 
763  ::new ((void*) this->end()) T(::std::move(this->back()));
764  // Push everything else over.
765  std::move_backward(I, this->end()-1, this->end());
766  this->set_size(this->size() + 1);
767 
768  // If we just moved the element we're inserting, be sure to update
769  // the reference (never happens if TakesParamByValue).
770  static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
771  "ArgType must be 'T' when taking by value!");
772  if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
773  ++EltPtr;
774 
775  *I = ::std::forward<ArgType>(*EltPtr);
776  return I;
777  }
778 
779 public:
780  iterator insert(iterator I, T &&Elt) {
781  return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
782  }
783 
784  iterator insert(iterator I, const T &Elt) {
785  return insert_one_impl(I, this->forward_value_param(Elt));
786  }
787 
789  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
790  size_t InsertElt = I - this->begin();
791 
792  if (I == this->end()) { // Important special case for empty vector.
793  append(NumToInsert, Elt);
794  return this->begin()+InsertElt;
795  }
796 
797  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
798 
799  // Ensure there is enough space, and get the (maybe updated) address of
800  // Elt.
801  const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
802 
803  // Uninvalidate the iterator.
804  I = this->begin()+InsertElt;
805 
806  // If there are more elements between the insertion point and the end of the
807  // range than there are being inserted, we can use a simple approach to
808  // insertion. Since we already reserved space, we know that this won't
809  // reallocate the vector.
810  if (size_t(this->end()-I) >= NumToInsert) {
811  T *OldEnd = this->end();
812  append(std::move_iterator<iterator>(this->end() - NumToInsert),
813  std::move_iterator<iterator>(this->end()));
814 
815  // Copy the existing elements that get replaced.
816  std::move_backward(I, OldEnd-NumToInsert, OldEnd);
817 
818  // If we just moved the element we're inserting, be sure to update
819  // the reference (never happens if TakesParamByValue).
820  if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
821  EltPtr += NumToInsert;
822 
823  std::fill_n(I, NumToInsert, *EltPtr);
824  return I;
825  }
826 
827  // Otherwise, we're inserting more elements than exist already, and we're
828  // not inserting at the end.
829 
830  // Move over the elements that we're about to overwrite.
831  T *OldEnd = this->end();
832  this->set_size(this->size() + NumToInsert);
833  size_t NumOverwritten = OldEnd-I;
834  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
835 
836  // If we just moved the element we're inserting, be sure to update
837  // the reference (never happens if TakesParamByValue).
838  if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
839  EltPtr += NumToInsert;
840 
841  // Replace the overwritten part.
842  std::fill_n(I, NumOverwritten, *EltPtr);
843 
844  // Insert the non-overwritten middle part.
845  std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
846  return I;
847  }
848 
849  template <typename ItTy,
850  typename = std::enable_if_t<std::is_convertible<
851  typename std::iterator_traits<ItTy>::iterator_category,
852  std::input_iterator_tag>::value>>
854  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
855  size_t InsertElt = I - this->begin();
856 
857  if (I == this->end()) { // Important special case for empty vector.
858  append(From, To);
859  return this->begin()+InsertElt;
860  }
861 
862  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
863 
864  // Check that the reserve that follows doesn't invalidate the iterators.
865  this->assertSafeToAddRange(From, To);
866 
867  size_t NumToInsert = std::distance(From, To);
868 
869  // Ensure there is enough space.
870  reserve(this->size() + NumToInsert);
871 
872  // Uninvalidate the iterator.
873  I = this->begin()+InsertElt;
874 
875  // If there are more elements between the insertion point and the end of the
876  // range than there are being inserted, we can use a simple approach to
877  // insertion. Since we already reserved space, we know that this won't
878  // reallocate the vector.
879  if (size_t(this->end()-I) >= NumToInsert) {
880  T *OldEnd = this->end();
881  append(std::move_iterator<iterator>(this->end() - NumToInsert),
882  std::move_iterator<iterator>(this->end()));
883 
884  // Copy the existing elements that get replaced.
885  std::move_backward(I, OldEnd-NumToInsert, OldEnd);
886 
887  std::copy(From, To, I);
888  return I;
889  }
890 
891  // Otherwise, we're inserting more elements than exist already, and we're
892  // not inserting at the end.
893 
894  // Move over the elements that we're about to overwrite.
895  T *OldEnd = this->end();
896  this->set_size(this->size() + NumToInsert);
897  size_t NumOverwritten = OldEnd-I;
898  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
899 
900  // Replace the overwritten part.
901  for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
902  *J = *From;
903  ++J; ++From;
904  }
905 
906  // Insert the non-overwritten middle part.
907  this->uninitialized_copy(From, To, OldEnd);
908  return I;
909  }
910 
911  void insert(iterator I, std::initializer_list<T> IL) {
912  insert(I, IL.begin(), IL.end());
913  }
914 
915  template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
916  if (LLVM_UNLIKELY(this->size() >= this->capacity()))
917  return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
918 
919  ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
920  this->set_size(this->size() + 1);
921  return this->back();
922  }
923 
925 
927 
928  bool operator==(const SmallVectorImpl &RHS) const {
929  if (this->size() != RHS.size()) return false;
930  return std::equal(this->begin(), this->end(), RHS.begin());
931  }
932  bool operator!=(const SmallVectorImpl &RHS) const {
933  return !(*this == RHS);
934  }
935 
936  bool operator<(const SmallVectorImpl &RHS) const {
937  return std::lexicographical_compare(this->begin(), this->end(),
938  RHS.begin(), RHS.end());
939  }
940 };
941 
942 template <typename T>
944  if (this == &RHS) return;
945 
946  // We can only avoid copying elements if neither vector is small.
947  if (!this->isSmall() && !RHS.isSmall()) {
948  std::swap(this->BeginX, RHS.BeginX);
949  std::swap(this->Size, RHS.Size);
950  std::swap(this->Capacity, RHS.Capacity);
951  return;
952  }
953  this->reserve(RHS.size());
954  RHS.reserve(this->size());
955 
956  // Swap the shared elements.
957  size_t NumShared = this->size();
958  if (NumShared > RHS.size()) NumShared = RHS.size();
959  for (size_type i = 0; i != NumShared; ++i)
960  std::swap((*this)[i], RHS[i]);
961 
962  // Copy over the extra elts.
963  if (this->size() > RHS.size()) {
964  size_t EltDiff = this->size() - RHS.size();
965  this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
966  RHS.set_size(RHS.size() + EltDiff);
967  this->destroy_range(this->begin()+NumShared, this->end());
968  this->set_size(NumShared);
969  } else if (RHS.size() > this->size()) {
970  size_t EltDiff = RHS.size() - this->size();
971  this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
972  this->set_size(this->size() + EltDiff);
973  this->destroy_range(RHS.begin()+NumShared, RHS.end());
974  RHS.set_size(NumShared);
975  }
976 }
977 
978 template <typename T>
981  // Avoid self-assignment.
982  if (this == &RHS) return *this;
983 
984  // If we already have sufficient space, assign the common elements, then
985  // destroy any excess.
986  size_t RHSSize = RHS.size();
987  size_t CurSize = this->size();
988  if (CurSize >= RHSSize) {
989  // Assign common elements.
990  iterator NewEnd;
991  if (RHSSize)
992  NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
993  else
994  NewEnd = this->begin();
995 
996  // Destroy excess elements.
997  this->destroy_range(NewEnd, this->end());
998 
999  // Trim.
1000  this->set_size(RHSSize);
1001  return *this;
1002  }
1003 
1004  // If we have to grow to have enough elements, destroy the current elements.
1005  // This allows us to avoid copying them during the grow.
1006  // FIXME: don't do this if they're efficiently moveable.
1007  if (this->capacity() < RHSSize) {
1008  // Destroy current elements.
1009  this->clear();
1010  CurSize = 0;
1011  this->grow(RHSSize);
1012  } else if (CurSize) {
1013  // Otherwise, use assignment for the already-constructed elements.
1014  std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
1015  }
1016 
1017  // Copy construct the new elements in place.
1018  this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
1019  this->begin()+CurSize);
1020 
1021  // Set end.
1022  this->set_size(RHSSize);
1023  return *this;
1024 }
1025 
1026 template <typename T>
1028  // Avoid self-assignment.
1029  if (this == &RHS) return *this;
1030 
1031  // If the RHS isn't small, clear this vector and then steal its buffer.
1032  if (!RHS.isSmall()) {
1033  this->destroy_range(this->begin(), this->end());
1034  if (!this->isSmall()) free(this->begin());
1035  this->BeginX = RHS.BeginX;
1036  this->Size = RHS.Size;
1037  this->Capacity = RHS.Capacity;
1038  RHS.resetToSmall();
1039  return *this;
1040  }
1041 
1042  // If we already have sufficient space, assign the common elements, then
1043  // destroy any excess.
1044  size_t RHSSize = RHS.size();
1045  size_t CurSize = this->size();
1046  if (CurSize >= RHSSize) {
1047  // Assign common elements.
1048  iterator NewEnd = this->begin();
1049  if (RHSSize)
1050  NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1051 
1052  // Destroy excess elements and trim the bounds.
1053  this->destroy_range(NewEnd, this->end());
1054  this->set_size(RHSSize);
1055 
1056  // Clear the RHS.
1057  RHS.clear();
1058 
1059  return *this;
1060  }
1061 
1062  // If we have to grow to have enough elements, destroy the current elements.
1063  // This allows us to avoid copying them during the grow.
1064  // FIXME: this may not actually make any sense if we can efficiently move
1065  // elements.
1066  if (this->capacity() < RHSSize) {
1067  // Destroy current elements.
1068  this->clear();
1069  CurSize = 0;
1070  this->grow(RHSSize);
1071  } else if (CurSize) {
1072  // Otherwise, use assignment for the already-constructed elements.
1073  std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
1074  }
1075 
1076  // Move-construct the new elements in place.
1077  this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
1078  this->begin()+CurSize);
1079 
1080  // Set end.
1081  this->set_size(RHSSize);
1082 
1083  RHS.clear();
1084  return *this;
1085 }
1086 
1087 /// Storage for the SmallVector elements. This is specialized for the N=0 case
1088 /// to avoid allocating unnecessary storage.
1089 template <typename T, unsigned N>
1091  alignas(T) char InlineElts[N * sizeof(T)];
1092 };
1093 
1094 /// We need the storage to be properly aligned even for small-size of 0 so that
1095 /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1096 /// well-defined.
1097 template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
1098 
1099 /// Forward declaration of SmallVector so that
1100 /// calculateSmallVectorDefaultInlinedElements can reference
1101 /// `sizeof(SmallVector<T, 0>)`.
1102 template <typename T, unsigned N> class LLVM_GSL_OWNER SmallVector;
1103 
1104 /// Helper class for calculating the default number of inline elements for
1105 /// `SmallVector<T>`.
1106 ///
1107 /// This should be migrated to a constexpr function when our minimum
1108 /// compiler support is enough for multi-statement constexpr functions.
1109 template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
1110  // Parameter controlling the default number of inlined elements
1111  // for `SmallVector<T>`.
1112  //
1113  // The default number of inlined elements ensures that
1114  // 1. There is at least one inlined element.
1115  // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1116  // it contradicts 1.
1117  static constexpr size_t kPreferredSmallVectorSizeof = 64;
1118 
1119  // static_assert that sizeof(T) is not "too big".
1120  //
1121  // Because our policy guarantees at least one inlined element, it is possible
1122  // for an arbitrarily large inlined element to allocate an arbitrarily large
1123  // amount of inline storage. We generally consider it an antipattern for a
1124  // SmallVector to allocate an excessive amount of inline storage, so we want
1125  // to call attention to these cases and make sure that users are making an
1126  // intentional decision if they request a lot of inline storage.
1127  //
1128  // We want this assertion to trigger in pathological cases, but otherwise
1129  // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
1130  // larger than kPreferredSmallVectorSizeof (otherwise,
1131  // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1132  // pattern seems useful in practice).
1133  //
1134  // One wrinkle is that this assertion is in theory non-portable, since
1135  // sizeof(T) is in general platform-dependent. However, we don't expect this
1136  // to be much of an issue, because most LLVM development happens on 64-bit
1137  // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
1138  // 32-bit hosts, dodging the issue. The reverse situation, where development
1139  // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
1140  // 64-bit host, is expected to be very rare.
1141  static_assert(
1142  sizeof(T) <= 256,
1143  "You are trying to use a default number of inlined elements for "
1144  "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1145  "explicit number of inlined elements with `SmallVector<T, N>` to make "
1146  "sure you really want that much inline storage.");
1147 
1148  // Discount the size of the header itself when calculating the maximum inline
1149  // bytes.
1150  static constexpr size_t PreferredInlineBytes =
1151  kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1152  static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
1153  static constexpr size_t value =
1154  NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1155 };
1156 
1157 /// This is a 'vector' (really, a variable-sized array), optimized
1158 /// for the case when the array is small. It contains some number of elements
1159 /// in-place, which allows it to avoid heap allocation when the actual number of
1160 /// elements is below that threshold. This allows normal "small" cases to be
1161 /// fast without losing generality for large inputs.
1162 ///
1163 /// \note
1164 /// In the absence of a well-motivated choice for the number of inlined
1165 /// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1166 /// omitting the \p N). This will choose a default number of inlined elements
1167 /// reasonable for allocation on the stack (for example, trying to keep \c
1168 /// sizeof(SmallVector<T>) around 64 bytes).
1169 ///
1170 /// \warning This does not attempt to be exception safe.
1171 ///
1172 /// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1173 template <typename T,
1176  SmallVectorStorage<T, N> {
1177 public:
1179 
1181  // Destroy the constructed elements in the vector.
1182  this->destroy_range(this->begin(), this->end());
1183  }
1184 
1185  explicit SmallVector(size_t Size, const T &Value = T())
1186  : SmallVectorImpl<T>(N) {
1187  this->assign(Size, Value);
1188  }
1189 
1190  template <typename ItTy,
1191  typename = std::enable_if_t<std::is_convertible<
1192  typename std::iterator_traits<ItTy>::iterator_category,
1193  std::input_iterator_tag>::value>>
1195  this->append(S, E);
1196  }
1197 
1198  template <typename RangeTy>
1200  : SmallVectorImpl<T>(N) {
1201  this->append(R.begin(), R.end());
1202  }
1203 
1204  SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1205  this->assign(IL);
1206  }
1207 
1209  if (!RHS.empty())
1211  }
1212 
1215  return *this;
1216  }
1217 
1219  if (!RHS.empty())
1221  }
1222 
1224  if (!RHS.empty())
1226  }
1227 
1230  return *this;
1231  }
1232 
1235  return *this;
1236  }
1237 
1238  SmallVector &operator=(std::initializer_list<T> IL) {
1239  this->assign(IL);
1240  return *this;
1241  }
1242 };
1243 
1244 template <typename T, unsigned N>
1245 inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1246  return X.capacity_in_bytes();
1247 }
1248 
1249 template <typename RangeType>
1250 using ValueTypeFromRangeType =
1251  typename std::remove_const<typename std::remove_reference<
1252  decltype(*std::begin(std::declval<RangeType &>()))>::type>::type;
1253 
1254 /// Given a range of type R, iterate the entire range and return a
1255 /// SmallVector with elements of the vector. This is useful, for example,
1256 /// when you want to iterate a range and then sort the results.
1257 template <unsigned Size, typename R>
1259  return {std::begin(Range), std::end(Range)};
1260 }
1261 template <typename R>
1262 SmallVector<ValueTypeFromRangeType<R>,
1263  CalculateSmallVectorDefaultInlinedElements<
1264  ValueTypeFromRangeType<R>>::value>
1265 to_vector(R &&Range) {
1266  return {std::begin(Range), std::end(Range)};
1267 }
1268 
1269 } // end namespace llvm
1270 
1271 namespace std {
1272 
1273  /// Implement std::swap in terms of SmallVector swap.
1274  template<typename T>
1275  inline void
1277  LHS.swap(RHS);
1278  }
1279 
1280  /// Implement std::swap in terms of SmallVector swap.
1281  template<typename T, unsigned N>
1282  inline void
1284  LHS.swap(RHS);
1285  }
1286 
1287 } // end namespace std
1288 
1289 #endif // LLVM_ADT_SMALLVECTOR_H
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::SmallVectorTemplateCommon::operator[]
const_reference operator[](size_type idx) const
Definition: SmallVector.h:274
i
i
Definition: README.txt:29
llvm::SmallVectorTemplateCommon::isReferenceToStorage
bool isReferenceToStorage(const void *V) const
Return true if V is an internal reference to this vector.
Definition: SmallVector.h:139
llvm::SmallVectorTemplateBase::forward_value_param
static T && forward_value_param(T &&V)
Definition: SmallVector.h:373
llvm::SmallVectorTemplateCommon::end
iterator end()
Definition: SmallVector.h:249
llvm::SmallVectorTemplateCommon::isReferenceToRange
bool isReferenceToRange(const void *V, const void *First, const void *Last) const
Return true if V is an internal reference to the given range.
Definition: SmallVector.h:132
llvm::SmallVectorImpl::SmallVectorImpl
SmallVectorImpl(unsigned N)
Definition: SmallVector.h:566
llvm::SmallVectorTemplateCommon::isRangeInStorage
bool isRangeInStorage(const void *First, const void *Last) const
Return true if First and Last form a valid (possibly empty) range in this vector's storage.
Definition: SmallVector.h:145
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:712
llvm::SmallVectorBase::Capacity
Size_T Capacity
Definition: SmallVector.h:46
llvm::SmallVectorTemplateCommon::isSafeToReferenceAfterResize
bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Return true unless Elt will be invalidated by resizing the vector to NewSize.
Definition: SmallVector.h:154
llvm::SmallVectorBase::BeginX
void * BeginX
Definition: SmallVector.h:45
llvm::SmallVector::operator=
SmallVector & operator=(SmallVectorImpl< T > &&RHS)
Definition: SmallVector.h:1233
llvm::SmallVector::SmallVector
SmallVector(SmallVectorImpl< T > &&RHS)
Definition: SmallVector.h:1223
llvm::SmallVector::SmallVector
SmallVector(std::initializer_list< T > IL)
Definition: SmallVector.h:1204
return
return
Definition: README.txt:242
llvm::SmallVectorImpl::append
void append(const SmallVectorImpl &RHS)
Definition: SmallVector.h:674
llvm::SmallVectorImpl::append
void append(size_type NumInputs, ValueParamT Elt)
Append NumInputs copies of Elt to the end.
Definition: SmallVector.h:664
llvm::SmallVectorImpl::append
void append(std::initializer_list< T > IL)
Definition: SmallVector.h:670
llvm::SmallVectorImpl::assign
void assign(std::initializer_list< T > IL)
Definition: SmallVector.h:705
llvm::SmallVectorTemplateBase< T, true >::reserveForParamAndGetAddress
const T * reserveForParamAndGetAddress(const T &Elt, size_t N=1)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
Definition: SmallVector.h:508
llvm::SmallVectorTemplateCommon::begin
const_iterator begin() const
Definition: SmallVector.h:248
llvm::SmallVectorTemplateCommon::reserveForParamAndGetAddressImpl
static const T * reserveForParamAndGetAddressImpl(U *This, const T &Elt, size_t N)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
Definition: SmallVector.h:209
offsetof
#define offsetof(TYPE, MEMBER)
Definition: AMDHSAKernelDescriptor.h:23
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1175
llvm::SmallVectorTemplateBase< T, true >::forward_value_param
static ValueParamT forward_value_param(ValueParamT V)
Copy V or return a reference, depending on ValueParamT.
Definition: SmallVector.h:520
llvm::SmallVectorTemplateBase< T, true >::grow
void grow(size_t MinSize=0)
Double the size of the allocated memory, guaranteeing space for at least one more element or MinSize ...
Definition: SmallVector.h:504
llvm::SmallVectorBase::grow_pod
void grow_pod(void *FirstEl, size_t MinSize, size_t TSize)
This is an implementation of the grow() method which only works on POD-like data types and is out of ...
Definition: SmallVector.cpp:121
llvm::SmallVectorImpl::insert
iterator insert(iterator I, ItTy From, ItTy To)
Definition: SmallVector.h:853
LLVM_GSL_OWNER
#define LLVM_GSL_OWNER
LLVM_GSL_OWNER - Apply this to owning classes like SmallVector to enable lifetime warnings.
Definition: Compiler.h:307
llvm::SmallVectorTemplateBase::destroy_range
static void destroy_range(T *S, T *E)
Definition: SmallVector.h:318
llvm::SmallVectorTemplateCommon< T >::const_iterator
const T * const_iterator
Definition: SmallVector.h:232
llvm::SmallVectorImpl::assign
void assign(const SmallVectorImpl &RHS)
Definition: SmallVector.h:710
llvm::SmallVectorTemplateBase::TakesParamByValue
static constexpr bool TakesParamByValue
Definition: SmallVector.h:313
llvm::capacity_in_bytes
BitVector::size_type capacity_in_bytes(const BitVector &X)
Definition: BitVector.h:827
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
llvm::SmallVectorTemplateBase::moveElementsForGrow
void moveElementsForGrow(T *NewElts)
Move existing elements over to the new allocation NewElts, the middle section of grow().
Definition: SmallVector.h:427
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:227
llvm::ValueTypeFromRangeType
typename std::remove_const< typename std::remove_reference< decltype(*std::begin(std::declval< RangeType & >()))>::type >::type ValueTypeFromRangeType
Definition: SmallVector.h:1252
T1
#define T1
Definition: Mips16ISelLowering.cpp:340
llvm::SmallVectorStorage
Storage for the SmallVector elements.
Definition: SmallVector.h:1090
llvm::SmallVectorTemplateCommon< T >::const_reference
const T & const_reference
Definition: SmallVector.h:238
llvm::SmallVectorTemplateCommon::resetToSmall
void resetToSmall()
Put this vector in a state of being small.
Definition: SmallVector.h:126
llvm::SmallVectorTemplateCommon::max_size
size_type max_size() const
Definition: SmallVector.h:259
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CS, const_iterator CE)
Definition: SmallVector.h:726
llvm::SmallVector::SmallVector
SmallVector()
Definition: SmallVector.h:1178
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::SmallVectorBase::Size
Size_T Size
Definition: SmallVector.h:46
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::SmallVectorTemplateCommon::back
reference back()
Definition: SmallVector.h:288
llvm::SmallVectorTemplateCommon::size_type
size_t size_type
Definition: SmallVector.h:228
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:642
llvm::SmallVectorTemplateCommon::isSmall
bool isSmall() const
Return true if this is a smallvector which has not had dynamic memory allocated for it.
Definition: SmallVector.h:123
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
llvm::SmallVectorTemplateCommon< T >::reverse_iterator
std::reverse_iterator< iterator > reverse_iterator
Definition: SmallVector.h:235
llvm::SmallVectorBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:71
llvm::SmallVectorTemplateCommon::front
reference front()
Definition: SmallVector.h:279
size_t
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::SmallVectorTemplateCommon::rbegin
reverse_iterator rbegin()
Definition: SmallVector.h:253
llvm::SmallVectorTemplateBase::growAndAssign
void growAndAssign(size_t NumElts, const T &Elt)
Definition: SmallVector.h:376
llvm::lltok::equal
@ equal
Definition: LLToken.h:25
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
llvm::SmallVectorTemplateBase::forward_value_param
static const T & forward_value_param(const T &V)
Definition: SmallVector.h:374
llvm::SmallVectorImpl::truncate
void truncate(size_type N)
Like resize, but requires that N is less than size().
Definition: SmallVector.h:613
llvm::SmallVectorBase::SizeTypeMax
static constexpr size_t SizeTypeMax()
The maximum value of the Size_T used.
Definition: SmallVector.h:49
llvm::SmallVectorTemplateCommon::data
const_pointer data() const
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:268
ptrdiff_t
llvm::SmallVector::SmallVector
SmallVector(const SmallVector &RHS)
Definition: SmallVector.h:1208
llvm::SmallVectorTemplateBase::uninitialized_move
static void uninitialized_move(It1 I, It1 E, It2 Dest)
Move the range [I, E) into the uninitialized memory starting with "Dest", constructing elements as ne...
Definition: SmallVector.h:328
llvm::SmallVectorTemplateCommon< T >::reference
T & reference
Definition: SmallVector.h:237
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:655
ItTy
llvm::SmallVectorImpl::insert
iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt)
Definition: SmallVector.h:788
llvm::SmallVectorTemplateBase::mallocForGrow
T * mallocForGrow(size_t MinSize, size_t &NewCapacity)
Create a new allocation big enough for MinSize and pass back its size in NewCapacity.
Definition: SmallVector.h:347
llvm::SmallVectorBase::size
size_t size() const
Definition: SmallVector.h:68
llvm::SmallVectorTemplateCommon< T >::value_type
T value_type
Definition: SmallVector.h:230
llvm::SmallVectorTemplateBase::grow
void grow(size_t MinSize=0)
Grow the allocated memory (without initializing new elements), doubling the size of the allocated mem...
Definition: SmallVector.h:418
llvm::SmallVectorImpl::assign
void assign(in_iter in_start, in_iter in_end)
Definition: SmallVector.h:699
llvm::SmallVector::SmallVector
SmallVector(const iterator_range< RangeTy > &R)
Definition: SmallVector.h:1199
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::SmallVectorBase::SmallVectorBase
SmallVectorBase(void *FirstEl, size_t TotalCapacity)
Definition: SmallVector.h:54
be
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can be
Definition: README.txt:14
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:607
llvm::SmallVectorTemplateBase< T, true >::push_back
void push_back(ValueParamT Elt)
Definition: SmallVector.h:540
llvm::SmallVectorTemplateCommon::rbegin
const_reverse_iterator rbegin() const
Definition: SmallVector.h:254
llvm::SmallVector::SmallVector
SmallVector(ItTy S, ItTy E)
Definition: SmallVector.h:1194
llvm::SmallVectorTemplateBase::reserveForParamAndGetAddress
T * reserveForParamAndGetAddress(T &Elt, size_t N=1)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
Definition: SmallVector.h:368
llvm::SmallVector::operator=
SmallVector & operator=(SmallVector &&RHS)
Definition: SmallVector.h:1228
llvm::SmallVectorTemplateBase< T, true >::uninitialized_move
static void uninitialized_move(It1 I, It1 E, It2 Dest)
Move the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
Definition: SmallVector.h:474
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::SmallVectorSizeType
typename std::conditional< sizeof(T)< 4 &&sizeof(void *) >=8, uint64_t, uint32_t >::type SmallVectorSizeType
Definition: SmallVector.h:87
llvm::SmallVectorTemplateCommon::end
const_iterator end() const
Definition: SmallVector.h:250
llvm::SmallVectorImpl::resize_for_overwrite
void resize_for_overwrite(size_type N)
Like resize, but T is POD, the new values won't be initialized.
Definition: SmallVector.h:610
llvm::to_vector
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
Definition: SmallVector.h:1258
llvm::SmallVectorTemplateCommon< T >::const_pointer
const T * const_pointer
Definition: SmallVector.h:240
llvm::SmallVectorTemplateCommon::rend
reverse_iterator rend()
Definition: SmallVector.h:255
llvm::SmallVectorTemplateCommon
This is the part of SmallVectorTemplateBase which does not depend on whether the type T is a POD.
Definition: SmallVector.h:100
llvm::SmallVectorImpl::operator=
SmallVectorImpl & operator=(const SmallVectorImpl &RHS)
Definition: SmallVector.h:980
llvm::SmallVectorImpl::operator==
bool operator==(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:928
llvm::SmallVectorBase::set_size
void set_size(size_t N)
Set the array size to N, which the current array must have enough capacity for.
Definition: SmallVector.h:78
llvm::SmallVectorTemplateBase::push_back
void push_back(const T &Elt)
Definition: SmallVector.h:398
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
llvm::SmallVectorTemplateBase< T, true >::uninitialized_copy
static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest, std::enable_if_t< std::is_same< typename std::remove_const< T1 >::type, T2 >::value > *=nullptr)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
Definition: SmallVector.h:490
llvm::SmallVectorBase::SmallVectorBase
SmallVectorBase()=delete
llvm::SmallVectorTemplateCommon::operator[]
reference operator[](size_type idx)
Definition: SmallVector.h:270
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
uint64_t
llvm::SmallVectorTemplateCommon::assertSafeToReferenceAfterResize
void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Check whether Elt will be invalidated by resizing the vector to NewSize.
Definition: SmallVector.h:168
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::SmallVectorTemplateCommon::grow_pod
void grow_pod(size_t MinSize, size_t TSize)
Definition: SmallVector.h:117
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SmallVectorTemplateBase< T, true >::growAndEmplaceBack
T & growAndEmplaceBack(ArgTypes &&... Args)
Definition: SmallVector.h:531
llvm::SmallVectorImpl< llvm::VectorizationFactor >::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:557
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1707
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:852
memcpy
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
llvm::SmallVectorImpl::resize
void resize(size_type N, ValueParamT NV)
Definition: SmallVector.h:619
iterator_range.h
llvm::SmallVectorTemplateCommon::rend
const_reverse_iterator rend() const
Definition: SmallVector.h:256
llvm::SmallVectorTemplateBase::takeAllocationForGrow
void takeAllocationForGrow(T *NewElts, size_t NewCapacity)
Transfer ownership of the allocation, finishing up grow().
Definition: SmallVector.h:438
llvm::SmallVectorTemplateCommon::data
pointer data()
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:266
llvm::SmallVectorTemplateBase< T, true >::pop_back
void pop_back()
Definition: SmallVector.h:546
llvm::SmallVectorTemplateBase::growAndEmplaceBack
T & growAndEmplaceBack(ArgTypes &&... Args)
Definition: SmallVector.h:386
llvm::SmallVectorTemplateCommon::size_in_bytes
size_type size_in_bytes() const
Definition: SmallVector.h:258
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1630
llvm::SmallVector::SmallVector
SmallVector(SmallVector &&RHS)
Definition: SmallVector.h:1218
llvm::SmallVectorTemplateBase::push_back
void push_back(T &&Elt)
Definition: SmallVector.h:404
llvm::SmallVectorTemplateCommon::begin
iterator begin()
Definition: SmallVector.h:247
llvm::SmallVectorTemplateCommon::assertSafeToReferenceAfterClear
void assertSafeToReferenceAfterClear(ItTy, ItTy)
Definition: SmallVector.h:191
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
llvm::SmallVectorTemplateCommon::front
const_reference front() const
Definition: SmallVector.h:283
llvm::SmallVectorImpl::~SmallVectorImpl
~SmallVectorImpl()
Definition: SmallVector.h:572
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
uint32_t
Compiler.h
llvm::SmallVectorTemplateCommon< T >::iterator
T * iterator
Definition: SmallVector.h:231
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
SmallVectorSizeType< T >
llvm::SmallVectorImpl::operator!=
bool operator!=(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:932
llvm::SmallVectorTemplateCommon::assertSafeToAdd
void assertSafeToAdd(const void *Elt, size_t N=1)
Check whether Elt will be invalidated by increasing the size of the vector by N.
Definition: SmallVector.h:176
llvm::SmallVectorTemplateCommon::capacity_in_bytes
size_t capacity_in_bytes() const
Definition: SmallVector.h:263
llvm::SmallVector::~SmallVector
~SmallVector()
Definition: SmallVector.h:1180
llvm::SmallVectorTemplateBase::ValueParamT
const T & ValueParamT
Definition: SmallVector.h:314
llvm::SmallVectorTemplateBase< T, true >::growAndAssign
void growAndAssign(size_t NumElts, T Elt)
Definition: SmallVector.h:522
llvm::SmallVectorTemplateCommon< T >::const_reverse_iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: SmallVector.h:234
std
Definition: BitVector.h:850
llvm::SmallVectorImpl::swap
void swap(SmallVectorImpl &RHS)
Definition: SmallVector.h:943
type_traits.h
llvm::SmallVectorImpl::assign
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:676
llvm::SmallVectorTemplateBase::uninitialized_copy
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements as ne...
Definition: SmallVector.h:336
llvm::SmallVectorAlignmentAndSize
Figure out the offset of the first element.
Definition: SmallVector.h:90
llvm::SmallVectorTemplateCommon< T >::pointer
T * pointer
Definition: SmallVector.h:239
llvm::SmallVectorTemplateCommon::assertSafeToReferenceAfterClear
void assertSafeToReferenceAfterClear(const T *From, const T *To)
Check whether any part of the range will be invalidated by clearing.
Definition: SmallVector.h:181
llvm::SmallVectorTemplateBase< T, true >::destroy_range
static void destroy_range(T *, T *)
Definition: SmallVector.h:469
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:165
llvm::SmallVectorImpl::insert
iterator insert(iterator I, const T &Elt)
Definition: SmallVector.h:784
llvm::SmallVectorImpl< llvm::VectorizationFactor >::ValueParamT
typename SuperClass::ValueParamT ValueParamT
Definition: SmallVector.h:563
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:579
llvm::SmallVectorTemplateCommon::assertSafeToAddRange
void assertSafeToAddRange(const T *From, const T *To)
Check whether any part of the range will be invalidated by growing.
Definition: SmallVector.h:194
llvm::SmallVectorBase::capacity
size_t capacity() const
Definition: SmallVector.h:69
This
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical This
Definition: README.txt:418
llvm::CalculateSmallVectorDefaultInlinedElements
Helper class for calculating the default number of inline elements for SmallVector<T>.
Definition: SmallVector.h:1109
SuperClass
llvm::SmallVectorImpl::pop_back_n
void pop_back_n(size_type NumItems)
Definition: SmallVector.h:637
llvm::SmallVectorTemplateCommon::SmallVectorTemplateCommon
SmallVectorTemplateCommon(size_t Size)
Definition: SmallVector.h:115
llvm::SmallVectorTemplateBase< T, true >::reserveForParamAndGetAddress
T * reserveForParamAndGetAddress(T &Elt, size_t N=1)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
Definition: SmallVector.h:514
llvm::SmallVector::operator=
SmallVector & operator=(std::initializer_list< T > IL)
Definition: SmallVector.h:1238
llvm::SmallVectorImpl< llvm::VectorizationFactor >::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:556
N
#define N
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
LLVM_LIKELY
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:229
llvm::SmallVectorTemplateBase::reserveForParamAndGetAddress
const T * reserveForParamAndGetAddress(const T &Elt, size_t N=1)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
Definition: SmallVector.h:362
llvm::SmallVectorImpl< llvm::VectorizationFactor >::size_type
typename SuperClass::size_type size_type
Definition: SmallVector.h:559
llvm::SmallVectorTemplateBase::SmallVectorTemplateBase
SmallVectorTemplateBase(size_t Size)
Definition: SmallVector.h:316
llvm::SmallVector::SmallVector
SmallVector(size_t Size, const T &Value=T())
Definition: SmallVector.h:1185
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::SmallVectorImpl::insert
void insert(iterator I, std::initializer_list< T > IL)
Definition: SmallVector.h:911
llvm::SmallVectorTemplateBase< T, true >::SmallVectorTemplateBase
SmallVectorTemplateBase(size_t Size)
Definition: SmallVector.h:466
llvm::SmallVectorTemplateBase< T, true >::ValueParamT
typename std::conditional< TakesParamByValue, T, const T & >::type ValueParamT
Either const T& or T, depending on whether it's cheap enough to take parameters by value.
Definition: SmallVector.h:464
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
LLVM_UNLIKELY
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:230
llvm::SmallVectorAlignmentAndSize::FirstEl
char FirstEl[sizeof(T)]
Definition: SmallVector.h:93
llvm::SmallVectorAlignmentAndSize::Base
char Base[sizeof(SmallVectorBase< SmallVectorSizeType< T >>)]
Definition: SmallVector.h:92
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:632
llvm::SmallVectorBase
This is all the stuff common to all SmallVectors.
Definition: SmallVector.h:43
llvm::SmallVectorBase::mallocForGrow
void * mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity)
This is a helper for grow() that's out of line to reduce code duplication.
Definition: SmallVector.cpp:113
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101
llvm::SmallVector::operator=
SmallVector & operator=(const SmallVector &RHS)
Definition: SmallVector.h:1213
llvm::SmallVectorTemplateBase::pop_back
void pop_back()
Definition: SmallVector.h:410
llvm::SmallVectorImpl::operator<
bool operator<(const SmallVectorImpl &RHS) const
Definition: SmallVector.h:936
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::SmallVectorImpl< llvm::VectorizationFactor >::reference
typename SuperClass::reference reference
Definition: SmallVector.h:558
llvm::iterator_range::begin
IteratorT begin() const
Definition: iterator_range.h:44
llvm::SmallVectorTemplateBase< T, true >::uninitialized_copy
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
Definition: SmallVector.h:482
llvm::SmallVectorTemplateBase
SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put method implementations that...
Definition: SmallVector.h:309
llvm::SmallVectorTemplateCommon::assertSafeToAddRange
void assertSafeToAddRange(ItTy, ItTy)
Definition: SmallVector.h:204
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:915
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:780
llvm::SmallVectorTemplateCommon::back
const_reference back() const
Definition: SmallVector.h:292