[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 <mehdi.amini@apple.com>
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

[C++11] Replace some comparisons with 'nullptr' with simple boolean checks to reduce verbosity.

llvm-svn: 205829

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

llvm-svn: 205697

Add some __builtin_expect magic to StringMap.

Tombstones and full hash collisions are rare, mark the "empty"
and "no collision" paths as likely. The bug in simplifycfg
that prevented the hints from

Add some __builtin_expect magic to StringMap.

Tombstones and full hash collisions are rare, mark the "empty"
and "no collision" paths as likely. The bug in simplifycfg
that prevented the hints from being picked during selfhost
up was fixed recently :)

llvm-svn: 162874

show more ...

Fix PR13148, an inf-loop in StringMap.

StringMap suffered from the same bug as DenseMap: when you explicitly
construct it with a small number of buckets, you can arrange for the
tombstone-based grow

Fix PR13148, an inf-loop in StringMap.

StringMap suffered from the same bug as DenseMap: when you explicitly
construct it with a small number of buckets, you can arrange for the
tombstone-based growth path to be followed when the number of buckets
was less than '8'. In that case, even with a full map, it would compare
'0' as not less than '0', and refuse to grow the table, leading to
inf-loops trying to find an empty bucket on the next insertion. The fix
is very simple: use '<=' as the comparison. The same fix was applied to
DenseMap as well during its recent refactoring.

Thanks to Alex Bolz for the great report and test case. =]

llvm-svn: 158725

show more ...

Switch StringMap from an array of structures to a structure of arrays.

- -25% memory usage of the main table on x86_64 (was wasted in struct padding).
- no significant performance change.

llvm-svn:

Switch StringMap from an array of structures to a structure of arrays.

- -25% memory usage of the main table on x86_64 (was wasted in struct padding).
- no significant performance change.

llvm-svn: 147294

show more ...

Reset StringMap's NumTombstones on clears and rehashes.

StringMap was not properly updating NumTombstones after a clear or rehash.

This was not fatal until now because the table was growing faster

Reset StringMap's NumTombstones on clears and rehashes.

StringMap was not properly updating NumTombstones after a clear or rehash.

This was not fatal until now because the table was growing faster than
NumTombstones could, but with the previous change of preventing infinite
growth of the table the invariant (NumItems + NumTombstones <= NumBuckets)
stopped being observed, causing infinite loops in certain situations.

Patch by José Fonseca!

llvm-svn: 128567

show more ...

Prevent infinite growth of SmallMap instances.

Rehash but don't grow when full of tombstones.

Patch by José Fonseca!

llvm-svn: 128565

Change all self assignments X=X to (void)X, so that we can turn on a
new gcc warning that complains on self-assignments and
self-initializations.

llvm-svn: 122458

Pass StringRef by value.

llvm-svn: 86251

Move StringMap's string has function into StringExtras.h

llvm-svn: 84344

Convert StringMap to using StringRef for its APIs.
- Yay for '-'s and simplifications!

- I kept StringMap::GetOrCreateValue for compatibility purposes, this can
eventually go away. Likewise the

Convert StringMap to using StringRef for its APIs.
- Yay for '-'s and simplifications!

- I kept StringMap::GetOrCreateValue for compatibility purposes, this can
eventually go away. Likewise the StringMapEntry Create functions still follow
the old style.

- NIFC.

llvm-svn: 76888

show more ...

Remove attribution from file headers, per discussion on llvmdev.

llvm-svn: 45418

stringmap memory managed with malloc now

llvm-svn: 35666

use calloc instead of new/memset, it is more efficient

llvm-svn: 35644