ADT: Fix reference invalidation in SmallVector APIs that pass in a value

[dexonsmith]

Summary

Fix reference invalidation in SmallVector APIs that pass in a T, taking it by value when it's small enough and trivially copyable, and doing a pointer-to-index-to-pointer dance otherwise.

This doesn't fix all possible reference invalidation, but if it avoids the compile-time regressions from https://reviews.llvm.org/D87326 (which does fix them all) it seems like a good incremental step. The mental model also seems more clear than https://reviews.llvm.org/D91467 (which only fixed invalidation for small enough, trivially copyable T).

I'm currently building a few variants of clang (matching how the patches are sequenced in my local tree (probably they should be committed separately so they can be reverted individually if necessary, but I figured it made more sense to start with a single Phab review)) to test effects on compile-time:

• baseline
• fix only push_back and single-element insert (tied together since insert uses `push_back)
• fix also N-element versions of append and insert (tied together since insert uses append)
• fix also resize

I'll start with compiling a "big" file a few times (in the other review I used llvm/lib/Target/X86/X86ISelLowering.cpp), but I'm happy to do more work if it seems prudent.

[dexonsmith]

Compile-time results below for llvm/lib/Target/X86/X86ISelLowering.cpp:

$ for c in $(find refinvalid-*/build -type f -name clang-12); do du $c; cabs=$PWD/$c; (cd build && for n in {0..4}; do /usr/bin/time ../compile-big-file.sh $cabs; done); done
231952	refinvalid-baseline/build/bin/clang-12
       30.66 real        30.28 user         0.36 sys
       30.14 real        29.79 user         0.34 sys
       30.11 real        29.77 user         0.33 sys
       29.85 real        29.52 user         0.33 sys
       30.04 real        29.72 user         0.32 sys
232200	refinvalid-pushback+append+insert+resize/build/bin/clang-12
       30.55 real        30.20 user         0.34 sys
       30.59 real        30.27 user         0.31 sys
       30.14 real        29.80 user         0.33 sys
       30.02 real        29.69 user         0.33 sys
       30.11 real        29.80 user         0.30 sys
232200	refinvalid-pushback+append+insert/build/bin/clang-12
       30.30 real        29.93 user         0.36 sys
       30.45 real        30.11 user         0.34 sys
       30.14 real        29.82 user         0.31 sys
       30.74 real        30.40 user         0.32 sys
       30.86 real        30.52 user         0.33 sys
232224	refinvalid-pushback/build/bin/clang-12
       30.29 real        29.95 user         0.32 sys
       30.35 real        30.00 user         0.33 sys
       30.22 real        29.87 user         0.34 sys
       30.01 real        29.68 user         0.33 sys
       30.36 real        30.04 user         0.31 sys

Seems mostly in the noise to me. (top is baseline, next is this patch, next is just push_back, append, and insert, final is just push_back and single-element insert)

[mehdi_amini]

LGTM!

@njames93 ?

[njames93]

llvm/include/llvm/ADT/SmallVector.h

698

Shouldn't this use the move constructor T(std::move(Elt)) Otherwise this adds the unnecessary requirement that T is copyable when calling the xvalue version of insert.

[dexonsmith]

@njames93, thanks for the review, I've responded inline (I was out last week).

llvm/include/llvm/ADT/SmallVector.h

286–294

Note: TakesParamByValue is always false when T is not copy-constructible.

698

The enable_if restricts this to when TakesParamByValue, which already requires that T is copyable (see note above). Do you think an expanded comment would be a good idea?

Or, maybe I've missed your point, let me know if I didn't understand.

[njames93]

llvm/include/llvm/ADT/SmallVector.h

698

No I missed the point, disregard it.

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

698

Just to confirm, do you think this is good to commit?

[dexonsmith]

@njames93, do you have any other concerns? Do you think this is a reasonable approach?

[dexonsmith]

Rebase.

[dexonsmith]

@njames93 , ping

[njames93]

I'd like to get @nikic's input first, but I have no issues here.

[nikic]

Here are the number I see for this patch:

Instructions retired: https://llvm-compile-time-tracker.com/compare.php?from=2af2f58ec09257d65a2a6f99f833a1b242d434a3&to=1d9e441fa77400d0a97a371b4d9bdbf9c6979266&stat=instructions Geomean 0.2% regression, which is much better than the previous versions (which were something like 1.5%)
Max-RSS: https://llvm-compile-time-tracker.com/compare.php?from=2af2f58ec09257d65a2a6f99f833a1b242d434a3&to=1d9e441fa77400d0a97a371b4d9bdbf9c6979266&stat=max-rss Geomean 0.3% regression (changes here are always a bit mysterious...)
Code size for clang binary: From 82761400 to 82820191, which is a 0.07% increase, which is negligible. (Code size increase with GCC host compiler was a big issue in some of the earlier versions.)

Overall the impact looks reasonable to me now.

[dexonsmith]

Great, thanks for doing that analysis @nikic!

@njames93, I'll land this once you accept.

[njames93]

In D91837#2467008, @dexonsmith wrote:

Great, thanks for doing that analysis @nikic!

@njames93, I'll land this once you accept.

LGTM, but I'm not the gatekeeper of ADT.

[dblaikie]

llvm/include/llvm/ADT/SmallVector.h

141

Absurd C++ pedantry, but I believe op< on pointers to unrelated objects is unspecified in C++? ("If two pointers are not specified to compare greater or compare equal, the result of the comparison is unspecified. An unspecified result may be nondeterministic, and need not be consistent even for multiple evaluations of the same expression with the same operands in the same execution of the program" - https://en.cppreference.com/w/cpp/language/operator_comparison) but std::less is specified to handle this case: "A specialization of std::less for any pointer type yields a strict total order, even if the built-in operator< does not." - https://en.cppreference.com/w/cpp/utility/functional/less)

Because C++ is fun like that.

334

Is there any case where 'Elt' could be contained within a subobject of an element of the SmallVector, while not being an element itself? I guess not, because T can't contain (directly) another T - but asking just in case I've missed a possibility (if this were true, then an index would be inadequate for persisting 'Elt' across the grow operation).

454–467

Is this text identical between the trivially copyable and non-trivially copyable specializations? If so, can it be shared at all? I guess it'd need to be in a CRTP base placed between these specializations and SmallVectorTemplateCommon, and possibly not worth the added complexity?

677–686

Perhaps all this infrastructure and SFINAE might merit a separate patch? (breaking this patch up into separate changes for adding reference validity for each independent operation might be nice in general, but especially this part/set of changes, if they can be separate - it'd also make some of the other changes a bit clearer, once the reserveForAndGetAddress is added, subsequent changes would be "port to use that, and add test")

But I know that can be a hassle to make, manage the reviews, etc, so not vital by any means.

llvm/unittests/ADT/SmallVectorTest.cpp

1083–1085

By this you mean "sanitizers would catch use-after-free if this support were missing/broken"? Otherwise this reads as though it might be a sanitizer-only death test, specifically checking that misuse fails/is diagnosed, which it isn't.

[dblaikie]

Oh, one other question: How's all this implementation strategy compared to std::vector? Be nice to be relying on prior art where possible.

[dexonsmith]

Thanks for the review!

A few responses inline; I'll try to update the patch tomorrow.

Regarding number of patches, this is already split into multiple patches in my local tree:

1. Fix invalidation for push_back and insert (one), the latter of which sometimes calls push_back.
2. Fix invalidation for append and insert (N), the latter of which sometimes calls append.
3. Fix invalidation for resize.

(The various helpers get added as needed.)

Happy to split it now that the performance has been validated. I'll probably find time to rebase and post tomorrow -- let me know if there's something else you'd like split out.

In D91837#2468608, @dblaikie wrote:

Oh, one other question: How's all this implementation strategy compared to std::vector? Be nice to be relying on prior art where possible.

Libc++'s std::vector uses a more general, split buffer approach that fixes all the invalidation, quite similar to https://reviews.llvm.org/D87326. Unfortunately that was reverted due to compile-time and code size regressions. My thinking is that we can try to land https://reviews.llvm.org/D87326 again after this patch (series) to fix the remaining invalidation (and that the regressions may be less bad / acceptable since the common cases in this patch are handled in a more lightweight manner).

llvm/include/llvm/ADT/SmallVector.h

141

Hah; I wondered about this, but couldn't find it in the standard, so ended up leaving it as it was in the prep patch. I'll fix in a prep commit.

334

Correct, not possible. As a result this code wouldn't handle V.emplace_back(subobject_reference), but it's not used for that at this point. (We could probably handle emplace_back somehow with this technique, but I'm not sure it would still be lightweight / worth it.)

454–467

Yes, it's identical. I can take a look to see how bad it is with CRTP.

677–686

Very happy to split this up; just wanted to start with the holistic patch to get numbers (it's already split up locally).

llvm/unittests/ADT/SmallVectorTest.cpp

1083–1085

Correct; not a death test, but I expect the sanitizers to catch the problem if the implementation is wrong.

[dblaikie]

In D91837#2469329, @dexonsmith wrote:

Thanks for the review!

A few responses inline; I'll try to update the patch tomorrow.

Regarding number of patches, this is already split into multiple patches in my local tree:

1. Fix invalidation for push_back and insert (one), the latter of which sometimes calls push_back.
2. Fix invalidation for append and insert (N), the latter of which sometimes calls append.
3. Fix invalidation for resize.

(The various helpers get added as needed.)

Happy to split it now that the performance has been validated. I'll probably find time to rebase and post tomorrow -- let me know if there's something else you'd like split out.

Makes sense/sounds good.

In D91837#2468608, @dblaikie wrote:

Oh, one other question: How's all this implementation strategy compared to std::vector? Be nice to be relying on prior art where possible.

Libc++'s std::vector uses a more general, split buffer approach that fixes all the invalidation, quite similar to https://reviews.llvm.org/D87326. Unfortunately that was reverted due to compile-time and code size regressions. My thinking is that we can try to land https://reviews.llvm.org/D87326 again after this patch (series) to fix the remaining invalidation (and that the regressions may be less bad / acceptable since the common cases in this patch are handled in a more lightweight manner).

*thumbs up*

llvm/unittests/ADT/SmallVectorTest.cpp

1083–1085

Would probably be good to rephrase this comment (& elsewhere the same text appears) to clarify. I'd find this confusing if/when I come across it in the future.

[dexonsmith]

Thanks again for the reviews here. For landing this (and a bit more review from @dblaikie) I've split this up into:

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

"Abandoning" this one, but that patch series gets to essentially the same end result (modulo incorporating some feedback from here).

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.
   }
 
+  // Return true if V is in this vector.
+  bool isReferenceToStorage(const void *V) const {
+    return V >= this->begin() && V < this->end();
+  }
+
   /// Return true unless Elt will be invalidated by resizing the vector to
   /// NewSize.
   bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
     // Past the end.
-    if (LLVM_LIKELY(Elt < this->begin() || Elt >= this->end()))
+    if (LLVM_LIKELY(!isReferenceToStorage(Elt)))
       return true;
 
     // Return false if Elt will be destroyed by shrinking.
     if (NewSize <= this->size())
       return Elt < this->begin() + NewSize;
 
     // Return false if we need to grow.
     return NewSize <= this->capacity();

 /// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
 /// method implementations that are designed to work with non-trivial T's.
 ///
 /// We approximate is_trivially_copyable with trivial move/copy construction and
 /// 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> {
 protected:
+  static constexpr bool TakesParamByValue = false;
+  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();
     }
   }
 
static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
     std::uninitialized_copy(I, E, Dest);
   }
 
   /// 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);
 
+  /// Reserve enough space to add N copies of Elt, and return the updated
+  /// element pointer in case it was a reference to the storage.
+  T *reserveForAndGetAddress(T &Elt, size_t N = 1) {
+    size_t NewSize = this->size() + N;
+    if (LLVM_LIKELY(NewSize <= this->capacity()))
+      return const_cast<T *>(&Elt);
+
+    bool ReferencesStorage = false;
+    int64_t Index = -1;
+    if (LLVM_UNLIKELY(this->isReferenceToStorage(&Elt))) {
+      ReferencesStorage = true;
+      Index = &Elt - this->begin();
+    }
+    this->grow(NewSize);
+    return ReferencesStorage ? this->begin() + Index : &Elt;
+  }
+  const T *reserveForAndGetAddress(const T &Elt, size_t N = 1) {
+    return reserveForAndGetAddress(const_cast<T &>(Elt), N);
+  }
+
 public:
   void push_back(const T &Elt) {
-    this->assertSafeToAdd(&Elt);
-    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
-      this->grow();
-    ::new ((void*) this->end()) T(Elt);
+    const T *EltPtr = reserveForAndGetAddress(Elt);
+    ::new ((void *)this->end()) T(*EltPtr);
     this->set_size(this->size() + 1);
   }
 
   void push_back(T &&Elt) {
-    this->assertSafeToAdd(&Elt);
-    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
-      this->grow();
-    ::new ((void*) this->end()) T(::std::move(Elt));
+    T *EltPtr = reserveForAndGetAddress(Elt);
+    ::new ((void *)this->end()) T(::std::move(*EltPtr));
     this->set_size(this->size() + 1);
   }
 
   void pop_back() {
     this->set_size(this->size() - 1);
     this->end()->~T();
   }
 };

 
 /// 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> {
 protected:
+  /// True if it's cheap enough to take parameters by value. Doing so avoids
+  /// overhead related to mitigations for reference invalidation.
+  static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
+
+  /// Either const T& or T, depending on whether it's cheap enough to take
+  /// parameters by value.
+  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_copy(
     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)); }
 
+  /// Reserve enough space to add N copies of Elt, and return the updated
+  /// element pointer in case it was a reference to the storage.
+  T *reserveForAndGetAddress(const T &Elt, size_t N = 1) {
+    size_t NewSize = this->size() + N;
+    if (LLVM_LIKELY(NewSize <= this->capacity()))
+      return const_cast<T *>(&Elt);
+
+    bool ReferencesStorage = false;
+    int64_t Index = -1;
+    if (LLVM_UNLIKELY(!TakesParamByValue && this->isReferenceToStorage(&Elt))) {
+      ReferencesStorage = true;
+      Index = &Elt - this->begin();
+    }
+    this->grow(NewSize);
+    return ReferencesStorage ? this->begin() + Index : const_cast<T *>(&Elt);
+  }
+
 public:
-  void push_back(const T &Elt) {
-    this->assertSafeToAdd(&Elt);
-    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
-      this->grow();
-    memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
+  void push_back(ValueParamT Elt) {
+    const T *EltPtr = reserveForAndGetAddress(Elt);
+    memcpy(reinterpret_cast<void *>(this->end()), EltPtr, 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;
 
 protected:
+  using SmallVectorTemplateBase<T>::TakesParamByValue;
+  using ValueParamT = typename SuperClass::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 (N == this->size())
       return;
 
     if (N < this->size()) {
       this->destroy_range(this->begin()+N, this->end());
       this->set_size(N);
       return;
     }
 
-    this->assertSafeToReferenceAfterResize(&NV, N);
-    if (this->capacity() < N)
-      this->grow(N);
-    std::uninitialized_fill(this->end(), this->begin() + N, NV);
+    const T *NVPtr = this->reserveForAndGetAddress(NV, N - this->size());
+    std::uninitialized_fill(this->end(), this->begin() + N, *NVPtr);
     this->set_size(N);
   }
 
   void reserve(size_type N) {
     if (this->capacity() < N)
       this->grow(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) {
-    this->assertSafeToAdd(&Elt, NumInputs);
-    if (NumInputs > this->capacity() - this->size())
-      this->grow(this->size()+NumInputs);
-
-    std::uninitialized_fill_n(this->end(), NumInputs, Elt);
+  void append(size_type NumInputs, ValueParamT Elt) {
+    const T *EltPtr = this->reserveForAndGetAddress(Elt, NumInputs);
+    std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
     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 &
template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
     if (I == this->end()) {  // Important special case for empty vector.
       this->push_back(::std::forward<ArgType>(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.
-    this->assertSafeToAdd(&Elt);
-
-    if (this->size() >= this->capacity()) {
-      size_t EltNo = I-this->begin();
-      this->grow();
-      I = this->begin()+EltNo;
-    }
+    // Grow if necessary.
+    size_t Index = I - this->begin();
+    std::remove_reference_t<ArgType> *EltPtr =
+        this->reserveForAndGetAddress(Elt);
+    I = this->begin() + Index;
 
     ::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.
-    std::remove_reference_t<ArgType> *EltPtr = &Elt;
-    if (I <= EltPtr && EltPtr < this->end())
+    // the reference (never happens if TakesParamByValue).
+    if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
       ++EltPtr;
 
     *I = ::std::forward<ArgType>(*EltPtr);
     return I;
   }
 
+  template <
+      class ArgType,
+      std::enable_if_t<
+          std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
+                       T>::value &&
+              !TakesParamByValue,
+          bool> = false>
+  iterator insert_one_maybe_copy(iterator I, ArgType &&Elt) {
+    return insert_one_impl(I, std::forward<ArgType>(Elt));
+  }
+
+  template <
+      class ArgType,
+      std::enable_if_t<
+          std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
+                       T>::value &&
+              TakesParamByValue,
+          bool> = false>
+  iterator insert_one_maybe_copy(iterator I, ArgType &&Elt) {
+    // Copy Elt in order to mitigate reference invalidation without needing to
+    // update the pointer values in insert_one_impl.
+    return insert_one_impl(I, T(Elt));
+  }
+
 public:
   iterator insert(iterator I, T &&Elt) {
-    return insert_one_impl(I, std::move(Elt));
+    return insert_one_maybe_copy(I, std::move(Elt));
   }
 
-  iterator insert(iterator I, const T &Elt) { return insert_one_impl(I, Elt); }
+  iterator insert(iterator I, const T &Elt) {
+    return insert_one_maybe_copy(I, Elt);
+  }
 
-  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.
-    this->assertSafeToAdd(&Elt, NumToInsert);
-
-    // Ensure there is enough space.
-    reserve(this->size() + NumToInsert);
+    // Ensure there is enough space, and get the (maybe updated) address of
+    // Elt.
+    const T *EltPtr = this->reserveForAndGetAddress(Elt, 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
     // insertion.  Since we already reserved space, we know that this won't
     // reallocate the vector.
     if (size_t(this->end()-I) >= NumToInsert) {
       T *OldEnd = this->end();
       append(std::move_iterator<iterator>(this->end() - NumToInsert),
              std::move_iterator<iterator>(this->end()));
 
       // Copy the existing elements that get replaced.
       std::move_backward(I, OldEnd-NumToInsert, OldEnd);
 
-      std::fill_n(I, NumToInsert, Elt);
+      // If we just moved the element we're inserting, be sure to update
+      // the reference (never happens if TakesParamByValue).
+      if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
+        EltPtr += NumToInsert;
+
+      std::fill_n(I, NumToInsert, *EltPtr);
       return I;
     }
 
     // Otherwise, we're inserting more elements than exist already, and we're
     // not inserting at the end.
 
     // Move over the elements that we're about to overwrite.
     T *OldEnd = this->end();
     this->set_size(this->size() + NumToInsert);
     size_t NumOverwritten = OldEnd-I;
     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
 
+    // If we just moved the element we're inserting, be sure to update
+    // the reference (never happens if TakesParamByValue).
+    if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
+      EltPtr += NumToInsert;
+
     // Replace the overwritten part.
-    std::fill_n(I, NumOverwritten, Elt);
+    std::fill_n(I, NumOverwritten, *EltPtr);
 
     // Insert the non-overwritten middle part.
-    std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
+    std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, *EltPtr);
     return I;
   }
 
   template <typename ItTy,
             typename = std::enable_if_t<std::is_convertible<
                 typename std::iterator_traits<ItTy>::iterator_category,
                 std::input_iterator_tag>::value>>
   iterator insert(iterator I, ItTy From, ItTy To) {

llvm/unittests/ADT/SmallVectorTest.cpp

public:
   Constructable(const Constructable & src) : constructed(true) {
     value = src.value;
     ++numConstructorCalls;
     ++numCopyConstructorCalls;
   }
 
   Constructable(Constructable && src) : constructed(true) {
     value = src.value;
+    src.value = 0;
     ++numConstructorCalls;
     ++numMoveConstructorCalls;
   }
 
   ~Constructable() {
     EXPECT_TRUE(constructed);
     ++numDestructorCalls;
     constructed = false;
   }
 
   Constructable & operator=(const Constructable & src) {
     EXPECT_TRUE(constructed);
     value = src.value;
     ++numAssignmentCalls;
     ++numCopyAssignmentCalls;
     return *this;
   }
 
   Constructable & operator=(Constructable && src) {
     EXPECT_TRUE(constructed);
     value = src.value;
+    src.value = 0;
     ++numAssignmentCalls;
     ++numMoveAssignmentCalls;
     return *this;
   }
 
   int getValue() const {
     return abs(value);
   }
protected:
 
   VectorT V;
 
   template <typename T, unsigned N>
   static unsigned NumBuiltinElts(const SmallVector<T, N> &) {
     return N;
   }
 
+  template <class T> static bool isValueType() {
+    return std::is_same<T, typename VectorT::value_type>::value;
+  }
+
   void SetUp() override {
     SmallVectorTestBase::SetUp();
 
     // Fill up the small size so that insertions move the elements.
-    V.append({0, 0, 0});
+    for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)
+      V.emplace_back(I + 1);
   }
 };
 
 // Test one type that's trivially copyable (int) and one that isn't
 // (Constructable) since reference invalidation may be fixed differently for
 // each.
 using SmallVectorReferenceInvalidationTestTypes =
     ::testing::Types<SmallVector<int, 3>, SmallVector<Constructable, 3>>;
 
 TYPED_TEST_CASE(SmallVectorReferenceInvalidationTest,
                 SmallVectorReferenceInvalidationTestTypes);
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBack) {
   auto &V = this->V;
-  (void)V;
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.push_back(V.back()), this->AssertionMessage);
-#endif
+  V.push_back(V.back());
+  int N = this->NumBuiltinElts(V);
+  EXPECT_EQ(N, V.back());
+  if (this->template isValueType<Constructable>())
+    EXPECT_EQ(N, V[N - 1]);
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) {
   auto &V = this->V;
-  (void)V;
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.push_back(std::move(V.back())), this->AssertionMessage);
-#endif
+  V.push_back(std::move(V.back()));
+  int N = this->NumBuiltinElts(V);
+  EXPECT_EQ(N, V.back());
+  if (this->template isValueType<Constructable>())
+    EXPECT_EQ(0, V[N - 1]);
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, Resize) {
   auto &V = this->V;
   (void)V;
   int N = this->NumBuiltinElts(V);
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.resize(N + 1, V.back()), this->AssertionMessage);
-#endif
+  V.resize(N + 1, V.back());
+  EXPECT_EQ(N, V.back());
 
-  // No assertion when shrinking, since the parameter isn't accessed.
-  V.resize(N - 1, V.back());
+  // Append enough more elements that V will grow again. This time the old
+  // storage will have been freed at time of access and sanitizers can catch
+  // the use-after-free.
+  V.resize(V.capacity() + 1, V.front());
+  EXPECT_EQ(1, V.back());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, Append) {
   auto &V = this->V;
   (void)V;
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.append(1, V.back()), this->AssertionMessage);
-#endif
+  V.append(1, V.back());
+  int N = this->NumBuiltinElts(V);
+  EXPECT_EQ(N, V[N - 1]);
+
+  // Append enough more elements that V will grow again. This time the old
+  // storage will have been freed at time of access and sanitizers can catch
+  // the use-after-free.
+  V.append(V.capacity(), V.front());
+  EXPECT_EQ(1, V.back());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, AppendRange) {
   auto &V = this->V;
   (void)V;
 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
   EXPECT_DEATH(V.append(V.begin(), V.begin() + 1), this->AssertionMessage);
 

 #endif
   V.assign(V.begin(), V.begin());
   EXPECT_TRUE(V.empty());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, Insert) {
   auto &V = this->V;
   (void)V;
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.insert(V.begin(), V.back()), this->AssertionMessage);
-#endif
+  V.insert(V.begin(), V.back());
+  int N = this->NumBuiltinElts(V);
+  EXPECT_EQ(N, V.front());
+  if (this->template isValueType<Constructable>()) {
+    // Check that the value was copied out (not moved).
+    EXPECT_EQ(N, V.back());
+  }
+
+  // The logic for reference invalidation when NOT growing is disabled when
+  // TakesParamByValue since it relies on taking a copy. Check that we actually
+  // took a copy.
+  V.insert(V.begin(), V.back());
+  EXPECT_EQ(N, V.front());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertMoved) {
   auto &V = this->V;
   (void)V;
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.insert(V.begin(), std::move(V.back())),
-               this->AssertionMessage);
-#endif
+  int N = this->NumBuiltinElts(V);
+  V.insert(V.begin(), std::move(V.back()));
+  EXPECT_EQ(N, V.front());
+  if (this->template isValueType<Constructable>()) {
+    // Check that the value got moved out, then copy it back in.
+    EXPECT_EQ(0, V.back());
+    V.back() = V.front();
+  }
+
+  // The logic for reference invalidation when NOT growing is disabled when
+  // TakesParamByValue since it relies on taking a copy. Check that we actually
+  // took a copy.
+  V.insert(V.begin(), std::move(V.back()));
+  EXPECT_EQ(N, V.front());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertN) {
   auto &V = this->V;
   (void)V;
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.insert(V.begin(), 2, V.back()), this->AssertionMessage);
-#endif
+
+  // Cover NumToInsert <= this->end() - I.
+  V.insert(V.begin() + 1, 1, V.back());
+  int N = this->NumBuiltinElts(V);
+  EXPECT_EQ(N, V[1]);
+
+  // Cover NumToInsert > this->end() - I. Also insert enough more elements that
+  // V will grow again. This time the old storage will have been freed at time
+  // of access and sanitizers can catch the use-after-free.
+  V.insert(V.begin(), V.capacity(), V.front());
+  EXPECT_EQ(1, V.front());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertRange) {
   auto &V = this->V;
   (void)V;
 #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
   EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.begin() + 1),
                this->AssertionMessage);