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