contrib/llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

   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
  10 #include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
  11 #include "llvm/ADT/SmallString.h"
  12 #include "llvm/ADT/StringExtras.h"
  13 #include "llvm/DebugInfo/CodeView/CVTypeVisitor.h"
  14 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
  15 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
  16 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
  17 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
  18 #include "llvm/Support/Error.h"
  19 #include "llvm/Support/ScopedPrinter.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 : public TypeVisitorCallbacks {
  59 public:
  60   TypeStreamMerger(TypeTableBuilder &DestIdStream,
  61                    TypeTableBuilder &DestTypeStream,
  62                    SmallVectorImpl<TypeIndex> &SourceToDest,
  63                    TypeServerHandler *Handler)
  64       : DestIdStream(DestIdStream), DestTypeStream(DestTypeStream),
  65         FieldListBuilder(DestTypeStream), Handler(Handler),
  66         IndexMap(SourceToDest) {}
  67
  68   static const TypeIndex Untranslated;
  69
  70 /// TypeVisitorCallbacks overrides.
  71 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
  72   Error visitKnownRecord(CVType &CVR, Name##Record &Record) override;
  73 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
  74   Error visitKnownMember(CVMemberRecord &CVR, Name##Record &Record) override;
  75 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
  76 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
  77 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
  78
  79   Error visitUnknownType(CVType &Record) override;
  80
  81   Error visitTypeBegin(CVType &Record) override;
  82   Error visitTypeEnd(CVType &Record) override;
  83   Error visitMemberEnd(CVMemberRecord &Record) override;
  84
  85   Error mergeStream(const CVTypeArray &Types);
  86
  87 private:
  88   void addMapping(TypeIndex Idx);
  89
  90   bool remapIndex(TypeIndex &Idx);
  91
  92   size_t slotForIndex(TypeIndex Idx) const {
  93     assert(!Idx.isSimple() && "simple type indices have no slots");
  94     return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
  95   }
  96
  97   Error errorCorruptRecord() const {
  98     return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
  99   }
 100
 101   template <typename RecordType>
 102   Error writeRecord(RecordType &R, bool RemapSuccess) {
 103     TypeIndex DestIdx = Untranslated;
 104     if (RemapSuccess)
 105       DestIdx = DestTypeStream.writeKnownType(R);
 106     addMapping(DestIdx);
 107     return Error::success();
 108   }
 109
 110   template <typename RecordType>
 111   Error writeIdRecord(RecordType &R, bool RemapSuccess) {
 112     TypeIndex DestIdx = Untranslated;
 113     if (RemapSuccess)
 114       DestIdx = DestIdStream.writeKnownType(R);
 115     addMapping(DestIdx);
 116     return Error::success();
 117   }
 118
 119   template <typename RecordType>
 120   Error writeMember(RecordType &R, bool RemapSuccess) {
 121     if (RemapSuccess)
 122       FieldListBuilder.writeMemberType(R);
 123     else
 124       HadUntranslatedMember = true;
 125     return Error::success();
 126   }
 127
 128   Optional<Error> LastError;
 129
 130   bool IsSecondPass = false;
 131
 132   bool HadUntranslatedMember = false;
 133
 134   unsigned NumBadIndices = 0;
 135
 136   BumpPtrAllocator Allocator;
 137
 138   TypeTableBuilder &DestIdStream;
 139   TypeTableBuilder &DestTypeStream;
 140   FieldListRecordBuilder FieldListBuilder;
 141   TypeServerHandler *Handler;
 142
 143   TypeIndex CurIndex{TypeIndex::FirstNonSimpleIndex};
 144
 145   /// Map from source type index to destination type index. Indexed by source
 146   /// type index minus 0x1000.
 147   SmallVectorImpl<TypeIndex> &IndexMap;
 148 };
 149
 150 } // end anonymous namespace
 151
 152 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
 153
 154 Error TypeStreamMerger::visitTypeBegin(CVRecord<TypeLeafKind> &Rec) {
 155   return Error::success();
 156 }
 157
 158 Error TypeStreamMerger::visitTypeEnd(CVRecord<TypeLeafKind> &Rec) {
 159   CurIndex = TypeIndex(CurIndex.getIndex() + 1);
 160   if (!IsSecondPass)
 161     assert(IndexMap.size() == slotForIndex(CurIndex) &&
 162            "visitKnownRecord should add one index map entry");
 163   return Error::success();
 164 }
 165
 166 Error TypeStreamMerger::visitMemberEnd(CVMemberRecord &Rec) {
 167   return Error::success();
 168 }
 169
 170 void TypeStreamMerger::addMapping(TypeIndex Idx) {
 171   if (!IsSecondPass) {
 172     assert(IndexMap.size() == slotForIndex(CurIndex) &&
 173            "visitKnownRecord should add one index map entry");
 174     IndexMap.push_back(Idx);
 175   } else {
 176     assert(slotForIndex(CurIndex) < IndexMap.size());
 177     IndexMap[slotForIndex(CurIndex)] = Idx;
 178   }
 179 }
 180
 181 bool TypeStreamMerger::remapIndex(TypeIndex &Idx) {
 182   // Simple types are unchanged.
 183   if (Idx.isSimple())
 184     return true;
 185
 186   // Check if this type index refers to a record we've already translated
 187   // successfully. If it refers to a type later in the stream or a record we
 188   // had to defer, defer it until later pass.
 189   unsigned MapPos = slotForIndex(Idx);
 190   if (MapPos < IndexMap.size() && IndexMap[MapPos] != Untranslated) {
 191     Idx = IndexMap[MapPos];
 192     return true;
 193   }
 194
 195   // If this is the second pass and this index isn't in the map, then it points
 196   // outside the current type stream, and this is a corrupt record.
 197   if (IsSecondPass && MapPos >= IndexMap.size()) {
 198     // FIXME: Print a more useful error. We can give the current record and the
 199     // index that we think its pointing to.
 200     LastError = joinErrors(std::move(*LastError), errorCorruptRecord());
 201   }
 202
 203   ++NumBadIndices;
 204
 205   // This type index is invalid. Remap this to "not translated by cvpack",
 206   // and return failure.
 207   Idx = Untranslated;
 208   return false;
 209 }
 210
 211 //----------------------------------------------------------------------------//
 212 // Item records
 213 //----------------------------------------------------------------------------//
 214
 215 Error TypeStreamMerger::visitKnownRecord(CVType &, FuncIdRecord &R) {
 216   bool Success = true;
 217   Success &= remapIndex(R.ParentScope);
 218   Success &= remapIndex(R.FunctionType);
 219   return writeIdRecord(R, Success);
 220 }
 221
 222 Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFuncIdRecord &R) {
 223   bool Success = true;
 224   Success &= remapIndex(R.ClassType);
 225   Success &= remapIndex(R.FunctionType);
 226   return writeIdRecord(R, Success);
 227 }
 228
 229 Error TypeStreamMerger::visitKnownRecord(CVType &, StringIdRecord &R) {
 230   return writeIdRecord(R, remapIndex(R.Id));
 231 }
 232
 233 Error TypeStreamMerger::visitKnownRecord(CVType &, StringListRecord &R) {
 234   bool Success = true;
 235   for (TypeIndex &Str : R.StringIndices)
 236     Success &= remapIndex(Str);
 237   return writeIdRecord(R, Success);
 238 }
 239
 240 Error TypeStreamMerger::visitKnownRecord(CVType &, BuildInfoRecord &R) {
 241   bool Success = true;
 242   for (TypeIndex &Arg : R.ArgIndices)
 243     Success &= remapIndex(Arg);
 244   return writeIdRecord(R, Success);
 245 }
 246
 247 Error TypeStreamMerger::visitKnownRecord(CVType &, UdtSourceLineRecord &R) {
 248   bool Success = true;
 249   Success &= remapIndex(R.UDT);
 250   Success &= remapIndex(R.SourceFile);
 251   // FIXME: Translate UdtSourceLineRecord into UdtModSourceLineRecords in the
 252   // IPI stream.
 253   return writeIdRecord(R, Success);
 254 }
 255
 256 Error TypeStreamMerger::visitKnownRecord(CVType &, UdtModSourceLineRecord &R) {
 257   bool Success = true;
 258   Success &= remapIndex(R.UDT);
 259   Success &= remapIndex(R.SourceFile);
 260   return writeIdRecord(R, Success);
 261 }
 262
 263 //----------------------------------------------------------------------------//
 264 // Type records
 265 //----------------------------------------------------------------------------//
 266
 267 Error TypeStreamMerger::visitKnownRecord(CVType &, ModifierRecord &R) {
 268   return writeRecord(R, remapIndex(R.ModifiedType));
 269 }
 270
 271 Error TypeStreamMerger::visitKnownRecord(CVType &, ProcedureRecord &R) {
 272   bool Success = true;
 273   Success &= remapIndex(R.ReturnType);
 274   Success &= remapIndex(R.ArgumentList);
 275   return writeRecord(R, Success);
 276 }
 277
 278 Error TypeStreamMerger::visitKnownRecord(CVType &, MemberFunctionRecord &R) {
 279   bool Success = true;
 280   Success &= remapIndex(R.ReturnType);
 281   Success &= remapIndex(R.ClassType);
 282   Success &= remapIndex(R.ThisType);
 283   Success &= remapIndex(R.ArgumentList);
 284   return writeRecord(R, Success);
 285 }
 286
 287 Error TypeStreamMerger::visitKnownRecord(CVType &Type, ArgListRecord &R) {
 288   bool Success = true;
 289   for (TypeIndex &Arg : R.ArgIndices)
 290     Success &= remapIndex(Arg);
 291   if (auto EC = writeRecord(R, Success))
 292     return EC;
 293   return Error::success();
 294 }
 295
 296 Error TypeStreamMerger::visitKnownRecord(CVType &, PointerRecord &R) {
 297   bool Success = true;
 298   Success &= remapIndex(R.ReferentType);
 299   if (R.isPointerToMember())
 300     Success &= remapIndex(R.MemberInfo->ContainingType);
 301   return writeRecord(R, Success);
 302 }
 303
 304 Error TypeStreamMerger::visitKnownRecord(CVType &, ArrayRecord &R) {
 305   bool Success = true;
 306   Success &= remapIndex(R.ElementType);
 307   Success &= remapIndex(R.IndexType);
 308   return writeRecord(R, Success);
 309 }
 310
 311 Error TypeStreamMerger::visitKnownRecord(CVType &, ClassRecord &R) {
 312   bool Success = true;
 313   Success &= remapIndex(R.FieldList);
 314   Success &= remapIndex(R.DerivationList);
 315   Success &= remapIndex(R.VTableShape);
 316   return writeRecord(R, Success);
 317 }
 318
 319 Error TypeStreamMerger::visitKnownRecord(CVType &, UnionRecord &R) {
 320   return writeRecord(R, remapIndex(R.FieldList));
 321 }
 322
 323 Error TypeStreamMerger::visitKnownRecord(CVType &, EnumRecord &R) {
 324   bool Success = true;
 325   Success &= remapIndex(R.FieldList);
 326   Success &= remapIndex(R.UnderlyingType);
 327   return writeRecord(R, Success);
 328 }
 329
 330 Error TypeStreamMerger::visitKnownRecord(CVType &, BitFieldRecord &R) {
 331   return writeRecord(R, remapIndex(R.Type));
 332 }
 333
 334 Error TypeStreamMerger::visitKnownRecord(CVType &, VFTableShapeRecord &R) {
 335   return writeRecord(R, true);
 336 }
 337
 338 Error TypeStreamMerger::visitKnownRecord(CVType &, TypeServer2Record &R) {
 339   return writeRecord(R, true);
 340 }
 341
 342 Error TypeStreamMerger::visitKnownRecord(CVType &, LabelRecord &R) {
 343   return writeRecord(R, true);
 344 }
 345
 346 Error TypeStreamMerger::visitKnownRecord(CVType &, VFTableRecord &R) {
 347   bool Success = true;
 348   Success &= remapIndex(R.CompleteClass);
 349   Success &= remapIndex(R.OverriddenVFTable);
 350   return writeRecord(R, Success);
 351 }
 352
 353 Error TypeStreamMerger::visitKnownRecord(CVType &,
 354                                          MethodOverloadListRecord &R) {
 355   bool Success = true;
 356   for (OneMethodRecord &Meth : R.Methods)
 357     Success &= remapIndex(Meth.Type);
 358   return writeRecord(R, Success);
 359 }
 360
 361 Error TypeStreamMerger::visitKnownRecord(CVType &, FieldListRecord &R) {
 362   // Visit the members inside the field list.
 363   HadUntranslatedMember = false;
 364   FieldListBuilder.begin();
 365   if (auto EC = codeview::visitMemberRecordStream(R.Data, *this))
 366     return EC;
 367
 368   // Write the record if we translated all field list members.
 369   TypeIndex DestIdx = Untranslated;
 370   if (!HadUntranslatedMember)
 371     DestIdx = FieldListBuilder.end();
 372   else
 373     FieldListBuilder.reset();
 374   addMapping(DestIdx);
 375
 376   return Error::success();
 377 }
 378
 379 //----------------------------------------------------------------------------//
 380 // Member records
 381 //----------------------------------------------------------------------------//
 382
 383 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 384                                          NestedTypeRecord &R) {
 385   return writeMember(R, remapIndex(R.Type));
 386 }
 387
 388 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, OneMethodRecord &R) {
 389   bool Success = true;
 390   Success &= remapIndex(R.Type);
 391   return writeMember(R, Success);
 392 }
 393
 394 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 395                                          OverloadedMethodRecord &R) {
 396   return writeMember(R, remapIndex(R.MethodList));
 397 }
 398
 399 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 400                                          DataMemberRecord &R) {
 401   return writeMember(R, remapIndex(R.Type));
 402 }
 403
 404 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 405                                          StaticDataMemberRecord &R) {
 406   return writeMember(R, remapIndex(R.Type));
 407 }
 408
 409 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 410                                          EnumeratorRecord &R) {
 411   return writeMember(R, true);
 412 }
 413
 414 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, VFPtrRecord &R) {
 415   return writeMember(R, remapIndex(R.Type));
 416 }
 417
 418 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &, BaseClassRecord &R) {
 419   return writeMember(R, remapIndex(R.Type));
 420 }
 421
 422 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 423                                          VirtualBaseClassRecord &R) {
 424   bool Success = true;
 425   Success &= remapIndex(R.BaseType);
 426   Success &= remapIndex(R.VBPtrType);
 427   return writeMember(R, Success);
 428 }
 429
 430 Error TypeStreamMerger::visitKnownMember(CVMemberRecord &,
 431                                          ListContinuationRecord &R) {
 432   return writeMember(R, remapIndex(R.ContinuationIndex));
 433 }
 434
 435 Error TypeStreamMerger::visitUnknownType(CVType &Rec) {
 436   // We failed to translate a type. Translate this index as "not translated".
 437   addMapping(TypeIndex(SimpleTypeKind::NotTranslated));
 438   return errorCorruptRecord();
 439 }
 440
 441 Error TypeStreamMerger::mergeStream(const CVTypeArray &Types) {
 442   assert(IndexMap.empty());
 443   LastError = Error::success();
 444
 445   if (auto EC = codeview::visitTypeStream(Types, *this, Handler))
 446     return EC;
 447
 448   // If we found bad indices but no other errors, try doing another pass and see
 449   // if we can resolve the indices that weren't in the map on the first pass.
 450   // This may require multiple passes, but we should always make progress. MASM
 451   // is the only known CodeView producer that makes type streams that aren't
 452   // topologically sorted. The standard library contains MASM-produced objects,
 453   // so this is important to handle correctly, but we don't have to be too
 454   // efficient. MASM type streams are usually very small.
 455   while (!*LastError && NumBadIndices > 0) {
 456     unsigned BadIndicesRemaining = NumBadIndices;
 457     IsSecondPass = true;
 458     NumBadIndices = 0;
 459     CurIndex = TypeIndex(TypeIndex::FirstNonSimpleIndex);
 460
 461     if (auto EC = codeview::visitTypeStream(Types, *this, Handler))
 462       return EC;
 463
 464     assert(NumBadIndices <= BadIndicesRemaining &&
 465            "second pass found more bad indices");
 466     if (!*LastError && NumBadIndices == BadIndicesRemaining) {
 467       return llvm::make_error<CodeViewError>(
 468           cv_error_code::corrupt_record, "input type graph contains cycles");
 469     }
 470   }
 471
 472   IndexMap.clear();
 473
 474   Error Ret = std::move(*LastError);
 475   LastError.reset();
 476   return Ret;
 477 }
 478
 479 Error llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestIdStream,
 480                                        TypeTableBuilder &DestTypeStream,
 481                                        SmallVectorImpl<TypeIndex> &SourceToDest,
 482                                        TypeServerHandler *Handler,
 483                                        const CVTypeArray &Types) {
 484   return TypeStreamMerger(DestIdStream, DestTypeStream, SourceToDest, Handler)
 485       .mergeStream(Types);
 486 }