ADT: Fix reference invalidation in SmallVector::push_back and single-element insert

[dexonsmith]

Summary

For small enough, trivially copyable T, take the argument by value in
SmallVector::push_back and copy it when forwarding to
SmallVector::insert_one_impl. Otherwise, when growing, update the
argument appropriately.

Depends on https://reviews.llvm.org/D93777.
Split out from https://reviews.llvm.org/D91837.

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

235

reserveForAndGetAddressImpl is used in SmallVectorTemplateBase<T> and needs to call grow() here, but the text of the implementation does not depend on whether T is trivially copyable.

https://reviews.llvm.org/D91837#inline-875946 suggested using CRTP, but that seemed to require yet more names for SmallVector base classes and it seemed like a bit of a mess.

Actually... now I realize there is another option I'd missed: just add a CRTP parameter to SmallVectorTemplateCommon (no need for a new name). If you think that's worth trying I can try it and post an update.

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

235

Ah, no, it's not that easy... we can't easily add new parameters to SmallVectorTemplateCommon.

/// [...] The extra dummy template argument is used by ArrayRef
/// to avoid unnecessarily requiring T to be complete.
template <typename T, typename = void>
class SmallVectorTemplateCommon

I suspect adding a DerivedT template parameter would defeat this compile-time optimization.

[dblaikie]

llvm/include/llvm/ADT/SmallVector.h

481–491

While I think it's not technically a problem (because the casted-away-const-ness pointer is never dereferenced) - I'd usually implement these the other way around. Have an implementation that uses const pointers only, then the non-const wrapper can cast-to-const, call, cast away const, and it's "clearer" (marginally, perhaps) that it's const correct because only that non-const wrapper has the interesting const handling - rather than the longer distance behavior in this implementation.

700–701

Is this correct? If ArgType differs from the container's value type, wouldn't this break? (if you insert something that's convertible to the element type, but isn't the actual element type)

I guess insert_one_maybe_copy does SFINAE, etc to ensure this is always called with the value type? So ArgType is only ever some kind of ref qualified T?

llvm/unittests/ADT/SmallVectorTest.cpp

1089–1090

I'm not following what this part of the test does - could you walk me through it?

1206–1210

I'm not following how this validates that a copy was taken (I'd have thought it'd be unobservable whether a copy was made or the pointer-index-pointer dance was done) - could you walk me through that in a bit more detail?

[dexonsmith]

Rebase and respond to review feedback.

[dexonsmith]

Thanks for the review! (Just coming back to this now after the holidays.)

llvm/include/llvm/ADT/SmallVector.h

481–491

Good point; I've updated ...Impl() to take/return const, and both callers now call it directly.

700–701

Correct. I added a comment and static assertion above to document this.

711–713

I added a static assert here to confirm we have a copy, since the logic relies on that.

llvm/unittests/ADT/SmallVectorTest.cpp

1089–1090

I've rewritten it (I couldn't fully make sense of it either, coming back to it). It now tests:

• The correct value gets copied when pushing back with a reference, growing from small storage.
• The correct value gets copied when pushing back with a reference, growing from large storage.
• The value is actually copied, not moved (the difference is only observable for Constructable). See PushBackMoved below, where a 0 is left behind. This seems potentially worth testing in case a std::forward is missed somewhere, but i'm open to dropping that part if you think it's already covered well enough above.

1206–1210

I've rewritten this in the same way as the push_back tests.

[dblaikie]

Looks good, thanks!

llvm/unittests/ADT/SmallVectorTest.cpp

1089–1090

Looks good, don't have strong feelings about the last test case - take it or leave it as you see fit

[dexonsmith]

Reverted in 56d1ffb927d03958a7a31442596df749264a7792 due to an error on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489/steps/7/logs/stdio
if it's obvious I'll recommit in a minute, but if anyone has ideas I'd welcome them.

[dblaikie]

In D93779#2497099, @dexonsmith wrote:

