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