[Hashing] Use a non-deterministic seed if LLVM_ENABLE_ABI_BREAKING_CHECKS

Hashing.h provides hash_value/hash_combine/hash_combine_range, which are
primarily used by `DenseMap<StringRef, X>`

Users s

[Hashing] Use a non-deterministic seed if LLVM_ENABLE_ABI_BREAKING_CHECKS

Hashing.h provides hash_value/hash_combine/hash_combine_range, which are
primarily used by `DenseMap<StringRef, X>`

Users shouldn't rely on specific hash values due to size_t differences
on 32-bit/64-bit platforms and potential algorithm changes.
`set_fixed_execution_hash_seed` is provided but it has never been used.

In LLVM_ENABLE_ABI_BREAKING_CHECKS builds, take the the address of a
static storage duration variable as the seed like
absl/hash/internal/hash.h `kSeed`. (See https://reviews.llvm.org/D93931
for workaround for older Clang. Mach-O x86-64 forces PIC, so absl's
`__apple_build_version__` check is unnecessary.)

LLVM_ENABLE_ABI_BREAKING_CHECKS defaults to `WITH_ASSERTS` and is
enabled in an assertion build.

In a non-assertion build, `get_execution_seed` returns the fixed value
regardless of `NDEBUG`. Removing a variable load yields noticeable
size/performance improvement.

