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