ADT: Fix reference invalidation in SmallVector::emplace_back and the size+value version of SmallVector::assign

[dexonsmith]

Summary

Fix the final (I think?) reference invalidation in SmallVector that
we need to fix to align with std::vector. (There is still some left in
the range insert / append / assign, but the standard calls that UB for
std::vector so I think we don't care?)

Avoid reference invalidation during SmallVector::emplace_back when one
of the arguments is an internal reference to storage and the vector has
to grow.

For POD-like types, reimplement emplace_back in terms of push_back.

For other types, split the grow operation in three and construct the new
element in the middle.

Also reimplement SmallVector:assign(size_type, const T&) to avoid
invalidating the argument during clear() when it's an internal
reference.

There is a minor semantic change when not growing. Previously, assign
would start with clear(), and so the old elements were destructed and
all elements of the new vector were copy-constructed. The new
implementation skips destruction and uses copy-assignment for the prefix
of the new vector less than size(). The new semantics match what
libc++ does for std::vector::assign.

Note that the following is another possible implementation:

void assign(size_type NumElts, ValueParamT Elt) {
  std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
  this->resize(NumElts, Elt);
}

The downside of this is that if the vector has to grow there will be
size() redundant copy operations.

I should probably split this patch up into three for committing:

1. NFC refactoring to split up grow().
2. Fix emplace_back().
3. Fix assign().

... but I wanted to start the review all together since the patches
will be interdependent.

[dexonsmith]

Note that this is a follow-up to https://reviews.llvm.org/D91837 (and the patches split out from it), and an alternative implementation for https://reviews.llvm.org/D87326.

I still need to do compile-time measurements; feel free to delay review until then.

The main concern I have (without having run numbers) is POD-like version of emplace_back (which now calls push_back). For large T where TakesParamByValue is false, this is now making a copy and I could imagine a slowdown. The other primary option is for emplace_back to use a split grow operation, but then it won't be able to use realloc()... I suspect the copy is less bad than dropping the realloc.

Hmm... or I could update the POD-like !TakesParamByValue to only copy when growing (only when it's useful). Marking this as "Plan Changes" to try implementing that before collecting compile-time.

[dexonsmith]

Simplified emplace_back and addressed the concern I had with copying large POD-like types too often.

• Moved it back to SmallVectorImpl, only delegating to SmallVectorTemplateBase for growAndEmplaceBack().
• Now it only defers to push_back when growing (still just for POD-like types).
• Also improved the comment to explain why the copy makes sense even for large POD-like types: that it's better than losing the realloc optimization.

See also https://reviews.llvm.org/D94800, which potentially speeds up push_back in a minor way for small POD-like types.

[dexonsmith]

Note that this depends on https://reviews.llvm.org/D93781 and predecessors, which were reverted due to the lack of https://reviews.llvm.org/D94800.

[dexonsmith]

I did a spot check of code size / compile-time, capturing clang's binary size in KiB (78460KiB => 78484KiB) and 5 runs of compiling VirtualFileSystem.cpp.o (looks like it's in the noise):

78460	baseline/build/bin/clang
        3.84 real         3.74 user         0.09 sys
        3.85 real         3.75 user         0.09 sys
        3.83 real         3.73 user         0.09 sys
        3.84 real         3.73 user         0.10 sys
        3.84 real         3.74 user         0.09 sys
78484	invalidation/build/bin/clang
        3.83 real         3.73 user         0.09 sys
        3.87 real         3.77 user         0.09 sys
        3.83 real         3.73 user         0.09 sys
        3.83 real         3.72 user         0.10 sys
        3.90 real         3.80 user         0.09 sys

"baseline" is ceaf0110ff5e0c2de1f03d65d13703d34d0d5737, and "invalidation" has this patch applied on top.

I also checked a big file, X86ISelLowering.cpp.o:

78460	baseline/build/bin/clang
       31.05 real        30.70 user         0.34 sys
       30.83 real        30.46 user         0.36 sys
       30.94 real        30.59 user         0.34 sys
       31.15 real        30.76 user         0.38 sys
       30.80 real        30.43 user         0.36 sys
78484	invalidation/build/bin/clang
       31.67 real        30.71 user         0.37 sys
       30.90 real        30.53 user         0.36 sys
       31.53 real        31.16 user         0.35 sys
       31.30 real        30.93 user         0.36 sys
       31.01 real        30.65 user         0.34 sys

Best of 5 gives 30.43 vs. 30.53, which is less than 0.4%; not sure if that's significant (certainly my environment isn't stabilized, so it's not a high quality result).

@nikic, maybe I can trigger your compile-time tracker myself (I just sent you an email), but if that doesn't work out, any chance you could kick off a perf run for this patch as well?

[dexonsmith]

Remove some unnecessary templates in SmallVector.cpp. I just realized I hadn't uploaded this version of the patch, which is what I ran the perf on.

[dexonsmith]

In D94739#2502527, @dexonsmith wrote:

[...] maybe I can trigger [the] compile-time tracker myself [...]

Done (thanks @nikic for the help!); here are the results:
https://llvm-compile-time-tracker.com/compare.php?from=ceaf0110ff5e0c2de1f03d65d13703d34d0d5737&to=7301e35eb244bb26c17ca9280813db3d9727cdbd

Looks mostly in the noise to me, with minor improvements and regressions on a few metrics (vaguely more improvements than regressions). IMO, this is good to go from a compile-time perspective.

[dblaikie]

Haven't reviewed the logic in detail - but generally looks about right to me.

[dexonsmith]

Thanks for the review; I'm holding off committing this for now because of https://reviews.llvm.org/D95112 (I must not have run all of check-llvm before).

llvm/include/llvm/ADT/SmallVector.h

protected:
   static constexpr size_t SizeTypeMax() {
     return std::numeric_limits<Size_T>::max();
   }
 
   SmallVectorBase() = delete;
   SmallVectorBase(void *FirstEl, size_t TotalCapacity)
       : BeginX(FirstEl), Capacity(TotalCapacity) {}
 
+  /// This is a helper for \a grow() that's out of line to reduce code
+  /// duplication.  This function will report a fatal error if it can't grow at
+  /// least to \p MinSize.
+  void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
+
   /// This is an implementation of the grow() method which only works
   /// on POD-like data types and is out of line to reduce code duplication.
   /// This function will report a fatal error if it cannot increase capacity.
   void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
 
-  /// Report that MinSize doesn't fit into this vector's size type. Throws
-  /// std::length_error or calls report_fatal_error.
-  LLVM_ATTRIBUTE_NORETURN static void report_size_overflow(size_t MinSize);
-  /// Report that this vector is already at maximum capacity. Throws
-  /// std::length_error or calls report_fatal_error.
-  LLVM_ATTRIBUTE_NORETURN static void report_at_maximum_capacity();
-
 public:
   size_t size() const { return Size; }
   size_t capacity() const { return Capacity; }
 
   LLVM_NODISCARD bool empty() const { return !Size; }
 
   /// Set the array size to \p N, which the current array must have enough
   /// capacity for.
void assertSafeToAddRange(const T *From, const T *To) {
     this->assertSafeToAdd(To - 1, To - From);
   }
   template <
       class ItTy,
       std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
                        bool> = false>
   void assertSafeToAddRange(ItTy, ItTy) {}
 
-  /// Check whether any argument will be invalidated by growing for
-  /// 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 *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                    size_t N) {
     size_t NewSize = This->size() + N;
     if (LLVM_LIKELY(NewSize <= This->capacity()))
       return &Elt;
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);
 