Reverted in 56d1ffb927d03958a7a31442596df749264a7792 due to an error on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489/steps/7/logs/stdio
if it's obvious I'll recommit in a minute, but if anyone has ideas I'd welcome them.

Guess maybe something in the std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, T>::value isn't working quite right on MSVC? (could test that with godbolt, maybe) - is it needed? Since it's on both insert_one_maybe_copy and there's an implementation detail/doesn't need to protect from violations of that constraint (admittedly I'm proposing removing it because maybe MSVC is violating it... )? And instead SFINAE/enable_if only on the TakesParamByValue part?

[dexonsmith]

Replacing insert_one_maybe_copy indirection with a forwarding helper called forward_value_param.

[dexonsmith]

In D93779#2497112, @dblaikie wrote:

In D93779#2497099, @dexonsmith wrote:

Reverted in 56d1ffb927d03958a7a31442596df749264a7792 due to an error on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489/steps/7/logs/stdio
if it's obvious I'll recommit in a minute, but if anyone has ideas I'd welcome them.

Guess maybe something in the std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, T>::value isn't working quite right on MSVC? (could test that with godbolt, maybe) - is it needed? Since it's on both insert_one_maybe_copy and there's an implementation detail/doesn't need to protect from violations of that constraint (admittedly I'm proposing removing it because maybe MSVC is violating it... )? And instead SFINAE/enable_if only on the TakesParamByValue part?

Thanks for looking; I think you're right. The constraint was a trick to allow use of SFINAE since TakesParamByValue didn't depend on the template parameter so I can't just remove it, I need a different solution...

...but I've found one, and it's a bit cleaner too. Instead of the indirection through insert_one_maybe_copy, I've added a forwarding function defined in the POD vs. non-POD base classes called forward_value_param.

I'll commit the new version once I confirm check-llvm passes locally.

llvm/include/llvm/ADT/SmallVector.h

370–371

In the non-POD case it just returns what it has been given.

493–494

In the POD (well, trivially move/copy constructible) case it's either T (a copy) or const T& (a reference). No need for moving since it's trivially constructible.

745–752

The new forwarding function also means we don't need to indirect through instert_one_maybe_copy.

[dblaikie]

In D93779#2497131, @dexonsmith wrote:

In D93779#2497112, @dblaikie wrote:

In D93779#2497099, @dexonsmith wrote:

Reverted in 56d1ffb927d03958a7a31442596df749264a7792 due to an error on Windows:
http://lab.llvm.org:8011/#/builders/127/builds/4489/steps/7/logs/stdio
if it's obvious I'll recommit in a minute, but if anyone has ideas I'd welcome them.

Guess maybe something in the std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, T>::value isn't working quite right on MSVC? (could test that with godbolt, maybe) - is it needed? Since it's on both insert_one_maybe_copy and there's an implementation detail/doesn't need to protect from violations of that constraint (admittedly I'm proposing removing it because maybe MSVC is violating it... )? And instead SFINAE/enable_if only on the TakesParamByValue part?

Thanks for looking; I think you're right. The constraint was a trick to allow use of SFINAE since TakesParamByValue didn't depend on the template parameter so I can't just remove it, I need a different solution...

...but I've found one, and it's a bit cleaner too. Instead of the indirection through insert_one_maybe_copy, I've added a forwarding function defined in the POD vs. non-POD base classes called forward_value_param.

I'll commit the new version once I confirm check-llvm passes locally.

Yeah, looks nice/simpler to me!

[rupprecht]

This patch seems to have found a bug: in AArch64InstrInfo.cpp, there is a -Wsometimes-uninitialized warning that now triggers, and adding an assertion to make sure the value is eventually set causes a few tests to fail. The usage is DelInstrs.push_back(MUL), which I guess is how it ties in to this patch.

More details in 752fafda3dbf1f4885c64408a13ddb67c91ccb13, which gets things back to building, but doesn't do anything about the bug.

[dexonsmith]

In D93779#2497200, @rupprecht wrote:

This patch seems to have found a bug: in AArch64InstrInfo.cpp, there is a -Wsometimes-uninitialized warning that now triggers, and adding an assertion to make sure the value is eventually set causes a few tests to fail. The usage is DelInstrs.push_back(MUL), which I guess is how it ties in to this patch.

More details in 752fafda3dbf1f4885c64408a13ddb67c91ccb13, which gets things back to building, but doesn't do anything about the bug.

Oh weird, I saw that too, but (wrongly) assumed it was unrelated to my change. Thanks for digging into it.

[dexonsmith]

In D93779#2497213, @dexonsmith wrote:

In D93779#2497200, @rupprecht wrote:

This patch seems to have found a bug: in AArch64InstrInfo.cpp, there is a -Wsometimes-uninitialized warning that now triggers, and adding an assertion to make sure the value is eventually set causes a few tests to fail. The usage is DelInstrs.push_back(MUL), which I guess is how it ties in to this patch.

More details in 752fafda3dbf1f4885c64408a13ddb67c91ccb13, which gets things back to building, but doesn't do anything about the bug.

Oh weird, I saw that too, but (wrongly) assumed it was unrelated to my change. Thanks for digging into it.

@t.p.northover, maybe you can take a look at 752fafda3dbf1f4885c64408a13ddb67c91ccb13?

[xbolva00]

http://llvm-compile-time-tracker.com/compare.php?from=4c1617dac8fa13a8eac9cc4ac13a8f1fb3da512e&to=49142991a685bd427d7e877c29c77371dfb7634c&stat=instructions

Compile time regression is too big.. Please revert.

@nikic

[lebedev.ri]

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

[dblaikie]

In D93779#2498501, @lebedev.ri wrote:

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

I believe the standard library supports this, so I think it's a somewhat awkward limitation to have a standard-library-like container that misses that. (of course the small-mode isn't entirely compatible with std::vector, etc anyway - so some divergence is possible)

[xbolva00]

In D93779#2498509, @dblaikie wrote:

In D93779#2498501, @lebedev.ri wrote:

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

I believe the standard library supports this, so I think it's a somewhat awkward limitation to have a standard-library-like container that misses that. (of course the small-mode isn't entirely compatible with std::vector, etc anyway - so some divergence is possible)

But currently the cost (compile time) is too high to be acceptable.

[dblaikie]

In D93779#2498612, @xbolva00 wrote:

In D93779#2498509, @dblaikie wrote:

In D93779#2498501, @lebedev.ri wrote:

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

I believe the standard library supports this, so I think it's a somewhat awkward limitation to have a standard-library-like container that misses that. (of course the small-mode isn't entirely compatible with std::vector, etc anyway - so some divergence is possible)

