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
17using namespace llvm;
18using namespace llvm::pdb;
19using namespace llvm::codeview;
20
21// LazyRandomTypeCollection doesn't appear to expose the number of records, so
22// just iterate up front to find out.
23static 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
30TypeReferenceTracker::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
50void 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
88void 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
100void 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
108void 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
125void 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