+  /// Create a new allocation big enough for \p MinSize and pass back its size
+  /// in \p NewCapacity. This is the first section of \a grow().
+  T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
+    return static_cast<T *>(
+        SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
+            MinSize, sizeof(T), NewCapacity));
+  }
+
+  /// Move existing elements over to the new allocation \p NewElts, the middle
+  /// section of \a grow().
+  void moveElementsForGrow(T *NewElts);
+
+  /// Transfer ownership of the allocation, finishing up \a grow().
+  void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
+
   /// Reserve enough space to add one element, and return the updated element
   /// pointer in case it was a reference to the storage.
   const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
     return this->reserveForParamAndGetAddressImpl(this, Elt, N);
   }
 
   /// Reserve enough space to add one element, and return the updated element
   /// pointer in case it was a reference to the storage.
   T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
     return const_cast<T *>(
         this->reserveForParamAndGetAddressImpl(this, Elt, N));
   }
 
   static T &&forward_value_param(T &&V) { return std::move(V); }
   static const T &forward_value_param(const T &V) { return V; }
 
+  void growAndAssign(size_t NumElts, const T &Elt) {
+    // Grow manually in case Elt is an internal reference.
+    size_t NewCapacity;
+    T *NewElts = mallocForGrow(NumElts, NewCapacity);
+    std::uninitialized_fill_n(NewElts, NumElts, Elt);
+    this->destroy_range(this->begin(), this->end());
+    takeAllocationForGrow(NewElts, NewCapacity);
+    this->set_size(NumElts);
+  }
+
+  template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
+    // Grow manually in case one of Args is an internal reference.
+    size_t NewCapacity;
+    T *NewElts = mallocForGrow(0, NewCapacity);
+    ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
+    moveElementsForGrow(NewElts);
+    takeAllocationForGrow(NewElts, NewCapacity);
+    this->set_size(this->size() + 1);
+    return this->back();
+  }
+
 public:
   void push_back(const T &Elt) {
     const T *EltPtr = reserveForParamAndGetAddress(Elt);
     ::new ((void *)this->end()) T(*EltPtr);
     this->set_size(this->size() + 1);
   }
 
   void push_back(T &&Elt) {
     T *EltPtr = reserveForParamAndGetAddress(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();
   }
 };
 
 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 template <typename T, bool TriviallyCopyable>
 void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
