llvm/tools/llvm-pdbutil/TypeReferenceTracker.cpp

   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 (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(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 }