[ADT] Declare replaceAllocation in SmallVector.cpp (NFC) (#107469)

This patch changes replaceAllocation to a static function while moving
the declaration to SmallVector.cpp. Note that:

- replac

[ADT] Declare replaceAllocation in SmallVector.cpp (NFC) (#107469)

This patch changes replaceAllocation to a static function while moving
the declaration to SmallVector.cpp. Note that:

- replaceAllocation is used only within SmallVector.cpp.
- replaceAllocation doesn't access any class members.

show more ...

Revert "[ADT] Always use 32-bit size type for SmallVector with 16-bit elements" (#96826)

Reverts llvm/llvm-project#95536, this is breaking macOS GreenDragon
buildbots on arm64 and x86_64
https://g

Revert "[ADT] Always use 32-bit size type for SmallVector with 16-bit elements" (#96826)

Reverts llvm/llvm-project#95536, this is breaking macOS GreenDragon
buildbots on arm64 and x86_64
https://green.lab.llvm.org/job/llvm.org/view/LLDB/job/as-lldb-cmake/6522/console,
also breaks the Darwin LLVM buildbots:
https://lab.llvm.org/buildbot/#/builders/23/builds/398

show more ...

[ADT] Always use 32-bit size type for SmallVector with 16-bit elements (#95536)

`SmallVector` has a special case to allow vector of char to exceed 4 GB
in
size on 64-bit hosts. Apply this special

[ADT] Always use 32-bit size type for SmallVector with 16-bit elements (#95536)

`SmallVector` has a special case to allow vector of char to exceed 4 GB
in
size on 64-bit hosts. Apply this special case only for 8-bit element
types, instead of all element types < 32 bits.

This makes `SmallVector<MCPhysReg>` more compact because `MCPhysReg` is
`uint16_t`.

---------

Co-authored-by: Nikita Popov <github@npopov.com>

show more ...

[LLVM][ADT] Explicitly convert size_t values to SmallVector's size type (#77939)

Multiple places rely on implicit conversion when assigning 'size_t'
values to the member fields (size or capacity) o

[LLVM][ADT] Explicitly convert size_t values to SmallVector's size type (#77939)

Multiple places rely on implicit conversion when assigning 'size_t'
values to the member fields (size or capacity) of SmallVector.

Depending on the platform / compiler configuration, this may result in
narrowing conversion warnings (especially given that the size type of
SmallVector's member fields is determined based on type T - in
SmallVector<T>). To avoid the problem altogether, make the conversions
explicit.

Co-authored-by: Orest Chura <orest.chura@intel.com>

show more ...

[SmallVector] Reallocate if assigned memory is right after the current vector, created with capacity 0

Potential solution for
https://github.com/llvm/llvm-project/issues/57324.

Differential Revisio

[SmallVector] Reallocate if assigned memory is right after the current vector, created with capacity 0

Potential solution for
https://github.com/llvm/llvm-project/issues/57324.

Differential Revision: https://reviews.llvm.org/D132512

show more ...

[Support] Use std::clamp (NFC)

We can safely use std::clamp here because the call to
report_size_overflow a few lines above guarantees MinSize <= MaxSize.

[llvm] Cleanup header dependencies in ADT and Support

The cleanup was manual, but assisted by "include-what-you-use". It consists in

1. Removing unused forward declaration. No impact expected.
2. R

[llvm] Cleanup header dependencies in ADT and Support

The cleanup was manual, but assisted by "include-what-you-use". It consists in

1. Removing unused forward declaration. No impact expected.
2. Removing unused headers in .cpp files. No impact expected.
3. Removing unused headers in .h files. This removes implicit dependencies and
is generally considered a good thing, but this may break downstream builds.
I've updated llvm, clang, lld, lldb and mlir deps, and included a list of the
modification in the second part of the commit.
4. Replacing header inclusion by forward declaration. This has the same impact
as 3.

Notable changes:

- llvm/Support/TargetParser.h no longer includes llvm/Support/AArch64TargetParser.h nor llvm/Support/ARMTargetParser.h
- llvm/Support/TypeSize.h no longer includes llvm/Support/WithColor.h
- llvm/Support/YAMLTraits.h no longer includes llvm/Support/Regex.h
- llvm/ADT/SmallVector.h no longer includes llvm/Support/MemAlloc.h nor llvm/Support/ErrorHandling.h

You may need to add some of these headers in your compilation units, if needs be.

As an hint to the impact of the cleanup, running

clang++ -E -Iinclude -I../llvm/include ../llvm/lib/Support/*.cpp -std=c++14 -fno-rtti -fno-exceptions | wc -l

before: 8000919 lines
after: 7917500 lines

Reduced dependencies also helps incremental rebuilds and is more ccache
friendly, something not shown by the above metric :-)

Discourse thread on the topic: https://llvm.discourse.group/t/include-what-you-use-include-cleanup/5831

show more ...

[Support] Update SmallVector report_fatal_error calls to use Twine and add missing implicit header dependency.

[AIX] Suppress -Waix-compat warning with SmallVector class

When building LLVM with Open XL and -Werror is specified, the -Waix-compat warning becomes an error. This patch updates the SmallVector cla

[AIX] Suppress -Waix-compat warning with SmallVector class

When building LLVM with Open XL and -Werror is specified, the -Waix-compat warning becomes an error. This patch updates the SmallVector class to suppress the -Waix-compat warning/error on AIX.

Reviewed By: daltenty

Differential Revision: https://reviews.llvm.org/D108577

show more ...

[llvm] Replace LLVM_ATTRIBUTE_NORETURN with C++11 [[noreturn]]

[[noreturn]] can be used since Oct 2016 when the minimum compiler requirement was bumped to GCC 4.8/MSVC 2015.

Note: the definition of

[llvm] Replace LLVM_ATTRIBUTE_NORETURN with C++11 [[noreturn]]

[[noreturn]] can be used since Oct 2016 when the minimum compiler requirement was bumped to GCC 4.8/MSVC 2015.

Note: the definition of LLVM_ATTRIBUTE_NORETURN is kept for now.

show more ...

ADT: Fix reference invalidation in SmallVector::emplace_back and assign(N,V)

This fixes the final (I think?) reference invalidation in `SmallVector`
that we need to fix to align with `std::vector`.

ADT: Fix reference invalidation in SmallVector::emplace_back and assign(N,V)

This fixes the final (I think?) reference invalidation in `SmallVector`
that we need to fix to align with `std::vector`. (There is still some
left in the range insert / append / assign, but the standard calls that
UB for `std::vector` so I think we don't care?)

For POD-like types, reimplement `emplace_back()` in terms of
`push_back()`, taking a copy even for large `T` rather than lose the
realloc optimization in `grow_pod()`.

For other types, split the grow operation in three and construct the new
element in the middle.

- `mallocForGrow()` calculates the new capacity and returns the result
of `safe_malloc()`. We only need a single definition per
`SmallVectorBase` so this is defined in SmallVector.cpp to avoid code
size bloat. Moving this part of non-POD grow to the source file also
allows the logic to be easily shared with `grow_pod`, and
`report_size_overflow()` and `report_at_maximum_capacity()` can move
there too.
- `moveElementsForGrow()` moves elements from the old to the new
allocation.
- `takeAllocationForGrow()` frees the old allocation and saves the
new allocation and capacity .

`SmallVector:assign(size_type, const T&)` also uses the split-grow
operations for non-POD, but it also has a semantic change when not
growing. Previously, assign would start with `clear()`, and so the old
elements were destructed and all elements of the new vector were
copy-constructed (potentially invalidating references). The new
implementation skips destruction and uses copy-assignment for the prefix
of the new vector that fits. The new semantics match what libc++ does
for `std::vector::assign()`.

Note that the following is another possible implementation:
```
void assign(size_type NumElts, ValueParamT Elt) {
std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
this->resize(NumElts, Elt);
}
```
The downside of this simpler implementation is that if the vector has to
grow there will be `size()` redundant copy operations.

(I had planned on splitting this patch up into three for committing
(after getting performance numbers / initial review), but I've realized
that if this does for some reason need to be reverted we'll probably
want to revert the whole package...)

Differential Revision: https://reviews.llvm.org/D94739

show more ...

s/instantate/instantiate/ throughout. NFCI.

The static_assert in "libcxx/include/memory" was the main offender here,
but then I figured I might as well `git grep -i instantat` and fix all
the instan

s/instantate/instantiate/ throughout. NFCI.

The static_assert in "libcxx/include/memory" was the main offender here,
but then I figured I might as well `git grep -i instantat` and fix all
the instances I found. One was in user-facing HTML documentation;
the rest were in comments or tests.

show more ...

[SmallVector] Move error handling out of line

This reduces duplication and avoids emitting ice cold code into every
instance of grow().

Improve error handling for SmallVector programming errors

This patch changes errors in `SmallVector::grow` that are independent of
memory capacity to be reported using report_fatal_error or
std::len

Improve error handling for SmallVector programming errors

This patch changes errors in `SmallVector::grow` that are independent of
memory capacity to be reported using report_fatal_error or
std::length_error instead of report_bad_alloc_error, which falsely signals
an OOM.

It also cleans up a few related things:
- makes report_bad_alloc_error to print the failure reason passed
to it.
- fixes the documentation to indicate that report_bad_alloc_error
calls `abort()` not "an assertion"
- uses a consistent name for the size/capacity argument to `grow`
and `grow_pod`

Reviewed By: mehdi_amini, MaskRay

Differential Revision: https://reviews.llvm.org/D86892

show more ...

[NFC] Add include cstdint for SIZE_MAX.

Revert "Revert "[ADT] Fix SmallVector unused template instantiation on 32-bit systems.""

This reverts commit ac2635e457d53b80b0a6f73a5041767197643aae.

Revert was too hasty, build was already broken.

Revert "[ADT] Fix SmallVector unused template instantiation on 32-bit systems."

This reverts commit 25e2e92297e21bb4e0acab1b6bb5b2fdd5dc49ad.

Buildbot failure.

[ADT] Fix SmallVector unused template instantiation on 32-bit systems.

Summary:
This was introduced in dda3c19a3618dce94 aka D77621.

The unused template instantiation causes a warning on 32 bit sys

[ADT] Fix SmallVector unused template instantiation on 32-bit systems.

Summary:
This was introduced in dda3c19a3618dce94 aka D77621.

The unused template instantiation causes a warning on 32 bit systems
about truncating a uint64_t to 32-bit size_t.

Reviewed By: dblaikie, smeenai

Differential Revision: https://reviews.llvm.org/D79214

show more ...

ADT: SmallVector size/capacity use word-size integers when elements are small

SmallVector currently uses 32bit integers for size and capacity to reduce
sizeof(SmallVector). This limits the number of

ADT: SmallVector size/capacity use word-size integers when elements are small

SmallVector currently uses 32bit integers for size and capacity to reduce
sizeof(SmallVector). This limits the number of elements to UINT32_MAX.

For a SmallVector<char>, this limits the SmallVector size to only 4GB.
Buffering bitcode output uses SmallVector<char>, but needs >4GB output.

This changes SmallVector size and capacity to conditionally use word-size
integers if the element type is small (<4 bytes). For larger elements types,
the vector size can reach ~16GB with 32bit size.

Making this conditional on the element type provides both the smaller
sizeof(SmallVector) for larger types which are unlikely to grow so large,
and supports larger capacities for smaller element types.

This recommit fixes the same template being instantiated twice on platforms
where uintptr_t is the same as uint32_t.

show more ...

Revert "ADT: SmallVector size/capacity use word-size integers when elements are small"

This reverts commit b5f0eae1dc3c09c020cdf9d07238dec9acdacf5f.

clang-cmake-armv7-quick/llvm/llvm/lib/Support/Sm

Revert "ADT: SmallVector size/capacity use word-size integers when elements are small"

This reverts commit b5f0eae1dc3c09c020cdf9d07238dec9acdacf5f.

clang-cmake-armv7-quick/llvm/llvm/lib/Support/SmallVector.cpp:81:22:
error: duplicate explicit instantiation of 'SmallVectorBase<unsigned int>'

show more ...

ADT: SmallVector size/capacity use word-size integers when elements are small

SmallVector currently uses 32bit integers for size and capacity to reduce
sizeof(SmallVector). This limits the number of

ADT: SmallVector size/capacity use word-size integers when elements are small

SmallVector currently uses 32bit integers for size and capacity to reduce
sizeof(SmallVector). This limits the number of elements to UINT32_MAX.

For a SmallVector<char>, this limits the SmallVector size to only 4GB.
Buffering bitcode output uses SmallVector<char>, but needs >4GB output.

This changes SmallVector size and capacity to conditionally use word-size
integers if the element type is small (<4 bytes). For larger elements types,
the vector size can reach ~16GB with 32bit size.

Making this conditional on the element type provides both the smaller
sizeof(SmallVector) for larger types which are unlikely to grow so large,
and supports larger capacities for smaller element types.

show more ...

Make SmallVector assert if it cannot grow.

Context:

/// Double the size of the allocated memory, guaranteeing space for at
/// least one more element or MinSize if specified.
void grow(size_t

Make SmallVector assert if it cannot grow.

Context:

/// 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)); }

void push_back(const T &Elt) {
if (LLVM_UNLIKELY(this->size() >= this->capacity()))
this->grow();
memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
this->set_size(this->size() + 1);
}

When grow is called in push_back() without a MinSize specified, this is
relying on the guarantee of space for at least one more element.

There is an edge case bug where the SmallVector is already at its maximum size
and push_back() calls grow() with default MinSize of zero. Grow is unable to
provide space for one more element, but push_back() assumes the additional
element it will be available. This can result in silent memory corruption, as
this->end() will be an invalid pointer and the program may continue executing.

Another alternative to fix would be to remove the default argument from
grow(), which would mean several changing grow() to grow(this->size()+1)
in several places.

No test case added because it would require allocating ~4GB.

Reviewers: echristo

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D77601

show more ...

Revert "ADT: SmallVector size/capacity use word-size integers when elements are small"

This reverts commit b8d08e961df1d229872c785ebdbc8367432e9752.

This change causes a 1% compile-time and 1% memo

Revert "ADT: SmallVector size/capacity use word-size integers when elements are small"

This reverts commit b8d08e961df1d229872c785ebdbc8367432e9752.

This change causes a 1% compile-time and 1% memory usage regression:

http://llvm-compile-time-tracker.com/compare.php?from=73b7dd1fb3c17a4ac4b1f1e603f26fa708009649&to=b8d08e961df1d229872c785ebdbc8367432e9752&stat=instructions
http://llvm-compile-time-tracker.com/compare.php?from=73b7dd1fb3c17a4ac4b1f1e603f26fa708009649&to=b8d08e961df1d229872c785ebdbc8367432e9752&stat=max-rss

show more ...

ADT: SmallVector size/capacity use word-size integers when elements are small

SmallVector currently uses 32bit integers for size and capacity to reduce
sizeof(SmallVector). This limits the number of

ADT: SmallVector size/capacity use word-size integers when elements are small

SmallVector currently uses 32bit integers for size and capacity to reduce
sizeof(SmallVector). This limits the number of elements to UINT32_MAX.

For a SmallVector<char>, this limits the SmallVector size to only 4GB.
Buffering bitcode output uses SmallVector<char>, but needs >4GB output.

This changes SmallVector size and capacity to conditionally use word-size
integers if the element type is small (<4 bytes). For larger elements types,
the vector size can reach ~16GB with 32bit size.

Making this conditional on the element type provides both the smaller
sizeof(SmallVector) for larger types which are unlikely to grow so large,
and supports larger capacities for smaller element types.

This change also includes a fix for the bug where a SmallVector with 32bit
size has reached UINT32_MAX elements, and cannot provide guaranteed growth.

Context:

// 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)); }

void push_back(const T &Elt) {
if (LLVM_UNLIKELY(this->size() >= this->capacity()))
this->grow();
memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
this->set_size(this->size() + 1);
}

When grow is called in push_back() without a MinSize specified, this is
relying on the guarantee of space for at least one more element.

There is an edge case bug where the SmallVector is already at its maximum size
and push_back() calls grow() with default MinSize of zero. Grow is unable to
provide space for one more element, but push_back() assumes the additional
element it will be available. This can result in silent memory corruption, as
this->end() will be an invalid pointer and the program may continue executing.

An alternative to this fix would be to remove the default argument from
grow(), which would mean several changing grow() to grow(this->size()+1)
in several places.

No test case added because it would require allocating a large ammount.

Differential Revision: https://reviews.llvm.org/D77621

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...