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 @@ -16,10 +16,10 @@ #include "llvm/ADT/iterator_range.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/MemAlloc.h" #include "llvm/Support/type_traits.h" -#include "llvm/Support/ErrorHandling.h" #include #include #include @@ -27,6 +27,7 @@ #include #include #include +#include #include #include #include @@ -34,11 +35,23 @@ namespace llvm { -/// This is all the non-templated stuff common to all SmallVectors. -class SmallVectorBase { +/// This is all the stuff common to all SmallVectors. +/// +/// The template parameter specifies the type which should be used to hold the +/// Size and Capacity of the SmallVector, so it can be adjusted. +/// Using 32 bit size is desirable to shink the size of the SmallVector. +/// Using 64 bit size is desirable for cases like SmallVector, where a +/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for +/// buffering bitcode output - which can exceed 4GB. +template class SmallVectorBase { protected: void *BeginX; - unsigned Size = 0, Capacity; + Size_T Size = 0, Capacity; + + // The maximum size depends on size_type used. + static constexpr size_t SizeMax() { + return std::numeric_limits::max(); + } SmallVectorBase() = delete; SmallVectorBase(void *FirstEl, size_t TotalCapacity) @@ -46,7 +59,39 @@ /// 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. - void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize); + /// This function will report a fatal error if it cannot increase capacity. + void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize) { + // Ensure we can fit the new capacity. + // This is only going to be applicable if the when the capacity is 32 bit. + if (MinCapacity > SizeMax()) + report_bad_alloc_error("SmallVector capacity overflow during allocation"); + + // 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 MinCapacity of 0, but the current capacity cannot be increased. + // This is only going to be applicable if the when the capacity is 32 bit. + if (capacity() == SizeMax()) + report_bad_alloc_error("SmallVector capacity unable to grow"); + + // 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, MinCapacity), SizeMax()); + + 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. + NewElts = safe_realloc(this->BeginX, NewCapacity * TSize); + } + + this->BeginX = NewElts; + this->Capacity = NewCapacity; + } public: size_t size() const { return Size; } @@ -69,9 +114,13 @@ } }; +template +using SmallVectorSizeType = + typename std::conditional::type; + /// Figure out the offset of the first element. template struct SmallVectorAlignmentAndSize { - AlignedCharArrayUnion Base; + AlignedCharArrayUnion>> Base; AlignedCharArrayUnion FirstEl; }; @@ -79,7 +128,10 @@ /// the type T is a POD. The extra dummy template argument is used by ArrayRef /// to avoid unnecessarily requiring T to be complete. template -class SmallVectorTemplateCommon : public SmallVectorBase { +class SmallVectorTemplateCommon + : public SmallVectorBase> { + using Base = SmallVectorBase>; + /// 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 /// SmallVectorStorage is properly-aligned even for small-size of 0. @@ -91,21 +143,20 @@ // Space after 'FirstEl' is clobbered, do not add any instance vars after it. protected: - SmallVectorTemplateCommon(size_t Size) - : SmallVectorBase(getFirstEl(), Size) {} + SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {} void grow_pod(size_t MinCapacity, size_t TSize) { - SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize); + Base::grow_pod(getFirstEl(), MinCapacity, TSize); } /// Return true if this is a smallvector which has not had dynamic /// memory allocated for it. - bool isSmall() const { return BeginX == getFirstEl(); } + bool isSmall() const { return this->BeginX == getFirstEl(); } /// Put this vector in a state of being small. void resetToSmall() { - BeginX = getFirstEl(); - Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect. + this->BeginX = getFirstEl(); + this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect. } public: @@ -123,6 +174,10 @@ using pointer = T *; using const_pointer = const T *; + using Base::capacity; + using Base::empty; + using Base::size; + // forward iterator creation methods. iterator begin() { return (iterator)this->BeginX; } const_iterator begin() const { return (const_iterator)this->BeginX; } @@ -231,12 +286,21 @@ // Define this out-of-line to dissuade the C++ compiler from inlining it. template void SmallVectorTemplateBase::grow(size_t MinSize) { - if (MinSize > UINT32_MAX) + // Ensure we can fit the new capacity. + // This is only going to be applicable if the when the capacity is 32 bit. + if (MinSize > this->SizeMax()) report_bad_alloc_error("SmallVector capacity overflow during allocation"); + // 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 MinCapacity of 0, but the current capacity cannot be increased. + // This is only going to be applicable if the when the capacity is 32 bit. + if (this->capacity() == this->SizeMax()) + report_bad_alloc_error("SmallVector capacity unable to grow"); + // Always grow, even from zero. size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2)); - NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX)); + NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeMax()); T *NewElts = static_cast(llvm::safe_malloc(NewCapacity*sizeof(T))); // Move the elements over. 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 @@ -36,30 +36,6 @@ static_assert(sizeof(SmallVector) == sizeof(unsigned) * 2 + sizeof(void *) * 2, "wasted space in SmallVector size 1"); - -/// grow_pod - This is an implementation of the grow() method which only works -/// on POD-like datatypes and is out of line to reduce code duplication. -void SmallVectorBase::grow_pod(void *FirstEl, size_t MinCapacity, - size_t TSize) { - // Ensure we can fit the new capacity in 32 bits. - if (MinCapacity > UINT32_MAX) - report_bad_alloc_error("SmallVector capacity overflow during allocation"); - - size_t NewCapacity = 2 * capacity() + 1; // Always grow. - NewCapacity = - std::min(std::max(NewCapacity, MinCapacity), size_t(UINT32_MAX)); - - 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. - NewElts = safe_realloc(this->BeginX, NewCapacity * TSize); - } - - this->BeginX = NewElts; - this->Capacity = NewCapacity; -} +static_assert(sizeof(SmallVector) == + sizeof(void *) * 2 + sizeof(void *), + "1 byte elements have word-sized type for size and capacity");