But currently the cost (compile time) is too high to be acceptable.

Perhaps - my comment was intended to address "why are we trying to support this rather than using assertions" not the compile time cost question.

[nikic]

The last time I tested this in https://reviews.llvm.org/D91837#2464554, the impact was much smaller. Some change between then and the landed version must have regressed things again. I think the numbers are now similar to what we saw before the "small value" optimization was added.

[nikic]

Over in D91837 the reserveForAndGetAddress() implementation contained a check for TakesParamByValue that seems to be gone in this revision. My first guess is that this is the culprit, and we're now always performing the isReferenceToStorage() check.

[dexonsmith]

In D93779#2499361, @nikic wrote:

Over in D91837 the reserveForAndGetAddress() implementation contained a check for TakesParamByValue that seems to be gone in this revision. My first guess is that this is the culprit, and we're now always performing the isReferenceToStorage() check.

Somehow I missed the replies here until now. I came across the same thing independently: https://reviews.llvm.org/D94800.

[dexonsmith]

@xbolva00, thanks for reporting the regression. After the performance analysis was finished in https://reviews.llvm.org/D91837, I split the patch up for more detailed review, and in responding to review comments I somehow lost the critical check against TakesParamByValue.

Also, @nikic, thanks for the reverts yesterday when I missed the updates here.

