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 (Optional<TypeIndex> TI = Types.getFirst(); TI; TI = Types.getNext(*TI))
28     ++NumTypes;
29   return NumTypes;
30 }
31 
32 TypeReferenceTracker::TypeReferenceTracker(InputFile &File)
33     : File(File), Types(File.types()),
34       Ids(File.isPdb() ? &File.ids() : nullptr) {
35   NumTypeRecords = getNumRecordsInCollection(Types);
36   TypeReferenced.resize(NumTypeRecords, false);
37 
38   // If this is a PDB, ids are stored separately, so make a separate bit vector.
39   if (Ids) {
40     NumIdRecords = getNumRecordsInCollection(*Ids);
41     IdReferenced.resize(NumIdRecords, false);
42   }
43 
44   // Get the TpiStream pointer for forward decl resolution if this is a pdb.
45   // Build the hash map to enable resolving forward decls.
46   if (File.isPdb()) {
47     Tpi = &cantFail(File.pdb().getPDBTpiStream());
48     Tpi->buildHashMap();
49   }
50 }
51 
52 void TypeReferenceTracker::mark() {
53   // Walk type roots:
54   // - globals
55   // - modi symbols
56   // - LF_UDT_MOD_SRC_LINE? VC always links these in.
57   for (SymbolGroup SG : File.symbol_groups()) {
58     if (File.isObj()) {
59       for (const auto &SS : SG.getDebugSubsections()) {
60         // FIXME: Are there other type-referencing subsections? Inlinees?
61         // Probably for IDs.
62         if (SS.kind() != DebugSubsectionKind::Symbols)
63           continue;
64 
65         CVSymbolArray Symbols;
66         BinaryStreamReader Reader(SS.getRecordData());
67         cantFail(Reader.readArray(Symbols, Reader.getLength()));
68         for (const CVSymbol &S : Symbols)
69           addTypeRefsFromSymbol(S);
70       }
71     } else if (SG.hasDebugStream()) {
72       for (const CVSymbol &S : SG.getPdbModuleStream().getSymbolArray())
73         addTypeRefsFromSymbol(S);
74     }
75   }
76 
77   // Walk globals and mark types referenced from globals.
78   if (File.isPdb() && File.pdb().hasPDBGlobalsStream()) {
79     SymbolStream &SymStream = cantFail(File.pdb().getPDBSymbolStream());
80     GlobalsStream &GS = cantFail(File.pdb().getPDBGlobalsStream());
81     for (uint32_t PubSymOff : GS.getGlobalsTable()) {
82       CVSymbol Sym = SymStream.readRecord(PubSymOff);
83       addTypeRefsFromSymbol(Sym);
84     }
85   }
86 
87   // FIXME: Should we walk Ids?
88 }
89 
90 void TypeReferenceTracker::addOneTypeRef(TiRefKind RefKind, TypeIndex RefTI) {
91   // If it's simple or already seen, no need to add to work list.
92   BitVector &TypeOrIdReferenced =
93       (Ids && RefKind == TiRefKind::IndexRef) ? IdReferenced : TypeReferenced;
94   if (RefTI.isSimple() || TypeOrIdReferenced.test(RefTI.toArrayIndex()))
95     return;
96 
97   // Otherwise, mark it seen and add it to the work list.
98   TypeOrIdReferenced.set(RefTI.toArrayIndex());
99   RefWorklist.push_back({RefKind, RefTI});
100 }
101 
102 void TypeReferenceTracker::addTypeRefsFromSymbol(const CVSymbol &Sym) {
103   SmallVector<TiReference, 4> DepList;
104   // FIXME: Check for failure.
105   discoverTypeIndicesInSymbol(Sym, DepList);
106   addReferencedTypes(Sym.content(), DepList);
107   markReferencedTypes();
108 }
109 
110 void TypeReferenceTracker::addReferencedTypes(ArrayRef<uint8_t> RecData,
111                                               ArrayRef<TiReference> DepList) {
112   for (const auto &Ref : DepList) {
113     // FIXME: Report OOB slice instead of truncating.
114     ArrayRef<uint8_t> ByteSlice =
115         RecData.drop_front(Ref.Offset).take_front(4 * Ref.Count);
116     ArrayRef<TypeIndex> TIs(
117         reinterpret_cast<const TypeIndex *>(ByteSlice.data()),
118         ByteSlice.size() / 4);
119 
120     // If this is a PDB and this is an item reference, track it in the IPI
121     // bitvector. Otherwise, it's a type ref, or there is only one stream.
122     for (TypeIndex RefTI : TIs)
123       addOneTypeRef(Ref.Kind, RefTI);
124   }
125 }
126 
127 void TypeReferenceTracker::markReferencedTypes() {
128   while (!RefWorklist.empty()) {
129     TiRefKind RefKind;
130     TypeIndex RefTI;
131     std::tie(RefKind, RefTI) = RefWorklist.pop_back_val();
132     Optional<CVType> Rec = (Ids && RefKind == TiRefKind::IndexRef)
133                                ? Ids->tryGetType(RefTI)
134                                : Types.tryGetType(RefTI);
135     if (!Rec)
136       continue; // FIXME: Report a reference to a non-existant type.
137 
138     SmallVector<TiReference, 4> DepList;
139     // FIXME: Check for failure.
140     discoverTypeIndices(*Rec, DepList);
141     addReferencedTypes(Rec->content(), DepList);
142 
143     // If this is a tag kind and this is a PDB input, mark the complete type as
144     // referenced.
145     // FIXME: This limitation makes this feature somewhat useless on object file
146     // inputs.
147     if (Tpi) {
148       switch (Rec->kind()) {
149       default:
150         break;
151       case LF_CLASS:
152       case LF_INTERFACE:
153       case LF_STRUCTURE:
154       case LF_UNION:
155       case LF_ENUM:
156         addOneTypeRef(TiRefKind::TypeRef,
157                       cantFail(Tpi->findFullDeclForForwardRef(RefTI)));
158         break;
159       }
160     }
161   }
162 }
163