From: Richard Smith Date: Wed, 22 Aug 2012 00:11:07 +0000 (+0000) Subject: Reduce alignment of SmallVector to the required amount, rather than forcing 16... X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=bc363931085587bac42a40653962a3e5acd1ffce Reduce alignment of SmallVector to the required amount, rather than forcing 16-byte alignment. This fixes misaligned SmallVector accesses via ExtractValueInst's SmallVector data member. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162331 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index cf55aadef31..1e35d627921 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -59,12 +59,17 @@ namespace llvm { ArrayRef(const T *begin, const T *end) : Data(begin), Length(end - begin) {} - /// Construct an ArrayRef from a SmallVector. - /*implicit*/ ArrayRef(const SmallVectorTemplateCommon &Vec) - : Data(Vec.data()), Length(Vec.size()) {} + /// Construct an ArrayRef from a SmallVector. This is templated in order to + /// avoid instantiating SmallVectorTemplateCommon whenever we + /// copy-construct an ArrayRef. + template + /*implicit*/ ArrayRef(const SmallVectorTemplateCommon &Vec) + : Data(Vec.data()), Length(Vec.size()) { + } /// Construct an ArrayRef from a std::vector. - /*implicit*/ ArrayRef(const std::vector &Vec) + template + /*implicit*/ ArrayRef(const std::vector &Vec) : Data(Vec.empty() ? (T*)0 : &Vec[0]), Length(Vec.size()) {} /// Construct an ArrayRef from a C array. diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 9fbbbe4f3b5..769b7dc9f5e 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -14,6 +14,7 @@ #ifndef LLVM_ADT_SMALLVECTOR_H #define LLVM_ADT_SMALLVECTOR_H +#include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/type_traits.h" #include @@ -32,44 +33,20 @@ class SmallVectorBase { protected: void *BeginX, *EndX, *CapacityX; - // 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. An array of char would work great, but might not be - // aligned sufficiently. Instead we use some number of union instances for - // the space, which guarantee maximal alignment. - union U { - double D; - long double LD; - long long L; - void *P; - } FirstEl; - // Space after 'FirstEl' is clobbered, do not add any instance vars after it. - protected: - SmallVectorBase(size_t Size) - : BeginX(&FirstEl), EndX(&FirstEl), CapacityX((char*)&FirstEl+Size) {} - - /// isSmall - Return true if this is a smallvector which has not had dynamic - /// memory allocated for it. - bool isSmall() const { - return BeginX == static_cast(&FirstEl); - } - - /// resetToSmall - Put this vector in a state of being small. - void resetToSmall() { - BeginX = EndX = CapacityX = &FirstEl; - } + SmallVectorBase(void *FirstEl, size_t Size) + : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {} /// grow_pod - 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(size_t MinSizeInBytes, size_t TSize); + void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize); public: /// size_in_bytes - 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); @@ -78,11 +55,41 @@ public: bool empty() const { return BeginX == EndX; } }; +template struct SmallVectorStorage; -template +/// SmallVectorTemplateCommon - 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 class SmallVectorTemplateCommon : public SmallVectorBase { +private: + template 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. + typedef llvm::AlignedCharArrayUnion U; + U FirstEl; + // Space after 'FirstEl' is clobbered, do not add any instance vars after it. + protected: - SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(Size) {} + SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {} + + void grow_pod(size_t MinSizeInBytes, size_t TSize) { + SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize); + } + + /// isSmall - Return true if this is a smallvector which has not had dynamic + /// memory allocated for it. + bool isSmall() const { + return BeginX == static_cast(&FirstEl); + } + + /// resetToSmall - Put this vector in a state of being small. + void resetToSmall() { + BeginX = EndX = CapacityX = &FirstEl; + } void setEnd(T *P) { this->EndX = P; } public: @@ -844,6 +851,17 @@ SmallVectorImpl &SmallVectorImpl::operator=(SmallVectorImpl &&RHS) { } #endif +/// 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 +/// to avoid allocating unnecessary storage. +template +struct SmallVectorStorage { + typename SmallVectorTemplateCommon::U InlineElts[N - 1]; +}; +template struct SmallVectorStorage {}; +template struct SmallVectorStorage {}; + /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized /// for the case when the array is small. It contains some number of elements /// in-place, which allows it to avoid heap allocation when the actual number of @@ -854,41 +872,23 @@ SmallVectorImpl &SmallVectorImpl::operator=(SmallVectorImpl &&RHS) { /// template class SmallVector : public SmallVectorImpl { - /// InlineElts - These are 'N-1' elements that are stored inline in the body - /// of the vector. The extra '1' element is stored in SmallVectorImpl. - typedef typename SmallVectorImpl::U U; - enum { - // MinUs - The number of U's require to cover N T's. - MinUs = (static_cast(sizeof(T))*N + - static_cast(sizeof(U)) - 1) / - static_cast(sizeof(U)), - - // NumInlineEltsElts - The number of elements actually in this array. There - // is already one in the parent class, and we have to round up to avoid - // having a zero-element array. - NumInlineEltsElts = MinUs > 1 ? (MinUs - 1) : 1, - - // NumTsAvailable - The number of T's we actually have space for, which may - // be more than N due to rounding. - NumTsAvailable = (NumInlineEltsElts+1)*static_cast(sizeof(U))/ - static_cast(sizeof(T)) - }; - U InlineElts[NumInlineEltsElts]; + /// Storage - Inline space for elements which aren't stored in the base class. + SmallVectorStorage Storage; public: - SmallVector() : SmallVectorImpl(NumTsAvailable) { + SmallVector() : SmallVectorImpl(N) { } explicit SmallVector(unsigned Size, const T &Value = T()) - : SmallVectorImpl(NumTsAvailable) { + : SmallVectorImpl(N) { this->assign(Size, Value); } template - SmallVector(ItTy S, ItTy E) : SmallVectorImpl(NumTsAvailable) { + SmallVector(ItTy S, ItTy E) : SmallVectorImpl(N) { this->append(S, E); } - SmallVector(const SmallVector &RHS) : SmallVectorImpl(NumTsAvailable) { + SmallVector(const SmallVector &RHS) : SmallVectorImpl(N) { if (!RHS.empty()) SmallVectorImpl::operator=(RHS); } @@ -899,7 +899,7 @@ public: } #if LLVM_USE_RVALUE_REFERENCES - SmallVector(SmallVector &&RHS) : SmallVectorImpl(NumTsAvailable) { + SmallVector(SmallVector &&RHS) : SmallVectorImpl(N) { if (!RHS.empty()) SmallVectorImpl::operator=(::std::move(RHS)); } @@ -912,48 +912,6 @@ public: }; -/// Specialize SmallVector at N=0. This specialization guarantees -/// that it can be instantiated at an incomplete T if none of its -/// members are required. -template -class SmallVector : public SmallVectorImpl { -public: - SmallVector() : SmallVectorImpl(0) { - } - - explicit SmallVector(unsigned Size, const T &Value = T()) - : SmallVectorImpl(0) { - this->assign(Size, Value); - } - - template - SmallVector(ItTy S, ItTy E) : SmallVectorImpl(0) { - this->append(S, E); - } - - SmallVector(const SmallVector &RHS) : SmallVectorImpl(0) { - if (!RHS.empty()) - SmallVectorImpl::operator=(RHS); - } - - const SmallVector &operator=(const SmallVector &RHS) { - SmallVectorImpl::operator=(RHS); - return *this; - } - -#if LLVM_USE_RVALUE_REFERENCES - SmallVector(SmallVector &&RHS) : SmallVectorImpl(0) { - if (!RHS.empty()) - SmallVectorImpl::operator=(::std::move(RHS)); - } - - const SmallVector &operator=(SmallVector &&RHS) { - SmallVectorImpl::operator=(::std::move(RHS)); - return *this; - } -#endif -}; - template static inline size_t capacity_in_bytes(const SmallVector &X) { return X.capacity_in_bytes(); diff --git a/lib/Support/SmallVector.cpp b/lib/Support/SmallVector.cpp index a89f1495763..f9c0e78270c 100644 --- a/lib/Support/SmallVector.cpp +++ b/lib/Support/SmallVector.cpp @@ -16,14 +16,15 @@ using namespace llvm; /// 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(size_t MinSizeInBytes, size_t TSize) { +void SmallVectorBase::grow_pod(void *FirstEl, size_t MinSizeInBytes, + size_t TSize) { size_t CurSizeBytes = size_in_bytes(); size_t NewCapacityInBytes = 2 * capacity_in_bytes() + TSize; // Always grow. if (NewCapacityInBytes < MinSizeInBytes) NewCapacityInBytes = MinSizeInBytes; void *NewElts; - if (this->isSmall()) { + if (BeginX == FirstEl) { NewElts = malloc(NewCapacityInBytes); // Copy the elements over. No need to run dtors on PODs. @@ -37,4 +38,3 @@ void SmallVectorBase::grow_pod(size_t MinSizeInBytes, size_t TSize) { this->BeginX = NewElts; this->CapacityX = (char*)this->BeginX + NewCapacityInBytes; } -