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