LLVM  7.0.0svn
TypeStreamMerger.cpp
Go to the documentation of this file.
1 //===-- TypeStreamMerger.cpp ------------------------------------*- C++ -*-===//
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/SmallString.h"
12 #include "llvm/ADT/StringExtras.h"
18 #include "llvm/Support/Error.h"
19 
20 using namespace llvm;
21 using namespace llvm::codeview;
22 
23 static inline size_t slotForIndex(TypeIndex Idx) {
24  assert(!Idx.isSimple() && "simple type indices have no slots");
26 }
27 
28 namespace {
29 
30 /// Implementation of CodeView type stream merging.
31 ///
32 /// A CodeView type stream is a series of records that reference each other
33 /// through type indices. A type index is either "simple", meaning it is less
34 /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
35 /// refers to a prior type record in the current stream. The type index of a
36 /// record is equal to the number of records before it in the stream plus
37 /// 0x1000.
38 ///
39 /// Type records are only allowed to use type indices smaller than their own, so
40 /// a type stream is effectively a topologically sorted DAG. Cycles occuring in
41 /// the type graph of the source program are resolved with forward declarations
42 /// of composite types. This class implements the following type stream merging
43 /// algorithm, which relies on this DAG structure:
44 ///
45 /// - Begin with a new empty stream, and a new empty hash table that maps from
46 /// type record contents to new type index.
47 /// - For each new type stream, maintain a map from source type index to
48 /// destination type index.
49 /// - For each record, copy it and rewrite its type indices to be valid in the
50 /// destination type stream.
51 /// - If the new type record is not already present in the destination stream
52 /// hash table, append it to the destination type stream, assign it the next
53 /// type index, and update the two hash tables.
54 /// - If the type record already exists in the destination stream, discard it
55 /// and update the type index map to forward the source type index to the
56 /// existing destination type index.
57 ///
58 /// As an additional complication, type stream merging actually produces two
59 /// streams: an item (or IPI) stream and a type stream, as this is what is
60 /// actually stored in the final PDB. We choose which records go where by
61 /// looking at the record kind.
62 class TypeStreamMerger {
63 public:
64  explicit TypeStreamMerger(SmallVectorImpl<TypeIndex> &SourceToDest)
65  : IndexMap(SourceToDest) {
66  SourceToDest.clear();
67  }
68 
69  static const TypeIndex Untranslated;
70 
71  // Local hashing entry points
72  Error mergeTypesAndIds(MergingTypeTableBuilder &DestIds,
73  MergingTypeTableBuilder &DestTypes,
74  const CVTypeArray &IdsAndTypes);
76  ArrayRef<TypeIndex> TypeSourceToDest,
77  const CVTypeArray &Ids);
79  const CVTypeArray &Types);
80 
81  // Global hashing entry points
82  Error mergeTypesAndIds(GlobalTypeTableBuilder &DestIds,
83  GlobalTypeTableBuilder &DestTypes,
84  const CVTypeArray &IdsAndTypes,
87  ArrayRef<TypeIndex> TypeSourceToDest,
88  const CVTypeArray &Ids,
92 
93 private:
94  Error doit(const CVTypeArray &Types);
95 
96  Error remapAllTypes(const CVTypeArray &Types);
97 
98  Error remapType(const CVType &Type);
99 
100  void addMapping(TypeIndex Idx);
101 
102  inline bool remapTypeIndex(TypeIndex &Idx) {
103  // If we're mapping a pure index stream, then IndexMap only contains
104  // mappings from OldIdStream -> NewIdStream, in which case we will need to
105  // use the special mapping from OldTypeStream -> NewTypeStream which was
106  // computed externally. Regardless, we use this special map if and only if
107  // we are doing an id-only mapping.
108  if (!hasTypeStream())
109  return remapIndex(Idx, TypeLookup);
110 
111  assert(TypeLookup.empty());
112  return remapIndex(Idx, IndexMap);
113  }
114  inline bool remapItemIndex(TypeIndex &Idx) {
115  assert(hasIdStream());
116  return remapIndex(Idx, IndexMap);
117  }
118 
119  bool hasTypeStream() const {
120  return (UseGlobalHashes) ? (!!DestGlobalTypeStream) : (!!DestTypeStream);
121  }
122 
123  bool hasIdStream() const {
124  return (UseGlobalHashes) ? (!!DestGlobalIdStream) : (!!DestIdStream);
125  }
126 
127  ArrayRef<uint8_t> remapIndices(const CVType &OriginalType,
128  MutableArrayRef<uint8_t> Storage);
129 
130  inline bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
131  if (LLVM_LIKELY(remapIndexSimple(Idx, Map)))
132  return true;
133 
134  return remapIndexFallback(Idx, Map);
135  }
136 
137  inline bool remapIndexSimple(TypeIndex &Idx, ArrayRef<TypeIndex> Map) const {
138  // Simple types are unchanged.
139  if (Idx.isSimple())
140  return true;
141 
142  // Check if this type index refers to a record we've already translated
143  // successfully. If it refers to a type later in the stream or a record we
144  // had to defer, defer it until later pass.
145  unsigned MapPos = slotForIndex(Idx);
146  if (LLVM_UNLIKELY(MapPos >= Map.size() || Map[MapPos] == Untranslated))
147  return false;
148 
149  Idx = Map[MapPos];
150  return true;
151  }
152 
153  bool remapIndexFallback(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
154 
155  Error errorCorruptRecord() const {
156  return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
157  }
158 
159  Optional<Error> LastError;
160 
161  bool UseGlobalHashes = false;
162 
163  bool IsSecondPass = false;
164 
165  unsigned NumBadIndices = 0;
166 
168 
169  MergingTypeTableBuilder *DestIdStream = nullptr;
170  MergingTypeTableBuilder *DestTypeStream = nullptr;
171 
172  GlobalTypeTableBuilder *DestGlobalIdStream = nullptr;
173  GlobalTypeTableBuilder *DestGlobalTypeStream = nullptr;
174 
175  ArrayRef<GloballyHashedType> GlobalHashes;
176 
177  // If we're only mapping id records, this array contains the mapping for
178  // type records.
179  ArrayRef<TypeIndex> TypeLookup;
180 
181  /// Map from source type index to destination type index. Indexed by source
182  /// type index minus 0x1000.
183  SmallVectorImpl<TypeIndex> &IndexMap;
184 
185  /// Temporary storage that we use to copy a record's data while re-writing
186  /// its type indices.
187  SmallVector<uint8_t, 256> RemapStorage;
188 };
189 
190 } // end anonymous namespace
191 
192 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
193 
194 static bool isIdRecord(TypeLeafKind K) {
195  switch (K) {
196  case TypeLeafKind::LF_FUNC_ID:
197  case TypeLeafKind::LF_MFUNC_ID:
198  case TypeLeafKind::LF_STRING_ID:
199  case TypeLeafKind::LF_SUBSTR_LIST:
200  case TypeLeafKind::LF_BUILDINFO:
201  case TypeLeafKind::LF_UDT_SRC_LINE:
202  case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
203  return true;
204  default:
205  return false;
206  }
207 }
208 
209 void TypeStreamMerger::addMapping(TypeIndex Idx) {
210  if (!IsSecondPass) {
211  assert(IndexMap.size() == slotForIndex(CurIndex) &&
212  "visitKnownRecord should add one index map entry");
213  IndexMap.push_back(Idx);
214  } else {
215  assert(slotForIndex(CurIndex) < IndexMap.size());
216  IndexMap[slotForIndex(CurIndex)] = Idx;
217  }
218 }
219 
220 bool TypeStreamMerger::remapIndexFallback(TypeIndex &Idx,
221  ArrayRef<TypeIndex> Map) {
222  size_t MapPos = slotForIndex(Idx);
223 
224  // If this is the second pass and this index isn't in the map, then it points
225  // outside the current type stream, and this is a corrupt record.
226  if (IsSecondPass && MapPos >= Map.size()) {
227  // FIXME: Print a more useful error. We can give the current record and the
228  // index that we think its pointing to.
229  LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
230  }
231 
232  ++NumBadIndices;
233 
234  // This type index is invalid. Remap this to "not translated by cvpack",
235  // and return failure.
236  Idx = Untranslated;
237  return false;
238 }
239 
240 // Local hashing entry points
242  const CVTypeArray &Types) {
243  DestTypeStream = &Dest;
244  UseGlobalHashes = false;
245 
246  return doit(Types);
247 }
248 
250  ArrayRef<TypeIndex> TypeSourceToDest,
251  const CVTypeArray &Ids) {
252  DestIdStream = &Dest;
253  TypeLookup = TypeSourceToDest;
254  UseGlobalHashes = false;
255 
256  return doit(Ids);
257 }
258 
259 Error TypeStreamMerger::mergeTypesAndIds(MergingTypeTableBuilder &DestIds,
260  MergingTypeTableBuilder &DestTypes,
261  const CVTypeArray &IdsAndTypes) {
262  DestIdStream = &DestIds;
263  DestTypeStream = &DestTypes;
264  UseGlobalHashes = false;
265  return doit(IdsAndTypes);
266 }
267 
268 // Global hashing entry points
270  const CVTypeArray &Types,
272  DestGlobalTypeStream = &Dest;
273  UseGlobalHashes = true;
274  GlobalHashes = Hashes;
275 
276  return doit(Types);
277 }
278 
280  ArrayRef<TypeIndex> TypeSourceToDest,
281  const CVTypeArray &Ids,
283  DestGlobalIdStream = &Dest;
284  TypeLookup = TypeSourceToDest;
285  UseGlobalHashes = true;
286  GlobalHashes = Hashes;
287 
288  return doit(Ids);
289 }
290 
291 Error TypeStreamMerger::mergeTypesAndIds(GlobalTypeTableBuilder &DestIds,
292  GlobalTypeTableBuilder &DestTypes,
293  const CVTypeArray &IdsAndTypes,
295  DestGlobalIdStream = &DestIds;
296  DestGlobalTypeStream = &DestTypes;
297  UseGlobalHashes = true;
298  GlobalHashes = Hashes;
299  return doit(IdsAndTypes);
300 }
301 
302 Error TypeStreamMerger::doit(const CVTypeArray &Types) {
303  if (auto EC = remapAllTypes(Types))
304  return EC;
305 
306  // If we found bad indices but no other errors, try doing another pass and see
307  // if we can resolve the indices that weren't in the map on the first pass.
308  // This may require multiple passes, but we should always make progress. MASM
309  // is the only known CodeView producer that makes type streams that aren't
310  // topologically sorted. The standard library contains MASM-produced objects,
311  // so this is important to handle correctly, but we don't have to be too
312  // efficient. MASM type streams are usually very small.
313  while (!LastError && NumBadIndices > 0) {
314  unsigned BadIndicesRemaining = NumBadIndices;
315  IsSecondPass = true;
316  NumBadIndices = 0;
318 
319  if (auto EC = remapAllTypes(Types))
320  return EC;
321 
322  assert(NumBadIndices <= BadIndicesRemaining &&
323  "second pass found more bad indices");
324  if (!LastError && NumBadIndices == BadIndicesRemaining) {
325  return llvm::make_error<CodeViewError>(
326  cv_error_code::corrupt_record, "input type graph contains cycles");
327  }
328  }
329 
330  if (LastError)
331  return std::move(*LastError);
332  return Error::success();
333 }
334 
335 Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
336  BinaryStreamRef Stream = Types.getUnderlyingStream();
337  ArrayRef<uint8_t> Buffer;
338  cantFail(Stream.readBytes(0, Stream.getLength(), Buffer));
339 
340  return forEachCodeViewRecord<CVType>(
341  Buffer, [this](const CVType &T) { return remapType(T); });
342 }
343 
344 Error TypeStreamMerger::remapType(const CVType &Type) {
345  auto DoSerialize =
346  [this, Type](MutableArrayRef<uint8_t> Storage) -> ArrayRef<uint8_t> {
347  return remapIndices(Type, Storage);
348  };
349 
350  TypeIndex DestIdx = Untranslated;
351  if (LLVM_LIKELY(UseGlobalHashes)) {
352  GlobalTypeTableBuilder &Dest =
353  isIdRecord(Type.kind()) ? *DestGlobalIdStream : *DestGlobalTypeStream;
354  GloballyHashedType H = GlobalHashes[CurIndex.toArrayIndex()];
355  DestIdx = Dest.insertRecordAs(H, Type.RecordData.size(), DoSerialize);
356  } else {
358  isIdRecord(Type.kind()) ? *DestIdStream : *DestTypeStream;
359 
360  RemapStorage.resize(Type.RecordData.size());
361  ArrayRef<uint8_t> Result = DoSerialize(RemapStorage);
362  if (!Result.empty())
363  DestIdx = Dest.insertRecordBytes(Result);
364  }
365  addMapping(DestIdx);
366 
367  ++CurIndex;
368  assert((IsSecondPass || IndexMap.size() == slotForIndex(CurIndex)) &&
369  "visitKnownRecord should add one index map entry");
370  return Error::success();
371 }
372 
374 TypeStreamMerger::remapIndices(const CVType &OriginalType,
375  MutableArrayRef<uint8_t> Storage) {
377  discoverTypeIndices(OriginalType.RecordData, Refs);
378  if (Refs.empty())
379  return OriginalType.RecordData;
380 
381  ::memcpy(Storage.data(), OriginalType.RecordData.data(),
382  OriginalType.RecordData.size());
383 
384  uint8_t *DestContent = Storage.data() + sizeof(RecordPrefix);
385 
386  for (auto &Ref : Refs) {
387  TypeIndex *DestTIs =
388  reinterpret_cast<TypeIndex *>(DestContent + Ref.Offset);
389 
390  for (size_t I = 0; I < Ref.Count; ++I) {
391  TypeIndex &TI = DestTIs[I];
392  bool Success = (Ref.Kind == TiRefKind::IndexRef) ? remapItemIndex(TI)
393  : remapTypeIndex(TI);
394  if (LLVM_UNLIKELY(!Success))
395  return {};
396  }
397  }
398  return Storage;
399 }
400 
402  SmallVectorImpl<TypeIndex> &SourceToDest,
403  const CVTypeArray &Types) {
404  TypeStreamMerger M(SourceToDest);
405  return M.mergeTypeRecords(Dest, Types);
406 }
407 
409  ArrayRef<TypeIndex> TypeSourceToDest,
410  SmallVectorImpl<TypeIndex> &SourceToDest,
411  const CVTypeArray &Ids) {
412  TypeStreamMerger M(SourceToDest);
413  return M.mergeIdRecords(Dest, TypeSourceToDest, Ids);
414 }
415 
418  SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes) {
419  TypeStreamMerger M(SourceToDest);
420  return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes);
421 }
422 
424  GlobalTypeTableBuilder &DestIds, GlobalTypeTableBuilder &DestTypes,
425  SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes,
427  TypeStreamMerger M(SourceToDest);
428  return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes, Hashes);
429 }
430 
432  SmallVectorImpl<TypeIndex> &SourceToDest,
433  const CVTypeArray &Types,
435  TypeStreamMerger M(SourceToDest);
436  return M.mergeTypeRecords(Dest, Types, Hashes);
437 }
438 
440  ArrayRef<TypeIndex> Types,
441  SmallVectorImpl<TypeIndex> &SourceToDest,
442  const CVTypeArray &Ids,
444  TypeStreamMerger M(SourceToDest);
445  return M.mergeIdRecords(Dest, Types, Ids, Hashes);
446 }
void cantFail(Error Err, const char *Msg=nullptr)
Report a fatal error if Err is a failure value.
Definition: Error.h:688
void discoverTypeIndices(ArrayRef< uint8_t > RecordData, SmallVectorImpl< TiReference > &Refs)
Kind kind() const
Definition: CVRecord.h:37
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
TypeLeafKind
Duplicate copy of the above enum, but using the official CV names.
Definition: CodeView.h:34
Error mergeTypeAndIdRecords(MergingTypeTableBuilder &DestIds, MergingTypeTableBuilder &DestTypes, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &IdsAndTypes)
Merge a unified set of type and id records, splitting them into separate output streams.
BinaryStreamRef getUnderlyingStream() const
Error mergeTypeRecords(MergingTypeTableBuilder &Dest, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &Types)
Merge one set of type records into another.
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:175
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
The access may reference the value stored in memory.
#define T
static const uint32_t FirstNonSimpleIndex
Definition: TypeIndex.h:98
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
A 32-bit type reference.
Definition: TypeIndex.h:96
A globally hashed type represents a hash value that is sufficient to uniquely identify a record acros...
Definition: TypeHashing.h:75
Error readBytes(uint32_t Offset, uint32_t Size, ArrayRef< uint8_t > &Buffer) const
Given an Offset into this StreamRef and a Size, return a reference to a buffer owned by the stream...
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
#define H(x, y, z)
Definition: MD5.cpp:57
const T * data() const
Definition: ArrayRef.h:146
uint32_t getIndex() const
Definition: TypeIndex.h:111
uint32_t getLength() const
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
BinaryStreamRef is to BinaryStream what ArrayRef is to an Array.
static bool isIdRecord(TypeLeafKind K)
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:176
static size_t slotForIndex(TypeIndex Idx)
#define Success
ArrayRef< uint8_t > RecordData
Definition: CVRecord.h:53
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Error joinErrors(Error E1, Error E2)
Concatenate errors.
Definition: Error.h:408
TypeIndex insertRecordBytes(ArrayRef< uint8_t > &Record)
#define I(x, y, z)
Definition: MD5.cpp:58
Error mergeIdRecords(MergingTypeTableBuilder &Dest, ArrayRef< TypeIndex > Types, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &Ids)
Merge one set of id records into another.
T * data() const
Definition: ArrayRef.h:329
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
TypeIndex insertRecordAs(GloballyHashedType Hash, size_t RecordSize, CreateFunc Create)
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144