Author: Duncan P. N. Exon Smith Date: 2021-01-13T19:04:20-08:00 New Revision: 56d1ffb927d03958a7a31442596df749264a7792
URL: https://github.com/llvm/llvm-project/commit/56d1ffb927d03958a7a31442596df749264a7792 DIFF: https://github.com/llvm/llvm-project/commit/56d1ffb927d03958a7a31442596df749264a7792.diff LOG: Revert "ADT: Fix reference invalidation in SmallVector::push_back and single-element insert" This reverts commit 9abac60309006db00eca0af406c2e16bef26807c since there are some bot errors on Windows: http://lab.llvm.org:8011/#/builders/127/builds/4489 ``` FAILED: lib/Support/CMakeFiles/LLVMSupport.dir/IntervalMap.cpp.obj C:\PROGRA~2\MIB055~1\2017\PROFES~1\VC\Tools\MSVC\1416~1.270\bin\Hostx64\x64\cl.exe /nologo /TP -DGTEST_HAS_RTTI=0 -DUNICODE -D_CRT_NONSTDC_NO_DEPRECATE -D_CRT_NONSTDC_NO_WARNINGS -D_CRT_SECURE_NO_DEPRECATE -D_CRT_SECURE_NO_WARNINGS -D_HAS_EXCEPTIONS=0 -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS -D_UNICODE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib\Support -IC:\b\slave\sanitizer-windows\llvm-project\llvm\lib\Support -Iinclude -IC:\b\slave\sanitizer-windows\llvm-project\llvm\include /DWIN32 /D_WINDOWS /Zc:inline /Zc:__cplusplus /Zi /Zc:strictStrings /Oi /Zc:rvalueCast /bigobj /W4 -wd4141 -wd4146 -wd4244 -wd4267 -wd4291 -wd4351 -wd4456 -wd4457 -wd4458 -wd4459 -wd4503 -wd4624 -wd4722 -wd4100 -wd4127 -wd4512 -wd4505 -wd4610 -wd4510 -wd4702 -wd4245 -wd4706 -wd4310 -wd4701 -wd4703 -wd4389 -wd4611 -wd4805 -wd4204 -wd4577 -wd4091 -wd4592 -wd4319 -wd4709 -wd4324 -w14062 -we4238 /Gw /MD /O2 /Ob2 -UNDEBUG -std:c++14 /EHs-c- /GR- /showIncludes /Folib\Support\CMakeFiles\LLVMSupport.dir\IntervalMap.cpp.obj /Fdlib\Support\CMakeFiles\LLVMSupport.dir\LLVMSupport.pdb /FS -c C:\b\slave\sanitizer-windows\llvm-project\llvm\lib\Support\IntervalMap.cpp C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(746): error C2672: 'llvm::SmallVectorImpl<T>::insert_one_maybe_copy': no matching overloaded function found with [ T=llvm::IntervalMapImpl::Path::Entry ] C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(745): note: while compiling class template member function 'llvm::IntervalMapImpl::Path::Entry *llvm::SmallVectorImpl<T>::insert(llvm::IntervalMapImpl::Path::Entry *,T &&)' with [ T=llvm::IntervalMapImpl::Path::Entry ] C:\b\slave\sanitizer-windows\llvm-project\llvm\lib\Support\IntervalMap.cpp(22): note: see reference to function template instantiation 'llvm::IntervalMapImpl::Path::Entry *llvm::SmallVectorImpl<T>::insert(llvm::IntervalMapImpl::Path::Entry *,T &&)' being compiled with [ T=llvm::IntervalMapImpl::Path::Entry ] C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(1136): note: see reference to class template instantiation 'llvm::SmallVectorImpl<T>' being compiled with [ T=llvm::IntervalMapImpl::Path::Entry ] C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/IntervalMap.h(790): note: see reference to class template instantiation 'llvm::SmallVector<llvm::IntervalMapImpl::Path::Entry,4>' being compiled C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(746): error C2783: 'llvm::IntervalMapImpl::Path::Entry *llvm::SmallVectorImpl<T>::insert_one_maybe_copy(llvm::IntervalMapImpl::Path::Entry *,ArgType &&)': could not deduce template argument for '__formal' with [ T=llvm::IntervalMapImpl::Path::Entry ] C:\b\slave\sanitizer-windows\llvm-project\llvm\include\llvm/ADT/SmallVector.h(727): note: see declaration of 'llvm::SmallVectorImpl<T>::insert_one_maybe_copy' with [ T=llvm::IntervalMapImpl::Path::Entry ] ``` Added: Modified: llvm/include/llvm/ADT/SmallVector.h llvm/unittests/ADT/SmallVectorTest.cpp Removed: ################################################################################ diff --git a/llvm/include/llvm/ADT/SmallVector.h b/llvm/include/llvm/ADT/SmallVector.h index f5293970aa9f..803588143d81 100644 --- a/llvm/include/llvm/ADT/SmallVector.h +++ b/llvm/include/llvm/ADT/SmallVector.h @@ -220,23 +220,6 @@ class SmallVectorTemplateCommon } 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 diff erence_type = ptr diff _t; @@ -320,12 +303,7 @@ 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) { @@ -355,28 +333,20 @@ class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { /// 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) { - const T *EltPtr = reserveForAndGetAddress(Elt); - ::new ((void *)this->end()) T(*EltPtr); + this->assertSafeToAdd(&Elt); + if (LLVM_UNLIKELY(this->size() >= this->capacity())) + this->grow(); + ::new ((void*) this->end()) T(Elt); this->set_size(this->size() + 1); } void push_back(T &&Elt) { - T *EltPtr = reserveForAndGetAddress(Elt); - ::new ((void *)this->end()) T(::std::move(*EltPtr)); + this->assertSafeToAdd(&Elt); + if (LLVM_UNLIKELY(this->size() >= this->capacity())) + this->grow(); + ::new ((void*) this->end()) T(::std::move(Elt)); this->set_size(this->size() + 1); } @@ -426,18 +396,7 @@ void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) { /// 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. @@ -478,22 +437,12 @@ class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { /// 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(ValueParamT Elt) { - const T *EltPtr = reserveForAndGetAddress(Elt); - memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T)); + 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)); this->set_size(this->size() + 1); } @@ -513,9 +462,6 @@ class SmallVectorImpl : public SmallVectorTemplateBase<T> { 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) {} @@ -682,12 +628,6 @@ class SmallVectorImpl : public SmallVectorTemplateBase<T> { 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; @@ -695,11 +635,14 @@ class SmallVectorImpl : public SmallVectorTemplateBase<T> { assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds."); - // Grow if necessary. - size_t Index = I - this->begin(); - std::remove_reference_t<ArgType> *EltPtr = - this->reserveForAndGetAddress(Elt); - I = this->begin() + Index; + // 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; + } ::new ((void*) this->end()) T(::std::move(this->back())); // Push everything else over. @@ -707,48 +650,21 @@ class SmallVectorImpl : public SmallVectorTemplateBase<T> { this->set_size(this->size() + 1); // If we just moved the element we're inserting, be sure to update - // 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())) + // the reference. + std::remove_reference_t<ArgType> *EltPtr = &Elt; + if (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_maybe_copy(I, std::move(Elt)); + return insert_one_impl(I, std::move(Elt)); } - iterator insert(iterator I, const T &Elt) { - return insert_one_maybe_copy(I, Elt); - } + iterator insert(iterator I, const T &Elt) { return insert_one_impl(I, Elt); } iterator insert(iterator I, size_type NumToInsert, const T &Elt) { // Convert iterator to elt# to avoid invalidating iterator when we reserve() diff --git a/llvm/unittests/ADT/SmallVectorTest.cpp b/llvm/unittests/ADT/SmallVectorTest.cpp index c880a6b6c543..d97ab577524f 100644 --- a/llvm/unittests/ADT/SmallVectorTest.cpp +++ b/llvm/unittests/ADT/SmallVectorTest.cpp @@ -53,7 +53,6 @@ class Constructable { Constructable(Constructable && src) : constructed(true) { value = src.value; - src.value = 0; ++numConstructorCalls; ++numMoveConstructorCalls; } @@ -75,7 +74,6 @@ class Constructable { Constructable & operator=(Constructable && src) { EXPECT_TRUE(constructed); value = src.value; - src.value = 0; ++numAssignmentCalls; ++numMoveAssignmentCalls; return *this; @@ -1058,16 +1056,11 @@ class SmallVectorReferenceInvalidationTest : public SmallVectorTestBase { 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. - for (int I = 0, E = NumBuiltinElts(V); I != E; ++I) - V.emplace_back(I + 1); + V.append({0, 0, 0}); } }; @@ -1081,54 +1074,19 @@ 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; - 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()); + (void)V; +#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST + EXPECT_DEATH(V.push_back(V.back()), this->AssertionMessage); +#endif } TYPED_TEST(SmallVectorReferenceInvalidationTest, PushBackMoved) { - // Note: setup adds [1, 2, ...] to V until it's at capacity in small mode. auto &V = this->V; - 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]); - } + (void)V; +#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST + EXPECT_DEATH(V.push_back(std::move(V.back())), this->AssertionMessage); +#endif } TYPED_TEST(SmallVectorReferenceInvalidationTest, Resize) { @@ -1192,53 +1150,20 @@ TYPED_TEST(SmallVectorReferenceInvalidationTest, AssignRange) { } 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; - - // 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()); +#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST + EXPECT_DEATH(V.insert(V.begin(), V.back()), this->AssertionMessage); +#endif } 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; - - // 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()); - } +#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST + EXPECT_DEATH(V.insert(V.begin(), std::move(V.back())), + this->AssertionMessage); +#endif } TYPED_TEST(SmallVectorReferenceInvalidationTest, InsertN) { _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
