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