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