-  // Ensure we can fit the new capacity.
-  // This is only going to be applicable when the capacity is 32 bit.
-  if (MinSize > this->SizeTypeMax())
-    this->report_size_overflow(MinSize);
-
-  // Ensure we can meet the guarantee of space for at least one more element.
-  // The above check alone will not catch the case where grow is called with a
-  // default MinSize of 0, but the current capacity cannot be increased.
-  // This is only going to be applicable when the capacity is 32 bit.
-  if (this->capacity() == this->SizeTypeMax())
-    this->report_at_maximum_capacity();
-
-  // Always grow, even from zero.
-  size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
-  NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax());
-  T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
+  size_t NewCapacity;
+  T *NewElts = mallocForGrow(MinSize, NewCapacity);
+  moveElementsForGrow(NewElts);
+  takeAllocationForGrow(NewElts, NewCapacity);
+}
 
+// Define this out-of-line to dissuade the C++ compiler from inlining it.
+template <typename T, bool TriviallyCopyable>
+void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
+    T *NewElts) {
   // Move the elements over.
   this->uninitialized_move(this->begin(), this->end(), NewElts);
 
   // Destroy the original elements.
   destroy_range(this->begin(), this->end());
+}
 
+// Define this out-of-line to dissuade the C++ compiler from inlining it.
+template <typename T, bool TriviallyCopyable>
+void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
+    T *NewElts, size_t NewCapacity) {
   // If this wasn't grown from the inline copy, deallocate the old space.
   if (!this->isSmall())
     free(this->begin());
 
   this->BeginX = NewElts;
   this->Capacity = NewCapacity;
 }
 
protected:
   T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
     return const_cast<T *>(
         this->reserveForParamAndGetAddressImpl(this, Elt, N));
   }
 
   /// Copy \p V or return a reference, depending on \a ValueParamT.
   static ValueParamT forward_value_param(ValueParamT V) { return V; }
 
