Index: llvm/include/llvm/ADT/SmallVector.h =================================================================== --- llvm/include/llvm/ADT/SmallVector.h +++ llvm/include/llvm/ADT/SmallVector.h @@ -270,7 +270,14 @@ (is_trivially_move_constructible::value) && std::is_trivially_destructible::value> class SmallVectorTemplateBase : public SmallVectorTemplateCommon { +public: + /// Take parameters by reference (not by value) since T is not trivially + /// copyable. + static constexpr bool TakesParamByValue = false; + protected: + using ValueParamT = const T &; + SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon(Size) {} static void destroy_range(T *S, T *E) { @@ -301,8 +308,9 @@ void grow(size_t MinSize = 0); public: - void push_back(const T &Elt) { - this->assertSafeToAdd(&Elt); + void push_back(ValueParamT Elt) { + if (!TakesParamByValue) + this->assertSafeToAdd(&Elt); if (LLVM_UNLIKELY(this->size() >= this->capacity())) this->grow(); ::new ((void*) this->end()) T(Elt); @@ -363,7 +371,16 @@ /// skipping destruction. template class SmallVectorTemplateBase : public SmallVectorTemplateCommon { +public: + /// Take parameters by value when T is small since it's trivially copyable. + static constexpr bool TakesParamByValue = + std::conditional::type::value; + protected: + using ValueParamT = + typename std::conditional::type; + SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon(Size) {} // No need to do a destroy loop for POD's. @@ -405,8 +422,9 @@ void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); } public: - void push_back(const T &Elt) { - this->assertSafeToAdd(&Elt); + void push_back(ValueParamT Elt) { + if (!TakesParamByValue) + this->assertSafeToAdd(&Elt); if (LLVM_UNLIKELY(this->size() >= this->capacity())) this->grow(); memcpy(reinterpret_cast(this->end()), &Elt, sizeof(T)); @@ -428,7 +446,11 @@ using reference = typename SuperClass::reference; using size_type = typename SuperClass::size_type; + using SmallVectorTemplateBase::TakesParamByValue; + protected: + using ValueParamT = typename SmallVectorTemplateBase::ValueParamT; + // Default ctor - Initialize to empty. explicit SmallVectorImpl(unsigned N) : SmallVectorTemplateBase(N) {} @@ -461,8 +483,9 @@ } } - void resize(size_type N, const T &NV) { - this->assertSafeToReferenceAfterResize(&NV, N); + void resize(size_type N, ValueParamT NV) { + if (!TakesParamByValue) + this->assertSafeToReferenceAfterResize(&NV, N); if (N < this->size()) { this->destroy_range(this->begin()+N, this->end()); this->set_size(N); @@ -509,8 +532,9 @@ } /// Append \p NumInputs copies of \p Elt to the end. - void append(size_type NumInputs, const T &Elt) { - this->assertSafeToAdd(&Elt, NumInputs); + void append(size_type NumInputs, ValueParamT Elt) { + if (!TakesParamByValue) + this->assertSafeToAdd(&Elt, NumInputs); if (NumInputs > this->capacity() - this->size()) this->grow(this->size()+NumInputs); @@ -525,8 +549,9 @@ // FIXME: Consider assigning over existing elements, rather than clearing & // re-initializing them - for all assign(...) variants. - void assign(size_type NumElts, const T &Elt) { - this->assertSafeToReferenceAfterResize(&Elt, 0); + void assign(size_type NumElts, ValueParamT Elt) { + if (!TakesParamByValue) + this->assertSafeToReferenceAfterResize(&Elt, 0); clear(); if (this->capacity() < NumElts) this->grow(NumElts); @@ -593,7 +618,8 @@ assert(I <= this->end() && "Inserting past the end of the vector."); // Check that adding an element won't invalidate Elt. - this->assertSafeToAdd(&Elt); + if (!TakesParamByValue) + this->assertSafeToAdd(&Elt); if (this->size() >= this->capacity()) { size_t EltNo = I-this->begin(); @@ -609,21 +635,49 @@ // If we just moved the element we're inserting, be sure to update // the reference. std::remove_reference_t *EltPtr = &Elt; - if (I <= EltPtr && EltPtr < this->end()) + if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end()) ++EltPtr; *I = ::std::forward(*EltPtr); return I; } + template < + class ArgType, + std::enable_if_t< + std::is_same>, + T>::value && + !TakesParamByValue, + bool> = true> + iterator insert_one_maybe_copy(iterator I, ArgType &&Elt) { + // TakesParamByValue is false. Just forward to insert_one_impl. + return insert_one_impl(I, std::forward(Elt)); + } + + /// insert a T, where TakesParamByValue is true. Calls insert_one_impl with a + /// copy of Elt to avoid invalidation. + template < + class ArgType, + std::enable_if_t< + std::is_same>, + T>::value && + TakesParamByValue, + bool> = true> + iterator insert_one_maybe_copy(iterator I, ArgType &&Elt) { + // TakesParamByValue is true. Call insert_one_impl with a copy of Elt. + 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(); @@ -636,7 +690,8 @@ assert(I <= this->end() && "Inserting past the end of the vector."); // Check that adding NumToInsert elements won't invalidate Elt. - this->assertSafeToAdd(&Elt, NumToInsert); + if (!TakesParamByValue) + this->assertSafeToAdd(&Elt, NumToInsert); // Ensure there is enough space. reserve(this->size() + NumToInsert); @@ -744,7 +799,9 @@ insert(I, IL.begin(), IL.end()); } - template reference emplace_back(ArgTypes &&... Args) { +private: + template + reference emplace_back_impl(ArgTypes &&... Args) { this->assertSafeToEmplace(Args...); if (LLVM_UNLIKELY(this->size() >= this->capacity())) this->grow(); @@ -753,6 +810,43 @@ return this->back(); } +public: + reference emplace_back() { return emplace_back_impl(); } + + template < + class ArgType, + std::enable_if_t< + !std::is_same>, + T>::value || + !TakesParamByValue, + bool> = true> + reference emplace_back(ArgType &&Arg) { + return emplace_back_impl(std::forward(Arg)); + } + + template < + class ArgType, + std::enable_if_t< + std::is_same>, + T>::value && + TakesParamByValue, + bool> = true> + reference emplace_back(ArgType &&Arg) { + // ArgType is a T and may be a reference into this vector, but + // TakesParamByValue is true. Forward to push_back, which will take Arg by + // value and avoid reference invalidation. + this->push_back(Arg); + return this->back(); + } + + template + reference emplace_back(ArgType1 &&Arg1, ArgType2 &&Arg2, + ArgTypes &&... Args) { + return emplace_back_impl(std::forward(Arg1), + std::forward(Arg2), + std::forward(Args)...); + } + SmallVectorImpl &operator=(const SmallVectorImpl &RHS); SmallVectorImpl &operator=(SmallVectorImpl &&RHS); @@ -943,6 +1037,8 @@ template class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl, SmallVectorStorage { + using ValueParamT = typename SmallVectorImpl::ValueParamT; + public: SmallVector() : SmallVectorImpl(N) {} @@ -951,8 +1047,8 @@ this->destroy_range(this->begin(), this->end()); } - explicit SmallVector(size_t Size, const T &Value = T()) - : SmallVectorImpl(N) { + explicit SmallVector(size_t Size, ValueParamT Value = T()) + : SmallVectorImpl(N) { this->assign(Size, Value); } Index: llvm/unittests/ADT/SmallVectorTest.cpp =================================================================== --- llvm/unittests/ADT/SmallVectorTest.cpp +++ llvm/unittests/ADT/SmallVectorTest.cpp @@ -1004,6 +1004,7 @@ template class SmallVectorReferenceInvalidationTest : public SmallVectorTestBase { protected: + bool TakesParamByValue = VectorT::TakesParamByValue; const char *AssertionMessage = "Attempting to reference an element of the vector in an operation \" " "\"that invalidates it"; @@ -1024,8 +1025,11 @@ }; // Test one type that's trivially copyable (int) and one that isn't -// (Constructable) since reference invalidation may be fixed differently for -// each. +// (Constructable). +static_assert(SmallVectorImpl::TakesParamByValue, + "int should be trivially copyable and small enough"); +static_assert(!SmallVectorImpl::TakesParamByValue, + "Constructable should not be trivially copyable"); using SmallVectorReferenceInvalidationTestTypes = ::testing::Types, SmallVector>; @@ -1034,7 +1038,10 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBack) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.push_back(V.back()); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST EXPECT_DEATH(V.push_back(V.back()), this->AssertionMessage); #endif @@ -1042,7 +1049,10 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.push_back(std::move(V.back())); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST EXPECT_DEATH(V.push_back(std::move(V.back())), this->AssertionMessage); #endif @@ -1050,7 +1060,10 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, Resize) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.resize(2, V.back()); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST EXPECT_DEATH(V.resize(2, V.back()), this->AssertionMessage); #endif @@ -1058,7 +1071,10 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, Append) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.append(1, V.back()); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST EXPECT_DEATH(V.append(1, V.back()), this->AssertionMessage); #endif @@ -1083,7 +1099,12 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, Assign) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.assign(1, V.back()); + V.assign(this->NumBuiltinElts(V), V.back()); + V.assign(this->NumBuiltinElts(V) + 1, V.back()); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST // Regardless of capacity, assign should never reference an internal element. EXPECT_DEATH(V.assign(1, V.back()), this->AssertionMessage); @@ -1106,7 +1127,10 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, Insert) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.insert(V.begin(), V.back()); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST EXPECT_DEATH(V.insert(V.begin(), V.back()), this->AssertionMessage); #endif @@ -1114,7 +1138,10 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertMoved) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.insert(V.begin(), std::move(V.back())); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST EXPECT_DEATH(V.insert(V.begin(), std::move(V.back())), this->AssertionMessage); @@ -1123,7 +1150,10 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertN) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.insert(V.begin(), 2, V.back()); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST EXPECT_DEATH(V.insert(V.begin(), 2, V.back()), this->AssertionMessage); #endif @@ -1149,12 +1179,26 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, EmplaceBack) { auto &V = this->V; - (void)V; + if (this->TakesParamByValue) { + V.emplace_back(V.back()); + return; + } #if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST EXPECT_DEATH(V.emplace_back(V.back()), this->AssertionMessage); #endif } +TYPED_TEST(SmallVectorReferenceInvalidationTest, EmplaceBackMoved) { + auto &V = this->V; + if (this->TakesParamByValue) { + V.emplace_back(std::move(V.back())); + return; + } +#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST + EXPECT_DEATH(V.emplace_back(std::move(V.back())), this->AssertionMessage); +#endif +} + template class SmallVectorInternalReferenceInvalidationTest : public SmallVectorTestBase {