LLVM  9.0.0svn
TypeHashing.h
Go to the documentation of this file.
1 //===- TypeHashing.h ---------------------------------------------*- 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 #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEHASHING_H
10 #define LLVM_DEBUGINFO_CODEVIEW_TYPEHASHING_H
11 
12 #include "llvm/ADT/DenseMapInfo.h"
13 #include "llvm/ADT/Hashing.h"
14 
18 
20 
21 #include <type_traits>
22 
23 namespace llvm {
24 namespace codeview {
25 
26 /// A locally hashed type represents a straightforward hash code of a serialized
27 /// record. The record is simply serialized, and then the bytes are hashed by
28 /// a standard algorithm. This is sufficient for the case of de-duplicating
29 /// records within a single sequence of types, because if two records both have
30 /// a back-reference to the same type in the same stream, they will both have
31 /// the same numeric value for the TypeIndex of the back reference.
35 
36  /// Given a type, compute its local hash.
37  static LocallyHashedType hashType(ArrayRef<uint8_t> RecordData);
38 
39  /// Given a sequence of types, compute all of the local hashes.
40  template <typename Range>
41  static std::vector<LocallyHashedType> hashTypes(Range &&Records) {
42  std::vector<LocallyHashedType> Hashes;
43  Hashes.reserve(std::distance(std::begin(Records), std::end(Records)));
44  for (const auto &R : Records)
45  Hashes.push_back(hashType(R));
46 
47  return Hashes;
48  }
49 
50  static std::vector<LocallyHashedType>
52  std::vector<LocallyHashedType> Hashes;
53  Types.ForEachRecord([&Hashes](TypeIndex TI, const CVType &Type) {
54  Hashes.push_back(hashType(Type.RecordData));
55  });
56  return Hashes;
57  }
58 };
59 
60 enum class GlobalTypeHashAlg : uint16_t {
61  SHA1 = 0, // standard 20-byte SHA1 hash
62  SHA1_8 // last 8-bytes of standard SHA1 hash
63 };
64 
65 /// A globally hashed type represents a hash value that is sufficient to
66 /// uniquely identify a record across multiple type streams or type sequences.
67 /// This works by, for any given record A which references B, replacing the
68 /// TypeIndex that refers to B with a previously-computed global hash for B. As
69 /// this is a recursive algorithm (e.g. the global hash of B also depends on the
70 /// global hashes of the types that B refers to), a global hash can uniquely
71 /// identify identify that A occurs in another stream that has a completely
72 /// different graph structure. Although the hash itself is slower to compute,
73 /// probing is much faster with a globally hashed type, because the hash itself
74 /// is considered "as good as" the original type. Since type records can be
75 /// quite large, this makes the equality comparison of the hash much faster than
76 /// equality comparison of a full record.
78  GloballyHashedType() = default;
80  : GloballyHashedType(ArrayRef<uint8_t>(H.bytes_begin(), H.bytes_end())) {}
82  assert(H.size() == 8);
83  ::memcpy(Hash.data(), H.data(), 8);
84  }
85  std::array<uint8_t, 8> Hash;
86 
87  bool empty() const { return *(const uint64_t*)Hash.data() == 0; }
88 
89  /// Given a sequence of bytes representing a record, compute a global hash for
90  /// this record. Due to the nature of global hashes incorporating the hashes
91  /// of referenced records, this function requires a list of types and ids
92  /// that RecordData might reference, indexable by TypeIndex.
94  ArrayRef<GloballyHashedType> PreviousTypes,
95  ArrayRef<GloballyHashedType> PreviousIds);
96 
97  /// Given a sequence of bytes representing a record, compute a global hash for
98  /// this record. Due to the nature of global hashes incorporating the hashes
99  /// of referenced records, this function requires a list of types and ids
100  /// that RecordData might reference, indexable by TypeIndex.
102  ArrayRef<GloballyHashedType> PreviousTypes,
103  ArrayRef<GloballyHashedType> PreviousIds) {
104  return hashType(Type.RecordData, PreviousTypes, PreviousIds);
105  }
106 
107  /// Given a sequence of combined type and ID records, compute global hashes
108  /// for each of them, returning the results in a vector of hashed types.
109  template <typename Range>
110  static std::vector<GloballyHashedType> hashTypes(Range &&Records) {
111  std::vector<GloballyHashedType> Hashes;
112  bool UnresolvedRecords = false;
113  for (const auto &R : Records) {
114  GloballyHashedType H = hashType(R, Hashes, Hashes);
115  if (H.empty())
116  UnresolvedRecords = true;
117  Hashes.push_back(H);
118  }
119 
120  // In some rare cases, there might be records with forward references in the
121  // stream. Several passes might be needed to fully hash each record in the
122  // Type stream. However this occurs on very small OBJs generated by MASM,
123  // with a dozen records at most. Therefore this codepath isn't
124  // time-critical, as it isn't taken in 99% of cases.
125  while (UnresolvedRecords) {
126  UnresolvedRecords = false;
127  auto HashIt = Hashes.begin();
128  for (const auto &R : Records) {
129  if (HashIt->empty()) {
130  GloballyHashedType H = hashType(R, Hashes, Hashes);
131  if (H.empty())
132  UnresolvedRecords = true;
133  else
134  *HashIt = H;
135  }
136  ++HashIt;
137  }
138  }
139 
140  return Hashes;
141  }
142 
143  /// Given a sequence of combined type and ID records, compute global hashes
144  /// for each of them, returning the results in a vector of hashed types.
145  template <typename Range>
146  static std::vector<GloballyHashedType>
147  hashIds(Range &&Records, ArrayRef<GloballyHashedType> TypeHashes) {
148  std::vector<GloballyHashedType> IdHashes;
149  for (const auto &R : Records)
150  IdHashes.push_back(hashType(R, TypeHashes, IdHashes));
151 
152  return IdHashes;
153  }
154 
155  static std::vector<GloballyHashedType>
157  std::vector<GloballyHashedType> Hashes;
158  Types.ForEachRecord([&Hashes](TypeIndex TI, const CVType &Type) {
159  Hashes.push_back(hashType(Type.RecordData, Hashes, Hashes));
160  });
161  return Hashes;
162  }
163 };
164 #if defined(_MSC_VER)
165 // is_trivially_copyable is not available in older versions of libc++, but it is
166 // available in all supported versions of MSVC, so at least this gives us some
167 // coverage.
168 static_assert(std::is_trivially_copyable<GloballyHashedType>::value,
169  "GloballyHashedType must be trivially copyable so that we can "
170  "reinterpret_cast arrays of hash data to arrays of "
171  "GloballyHashedType");
172 #endif
173 } // namespace codeview
174 
175 template <> struct DenseMapInfo<codeview::LocallyHashedType> {
178 
179  static codeview::LocallyHashedType getEmptyKey() { return Empty; }
180 
181  static codeview::LocallyHashedType getTombstoneKey() { return Tombstone; }
182 
184  return Val.Hash;
185  }
186 
189  if (LHS.Hash != RHS.Hash)
190  return false;
191  return LHS.RecordData == RHS.RecordData;
192  }
193 };
194 
195 template <> struct DenseMapInfo<codeview::GloballyHashedType> {
198 
199  static codeview::GloballyHashedType getEmptyKey() { return Empty; }
200 
201  static codeview::GloballyHashedType getTombstoneKey() { return Tombstone; }
202 
204  return *reinterpret_cast<const unsigned *>(Val.Hash.data());
205  }
206 
209  return LHS.Hash == RHS.Hash;
210  }
211 };
212 
213 template <> struct format_provider<codeview::LocallyHashedType> {
214 public:
215  static void format(const codeview::LocallyHashedType &V,
216  llvm::raw_ostream &Stream, StringRef Style) {
217  write_hex(Stream, V.Hash, HexPrintStyle::Upper, 8);
218  }
219 };
220 
221 template <> struct format_provider<codeview::GloballyHashedType> {
222 public:
223  static void format(const codeview::GloballyHashedType &V,
224  llvm::raw_ostream &Stream, StringRef Style) {
225  for (uint8_t B : V.Hash) {
226  write_hex(Stream, B, HexPrintStyle::Upper, 2);
227  }
228  }
229 };
230 
231 } // namespace llvm
232 
233 #endif
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:258
static GloballyHashedType hashType(CVType Type, ArrayRef< GloballyHashedType > PreviousTypes, ArrayRef< GloballyHashedType > PreviousIds)
Given a sequence of bytes representing a record, compute a global hash for this record.
Definition: TypeHashing.h:101
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:249
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A locally hashed type represents a straightforward hash code of a serialized record.
Definition: TypeHashing.h:32
static bool isEqual(codeview::LocallyHashedType LHS, codeview::LocallyHashedType RHS)
Definition: TypeHashing.h:187
static codeview::GloballyHashedType getTombstoneKey()
Definition: TypeHashing.h:201
static bool isEqual(codeview::GloballyHashedType LHS, codeview::GloballyHashedType RHS)
Definition: TypeHashing.h:207
A class that wrap the SHA1 algorithm.
Definition: SHA1.h:28
static void format(const codeview::GloballyHashedType &V, llvm::raw_ostream &Stream, StringRef Style)
Definition: TypeHashing.h:223
static codeview::LocallyHashedType Tombstone
Definition: TypeHashing.h:177
static std::vector< GloballyHashedType > hashTypes(Range &&Records)
Given a sequence of combined type and ID records, compute global hashes for each of them...
Definition: TypeHashing.h:110
static LocallyHashedType hashType(ArrayRef< uint8_t > RecordData)
Given a type, compute its local hash.
Definition: TypeHashing.cpp:28
static std::vector< LocallyHashedType > hashTypes(Range &&Records)
Given a sequence of types, compute all of the local hashes.
Definition: TypeHashing.h:41
static codeview::LocallyHashedType getEmptyKey()
Definition: TypeHashing.h:179
static std::vector< LocallyHashedType > hashTypeCollection(TypeCollection &Types)
Definition: TypeHashing.h:51
A 32-bit type reference.
Definition: TypeIndex.h:95
A globally hashed type represents a hash value that is sufficient to uniquely identify a record acros...
Definition: TypeHashing.h:77
static codeview::LocallyHashedType Empty
Definition: TypeHashing.h:176
static std::vector< GloballyHashedType > hashTypeCollection(TypeCollection &Types)
Definition: TypeHashing.h:156
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
#define H(x, y, z)
Definition: MD5.cpp:57
std::array< uint8_t, 8 > Hash
Definition: TypeHashing.h:85
GloballyHashedType(ArrayRef< uint8_t > H)
Definition: TypeHashing.h:81
const T * data() const
Definition: ArrayRef.h:145
static codeview::GloballyHashedType Empty
Definition: TypeHashing.h:196
static codeview::GloballyHashedType getEmptyKey()
Definition: TypeHashing.h:199
static std::vector< GloballyHashedType > hashIds(Range &&Records, ArrayRef< GloballyHashedType > TypeHashes)
Given a sequence of combined type and ID records, compute global hashes for each of them...
Definition: TypeHashing.h:147
static unsigned getHashValue(codeview::LocallyHashedType Val)
Definition: TypeHashing.h:183
An opaque object representing a hash code.
Definition: Hashing.h:71
void write_hex(raw_ostream &S, uint64_t N, HexPrintStyle Style, Optional< size_t > Width=None)
ArrayRef< uint8_t > RecordData
Definition: CVRecord.h:48
static unsigned getHashValue(codeview::GloballyHashedType Val)
Definition: TypeHashing.h:203
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void format(const codeview::LocallyHashedType &V, llvm::raw_ostream &Stream, StringRef Style)
Definition: TypeHashing.h:215
static codeview::GloballyHashedType Tombstone
Definition: TypeHashing.h:197
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
ArrayRef< uint8_t > RecordData
Definition: TypeHashing.h:34
static codeview::LocallyHashedType getTombstoneKey()
Definition: TypeHashing.h:181