1351278Sdim//===- TypeReferenceTracker.cpp ------------------------------- *- C++ --*-===// 2351278Sdim// 3351278Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351278Sdim// See https://llvm.org/LICENSE.txt for license information. 5351278Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351278Sdim// 7351278Sdim//===----------------------------------------------------------------------===// 8351278Sdim 9351278Sdim#include "TypeReferenceTracker.h" 10351278Sdim 11351278Sdim#include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h" 12351278Sdim#include "llvm/DebugInfo/PDB/Native/PDBFile.h" 13351278Sdim#include "llvm/DebugInfo/PDB/Native/TpiStream.h" 14351278Sdim#include "llvm/DebugInfo/PDB/Native/GlobalsStream.h" 15351278Sdim#include "llvm/DebugInfo/PDB/Native/SymbolStream.h" 16351278Sdim 17351278Sdimusing namespace llvm; 18351278Sdimusing namespace llvm::pdb; 19351278Sdimusing namespace llvm::codeview; 20351278Sdim 21351278Sdim// LazyRandomTypeCollection doesn't appear to expose the number of records, so 22351278Sdim// just iterate up front to find out. 23351278Sdimstatic uint32_t getNumRecordsInCollection(LazyRandomTypeCollection &Types) { 24351278Sdim uint32_t NumTypes = 0; 25351278Sdim for (Optional<TypeIndex> TI = Types.getFirst(); TI; TI = Types.getNext(*TI)) 26351278Sdim ++NumTypes; 27351278Sdim return NumTypes; 28351278Sdim} 29351278Sdim 30351278SdimTypeReferenceTracker::TypeReferenceTracker(InputFile &File) 31351278Sdim : File(File), Types(File.types()), 32351278Sdim Ids(File.isPdb() ? &File.ids() : nullptr) { 33351278Sdim NumTypeRecords = getNumRecordsInCollection(Types); 34351278Sdim TypeReferenced.resize(NumTypeRecords, false); 35351278Sdim 36351278Sdim // If this is a PDB, ids are stored separately, so make a separate bit vector. 37351278Sdim if (Ids) { 38351278Sdim NumIdRecords = getNumRecordsInCollection(*Ids); 39351278Sdim IdReferenced.resize(NumIdRecords, false); 40351278Sdim } 41351278Sdim 42351278Sdim // Get the TpiStream pointer for forward decl resolution if this is a pdb. 43351278Sdim // Build the hash map to enable resolving forward decls. 44351278Sdim if (File.isPdb()) { 45351278Sdim Tpi = &cantFail(File.pdb().getPDBTpiStream()); 46351278Sdim Tpi->buildHashMap(); 47351278Sdim } 48351278Sdim} 49351278Sdim 50351278Sdimvoid TypeReferenceTracker::mark() { 51351278Sdim // Walk type roots: 52351278Sdim // - globals 53351278Sdim // - modi symbols 54351278Sdim // - LF_UDT_MOD_SRC_LINE? VC always links these in. 55351278Sdim for (SymbolGroup SG : File.symbol_groups()) { 56351278Sdim if (File.isObj()) { 57351278Sdim for (const auto &SS : SG.getDebugSubsections()) { 58351278Sdim // FIXME: Are there other type-referencing subsections? Inlinees? 59351278Sdim // Probably for IDs. 60351278Sdim if (SS.kind() != DebugSubsectionKind::Symbols) 61351278Sdim continue; 62351278Sdim 63351278Sdim CVSymbolArray Symbols; 64351278Sdim BinaryStreamReader Reader(SS.getRecordData()); 65351278Sdim cantFail(Reader.readArray(Symbols, Reader.getLength())); 66351278Sdim for (const CVSymbol &S : Symbols) 67351278Sdim addTypeRefsFromSymbol(S); 68351278Sdim } 69351278Sdim } else if (SG.hasDebugStream()) { 70351278Sdim for (const CVSymbol &S : SG.getPdbModuleStream().getSymbolArray()) 71351278Sdim addTypeRefsFromSymbol(S); 72351278Sdim } 73351278Sdim } 74351278Sdim 75351278Sdim // Walk globals and mark types referenced from globals. 76351278Sdim if (File.isPdb() && File.pdb().hasPDBGlobalsStream()) { 77351278Sdim SymbolStream &SymStream = cantFail(File.pdb().getPDBSymbolStream()); 78351278Sdim GlobalsStream &GS = cantFail(File.pdb().getPDBGlobalsStream()); 79351278Sdim for (uint32_t PubSymOff : GS.getGlobalsTable()) { 80351278Sdim CVSymbol Sym = SymStream.readRecord(PubSymOff); 81351278Sdim addTypeRefsFromSymbol(Sym); 82351278Sdim } 83351278Sdim } 84351278Sdim 85351278Sdim // FIXME: Should we walk Ids? 86351278Sdim} 87351278Sdim 88351278Sdimvoid TypeReferenceTracker::addOneTypeRef(TiRefKind RefKind, TypeIndex RefTI) { 89351278Sdim // If it's simple or already seen, no need to add to work list. 90351278Sdim BitVector &TypeOrIdReferenced = 91351278Sdim (Ids && RefKind == TiRefKind::IndexRef) ? IdReferenced : TypeReferenced; 92351278Sdim if (RefTI.isSimple() || TypeOrIdReferenced.test(RefTI.toArrayIndex())) 93351278Sdim return; 94351278Sdim 95351278Sdim // Otherwise, mark it seen and add it to the work list. 96351278Sdim TypeOrIdReferenced.set(RefTI.toArrayIndex()); 97351278Sdim RefWorklist.push_back({RefKind, RefTI}); 98351278Sdim} 99351278Sdim 100351278Sdimvoid TypeReferenceTracker::addTypeRefsFromSymbol(const CVSymbol &Sym) { 101351278Sdim SmallVector<TiReference, 4> DepList; 102351278Sdim // FIXME: Check for failure. 103351278Sdim discoverTypeIndicesInSymbol(Sym, DepList); 104351278Sdim addReferencedTypes(Sym.content(), DepList); 105351278Sdim markReferencedTypes(); 106351278Sdim} 107351278Sdim 108351278Sdimvoid TypeReferenceTracker::addReferencedTypes(ArrayRef<uint8_t> RecData, 109351278Sdim ArrayRef<TiReference> DepList) { 110351278Sdim for (const auto &Ref : DepList) { 111351278Sdim // FIXME: Report OOB slice instead of truncating. 112351278Sdim ArrayRef<uint8_t> ByteSlice = 113351278Sdim RecData.drop_front(Ref.Offset).take_front(4 * Ref.Count); 114351278Sdim ArrayRef<TypeIndex> TIs( 115351278Sdim reinterpret_cast<const TypeIndex *>(ByteSlice.data()), 116351278Sdim ByteSlice.size() / 4); 117351278Sdim 118351278Sdim // If this is a PDB and this is an item reference, track it in the IPI 119351278Sdim // bitvector. Otherwise, it's a type ref, or there is only one stream. 120351278Sdim for (TypeIndex RefTI : TIs) 121351278Sdim addOneTypeRef(Ref.Kind, RefTI); 122351278Sdim } 123351278Sdim} 124351278Sdim 125351278Sdimvoid TypeReferenceTracker::markReferencedTypes() { 126351278Sdim while (!RefWorklist.empty()) { 127351278Sdim TiRefKind RefKind; 128351278Sdim TypeIndex RefTI; 129351278Sdim std::tie(RefKind, RefTI) = RefWorklist.pop_back_val(); 130351278Sdim Optional<CVType> Rec = (Ids && RefKind == TiRefKind::IndexRef) 131351278Sdim ? Ids->tryGetType(RefTI) 132351278Sdim : Types.tryGetType(RefTI); 133351278Sdim if (!Rec) 134351278Sdim continue; // FIXME: Report a reference to a non-existant type. 135351278Sdim 136351278Sdim SmallVector<TiReference, 4> DepList; 137351278Sdim // FIXME: Check for failure. 138351278Sdim discoverTypeIndices(*Rec, DepList); 139351278Sdim addReferencedTypes(Rec->content(), DepList); 140351278Sdim 141351278Sdim // If this is a tag kind and this is a PDB input, mark the complete type as 142351278Sdim // referenced. 143351278Sdim // FIXME: This limitation makes this feature somewhat useless on object file 144351278Sdim // inputs. 145351278Sdim if (Tpi) { 146351278Sdim switch (Rec->kind()) { 147351278Sdim default: 148351278Sdim break; 149351278Sdim case LF_CLASS: 150351278Sdim case LF_INTERFACE: 151351278Sdim case LF_STRUCTURE: 152351278Sdim case LF_UNION: 153351278Sdim case LF_ENUM: 154351278Sdim addOneTypeRef(TiRefKind::TypeRef, 155351278Sdim cantFail(Tpi->findFullDeclForForwardRef(RefTI))); 156351278Sdim break; 157351278Sdim } 158351278Sdim } 159351278Sdim } 160351278Sdim} 161