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 
19 using namespace llvm;
20 using namespace llvm::pdb;
21 using namespace llvm::codeview;
22 
23 // LazyRandomTypeCollection doesn't appear to expose the number of records, so
24 // just iterate up front to find out.
25 static uint32_t getNumRecordsInCollection(LazyRandomTypeCollection &Types) {
26   uint32_t NumTypes = 0;
27   for (std::optional<TypeIndex> TI = Types.getFirst(); TI;
28        TI = Types.getNext(*TI))
29     ++NumTypes;
30   return NumTypes;
31 }
32 
33 TypeReferenceTracker::TypeReferenceTracker(InputFile &File)
34     : File(File), Types(File.types()),
35       Ids(File.isPdb() ? &File.ids() : nullptr) {
36   NumTypeRecords = getNumRecordsInCollection(Types);
37   TypeReferenced.resize(NumTypeRecords, false);
38 
39   // If this is a PDB, ids are stored separately, so make a separate bit vector.
40   if (Ids) {
41     NumIdRecords = getNumRecordsInCollection(*Ids);
42     IdReferenced.resize(NumIdRecords, 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(File.pdb().getPDBTpiStream());
49     Tpi->buildHashMap();
50   }
51 }
52 
53 void TypeReferenceTracker::mark() {
54   // Walk type roots:
55   // - globals
56   // - modi symbols
57   // - LF_UDT_MOD_SRC_LINE? VC always links these in.
58   for (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(Reader.readArray(Symbols, Reader.getLength()));
69         for (const CVSymbol &S : Symbols)
70           addTypeRefsFromSymbol(S);
71       }
72     } else if (SG.hasDebugStream()) {
73       for (const CVSymbol &S : SG.getPdbModuleStream().getSymbolArray())
74         addTypeRefsFromSymbol(S);
75     }
76   }
77 
78   // Walk globals and mark types referenced from globals.
79   if (File.isPdb() && File.pdb().hasPDBGlobalsStream()) {
80     SymbolStream &SymStream = cantFail(File.pdb().getPDBSymbolStream());
81     GlobalsStream &GS = cantFail(File.pdb().getPDBGlobalsStream());
82     for (uint32_t PubSymOff : GS.getGlobalsTable()) {
83       CVSymbol Sym = SymStream.readRecord(PubSymOff);
84       addTypeRefsFromSymbol(Sym);
85     }
86   }
87 
88   // FIXME: Should we walk Ids?
89 }
90 
91 void 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(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({RefKind, RefTI});
101 }
102 
103 void TypeReferenceTracker::addTypeRefsFromSymbol(const CVSymbol &Sym) {
104   SmallVector<TiReference, 4> DepList;
105   // FIXME: Check for failure.
106   discoverTypeIndicesInSymbol(Sym, DepList);
107   addReferencedTypes(Sym.content(), DepList);
108   markReferencedTypes();
109 }
110 
111 void 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(Ref.Offset).take_front(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(Ref.Kind, RefTI);
125   }
126 }
127 
128 void TypeReferenceTracker::markReferencedTypes() {
129   while (!RefWorklist.empty()) {
130     TiRefKind RefKind;
131     TypeIndex RefTI;
132     std::tie(RefKind, RefTI) = RefWorklist.pop_back_val();
133     std::optional<CVType> Rec = (Ids && RefKind == TiRefKind::IndexRef)
134                                     ? Ids->tryGetType(RefTI)
135                                     : Types.tryGetType(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(*Rec, DepList);
142     addReferencedTypes(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(TiRefKind::TypeRef,
158                       cantFail(Tpi->findFullDeclForForwardRef(RefTI)));
159         break;
160       }
161     }
162   }
163 }
164