Update clang to r339409.
Change-Id: I800772d2d838223be1f6b40d490c4591b937fca2
diff --git a/linux-x64/clang/include/llvm/ADT/SmallVector.h b/linux-x64/clang/include/llvm/ADT/SmallVector.h
index 3d17e70..e4ddd12 100644
--- a/linux-x64/clang/include/llvm/ADT/SmallVector.h
+++ b/linux-x64/clang/include/llvm/ADT/SmallVector.h
@@ -18,6 +18,7 @@
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/MemAlloc.h"
#include "llvm/Support/type_traits.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
@@ -37,28 +38,42 @@
/// This is all the non-templated stuff common to all SmallVectors.
class SmallVectorBase {
protected:
- void *BeginX, *EndX, *CapacityX;
+ void *BeginX;
+ unsigned Size = 0, Capacity;
-protected:
- SmallVectorBase(void *FirstEl, size_t Size)
- : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
+ SmallVectorBase() = delete;
+ SmallVectorBase(void *FirstEl, size_t Capacity)
+ : BeginX(FirstEl), Capacity(Capacity) {}
/// 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 MinSizeInBytes, size_t TSize);
+ void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize);
public:
- /// This returns size()*sizeof(T).
- size_t size_in_bytes() const {
- return size_t((char*)EndX - (char*)BeginX);
- }
+ size_t size() const { return Size; }
+ size_t capacity() const { return Capacity; }
- /// capacity_in_bytes - This returns capacity()*sizeof(T).
- size_t capacity_in_bytes() const {
- return size_t((char*)CapacityX - (char*)BeginX);
- }
+ LLVM_NODISCARD bool empty() const { return !Size; }
- LLVM_NODISCARD bool empty() const { return BeginX == EndX; }
+ /// Set the array size to \p N, which the current array must have enough
+ /// capacity for.
+ ///
+ /// This does not construct or destroy any elements in the vector.
+ ///
+ /// Clients can use this in conjunction with capacity() to write past the end
+ /// of the buffer when they know that more elements are available, and only
+ /// update the size later. This avoids the cost of value initializing elements
+ /// which will only be overwritten.
+ void set_size(size_t Size) {
+ assert(Size <= capacity());
+ this->Size = Size;
+ }
+};
+
+/// Figure out the offset of the first element.
+template <class T, typename = void> struct SmallVectorAlignmentAndSize {
+ AlignedCharArrayUnion<SmallVectorBase> Base;
+ AlignedCharArrayUnion<T> FirstEl;
};
/// This is the part of SmallVectorTemplateBase which does not depend on whether
@@ -66,36 +81,34 @@
/// to avoid unnecessarily requiring T to be complete.
template <typename T, typename = void>
class SmallVectorTemplateCommon : public SmallVectorBase {
-private:
- template <typename, unsigned> friend struct SmallVectorStorage;
-
- // Allocate raw space for N elements of type T. If T has a ctor or dtor, we
- // don't want it to be automatically run, so we need to represent the space as
- // something else. Use an array of char of sufficient alignment.
- using U = AlignedCharArrayUnion<T>;
- U FirstEl;
+ /// 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.
+ void *getFirstEl() const {
+ return const_cast<void *>(reinterpret_cast<const void *>(
+ reinterpret_cast<const char *>(this) +
+ offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
+ }
// Space after 'FirstEl' is clobbered, do not add any instance vars after it.
protected:
- SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
+ SmallVectorTemplateCommon(size_t Size)
+ : SmallVectorBase(getFirstEl(), Size) {}
- void grow_pod(size_t MinSizeInBytes, size_t TSize) {
- SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
+ void grow_pod(size_t MinCapacity, size_t TSize) {
+ SmallVectorBase::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 == static_cast<const void*>(&FirstEl);
- }
+ bool isSmall() const { return BeginX == getFirstEl(); }
/// Put this vector in a state of being small.
void resetToSmall() {
- BeginX = EndX = CapacityX = &FirstEl;
+ BeginX = getFirstEl();
+ Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
}
- void setEnd(T *P) { this->EndX = P; }
-
public:
using size_type = size_t;
using difference_type = ptrdiff_t;
@@ -117,27 +130,20 @@
LLVM_ATTRIBUTE_ALWAYS_INLINE
const_iterator begin() const { return (const_iterator)this->BeginX; }
LLVM_ATTRIBUTE_ALWAYS_INLINE
- iterator end() { return (iterator)this->EndX; }
+ iterator end() { return begin() + size(); }
LLVM_ATTRIBUTE_ALWAYS_INLINE
- const_iterator end() const { return (const_iterator)this->EndX; }
+ const_iterator end() const { return begin() + size(); }
-protected:
- iterator capacity_ptr() { return (iterator)this->CapacityX; }
- const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
-
-public:
// reverse iterator creation methods.
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
- LLVM_ATTRIBUTE_ALWAYS_INLINE
- size_type size() const { return end()-begin(); }
+ size_type size_in_bytes() const { return size() * sizeof(T); }
size_type max_size() const { return size_type(-1) / sizeof(T); }
- /// Return the total number of elements in the currently allocated buffer.
- size_t capacity() const { return capacity_ptr() - begin(); }
+ size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
/// Return a pointer to the vector's buffer, even if empty().
pointer data() { return pointer(begin()); }
@@ -210,21 +216,21 @@
public:
void push_back(const T &Elt) {
- if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+ if (LLVM_UNLIKELY(this->size() >= this->capacity()))
this->grow();
::new ((void*) this->end()) T(Elt);
- this->setEnd(this->end()+1);
+ this->set_size(this->size() + 1);
}
void push_back(T &&Elt) {
- if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+ if (LLVM_UNLIKELY(this->size() >= this->capacity()))
this->grow();
::new ((void*) this->end()) T(::std::move(Elt));
- this->setEnd(this->end()+1);
+ this->set_size(this->size() + 1);
}
void pop_back() {
- this->setEnd(this->end()-1);
+ this->set_size(this->size() - 1);
this->end()->~T();
}
};
@@ -232,15 +238,13 @@
// Define this out-of-line to dissuade the C++ compiler from inlining it.
template <typename T, bool isPodLike>
void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
- size_t CurCapacity = this->capacity();
- size_t CurSize = this->size();
+ if (MinSize > UINT32_MAX)
+ report_bad_alloc_error("SmallVector capacity overflow during allocation");
+
// Always grow, even from zero.
- size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2));
- if (NewCapacity < MinSize)
- NewCapacity = MinSize;
- T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T)));
- if (NewElts == nullptr)
- report_bad_alloc_error("Allocation of SmallVector element failed.");
+ size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
+ NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX));
+ T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
// Move the elements over.
this->uninitialized_move(this->begin(), this->end(), NewElts);
@@ -252,9 +256,8 @@
if (!this->isSmall())
free(this->begin());
- this->setEnd(NewElts+CurSize);
this->BeginX = NewElts;
- this->CapacityX = this->begin()+NewCapacity;
+ this->Capacity = NewCapacity;
}
@@ -296,26 +299,22 @@
// use memcpy here. Note that I and E are iterators and thus might be
// invalid for memcpy if they are equal.
if (I != E)
- memcpy(Dest, I, (E - I) * sizeof(T));
+ memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
}
/// Double the size of the allocated memory, guaranteeing space for at
/// least one more element or MinSize if specified.
- void grow(size_t MinSize = 0) {
- this->grow_pod(MinSize*sizeof(T), sizeof(T));
- }
+ void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
public:
void push_back(const T &Elt) {
- if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+ if (LLVM_UNLIKELY(this->size() >= this->capacity()))
this->grow();
- memcpy(this->end(), &Elt, sizeof(T));
- this->setEnd(this->end()+1);
+ memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
+ this->set_size(this->size() + 1);
}
- void pop_back() {
- this->setEnd(this->end()-1);
- }
+ void pop_back() { this->set_size(this->size() - 1); }
};
/// This class consists of common code factored out of the SmallVector class to
@@ -332,8 +331,7 @@
protected:
// Default ctor - Initialize to empty.
explicit SmallVectorImpl(unsigned N)
- : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
- }
+ : SmallVectorTemplateBase<T, isPodLike<T>::value>(N) {}
public:
SmallVectorImpl(const SmallVectorImpl &) = delete;
@@ -347,31 +345,31 @@
void clear() {
this->destroy_range(this->begin(), this->end());
- this->EndX = this->BeginX;
+ this->Size = 0;
}
void resize(size_type N) {
if (N < this->size()) {
this->destroy_range(this->begin()+N, this->end());
- this->setEnd(this->begin()+N);
+ this->set_size(N);
} else if (N > this->size()) {
if (this->capacity() < N)
this->grow(N);
for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
new (&*I) T();
- this->setEnd(this->begin()+N);
+ this->set_size(N);
}
}
void resize(size_type N, const T &NV) {
if (N < this->size()) {
this->destroy_range(this->begin()+N, this->end());
- this->setEnd(this->begin()+N);
+ this->set_size(N);
} else if (N > this->size()) {
if (this->capacity() < N)
this->grow(N);
std::uninitialized_fill(this->end(), this->begin()+N, NV);
- this->setEnd(this->begin()+N);
+ this->set_size(N);
}
}
@@ -396,23 +394,23 @@
void append(in_iter in_start, in_iter in_end) {
size_type NumInputs = std::distance(in_start, in_end);
// Grow allocated space if needed.
- if (NumInputs > size_type(this->capacity_ptr()-this->end()))
+ if (NumInputs > this->capacity() - this->size())
this->grow(this->size()+NumInputs);
// Copy the new elements over.
this->uninitialized_copy(in_start, in_end, this->end());
- this->setEnd(this->end() + NumInputs);
+ this->set_size(this->size() + NumInputs);
}
/// Add the specified range to the end of the SmallVector.
void append(size_type NumInputs, const T &Elt) {
// Grow allocated space if needed.
- if (NumInputs > size_type(this->capacity_ptr()-this->end()))
+ if (NumInputs > this->capacity() - this->size())
this->grow(this->size()+NumInputs);
// Copy the new elements over.
std::uninitialized_fill_n(this->end(), NumInputs, Elt);
- this->setEnd(this->end() + NumInputs);
+ this->set_size(this->size() + NumInputs);
}
void append(std::initializer_list<T> IL) {
@@ -426,7 +424,7 @@
clear();
if (this->capacity() < NumElts)
this->grow(NumElts);
- this->setEnd(this->begin()+NumElts);
+ this->set_size(NumElts);
std::uninitialized_fill(this->begin(), this->end(), Elt);
}
@@ -473,7 +471,7 @@
iterator I = std::move(E, this->end(), S);
// Drop the last elts.
this->destroy_range(I, this->end());
- this->setEnd(I);
+ this->set_size(I - this->begin());
return(N);
}
@@ -486,7 +484,7 @@
assert(I >= this->begin() && "Insertion iterator is out of bounds.");
assert(I <= this->end() && "Inserting past the end of the vector.");
- if (this->EndX >= this->CapacityX) {
+ if (this->size() >= this->capacity()) {
size_t EltNo = I-this->begin();
this->grow();
I = this->begin()+EltNo;
@@ -495,12 +493,12 @@
::new ((void*) this->end()) T(::std::move(this->back()));
// Push everything else over.
std::move_backward(I, this->end()-1, this->end());
- this->setEnd(this->end()+1);
+ this->set_size(this->size() + 1);
// If we just moved the element we're inserting, be sure to update
// the reference.
T *EltPtr = &Elt;
- if (I <= EltPtr && EltPtr < this->EndX)
+ if (I <= EltPtr && EltPtr < this->end())
++EltPtr;
*I = ::std::move(*EltPtr);
@@ -516,7 +514,7 @@
assert(I >= this->begin() && "Insertion iterator is out of bounds.");
assert(I <= this->end() && "Inserting past the end of the vector.");
- if (this->EndX >= this->CapacityX) {
+ if (this->size() >= this->capacity()) {
size_t EltNo = I-this->begin();
this->grow();
I = this->begin()+EltNo;
@@ -524,12 +522,12 @@
::new ((void*) this->end()) T(std::move(this->back()));
// Push everything else over.
std::move_backward(I, this->end()-1, this->end());
- this->setEnd(this->end()+1);
+ this->set_size(this->size() + 1);
// If we just moved the element we're inserting, be sure to update
// the reference.
const T *EltPtr = &Elt;
- if (I <= EltPtr && EltPtr < this->EndX)
+ if (I <= EltPtr && EltPtr < this->end())
++EltPtr;
*I = *EltPtr;
@@ -575,7 +573,7 @@
// Move over the elements that we're about to overwrite.
T *OldEnd = this->end();
- this->setEnd(this->end() + NumToInsert);
+ this->set_size(this->size() + NumToInsert);
size_t NumOverwritten = OldEnd-I;
this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
@@ -632,7 +630,7 @@
// Move over the elements that we're about to overwrite.
T *OldEnd = this->end();
- this->setEnd(this->end() + NumToInsert);
+ this->set_size(this->size() + NumToInsert);
size_t NumOverwritten = OldEnd-I;
this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
@@ -652,10 +650,10 @@
}
template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
- if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+ if (LLVM_UNLIKELY(this->size() >= this->capacity()))
this->grow();
::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
- this->setEnd(this->end() + 1);
+ this->set_size(this->size() + 1);
}
SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
@@ -674,20 +672,6 @@
return std::lexicographical_compare(this->begin(), this->end(),
RHS.begin(), RHS.end());
}
-
- /// Set the array size to \p N, which the current array must have enough
- /// capacity for.
- ///
- /// This does not construct or destroy any elements in the vector.
- ///
- /// Clients can use this in conjunction with capacity() to write past the end
- /// of the buffer when they know that more elements are available, and only
- /// update the size later. This avoids the cost of value initializing elements
- /// which will only be overwritten.
- void set_size(size_type N) {
- assert(N <= this->capacity());
- this->setEnd(this->begin() + N);
- }
};
template <typename T>
@@ -697,8 +681,8 @@
// We can only avoid copying elements if neither vector is small.
if (!this->isSmall() && !RHS.isSmall()) {
std::swap(this->BeginX, RHS.BeginX);
- std::swap(this->EndX, RHS.EndX);
- std::swap(this->CapacityX, RHS.CapacityX);
+ std::swap(this->Size, RHS.Size);
+ std::swap(this->Capacity, RHS.Capacity);
return;
}
if (RHS.size() > this->capacity())
@@ -716,15 +700,15 @@
if (this->size() > RHS.size()) {
size_t EltDiff = this->size() - RHS.size();
this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
- RHS.setEnd(RHS.end()+EltDiff);
+ RHS.set_size(RHS.size() + EltDiff);
this->destroy_range(this->begin()+NumShared, this->end());
- this->setEnd(this->begin()+NumShared);
+ this->set_size(NumShared);
} else if (RHS.size() > this->size()) {
size_t EltDiff = RHS.size() - this->size();
this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
- this->setEnd(this->end() + EltDiff);
+ this->set_size(this->size() + EltDiff);
this->destroy_range(RHS.begin()+NumShared, RHS.end());
- RHS.setEnd(RHS.begin()+NumShared);
+ RHS.set_size(NumShared);
}
}
@@ -750,7 +734,7 @@
this->destroy_range(NewEnd, this->end());
// Trim.
- this->setEnd(NewEnd);
+ this->set_size(RHSSize);
return *this;
}
@@ -760,7 +744,7 @@
if (this->capacity() < RHSSize) {
// Destroy current elements.
this->destroy_range(this->begin(), this->end());
- this->setEnd(this->begin());
+ this->set_size(0);
CurSize = 0;
this->grow(RHSSize);
} else if (CurSize) {
@@ -773,7 +757,7 @@
this->begin()+CurSize);
// Set end.
- this->setEnd(this->begin()+RHSSize);
+ this->set_size(RHSSize);
return *this;
}
@@ -787,8 +771,8 @@
this->destroy_range(this->begin(), this->end());
if (!this->isSmall()) free(this->begin());
this->BeginX = RHS.BeginX;
- this->EndX = RHS.EndX;
- this->CapacityX = RHS.CapacityX;
+ this->Size = RHS.Size;
+ this->Capacity = RHS.Capacity;
RHS.resetToSmall();
return *this;
}
@@ -805,7 +789,7 @@
// Destroy excess elements and trim the bounds.
this->destroy_range(NewEnd, this->end());
- this->setEnd(NewEnd);
+ this->set_size(RHSSize);
// Clear the RHS.
RHS.clear();
@@ -820,7 +804,7 @@
if (this->capacity() < RHSSize) {
// Destroy current elements.
this->destroy_range(this->begin(), this->end());
- this->setEnd(this->begin());
+ this->set_size(0);
CurSize = 0;
this->grow(RHSSize);
} else if (CurSize) {
@@ -833,22 +817,23 @@
this->begin()+CurSize);
// Set end.
- this->setEnd(this->begin()+RHSSize);
+ this->set_size(RHSSize);
RHS.clear();
return *this;
}
-/// Storage for the SmallVector elements which aren't contained in
-/// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1'
-/// element is in the base class. This is specialized for the N=1 and N=0 cases
+/// Storage for the SmallVector elements. This is specialized for the N=0 case
/// to avoid allocating unnecessary storage.
template <typename T, unsigned N>
struct SmallVectorStorage {
- typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
+ AlignedCharArrayUnion<T> InlineElts[N];
};
-template <typename T> struct SmallVectorStorage<T, 1> {};
-template <typename T> struct SmallVectorStorage<T, 0> {};
+
+/// We need the storage to be properly aligned even for small-size of 0 so that
+/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
+/// well-defined.
+template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
/// This is a 'vector' (really, a variable-sized array), optimized
/// for the case when the array is small. It contains some number of elements
@@ -859,10 +844,7 @@
/// Note that this does not attempt to be exception safe.
///
template <typename T, unsigned N>
-class SmallVector : public SmallVectorImpl<T> {
- /// Inline space for elements which aren't stored in the base class.
- SmallVectorStorage<T, N> Storage;
-
+class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
public:
SmallVector() : SmallVectorImpl<T>(N) {}