ADT: Take small enough, trivially copyable T by value in SmallVector

[dexonsmith]

Summary

Change SmallVector functions taking a const T& parameter for
insertion to take T instead when T is trivially copyable and "small
enough" (the heuristic is sizeof(T) <= 2 * sizeof(void *)). When it
applies it avoids iterator invalidation gotchas.

For insert, layer insert_one_maybe_copy between insert and
insert_one_impl in order to copy Elt when we want to take it by
value.

For emplace_back, forward to push_back when we want to take the
parameter by value.

Note: the intent here is to help unblock https://reviews.llvm.org/D87326:

In D87326#2352570, @njames93 wrote:

Overhead is likely caused by slightly more code needing to be emitted. However there is a glaring hole here that SmallVector isn't very smart about how it should take paramaters for calls like push_back.
For small trivial types it makes sense to take those by value and in those instances the current implementation of just calling grow would have no issue about reference invalidation as there no longer a reference.
Downside is it would require copying most of the small vector implementation code for this special case, kind of like what currently happens for SmallVectorTemplateBase with trivially copyable types.

Given that a lot of use cases of SmallVector seem to be for storing pointers or as the base class for SmallString, this would remove this specific overhead in these cases.

[dexonsmith]

This is from an idea @njames93 posted in https://reviews.llvm.org/D87326. I've just built/run SupportTests; can/will run check-all and/or write extra tests if others think this is worth committing.

See also https://reviews.llvm.org/D84293 which is in the same space.

[njames93]

llvm/include/llvm/ADT/SmallVector.h

349

In relation to my comment about insert, it would be a lot easier to implement if this condition was extracted out into a static constexpr variable

static constexpr bool IsPushByVal = sizeof(T) <= 16;

A second point is maybe this should be based loosely on the target. Though I'm not super sure on that, WDYT?

sizeof(T) <= 2 * sizeof(void*)

637–642

This code is redundant if Elt is passed by value, however I don't think all(or any) compilers are smart enough to see that, wrapping this around an if block dependent on whether Elt is passed by ref would in all likelihood be a win. Same goes for the other call to insert below.

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

637–642

Good point; I’ll update on Monday.

[silvas]

Do you have any performance and binary size results? I suspect that these are frequently just inlined + sroa'd so this won't make much of a difference in the end.

llvm/include/llvm/ADT/SmallVector.h

349

+1, I think that basing it on sizeof(void*) probably makes sense.

[mehdi_amini]

Won't we end up with a different behavior (with respect to iterator invalidation) based on the platform?

[dexonsmith]

Updates:

• Switched size limit to 2 * sizeof(void *).
• Rebased on top of 2c196bbc6bd897b3dcc1d87a3baac28e1e88df41.
• Added assertions catching invalidation when the by-value optimization doesn't kick in.
• Added tests.

Note that the new assertions caught a bug in llvm/utils/TableGen/CodeGenSchedule.cpp and I found another related one by chance (not caught by these assertions though, since emplace_back is opaque). I'm still building, so once the tests run I assume there will be a number of other failures.

[dexonsmith]

In D91467#2395394, @mehdi_amini wrote:

Won't we end up with a different behavior (with respect to iterator invalidation) based on the platform?

Yes; that's true of both choices so far (<= 2 * sizeof(void *) and <= 16). It's not ideal, but maybe it's better than the status quo? Curious if you have an idea for something that would be stable.

A third option that doesn't change behaviour per platform is to always take by-value when it's trivially copyable. Not sure how much that pessimizes large T.

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

349

BTW, the updated patch takes both of these suggestions.

637–642

Updated patch covers this.

[dexonsmith]

In D91467#2400888, @dexonsmith wrote:

Note that the new assertions caught a bug in llvm/utils/TableGen/CodeGenSchedule.cpp and I found another related one by chance (not caught by these assertions though, since emplace_back is opaque). I'm still building, so once the tests run I assume there will be a number of other failures.

Actually, that was it. Probably helps that for small T the invalidation was "fixed". Maybe there would be more failures on 32-bit platforms, and/or on a bootstrap; I'll run a bootstrap before committing but don't want to spend the time if this is DOA anyway.

