LLVM  6.0.0svn
TypeSerializer.cpp
Go to the documentation of this file.
1 //===- TypeSerialzier.cpp -------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/DenseSet.h"
13 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/Support/Allocator.h"
20 #include "llvm/Support/Endian.h"
21 #include "llvm/Support/Error.h"
22 #include <algorithm>
23 #include <cassert>
24 #include <cstdint>
25 #include <cstring>
26 
27 using namespace llvm;
28 using namespace llvm::codeview;
29 
30 namespace {
31 
32 struct HashedType {
33  uint64_t Hash;
34  const uint8_t *Data;
35  unsigned Size; // FIXME: Go to uint16_t?
36  TypeIndex Index;
37 };
38 
39 /// Wrapper around a poitner to a HashedType. Hash and equality operations are
40 /// based on data in the pointee.
41 struct HashedTypePtr {
42  HashedTypePtr() = default;
43  HashedTypePtr(HashedType *Ptr) : Ptr(Ptr) {}
44 
45  HashedType *Ptr = nullptr;
46 };
47 
48 } // end anonymous namespace
49 
50 namespace llvm {
51 
52 template <> struct DenseMapInfo<HashedTypePtr> {
53  static inline HashedTypePtr getEmptyKey() { return HashedTypePtr(nullptr); }
54 
55  static inline HashedTypePtr getTombstoneKey() {
56  return HashedTypePtr(reinterpret_cast<HashedType *>(1));
57  }
58 
59  static unsigned getHashValue(HashedTypePtr Val) {
60  assert(Val.Ptr != getEmptyKey().Ptr && Val.Ptr != getTombstoneKey().Ptr);
61  return Val.Ptr->Hash;
62  }
63 
64  static bool isEqual(HashedTypePtr LHSP, HashedTypePtr RHSP) {
65  HashedType *LHS = LHSP.Ptr;
66  HashedType *RHS = RHSP.Ptr;
67  if (RHS == getEmptyKey().Ptr || RHS == getTombstoneKey().Ptr)
68  return LHS == RHS;
69  if (LHS->Hash != RHS->Hash || LHS->Size != RHS->Size)
70  return false;
71  return ::memcmp(LHS->Data, RHS->Data, LHS->Size) == 0;
72  }
73 };
74 
75 } // end namespace llvm
76 
77 /// Private implementation so that we don't leak our DenseMap instantiations to
78 /// users.
80 private:
81  /// Storage for type record provided by the caller. Records will outlive the
82  /// hasher object, so they should be allocated here.
83  BumpPtrAllocator &RecordStorage;
84 
85  /// Storage for hash keys. These only need to live as long as the hashing
86  /// operation.
87  BumpPtrAllocator KeyStorage;
88 
89  /// Hash table. We really want a DenseMap<ArrayRef<uint8_t>, TypeIndex> here,
90  /// but DenseMap is inefficient when the keys are long (like type records)
91  /// because it recomputes the hash value of every key when it grows. This
92  /// value type stores the hash out of line in KeyStorage, so that table
93  /// entries are small and easy to rehash.
94  DenseSet<HashedTypePtr> HashedRecords;
95 
96 public:
97  TypeHasher(BumpPtrAllocator &RecordStorage) : RecordStorage(RecordStorage) {}
98 
99  void reset() { HashedRecords.clear(); }
100 
101  /// Takes the bytes of type record, inserts them into the hash table, saves
102  /// them, and returns a pointer to an identical stable type record along with
103  /// its type index in the destination stream.
104  TypeIndex getOrCreateRecord(ArrayRef<uint8_t> &Record, TypeIndex TI);
105 };
106 
108  TypeIndex TI) {
109  assert(Record.size() < UINT32_MAX && "Record too big");
110  assert(Record.size() % 4 == 0 && "Record is not aligned to 4 bytes!");
111 
112  // Compute the hash up front so we can store it in the key.
113  HashedType TempHashedType = {hash_value(Record), Record.data(),
114  unsigned(Record.size()), TI};
115  auto Result = HashedRecords.insert(HashedTypePtr(&TempHashedType));
116  HashedType *&Hashed = Result.first->Ptr;
117 
118  if (Result.second) {
119  // This was a new type record. We need stable storage for both the key and
120  // the record. The record should outlive the hashing operation.
121  Hashed = KeyStorage.Allocate<HashedType>();
122  *Hashed = TempHashedType;
123 
124  uint8_t *Stable = RecordStorage.Allocate<uint8_t>(Record.size());
125  memcpy(Stable, Record.data(), Record.size());
126  Hashed->Data = Stable;
127  assert(Hashed->Size == Record.size());
128  }
129 
130  // Update the caller's copy of Record to point a stable copy.
131  Record = ArrayRef<uint8_t>(Hashed->Data, Hashed->Size);
132  return Hashed->Index;
133 }
134 
135 TypeIndex TypeSerializer::nextTypeIndex() const {
136  return TypeIndex::fromArrayIndex(SeenRecords.size());
137 }
138 
139 bool TypeSerializer::isInFieldList() const {
140  return TypeKind.hasValue() && *TypeKind == TypeLeafKind::LF_FIELDLIST;
141 }
142 
143 MutableArrayRef<uint8_t> TypeSerializer::getCurrentSubRecordData() {
144  assert(isInFieldList());
145  return getCurrentRecordData().drop_front(CurrentSegment.length());
146 }
147 
148 MutableArrayRef<uint8_t> TypeSerializer::getCurrentRecordData() {
149  return MutableArrayRef<uint8_t>(RecordBuffer).take_front(Writer.getOffset());
150 }
151 
152 Error TypeSerializer::writeRecordPrefix(TypeLeafKind Kind) {
154  Prefix.RecordKind = Kind;
155  Prefix.RecordLen = 0;
156  if (auto EC = Writer.writeObject(Prefix))
157  return EC;
158  return Error::success();
159 }
160 
162 TypeSerializer::addPadding(MutableArrayRef<uint8_t> Record) {
163  uint32_t Align = Record.size() % 4;
164  if (Align == 0)
165  return Record;
166 
167  int PaddingBytes = 4 - Align;
168  int N = PaddingBytes;
169  while (PaddingBytes > 0) {
170  uint8_t Pad = static_cast<uint8_t>(LF_PAD0 + PaddingBytes);
171  if (auto EC = Writer.writeInteger(Pad))
172  return std::move(EC);
173  --PaddingBytes;
174  }
175  return MutableArrayRef<uint8_t>(Record.data(), Record.size() + N);
176 }
177 
179  : RecordStorage(Storage), RecordBuffer(MaxRecordLength * 2),
180  Stream(RecordBuffer, support::little), Writer(Stream),
181  Mapping(Writer) {
182  // RecordBuffer needs to be able to hold enough data so that if we are 1
183  // byte short of MaxRecordLen, and then we try to write MaxRecordLen bytes,
184  // we won't overflow.
185  if (Hash)
186  Hasher = llvm::make_unique<TypeHasher>(Storage);
187 }
188 
190 
192  return SeenRecords;
193 }
194 
196  if (Hasher)
197  Hasher->reset();
198  Writer.setOffset(0);
199  CurrentSegment = RecordSegment();
200  FieldListSegments.clear();
201  TypeKind.reset();
202  MemberKind.reset();
203  SeenRecords.clear();
204 }
205 
207  assert(!TypeKind.hasValue() && "Already in a type mapping!");
208  assert(Writer.getOffset() == 0 && "Stream has data already!");
209 
210  if (Hasher) {
211  TypeIndex ActualTI = Hasher->getOrCreateRecord(Record, nextTypeIndex());
212  if (nextTypeIndex() == ActualTI)
213  SeenRecords.push_back(Record);
214  return ActualTI;
215  }
216 
217  TypeIndex NewTI = nextTypeIndex();
218  uint8_t *Stable = RecordStorage.Allocate<uint8_t>(Record.size());
219  memcpy(Stable, Record.data(), Record.size());
220  Record = ArrayRef<uint8_t>(Stable, Record.size());
221  SeenRecords.push_back(Record);
222  return NewTI;
223 }
224 
226  assert(!TypeKind.hasValue() && "Already in a type mapping!");
227  assert(Writer.getOffset() == 0 && "Stream has data already!");
228 
229  TypeIndex TI;
230  ArrayRef<uint8_t> OriginalData = Record.OriginalRecord.RecordData;
231  if (Record.Mappings.empty()) {
232  // This record did not remap any type indices. Just write it.
233  return insertRecordBytes(OriginalData);
234  }
235 
236  // At least one type index was remapped. Before we can hash it we have to
237  // copy the full record bytes, re-write each type index, then hash the copy.
238  // We do this in temporary storage since only the DenseMap can decide whether
239  // this record already exists, and if it does we don't want the memory to
240  // stick around.
241  RemapStorage.resize(OriginalData.size());
242  ::memcpy(&RemapStorage[0], OriginalData.data(), OriginalData.size());
243  uint8_t *ContentBegin = RemapStorage.data() + sizeof(RecordPrefix);
244  for (const auto &M : Record.Mappings) {
245  // First 4 bytes of every record are the record prefix, but the mapping
246  // offset is relative to the content which starts after.
247  *(TypeIndex *)(ContentBegin + M.first) = M.second;
248  }
249  auto RemapRef = makeArrayRef(RemapStorage);
250  return insertRecordBytes(RemapRef);
251 }
252 
254  assert(!TypeKind.hasValue() && "Already in a type mapping!");
255  assert(Writer.getOffset() == 0 && "Stream has data already!");
256 
257  if (auto EC = writeRecordPrefix(Record.kind()))
258  return EC;
259 
260  TypeKind = Record.kind();
261  if (auto EC = Mapping.visitTypeBegin(Record))
262  return EC;
263 
264  return Error::success();
265 }
266 
268  assert(TypeKind.hasValue() && "Not in a type mapping!");
269  if (auto EC = Mapping.visitTypeEnd(Record))
270  return std::move(EC);
271 
272  // Update the record's length and fill out the CVType members to point to
273  // the stable memory holding the record's data.
274  auto ThisRecordData = getCurrentRecordData();
275  auto ExpectedData = addPadding(ThisRecordData);
276  if (!ExpectedData)
277  return ExpectedData.takeError();
278  ThisRecordData = *ExpectedData;
279 
281  reinterpret_cast<RecordPrefix *>(ThisRecordData.data());
282  Prefix->RecordLen = ThisRecordData.size() - sizeof(uint16_t);
283 
284  Record.Type = *TypeKind;
285  Record.RecordData = ThisRecordData;
286 
287  // insertRecordBytes assumes we're not in a mapping, so do this first.
288  TypeKind.reset();
289  Writer.setOffset(0);
290 
291  TypeIndex InsertedTypeIndex = insertRecordBytes(Record.RecordData);
292 
293  // Write out each additional segment in reverse order, and update each
294  // record's continuation index to point to the previous one.
295  for (auto X : reverse(FieldListSegments)) {
296  auto CIBytes = X.take_back(sizeof(uint32_t));
298  reinterpret_cast<support::ulittle32_t *>(CIBytes.data());
299  assert(*CI == 0xB0C0B0C0 && "Invalid TypeIndex placeholder");
300  *CI = InsertedTypeIndex.getIndex();
301  InsertedTypeIndex = insertRecordBytes(X);
302  }
303 
304  FieldListSegments.clear();
305  CurrentSegment.SubRecords.clear();
306 
307  return InsertedTypeIndex;
308 }
309 
311  auto ExpectedIndex = visitTypeEndGetIndex(Record);
312  if (!ExpectedIndex)
313  return ExpectedIndex.takeError();
314  return Error::success();
315 }
316 
318  assert(isInFieldList() && "Not in a field list!");
319  assert(!MemberKind.hasValue() && "Already in a member record!");
320  MemberKind = Record.Kind;
321 
322  if (auto EC = Mapping.visitMemberBegin(Record))
323  return EC;
324 
325  return Error::success();
326 }
327 
329  if (auto EC = Mapping.visitMemberEnd(Record))
330  return EC;
331 
332  // Check if this subrecord makes the current segment not fit in 64K minus
333  // the space for a continuation record (8 bytes). If the segment does not
334  // fit, insert a continuation record.
335  if (Writer.getOffset() > MaxRecordLength - ContinuationLength) {
336  MutableArrayRef<uint8_t> Data = getCurrentRecordData();
337  SubRecord LastSubRecord = CurrentSegment.SubRecords.back();
338  uint32_t CopySize = CurrentSegment.length() - LastSubRecord.Size;
339  auto CopyData = Data.take_front(CopySize);
340  auto LeftOverData = Data.drop_front(CopySize);
341  assert(LastSubRecord.Size == LeftOverData.size());
342 
343  // Allocate stable storage for the record and copy the old record plus
344  // continuation over.
345  uint16_t LengthWithSize = CopySize + ContinuationLength;
346  assert(LengthWithSize <= MaxRecordLength);
347  RecordPrefix *Prefix = reinterpret_cast<RecordPrefix *>(CopyData.data());
348  Prefix->RecordLen = LengthWithSize - sizeof(uint16_t);
349 
350  uint8_t *SegmentBytes = RecordStorage.Allocate<uint8_t>(LengthWithSize);
351  auto SavedSegment = MutableArrayRef<uint8_t>(SegmentBytes, LengthWithSize);
352  MutableBinaryByteStream CS(SavedSegment, support::little);
353  BinaryStreamWriter CW(CS);
354  if (auto EC = CW.writeBytes(CopyData))
355  return EC;
356  if (auto EC = CW.writeEnum(TypeLeafKind::LF_INDEX))
357  return EC;
358  if (auto EC = CW.writeInteger<uint16_t>(0))
359  return EC;
360  if (auto EC = CW.writeInteger<uint32_t>(0xB0C0B0C0))
361  return EC;
362  FieldListSegments.push_back(SavedSegment);
363 
364  // Write a new placeholder record prefix to mark the start of this new
365  // top-level record.
366  Writer.setOffset(0);
367  if (auto EC = writeRecordPrefix(TypeLeafKind::LF_FIELDLIST))
368  return EC;
369 
370  // Then move over the subrecord that overflowed the old segment to the
371  // beginning of this segment. Note that we have to use memmove here
372  // instead of Writer.writeBytes(), because the new and old locations
373  // could overlap.
374  ::memmove(Stream.data().data() + sizeof(RecordPrefix), LeftOverData.data(),
375  LeftOverData.size());
376  // And point the segment writer at the end of that subrecord.
377  Writer.setOffset(LeftOverData.size() + sizeof(RecordPrefix));
378 
379  CurrentSegment.SubRecords.clear();
380  CurrentSegment.SubRecords.push_back(LastSubRecord);
381  }
382 
383  // Update the CVMemberRecord since we may have shifted around or gotten
384  // padded.
385  Record.Data = getCurrentSubRecordData();
386 
387  MemberKind.reset();
388  return Error::success();
389 }
void push_back(const T &Elt)
Definition: SmallVector.h:212
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
Error writeBytes(ArrayRef< uint8_t > Buffer)
Write the bytes specified in Buffer to the underlying stream.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
An implementation of BinaryStream which holds its entire data set in a single contiguous buffer...
Kind kind() const
Definition: CVRecord.h:37
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
MutableArrayRef< uint8_t > data() const
TypeIndex getOrCreateRecord(ArrayRef< uint8_t > &Record, TypeIndex TI)
Takes the bytes of type record, inserts them into the hash table, saves them, and returns a pointer t...
TypeLeafKind
Duplicate copy of the above enum, but using the official CV names.
Definition: CodeView.h:34
ArrayRef< uint8_t > Data
Definition: TypeRecord.h:41
Error visitMemberBegin(CVMemberRecord &Record) override
TypeIndex insertRecord(const RemappedType &Record)
Error visitTypeEnd(CVType &Record) override
ArrayRef< ArrayRef< uint8_t > > records() const
Private implementation so that we don&#39;t leak our DenseMap instantiations to users.
TypeHasher(BumpPtrAllocator &RecordStorage)
Error visitMemberEnd(CVMemberRecord &Record) override
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
SmallVector< std::pair< uint32_t, TypeIndex >, 8 > Mappings
Definition: CVRecord.h:61
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
CVRecord< Kind > OriginalRecord
Definition: CVRecord.h:60
static bool isEqual(HashedTypePtr LHSP, HashedTypePtr RHSP)
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
Error visitTypeEnd(CVType &Record) override
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:186
MutableArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
Definition: ArrayRef.h:362
Error visitTypeBegin(CVType &Record) override
Paired begin/end actions for all types.
A 32-bit type reference.
Definition: TypeIndex.h:96
hash_code hash_value(const APFloat &Arg)
See friend declarations above.
Definition: APFloat.cpp:4428
static TypeIndex fromArrayIndex(uint32_t Index)
Definition: TypeIndex.h:121
Error visitTypeBegin(CVType &Record) override
Paired begin/end actions for all types.
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
static HashedTypePtr getTombstoneKey()
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:212
static HashedTypePtr getEmptyKey()
Provides write only access to a subclass of WritableBinaryStream.
Error writeInteger(T Value)
Write the the integer Value to the underlying stream in the specified endianness. ...
const T * data() const
Definition: ArrayRef.h:146
uint32_t getIndex() const
Definition: TypeIndex.h:110
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
static unsigned getHashValue(HashedTypePtr Val)
Error writeEnum(T Num)
Similar to writeInteger.
void setOffset(uint32_t Off)
bool hasValue() const
Definition: Optional.h:137
ArrayRef< uint8_t > RecordData
Definition: CVRecord.h:53
pointer data()
Return a pointer to the vector&#39;s buffer, even if empty().
Definition: SmallVector.h:143
Merge contiguous icmps into a memcmp
Definition: MergeICmps.cpp:649
MutableArrayRef< T > take_front(size_t N=1) const
Return a copy of *this with only the first N elements.
Definition: ArrayRef.h:387
#define N
T * data() const
Definition: ArrayRef.h:329
Error visitMemberEnd(CVMemberRecord &Record) override
const unsigned Kind
void reset()
Definition: Optional.h:112
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
TypeIndex insertRecordBytes(ArrayRef< uint8_t > &Record)
Error visitMemberBegin(CVMemberRecord &Record) override
Expected< TypeIndex > visitTypeEndGetIndex(CVType &Record)
TypeSerializer(BumpPtrAllocator &Storage, bool Hash=true)
void resize(size_type N)
Definition: SmallVector.h:355