llvm/llvm/lib/DebugInfo/CodeView/TypeStreamMerger.cpp

//===-- TypeStreamMerger.cpp ------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/DebugInfo/CodeView/TypeStreamMerger.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
#include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
#include "llvm/DebugInfo/CodeView/TypeDeserializer.h"
#include "llvm/DebugInfo/CodeView/TypeIndex.h"
#include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h"
#include "llvm/DebugInfo/CodeView/TypeRecord.h"
#include "llvm/DebugInfo/CodeView/TypeRecordHelpers.h"
#include "llvm/Support/Error.h"
#include <optional>

usingnamespacellvm;
usingnamespacellvm::codeview;

static inline size_t slotForIndex(TypeIndex Idx) { … }

namespace {

/// Implementation of CodeView type stream merging.
///
/// A CodeView type stream is a series of records that reference each other
/// through type indices. A type index is either "simple", meaning it is less
/// than 0x1000 and refers to a builtin type, or it is complex, meaning it
/// refers to a prior type record in the current stream. The type index of a
/// record is equal to the number of records before it in the stream plus
/// 0x1000.
///
/// Type records are only allowed to use type indices smaller than their own, so
/// a type stream is effectively a topologically sorted DAG. Cycles occurring in
/// the type graph of the source program are resolved with forward declarations
/// of composite types. This class implements the following type stream merging
/// algorithm, which relies on this DAG structure:
///
/// - Begin with a new empty stream, and a new empty hash table that maps from
///   type record contents to new type index.
/// - For each new type stream, maintain a map from source type index to
///   destination type index.
/// - For each record, copy it and rewrite its type indices to be valid in the
///   destination type stream.
/// - If the new type record is not already present in the destination stream
///   hash table, append it to the destination type stream, assign it the next
///   type index, and update the two hash tables.
/// - If the type record already exists in the destination stream, discard it
///   and update the type index map to forward the source type index to the
///   existing destination type index.
///
/// As an additional complication, type stream merging actually produces two
/// streams: an item (or IPI) stream and a type stream, as this is what is
/// actually stored in the final PDB. We choose which records go where by
/// looking at the record kind.
class TypeStreamMerger { … };

} // end anonymous namespace

const TypeIndex TypeStreamMerger::Untranslated(SimpleTypeKind::NotTranslated);

void TypeStreamMerger::addMapping(TypeIndex Idx) { … }

bool TypeStreamMerger::remapIndexFallback(TypeIndex &Idx,
                                          ArrayRef<TypeIndex> Map) { … }

// Local hashing entry points
Error TypeStreamMerger::mergeTypeRecords(MergingTypeTableBuilder &Dest,
                                         const CVTypeArray &Types) { … }

Error TypeStreamMerger::mergeIdRecords(MergingTypeTableBuilder &Dest,
                                       ArrayRef<TypeIndex> TypeSourceToDest,
                                       const CVTypeArray &Ids) { … }

Error TypeStreamMerger::mergeTypesAndIds(
    MergingTypeTableBuilder &DestIds, MergingTypeTableBuilder &DestTypes,
    const CVTypeArray &IdsAndTypes, std::optional<PCHMergerInfo> &PCHInfo) { … }

// Global hashing entry points
Error TypeStreamMerger::mergeTypeRecords(
    GlobalTypeTableBuilder &Dest, const CVTypeArray &Types,
    ArrayRef<GloballyHashedType> Hashes,
    std::optional<PCHMergerInfo> &PCHInfo) { … }

Error TypeStreamMerger::mergeIdRecords(GlobalTypeTableBuilder &Dest,
                                       ArrayRef<TypeIndex> TypeSourceToDest,
                                       const CVTypeArray &Ids,
                                       ArrayRef<GloballyHashedType> Hashes) { … }

Error TypeStreamMerger::mergeTypesAndIds(
    GlobalTypeTableBuilder &DestIds, GlobalTypeTableBuilder &DestTypes,
    const CVTypeArray &IdsAndTypes, ArrayRef<GloballyHashedType> Hashes,
    std::optional<PCHMergerInfo> &PCHInfo) { … }

Error TypeStreamMerger::doit(const CVTypeArray &Types) { … }

Error TypeStreamMerger::remapAllTypes(const CVTypeArray &Types) { … }

Error TypeStreamMerger::remapType(const CVType &Type) { … }

ArrayRef<uint8_t>
TypeStreamMerger::remapIndices(const CVType &OriginalType,
                               MutableArrayRef<uint8_t> Storage) { … }

Error llvm::codeview::mergeTypeRecords(MergingTypeTableBuilder &Dest,
                                       SmallVectorImpl<TypeIndex> &SourceToDest,
                                       const CVTypeArray &Types) { … }

Error llvm::codeview::mergeIdRecords(MergingTypeTableBuilder &Dest,
                                     ArrayRef<TypeIndex> TypeSourceToDest,
                                     SmallVectorImpl<TypeIndex> &SourceToDest,
                                     const CVTypeArray &Ids) { … }

Error llvm::codeview::mergeTypeAndIdRecords(
    MergingTypeTableBuilder &DestIds, MergingTypeTableBuilder &DestTypes,
    SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes,
    std::optional<PCHMergerInfo> &PCHInfo) { … }

Error llvm::codeview::mergeTypeAndIdRecords(
    GlobalTypeTableBuilder &DestIds, GlobalTypeTableBuilder &DestTypes,
    SmallVectorImpl<TypeIndex> &SourceToDest, const CVTypeArray &IdsAndTypes,
    ArrayRef<GloballyHashedType> Hashes,
    std::optional<PCHMergerInfo> &PCHInfo) { … }

Error llvm::codeview::mergeTypeRecords(GlobalTypeTableBuilder &Dest,
                                       SmallVectorImpl<TypeIndex> &SourceToDest,
                                       const CVTypeArray &Types,
                                       ArrayRef<GloballyHashedType> Hashes,
                                       std::optional<PCHMergerInfo> &PCHInfo) { … }

Error llvm::codeview::mergeIdRecords(GlobalTypeTableBuilder &Dest,
                                     ArrayRef<TypeIndex> Types,
                                     SmallVectorImpl<TypeIndex> &SourceToDest,
                                     const CVTypeArray &Ids,
                                     ArrayRef<GloballyHashedType> Hashes) { … }

Expected<bool> TypeStreamMerger::shouldRemapType(const CVType &Type) { … }