[NFC][llvm][StringMap]Extract createTable and getHashTable functions and add the inline attribute to the getMinBucketToReserveForEntries function.

1. Extract createTable and getHashTable functions.

[NFC][llvm][StringMap]Extract createTable and getHashTable functions and add the inline attribute to the getMinBucketToReserveForEntries function.

1. Extract createTable and getHashTable functions.
2. Add the inline attribute to the getMinBucketToReserveForEntries function.
3. Remove unnecessary local variable HTSize.

Statements in the following order appear in llvm::StringMapImpl::init and llvm::StringMapImpl::RehashTable, so I extracted this code into a function. getHashTable is for the same reason, it appears in llvm::StringMapImpl::FindKey, llvm::StringMapImpl::LookupBucketFor and llvm::StringMapImpl::RehashTable.

```
auto **Table = static_cast<StringMapEntryBase **>(safe_calloc(
NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned)));

// Allocate one extra bucket, set it to look filled so the iterators stop at
// end.
Table[NewNumBuckets] = (StringMapEntryBase *)2;
```

```
unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
```

Reviewed By: skan, sepavloff

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

show more ...

[llvm][ADT] Remove duplicate code in llvm::StringMapImpl::RehashTable

Remove duplicate code in llvm::StringMapImpl::RehashTable, near StringMap.cpp:229