In D91467#2395340, @silvas wrote:

Do you have any performance and binary size results?

Nope, happy to collect something though. What do you think we need to see?

Note that right now the "fix invalidation" and "assert if invalid" are tied together in the same patch. Of course they're separable, but I'd be tempted to keep them together if there's a path to landing both. But if the optimization is DOA, I imagine we'd still want the assertion (and fixes for any extra assertion failures).

[silvas]

In D91467#2401023, @dexonsmith wrote:

In D91467#2400888, @dexonsmith wrote:

Note that the new assertions caught a bug in llvm/utils/TableGen/CodeGenSchedule.cpp and I found another related one by chance (not caught by these assertions though, since emplace_back is opaque). I'm still building, so once the tests run I assume there will be a number of other failures.

Actually, that was it. Probably helps that for small T the invalidation was "fixed". Maybe there would be more failures on 32-bit platforms, and/or on a bootstrap; I'll run a bootstrap before committing but don't want to spend the time if this is DOA anyway.

In D91467#2395340, @silvas wrote:

Do you have any performance and binary size results?

Nope, happy to collect something though. What do you think we need to see?

Note that right now the "fix invalidation" and "assert if invalid" are tied together in the same patch. Of course they're separable, but I'd be tempted to keep them together if there's a path to landing both. But if the optimization is DOA, I imagine we'd still want the assertion (and fixes for any extra assertion failures).

I think we can probably get a good signal from:

1. Clang execution time compiling some cpp file at by-value thresholds of 0, 1 * sizeof(void*), 2 * sizeof(void*) would be enough to get a signal on whether this is measurable performance wise.
2. Clang binary size for those 3 cases.

[dexonsmith]

Rebase on top of https://reviews.llvm.org/D91674, which streamlines insert, and handle emplace_back in a similar way.

[dexonsmith]

In D91467#2401127, @silvas wrote:

I think we can probably get a good signal from:

1. Clang execution time compiling some cpp file at by-value thresholds of 0, 1 * sizeof(void*), 2 * sizeof(void*) would be enough to get a signal on whether this is measurable performance wise.
2. Clang binary size for those 3 cases.

That sounds good. I'll throw in a version with no threshold.

[dexonsmith]

In D91467#2401471, @dexonsmith wrote:

In D91467#2401127, @silvas wrote:

I think we can probably get a good signal from:

1. Clang execution time compiling some cpp file at by-value thresholds of 0, 1 * sizeof(void*), 2 * sizeof(void*) would be enough to get a signal on whether this is measurable performance wise.
2. Clang binary size for those 3 cases.

That sounds good. I'll throw in a version with no threshold.

Results of du -k path/to/clang followed by timing to compile llvm/lib/Target/X86/X86ISelLowering.cpp three times in a row:

116216	threshold-0/build/bin/clang-12
       30.31 real        29.96 user         0.34 sys
       30.10 real        29.77 user         0.31 sys
       30.48 real        30.15 user         0.32 sys
116200	threshold-1-ptr/build/bin/clang-12
       30.58 real        30.23 user         0.33 sys
       30.17 real        29.79 user         0.37 sys
       30.28 real        29.94 user         0.33 sys
116184	threshold-2-ptr/build/bin/clang-12
       30.15 real        29.85 user         0.30 sys
       29.98 real        29.66 user         0.31 sys
       30.02 real        29.70 user         0.32 sys
116216	threshold-none/build/bin/clang-12
       30.15 real        29.83 user         0.31 sys
       30.16 real        29.82 user         0.34 sys
       30.21 real        29.90 user         0.30 sys

Sizes are all really close, around 116MB. Best of three runs for user time seems to favour 2 * sizeof(void *) very slightly, but I'm not sure it's significant:

• 29.77s: threshold of 0 (never by-value)
• 29.79s: threshold of sizeof(void*)
• 29.66s: threshold of 2 * sizeof(void*)
• 29.82s: no threshold (always by-value when trivially copyable)

Happy to collect more data if that's useful.

[dexonsmith]

Update: I decided to split out the assertions to https://reviews.llvm.org/D91744 after all. This is just rebasing on top of that.

[dexonsmith]

