HomePhabricator

ADT: Fix reference invalidation in SmallVector::emplace_back and assign(N,V)

Authored by dexonsmith on Jan 14 2021, 4:40 PM.

Description

ADT: Fix reference invalidation in SmallVector::emplace_back and assign(N,V)

This fixes 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?)

For POD-like types, reimplement emplace_back() in terms of
push_back(), taking a copy even for large T rather than lose the
realloc optimization in grow_pod().

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

  • mallocForGrow() calculates the new capacity and returns the result of safe_malloc(). We only need a single definition per SmallVectorBase so this is defined in SmallVector.cpp to avoid code size bloat. Moving this part of non-POD grow to the source file also allows the logic to be easily shared with grow_pod, and report_size_overflow() and report_at_maximum_capacity() can move there too.
  • moveElementsForGrow() moves elements from the old to the new allocation.
  • takeAllocationForGrow() frees the old allocation and saves the new allocation and capacity .

SmallVector:assign(size_type, const T&) also uses the split-grow
operations for non-POD, but it also has a 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 (potentially invalidating references). The new
implementation skips destruction and uses copy-assignment for the prefix
of the new vector that fits. 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 simpler implementation is that if the vector has to
grow there will be size() redundant copy operations.

(I had planned on splitting this patch up into three for committing
(after getting performance numbers / initial review), but I've realized
that if this does for some reason need to be reverted we'll probably
want to revert the whole package...)

Differential Revision: https://reviews.llvm.org/D94739