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:
TypeStreamMerger(TypeTableBuilder & DestStream)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:
hadError()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
visitTypeBegin(const CVRecord<TypeLeafKind> & Rec)96 Error TypeStreamMerger::visitTypeBegin(const CVRecord<TypeLeafKind> &Rec) {
97 BeginIndexMapSize = IndexMap.size();
98 return Error::success();
99 }
100
visitTypeEnd(const CVRecord<TypeLeafKind> & Rec)101 Error TypeStreamMerger::visitTypeEnd(const CVRecord<TypeLeafKind> &Rec) {
102 assert(IndexMap.size() == BeginIndexMapSize + 1);
103 return Error::success();
104 }
105
visitFieldListEnd(const CVRecord<TypeLeafKind> & Rec)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
visitUnknownType(const CVRecord<TypeLeafKind> & Rec)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
mergeStream(const CVTypeArray & Types)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
mergeTypeStreams(TypeTableBuilder & DestStream,const CVTypeArray & Types)146 bool llvm::codeview::mergeTypeStreams(TypeTableBuilder &DestStream,
147 const CVTypeArray &Types) {
148 return TypeStreamMerger(DestStream).mergeStream(Types);
149 }
150