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/FieldListRecordBuilder.h"
  15 #include "llvm/DebugInfo/CodeView/StreamRef.h"
  16 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
  17 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
  18 #include "llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h"
  19 #include "llvm/Support/Error.h"
  20 #include "llvm/Support/ScopedPrinter.h"
  21
  22 using namespace llvm;
  23 using namespace llvm::codeview;
  24
  25 namespace {
  26
  27 /// Implementation of CodeView type stream merging.
  28 ///
  29 /// A CodeView type stream is a series of records that reference each other
  30 /// through type indices. A type index is either "simple", meaning it is less
  31 /// than 0x1000 and refers to a builtin type, or it is complex, meaning it
  32 /// refers to a prior type record in the current stream. The type index of a
  33 /// record is equal to the number of records before it in the stream plus
  34 /// 0x1000.
  35 ///
  36 /// Type records are only allowed to use type indices smaller than their own, so
  37 /// a type stream is effectively a topologically sorted DAG. Cycles occuring in
  38 /// the type graph of the source program are resolved with forward declarations
  39 /// of composite types. This class implements the following type stream merging
  40 /// algorithm, which relies on this DAG structure:
  41 ///
  42 /// - Begin with a new empty stream, and a new empty hash table that maps from
  43 ///   type record contents to new type index.
  44 /// - For each new type stream, maintain a map from source type index to
  45 ///   destination type index.
  46 /// - For each record, copy it and rewrite its type indices to be valid in the
  47 ///   destination type stream.
  48 /// - If the new type record is not already present in the destination stream
  49 ///   hash table, append it to the destination type stream, assign it the next
  50 ///   type index, and update the two hash tables.
  51 /// - If the type record already exists in the destination stream, discard it
  52 ///   and update the type index map to forward the source type index to the
  53 ///   existing destination type index.
  54 class TypeStreamMerger : public TypeVisitorCallbacks {
  55 public:
  56   TypeStreamMerger(TypeTableBuilder &DestStream) : DestStream(DestStream) {
  57     assert(!hadError());
  58   }
  59
  60 /// TypeVisitorCallbacks overrides.
  61 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
  62   Error visit##Name(Name##Record &Record) override;
  63 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
  64   TYPE_RECORD(EnumName, EnumVal, Name)
  65 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
  66 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
  67 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
  68
  69   Error visitUnknownType(const CVRecord<TypeLeafKind> &Record) override;
  70
  71   Error visitTypeBegin(const CVRecord<TypeLeafKind> &Record) override;
  72   Error visitTypeEnd(const CVRecord<TypeLeafKind> &Record) override;
  73
  74   Error visitFieldListEnd(const CVRecord<TypeLeafKind> &Record) override;
  75
  76   bool mergeStream(const CVTypeArray &Types);
  77
  78 private:
  79   bool hadError() { return FoundBadTypeIndex; }
  80
  81   bool FoundBadTypeIndex = false;
  82
  83   FieldListRecordBuilder FieldBuilder;
  84
  85   TypeTableBuilder &DestStream;
  86
  87   size_t BeginIndexMapSize = 0;
  88
  89   /// Map from source type index to destination type index. Indexed by source
  90   /// type index minus 0x1000.
  91   SmallVector<TypeIndex, 0> IndexMap;
  92 };
  93
  94 } // end anonymous namespace
  95
  96 Error TypeStreamMerger::visitTypeBegin(const CVRecord<TypeLeafKind> &Rec) {
  97   BeginIndexMapSize = IndexMap.size();
  98   return Error::success();
  99 }
 100
 101 Error TypeStreamMerger::visitTypeEnd(const CVRecord<TypeLeafKind> &Rec) {
 102   assert(IndexMap.size() == BeginIndexMapSize + 1);
 103   return Error::success();
 104 }
 105
 106 Error TypeStreamMerger::visitFieldListEnd(const CVRecord<TypeLeafKind> &Rec) {
 107   IndexMap.push_back(DestStream.writeFieldList(FieldBuilder));
 108   FieldBuilder.reset();
 109   return Error::success();
 110 }
 111
 112 #define TYPE_RECORD(EnumName, EnumVal, Name)                                   \
 113   Error TypeStreamMerger::visit##Name(Name##Record &Record) {                  \
 114     FoundBadTypeIndex |= !Record.remapTypeIndices(IndexMap);                   \
 115     IndexMap.push_back(DestStream.write##Name(Record));                        \
 116     return Error::success();                                                   \
 117   }
 118 #define TYPE_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 119 #define MEMBER_RECORD(EnumName, EnumVal, Name)                                 \
 120   Error TypeStreamMerger::visit##Name(Name##Record &Record) {                  \
 121     FoundBadTypeIndex |= !Record.remapTypeIndices(IndexMap);                   \
 122     FieldBuilder.write##Name(Record);                                          \
 123     return Error::success();                                                   \
 124   }
 125 #define MEMBER_RECORD_ALIAS(EnumName, EnumVal, Name, AliasName)
 126 #include "llvm/DebugInfo/CodeView/TypeRecords.def"
 127
 128 Error TypeStreamMerger::visitUnknownType(const CVRecord<TypeLeafKind> &Rec) {
 129   // We failed to translate a type. Translate this index as "not translated".
 130   IndexMap.push_back(
 131       TypeIndex(SimpleTypeKind::NotTranslated, SimpleTypeMode::Direct));
 132   return llvm::make_error<CodeViewError>(cv_error_code::corrupt_record);
 133 }
 134
 135 bool TypeStreamMerger::mergeStream(const CVTypeArray &Types) {
 136   assert(IndexMap.empty());
 137   CVTypeVisitor Visitor(*this);
 138   if (auto EC = Visitor.visitTypeStream(Types)) {
 139     consumeError(std::move(EC));
 140     return false;
 141   }
 142   IndexMap.clear();
 143   return !hadError();
 144 }
 145
 146 bool llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestStream,
 147                                       const CVTypeArray &Types) {
 148   return TypeStreamMerger(DestStream).mergeStream(Types);
 149 }