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/TypeDeserializer.h"
  15 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
  16 #include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
  17 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
  18 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
  19 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
  20 #include "llvm/Support/Error.h"
  21 #include "llvm/Support/ScopedPrinter.h"
  22
  23 using namespace llvm;
  24 using namespace llvm::codeview;
  25
  26 namespace {
  27
  28 /// Implementation of CodeView type stream merging.
  29 ///
  30 /// A CodeView type stream is a series of records that reference each other
  31 /// through type indices. A type index is either "simple", meaning it is less
  32 /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
  33 /// refers to a prior type record in the current stream. The type index of a
  34 /// record is equal to the number of records before it in the stream plus
  35 /// 0x1000.
  36 ///
  37 /// Type records are only allowed to use type indices smaller than their own, so
  38 /// a type stream is effectively a topologically sorted DAG. Cycles occuring in
  39 /// the type graph of the source program are resolved with forward declarations
  40 /// of composite types. This class implements the following type stream merging
  41 /// algorithm, which relies on this DAG structure:
  42 ///
  43 /// - Begin with a new empty stream, and a new empty hash table that maps from
  44 ///   type record contents to new type index.
  45 /// - For each new type stream, maintain a map from source type index to
  46 ///   destination type index.
  47 /// - For each record, copy it and rewrite its type indices to be valid in the
  48 ///   destination type stream.
  49 /// - If the new type record is not already present in the destination stream
  50 ///   hash table, append it to the destination type stream, assign it the next
  51 ///   type index, and update the two hash tables.
  52 /// - If the type record already exists in the destination stream, discard it
  53 ///   and update the type index map to forward the source type index to the
  54 ///   existing destination type index.
  55 ///
  56 /// As an additional complication, type stream merging actually produces two
  57 /// streams: an item (or IPI) stream and a type stream, as this is what is
  58 /// actually stored in the final PDB. We choose which records go where by
  59 /// looking at the record kind.
  60 class TypeStreamMerger : public TypeVisitorCallbacks {
  61 public:
  62   explicit TypeStreamMerger(SmallVectorImpl<TypeIndex> &SourceToDest,
  63                             TypeServerHandler *Handler)
  64       : Handler(Handler), IndexMap(SourceToDest) {
  65     SourceToDest.clear();
  66   }
  67
  68   static const TypeIndex Untranslated;
  69
  70   Error visitTypeBegin(CVType &Record) override;
  71   Error visitTypeEnd(CVType &Record) override;
  72
  73   Error mergeTypesAndIds(TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
  74     const CVTypeArray &IdsAndTypes);
  75   Error mergeIdRecords(TypeTableBuilder &Dest,
  76                        ArrayRef<TypeIndex> TypeSourceToDest,
  77     const CVTypeArray &Ids);
  78   Error mergeTypeRecords(TypeTableBuilder &Dest, const CVTypeArray &Types);
  79
  80 private:
  81   Error doit(const CVTypeArray &Types);
  82
  83   void addMapping(TypeIndex Idx);
  84
  85   bool remapTypeIndex(TypeIndex &Idx);
  86   bool remapItemIndex(TypeIndex &Idx);
  87
  88   bool remapIndices(RemappedType &Record, ArrayRef<TiReference> Refs) {
  89     auto OriginalData = Record.OriginalRecord.content();
  90     bool Success = true;
  91     for (auto &Ref : Refs) {
  92       uint32_t Offset = Ref.Offset;
  93       ArrayRef<uint8_t> Bytes =
  94           OriginalData.slice(Ref.Offset, sizeof(TypeIndex));
  95       ArrayRef<TypeIndex> TIs(reinterpret_cast<const TypeIndex *>(Bytes.data()),
  96                               Ref.Count);
  97       for (auto TI : TIs) {
  98         TypeIndex NewTI = TI;
  99         bool ThisSuccess = (Ref.Kind == TiRefKind::IndexRef)
 100                                ? remapItemIndex(NewTI)
 101                                : remapTypeIndex(NewTI);
 102         if (ThisSuccess && NewTI != TI)
 103           Record.Mappings.emplace_back(Offset, NewTI);
 104         Offset += sizeof(TypeIndex);
 105         Success &= ThisSuccess;
 106       }
 107     }
 108     return Success;
 109   }
 110
 111   bool remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map);
 112
 113   size_t slotForIndex(TypeIndex Idx) const {
 114     assert(!Idx.isSimple() && "simple type indices have no slots");
 115     return Idx.getIndex() - TypeIndex::FirstNonSimpleIndex;
 116   }
 117
 118   Error errorCorruptRecord() const {
 119     return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
 120   }
 121
 122   Error writeRecord(TypeTableBuilder &Dest, const RemappedType &Record,
 123                     bool RemapSuccess) {
 124     TypeIndex DestIdx = Untranslated;
 125     if (RemapSuccess)
 126       DestIdx = Dest.writeSerializedRecord(Record);
 127     addMapping(DestIdx);
 128     return Error::success();
 129   }
 130
 131   Error writeTypeRecord(const CVType &Record) {
 132     TypeIndex DestIdx =
 133         DestTypeStream->writeSerializedRecord(Record.RecordData);
 134     addMapping(DestIdx);
 135     return Error::success();
 136   }
 137
 138   Error writeTypeRecord(const RemappedType &Record, bool RemapSuccess) {
 139     return writeRecord(*DestTypeStream, Record, RemapSuccess);
 140   }
 141
 142   Error writeIdRecord(const RemappedType &Record, bool RemapSuccess) {
 143     return writeRecord(*DestIdStream, Record, RemapSuccess);
 144   }
 145
 146   Optional<Error> LastError;
 147
 148   bool IsSecondPass = false;
 149
 150   unsigned NumBadIndices = 0;
 151
 152   TypeIndex CurIndex{TypeIndex::FirstNonSimpleIndex};
 153
 154   TypeTableBuilder *DestIdStream = nullptr;
 155   TypeTableBuilder *DestTypeStream = nullptr;
 156   TypeServerHandler *Handler = nullptr;
 157
 158   // If we're only mapping id records, this array contains the mapping for
 159   // type records.
 160   ArrayRef<TypeIndex> TypeLookup;
 161
 162   /// Map from source type index to destination type index. Indexed by source
 163   /// type index minus 0x1000.
 164   SmallVectorImpl<TypeIndex> &IndexMap;
 165 };
 166
 167 } // end anonymous namespace
 168
 169 const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);
 170
 171 Error TypeStreamMerger::visitTypeBegin(CVType &Rec) {
 172   RemappedType R(Rec);
 173   SmallVector<TiReference, 32> Refs;
 174   discoverTypeIndices(Rec.RecordData, Refs);
 175   bool Success = remapIndices(R, Refs);
 176   switch (Rec.kind()) {
 177   case TypeLeafKind::LF_FUNC_ID:
 178   case TypeLeafKind::LF_MFUNC_ID:
 179   case TypeLeafKind::LF_STRING_ID:
 180   case TypeLeafKind::LF_SUBSTR_LIST:
 181   case TypeLeafKind::LF_BUILDINFO:
 182   case TypeLeafKind::LF_UDT_SRC_LINE:
 183   case TypeLeafKind::LF_UDT_MOD_SRC_LINE:
 184     return writeIdRecord(R, Success);
 185   default:
 186     return writeTypeRecord(R, Success);
 187   }
 188   return Error::success();
 189 }
 190
 191 Error TypeStreamMerger::visitTypeEnd(CVType &Rec) {
 192   ++CurIndex;
 193   if (!IsSecondPass)
 194     assert(IndexMap.size() == slotForIndex(CurIndex) &&
 195            "visitKnownRecord should add one index map entry");
 196   return Error::success();
 197 }
 198
 199 void TypeStreamMerger::addMapping(TypeIndex Idx) {
 200   if (!IsSecondPass) {
 201     assert(IndexMap.size() == slotForIndex(CurIndex) &&
 202            "visitKnownRecord should add one index map entry");
 203     IndexMap.push_back(Idx);
 204   } else {
 205     assert(slotForIndex(CurIndex) < IndexMap.size());
 206     IndexMap[slotForIndex(CurIndex)] = Idx;
 207   }
 208 }
 209
 210 bool TypeStreamMerger::remapIndex(TypeIndex &Idx, ArrayRef<TypeIndex> Map) {
 211   // Simple types are unchanged.
 212   if (Idx.isSimple())
 213     return true;
 214
 215   // Check if this type index refers to a record we've already translated
 216   // successfully. If it refers to a type later in the stream or a record we
 217   // had to defer, defer it until later pass.
 218   unsigned MapPos = slotForIndex(Idx);
 219   if (MapPos < Map.size() && Map[MapPos] != Untranslated) {
 220     Idx = Map[MapPos];
 221     return true;
 222   }
 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 bool TypeStreamMerger::remapTypeIndex(TypeIndex &Idx) {
 241   // If we're mapping a pure index stream, then IndexMap only contains mappings
 242   // from OldIdStream -> NewIdStream, in which case we will need to use the
 243   // special mapping from OldTypeStream -> NewTypeStream which was computed
 244   // externally.  Regardless, we use this special map if and only if we are
 245   // doing an id-only mapping.
 246   if (DestTypeStream == nullptr)
 247     return remapIndex(Idx, TypeLookup);
 248
 249   assert(TypeLookup.empty());
 250   return remapIndex(Idx, IndexMap);
 251 }
 252
 253 bool TypeStreamMerger::remapItemIndex(TypeIndex &Idx) {
 254   assert(DestIdStream);
 255   return remapIndex(Idx, IndexMap);
 256 }
 257
 258 Error TypeStreamMerger::mergeTypeRecords(TypeTableBuilder &Dest,
 259   const CVTypeArray &Types) {
 260   DestTypeStream = &Dest;
 261
 262   return doit(Types);
 263 }
 264
 265 Error TypeStreamMerger::mergeIdRecords(TypeTableBuilder &Dest,
 266                                        ArrayRef<TypeIndex> TypeSourceToDest,
 267   const CVTypeArray &Ids) {
 268   DestIdStream = &Dest;
 269   TypeLookup = TypeSourceToDest;
 270
 271   return doit(Ids);
 272 }
 273
 274 Error TypeStreamMerger::mergeTypesAndIds(TypeTableBuilder &DestIds,
 275                                          TypeTableBuilder &DestTypes,
 276   const CVTypeArray &IdsAndTypes) {
 277   DestIdStream = &DestIds;
 278   DestTypeStream = &DestTypes;
 279
 280   return doit(IdsAndTypes);
 281 }
 282
 283 Error TypeStreamMerger::doit(const CVTypeArray &Types) {
 284   LastError = Error::success();
 285
 286   // We don't want to deserialize records.  I guess this flag is poorly named,
 287   // but it really means "Don't deserialize records before switching on the
 288   // concrete type.
 289   // FIXME: We can probably get even more speed here if we don't use the visitor
 290   // pipeline here, but instead write the switch ourselves.  I don't think it
 291   // would buy us much since it's already pretty fast, but it's probably worth
 292   // a few cycles.
 293   if (auto EC =
 294           codeview::visitTypeStream(Types, *this, VDS_BytesExternal, Handler))
 295     return EC;
 296
 297   // If we found bad indices but no other errors, try doing another pass and see
 298   // if we can resolve the indices that weren't in the map on the first pass.
 299   // This may require multiple passes, but we should always make progress. MASM
 300   // is the only known CodeView producer that makes type streams that aren't
 301   // topologically sorted. The standard library contains MASM-produced objects,
 302   // so this is important to handle correctly, but we don't have to be too
 303   // efficient. MASM type streams are usually very small.
 304   while (!*LastError && NumBadIndices > 0) {
 305     unsigned BadIndicesRemaining = NumBadIndices;
 306     IsSecondPass = true;
 307     NumBadIndices = 0;
 308     CurIndex = TypeIndex(TypeIndex::FirstNonSimpleIndex);
 309
 310     if (auto EC =
 311             codeview::visitTypeStream(Types, *this, VDS_BytesExternal, Handler))
 312       return EC;
 313
 314     assert(NumBadIndices <= BadIndicesRemaining &&
 315            "second pass found more bad indices");
 316     if (!*LastError && NumBadIndices == BadIndicesRemaining) {
 317       return llvm::make_error<CodeViewError>(
 318           cv_error_code::corrupt_record, "input type graph contains cycles");
 319     }
 320   }
 321
 322   Error Ret = std::move(*LastError);
 323   LastError.reset();
 324   return Ret;
 325 }
 326
 327 Error llvm::codeview::mergeTypeRecords(TypeTableBuilder &Dest,
 328                                        SmallVectorImpl<TypeIndex> &SourceToDest,
 329                                        TypeServerHandler *Handler,
 330   const CVTypeArray &Types) {
 331   TypeStreamMerger M(SourceToDest, Handler);
 332   return M.mergeTypeRecords(Dest, Types);
 333 }
 334
 335 Error llvm::codeview::mergeIdRecords(TypeTableBuilder &Dest,
 336                                      ArrayRef<TypeIndex> TypeSourceToDest,
 337                                      SmallVectorImpl<TypeIndex> &SourceToDest,
 338   const CVTypeArray &Ids) {
 339   TypeStreamMerger M(SourceToDest, nullptr);
 340   return M.mergeIdRecords(Dest, TypeSourceToDest, Ids);
 341 }
 342
 343 Error llvm::codeview::mergeTypeAndIdRecords(
 344     TypeTableBuilder &DestIds, TypeTableBuilder &DestTypes,
 345     SmallVectorImpl<TypeIndex> &SourceToDest, TypeServerHandler *Handler,
 346   const CVTypeArray &IdsAndTypes) {
 347
 348   TypeStreamMerger M(SourceToDest, Handler);
 349   return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes);
 350 }