Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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 |