ADT: Shrink SmallVector by 8B on 64-bit platforms

[dexonsmith]

Summary

Shrink sizeof(SmallVector) by 8B on 64-bit platforms by representing size and capacity directly as unsigned and calculating end() from begin() + size().

This limits the maximum size/capacity of a vector to UINT32_MAX.

A few notes:

• I haven't profiled whether there is a compile-time hit, but I'm tempted to check the bots post-commit to check for regressions since this is no more branchy than before. Happy to be proactive if others think it's warranted.

• I noticed that SmallVectorImpl::resetToSmall, used by SmallVectorImpl::operator=(SmallVectorImpl &&), drops the small capacity to 0. This is a little sad so I left behind a FIXME.

• I lifted set_size() up to SmallVectorBase to use in place of setEnd().

[dexonsmith]

Updating the patch since I decided to just lift set_size() up to SmallVectorBase. My ASan-ified check-llvm and check-clang came back happy.

Does anyone feel this needs compile-time testing pre-commit?

[dexonsmith]

Ping!

[rnk]

lgtm

Sorry, I was on vacation. Let's do this unsigned thing.

[dexonsmith]

Committed in r337504.

[dexonsmith]

Reverted in r337511 due to a bot failure:

#8 0x000055581f2895d8 (/b/sanitizer-x86_64-linux-autoconf/build/tsan_debug_build/bin/clang-7+0x1eb45d8)
#9 0x000055581f294323 llvm::ConstantAggrKeyType<llvm::ConstantArray>::create(llvm::ArrayType*) const /b/sanitizer-x86_64-linux-autoconf/build/llvm/lib/IR/ConstantsContext.h:409:0
#10 0x000055581f294323 llvm::ConstantUniqueMap<llvm::ConstantArray>::create(llvm::ArrayType*, llvm::ConstantAggrKeyType<llvm::ConstantArray>, std::pair<unsigned int, std::pair<llvm::ArrayType*, llvm::ConstantAggrKeyType<llvm::ConstantArray> > >&) /b/sanitizer-x86_64-linux-autoconf/build/llvm/lib/IR/ConstantsContext.h:635:0
#11 0x000055581f294323 llvm::ConstantUniqueMap<llvm::ConstantArray>::getOrCreate(llvm::ArrayType*, llvm::ConstantAggrKeyType<llvm::ConstantArray>) /b/sanitizer-x86_64-linux-autoconf/build/llvm/lib/IR/ConstantsContext.h:654:0
#12 0x000055581f2944cb llvm::ConstantArray::get(llvm::ArrayType*, llvm::ArrayRef<llvm::Constant*>) /b/sanitizer-x86_64-linux-autoconf/build/llvm/lib/IR/Constants.cpp:964:0
#13 0x000055581fa27e19 llvm::SmallVectorBase::size() const /b/sanitizer-x86_64-linux-autoconf/build/llvm/include/llvm/ADT/SmallVector.h:53:0
#14 0x000055581fa27e19 llvm::SmallVectorImpl<llvm::Constant*>::resize(unsigned long) /b/sanitizer-x86_64-linux-autoconf/build/llvm/include/llvm/ADT/SmallVector.h:347:0
#15 0x000055581fa27e19 (anonymous namespace)::EmitArrayConstant(clang::CodeGen::CodeGenModule&, clang::ConstantArrayType const*, llvm::Type*, unsigned int, llvm::SmallVectorImpl<llvm::Constant*>&, llvm::Constant*) /b/sanitizer-x86_64-linux-autoconf/build/llvm/tools/clang/lib/CodeGen/CGExprConstant.cpp:669:0

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/26526

[dexonsmith]

In D48518#1169138, @dexonsmith wrote:

Reverted in r337511 due to a bot failure:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/26526

Hmm... that bot was green again in r337508, before I had a chance to revert. Maybe the blame-list was faulty.

[dexonsmith]

In D48518#1169148, @dexonsmith wrote:

In D48518#1169138, @dexonsmith wrote:

Reverted in r337511 due to a bot failure:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/26526

Hmm... that bot was green again in r337508, before I had a chance to revert. Maybe the blame-list was faulty.

Committed again (unchanged) in r337514.

[peter.smith]

This patch is causing the http://lab.llvm.org:8011/builders/clang-cmake-aarch64-lld to fail. Unfortunately (for me) the failures seems to be restricted to older versions of clang and are not reproducible on Arm or X86. The buildbot itself is using the default /usr/bin/clang for Ubuntu 16.04 LTS (clang version 3.8.0-2ubuntu4 (tags/RELEASE_380/final). The failures go away if I use the 3.9.1 release (No failures on 4.0.1, 6.0.0 or built from master). At this stage I think that this could be a code-gen bug in the AArch64 backend of clang 3.8.1 so I don't think it is worth reverting, but I'm mentioning it here just in case there is a subtle problem that is only being exposed by that version.