A few users relying on the iteration order of `DenseMap<StringRef, X>`
have been fixed (e.g., f8f4235612b9 c025bd1fdbbd 89e8e63f47ff
86eb6bf6715c eb8d03656549 0ea6b8e476c2 58d7a6e0e636 8ea31db27211
592abf29f9f7 664497557ae7).
From my experience fixing [`StringMap`](https://discourse.llvm.org/t/reverse-iteration-bots/72224)
iteration order issues, the scale of issues is similar.

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

show more ...

Use llvm::endianness{,::little,::native} (NFC)

Now that llvm::support::endianness has been renamed to
llvm::endianness, we can use the shorter form. This patch replaces
llvm::support::endianness wi

Use llvm::endianness{,::little,::native} (NFC)

Now that llvm::support::endianness has been renamed to
llvm::endianness, we can use the shorter form. This patch replaces
llvm::support::endianness with llvm::endianness.

show more ...

[Support] Rename HashBuilderImpl to HashBuilder (NFC) (#68173)

Commit 9370271ec5debcb59e34629d5bd357c44213b2d3 made HashBuilder an
alias for HashBuilderImpl:

template <class HasherT, support::

[Support] Rename HashBuilderImpl to HashBuilder (NFC) (#68173)

Commit 9370271ec5debcb59e34629d5bd357c44213b2d3 made HashBuilder an
alias for HashBuilderImpl:

template <class HasherT, support::endianness Endianness>
using HashBuilder = HashBuilderImpl<HasherT, Endianness>;

This patch renames HashBuilderImpl to HashBuilder while removing the
alias above.

show more ...

[llvm] Add support for hashing std::optional

The credit for the hashing code, taken from D138934, goes to Ramkumar
Ramachandra. The test comes from OptionalTest.cpp and updated for
std::optional.

[llvm] Add support for hashing std::optional

The credit for the hashing code, taken from D138934, goes to Ramkumar
Ramachandra. The test comes from OptionalTest.cpp and updated for
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

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

show more ...

[Support] Automatically support `hash_value` when `HashBuilder` support is available.

Use the `HBuilder` interface to provide default implementations of `llvm::hash_value`.

Reviewed By: dexonsmith

[Support] Automatically support `hash_value` when `HashBuilder` support is available.

Use the `HBuilder` interface to provide default implementations of `llvm::hash_value`.

Reviewed By: dexonsmith

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

show more ...

Add hashing support for std::tuple

Summary:
All tuple values are passed directly to hash_combine. This is inspired by the implementation used for Swift:

https://github.com/llvm/llvm-project-staging

Add hashing support for std::tuple

Summary:
All tuple values are passed directly to hash_combine. This is inspired by the implementation used for Swift:

https://github.com/llvm/llvm-project-staging/commit/4a1b4edbe1d1969284c1528e2950ac81b25edc8f
https://github.com/llvm/llvm-project-staging/commit/845f3829b91522920a59c351b9011af01c5c7f87

Reviewers: gribozavr2

Reviewed By: gribozavr2

Subscribers: dexonsmith, llvm-commits

Tags: #llvm

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

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

Tests: fix tests encoding specific hash values for 32-bit systems.

I changed the seed slightly, but forgot to run the tests on a 32-bit system, so
tests which hard-code a specific hash value started

Tests: fix tests encoding specific hash values for 32-bit systems.

I changed the seed slightly, but forgot to run the tests on a 32-bit system, so
tests which hard-code a specific hash value started breaking.

llvm-svn: 341240

show more ...

Re-sort #include lines for unittests. This uses a slightly modified
clang-format (https://reviews.llvm.org/D33932) to keep primary headers
at the top and handle new utility headers like 'gmock' consi

Re-sort #include lines for unittests. This uses a slightly modified
clang-format (https://reviews.llvm.org/D33932) to keep primary headers
at the top and handle new utility headers like 'gmock' consistently with
other utility headers.

No other change was made. I did no manual edits, all of this is
clang-format.

This should allow other changes to have more clear and focused diffs,
and is especially motivated by moving some headers into more focused
libraries.

llvm-svn: 304786

show more ...

Remove no-op dtor so that use of the implicit copy ctor/assignment operator are not deprecated.

llvm-svn: 231112

ADT: Allow up to 18 arguments in hash_combine()

I just realized that the specialized metadata node patch I'm about to
commit won't compile on old compilers. Bump `hash_combine()`'s support
for non-

ADT: Allow up to 18 arguments in hash_combine()

I just realized that the specialized metadata node patch I'm about to
commit won't compile on old compilers. Bump `hash_combine()`'s support
for non-variadic templates to 18 (I tested this by reversing the logic
in the #ifdef).

llvm-svn: 228629

show more ...

[C++11] Use 'nullptr'.

llvm-svn: 210442

[C++11] Replace LLVM-style type traits with C++11 standard ones.

No functionality change.

llvm-svn: 203242

Fix typos found by http://github.com/lyda/misspell-check

llvm-svn: 157885

Add support to the hashing infrastructure for automatically hashing both
integral and enumeration types. This is accomplished with a bit of
template type trait magic. Thanks to Richard Smith for the

Add support to the hashing infrastructure for automatically hashing both
integral and enumeration types. This is accomplished with a bit of
template type trait magic. Thanks to Richard Smith for the core idea
here to detect viable types by detecting the set of types which can be
default constructed in a template parameter.

This is used (in conjunction with a system for detecting nullptr_t
should it exist) to provide an is_integral_or_enum type trait that
doesn't need a whitelist or direct compiler support.

With this, the hashing is extended to the more general facility. This
will be used in a subsequent commit to hashing more things, but I wanted
to make sure the type trait magic went through the build bots separately
in case other compilers don't like this formulation.

llvm-svn: 152217

show more ...

Teach the hashing facilities how to hash std::string objects.

llvm-svn: 152000

Split this test up into two smaller, and more focused tests.

llvm-svn: 151999

Move the NonPOD struct out of the anonymous namespace instead of adding llvm:: everywhere to fix the HashingTest on MSVC .

chandlerc proposed this better solution on IRC.

llvm-svn: 151974

Fixes the Hashing tests on MSVC by adding llvm:: prefix to hash_value function call.

llvm-svn: 151971

unittests/ADT/HashingTest.cpp: Temporarily disable a new test introduced in r151891, to appease msvc.

llvm-svn: 151970

Simplify the pair optimization. Rather than using complex type traits,
just ensure that the number of bytes in the pair is the sum of the bytes
in each side of the pair. As long as thats true, there

Simplify the pair optimization. Rather than using complex type traits,
just ensure that the number of bytes in the pair is the sum of the bytes
in each side of the pair. As long as thats true, there are no extra
bytes that might be padding.

Also add a few tests that previously would have slipped through the
checking. The more accurate checking mechanism catches these and ensures
they are handled conservatively correctly.

Thanks to Duncan for prodding me to do this right and more simply.

llvm-svn: 151891

show more ...

Add a golden data test that I missed somehow the first time around.

llvm-svn: 151886

Fix bad indenting that was left over from cut/paste of the golden values
for 32-bit builds in here.

llvm-svn: 151885

We really want to hash pairs of directly-hashable data as directly
hashable data. This matters when we have pair<T*, U*> as a key, which is
quite common in DenseMap, etc. To that end, we need to dete

We really want to hash pairs of directly-hashable data as directly
hashable data. This matters when we have pair<T*, U*> as a key, which is
quite common in DenseMap, etc. To that end, we need to detect when this
is safe. The requirements on a generic std::pair<T, U> are:

1) Both T and U must satisfy the existing is_hashable_data trait. Note
that this includes the requirement that T and U have no internal
padding bits or other bits not contributing directly to equality.
2) The alignment constraints of std::pair<T, U> do not require padding
between consecutive objects.
3) The alignment constraints of U and the size of T do not conspire to
require padding between the first and second elements.

Grow two somewhat magical traits to detect this by forming a pod
structure and inspecting offset artifacts on it. Hopefully this won't
cause any compilers to panic.

Added and adjusted tests now that pairs, even nested pairs, are treated
as just sequences of data.

Thanks to Jeffrey Yasskin for helping me sort through this and reviewing
the somewhat subtle traits.

llvm-svn: 151883

show more ...

Add support for hashing pairs by delegating to each sub-object. There is
an open question of whether we can do better than this by treating pairs
as boring data containers and directly hashing the tw

Add support for hashing pairs by delegating to each sub-object. There is
an open question of whether we can do better than this by treating pairs
as boring data containers and directly hashing the two subobjects. This
at least makes the API reasonable.

In order to make this change, I reorganized the header a bit. I lifted
the declarations of the hash_value functions up to the top of the header
with their doxygen comments as these are intended for users to interact
with. They shouldn't have to wade through implementation details. I then
defined them at the very end so that they could be defined in terms of
hash_combine or any other hashing infrastructure.

Added various pair-hashing unittests.

llvm-svn: 151882

show more ...