LLVM  6.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"
20 
21 using namespace llvm;
22 using namespace llvm::codeview;
23 
24 namespace {
25 
26 /// Implementation of CodeView type stream merging.
27 ///
28 /// A CodeView type stream is a series of records that reference each other
29 /// through type indices. A type index is either "simple", meaning it is less
30 /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
31 /// refers to a prior type record in the current stream. The type index of a
32 /// record is equal to the number of records before it in the stream plus
33 /// 0x1000.
34 ///
35 /// Type records are only allowed to use type indices smaller than their own, so
36 /// a type stream is effectively a topologically sorted DAG. Cycles occuring in
37 /// the type graph of the source program are resolved with forward declarations
38 /// of composite types. This class implements the following type stream merging
39 /// algorithm, which relies on this DAG structure:
40 ///
41 /// - Begin with a new empty stream, and a new empty hash table that maps from
42 /// type record contents to new type index.
43 /// - For each new type stream, maintain a map from source type index to
44 /// destination type index.
45 /// - For each record, copy it and rewrite its type indices to be valid in the
46 /// destination type stream.
47 /// - If the new type record is not already present in the destination stream
48 /// hash table, append it to the destination type stream, assign it the next
49 /// type index, and update the two hash tables.
50 /// - If the type record already exists in the destination stream, discard it
51 /// and update the type index map to forward the source type index to the
52 /// existing destination type index.
53 ///
54 /// As an additional complication, type stream merging actually produces two
55 /// streams: an item (or IPI) stream and a type stream, as this is what is
56 /// actually stored in the final PDB. We choose which records go where by
57 /// looking at the record kind.
58 class TypeStreamMerger {
59 public:
60  explicit TypeStreamMerger(SmallVectorImpl<TypeIndex> &SourceToDest)
61  : IndexMap(SourceToDest) {
62  SourceToDest.clear();
63  }
64 
65  static const TypeIndex Untranslated;
66 
67  Error mergeTypesAndIds(TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
68  const CVTypeArray &IdsAndTypes);
70  ArrayRef<TypeIndex> TypeSourceToDest,
71  const CVTypeArray &Ids);
73 
74 private:
75  Error doit(const CVTypeArray &Types);
76 
77  Error remapAllTypes(const CVTypeArray &Types);
78 
79  Error remapType(const CVType &Type);
80 
81  void addMapping(TypeIndex Idx);
82 
83  bool remapTypeIndex(TypeIndex &Idx);
84  bool remapItemIndex(TypeIndex &Idx);
85 
86  bool remapIndices(RemappedType &Record, ArrayRef<TiReference> Refs);
87 
88  bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
89 
90  size_t slotForIndex(TypeIndex Idx) const {
91  assert(!Idx.isSimple() && "simple type indices have no slots");
93  }
94 
95  Error errorCorruptRecord() const {
96  return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
97  }
98 
99  Error writeRecord(TypeTableBuilder &Dest, const RemappedType &Record,
100  bool RemapSuccess) {
101  TypeIndex DestIdx = Untranslated;
102  if (RemapSuccess)
103  DestIdx = Dest.writeSerializedRecord(Record);
104  addMapping(DestIdx);
105  return Error::success();
106  }
107 
108  Optional<Error> LastError;
109 
110  bool IsSecondPass = false;
111 
112  unsigned NumBadIndices = 0;
113 
115 
116  TypeTableBuilder *DestIdStream = nullptr;
117  TypeTableBuilder *DestTypeStream = nullptr;
118 
119  // If we're only mapping id records, this array contains the mapping for
120  // type records.
121  ArrayRef<TypeIndex> TypeLookup;
122 
123  /// Map from source type index to destination type index. Indexed by source
124  /// type index minus 0x1000.
125  SmallVectorImpl<TypeIndex> &IndexMap;
126 };
127 
128 } // end anonymous namespace
129 
130 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
131 
132 static bool isIdRecord(TypeLeafKind K) {
133  switch (K) {
134  case TypeLeafKind::LF_FUNC_ID:
135  case TypeLeafKind::LF_MFUNC_ID:
136  case TypeLeafKind::LF_STRING_ID:
137  case TypeLeafKind::LF_SUBSTR_LIST:
138  case TypeLeafKind::LF_BUILDINFO:
139  case TypeLeafKind::LF_UDT_SRC_LINE:
140  case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
141  return true;
142  default:
143  return false;
144  }
145 }
146 
147 void TypeStreamMerger::addMapping(TypeIndex Idx) {
148  if (!IsSecondPass) {
149  assert(IndexMap.size() == slotForIndex(CurIndex) &&
150  "visitKnownRecord should add one index map entry");
151  IndexMap.push_back(Idx);
152  } else {
153  assert(slotForIndex(CurIndex) < IndexMap.size());
154  IndexMap[slotForIndex(CurIndex)] = Idx;
155  }
156 }
157 
158 bool TypeStreamMerger::remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
159  // Simple types are unchanged.
160  if (Idx.isSimple())
161  return true;
162 
163  // Check if this type index refers to a record we've already translated
164  // successfully. If it refers to a type later in the stream or a record we
165  // had to defer, defer it until later pass.
166  unsigned MapPos = slotForIndex(Idx);
167  if (MapPos < Map.size() && Map[MapPos] != Untranslated) {
168  Idx = Map[MapPos];
169  return true;
170  }
171 
172  // If this is the second pass and this index isn't in the map, then it points
173  // outside the current type stream, and this is a corrupt record.
174  if (IsSecondPass && MapPos >= Map.size()) {
175  // FIXME: Print a more useful error. We can give the current record and the
176  // index that we think its pointing to.
177  LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
178  }
179 
180  ++NumBadIndices;
181 
182  // This type index is invalid. Remap this to "not translated by cvpack",
183  // and return failure.
184  Idx = Untranslated;
185  return false;
186 }
187 
188 bool TypeStreamMerger::remapTypeIndex(TypeIndex &Idx) {
189  // If we're mapping a pure index stream, then IndexMap only contains mappings
190  // from OldIdStream -> NewIdStream, in which case we will need to use the
191  // special mapping from OldTypeStream -> NewTypeStream which was computed
192  // externally. Regardless, we use this special map if and only if we are
193  // doing an id-only mapping.
194  if (DestTypeStream == nullptr)
195  return remapIndex(Idx, TypeLookup);
196 
197  assert(TypeLookup.empty());
198  return remapIndex(Idx, IndexMap);
199 }
200 
201 bool TypeStreamMerger::remapItemIndex(TypeIndex &Idx) {
202  assert(DestIdStream);
203  return remapIndex(Idx, IndexMap);
204 }
205 
207  const CVTypeArray &Types) {
208  DestTypeStream = &Dest;
209 
210  return doit(Types);
211 }
212 
214  ArrayRef<TypeIndex> TypeSourceToDest,
215  const CVTypeArray &Ids) {
216  DestIdStream = &Dest;
217  TypeLookup = TypeSourceToDest;
218 
219  return doit(Ids);
220 }
221 
222 Error TypeStreamMerger::mergeTypesAndIds(TypeTableBuilder &DestIds,
223  TypeTableBuilder &DestTypes,
224  const CVTypeArray &IdsAndTypes) {
225  DestIdStream = &DestIds;
226  DestTypeStream = &DestTypes;
227  return doit(IdsAndTypes);
228 }
229 
230 Error TypeStreamMerger::doit(const CVTypeArray &Types) {
231  if (auto EC = remapAllTypes(Types))
232  return EC;
233 
234  // If we found bad indices but no other errors, try doing another pass and see
235  // if we can resolve the indices that weren't in the map on the first pass.
236  // This may require multiple passes, but we should always make progress. MASM
237  // is the only known CodeView producer that makes type streams that aren't
238  // topologically sorted. The standard library contains MASM-produced objects,
239  // so this is important to handle correctly, but we don't have to be too
240  // efficient. MASM type streams are usually very small.
241  while (!LastError && NumBadIndices > 0) {
242  unsigned BadIndicesRemaining = NumBadIndices;
243  IsSecondPass = true;
244  NumBadIndices = 0;
246 
247  if (auto EC = remapAllTypes(Types))
248  return EC;
249 
250  assert(NumBadIndices <= BadIndicesRemaining &&
251  "second pass found more bad indices");
252  if (!LastError && NumBadIndices == BadIndicesRemaining) {
253  return llvm::make_error<CodeViewError>(
254  cv_error_code::corrupt_record, "input type graph contains cycles");
255  }
256  }
257 
258  if (LastError)
259  return std::move(*LastError);
260  return Error::success();
261 }
262 
263 Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) {
264  for (const CVType &Type : Types)
265  if (auto EC = remapType(Type))
266  return EC;
267  return Error::success();
268 }
269 
270 Error TypeStreamMerger::remapType(const CVType &Type) {
271  RemappedType R(Type);
273  discoverTypeIndices(Type.RecordData, Refs);
274  bool MappedAllIndices = remapIndices(R, Refs);
275  TypeTableBuilder &Dest =
276  isIdRecord(Type.kind()) ? *DestIdStream : *DestTypeStream;
277  if (auto EC = writeRecord(Dest, R, MappedAllIndices))
278  return EC;
279 
280  ++CurIndex;
281  assert((IsSecondPass || IndexMap.size() == slotForIndex(CurIndex)) &&
282  "visitKnownRecord should add one index map entry");
283  return Error::success();
284 }
285 
286 bool TypeStreamMerger::remapIndices(RemappedType &Record,
287  ArrayRef<TiReference> Refs) {
288  ArrayRef<uint8_t> OriginalData = Record.OriginalRecord.content();
289  bool Success = true;
290  for (auto &Ref : Refs) {
291  uint32_t Offset = Ref.Offset;
292  ArrayRef<uint8_t> Bytes = OriginalData.slice(Ref.Offset, sizeof(TypeIndex));
293  ArrayRef<TypeIndex> TIs(reinterpret_cast<const TypeIndex *>(Bytes.data()),
294  Ref.Count);
295  for (auto TI : TIs) {
296  TypeIndex NewTI = TI;
297  bool ThisSuccess = (Ref.Kind == TiRefKind::IndexRef)
298  ? remapItemIndex(NewTI)
299  : remapTypeIndex(NewTI);
300  if (ThisSuccess && NewTI != TI)
301  Record.Mappings.emplace_back(Offset, NewTI);
302  Offset += sizeof(TypeIndex);
303  Success &= ThisSuccess;
304  }
305  }
306  return Success;
307 }
308 
310  SmallVectorImpl<TypeIndex> &SourceToDest,
311  const CVTypeArray &Types) {
312  TypeStreamMerger M(SourceToDest);
313  return M.mergeTypeRecords(Dest, Types);
314 }
315 
317  ArrayRef<TypeIndex> TypeSourceToDest,
318  SmallVectorImpl<TypeIndex> &SourceToDest,
319  const CVTypeArray &Ids) {
320  TypeStreamMerger M(SourceToDest);
321  return M.mergeIdRecords(Dest, TypeSourceToDest, Ids);
322 }
323 
325  TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
326  SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes) {
327  TypeStreamMerger M(SourceToDest);
328  return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes);
329 }
void discoverTypeIndices(ArrayRef< uint8_t > RecordData, SmallVectorImpl< TiReference > &Refs)
Error mergeTypeRecords(TypeTableBuilder &Dest, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &Types)
Merge one set of type records into another.
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
SmallVector< std::pair< uint32_t, TypeIndex >, 8 > Mappings
Definition: CVRecord.h:61
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
CVRecord< Kind > OriginalRecord
Definition: CVRecord.h:60
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
TypeIndex writeSerializedRecord(ArrayRef< uint8_t > Record)
Error mergeTypeAndIdRecords(TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &IdsAndTypes)
Merge a unified set of type and id records, splitting them into separate output streams.
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
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
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
static bool isIdRecord(TypeLeafKind K)
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array...
Definition: ArrayRef.h:179
#define Success
ArrayRef< uint8_t > RecordData
Definition: CVRecord.h:53
Error joinErrors(Error E1, Error E2)
Concatenate errors.
Definition: Error.h:408
Error mergeIdRecords(TypeTableBuilder &Dest, ArrayRef< TypeIndex > Types, SmallVectorImpl< TypeIndex > &SourceToDest, const CVTypeArray &Ids)
Merge one set of id records into another.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156