The failures on the bot are all a llvm::unreachable in checkDeducedTemplateArguments() clang/lib/Sema/SemaTemplateDeduction.cpp:367. The only way that I can see that the unreachable gets hit is if there is some kind of corruption of the ArgKind.

A stripped down bit of code that will cause a clang built with 3.8.1 on AArch64 to fail is:

template<typename T, typename U>
class test_attach30 { };

template<typename T>
class test_attach30<T, int> { };

$ clang++ -fsyntax-only test.cpp
Invalid TemplateArgument Kind!
UNREACHABLE executed at
clang/lib/Sema/SemaTemplateDeduction.cpp:367!

[dexonsmith]

Hi Peter,

Thanks for the heads up. I tend to agree with your intuition/conclusion (i.e., it seems like a bug in 3.8.1 and not worth reverting for). But, FYI, I'll be OOO for a couple of weeks. If for some reason your conclusion changes, please don't wait for my response before reverting. I already know it won't revert cleanly because I committed r337820 (https://reviews.llvm.org/D49163 https://reviews.llvm.org/D49163) on top, but it should be pretty easy to resolve the conflict (you should just have to fine-tune the static_asserts).

Good luck,
Duncan

[dexonsmith]

Looks like I forgot to close when recommitting in r337514.

llvm/include/llvm/ADT/SmallVector.h

 #include <type_traits>
 #include <utility>
 
 namespace llvm {
 
 /// 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);
-  }
-
-  /// capacity_in_bytes - This returns capacity()*sizeof(T).
-  size_t capacity_in_bytes() const {
-    return size_t((char*)CapacityX - (char*)BeginX);
-  }
+  size_t size() const { return Size; }
+  size_t capacity() const { return Capacity; }
 
-  LLVM_NODISCARD bool empty() const { return BeginX == EndX; }
+  LLVM_NODISCARD bool empty() const { return !Size; }
 };
 
 /// This is the part of SmallVectorTemplateBase which does not depend on whether
 /// the type T is a POD. The extra dummy template argument is used by ArrayRef
 /// 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;
   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
 
 protected:
   SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, 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(&FirstEl, 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);
   }
 
   /// Put this vector in a state of being small.
   void resetToSmall() {
-    BeginX = EndX = CapacityX = &FirstEl;
+    BeginX = &FirstEl;
+    Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
   }
 
-  void setEnd(T *P) { this->EndX = P; }
+  void setSize(size_t Size) { this->Size = Size; }
 
 public:
   using size_type = size_t;
   using difference_type = ptrdiff_t;
   using value_type = T;
   using iterator = T *;
   using const_iterator = const T *;
 
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
   using reverse_iterator = std::reverse_iterator<iterator>;
 
   using reference = T &;
   using const_reference = const T &;
   using pointer = T *;
   using const_pointer = const T *;
 
   // forward iterator creation methods.
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   iterator begin() { return (iterator)this->BeginX; }
   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()); }
   /// Return a pointer to the vector's buffer, even if empty().
   const_pointer data() const { return const_pointer(begin()); }
 
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   reference operator[](size_type idx) {
protected:
 
   /// Grow the allocated memory (without initializing new elements), doubling
   /// the size of the allocated memory. Guarantees space for at least one more
   /// element, or MinSize more elements if specified.
   void grow(size_t MinSize = 0);
 
 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->setSize(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->setSize(this->size() + 1);
   }
 
   void pop_back() {
-    this->setEnd(this->end()-1);
+    this->setSize(this->size() - 1);
     this->end()->~T();
   }
 };
 
 // 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;
+  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);
 
   // Destroy the original elements.
   destroy_range(this->begin(), this->end());
 
   // If this wasn't grown from the inline copy, deallocate the old space.
   if (!this->isSmall())
     free(this->begin());
 
-  this->setEnd(NewElts+CurSize);
   this->BeginX = NewElts;
-  this->CapacityX = this->begin()+NewCapacity;
+  this->Capacity = NewCapacity;
 }
 
 
 /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
 /// implementations that are designed to work with POD-like T's.
 template <typename T>
 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
 protected:
static void uninitialized_copy(
     // 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));
   }
 
   /// 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);
+    this->setSize(this->size() + 1);
   }
 