https://reviews.llvm.org/D94800 adds back the critical check.

In D93779#2498509, @dblaikie wrote:

In D93779#2498501, @lebedev.ri wrote:

Why do we even want to bend over backwards and try to handle broken code correctly,
at the cost of regressed performance for everything,
instead of just adding defensive asserts against such problems,
and letting/telling the user fix the code?

I believe the standard library supports this, so I think it's a somewhat awkward limitation to have a standard-library-like container that misses that. (of course the small-mode isn't entirely compatible with std::vector, etc anyway - so some divergence is possible)

Exactly, this is part of rectifying some unnecessary awkwardness in SmallVector. I'm 100% agreed it's not worth it with the compile-time impact you reported, but this approach seems to get the benefits without significant cost (when I don't drop critical checks...). You can see the numbers in https://reviews.llvm.org/D91837.

llvm/include/llvm/ADT/SmallVector.h

232

The cause of the regression was dropping the check against TakesParamByValue on this line when I moved this function to SmallVectorTemplateCommon...

llvm/include/llvm/ADT/SmallVector.h

protected:
   /// emplace_back.
   template <class ArgType1, class... ArgTypes>
   void assertSafeToEmplace(ArgType1 &Arg1, ArgTypes &... Args) {
     this->assertSafeToAdd(&Arg1);
     this->assertSafeToEmplace(Args...);
   }
   void assertSafeToEmplace() {}
 
+  /// Reserve enough space to add one element, and return the updated element
+  /// pointer in case it was a reference to the storage.
+  template <class U>
+  static const T *reserveForAndGetAddressImpl(U *This, const T &Elt) {
+    if (LLVM_LIKELY(This->size() < This->capacity()))
+      return &Elt;
+
+    bool ReferencesStorage = false;
+    int64_t Index = -1;
+    if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
+      ReferencesStorage = true;
+      Index = &Elt - This->begin();
+    }
+    This->grow();
+    return ReferencesStorage ? This->begin() + Index : &Elt;
+  }
+
 public:
   using size_type = size_t;
   using difference_type = ptrdiff_t;
   using value_type = T;
   using iterator = T *;
   using const_iterator = const T *;
 
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;

 /// 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> {