+  void growAndAssign(size_t NumElts, T Elt) {
+    // Elt has been copied in case it's an internal reference, side-stepping
+    // reference invalidation problems without losing the realloc optimization.
+    this->set_size(0);
+    this->grow(NumElts);
+    std::uninitialized_fill_n(this->begin(), NumElts, Elt);
+    this->set_size(NumElts);
+  }
+
+  template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
+    // Use push_back with a copy in case Args has an internal reference,
+    // side-stepping reference invalidation problems without losing the realloc
+    // optimization.
+    push_back(T(std::forward<ArgTypes>(Args)...));
+    return this->back();
+  }
+
 public:
   void push_back(ValueParamT Elt) {
     const T *EltPtr = reserveForParamAndGetAddress(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); }
void append(size_type NumInputs, ValueParamT Elt) {
     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 &
-  // re-initializing them - for all assign(...) variants.
+  void assign(size_type NumElts, ValueParamT Elt) {
+    // Note that Elt could be an internal reference.
+    if (NumElts > this->capacity()) {
+      this->growAndAssign(NumElts, Elt);
+      return;
+    }
 
-  void assign(size_type NumElts, const T &Elt) {
-    this->assertSafeToReferenceAfterResize(&Elt, 0);
-    clear();
-    this->reserve(NumElts);
+    // Assign over existing elements.
+    std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
+    if (NumElts > this->size())
+      std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
+    else if (NumElts < this->size())
+      this->destroy_range(this->begin() + NumElts, this->end());
     this->set_size(NumElts);
-    std::uninitialized_fill(this->begin(), this->end(), Elt);
   }
 
+  // FIXME: Consider assigning over existing elements, rather than clearing &
+  // re-initializing them - for all assign(...) variants.
+
   template <typename in_iter,
             typename = std::enable_if_t<std::is_convertible<
                 typename std::iterator_traits<in_iter>::iterator_category,
                 std::input_iterator_tag>::value>>
   void assign(in_iter in_start, in_iter in_end) {
     this->assertSafeToReferenceAfterClear(in_start, in_end);
     clear();
     append(in_start, in_end);
iterator insert(iterator I, ItTy From, ItTy To) {
     return I;
   }
 
   void insert(iterator I, std::initializer_list<T> IL) {
     insert(I, IL.begin(), IL.end());
   }
 
   template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
-    this->assertSafeToEmplace(Args...);
     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
-      this->grow();
+      return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
+
     ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
     this->set_size(this->size() + 1);
     return this->back();
   }
 
   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
 
   SmallVectorImpl &operator=(SmallVectorImpl &&RHS);

llvm/lib/Support/SmallVector.cpp

 static_assert(sizeof(SmallVector<void *, 1>) ==
                   sizeof(unsigned) * 2 + sizeof(void *) * 2,
               "wasted space in SmallVector size 1");
 
 static_assert(sizeof(SmallVector<char, 0>) ==
                   sizeof(void *) * 2 + sizeof(void *),
               "1 byte elements have word-sized type for size and capacity");
 
-template <class Size_T>
-void SmallVectorBase<Size_T>::report_size_overflow(size_t MinSize) {
+/// Report that MinSize doesn't fit into this vector's size type. Throws
+/// std::length_error or calls report_fatal_error.
+LLVM_ATTRIBUTE_NORETURN
+static void report_size_overflow(size_t MinSize, size_t MaxSize);
+static void report_size_overflow(size_t MinSize, size_t MaxSize) {
   std::string Reason = "SmallVector unable to grow. Requested capacity (" +
                        std::to_string(MinSize) +
                        ") is larger than maximum value for size type (" +
-                       std::to_string(SizeTypeMax()) + ")";
+                       std::to_string(MaxSize) + ")";
 #ifdef LLVM_ENABLE_EXCEPTIONS
   throw std::length_error(Reason);
 #else
   report_fatal_error(Reason);
 #endif
 }
 
-template <class Size_T> void SmallVectorBase<Size_T>::report_at_maximum_capacity() {
+/// Report that this vector is already at maximum capacity. Throws
+/// std::length_error or calls report_fatal_error.
+LLVM_ATTRIBUTE_NORETURN static void report_at_maximum_capacity(size_t MaxSize);
+static void report_at_maximum_capacity(size_t MaxSize) {
   std::string Reason =
       "SmallVector capacity unable to grow. Already at maximum size " +
-      std::to_string(SizeTypeMax());
+      std::to_string(MaxSize);
 #ifdef LLVM_ENABLE_EXCEPTIONS
   throw std::length_error(Reason);
 #else
   report_fatal_error(Reason);
 #endif
 }
 
 // Note: Moving this function into the header may cause performance regression.
 template <class Size_T>
-void SmallVectorBase<Size_T>::grow_pod(void *FirstEl, size_t MinSize,
-                                       size_t TSize) {
+static size_t getNewCapacity(size_t MinSize, size_t TSize, size_t OldCapacity) {
+  constexpr size_t MaxSize = std::numeric_limits<Size_T>::max();
+
   // Ensure we can fit the new capacity.
   // This is only going to be applicable when the capacity is 32 bit.
-  if (MinSize > SizeTypeMax())
-    report_size_overflow(MinSize);
+  if (MinSize > MaxSize)
+    report_size_overflow(MinSize, MaxSize);
 
   // Ensure we can meet the guarantee of space for at least one more element.
   // The above check alone will not catch the case where grow is called with a
   // default MinSize of 0, but the current capacity cannot be increased.
   // This is only going to be applicable when the capacity is 32 bit.
-  if (capacity() == SizeTypeMax())
-    report_at_maximum_capacity();
+  if (OldCapacity == MaxSize)
+    report_at_maximum_capacity(MaxSize);
 
   // In theory 2*capacity can overflow if the capacity is 64 bit, but the
   // original capacity would never be large enough for this to be a problem.
-  size_t NewCapacity = 2 * capacity() + 1; // Always grow.
-  NewCapacity = std::min(std::max(NewCapacity, MinSize), SizeTypeMax());
+  size_t NewCapacity = 2 * OldCapacity + 1; // Always grow.
+  return std::min(std::max(NewCapacity, MinSize), MaxSize);
+}
 
+// Note: Moving this function into the header may cause performance regression.
+template <class Size_T>
+void *SmallVectorBase<Size_T>::mallocForGrow(size_t MinSize, size_t TSize,
+                                             size_t &NewCapacity) {
+  NewCapacity = getNewCapacity<Size_T>(MinSize, TSize, this->capacity());
+  return llvm::safe_malloc(NewCapacity * TSize);
+}
+
+// Note: Moving this function into the header may cause performance regression.
+template <class Size_T>
+void SmallVectorBase<Size_T>::grow_pod(void *FirstEl, size_t MinSize,
+                                       size_t TSize) {
+  size_t NewCapacity = getNewCapacity<Size_T>(MinSize, TSize, this->capacity());
   void *NewElts;
   if (BeginX == FirstEl) {
     NewElts = safe_malloc(NewCapacity * TSize);
 
     // Copy the elements over.  No need to run dtors on PODs.
     memcpy(NewElts, this->BeginX, size() * TSize);
   } else {
     // If this wasn't grown from the inline copy, grow the allocated space.

llvm/unittests/ADT/SmallVectorTest.cpp

#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
 
   // Confirm this checks for growth when there's more than one element
   // appended.
   EXPECT_DEATH(V.append(V.begin(), V.end()), this->AssertionMessage);
 #endif
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, Assign) {
+  // 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
-  // Regardless of capacity, assign should never reference an internal element.
-  EXPECT_DEATH(V.assign(1, V.back()), this->AssertionMessage);
-  EXPECT_DEATH(V.assign(this->NumBuiltinElts(V), V.back()),
-               this->AssertionMessage);
-  EXPECT_DEATH(V.assign(this->NumBuiltinElts(V) + 1, V.back()),
-               this->AssertionMessage);
-#endif
+  int N = this->NumBuiltinElts(V);
+  ASSERT_EQ(unsigned(N), V.size());
+  ASSERT_EQ(unsigned(N), V.capacity());
+
+  // Check assign that shrinks in small mode.
+  V.assign(1, V.back());
+  EXPECT_EQ(1u, V.size());
+  EXPECT_EQ(N, V[0]);
+
+  // Check assign that grows within small mode.
+  ASSERT_LT(V.size(), V.capacity());
+  V.assign(V.capacity(), V.back());
+  for (int I = 0, E = V.size(); I != E; ++I) {
+    EXPECT_EQ(N, V[I]);
+
+    // Reset to [1, 2, ...].
+    V[I] = I + 1;
+  }
+
+  // Check assign that grows to large mode.
+  ASSERT_EQ(2, V[1]);
+  V.assign(V.capacity() + 1, V[1]);
+  for (int I = 0, E = V.size(); I != E; ++I) {
+    EXPECT_EQ(2, V[I]);
+
+    // Reset to [1, 2, ...].
+    V[I] = I + 1;
+  }
+
+  // Check assign that shrinks in large mode.
+  V.assign(1, V[1]);
+  EXPECT_EQ(2, V[0]);
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, AssignRange) {
   auto &V = this->V;
 #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
#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
 
   // Confirm this checks for growth when there's more than one element
   // inserted.
   EXPECT_DEATH(V.insert(V.begin(), V.begin(), V.end()), this->AssertionMessage);
 #endif
 }
 
 TYPED_TEST(SmallVectorReferenceInvalidationTest, EmplaceBack) {
+  // 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.emplace_back(V.back()), this->AssertionMessage);
-#endif
+  int N = this->NumBuiltinElts(V);
+
+  // Push back a reference to last element when growing from small storage.
+  V.emplace_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.emplace_back(V.back());
+  EXPECT_EQ(int(V.size()) - 1, V.back());
 }
 
 template <class VectorT>
 class SmallVectorInternalReferenceInvalidationTest
     : public SmallVectorTestBase {
 protected:
   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(std::make_pair(0, 0));
+    for (int I = 0, E = NumBuiltinElts(V); I != E; ++I)
+      V.emplace_back(I + 1, I + 1);
   }
 };
 
 // Test pairs of the same types from SmallVectorReferenceInvalidationTestTypes.
 using SmallVectorInternalReferenceInvalidationTestTypes =
-    ::testing::Types<SmallVector<std::pair<int, int>, 1>,
-                     SmallVector<std::pair<Constructable, Constructable>, 1>>;
+    ::testing::Types<SmallVector<std::pair<int, int>, 3>,
+                     SmallVector<std::pair<Constructable, Constructable>, 3>>;
 
 TYPED_TEST_CASE(SmallVectorInternalReferenceInvalidationTest,
                 SmallVectorInternalReferenceInvalidationTestTypes);
 
 TYPED_TEST(SmallVectorInternalReferenceInvalidationTest, EmplaceBack) {
+  // 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.emplace_back(V.back().first, 0), this->AssertionMessage);
-  EXPECT_DEATH(V.emplace_back(0, V.back().second), this->AssertionMessage);
-#endif
+  int N = this->NumBuiltinElts(V);
+
+  // Push back a reference to last element when growing from small storage.
+  V.emplace_back(V.back().first, V.back().second);
+  EXPECT_EQ(N, V.back().first);
+  EXPECT_EQ(N, V.back().second);
+
+  // Check that the old value is still there (not moved away).
+  EXPECT_EQ(N, V[V.size() - 2].first);
+  EXPECT_EQ(N, V[V.size() - 2].second);
+
+  // Fill storage again.
+  V.back().first = V.back().second = V.size();
+  while (V.size() < V.capacity())
+    V.emplace_back(V.size() + 1, V.size() + 1);
+
+  // Push back a reference to last element when growing from large storage.
+  V.emplace_back(V.back().first, V.back().second);
+  EXPECT_EQ(int(V.size()) - 1, V.back().first);
+  EXPECT_EQ(int(V.size()) - 1, V.back().second);
 }
 
 } // end namespace