44#ifndef LLVM_ADT_HASHING_H
45#define LLVM_ADT_HASHING_H
60template <
typename T,
typename Enable>
struct DenseMapInfo;
86 operator size_t()
const {
return value; }
89 return lhs.value == rhs.value;
92 return lhs.value != rhs.value;
107std::enable_if_t<is_integral_or_enum<T>::value, hash_code>
hash_value(
T value);
112template <
typename T> hash_code
hash_value(
const T *ptr);
115template <
typename T,
typename U>
116hash_code
hash_value(
const std::pair<T, U> &arg);
119template <
typename... Ts>
120hash_code
hash_value(
const std::tuple<Ts...> &arg);
124hash_code
hash_value(
const std::basic_string<T> &arg);
127template <
typename T> hash_code
hash_value(
const std::optional<T> &arg);
154 memcpy(&result, p,
sizeof(result));
162 memcpy(&result, p,
sizeof(result));
179 return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
183 return val ^ (val >> 47);
188 const uint64_t kMul = 0x9ddfea08eb382d69ULL;
199 uint8_t b = s[len >> 1];
200 uint8_t c = s[len - 1];
223 llvm::rotr<uint64_t>(c ^ seed, 30) + d,
224 a + llvm::rotr<uint64_t>(b ^
k3, 20) - c + len + seed);
230 uint64_t b = llvm::rotr<uint64_t>(a + z, 52);
231 uint64_t c = llvm::rotr<uint64_t>(a, 37);
233 c += llvm::rotr<uint64_t>(a, 7);
236 uint64_t vs = b + llvm::rotr<uint64_t>(a, 31) + c;
239 b = llvm::rotr<uint64_t>(a + z, 52);
240 c = llvm::rotr<uint64_t>(a, 37);
242 c += llvm::rotr<uint64_t>(a, 7);
245 uint64_t ws = b + llvm::rotr<uint64_t>(a, 31) + c;
251 if (length >= 4 && length <= 8)
253 if (length > 8 && length <= 16)
255 if (length > 16 && length <= 32)
278 llvm::rotr<uint64_t>(seed ^
k1, 49),
292 b = llvm::rotr<uint64_t>(b + a + c, 21);
295 b += llvm::rotr<uint64_t>(a, 44) + d;
307 h2 = llvm::rotr<uint64_t>(
h2 +
h5, 33) *
k1;
340 const uint64_t seed_prime = 0xff51afd7ed558ccdULL;
359 : std::integral_constant<bool, ((is_integral_or_enum<T>::value ||
360 std::is_pointer<T>::value) &&
361 64 % sizeof(T) == 0)> {};
368 : std::integral_constant<bool, (is_hashable_data<T>::value &&
369 is_hashable_data<U>::value &&
370 (sizeof(T) + sizeof(U)) ==
371 sizeof(std::pair<T, U>))> {};
376std::enable_if_t<is_hashable_data<T>::value,
T>
384std::enable_if_t<!is_hashable_data<T>::value,
size_t>
386 using ::llvm::hash_value;
400 size_t store_size =
sizeof(
value) - offset;
401 if (buffer_ptr + store_size > buffer_end)
403 const char *value_data =
reinterpret_cast<const char *
>(&
value);
404 memcpy(buffer_ptr, value_data + offset, store_size);
405 buffer_ptr += store_size;
414template <
typename InputIteratorT>
417 char buffer[64], *buffer_ptr = buffer;
418 char *
const buffer_end = std::end(buffer);
423 return hash_short(buffer, buffer_ptr - buffer, seed);
424 assert(buffer_ptr == buffer_end);
428 while (first != last) {
439 std::rotate(buffer, buffer_ptr, buffer_end);
443 length += buffer_ptr - buffer;
457template <
typename ValueT>
458std::enable_if_t<is_hashable_data<ValueT>::value,
hash_code>
461 const char *s_begin =
reinterpret_cast<const char *
>(first);
462 const char *s_end =
reinterpret_cast<const char *
>(last);
463 const size_t length = std::distance(s_begin, s_end);
467 const char *s_aligned_end = s_begin + (length & ~63);
470 while (s_begin != s_aligned_end) {
475 state.mix(s_end - 64);
477 return state.finalize(length);
490template <
typename InputIteratorT>
492 return ::llvm::hashing::detail::hash_combine_range_impl(first, last);
526 template <
typename T>
527 char *
combine_data(
size_t &length,
char *buffer_ptr,
char *buffer_end,
T data) {
533 size_t partial_store_size = buffer_end - buffer_ptr;
534 memcpy(buffer_ptr, &data, partial_store_size);
565 template <
typename T,
typename ...Ts>
567 const T &arg,
const Ts &...
args) {
571 return combine(length, buffer_ptr, buffer_end,
args...);
589 std::rotate(
buffer, buffer_ptr, buffer_end);
593 length += buffer_ptr -
buffer;
632 const char *s =
reinterpret_cast<const char *
>(&
value);
644 return ::llvm::hashing::detail::hash_integer_value(
651 return ::llvm::hashing::detail::hash_integer_value(
652 reinterpret_cast<uintptr_t
>(ptr));
657template <
typename T,
typename U>
663 return std::apply([](
const auto &...xs) {
return hash_combine(xs...); }, arg);
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.
static constexpr uint64_t k2
uint64_t fetch64(const char *p)
uint64_t fixed_seed_override
A global, fixed seed-override variable.
uint64_t hash_17to32_bytes(const char *s, size_t len, uint64_t seed)
static constexpr uint64_t k1
uint64_t get_execution_seed()
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 set_fixed_execution_hash_seed(uint64_t fixed_value)
Override the execution seed with a fixed value.
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