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 22using namespace llvm; 23using namespace llvm::codeview; 24 25namespace { 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. 54class TypeStreamMerger : public TypeVisitorCallbacks { 55public: 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 78private: 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 96Error TypeStreamMerger::visitTypeBegin(const CVRecord<TypeLeafKind> &Rec) { 97 BeginIndexMapSize = IndexMap.size(); 98 return Error::success(); 99} 100 101Error TypeStreamMerger::visitTypeEnd(const CVRecord<TypeLeafKind> &Rec) { 102 assert(IndexMap.size() == BeginIndexMapSize + 1); 103 return Error::success(); 104} 105 106Error 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 128Error 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 135bool 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 146bool llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestStream, 147 const CVTypeArray &Types) { 148 return TypeStreamMerger(DestStream).mergeStream(Types); 149} 150