From 617330909f0c26a3f2ab8601a029b9bdca48aa61 Mon Sep 17 00:00:00 2001 From: Jean-Luc Duprat Date: Fri, 29 Mar 2013 05:45:22 +0000 Subject: Fix allocations of SmallVector and SmallPtrSet so they are more prone to being power-of-two sized. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178332 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Support/SmallPtrSet.cpp | 24 ++++++++---------------- 1 file changed, 8 insertions(+), 16 deletions(-) (limited to 'lib/Support/SmallPtrSet.cpp') diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 3b53e9f..f0fed77 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -29,13 +29,9 @@ void SmallPtrSetImpl::shrink_and_clear() { NumElements = NumTombstones = 0; // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); assert(CurArray && "Failed to allocate memory?"); memset(CurArray, -1, CurArraySize*sizeof(void*)); - - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[CurArraySize] = 0; } bool SmallPtrSetImpl::insert_imp(const void * Ptr) { @@ -139,15 +135,11 @@ void SmallPtrSetImpl::Grow(unsigned NewSize) { bool WasSmall = isSmall(); // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); + CurArray = (const void**)malloc(sizeof(void*) * NewSize); assert(CurArray && "Failed to allocate memory?"); CurArraySize = NewSize; memset(CurArray, -1, NewSize*sizeof(void*)); - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[NewSize] = 0; - // Copy over all the elements. if (WasSmall) { // Small sets store their elements in order. @@ -180,7 +172,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArray = SmallArray; // Otherwise, allocate new heap space (unless we were the same size) } else { - CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); assert(CurArray && "Failed to allocate memory?"); } @@ -188,7 +180,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArraySize = that.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); + memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); NumElements = that.NumElements; NumTombstones = that.NumTombstones; @@ -200,7 +192,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { if (isSmall() && RHS.isSmall()) assert(CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes"); - + // If we're becoming small, prepare to insert into our stack space if (RHS.isSmall()) { if (!isSmall()) @@ -209,9 +201,9 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { // Otherwise, allocate new heap space (unless we were the same size) } else if (CurArraySize != RHS.CurArraySize) { if (isSmall()) - CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); else - CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); + CurArray = (const void**)realloc(CurArray, sizeof(void*)*RHS.CurArraySize); assert(CurArray && "Failed to allocate memory?"); } @@ -219,7 +211,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { CurArraySize = RHS.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); + memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); NumElements = RHS.NumElements; NumTombstones = RHS.NumTombstones; -- cgit v1.1 From ef484a376cce3729b45ad86eab5724aa83a61823 Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Fri, 29 Mar 2013 07:11:21 +0000 Subject: Revert "Fix allocations of SmallVector and SmallPtrSet so they are more prone to" This reverts commit 617330909f0c26a3f2ab8601a029b9bdca48aa61. It broke the bots: /home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:150: PushPopTest /home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:118: Failure Value of: v[i].getValue() Actual: 0 Expected: value Which is: 2 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178334 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Support/SmallPtrSet.cpp | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-) (limited to 'lib/Support/SmallPtrSet.cpp') diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index f0fed77..3b53e9f 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -29,9 +29,13 @@ void SmallPtrSetImpl::shrink_and_clear() { NumElements = NumTombstones = 0; // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); + CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); assert(CurArray && "Failed to allocate memory?"); memset(CurArray, -1, CurArraySize*sizeof(void*)); + + // The end pointer, always valid, is set to a valid element to help the + // iterator. + CurArray[CurArraySize] = 0; } bool SmallPtrSetImpl::insert_imp(const void * Ptr) { @@ -135,11 +139,15 @@ void SmallPtrSetImpl::Grow(unsigned NewSize) { bool WasSmall = isSmall(); // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * NewSize); + CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); assert(CurArray && "Failed to allocate memory?"); CurArraySize = NewSize; memset(CurArray, -1, NewSize*sizeof(void*)); + // The end pointer, always valid, is set to a valid element to help the + // iterator. + CurArray[NewSize] = 0; + // Copy over all the elements. if (WasSmall) { // Small sets store their elements in order. @@ -172,7 +180,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArray = SmallArray; // Otherwise, allocate new heap space (unless we were the same size) } else { - CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); + CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); assert(CurArray && "Failed to allocate memory?"); } @@ -180,7 +188,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArraySize = that.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); + memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); NumElements = that.NumElements; NumTombstones = that.NumTombstones; @@ -192,7 +200,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { if (isSmall() && RHS.isSmall()) assert(CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes"); - + // If we're becoming small, prepare to insert into our stack space if (RHS.isSmall()) { if (!isSmall()) @@ -201,9 +209,9 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { // Otherwise, allocate new heap space (unless we were the same size) } else if (CurArraySize != RHS.CurArraySize) { if (isSmall()) - CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); + CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); else - CurArray = (const void**)realloc(CurArray, sizeof(void*)*RHS.CurArraySize); + CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); assert(CurArray && "Failed to allocate memory?"); } @@ -211,7 +219,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { CurArraySize = RHS.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); + memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); NumElements = RHS.NumElements; NumTombstones = RHS.NumTombstones; -- cgit v1.1 From e1e9366281a98cd06b61d5d7e136ce2b1a433ba6 Mon Sep 17 00:00:00 2001 From: Jean-Luc Duprat Date: Fri, 29 Mar 2013 22:07:12 +0000 Subject: SmallVector and SmallPtrSet allocations now power-of-two aligned. This time tested on both OSX and Linux. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178377 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Support/SmallPtrSet.cpp | 24 ++++++++---------------- 1 file changed, 8 insertions(+), 16 deletions(-) (limited to 'lib/Support/SmallPtrSet.cpp') diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 3b53e9f..f0fed77 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -29,13 +29,9 @@ void SmallPtrSetImpl::shrink_and_clear() { NumElements = NumTombstones = 0; // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); assert(CurArray && "Failed to allocate memory?"); memset(CurArray, -1, CurArraySize*sizeof(void*)); - - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[CurArraySize] = 0; } bool SmallPtrSetImpl::insert_imp(const void * Ptr) { @@ -139,15 +135,11 @@ void SmallPtrSetImpl::Grow(unsigned NewSize) { bool WasSmall = isSmall(); // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); + CurArray = (const void**)malloc(sizeof(void*) * NewSize); assert(CurArray && "Failed to allocate memory?"); CurArraySize = NewSize; memset(CurArray, -1, NewSize*sizeof(void*)); - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[NewSize] = 0; - // Copy over all the elements. if (WasSmall) { // Small sets store their elements in order. @@ -180,7 +172,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArray = SmallArray; // Otherwise, allocate new heap space (unless we were the same size) } else { - CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); assert(CurArray && "Failed to allocate memory?"); } @@ -188,7 +180,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArraySize = that.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); + memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); NumElements = that.NumElements; NumTombstones = that.NumTombstones; @@ -200,7 +192,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { if (isSmall() && RHS.isSmall()) assert(CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes"); - + // If we're becoming small, prepare to insert into our stack space if (RHS.isSmall()) { if (!isSmall()) @@ -209,9 +201,9 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { // Otherwise, allocate new heap space (unless we were the same size) } else if (CurArraySize != RHS.CurArraySize) { if (isSmall()) - CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); else - CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); + CurArray = (const void**)realloc(CurArray, sizeof(void*)*RHS.CurArraySize); assert(CurArray && "Failed to allocate memory?"); } @@ -219,7 +211,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { CurArraySize = RHS.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); + memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); NumElements = RHS.NumElements; NumTombstones = RHS.NumTombstones; -- cgit v1.1