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