[SmallPtrSet] Remove SmallArray member (NFC) (#118099)

Currently SmallPtrSet stores CurArray and SmallArray, with the former
pointing to the latter in small representation. Instead, only use
CurAr

[SmallPtrSet] Remove SmallArray member (NFC) (#118099)

Currently SmallPtrSet stores CurArray and SmallArray, with the former
pointing to the latter in small representation. Instead, only use
CurArray and a separate IsSmall boolean.

Most of the implementation doesn't need the separate SmallArray member
-- we only need it for copy/move/swap operations, where we may switch
back from large to small representation. In those cases, we explicitly
pass down the pointer to SmallStorage.

This reduces the size of SmallPtrSet and improves compile-time.

show more ...

[SmallPtrSet] Optimize find/erase

Port #100517 for DenseMap.

Pull Request: https://github.com/llvm/llvm-project/pull/104740

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

[ADT] Move DenseMapInfo for ArrayRef/StringRef into respective headers (NFC)

This is a followup to D103422. The DenseMapInfo implementations for
ArrayRef and StringRef are moved into the ArrayRef.h

[ADT] Move DenseMapInfo for ArrayRef/StringRef into respective headers (NFC)

This is a followup to D103422. The DenseMapInfo implementations for
ArrayRef and StringRef are moved into the ArrayRef.h and StringRef.h
headers, which means that these two headers no longer need to be
included by DenseMapInfo.h.

This required adding a few additional includes, as many files were
relying on various things pulled in by ArrayRef.h.

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

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

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

Revert commit 333506

It looks like this commit is responsible for the fail:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-autoconf/builds/24382.

llvm-svn: 333518

Use uniform mechanism for OOM errors handling

This is a recommit of r333390, which was reverted in r333395, because it
caused cyclic dependency when building shared library `LLVMDemangle.so`.
In thi

Use uniform mechanism for OOM errors handling

This is a recommit of r333390, which was reverted in r333395, because it
caused cyclic dependency when building shared library `LLVMDemangle.so`.
In this commit `ItaniumDemangler.cpp` was not changed.

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: 333506

show more ...

Reverted commits 333390, 333391 and 333394

Build of shared library LLVMDemangle.so fails due to dependency problem.

llvm-svn: 333395

Use uniform mechanism for OOM errors handling

In r325551 many calls of malloc/calloc/realloc were replaces with calls of
their safe counterparts defined in the namespace llvm. There functions
genera

Use uniform mechanism for OOM errors handling

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: 333390

show more ...

[SmallPtrSet] Add iterator epoch tracking.

This will detect invalid iterators when ABI breaking checks are enabled.

llvm-svn: 315746

Support, IR, ADT: Check nullptr after allocation with malloc/realloc or calloc

As a follow up of the bad alloc handler patch, this patch introduces nullptr checks on pointers returned from the
mallo

Support, IR, ADT: Check nullptr after allocation with malloc/realloc or calloc

As a follow up of the bad alloc handler patch, this patch introduces nullptr checks on pointers returned from the
malloc/realloc/calloc functions. In addition some memory size assignments are moved behind the allocation
of the corresponding memory to fulfill exception safe memory management (RAII).

patch by Klaus Kretzschmar

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

llvm-svn: 308576

show more ...

[SmallPtrSet] Introduce a find primitive and rewrite count/erase in terms of it

This was originally motivated by a compile time problem I've since figured out how to solve differently, but the clean

[SmallPtrSet] Introduce a find primitive and rewrite count/erase in terms of it

This was originally motivated by a compile time problem I've since figured out how to solve differently, but the cleanup seemed useful. We had the same logic - which essentially implemented find - in several places. By commoning them out, I can implement find and allow erase to be inlined at the call sites if profitable.

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

llvm-svn: 290779

show more ...

Fix some Clang-tidy modernize-use-using and Include What You Use warnings; other minor fixes.

Differential revision: https://reviews.llvm.org/D23789

llvm-svn: 279535

SmallPtrSet: Avoid initializing Array in the small case.

This patch avoids the initial memset at the cost of making iterators
slightly more complex. This should be beneficial as most SmallPtrSets
ho

SmallPtrSet: Avoid initializing Array in the small case.

This patch avoids the initial memset at the cost of making iterators
slightly more complex. This should be beneficial as most SmallPtrSets
hold no or only a few elements, while iterating over them is less
common.

Differential Revision: http://reviews.llvm.org/D16672

llvm-svn: 260913

show more ...

SmallPtrSet: Make destructor available for inlining

llvm-svn: 259019

SmallPtrSet: Share some code between copy/move constructor/assignment operator

llvm-svn: 259018

SmallPtrSet: Remove trailing whitespace, fix indentation

llvm-svn: 259017

SmallPtrSet: Inline the part of insert_imp in the small case

Most of the time we only hit the small case, so it is beneficial to pull
it out of the insert_imp() implementation. This improves compile

SmallPtrSet: Inline the part of insert_imp in the small case

Most of the time we only hit the small case, so it is beneficial to pull
it out of the insert_imp() implementation. This improves compile time
at least for non-LTO builds.

Differential Revision: http://reviews.llvm.org/D16619

llvm-svn: 258908

show more ...

Sync the __builtin_expects for our 3 quadratically probed hash table implementations.

This assumes that
a) finding the bucket containing the value is LIKELY
b) finding an empty bucket is LIKELY