Rebase.

[mehdi_amini]

Can you make more clear in the description the motivation for this patch? Is this mostly about iterator invalidation? Is this expected to make code safer?
I'm not sure about making the mental model a bit harder by having different iterator invalidation behavior implicitly based on T, WDYT?

[dexonsmith]

In D91467#2404305, @mehdi_amini wrote:

Can you make more clear in the description the motivation for this patch? Is this mostly about iterator invalidation? Is this expected to make code safer?

Oh, I did this because I happened upon this comment in https://reviews.llvm.org/D87326:

In D87326#2352570, @njames93 wrote:

Overhead is likely caused by slightly more code needing to be emitted. However there is a glaring hole here that SmallVector isn't very smart about how it should take paramaters for calls like push_back.
For small trivial types it makes sense to take those by value and in those instances the current implementation of just calling grow would have no issue about reference invalidation as there no longer a reference.
Downside is it would require copying most of the small vector implementation code for this special case, kind of like what currently happens for SmallVectorTemplateBase with trivially copyable types.

Given that a lot of use cases of SmallVector seem to be for storing pointers or as the base class for SmallString, this would remove this specific overhead in these cases.

I can update the description to be more clear if we decide I should commit this.

I'm not sure about making the mental model a bit harder by having different iterator invalidation behavior implicitly based on T, WDYT?

I'm not sure either, but I think it's worth doing if it unblocks @njames93's broader fix for iterator invalidation (at which point the mental model is simple again). @njames93 , WDYT?

[mehdi_amini]

Oh I didn't read about https://reviews.llvm.org/D87326 before, isn't the work there making obsolete all of the assertions you (and me before) just added by making this behavior safe?

[dexonsmith]

In D91467#2404392, @mehdi_amini wrote:

Oh I didn't read about https://reviews.llvm.org/D87326 before, isn't the work there making obsolete all of the assertions you (and me before) just added by making this behavior safe?

Yes, but that revision is blocked on landing due to compile-time regressions. It needs some number of commits to land first; maybe this is one of them; and I couldn't figure out how to test this one reasonably without adding the assertions; and it seems reasonable to fix existing bugs (with the assertions) while we wait for the beautiful future in case it doesn't come tomorrow.

Making @njames93 a blocking reviewer since I think we shouldn't move forward unless there appears to be a path to fixing invalidation generally (this seems like a useful incremental step, but I agree with @mehdi_amini that if things stop here the mental model is confusing for little gain).

[njames93]

In D91467#2404392, @mehdi_amini wrote:

Oh I didn't read about https://reviews.llvm.org/D87326 before, isn't the work there making obsolete all of the assertions you (and me before) just added by making this behavior safe?

Assertions are great now as a quick fix, however if we can get to the point where SmallVector is able to handle those cases without the compile time regressions observed in D87326 we should strive to use that instead.
It removes contracts that are only enforced in assertion enabled builds which have the potential to cause undefined behaviour in release builds if they slip through the cracks.

[silvas]

In D91467#2401683, @dexonsmith wrote:

Results of du -k path/to/clang followed by timing to compile llvm/lib/Target/X86/X86ISelLowering.cpp three times in a row:

116216	threshold-0/build/bin/clang-12
       30.31 real        29.96 user         0.34 sys
       30.10 real        29.77 user         0.31 sys
       30.48 real        30.15 user         0.32 sys
116200	threshold-1-ptr/build/bin/clang-12
       30.58 real        30.23 user         0.33 sys
       30.17 real        29.79 user         0.37 sys
       30.28 real        29.94 user         0.33 sys
116184	threshold-2-ptr/build/bin/clang-12
       30.15 real        29.85 user         0.30 sys
       29.98 real        29.66 user         0.31 sys
       30.02 real        29.70 user         0.32 sys
116216	threshold-none/build/bin/clang-12
       30.15 real        29.83 user         0.31 sys
       30.16 real        29.82 user         0.34 sys
       30.21 real        29.90 user         0.30 sys

Sizes are all really close, around 116MB. Best of three runs for user time seems to favour 2 * sizeof(void *) very slightly, but I'm not sure it's significant:

• 29.77s: threshold of 0 (never by-value)
• 29.79s: threshold of sizeof(void*)
• 29.66s: threshold of 2 * sizeof(void*)
• 29.82s: no threshold (always by-value when trivially copyable)

Happy to collect more data if that's useful.

Thanks! Looks in the noise. I guess inline+SROA really does clean it up very consistently :)

I don't have any objections to this patch. (It sounds like this ties into another workstream, so I'll let other folks give the final sign-off)

[dexonsmith]

Thanks! Looks in the noise. I guess inline+SROA really does clean it up very consistently :)

I don't have any objections to this patch. (It sounds like this ties into another workstream, so I'll let other folks give the final sign-off)

Thanks for the review!

I'm still a bit concerned about the point Mehdi brought up. I've posted an alternative at https://reviews.llvm.org/D91837 which breaks down the problem in a different way; if that doesn't work out (e.g., lots of perf regressions) I'll circle back here.

[dexonsmith]

Abandoning this in favour of:

• https://reviews.llvm.org/D93777
• https://reviews.llvm.org/D93779
• https://reviews.llvm.org/D93780
• https://reviews.llvm.org/D93781

(which are split out from https://reviews.llvm.org/D91837)

The new work fixes reference invalidation for most of the same APIs (skipping emplace_back so far) but for all T.

llvm/include/llvm/ADT/SmallVector.h

protected:
   bool isSmall() const { return this->BeginX == getFirstEl(); }
 
   /// Put this vector in a state of being small.
   void resetToSmall() {
     this->BeginX = getFirstEl();
     this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
   }
 
-  void assertSafeToPush(const void *Elt) {
-    assert(
-        (Elt < begin() || Elt >= end() || this->size() < this->capacity()) &&
-        "Attempting to push_back to the vector an element of the vector without"
-        " enough space reserved");
+  /// Check whether Elt will be invalidated by resizing the vector to NewSize.
+  void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
+    assert((Elt >= this->end() ||
+            (NewSize <= this->size()
+                 ? Elt < this->begin() + NewSize
+                 : (Elt < this->begin() || NewSize <= this->capacity()))) &&
+           "Attempting to reference an element of the vector in an operation "
+           "that invalidates it");
+  }
+
+  /// Check whether Elt will be invalidated by increasing the size of the
+  /// vector by N.
+  void assertSafeToAdd(const void *Elt, size_t N = 1) {
+    return this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
   }
 
 public:
   using size_type = size_t;
   using difference_type = ptrdiff_t;
   using value_type = T;
   using iterator = T *;
   using const_iterator = const T *;

 /// trivial destruction. While the standard doesn't specify that you're allowed
 /// copy these types with memcpy, there is no way for the type to observe this.
 /// This catches the important case of std::pair<POD, POD>, which is not
 /// trivially assignable.
 template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
                              (is_trivially_move_constructible<T>::value) &&
                              std::is_trivially_destructible<T>::value>
 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
+public:
+  /// Take parameters by reference (not by value) since T is not trivially
+  /// copyable.
+  static constexpr bool TakesParamByValue = false;
+
 protected:
+  using ValueParamT = const T &;
+
   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
 
   static void destroy_range(T *S, T *E) {
     while (S != E) {
       --E;
       E->~T();
     }
   }
protected:
   }
 
   /// Grow the allocated memory (without initializing new elements), doubling
   /// the size of the allocated memory. Guarantees space for at least one more
   /// element, or MinSize more elements if specified.
   void grow(size_t MinSize = 0);
 
 public:
-  void push_back(const T &Elt) {
-    this->assertSafeToPush(&Elt);
+  void push_back(ValueParamT Elt) {
+    if (!TakesParamByValue)
+      this->assertSafeToAdd(&Elt);
     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     ::new ((void*) this->end()) T(Elt);
     this->set_size(this->size() + 1);
   }
 
   void push_back(T &&Elt) {
-    this->assertSafeToPush(&Elt);
+    this->assertSafeToAdd(&Elt);
     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     ::new ((void*) this->end()) T(::std::move(Elt));
     this->set_size(this->size() + 1);
   }
 
   void pop_back() {
     this->set_size(this->size() - 1);

 }
 
 /// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
 /// method implementations that are designed to work with trivially copyable
 /// T's. This allows using memcpy in place of copy/move construction and
 /// skipping destruction.
 template <typename T>
 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
+public:
+  /// Take parameters by value when T is small since it's trivially copyable.
+  static constexpr bool TakesParamByValue =
+      std::conditional<sizeof(T) <= 2 * sizeof(void *), std::true_type,
+                       std::false_type>::type::value;
+
 protected:
+  using ValueParamT =
+      typename std::conditional<TakesParamByValue, T, const T &>::type;
+
   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
 
   // No need to do a destroy loop for POD's.
   static void destroy_range(T *, T *) {}
 
   /// Move the range [I, E) onto the uninitialized memory
   /// starting with "Dest", constructing elements into it as needed.
   template<typename It1, typename It2>
   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
if (I != E)
       memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
   }
 
   /// Double the size of the allocated memory, guaranteeing space for at
   /// least one more element or MinSize if specified.
   void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
 
 public:
