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
19using namespace llvm;
20using namespace llvm::pdb;
21using namespace llvm::codeview;
22
23// LazyRandomTypeCollection doesn't appear to expose the number of records, so
24// just iterate up front to find out.
25static 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
33TypeReferenceTracker::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
53void 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
91void 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
103void 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
111void 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
128void 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}
164