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 } 150