-  void pop_back() {
-    this->setEnd(this->end()-1);
-  }
+  void pop_back() { this->setSize(this->size() - 1); }
 };
 
 /// This class consists of common code factored out of the SmallVector class to
 /// reduce code duplication based on the SmallVector 'N' template parameter.
 template <typename T>
 class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
   using SuperClass = SmallVectorTemplateBase<T, isPodLike<T>::value>;
 
 public:
   using iterator = typename SuperClass::iterator;
   using const_iterator = typename SuperClass::const_iterator;
   using size_type = typename SuperClass::size_type;
 
 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;
 
   ~SmallVectorImpl() {
     // Subclass has already destructed this vector's elements.
     // If this wasn't grown from the inline copy, deallocate the old space.
     if (!this->isSmall())
       free(this->begin());
   }
 
   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->setSize(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->setSize(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->setSize(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->setSize(N);
     }
   }
 
   void reserve(size_type N) {
     if (this->capacity() < N)
       this->grow(N);
   }
 
   LLVM_NODISCARD T pop_back_val() {
     T Result = ::std::move(this->back());
     this->pop_back();
     return Result;
   }
 
   void swap(SmallVectorImpl &RHS);
 
   /// Add the specified range to the end of the SmallVector.
   template <typename in_iter,
             typename = typename std::enable_if<std::is_convertible<
                 typename std::iterator_traits<in_iter>::iterator_category,
                 std::input_iterator_tag>::value>::type>
   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->setSize(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->setSize(this->size() + NumInputs);
   }
 
   void append(std::initializer_list<T> IL) {
     append(IL.begin(), IL.end());
   }
 
   // FIXME: Consider assigning over existing elements, rather than clearing &
   // re-initializing them - for all assign(...) variants.
 
   void assign(size_type NumElts, const T &Elt) {
     clear();
     if (this->capacity() < NumElts)
       this->grow(NumElts);
-    this->setEnd(this->begin()+NumElts);
+    this->setSize(NumElts);
     std::uninitialized_fill(this->begin(), this->end(), Elt);
   }
 
   template <typename in_iter,
             typename = typename std::enable_if<std::is_convertible<
                 typename std::iterator_traits<in_iter>::iterator_category,
                 std::input_iterator_tag>::value>::type>
   void assign(in_iter in_start, in_iter in_end) {
iterator erase(const_iterator CS, const_iterator CE) {
     assert(S <= E && "Trying to erase invalid range.");
     assert(E <= this->end() && "Trying to erase past the end.");
 
     iterator N = S;
     // Shift all elts down.
     iterator I = std::move(E, this->end(), S);
     // Drop the last elts.
     this->destroy_range(I, this->end());
-    this->setEnd(I);
+    this->setSize(I - this->begin());
     return(N);
   }
 
   iterator insert(iterator I, T &&Elt) {
     if (I == this->end()) {  // Important special case for empty vector.
       this->push_back(::std::move(Elt));
       return this->end()-1;
     }
 
     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;
     }
 
     ::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->setSize(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);
     return I;
   }
 
   iterator insert(iterator I, const T &Elt) {
     if (I == this->end()) {  // Important special case for empty vector.
       this->push_back(Elt);
       return this->end()-1;
     }
 
     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;
     }
     ::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->setSize(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;
     return I;
   }
 
   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
if (size_t(this->end()-I) >= NumToInsert) {
       return I;
     }
 
     // Otherwise, we're inserting more elements than exist already, and we're
     // not inserting at the end.
 
     // Move over the elements that we're about to overwrite.
     T *OldEnd = this->end();
-    this->setEnd(this->end() + NumToInsert);
+    this->setSize(this->size() + NumToInsert);
     size_t NumOverwritten = OldEnd-I;
     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
 
     // Replace the overwritten part.
     std::fill_n(I, NumOverwritten, Elt);
 
     // Insert the non-overwritten middle part.
     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
if (size_t(this->end()-I) >= NumToInsert) {
       return I;
     }
 
     // Otherwise, we're inserting more elements than exist already, and we're
     // not inserting at the end.
 
     // Move over the elements that we're about to overwrite.
     T *OldEnd = this->end();
-    this->setEnd(this->end() + NumToInsert);
+    this->setSize(this->size() + NumToInsert);
     size_t NumOverwritten = OldEnd-I;
     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
 
     // Replace the overwritten part.
     for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
       *J = *From;
       ++J; ++From;
     }
 
     // Insert the non-overwritten middle part.
     this->uninitialized_copy(From, To, OldEnd);
     return I;
   }
 
   void insert(iterator I, std::initializer_list<T> IL) {
     insert(I, IL.begin(), IL.end());
   }
 
   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->setSize(this->size() + 1);
   }
 
   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
 
   SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
 
   bool operator==(const SmallVectorImpl &RHS) const {
     if (this->size() != RHS.size()) return false;
public:
   /// 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);
+    this->setSize(N);
   }
 };
 
 template <typename T>
 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
   if (this == &RHS) return;
 
   // 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())
     this->grow(RHS.size());
   if (this->size() > RHS.capacity())
     RHS.grow(this->size());
 
   // Swap the shared elements.
   size_t NumShared = this->size();
   if (NumShared > RHS.size()) NumShared = RHS.size();
   for (size_type i = 0; i != NumShared; ++i)
     std::swap((*this)[i], RHS[i]);
 
   // Copy over the extra elts.
   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.setSize(RHS.size() + EltDiff);
     this->destroy_range(this->begin()+NumShared, this->end());
