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/TypeRecord.h"
  17 #include "llvm/DebugInfo/CodeView/TypeTableBuilder.h"
  18 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.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 class TypeStreamMerger : public TypeVisitorCallbacks {
  56 public:
  57   TypeStreamMerger(TypeTableBuilder &DestStream)
  58       : DestStream(DestStream), FieldListBuilder(DestStream) {
  59     assert(!hadError());
  60   }
  61
  62 /// TypeVisitorCallbacks overrides.
  63 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
  64   Error visitKnownRecord(CVType &CVR, Name##Record &Record) override;
  65 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
  66   Error visitKnownMember(CVMemberRecord &CVR, Name##Record &Record) override;
  67 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
  68 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
  69 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
  70
  71   Error visitUnknownType(CVType &Record) override;
  72
  73   Error visitTypeBegin(CVType &Record) override;
  74   Error visitTypeEnd(CVType &Record) override;
  75   Error visitMemberEnd(CVMemberRecord &Record) override;
  76
  77   bool mergeStream(const CVTypeArray &Types);
  78
  79 private:
  80   template <typename RecordType>
  81   Error visitKnownRecordImpl(RecordType &Record) {
  82     FoundBadTypeIndex |= !Record.remapTypeIndices(IndexMap);
  83     IndexMap.push_back(DestStream.writeKnownType(Record));
  84     return Error::success();
  85   }
  86
  87   Error visitKnownRecordImpl(FieldListRecord &Record) {
  88     CVTypeVisitor Visitor(*this);
  89
  90     if (auto EC = Visitor.visitFieldListMemberStream(Record.Data))
  91       return EC;
  92     return Error::success();
  93   }
  94
  95   template <typename RecordType>
  96   Error visitKnownMemberRecordImpl(RecordType &Record) {
  97     FoundBadTypeIndex |= !Record.remapTypeIndices(IndexMap);
  98     FieldListBuilder.writeMemberType(Record);
  99     return Error::success();
 100   }
 101
 102   bool hadError() { return FoundBadTypeIndex; }
 103
 104   bool FoundBadTypeIndex = false;
 105
 106   BumpPtrAllocator Allocator;
 107
 108   TypeTableBuilder &DestStream;
 109   FieldListRecordBuilder FieldListBuilder;
 110
 111   bool IsInFieldList{false};
 112   size_t BeginIndexMapSize = 0;
 113
 114   /// Map from source type index to destination type index. Indexed by source
 115   /// type index minus 0x1000.
 116   SmallVector<TypeIndex, 0> IndexMap;
 117 };
 118
 119 } // end anonymous namespace
 120
 121 Error TypeStreamMerger::visitTypeBegin(CVRecord<TypeLeafKind> &Rec) {
 122   if (Rec.Type == TypeLeafKind::LF_FIELDLIST) {
 123     assert(!IsInFieldList);
 124     IsInFieldList = true;
 125     FieldListBuilder.begin();
 126   } else
 127     BeginIndexMapSize = IndexMap.size();
 128   return Error::success();
 129 }
 130
 131 Error TypeStreamMerger::visitTypeEnd(CVRecord<TypeLeafKind> &Rec) {
 132   if (Rec.Type == TypeLeafKind::LF_FIELDLIST) {
 133     TypeIndex Index = FieldListBuilder.end();
 134     IndexMap.push_back(Index);
 135     IsInFieldList = false;
 136   }
 137   return Error::success();
 138 }
 139
 140 Error TypeStreamMerger::visitMemberEnd(CVMemberRecord &Rec) {
 141   assert(IndexMap.size() == BeginIndexMapSize + 1);
 142   return Error::success();
 143 }
 144
 145 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
 146   Error TypeStreamMerger::visitKnownRecord(CVType &CVR,                        \
 147                                            Name##Record &Record) {             \
 148     return visitKnownRecordImpl(Record);                                       \
 149   }
 150 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 151 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
 152   Error TypeStreamMerger::visitKnownMember(CVMemberRecord &CVR,                \
 153                                            Name##Record &Record) {             \
 154     return visitKnownMemberRecordImpl(Record);                                 \
 155   }
 156 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 157 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
 158
 159 Error TypeStreamMerger::visitUnknownType(CVType &Rec) {
 160   // We failed to translate a type. Translate this index as "not translated".
 161   IndexMap.push_back(
 162       TypeIndex(SimpleTypeKind::NotTranslated, SimpleTypeMode::Direct));
 163   return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
 164 }
 165
 166 bool TypeStreamMerger::mergeStream(const CVTypeArray &Types) {
 167   assert(IndexMap.empty());
 168   TypeVisitorCallbackPipeline Pipeline;
 169
 170   TypeDeserializer Deserializer;
 171   Pipeline.addCallbackToPipeline(Deserializer);
 172   Pipeline.addCallbackToPipeline(*this);
 173
 174   CVTypeVisitor Visitor(Pipeline);
 175
 176   if (auto EC = Visitor.visitTypeStream(Types)) {
 177     consumeError(std::move(EC));
 178     return false;
 179   }
 180   IndexMap.clear();
 181   return !hadError();
 182 }
 183
 184 bool llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestStream,
 185                                       const CVTypeArray &Types) {
 186   return TypeStreamMerger(DestStream).mergeStream(Types);
 187 }