Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- llvm/CodeGen/StableHashing.h - Utilities for stable hashing * C++ *-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. //
  9. // This file provides types and functions for computing and combining stable
  10. // hashes. Stable hashes can be useful for hashing across different modules,
  11. // processes, or compiler runs.
  12. //
  13. //===----------------------------------------------------------------------===//
  14.  
  15. #ifndef LLVM_CODEGEN_STABLEHASHING_H
  16. #define LLVM_CODEGEN_STABLEHASHING_H
  17.  
  18. #include "llvm/ADT/StringRef.h"
  19.  
  20. namespace llvm {
  21.  
  22. /// An opaque object representing a stable hash code. It can be serialized,
  23. /// deserialized, and is stable across processes and executions.
  24. using stable_hash = uint64_t;
  25.  
  26. // Implementation details
  27. namespace hashing {
  28. namespace detail {
  29.  
  30. // Stable hashes are based on the 64-bit FNV-1 hash:
  31. // https://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
  32.  
  33. const uint64_t FNV_PRIME_64 = 1099511628211u;
  34. const uint64_t FNV_OFFSET_64 = 14695981039346656037u;
  35.  
  36. inline void stable_hash_append(stable_hash &Hash, const char Value) {
  37.   Hash = Hash ^ (Value & 0xFF);
  38.   Hash = Hash * FNV_PRIME_64;
  39. }
  40.  
  41. inline void stable_hash_append(stable_hash &Hash, stable_hash Value) {
  42.   for (unsigned I = 0; I < 8; ++I) {
  43.     stable_hash_append(Hash, static_cast<char>(Value));
  44.     Value >>= 8;
  45.   }
  46. }
  47.  
  48. } // namespace detail
  49. } // namespace hashing
  50.  
  51. inline stable_hash stable_hash_combine(stable_hash A, stable_hash B) {
  52.   stable_hash Hash = hashing::detail::FNV_OFFSET_64;
  53.   hashing::detail::stable_hash_append(Hash, A);
  54.   hashing::detail::stable_hash_append(Hash, B);
  55.   return Hash;
  56. }
  57.  
  58. inline stable_hash stable_hash_combine(stable_hash A, stable_hash B,
  59.                                        stable_hash C) {
  60.   stable_hash Hash = hashing::detail::FNV_OFFSET_64;
  61.   hashing::detail::stable_hash_append(Hash, A);
  62.   hashing::detail::stable_hash_append(Hash, B);
  63.   hashing::detail::stable_hash_append(Hash, C);
  64.   return Hash;
  65. }
  66.  
  67. inline stable_hash stable_hash_combine(stable_hash A, stable_hash B,
  68.                                        stable_hash C, stable_hash D) {
  69.   stable_hash Hash = hashing::detail::FNV_OFFSET_64;
  70.   hashing::detail::stable_hash_append(Hash, A);
  71.   hashing::detail::stable_hash_append(Hash, B);
  72.   hashing::detail::stable_hash_append(Hash, C);
  73.   hashing::detail::stable_hash_append(Hash, D);
  74.   return Hash;
  75. }
  76.  
  77. /// Compute a stable_hash for a sequence of values.
  78. ///
  79. /// This hashes a sequence of values. It produces the same stable_hash as
  80. /// 'stable_hash_combine(a, b, c, ...)', but can run over arbitrary sized
  81. /// sequences and is significantly faster given pointers and types which
  82. /// can be hashed as a sequence of bytes.
  83. template <typename InputIteratorT>
  84. stable_hash stable_hash_combine_range(InputIteratorT First,
  85.                                       InputIteratorT Last) {
  86.   stable_hash Hash = hashing::detail::FNV_OFFSET_64;
  87.   for (auto I = First; I != Last; ++I)
  88.     hashing::detail::stable_hash_append(Hash, *I);
  89.   return Hash;
  90. }
  91.  
  92. inline stable_hash stable_hash_combine_array(const stable_hash *P, size_t C) {
  93.   stable_hash Hash = hashing::detail::FNV_OFFSET_64;
  94.   for (size_t I = 0; I < C; ++I)
  95.     hashing::detail::stable_hash_append(Hash, P[I]);
  96.   return Hash;
  97. }
  98.  
  99. inline stable_hash stable_hash_combine_string(const StringRef &S) {
  100.   return stable_hash_combine_range(S.begin(), S.end());
  101. }
  102.  
  103. inline stable_hash stable_hash_combine_string(const char *C) {
  104.   stable_hash Hash = hashing::detail::FNV_OFFSET_64;
  105.   while (*C)
  106.     hashing::detail::stable_hash_append(Hash, *(C++));
  107.   return Hash;
  108. }
  109.  
  110. } // namespace llvm
  111.  
  112. #endif
  113.