```
if (!NewTableArray[NewBucket]) {
NewTab

[llvm][ADT] Remove duplicate code in llvm::StringMapImpl::RehashTable

Remove duplicate code in llvm::StringMapImpl::RehashTable, near StringMap.cpp:229

```
if (!NewTableArray[NewBucket]) {
NewTableArray[FullHash & (NewSize - 1)] = Bucket;
NewHashArray[FullHash & (NewSize - 1)] = FullHash;
if (I == BucketNo)
NewBucketNo = NewBucket;
continue;
}
```

Reviewed By: MaskRay, dexonsmith

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

show more ...

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

Revert "Use the default seed value for djb hash for StringMap"

This reverts commit d84440ec919019ac446241db72cfd905c6ac9dfa.

It breaks (at least) lldb and lld validation

https://lab.llvm.org/build

Revert "Use the default seed value for djb hash for StringMap"

This reverts commit d84440ec919019ac446241db72cfd905c6ac9dfa.

It breaks (at least) lldb and lld validation

https://lab.llvm.org/buildbot/#/builders/68/builds/7837
https://lab.llvm.org/buildbot/#/builders/36/builds/5495

show more ...

Use the default seed value for djb hash for StringMap

See original comment in 560ce2c70fb1fe8e4b9b5e39c54e494a50373ba8
Baiscally the default seed value results in less collision, but changes the
ite

Use the default seed value for djb hash for StringMap

See original comment in 560ce2c70fb1fe8e4b9b5e39c54e494a50373ba8
Baiscally the default seed value results in less collision, but changes the
iteration order, which matters for a few test cases.

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

show more ...

Refactor StringMap.h, splitting StringMapEntry out to its own header.

Summary:
StringMapEntry.h can have lower dependencies, than StringMap.h, which
is useful for public headers that want to expose

Refactor StringMap.h, splitting StringMapEntry out to its own header.

Summary:
StringMapEntry.h can have lower dependencies, than StringMap.h, which
is useful for public headers that want to expose inline methods on
StringMapEntry<> but don't need to expose all of StringMap.h. One
example of this is mlir's Identifier.h, another example is the existing
LLVM StringPool.h.

StringPool also could use a cleanup, I'll deal with that in a follow-on
patch.

Reviewers: rriddle

Subscribers: hiraditya, dexonsmith, llvm-commits

Tags: #llvm

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

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

Re-land: "[Support] Replace HashString with djbHash."

This patch removes the HashString function from StringExtraces and
replaces its uses with calls to djbHash from DJB.h.

This change is *almost*

Re-land: "[Support] Replace HashString with djbHash."

This patch removes the HashString function from StringExtraces and
replaces its uses with calls to djbHash from DJB.h.

This change is *almost* NFC. While the algorithm is identical, the
djbHash implementation in StringExtras used 0 as its default seed while
the implementation in DJB uses 5381. The latter has been shown to result
in less collisions and improved avalanching and is used by the DWARF
accelerator tables.

Because some test were implicitly relying on the hash order, I've
reverted to using zero as a seed for the following two files:

lld/include/lld/Core/SymbolTable.h
llvm/lib/Support/StringMap.cpp

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

llvm-svn: 326091

show more ...

Revert "[Support] Replace HashString with djbHash."

It looks like some of our tests depend on the ordering of hashed values.
I'm reverting my changes while I try to reproduce and fix this locally.

Revert "[Support] Replace HashString with djbHash."

It looks like some of our tests depend on the ordering of hashed values.
I'm reverting my changes while I try to reproduce and fix this locally.

Failing builds:

lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/18388
lab.llvm.org:8011/builders/clang-cmake-x86_64-sde-avx512-linux/builds/6743
lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/15607

llvm-svn: 326082

show more ...

[Support] Replace HashString with djbHash.

This removes the HashString function from StringExtraces and replaces
its uses with calls to djbHash from DJB.h

This is *almost* NFC. While the algorithm

[Support] Replace HashString with djbHash.

This removes the HashString function from StringExtraces and replaces
its uses with calls to djbHash from DJB.h

This is *almost* NFC. While the algorithm is identical, the djbHash
implementation in StringExtras used 0 as its seed while the
implementation in DJB uses 5381. The latter has been shown to result in
less collisions and improved avalanching.

https://reviews.llvm.org/D43615
(cherry picked from commit 77f7f965bc9499a9ae768a296ca5a1f7347d1d2c)

llvm-svn: 326081

show more ...

Report fatal error in the case of out of memory

This is the second part of recommit of r325224. The previous part was
committed in r325426, which deals with C++ memory allocation. Solution
for C mem

Report fatal error in the case of out of memory

This is the second part of recommit of r325224. The previous part was
committed in r325426, which deals with C++ memory allocation. Solution
for C memory allocation involved functions `llvm::malloc` and similar.
This was a fragile solution because it caused ambiguity errors in some
cases. In this commit the new functions have names like `llvm::safe_malloc`.

The relevant part of original comment is below, updated for new function
names.

Analysis of fails in the case of out of memory errors can be tricky on
Windows. Such error emerges at the point where memory allocation function
fails, but manifests itself when null pointer is used. These two points
may be distant from each other. Besides, next runs may not exhibit
allocation error.

In some cases memory is allocated by a call to some of C allocation
functions, malloc, calloc and realloc. They are used for interoperability
with C code, when allocated object has variable size and when it is
necessary to avoid call of constructors. In many calls the result is not
checked for null pointer. To simplify checks, new functions are defined
in the namespace 'llvm': `safe_malloc`, `safe_calloc` and `safe_realloc`.
They behave as corresponding standard functions but produce fatal error if
allocation fails. This change replaces the standard functions like 'malloc'
in the cases when the result of the allocation function is not checked
for null pointer.

Finally, there are plain C code, that uses malloc and similar functions. If
the result is not checked, assert statement is added.

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

llvm-svn: 325551

show more ...

Revert r325224 "Report fatal error in the case of out of memory"

It caused fails on some buildbots.

llvm-svn: 325227

Report fatal error in the case of out of memory

Analysis of fails in the case of out of memory errors can be tricky on
Windows. Such error emerges at the point where memory allocation function
fails

Report fatal error in the case of out of memory

Analysis of fails in the case of out of memory errors can be tricky on
Windows. Such error emerges at the point where memory allocation function
fails, but manifests itself when null pointer is used. These two points
may be distant from each other. Besides, next runs may not exhibit
allocation error.

Usual programming practice does not require checking result of 'operator
new' because it throws 'std::bad_alloc' in the case of allocation error.
However, LLVM is usually built with exceptions turned off, so 'new' can
return null pointer. This change installs custom new handler, which causes
fatal error in the case of out of memory. The handler is installed
automatically prior to call to 'main' during construction of a static
object defined in 'lib/Support/ErrorHandling.cpp'. If the application does
not use this file, the handler may be installed manually by a call to
'llvm::install_out_of_memory_new_handler', declared in
'include/llvm/Support/ErrorHandling.h".

There are calls to C allocation functions, malloc, calloc and realloc.
They are used for interoperability with C code, when allocated object has
variable size and when it is necessary to avoid call of constructors. In
many calls the result is not checked against null pointer. To simplify
checks, new functions are defined in the namespace 'llvm' with the
same names as these C function. These functions produce fatal error if
allocation fails. User should use 'llvm::malloc' instead of 'std::malloc'
in order to use the safe variant. This change replaces 'std::malloc'
in the cases when the result of allocation function is not checked against
null pointer.

Finally, there are plain C code, that uses malloc and similar functions. If
the result is not checked, assert statements are added.

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

llvm-svn: 325224

show more ...

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

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

Adjust initial size in StringMap constructor to guarantee no grow()

Summary:
StringMap ctor accepts an initialize size, but expect it to be
rounded to the next power of 2. The ctor can handle that d

Adjust initial size in StringMap constructor to guarantee no grow()

Summary:
StringMap ctor accepts an initialize size, but expect it to be
rounded to the next power of 2. The ctor can handle that directly
instead of expecting clients to round it. Also, since the map will
resize itself when 75% full, take this into account an initialize
a larger initial size to avoid any growth.

Reviewers: dblaikie

Subscribers: llvm-commits

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

From: Mehdi Amini <[email protected]>
llvm-svn: 264385

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

Recommit 211309 (StringMap::insert), reverted in 211328 due to issues with private, but non-deleted, move members.

Certain versions of GCC (~4.7) couldn't handle the SFINAE on access
control, but wi

Recommit 211309 (StringMap::insert), reverted in 211328 due to issues with private, but non-deleted, move members.

Certain versions of GCC (~4.7) couldn't handle the SFINAE on access
control, but with "= delete" (hidden behind a macro for portability)
this issue is worked around/addressed.

Patch by Agustín Bergé

llvm-svn: 211525

show more ...

Revert "Add StringMap::insert(pair) consistent with the standard associative container concept."

This reverts commit r211309.

It looks like it broke some bots:

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

Revert "Add StringMap::insert(pair) consistent with the standard associative container concept."

This reverts commit r211309.

It looks like it broke some bots:

http://lab.llvm.org:8011/builders/clang-x86_64-ubuntu-gdb-75/builds/15563/steps/compile/logs/stdio

llvm-svn: 211328

show more ...

Add StringMap::insert(pair) consistent with the standard associative container concept.

Patch by Agustín Bergé.

llvm-svn: 211309