1//===- TypeReferenceTracker.cpp ------------------------------- *- C++ --*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "TypeReferenceTracker.h"
10
11#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
12#include "llvm/DebugInfo/PDB/Native/GlobalsStream.h"
13#include "llvm/DebugInfo/PDB/Native/NativeSession.h"
14#include "llvm/DebugInfo/PDB/Native/PDBFile.h"
15#include "llvm/DebugInfo/PDB/Native/SymbolStream.h"
16#include "llvm/DebugInfo/PDB/Native/TpiStream.h"
17#include "llvm/Object/COFF.h"
18
19using namespace llvm;
20using namespace llvm::pdb;
21using namespace llvm::codeview;
22
23// LazyRandomTypeCollection doesn't appear to expose the number of records, so
24// just iterate up front to find out.
25static uint32_t getNumRecordsInCollection(LazyRandomTypeCollection &Types) {
26 uint32_t NumTypes = 0;
27 for (std::optional<TypeIndex> TI = Types.getFirst(); TI;
28 TI = Types.getNext(Prev: *TI))
29 ++NumTypes;
30 return NumTypes;
31}
32
33TypeReferenceTracker::TypeReferenceTracker(InputFile &File)
34 : File(File), Types(File.types()),
35 Ids(File.isPdb() ? &File.ids() : nullptr) {
36 NumTypeRecords = getNumRecordsInCollection(Types);
37 TypeReferenced.resize(N: NumTypeRecords, t: false);
38
39 // If this is a PDB, ids are stored separately, so make a separate bit vector.
40 if (Ids) {
41 NumIdRecords = getNumRecordsInCollection(Types&: *Ids);
42 IdReferenced.resize(N: NumIdRecords, t: false);
43 }
44
45 // Get the TpiStream pointer for forward decl resolution if this is a pdb.
46 // Build the hash map to enable resolving forward decls.
47 if (File.isPdb()) {
48 Tpi = &cantFail(ValOrErr: File.pdb().getPDBTpiStream());
49 Tpi->buildHashMap();
50 }
51}
52
53void TypeReferenceTracker::mark() {
54 // Walk type roots:
55 // - globals
56 // - modi symbols
57 // - LF_UDT_MOD_SRC_LINE? VC always links these in.
58 for (const SymbolGroup &SG : File.symbol_groups()) {
59 if (File.isObj()) {
60 for (const auto &SS : SG.getDebugSubsections()) {
61 // FIXME: Are there other type-referencing subsections? Inlinees?
62 // Probably for IDs.
63 if (SS.kind() != DebugSubsectionKind::Symbols)
64 continue;
65
66 CVSymbolArray Symbols;
67 BinaryStreamReader Reader(SS.getRecordData());
68 cantFail(Err: Reader.readArray(Array&: Symbols, Size: Reader.getLength()));
69 for (const CVSymbol &S : Symbols)
70 addTypeRefsFromSymbol(Sym: S);
71 }
72 } else if (SG.hasDebugStream()) {
73 for (const CVSymbol &S : SG.getPdbModuleStream().getSymbolArray())
74 addTypeRefsFromSymbol(Sym: S);
75 }
76 }
77
78 // Walk globals and mark types referenced from globals.
79 if (File.isPdb() && File.pdb().hasPDBGlobalsStream()) {
80 SymbolStream &SymStream = cantFail(ValOrErr: File.pdb().getPDBSymbolStream());
81 GlobalsStream &GS = cantFail(ValOrErr: File.pdb().getPDBGlobalsStream());
82 for (uint32_t PubSymOff : GS.getGlobalsTable()) {
83 CVSymbol Sym = SymStream.readRecord(Offset: PubSymOff);
84 addTypeRefsFromSymbol(Sym);
85 }
86 }
87
88 // FIXME: Should we walk Ids?
89}
90
91void TypeReferenceTracker::addOneTypeRef(TiRefKind RefKind, TypeIndex RefTI) {
92 // If it's simple or already seen, no need to add to work list.
93 BitVector &TypeOrIdReferenced =
94 (Ids && RefKind == TiRefKind::IndexRef) ? IdReferenced : TypeReferenced;
95 if (RefTI.isSimple() || TypeOrIdReferenced.test(Idx: RefTI.toArrayIndex()))
96 return;
97
98 // Otherwise, mark it seen and add it to the work list.
99 TypeOrIdReferenced.set(RefTI.toArrayIndex());
100 RefWorklist.push_back(Elt: {RefKind, RefTI});
101}
102
103void TypeReferenceTracker::addTypeRefsFromSymbol(const CVSymbol &Sym) {
104 SmallVector<TiReference, 4> DepList;
105 // FIXME: Check for failure.
106 discoverTypeIndicesInSymbol(Symbol: Sym, Refs&: DepList);
107 addReferencedTypes(RecData: Sym.content(), Refs: DepList);
108 markReferencedTypes();
109}
110
111void TypeReferenceTracker::addReferencedTypes(ArrayRef<uint8_t> RecData,
112 ArrayRef<TiReference> DepList) {
113 for (const auto &Ref : DepList) {
114 // FIXME: Report OOB slice instead of truncating.
115 ArrayRef<uint8_t> ByteSlice =
116 RecData.drop_front(N: Ref.Offset).take_front(N: 4 * Ref.Count);
117 ArrayRef<TypeIndex> TIs(
118 reinterpret_cast<const TypeIndex *>(ByteSlice.data()),
119 ByteSlice.size() / 4);
120
121 // If this is a PDB and this is an item reference, track it in the IPI
122 // bitvector. Otherwise, it's a type ref, or there is only one stream.
123 for (TypeIndex RefTI : TIs)
124 addOneTypeRef(RefKind: Ref.Kind, RefTI);
125 }
126}
127
128void TypeReferenceTracker::markReferencedTypes() {
129 while (!RefWorklist.empty()) {
130 TiRefKind RefKind;
131 TypeIndex RefTI;
132 std::tie(args&: RefKind, args&: RefTI) = RefWorklist.pop_back_val();
133 std::optional<CVType> Rec = (Ids && RefKind == TiRefKind::IndexRef)
134 ? Ids->tryGetType(Index: RefTI)
135 : Types.tryGetType(Index: RefTI);
136 if (!Rec)
137 continue; // FIXME: Report a reference to a non-existant type.
138
139 SmallVector<TiReference, 4> DepList;
140 // FIXME: Check for failure.
141 discoverTypeIndices(Type: *Rec, Refs&: DepList);
142 addReferencedTypes(RecData: Rec->content(), DepList);
143
144 // If this is a tag kind and this is a PDB input, mark the complete type as
145 // referenced.
146 // FIXME: This limitation makes this feature somewhat useless on object file
147 // inputs.
148 if (Tpi) {
149 switch (Rec->kind()) {
150 default:
151 break;
152 case LF_CLASS:
153 case LF_INTERFACE:
154 case LF_STRUCTURE:
155 case LF_UNION:
156 case LF_ENUM:
157 addOneTypeRef(RefKind: TiRefKind::TypeRef,
158 RefTI: cantFail(ValOrErr: Tpi->findFullDeclForForwardRef(ForwardRefTI: RefTI)));
159 break;
160 }
161 }
162 }
163}
164