Sync the __builtin_expects for our 3 quadratically probed hash table implementations.

This assumes that
a) finding the bucket containing the value is LIKELY
b) finding an empty bucket is LIKELY
c) growing the table is UNLIKELY

I also switched the a) and b) cases for SmallPtrSet as we seem to use
the set mostly more for insertion than for checking existence.

In a simple benchmark consisting of 2^21 insertions of 2^20 unique
pointers into a DenseMap or SmallPtrSet a few percent speedup on average,
but nothing statistically significant.

llvm-svn: 230232

show more ...

Update SetVector to rely on the underlying set's insert to return a pair<iterator, bool>

This is to be consistent with StringSet and ultimately with the standard
library's associative container inse

Update SetVector to rely on the underlying set's insert to return a pair<iterator, bool>

This is to be consistent with StringSet and ultimately with the standard
library's associative container insert function.

This lead to updating SmallSet::insert to return pair<iterator, bool>,
and then to update SmallPtrSet::insert to return pair<iterator, bool>,
and then to update all the existing users of those functions...

llvm-svn: 222334

show more ...

Fix an off by 1 bug that prevented SmallPtrSet from using all of its 'small' capacity. Then fix the early return in the move constructor that prevented 'small' moves from clearing the NumElements in

Fix an off by 1 bug that prevented SmallPtrSet from using all of its 'small' capacity. Then fix the early return in the move constructor that prevented 'small' moves from clearing the NumElements in the moved from object. The directed test missed this because it was always testing large moves due to the off by 1 bug.

llvm-svn: 216044

show more ...

[C++11] Make use of 'nullptr' in the Support library.

llvm-svn: 205697

[C++11] Remove the R-value reference #if usage from the ADT and Support
libraries. It is now always 1 in LLVM builds.

llvm-svn: 202580

Rename the non-templated base class of SmallPtrSet to
'SmallPtrSetImplBase'. This more closely matches the organization of
SmallVector and should allow introducing a SmallPtrSetImpl which serves
the

Rename the non-templated base class of SmallPtrSet to
'SmallPtrSetImplBase'. This more closely matches the organization of
SmallVector and should allow introducing a SmallPtrSetImpl which serves
the same purpose as SmallVectorImpl: isolating the element type from the
particular small size chosen. This in turn allows a lot of
simplification of APIs by not coding them against a specific small size
which is rarely needed.

llvm-svn: 200687

show more ...