+  friend class 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 one element, and return the updated element
+  /// pointer in case it was a reference to the storage.
+  const T *reserveForAndGetAddress(const T &Elt) {
+    return this->reserveForAndGetAddressImpl(this, Elt);
+  }
+
+  /// Reserve enough space to add one element, and return the updated element
+  /// pointer in case it was a reference to the storage.
+  T *reserveForAndGetAddress(T &Elt) {
+    return const_cast<T *>(this->reserveForAndGetAddressImpl(this, Elt));
+  }
+
 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> {
+  friend class 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 one element, and return the updated element
+  /// pointer in case it was a reference to the storage.
+  const T *reserveForAndGetAddress(const T &Elt) {
+    return this->reserveForAndGetAddressImpl(this, Elt);
+  }
+
+  /// Reserve enough space to add one element, and return the updated element
+  /// pointer in case it was a reference to the storage.
+  T *reserveForAndGetAddress(T &Elt) {
+    return const_cast<T *>(this->reserveForAndGetAddressImpl(this, 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() {
iterator erase(const_iterator CS, const_iterator CE) {
     // Drop the last elts.
     this->destroy_range(I, this->end());
     this->set_size(I - this->begin());
     return(N);
   }
 
 private:
   template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
+    // Callers ensure that ArgType is derived from T.
+    static_assert(
+        std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
+                     T>::value,
+        "ArgType must be derived from T!");
+
     if (I == this->end()) {  // Important special case for empty vector.
       this->push_back(::std::forward<ArgType>(Elt));
       return this->end()-1;
     }
 
     assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
 
-    // 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 (this->isReferenceToRange(EltPtr, I, this->end()))
+    // the reference (never happens if TakesParamByValue).
+    static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
+                  "ArgType must be 'T' when taking by value!");
+    if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, 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) {
     // 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;
     }

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) {
+  // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
   auto &V = this->V;
-  (void)V;
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.push_back(V.back()), this->AssertionMessage);
-#endif
+  int N = this->NumBuiltinElts(V);
+
+  // Push back a reference to last element when growing from small storage.
+  V.push_back(V.back());
+  EXPECT_EQ(N, V.back());
+
+  // Check that the old value is still there (not moved away).
+  EXPECT_EQ(N, V[V.size() - 2]);
+
+  // Fill storage again.
+  V.back() = V.size();
+  while (V.size() < V.capacity())
+    V.push_back(V.size() + 1);
+
+  // Push back a reference to last element when growing from large storage.
+  V.push_back(V.back());
+  EXPECT_EQ(int(V.size()) - 1, V.back());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) {
+  // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
   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
+  int N = this->NumBuiltinElts(V);
+
+  // Push back a reference to last element when growing from small storage.
+  V.push_back(std::move(V.back()));
+  EXPECT_EQ(N, V.back());
+  if (this->template isValueType<Constructable>()) {
+    // Check that the value was moved (not copied).
+    EXPECT_EQ(0, V[V.size() - 2]);
+  }
+
+  // Fill storage again.
+  V.back() = V.size();
+  while (V.size() < V.capacity())
+    V.push_back(V.size() + 1);
+
+  // Push back a reference to last element when growing from large storage.
+  V.push_back(std::move(V.back()));
+
+  // Check the values.
+  EXPECT_EQ(int(V.size()) - 1, V.back());
+  if (this->template isValueType<Constructable>()) {
+    // Check the value got moved out.
+    EXPECT_EQ(0, V[V.size() - 2]);
+  }
 }
 
 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);
#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
   EXPECT_DEATH(V.assign(V.begin(), V.end()), this->AssertionMessage);
   EXPECT_DEATH(V.assign(V.begin(), V.end() - 1), this->AssertionMessage);
 #endif
   V.assign(V.begin(), V.begin());
   EXPECT_TRUE(V.empty());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, Insert) {
+  // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
   auto &V = this->V;
   (void)V;
-#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
-  EXPECT_DEATH(V.insert(V.begin(), V.back()), this->AssertionMessage);
-#endif
+
+  // Insert a reference to the back (not at end() or else insert delegates to
+  // push_back()), growing out of small mode. Confirm the value was copied out
+  // (moving out Constructable sets it to 0).
+  V.insert(V.begin(), V.back());
+  EXPECT_EQ(int(V.size() - 1), V.front());
+  EXPECT_EQ(int(V.size() - 1), V.back());
+
+  // Fill up the vector again.
+  while (V.size() < V.capacity())
+    V.push_back(V.size() + 1);
+
+  // Grow again from large storage to large storage.
+  V.insert(V.begin(), V.back());
+  EXPECT_EQ(int(V.size() - 1), V.front());
+  EXPECT_EQ(int(V.size() - 1), V.back());
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertMoved) {
+  // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode.
   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
+
+  // Insert a reference to the back (not at end() or else insert delegates to
+  // push_back()), growing out of small mode. Confirm the value was copied out
+  // (moving out Constructable sets it to 0).
+  V.insert(V.begin(), std::move(V.back()));
+  EXPECT_EQ(int(V.size() - 1), V.front());
+  if (this->template isValueType<Constructable>()) {
+    // Check the value got moved out.
+    EXPECT_EQ(0, V.back());
+  }
+
+  // Fill up the vector again.
+  while (V.size() < V.capacity())
+    V.push_back(V.size() + 1);
+
+  // Grow again from large storage to large storage.
+  V.insert(V.begin(), std::move(V.back()));
+  EXPECT_EQ(int(V.size() - 1), V.front());
+  if (this->template isValueType<Constructable>()) {
+    // Check the value got moved out.
+    EXPECT_EQ(0, V.back());
+  }
 }
 
 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