LLVM  14.0.0git
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.
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 
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  friend inline bool operator==(const GloballyHashedType &L,
90  const GloballyHashedType &R) {
91  return L.Hash == R.Hash;
92  }
93 
94  friend inline bool operator!=(const GloballyHashedType &L,
95  const GloballyHashedType &R) {
96  return !(L.Hash == R.Hash);
97  }
98 
99  /// Given a sequence of bytes representing a record, compute a global hash for
100  /// this record. Due to the nature of global hashes incorporating the hashes
101  /// of referenced records, this function requires a list of types and ids
102  /// that RecordData might reference, indexable by TypeIndex.
104  ArrayRef<GloballyHashedType> PreviousTypes,
105  ArrayRef<GloballyHashedType> PreviousIds);
106 
107  /// Given a sequence of bytes representing a record, compute a global hash for
108  /// this record. Due to the nature of global hashes incorporating the hashes
109  /// of referenced records, this function requires a list of types and ids
110  /// that RecordData might reference, indexable by TypeIndex.
112  ArrayRef<GloballyHashedType> PreviousTypes,
113  ArrayRef<GloballyHashedType> PreviousIds) {
114  return hashType(Type.RecordData, PreviousTypes, PreviousIds);
115  }
116 
117  /// Given a sequence of combined type and ID records, compute global hashes
118  /// for each of them, returning the results in a vector of hashed types.
119  template <typename Range>
120  static std::vector<GloballyHashedType> hashTypes(Range &&Records) {
121  std::vector<GloballyHashedType> Hashes;
122  bool UnresolvedRecords = false;
123  for (const auto &R : Records) {
124  GloballyHashedType H = hashType(R, Hashes, Hashes);
125  if (H.empty())
126  UnresolvedRecords = true;
127  Hashes.push_back(H);
128  }
129 
130  // In some rare cases, there might be records with forward references in the
131  // stream. Several passes might be needed to fully hash each record in the
132  // Type stream. However this occurs on very small OBJs generated by MASM,
133  // with a dozen records at most. Therefore this codepath isn't
134  // time-critical, as it isn't taken in 99% of cases.
135  while (UnresolvedRecords) {
136  UnresolvedRecords = false;
137  auto HashIt = Hashes.begin();
138  for (const auto &R : Records) {
139  if (HashIt->empty()) {
140  GloballyHashedType H = hashType(R, Hashes, Hashes);
141  if (H.empty())
142  UnresolvedRecords = true;
143  else
144  *HashIt = H;
145  }
146  ++HashIt;
147  }
148  }
149 
150  return Hashes;
151  }
152 
153  /// Given a sequence of combined type and ID records, compute global hashes
154  /// for each of them, returning the results in a vector of hashed types.
155  template <typename Range>
156  static std::vector<GloballyHashedType>
157  hashIds(Range &&Records, ArrayRef<GloballyHashedType> TypeHashes) {
158  std::vector<GloballyHashedType> IdHashes;
159  for (const auto &R : Records)
160  IdHashes.push_back(hashType(R, TypeHashes, IdHashes));
161 
162  return IdHashes;
163  }
164 
165  static std::vector<GloballyHashedType>
167  std::vector<GloballyHashedType> Hashes;
168  Types.ForEachRecord([&Hashes](TypeIndex TI, const CVType &Type) {
169  Hashes.push_back(hashType(Type.RecordData, Hashes, Hashes));
170  });
171  return Hashes;
172  }
173 };
174 static_assert(std::is_trivially_copyable<GloballyHashedType>::value,
175  "GloballyHashedType must be trivially copyable so that we can "
176  "reinterpret_cast arrays of hash data to arrays of "
177  "GloballyHashedType");
178 } // namespace codeview
179 
180 template <> struct DenseMapInfo<codeview::LocallyHashedType> {
183 
184  static codeview::LocallyHashedType getEmptyKey() { return Empty; }
185 
186  static codeview::LocallyHashedType getTombstoneKey() { return Tombstone; }
187 
189  return Val.Hash;
190  }
191 
194  if (LHS.Hash != RHS.Hash)
195  return false;
196  return LHS.RecordData == RHS.RecordData;
197  }
198 };
199 
200 template <> struct DenseMapInfo<codeview::GloballyHashedType> {
203 
204  static codeview::GloballyHashedType getEmptyKey() { return Empty; }
205 
206  static codeview::GloballyHashedType getTombstoneKey() { return Tombstone; }
207 
209  return *reinterpret_cast<const unsigned *>(Val.Hash.data());
210  }
211 
214  return LHS == RHS;
215  }
216 };
217 
218 template <> struct format_provider<codeview::LocallyHashedType> {
219 public:
220  static void format(const codeview::LocallyHashedType &V,
221  llvm::raw_ostream &Stream, StringRef Style) {
222  write_hex(Stream, V.Hash, HexPrintStyle::Upper, 8);
223  }
224 };
225 
226 template <> struct format_provider<codeview::GloballyHashedType> {
227 public:
228  static void format(const codeview::GloballyHashedType &V,
229  llvm::raw_ostream &Stream, StringRef Style) {
230  for (uint8_t B : V.Hash) {
231  write_hex(Stream, B, HexPrintStyle::Upper, 2);
232  }
233  }
234 };
235 
236 } // namespace llvm
237 
238 #endif
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::codeview::GloballyHashedType::GloballyHashedType
GloballyHashedType()=default
llvm::HexPrintStyle::Upper
@ Upper
FormatProviders.h
llvm::format_provider
Definition: FormatVariadicDetails.h:18
llvm::codeview::TypeCollection::ForEachRecord
void ForEachRecord(TFunc Func)
Definition: TypeCollection.h:34
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::DenseMapInfo< codeview::LocallyHashedType >::Empty
static codeview::LocallyHashedType Empty
Definition: TypeHashing.h:181
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::codeview::GlobalTypeHashAlg::SHA1_8
@ SHA1_8
llvm::DenseMapInfo< codeview::LocallyHashedType >::getTombstoneKey
static codeview::LocallyHashedType getTombstoneKey()
Definition: TypeHashing.h:186
Hashing.h
llvm::codeview::GlobalTypeHashAlg
GlobalTypeHashAlg
Definition: TypeHashing.h:60
llvm::DenseMapInfo< codeview::GloballyHashedType >::getEmptyKey
static codeview::GloballyHashedType getEmptyKey()
Definition: TypeHashing.h:204
llvm::codeview::GloballyHashedType::Hash
std::array< uint8_t, 8 > Hash
Definition: TypeHashing.h:85
llvm::codeview::LocallyHashedType
A locally hashed type represents a straightforward hash code of a serialized record.
Definition: TypeHashing.h:32
llvm::format_provider< codeview::GloballyHashedType >::format
static void format(const codeview::GloballyHashedType &V, llvm::raw_ostream &Stream, StringRef Style)
Definition: TypeHashing.h:228
llvm::codeview::LocallyHashedType::RecordData
ArrayRef< uint8_t > RecordData
Definition: TypeHashing.h:34
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::codeview::GloballyHashedType::hashType
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:111
llvm::DenseMapInfo< codeview::GloballyHashedType >::getHashValue
static unsigned getHashValue(codeview::GloballyHashedType Val)
Definition: TypeHashing.h:208
llvm::format_provider< codeview::LocallyHashedType >::format
static void format(const codeview::LocallyHashedType &V, llvm::raw_ostream &Stream, StringRef Style)
Definition: TypeHashing.h:220
llvm::SHA1
A class that wrap the SHA1 algorithm.
Definition: SHA1.h:26
llvm::codeview::LocallyHashedType::hashTypes
static std::vector< LocallyHashedType > hashTypes(Range &&Records)
Given a sequence of types, compute all of the local hashes.
Definition: TypeHashing.h:41
llvm::codeview::TypeCollection
Definition: TypeCollection.h:18
llvm::codeview::GloballyHashedType::hashType
static GloballyHashedType hashType(ArrayRef< uint8_t > RecordData, ArrayRef< GloballyHashedType > PreviousTypes, ArrayRef< GloballyHashedType > PreviousIds)
Given a sequence of bytes representing a record, compute a global hash for this record.
Definition: TypeHashing.cpp:33
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::DenseMapInfo< codeview::GloballyHashedType >::Empty
static codeview::GloballyHashedType Empty
Definition: TypeHashing.h:201
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::DenseMapInfo< codeview::LocallyHashedType >::getHashValue
static unsigned getHashValue(codeview::LocallyHashedType Val)
Definition: TypeHashing.h:188
CodeView.h
llvm::codeview::GloballyHashedType
A globally hashed type represents a hash value that is sufficient to uniquely identify a record acros...
Definition: TypeHashing.h:77
uint64_t
llvm::codeview::GloballyHashedType::hashIds
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:157
llvm::codeview::GloballyHashedType::operator==
friend bool operator==(const GloballyHashedType &L, const GloballyHashedType &R)
Definition: TypeHashing.h:89
llvm::codeview::GloballyHashedType::GloballyHashedType
GloballyHashedType(StringRef H)
Definition: TypeHashing.h:79
llvm::DenseMapInfo< codeview::GloballyHashedType >::Tombstone
static codeview::GloballyHashedType Tombstone
Definition: TypeHashing.h:202
llvm::HexStyle::Style
Style
Definition: MCInstPrinter.h:32
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DenseMapInfo< codeview::LocallyHashedType >::Tombstone
static codeview::LocallyHashedType Tombstone
Definition: TypeHashing.h:182
memcpy
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
llvm::write_hex
void write_hex(raw_ostream &S, uint64_t N, HexPrintStyle Style, Optional< size_t > Width=None)
Definition: NativeFormatting.cpp:133
llvm::DenseMapInfo< codeview::GloballyHashedType >::getTombstoneKey
static codeview::GloballyHashedType getTombstoneKey()
Definition: TypeHashing.h:206
llvm::DenseMapInfo< codeview::LocallyHashedType >::isEqual
static bool isEqual(codeview::LocallyHashedType LHS, codeview::LocallyHashedType RHS)
Definition: TypeHashing.h:192
llvm::ArrayRef< uint8_t >
llvm::DenseMapInfo< codeview::GloballyHashedType >::isEqual
static bool isEqual(codeview::GloballyHashedType LHS, codeview::GloballyHashedType RHS)
Definition: TypeHashing.h:212
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::codeview::CVRecord< TypeLeafKind >
llvm::codeview::LocallyHashedType::hashTypeCollection
static std::vector< LocallyHashedType > hashTypeCollection(TypeCollection &Types)
Definition: TypeHashing.h:51
llvm::codeview::LocallyHashedType::Hash
hash_code Hash
Definition: TypeHashing.h:33
H
#define H(x, y, z)
Definition: MD5.cpp:58
uint16_t
llvm::codeview::GloballyHashedType::operator!=
friend bool operator!=(const GloballyHashedType &L, const GloballyHashedType &R)
Definition: TypeHashing.h:94
TypeCollection.h
llvm::codeview::LocallyHashedType::hashType
static LocallyHashedType hashType(ArrayRef< uint8_t > RecordData)
Given a type, compute its local hash.
Definition: TypeHashing.cpp:28
TypeIndex.h
llvm::codeview::GloballyHashedType::empty
bool empty() const
Definition: TypeHashing.h:87
llvm::codeview::GloballyHashedType::hashTypes
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:120
llvm::DenseMapInfo< codeview::LocallyHashedType >::getEmptyKey
static codeview::LocallyHashedType getEmptyKey()
Definition: TypeHashing.h:184
DenseMapInfo.h
llvm::codeview::TypeIndex
A 32-bit type reference.
Definition: TypeIndex.h:95
llvm::codeview::GloballyHashedType::GloballyHashedType
GloballyHashedType(ArrayRef< uint8_t > H)
Definition: TypeHashing.h:81
llvm::codeview::GloballyHashedType::hashTypeCollection
static std::vector< GloballyHashedType > hashTypeCollection(TypeCollection &Types)
Definition: TypeHashing.h:166
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:72