44#ifndef LLVM_ADT_HASHING_H
45#define LLVM_ADT_HASHING_H
47#include "llvm/Config/abi-breaking.h"
61template <
typename T,
typename Enable>
struct DenseMapInfo;
87 operator size_t()
const {
return value; }
90 return lhs.value == rhs.value;
93 return lhs.value != rhs.value;
108std::enable_if_t<is_integral_or_enum<T>::value, hash_code>
hash_value(
T value);
113template <
typename T> hash_code
hash_value(
const T *ptr);
116template <
typename T,
typename U>
117hash_code
hash_value(
const std::pair<T, U> &arg);
120template <
typename... Ts>
121hash_code
hash_value(
const std::tuple<Ts...> &arg);
125hash_code
hash_value(
const std::basic_string<T> &arg);
128template <
typename T> hash_code
hash_value(
const std::optional<T> &arg);
138 memcpy(&result, p,
sizeof(result));
146 memcpy(&result, p,
sizeof(result));
163 return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
167 return val ^ (val >> 47);
172 const uint64_t kMul = 0x9ddfea08eb382d69ULL;
183 uint8_t b = s[len >> 1];
184 uint8_t c = s[len - 1];
207 llvm::rotr<uint64_t>(c ^ seed, 30) + d,
208 a + llvm::rotr<uint64_t>(b ^
k3, 20) - c + len + seed);
214 uint64_t b = llvm::rotr<uint64_t>(a + z, 52);
215 uint64_t c = llvm::rotr<uint64_t>(a, 37);
217 c += llvm::rotr<uint64_t>(a, 7);
220 uint64_t vs = b + llvm::rotr<uint64_t>(a, 31) + c;
223 b = llvm::rotr<uint64_t>(a + z, 52);
224 c = llvm::rotr<uint64_t>(a, 37);
226 c += llvm::rotr<uint64_t>(a, 7);
229 uint64_t ws = b + llvm::rotr<uint64_t>(a, 31) + c;
235 if (length >= 4 && length <= 8)
237 if (length > 8 && length <= 16)
239 if (length > 16 && length <= 32)
262 llvm::rotr<uint64_t>(seed ^
k1, 49),
276 b = llvm::rotr<uint64_t>(b + a + c, 21);
279 b += llvm::rotr<uint64_t>(a, 44) + d;
291 h2 = llvm::rotr<uint64_t>(
h2 +
h5, 33) *
k1;
316#if LLVM_ENABLE_ABI_BREAKING_CHECKS && \
317 (!defined(__clang__) || __clang_major__ > 11)
321 return 0xff51afd7ed558ccdULL;
339 : std::integral_constant<bool, ((is_integral_or_enum<T>::value ||
340 std::is_pointer<T>::value) &&
341 64 % sizeof(T) == 0)> {};
348 : std::integral_constant<bool, (is_hashable_data<T>::value &&
349 is_hashable_data<U>::value &&
350 (sizeof(T) + sizeof(U)) ==
351 sizeof(std::pair<T, U>))> {};
356std::enable_if_t<is_hashable_data<T>::value,
T>
364std::enable_if_t<!is_hashable_data<T>::value,
size_t>
366 using ::llvm::hash_value;
380 size_t store_size =
sizeof(
value) - offset;
381 if (buffer_ptr + store_size > buffer_end)
383 const char *value_data =
reinterpret_cast<const char *
>(&
value);
384 memcpy(buffer_ptr, value_data + offset, store_size);
385 buffer_ptr += store_size;
394template <
typename InputIteratorT>
397 char buffer[64], *buffer_ptr = buffer;
398 char *
const buffer_end = std::end(buffer);
403 return hash_short(buffer, buffer_ptr - buffer, seed);
404 assert(buffer_ptr == buffer_end);
408 while (first != last) {
419 std::rotate(buffer, buffer_ptr, buffer_end);
423 length += buffer_ptr - buffer;
437template <
typename ValueT>
438std::enable_if_t<is_hashable_data<ValueT>::value,
hash_code>
441 const char *s_begin =
reinterpret_cast<const char *
>(first);
442 const char *s_end =
reinterpret_cast<const char *
>(last);
443 const size_t length = std::distance(s_begin, s_end);
447 const char *s_aligned_end = s_begin + (length & ~63);
450 while (s_begin != s_aligned_end) {
455 state.mix(s_end - 64);
457 return state.finalize(length);
470template <
typename InputIteratorT>
472 return ::llvm::hashing::detail::hash_combine_range_impl(first, last);
506 template <
typename T>
507 char *
combine_data(
size_t &length,
char *buffer_ptr,
char *buffer_end,
T data) {
513 size_t partial_store_size = buffer_end - buffer_ptr;
514 memcpy(buffer_ptr, &data, partial_store_size);
545 template <
typename T,
typename ...Ts>
547 const T &arg,
const Ts &...
args) {
551 return combine(length, buffer_ptr, buffer_end,
args...);
569 std::rotate(
buffer, buffer_ptr, buffer_end);
573 length += buffer_ptr -
buffer;
612 const char *s =
reinterpret_cast<const char *
>(&
value);
624 return ::llvm::hashing::detail::hash_integer_value(
631 return ::llvm::hashing::detail::hash_integer_value(
632 reinterpret_cast<uintptr_t
>(ptr));
637template <
typename T,
typename U>
643 return std::apply([](
const auto &...xs) {
return hash_combine(xs...); }, arg);
661 return static_cast<unsigned>(size_t(val));
Given that RA is a live value
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
An opaque object representing a hash code.
friend size_t hash_value(const hash_code &code)
Allow a hash_code to be directly run through hash_value.
friend bool operator==(const hash_code &lhs, const hash_code &rhs)
friend bool operator!=(const hash_code &lhs, const hash_code &rhs)
hash_code(size_t value)
Form a hash code directly from a numerical value.
hash_code()=default
Default construct a hash_code.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
uint64_t hash_1to3_bytes(const char *s, size_t len, uint64_t seed)
bool store_and_advance(char *&buffer_ptr, char *buffer_end, const T &value, size_t offset=0)
Helper to store data from a value into a buffer and advance the pointer into that buffer.
uint64_t hash_9to16_bytes(const char *s, size_t len, uint64_t seed)
uint64_t hash_4to8_bytes(const char *s, size_t len, uint64_t seed)
hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last)
Implement the combining of integral values into a hash_code.
std::enable_if_t< is_hashable_data< T >::value, T > get_hashable_data(const T &value)
Helper to get the hashable data representation for a type.
hash_code hash_integer_value(uint64_t value)
Helper to hash the value of a single integer.
uint64_t rotate(uint64_t val, size_t shift)
Bitwise right rotate.
static constexpr uint64_t k2
uint64_t fetch64(const char *p)
uint64_t hash_17to32_bytes(const char *s, size_t len, uint64_t seed)
static constexpr uint64_t k1
uint64_t get_execution_seed()
In LLVM_ENABLE_ABI_BREAKING_CHECKS builds, the seed is non-deterministic per process (address of a fu...
uint32_t fetch32(const char *p)
static constexpr uint64_t k3
uint64_t hash_short(const char *s, size_t length, uint64_t seed)
static constexpr uint64_t k0
Some primes between 2^63 and 2^64 for various uses.
uint64_t shift_mix(uint64_t val)
uint64_t hash_33to64_bytes(const char *s, size_t len, uint64_t seed)
uint64_t hash_16_bytes(uint64_t low, uint64_t high)
constexpr bool IsBigEndianHost
void swapByteOrder(T &Value)
This is an optimization pass for GlobalISel generic memory operations.
hash_code hash_value(const FixedPointSemantics &Val)
void install_fatal_error_handler(fatal_error_handler_t handler, void *user_data=nullptr)
install_fatal_error_handler - Installs a new error handler to be used whenever a serious (non-recover...
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static bool isEqual(hash_code LHS, hash_code RHS)
static hash_code getEmptyKey()
static unsigned getHashValue(hash_code val)
static hash_code getTombstoneKey()
An information struct used to provide DenseMap with the various necessary components for a given valu...
Helper class to manage the recursive combining of hash_combine arguments.
hash_code combine(size_t length, char *buffer_ptr, char *buffer_end)
Base case for recursive, variadic combining.
char * combine_data(size_t &length, char *buffer_ptr, char *buffer_end, T data)
Combine one chunk of data into the current in-flight hash.
hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, const T &arg, const Ts &...args)
Recursive, variadic combining method.
hash_combine_recursive_helper()
Construct a recursive hash combining helper.
The intermediate state used during hashing.
static hash_state create(const char *s, uint64_t seed)
Create a new hash_state structure and initialize it based on the seed and the first 64-byte chunk.
uint64_t finalize(size_t length)
Compute the final 64-bit hash code value based on the current state and the length of bytes hashed.
static void mix_32_bytes(const char *s, uint64_t &a, uint64_t &b)
Mix 32-bytes from the input sequence into the 16-bytes of 'a' and 'b', including whatever is already ...
void mix(const char *s)
Mix in a 64-byte buffer of data.
Trait to indicate whether a type's bits can be hashed directly.
size_t operator()(llvm::hash_code const &Val) const