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