-    this->setEnd(this->begin()+NumShared);
+    this->setSize(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->setSize(this->size() + EltDiff);
     this->destroy_range(RHS.begin()+NumShared, RHS.end());
-    RHS.setEnd(RHS.begin()+NumShared);
+    RHS.setSize(NumShared);
   }
 }
 
 template <typename T>
 SmallVectorImpl<T> &SmallVectorImpl<T>::
   operator=(const SmallVectorImpl<T> &RHS) {
   // Avoid self-assignment.
   if (this == &RHS) return *this;
if (RHSSize)
       NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
     else
       NewEnd = this->begin();
 
     // Destroy excess elements.
     this->destroy_range(NewEnd, this->end());
 
     // Trim.
-    this->setEnd(NewEnd);
+    this->setSize(RHSSize);
     return *this;
   }
 
   // If we have to grow to have enough elements, destroy the current elements.
   // This allows us to avoid copying them during the grow.
   // FIXME: don't do this if they're efficiently moveable.
   if (this->capacity() < RHSSize) {
     // Destroy current elements.
     this->destroy_range(this->begin(), this->end());
-    this->setEnd(this->begin());
+    this->setSize(0);
     CurSize = 0;
     this->grow(RHSSize);
   } else if (CurSize) {
     // Otherwise, use assignment for the already-constructed elements.
     std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
   }
 
   // Copy construct the new elements in place.
   this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
                            this->begin()+CurSize);
 
   // Set end.
-  this->setEnd(this->begin()+RHSSize);
+  this->setSize(RHSSize);
   return *this;
 }
 
 template <typename T>
 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
   // Avoid self-assignment.
   if (this == &RHS) return *this;
 
   // If the RHS isn't small, clear this vector and then steal its buffer.
   if (!RHS.isSmall()) {
     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;
   }
 
   // If we already have sufficient space, assign the common elements, then
   // destroy any excess.
   size_t RHSSize = RHS.size();
   size_t CurSize = this->size();
   if (CurSize >= RHSSize) {
     // Assign common elements.
     iterator NewEnd = this->begin();
     if (RHSSize)
       NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
 
     // Destroy excess elements and trim the bounds.
     this->destroy_range(NewEnd, this->end());
-    this->setEnd(NewEnd);
+    this->setSize(RHSSize);
 
     // Clear the RHS.
     RHS.clear();
 
     return *this;
   }
 
   // If we have to grow to have enough elements, destroy the current elements.
   // This allows us to avoid copying them during the grow.
   // FIXME: this may not actually make any sense if we can efficiently move
   // elements.
   if (this->capacity() < RHSSize) {
     // Destroy current elements.
     this->destroy_range(this->begin(), this->end());
-    this->setEnd(this->begin());
+    this->setSize(0);
     CurSize = 0;
     this->grow(RHSSize);
   } else if (CurSize) {
     // Otherwise, use assignment for the already-constructed elements.
     std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
   }
 
   // Move-construct the new elements in place.
   this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
                            this->begin()+CurSize);
 
   // Set end.
-  this->setEnd(this->begin()+RHSSize);
+  this->setSize(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

llvm/lib/Support/SmallVector.cpp

 // This file implements the SmallVector class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SmallVector.h"
 using namespace llvm;
 
 // Check that no bytes are wasted.
-static_assert(sizeof(SmallVector<void *, 1>) == sizeof(void *) * 4,
+static_assert(sizeof(SmallVector<void *, 1>) ==
+                  sizeof(unsigned) * 2 + sizeof(void *) * 2,
               "wasted space in SmallVector size 1; missing EBO?");
 
 /// 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 MinSizeInBytes,
+void SmallVectorBase::grow_pod(void *FirstEl, size_t MinCapacity,
                                size_t TSize) {
-  size_t CurSizeBytes = size_in_bytes();
-  size_t NewCapacityInBytes = 2 * capacity_in_bytes() + TSize; // Always grow.
-  if (NewCapacityInBytes < MinSizeInBytes)
-    NewCapacityInBytes = MinSizeInBytes;
+  // 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(NewCapacityInBytes);
+    NewElts = safe_malloc(NewCapacity * TSize);
 
     // Copy the elements over.  No need to run dtors on PODs.
-    memcpy(NewElts, this->BeginX, CurSizeBytes);
+    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, NewCapacityInBytes);
+    NewElts = safe_realloc(this->BeginX, NewCapacity * TSize);
   }
 
-  this->EndX = (char*)NewElts+CurSizeBytes;
   this->BeginX = NewElts;
-  this->CapacityX = (char*)this->BeginX + NewCapacityInBytes;
+  this->Capacity = NewCapacity;
 }