[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 ...

ADT: Shrink SmallVector size 0 to 16B on 64-bit platforms

SmallVectorTemplateCommon wants to know the address of the first element
so it can detect whether it's in "small size" mode.

The old implem

ADT: Shrink SmallVector size 0 to 16B on 64-bit platforms

SmallVectorTemplateCommon wants to know the address of the first element
so it can detect whether it's in "small size" mode.

The old implementation split the small array, creating the storage for
the first element in SmallVectorTemplateCommon, and pulling the rest
into SmallVectorStorage where we know the size of the array. This
bloats SmallVector size 0 by the larger of sizeof(void*) and sizeof(T),
and we're not even using the storage.

The new implementation leaves the full small storage to
SmallVectorStorage. To calculate the offset of the first element in
SmallVectorTemplateCommon, we just need to know how far to jump, which
we can calculate out-of-band. One subtlety is that we need
SmallVectorStorage to be properly aligned even when the size is 0, to be
sure that (for large alignments) we actually have the padding and it's
well defined to do the pointer math.

llvm-svn: 337820

show more ...

Reapply "ADT: Shrink size of SmallVector by 8B on 64-bit platforms"

I'm optimistically reverting commit r337511, effectively reapplying
r337504 *without* changes.

The failing bots that had `SmallVe

Reapply "ADT: Shrink size of SmallVector by 8B on 64-bit platforms"

I'm optimistically reverting commit r337511, effectively reapplying
r337504 *without* changes.

The failing bots that had `SmallVector` in the backtrace recovered after
the unrelated commit r337508. The backtraces looked bogus anyway, with
`SmallVector::size()` calling (e.g.) `ConstantArray::get()`.

Here's the original commit message:

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

Represent size and capacity directly as unsigned and calculate
`end()` using `begin() + size()`.

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

https://reviews.llvm.org/D48518

llvm-svn: 337514

show more ...

Revert "ADT: Shrink size of SmallVector by 8B on 64-bit platforms"

This reverts commit r337504 while I investigate a TSan bot failure that
seems related:

http://lab.llvm.org:8011/builders/sanitizer

Revert "ADT: Shrink size of SmallVector by 8B on 64-bit platforms"

This reverts commit r337504 while I investigate a TSan bot failure that
seems related:

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

#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

llvm-svn: 337511

show more ...

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

Representing size and capacity directly as unsigned and calculate
`end()` using `begin() + size()`.

This limits the maximum size/capacity o

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

Representing size and capacity directly as unsigned and calculate
`end()` using `begin() + size()`.

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

https://reviews.llvm.org/D48518

llvm-svn: 337504

show more ...

ADT: Use EBO to shrink SmallVector size 1

SmallVectorStorage is empty when its size is 1; use inheritance so that
the empty base class optimization kicks in.

llvm-svn: 335421

Use uniform mechanism for OOM errors handling

This is a recommit of r333506, which was reverted in r333518.
The original commit message is below.

In r325551 many calls of malloc/calloc/realloc were

Use uniform mechanism for OOM errors handling

This is a recommit of r333506, which was reverted in r333518.
The original commit message is below.

In r325551 many calls of malloc/calloc/realloc were replaces with calls of
their safe counterparts defined in the namespace llvm. There functions
generate crash if memory cannot be allocated, such behavior facilitates
handling of out of memory errors on Windows.

If the result of *alloc function were checked for success, the function was
not replaced with the safe variant. In these cases the calling function made
the error handling, like:

T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T)));
if (NewElts == nullptr)
report_bad_alloc_error("Allocation of SmallVector element failed.");

Actually knowledge about the function where OOM occurred is useless. Moreover
having a single entry point for OOM handling is convenient for investigation
of memory problems. This change removes custom OOM errors handling and
replaces them with calls to functions `llvm::safe_*alloc`.

Declarations of `safe_*alloc` are moved to a separate include file, to avoid
cyclic dependency in SmallVector.h

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

llvm-svn: 334344

show more ...