diff --git a/llvm/include/llvm/ADT/SmallVector.h b/llvm/include/llvm/ADT/SmallVector.h --- a/llvm/include/llvm/ADT/SmallVector.h +++ b/llvm/include/llvm/ADT/SmallVector.h @@ -13,6 +13,7 @@ #ifndef LLVM_ADT_SMALLVECTOR_H #define LLVM_ADT_SMALLVECTOR_H +#include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/ErrorHandling.h" @@ -34,6 +35,22 @@ namespace llvm { +template class GrowBufferBase { +private: + llvm::PointerIntPair PtrAndNeedsFree; + Size_T Size; + +public: + Size_T getSize() const { return Size; } + void setSize(Size_T NewSize) { Size = NewSize; } + + void *getBegin() const { return PtrAndNeedsFree.getPointer(); } + void setBegin(void *Ptr) { PtrAndNeedsFree.setPointer(Ptr); } + + bool getNeedsFree() const { return PtrAndNeedsFree.getInt(); } + void setNeedsFree(bool Val) { PtrAndNeedsFree.setInt(Val); } +}; + /// This is all the stuff common to all SmallVectors. /// /// The template parameter specifies the type which should be used to hold the @@ -56,11 +73,18 @@ SmallVectorBase(void *FirstEl, size_t TotalCapacity) : BeginX(FirstEl), Capacity(TotalCapacity) {} + size_t grow_size(size_t MinSize); + /// 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); + GrowBufferBase split_grow_impl(void *FirstEl, size_t MinSize, + size_t TSize); + + void finish_grow(const GrowBufferBase &Buffer, 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); @@ -108,6 +132,7 @@ class SmallVectorTemplateCommon : public SmallVectorBase> { using Base = SmallVectorBase>; + using GrowBuffer = GrowBufferBase>; /// Find the address of the first element. For this pointer math to be valid /// with small-size of 0 for T with lots of alignment, it's important that @@ -126,6 +151,14 @@ Base::grow_pod(getFirstEl(), MinSize, TSize); } + GrowBuffer split_grow_common(size_t MinSize, size_t TSize) { + return this->split_grow_impl(getFirstEl(), MinSize, TSize); + } + + void finish_grow_pod(const GrowBuffer &Buffer, size_t TSize) { + Base::finish_grow(Buffer, TSize); + } + /// Return true if this is a smallvector which has not had dynamic /// memory allocated for it. bool isSmall() const { return this->BeginX == getFirstEl(); } @@ -221,6 +254,7 @@ class SmallVectorTemplateBase : public SmallVectorTemplateCommon { protected: SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon(Size) {} + using GrowBuffer = GrowBufferBase>; static void destroy_range(T *S, T *E) { while (S != E) { @@ -249,19 +283,37 @@ /// element, or MinSize more elements if specified. void grow(size_t MinSize = 0); + GrowBuffer split_grow(size_t MinSize = 0) { + return this->split_grow_common(MinSize, sizeof(T)); + } + + void finish_grow(const GrowBuffer &Buff); + public: void push_back(const T &Elt) { - if (LLVM_UNLIKELY(this->size() >= this->capacity())) - this->grow(); + GrowBuffer Buffer; + bool NeedsSwap = false; + if (LLVM_UNLIKELY(this->size() >= this->capacity())) { + Buffer = split_grow(); + NeedsSwap = true; + } ::new ((void*) this->end()) T(Elt); this->set_size(this->size() + 1); + if (NeedsSwap) + finish_grow(Buffer); } void push_back(T &&Elt) { - if (LLVM_UNLIKELY(this->size() >= this->capacity())) - this->grow(); + GrowBuffer Buffer; + bool NeedsSwap = false; + if (LLVM_UNLIKELY(this->size() >= this->capacity())) { + Buffer = split_grow(); + NeedsSwap = true; + } ::new ((void*) this->end()) T(::std::move(Elt)); this->set_size(this->size() + 1); + if (NeedsSwap) + finish_grow(Buffer); } void pop_back() { @@ -273,21 +325,8 @@ // Define this out-of-line to dissuade the C++ compiler from inlining it. template void SmallVectorTemplateBase::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()); + + size_t NewCapacity = this->grow_size(MinSize); T *NewElts = static_cast(llvm::safe_malloc(NewCapacity*sizeof(T))); // Move the elements over. @@ -304,6 +343,23 @@ this->Capacity = NewCapacity; } +// Define this out-of-line to dissuade the C++ compiler from inlining it. +template +void SmallVectorTemplateBase::finish_grow( + const GrowBuffer &Buff) { + T *Begin = static_cast(Buff.getBegin()); + T *End = Begin + Buff.getSize(); + // Move the elements over. + this->uninitialized_move(Begin, End, this->begin()); + + // Destroy the original elements. + destroy_range(Begin, End); + + // If this wasn't grown from the inline copy, deallocate the old space. + if (Buff.getNeedsFree()) + free(Buff.getBegin()); +} + /// SmallVectorTemplateBase - 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 @@ -312,6 +368,7 @@ class SmallVectorTemplateBase : public SmallVectorTemplateCommon { protected: SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon(Size) {} + using GrowBuffer = GrowBufferBase>; // No need to do a destroy loop for POD's. static void destroy_range(T *, T *) {} @@ -351,12 +408,26 @@ /// least one more element or MinSize if specified. void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); } + GrowBuffer split_grow(size_t MinSize = 0) { + return this->split_grow_common(MinSize, sizeof(T)); + } + + void finish_grow(const GrowBuffer &Buffer) { + return this->finish_grow_pod(Buffer, sizeof(T)); + } + public: void push_back(const T &Elt) { - if (LLVM_UNLIKELY(this->size() >= this->capacity())) - this->grow(); + GrowBuffer Buffer; + bool NeedsSwap = false; + if (LLVM_UNLIKELY(this->size() >= this->capacity())) { + Buffer = split_grow(); + NeedsSwap = true; + } memcpy(reinterpret_cast(this->end()), &Elt, sizeof(T)); this->set_size(this->size() + 1); + if (NeedsSwap) + finish_grow(Buffer); } void pop_back() { this->set_size(this->size() - 1); } @@ -367,6 +438,7 @@ template class SmallVectorImpl : public SmallVectorTemplateBase { using SuperClass = SmallVectorTemplateBase; + using GrowBuffer = GrowBufferBase>; public: using iterator = typename SuperClass::iterator; @@ -379,6 +451,9 @@ explicit SmallVectorImpl(unsigned N) : SmallVectorTemplateBase(N) {} + void finish_grow_split(const GrowBuffer &Buffer, size_t InsStart, + size_t InsCount = 1); + public: SmallVectorImpl(const SmallVectorImpl &) = delete; @@ -439,19 +514,31 @@ std::input_iterator_tag>::value>> void append(in_iter in_start, in_iter in_end) { size_type NumInputs = std::distance(in_start, in_end); - if (NumInputs > this->capacity() - this->size()) - this->grow(this->size()+NumInputs); + GrowBuffer Buffer; + bool NeedsSwap = false; + if (NumInputs > this->capacity() - this->size()) { + Buffer = this->split_grow(this->size() + NumInputs); + NeedsSwap = true; + } this->uninitialized_copy(in_start, in_end, this->end()); + if (NeedsSwap) + this->finish_grow(Buffer); this->set_size(this->size() + NumInputs); } /// Append \p NumInputs copies of \p Elt to the end. void append(size_type NumInputs, const T &Elt) { - if (NumInputs > this->capacity() - this->size()) - this->grow(this->size()+NumInputs); + GrowBuffer Buffer; + bool NeedsSwap = false; + if (NumInputs > this->capacity() - this->size()) { + Buffer = this->split_grow(this->size() + NumInputs); + NeedsSwap = true; + } std::uninitialized_fill_n(this->end(), NumInputs, Elt); + if (NeedsSwap) + this->finish_grow(Buffer); this->set_size(this->size() + NumInputs); } @@ -528,8 +615,11 @@ if (this->size() >= this->capacity()) { size_t EltNo = I-this->begin(); - this->grow(); - I = this->begin()+EltNo; + GrowBuffer Buffer = this->split_grow(); + I = this->begin() + EltNo; + ::new (I) T(::std::move(Elt)); + finish_grow_split(Buffer, EltNo, 1); + return I; } ::new ((void*) this->end()) T(::std::move(this->back())); @@ -558,8 +648,11 @@ if (this->size() >= this->capacity()) { size_t EltNo = I-this->begin(); - this->grow(); - I = this->begin()+EltNo; + GrowBuffer Buffer = this->split_grow(); + I = this->begin() + EltNo; + ::new (I) T(Elt); + finish_grow_split(Buffer, EltNo, 1); + return I; } ::new ((void*) this->end()) T(std::move(this->back())); // Push everything else over. @@ -588,11 +681,13 @@ assert(I >= this->begin() && "Insertion iterator is out of bounds."); assert(I <= this->end() && "Inserting past the end of the vector."); - // Ensure there is enough space. - reserve(this->size() + NumToInsert); - - // Uninvalidate the iterator. - I = this->begin()+InsertElt; + if (this->size() + NumToInsert > this->capacity()) { + GrowBuffer Buffer = this->split_grow(this->size() + NumToInsert); + I = this->begin() + InsertElt; + std::uninitialized_fill_n(I, NumToInsert, Elt); + finish_grow_split(Buffer, InsertElt, NumToInsert); + return I; + } // If there are more elements between the insertion point and the end of the // range than there are being inserted, we can use a simple approach to @@ -645,11 +740,13 @@ size_t NumToInsert = std::distance(From, To); - // Ensure there is enough space. - reserve(this->size() + NumToInsert); - - // Uninvalidate the iterator. - I = this->begin()+InsertElt; + if (this->size() + NumToInsert > this->capacity()) { + GrowBuffer Buffer = this->split_grow(this->size() + NumToInsert); + I = this->begin() + InsertElt; + this->uninitialized_copy(From, To, I); + finish_grow_split(Buffer, InsertElt, NumToInsert); + return I; + } // If there are more elements between the insertion point and the end of the // range than there are being inserted, we can use a simple approach to @@ -692,10 +789,16 @@ } template reference emplace_back(ArgTypes &&... Args) { - if (LLVM_UNLIKELY(this->size() >= this->capacity())) - this->grow(); + GrowBuffer Buffer; + bool NeedsSwap = false; + if (LLVM_UNLIKELY(this->size() >= this->capacity())) { + Buffer = this->split_grow(); + NeedsSwap = true; + } ::new ((void *)this->end()) T(std::forward(Args)...); this->set_size(this->size() + 1); + if (NeedsSwap) + this->finish_grow(Buffer); return this->back(); } @@ -717,6 +820,20 @@ } }; +template +void SmallVectorImpl::finish_grow_split(const GrowBuffer &Buffer, + size_t InsStart, size_t InsCount) { + + iterator OldBegin = static_cast(Buffer.getBegin()); + this->uninitialized_move(OldBegin, OldBegin + InsStart, this->begin()); + this->uninitialized_move(OldBegin + InsStart, OldBegin + Buffer.getSize(), + this->begin() + InsStart + InsCount); + this->destroy_range(OldBegin, OldBegin + Buffer.getSize()); + if (Buffer.getNeedsFree()) + free(OldBegin); + this->set_size(this->size() + InsCount); +} + template void SmallVectorImpl::swap(SmallVectorImpl &RHS) { if (this == &RHS) return; diff --git a/llvm/lib/Support/SmallVector.cpp b/llvm/lib/Support/SmallVector.cpp --- a/llvm/lib/Support/SmallVector.cpp +++ b/llvm/lib/Support/SmallVector.cpp @@ -69,10 +69,8 @@ #endif } -// Note: Moving this function into the header may cause performance regression. template -void SmallVectorBase::grow_pod(void *FirstEl, size_t MinSize, - size_t TSize) { +size_t SmallVectorBase::grow_size(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 > SizeTypeMax()) @@ -88,8 +86,15 @@ // 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()); + return std::min(std::max(NewCapacity, MinSize), SizeTypeMax()); +} +// Note: Moving this function into the header may cause performance regression. +template +void SmallVectorBase::grow_pod(void *FirstEl, size_t MinSize, + size_t TSize) { + + size_t NewCapacity = grow_size(MinSize); void *NewElts; if (BeginX == FirstEl) { NewElts = safe_malloc(NewCapacity * TSize); @@ -105,6 +110,35 @@ this->Capacity = NewCapacity; } +template +GrowBufferBase SmallVectorBase::split_grow_impl(void *FirstEl, + size_t MinSize, + size_t TSize) { + size_t NewCapacity = grow_size(MinSize); + + void *NewElts = safe_malloc(NewCapacity * TSize); + + GrowBufferBase Buffer; + Buffer.setBegin(this->BeginX); + Buffer.setSize(this->Size); + Buffer.setNeedsFree(this->BeginX != FirstEl); + + this->BeginX = NewElts; + this->Capacity = NewCapacity; + + return Buffer; +} + +template +void SmallVectorBase::finish_grow(const GrowBufferBase &Buffer, + size_t TSize) { + memcpy(this->BeginX, Buffer.getBegin(), Buffer.getSize() * TSize); + + // If this wasn't grown from the inline copy, deallocate the old space. + if (Buffer.getNeedsFree()) + free(Buffer.getBegin()); +} + template class llvm::SmallVectorBase; // Disable the uint64_t instantiation for 32-bit builds. diff --git a/llvm/unittests/ADT/SmallVectorTest.cpp b/llvm/unittests/ADT/SmallVectorTest.cpp --- a/llvm/unittests/ADT/SmallVectorTest.cpp +++ b/llvm/unittests/ADT/SmallVectorTest.cpp @@ -32,39 +32,45 @@ static int numAssignmentCalls; static int numMoveAssignmentCalls; static int numCopyAssignmentCalls; + enum class ObjectState { Destroyed = 0, Constructed, MovedFrom }; - bool constructed; + ObjectState State; int value; public: - Constructable() : constructed(true), value(0) { + Constructable() : State(ObjectState::Constructed), value(0) { ++numConstructorCalls; } - Constructable(int val) : constructed(true), value(val) { + Constructable(int val) : State(ObjectState::Constructed), value(val) { ++numConstructorCalls; } - Constructable(const Constructable & src) : constructed(true) { + Constructable(const Constructable &src) : State(src.State) { + EXPECT_EQ(State, ObjectState::Constructed); value = src.value; ++numConstructorCalls; ++numCopyConstructorCalls; } - Constructable(Constructable && src) : constructed(true) { + Constructable(Constructable &&src) : State(src.State) { + EXPECT_EQ(State, ObjectState::Constructed); value = src.value; + src.State = ObjectState::MovedFrom; ++numConstructorCalls; ++numMoveConstructorCalls; } ~Constructable() { - EXPECT_TRUE(constructed); + EXPECT_NE(State, ObjectState::Destroyed); ++numDestructorCalls; - constructed = false; + State = ObjectState::Destroyed; } Constructable & operator=(const Constructable & src) { - EXPECT_TRUE(constructed); + EXPECT_NE(State, ObjectState::Destroyed); + EXPECT_EQ(src.State, ObjectState::Constructed); + State = src.State; value = src.value; ++numAssignmentCalls; ++numCopyAssignmentCalls; @@ -72,14 +78,18 @@ } Constructable & operator=(Constructable && src) { - EXPECT_TRUE(constructed); + EXPECT_NE(State, ObjectState::Destroyed); + EXPECT_EQ(src.State, ObjectState::Constructed); + State = src.State; value = src.value; + src.State = ObjectState::MovedFrom; ++numAssignmentCalls; ++numMoveAssignmentCalls; return *this; } int getValue() const { + EXPECT_EQ(State, ObjectState::Constructed); return abs(value); } @@ -462,8 +472,12 @@ SCOPED_TRACE("AssignTest"); this->theVector.push_back(Constructable(1)); + Constructable::reset(); this->theVector.assign(2, Constructable(77)); this->assertValuesInOrder(this->theVector, 2u, 77, 77); + EXPECT_EQ(Constructable::getNumCopyAssignmentCalls() + + Constructable::getNumCopyConstructorCalls(), + 2); } // Assign test @@ -481,8 +495,12 @@ SCOPED_TRACE("AssignTest"); this->theVector.push_back(Constructable(1)); + Constructable::reset(); this->theVector.assign(2, 7); this->assertValuesInOrder(this->theVector, 2u, 7, 7); + EXPECT_EQ(Constructable::getNumCopyAssignmentCalls() + + Constructable::getNumCopyConstructorCalls(), + 2); } // Move-assign test @@ -564,21 +582,28 @@ this->makeSequence(this->theVector, 1, 4); Constructable::reset(); + bool RequiresGrowth = this->theVector.capacity() < 6; auto I = this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16)); - // Move construct the top element into newly allocated space, and optionally - // reallocate the whole buffer, move constructing into it. - // FIXME: This is inefficient, we shouldn't move things into newly allocated - // space, then move them up/around, there should only be 2 or 4 move - // constructions here. - EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || - Constructable::getNumMoveConstructorCalls() == 6); - // Move assign the next two to shift them up and make a gap. - EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); - // Copy construct the two new elements from the parameter. - EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); - // All without any copy construction. - EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); + + if (RequiresGrowth) { + // Moving [1] and [2,3,4] into the new storage. + EXPECT_EQ(4, Constructable::getNumMoveConstructorCalls()); + // Copy construct the new elements directly into the new storage. + EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); + // Nothing is move or copy assigned in the growth case. + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + } else { + // Shifting [3,4] down 2 blocks into uninitialized storage. + EXPECT_EQ(2, Constructable::getNumMoveConstructorCalls()); + // Shifting [2] into where [4] lived. + EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); + // Copy assign the two new elements inside the buffer. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); + } + EXPECT_EQ(this->theVector.begin() + 1, I); this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4); } @@ -635,18 +660,28 @@ this->makeSequence(this->theVector, 1, 3); Constructable::reset(); + bool RequiresGrowth = this->theVector.capacity() < 6; auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3); - // Move construct the top 3 elements into newly allocated space. - // Possibly move the whole sequence into new space first. - // FIXME: This is inefficient, we shouldn't move things into newly allocated - // space, then move them up/around, there should only be 2 or 3 move - // constructions here. - EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || - Constructable::getNumMoveConstructorCalls() == 5); - // Copy assign the lower 2 new elements into existing space. - EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); - // Copy construct the third element into newly allocated space. - EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); + + if (RequiresGrowth) { + // Moving [1] and [2,3] into the new storage. + EXPECT_EQ(3, Constructable::getNumMoveConstructorCalls()); + // Copy construct the 3 items from Arr into the new storage. + EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls()); + // Nothing is move or copy assigned in the growth case. + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + } else { + // Shifting [2,3] down 3 blocks into uninitialized storage. + EXPECT_EQ(2, Constructable::getNumMoveConstructorCalls()); + // Copy assign the lower 2 new elements into existing storage. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + // Copy construct the third element into uninitialized storage. + EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); + // Nothing needs to be move assigned here as the only items that need + // shifting, are shifted into uninitialized storage. + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + } EXPECT_EQ(this->theVector.begin() + 1, I); this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3); }