-  void push_back(const T &Elt) {
-    this->assertSafeToPush(&Elt);
+  void push_back(ValueParamT Elt) {
+    if (!TakesParamByValue)
+      this->assertSafeToAdd(&Elt);
     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
     this->set_size(this->size() + 1);
   }
 
   void pop_back() { this->set_size(this->size() - 1); }
 };
 
 /// This class consists of common code factored out of the SmallVector class to
 /// reduce code duplication based on the SmallVector 'N' template parameter.
 template <typename T>
 class SmallVectorImpl : public SmallVectorTemplateBase<T> {
   using SuperClass = SmallVectorTemplateBase<T>;
 
 public:
   using iterator = typename SuperClass::iterator;
   using const_iterator = typename SuperClass::const_iterator;
   using reference = typename SuperClass::reference;
   using size_type = typename SuperClass::size_type;
 
+  using SmallVectorTemplateBase<T>::TakesParamByValue;
+
 protected:
+  using ValueParamT = typename SmallVectorTemplateBase<T>::ValueParamT;
+
   // Default ctor - Initialize to empty.
   explicit SmallVectorImpl(unsigned N)
       : SmallVectorTemplateBase<T>(N) {}
 
 public:
   SmallVectorImpl(const SmallVectorImpl &) = delete;
 
   ~SmallVectorImpl() {
if (N < this->size()) {
       if (this->capacity() < N)
         this->grow(N);
       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
         new (&*I) T();
       this->set_size(N);
     }
   }
 
-  void resize(size_type N, const T &NV) {
+  void resize(size_type N, ValueParamT NV) {
+    if (!TakesParamByValue)
+      this->assertSafeToReferenceAfterResize(&NV, N);
     if (N < this->size()) {
       this->destroy_range(this->begin()+N, this->end());
       this->set_size(N);
     } else if (N > this->size()) {
       if (this->capacity() < N)
         this->grow(N);
       std::uninitialized_fill(this->end(), this->begin()+N, NV);
       this->set_size(N);
void append(in_iter in_start, in_iter in_end) {
     if (NumInputs > this->capacity() - this->size())
       this->grow(this->size()+NumInputs);
 
     this->uninitialized_copy(in_start, in_end, this->end());
     this->set_size(this->size() + NumInputs);
   }
 
   /// Append \p NumInputs copies of \p Elt to the end.
-  void append(size_type NumInputs, const T &Elt) {
+  void append(size_type NumInputs, ValueParamT Elt) {
+    if (!TakesParamByValue)
+      this->assertSafeToAdd(&Elt, NumInputs);
     if (NumInputs > this->capacity() - this->size())
       this->grow(this->size()+NumInputs);
 
     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
     this->set_size(this->size() + NumInputs);
   }
 
   void append(std::initializer_list<T> IL) {
     append(IL.begin(), IL.end());
   }
 
   // FIXME: Consider assigning over existing elements, rather than clearing &
   // re-initializing them - for all assign(...) variants.
 
-  void assign(size_type NumElts, const T &Elt) {
+  void assign(size_type NumElts, ValueParamT Elt) {
+    if (!TakesParamByValue)
+      this->assertSafeToReferenceAfterResize(&Elt, 0);
     clear();
     if (this->capacity() < NumElts)
       this->grow(NumElts);
     this->set_size(NumElts);
     std::uninitialized_fill(this->begin(), this->end(), Elt);
   }
 
   template <typename in_iter,
iterator erase(const_iterator CS, const_iterator CE) {
     // Shift all elts down.
     iterator I = std::move(E, this->end(), S);
     // Drop the last elts.
     this->destroy_range(I, this->end());
     this->set_size(I - this->begin());
     return(N);
   }
 
-  iterator insert(iterator I, T &&Elt) {
+  // Use a mock template argument to allow use of enable_if for disabling this
+  // version of insert when ValueParamT is the same as T.
+  template <class IteratorT>
+  iterator insert(IteratorT I1, T &&Elt,
+                  typename std::enable_if_t<
+                      std::is_convertible<IteratorT, iterator>::value &&
+                      !TakesParamByValue> * = 0) {
+    iterator I = I1;
     if (I == this->end()) {  // Important special case for empty vector.
       this->push_back(::std::move(Elt));
       return this->end()-1;
     }
 
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
+    // Check that adding an element won't invalidate Elt.
+    if (!TakesParamByValue)
+      this->assertSafeToAdd(&Elt);
+
     if (this->size() >= this->capacity()) {
       size_t EltNo = I-this->begin();
       this->grow();
       I = this->begin()+EltNo;
     }
 
     ::new ((void*) this->end()) T(::std::move(this->back()));
     // Push everything else over.
     std::move_backward(I, this->end()-1, this->end());
     this->set_size(this->size() + 1);
 
     // If we just moved the element we're inserting, be sure to update
     // the reference.
     T *EltPtr = &Elt;
     if (I <= EltPtr && EltPtr < this->end())
       ++EltPtr;
 
     *I = ::std::move(*EltPtr);
     return I;
   }
 
-  iterator insert(iterator I, const T &Elt) {
+  iterator insert(iterator I, ValueParamT Elt) {
     if (I == this->end()) {  // Important special case for empty vector.
       this->push_back(Elt);
       return this->end()-1;
     }
 
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
+    // Check that adding an element won't invalidate Elt.
+    if (!TakesParamByValue)
+      this->assertSafeToAdd(&Elt);
+
     if (this->size() >= this->capacity()) {
       size_t EltNo = I-this->begin();
       this->grow();
       I = this->begin()+EltNo;
     }
     ::new ((void*) this->end()) T(std::move(this->back()));
     // Push everything else over.
     std::move_backward(I, this->end()-1, this->end());
     this->set_size(this->size() + 1);
 
     // If we just moved the element we're inserting, be sure to update
-    // the reference.
+    // the reference. The check for TakesParamByValue is redundant but can
+    // be resolved at compile-time.
     const T *EltPtr = &Elt;
-    if (I <= EltPtr && EltPtr < this->end())
+    if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
       ++EltPtr;
 
     *I = *EltPtr;
     return I;
   }
 
-  iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
+  iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
     size_t InsertElt = I - this->begin();
 
     if (I == this->end()) {  // Important special case for empty vector.
       append(NumToInsert, Elt);
       return this->begin()+InsertElt;
     }
 
     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     assert(I <= this->end() && "Inserting past the end of the vector.");
 
+    // Check that adding NumToInsert elements won't invalidate Elt.
+    if (!TakesParamByValue)
+      this->assertSafeToAdd(&Elt, NumToInsert);
+
     // Ensure there is enough space.
     reserve(this->size() + NumToInsert);
 
     // Uninvalidate the iterator.
     I = this->begin()+InsertElt;
 
     // If there are more elements between the insertion point and the end of the
     // range than there are being inserted, we can use a simple approach to

 /// elements is below that threshold.  This allows normal "small" cases to be
 /// fast without losing generality for large inputs.
 ///
 /// Note that this does not attempt to be exception safe.
 ///
 template <typename T, unsigned N>
 class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>,
                                    SmallVectorStorage<T, N> {
+  using ValueParamT = typename SmallVectorImpl<T>::ValueParamT;
+
 public:
   SmallVector() : SmallVectorImpl<T>(N) {}
 
   ~SmallVector() {
     // Destroy the constructed elements in the vector.
     this->destroy_range(this->begin(), this->end());
   }
 
-  explicit SmallVector(size_t Size, const T &Value = T())
+  explicit SmallVector(size_t Size, ValueParamT Value = T())
       : SmallVectorImpl<T>(N) {
     this->assign(Size, Value);
   }
 
   template <typename ItTy,
             typename = std::enable_if_t<std::is_convertible<
                 typename std::iterator_traits<ItTy>::iterator_category,
                 std::input_iterator_tag>::value>>
   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {

llvm/unittests/ADT/SmallVectorTest.cpp

TYPED_TEST(SmallVectorTest, PushPopTest) {
   this->assertValuesInOrder(this->theVector, 1u, 1);
   EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
   EXPECT_FALSE(this->theVector.empty());
 
   // Push another element
   this->theVector.push_back(Constructable(2));
   this->assertValuesInOrder(this->theVector, 2u, 1, 2);
 
-  // Insert at beginning
+  // Insert at beginning. Take a copy when necessary to avoid having the
+  // element invalidated by growth.
+  if (this->theVector.capacity() < 3)
+    this->theVector.insert(this->theVector.begin(),
+                           Constructable(this->theVector[1]));
+  else
     this->theVector.insert(this->theVector.begin(), this->theVector[1]);
   this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
 
   // Pop one element
   this->theVector.pop_back();
   this->assertValuesInOrder(this->theVector, 2u, 2, 1);
 
   // Pop remaining elements
   this->theVector.pop_back_n(2);
TEST(SmallVectorTest, InitializerList) {
   V2.assign({4});
   EXPECT_TRUE(makeArrayRef(V2).equals({4}));
   V2.append({3, 2});
   EXPECT_TRUE(makeArrayRef(V2).equals({4, 3, 2}));
   V2.insert(V2.begin() + 1, 5);
   EXPECT_TRUE(makeArrayRef(V2).equals({4, 5, 3, 2}));
 }
 
+template <class VectorT>
+class SmallVectorTakesParameterByValueTest : public SmallVectorTestBase {
+protected:
+  bool TakesParamByValue = VectorT::TakesParamByValue;
+  const char *AssertionMessage =
+      "Attempting to reference an element of the vector in an operation \" "
+      "\"that invalidates it";
+
+  VectorT V;
+
+  template <typename T, unsigned N>
+  static unsigned NumBuiltinElts(const SmallVector<T, N> &) {
+    return N;
+  }
+
+  void SetUp() override {
+    SmallVectorTestBase::SetUp();
+
+    // Fill up the small size so that insertions move the elements.
+    V.push_back(0);
+  }
+};
+
+static_assert(SmallVectorImpl<int>::TakesParamByValue,
+              "int should be trivially copyable and small enough");
+static_assert(!SmallVectorImpl<Constructable>::TakesParamByValue,
+              "Constructable should not be trivially copyable");
+using SmallVectorTakesParameterByValueTestTypes =
+    ::testing::Types<SmallVector<int, 1>, SmallVector<Constructable, 1>>;
+
+TYPED_TEST_CASE(SmallVectorTakesParameterByValueTest,
+                SmallVectorTakesParameterByValueTestTypes);
+
+TYPED_TEST(SmallVectorTakesParameterByValueTest, PushBack) {
+  auto &V = this->V;
+  if (this->TakesParamByValue) {
+    V.push_back(V.back());
+    return;
+  }
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(V.push_back(V.back()), this->AssertionMessage);
+#endif
+}
+
+TYPED_TEST(SmallVectorTakesParameterByValueTest, PushBackMoved) {
+  auto &V = this->V;
+  if (this->TakesParamByValue) {
+    V.push_back(std::move(V.back()));
+    return;
+  }
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(V.push_back(std::move(V.back())), this->AssertionMessage);
+#endif
+}
+
+TYPED_TEST(SmallVectorTakesParameterByValueTest, Resize) {
+  auto &V = this->V;
+  if (this->TakesParamByValue) {
+    V.resize(2, V.back());
+    return;
+  }
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(V.resize(2, V.back()), this->AssertionMessage);
+#endif
+}
+
+TYPED_TEST(SmallVectorTakesParameterByValueTest, Append) {
+  auto &V = this->V;
+  if (this->TakesParamByValue) {
+    V.append(1, V.back());
+    return;
+  }
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(V.append(1, V.back()), this->AssertionMessage);
+#endif
+}
+
+TYPED_TEST(SmallVectorTakesParameterByValueTest, Assign) {
+  auto &V = this->V;
+  if (this->TakesParamByValue) {
+    V.assign(1, V.back());
+    V.assign(2, V.back());
+    V.assign(3, V.back());
+    return;
+  }
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  // Regardless of capacity, assign should never reference an internal element.
+  EXPECT_DEATH(V.assign(1, V.back()), this->AssertionMessage);
+  EXPECT_DEATH(V.assign(2, V.back()), this->AssertionMessage);
+  EXPECT_DEATH(V.assign(3, V.back()), this->AssertionMessage);
+#endif
+}
+
+TYPED_TEST(SmallVectorTakesParameterByValueTest, Insert) {
+  auto &V = this->V;
+  if (this->TakesParamByValue) {
+    V.insert(V.begin(), V.back());
+    return;
+  }
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(V.insert(V.begin(), V.back()), this->AssertionMessage);
+#endif
+}
+
+TYPED_TEST(SmallVectorTakesParameterByValueTest, InsertMoved) {
+  auto &V = this->V;
+  if (this->TakesParamByValue) {
+    V.insert(V.begin(), std::move(V.back()));
+    return;
+  }
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(V.insert(V.begin(), std::move(V.back())),
+               this->AssertionMessage);
+#endif
+}
+
+TYPED_TEST(SmallVectorTakesParameterByValueTest, InsertN) {
+  auto &V = this->V;
+  if (this->TakesParamByValue) {
+    V.insert(V.begin(), 2, V.back());
+    return;
+  }
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+  EXPECT_DEATH(V.insert(V.begin(), 2, V.back()), this->AssertionMessage);
+#endif
+}
+
 } // end namespace

llvm/utils/TableGen/CodeGenSchedule.cpp

pushVariant(const TransVariant &VInfo, bool IsRead) {
 
   const CodeGenSchedRW &SchedRW = SchedModels.getSchedRW(VInfo.RWIdx, IsRead);
 
   SmallVectorImpl<SmallVector<unsigned,4>> &RWSequences = IsRead
     ? Trans.ReadSequences : Trans.WriteSequences;
   if (SchedRW.IsVariadic) {
     unsigned OperIdx = RWSequences.size()-1;
     // Make N-1 copies of this transition's last sequence.
+    RWSequences.reserve(RWSequences.size() + SelectedRWs.size() - 1);
     RWSequences.insert(RWSequences.end(), SelectedRWs.size() - 1,
                        RWSequences[OperIdx]);
     // Push each of the N elements of the SelectedRWs onto a copy of the last
     // sequence (split the current operand into N operands).
     // Note that write sequences should be expanded within this loop--the entire
     // sequence belongs to a single operand.
     for (IdxIter RWI = SelectedRWs.begin(), RWE = SelectedRWs.end();
          RWI != RWE; ++RWI, ++OperIdx) {
if (IsRead && IsForAnyCPU && HasAliases && !WasPushed) {
       // a) We have read variant for CPU A
       // b) We have write variant for CPU B
       // b) We don't have write variant for CPU A
       // d) We must expand all read/write variants (IsForAnyCPU is true)
       // e) We couldn't expand SchedRW because TransVec doesn't have
       //    any transition with compatible CPU ID.
       // In such case we create new empty transition with zero (AnyCPU)
       // index.
+      TransVec.reserve(TransVec.size() + 1);
       TransVec.emplace_back(TransVec[StartIdx].PredTerm);
       TransVec.back().ReadSequences.emplace_back();
       CollectAndAddVariants(TransVec.size() - 1, SchedRW);
     }
   }
 }
 
 // For each variant of a Read/Write in Trans, substitute the sequence of