DWARFLinker.cpp | Explore in Territory

//=== DWARFLinker.cpp -----------------------------------------------------===//
//
// 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/DWARFLinker/Classic/DWARFLinker.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/CodeGen/NonRelocatableStringpool.h"
#include "llvm/DWARFLinker/Classic/DWARFLinkerDeclContext.h"
#include "llvm/DWARFLinker/Classic/DWARFStreamer.h"
#include "llvm/DWARFLinker/Utils.h"
#include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
#include "llvm/DebugInfo/DWARF/DWARFContext.h"
#include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
#include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
#include "llvm/DebugInfo/DWARF/DWARFDebugMacro.h"
#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
#include "llvm/DebugInfo/DWARF/DWARFDie.h"
#include "llvm/DebugInfo/DWARF/DWARFExpression.h"
#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
#include "llvm/DebugInfo/DWARF/DWARFSection.h"
#include "llvm/DebugInfo/DWARF/DWARFUnit.h"
#include "llvm/MC/MCDwarf.h"
#include "llvm/Support/DataExtractor.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/ErrorOr.h"
#include "llvm/Support/FormatVariadic.h"
#include "llvm/Support/LEB128.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/ThreadPool.h"
#include <vector>

namespace llvm {

usingnamespacedwarf_linker;
usingnamespacedwarf_linker::classic;

/// Hold the input and output of the debug info size in bytes.
struct DebugInfoSize { … };

/// Compute the total size of the debug info.
static uint64_t getDebugInfoSize(DWARFContext &Dwarf) { … }

/// Similar to DWARFUnitSection::getUnitForOffset(), but returning our
/// CompileUnit object instead.
static CompileUnit *getUnitForOffset(const UnitListTy &Units, uint64_t Offset) { … }

/// Resolve the DIE attribute reference that has been extracted in \p RefValue.
/// The resulting DIE might be in another CompileUnit which is stored into \p
/// ReferencedCU. \returns null if resolving fails for any reason.
DWARFDie DWARFLinker::resolveDIEReference(const DWARFFile &File,
                                          const UnitListTy &Units,
                                          const DWARFFormValue &RefValue,
                                          const DWARFDie &DIE,
                                          CompileUnit *&RefCU) { … }

/// \returns whether the passed \a Attr type might contain a DIE reference
/// suitable for ODR uniquing.
static bool isODRAttribute(uint16_t Attr) { … }

static bool isTypeTag(uint16_t Tag) { … }

bool DWARFLinker::DIECloner::getDIENames(const DWARFDie &Die,
                                         AttributesInfo &Info,
                                         OffsetsStringPool &StringPool,
                                         bool StripTemplate) { … }

/// Resolve the relative path to a build artifact referenced by DWARF by
/// applying DW_AT_comp_dir.
static void resolveRelativeObjectPath(SmallVectorImpl<char> &Buf, DWARFDie CU) { … }

/// Collect references to parseable Swift interfaces in imported
/// DW_TAG_module blocks.
static void analyzeImportedModule(
    const DWARFDie &DIE, CompileUnit &CU,
    DWARFLinkerBase::SwiftInterfacesMapTy *ParseableSwiftInterfaces,
    std::function<void(const Twine &, const DWARFDie &)> ReportWarning) { … }

/// The distinct types of work performed by the work loop in
/// analyzeContextInfo.
enum class ContextWorklistItemType : uint8_t { … };

/// This class represents an item in the work list. The type defines what kind
/// of work needs to be performed when processing the current item. Everything
/// but the Type and Die fields are optional based on the type.
struct ContextWorklistItem { … };

static bool updatePruning(const DWARFDie &Die, CompileUnit &CU,
                          uint64_t ModulesEndOffset) { … }

static void updateChildPruning(const DWARFDie &Die, CompileUnit &CU,
                               CompileUnit::DIEInfo &ChildInfo) { … }

/// Recursive helper to build the global DeclContext information and
/// gather the child->parent relationships in the original compile unit.
///
/// This function uses the same work list approach as lookForDIEsToKeep.
///
/// \return true when this DIE and all of its children are only
/// forward declarations to types defined in external clang modules
/// (i.e., forward declarations that are children of a DW_TAG_module).
static void analyzeContextInfo(
    const DWARFDie &DIE, unsigned ParentIdx, CompileUnit &CU,
    DeclContext *CurrentDeclContext, DeclContextTree &Contexts,
    uint64_t ModulesEndOffset,
    DWARFLinkerBase::SwiftInterfacesMapTy *ParseableSwiftInterfaces,
    std::function<void(const Twine &, const DWARFDie &)> ReportWarning) { … }

static bool dieNeedsChildrenToBeMeaningful(uint32_t Tag) { … }

void DWARFLinker::cleanupAuxiliarryData(LinkContext &Context) { … }

static bool isTlsAddressCode(uint8_t DW_OP_Code) { … }

std::pair<bool, std::optional<int64_t>>
DWARFLinker::getVariableRelocAdjustment(AddressesMap &RelocMgr,
                                        const DWARFDie &DIE) { … }

/// Check if a variable describing DIE should be kept.
/// \returns updated TraversalFlags.
unsigned DWARFLinker::shouldKeepVariableDIE(AddressesMap &RelocMgr,
                                            const DWARFDie &DIE,
                                            CompileUnit::DIEInfo &MyInfo,
                                            unsigned Flags) { … }

/// Check if a function describing DIE should be kept.
/// \returns updated TraversalFlags.
unsigned DWARFLinker::shouldKeepSubprogramDIE(
    AddressesMap &RelocMgr, const DWARFDie &DIE, const DWARFFile &File,
    CompileUnit &Unit, CompileUnit::DIEInfo &MyInfo, unsigned Flags) { … }

/// Check if a DIE should be kept.
/// \returns updated TraversalFlags.
unsigned DWARFLinker::shouldKeepDIE(AddressesMap &RelocMgr, const DWARFDie &DIE,
                                    const DWARFFile &File, CompileUnit &Unit,
                                    CompileUnit::DIEInfo &MyInfo,
                                    unsigned Flags) { … }

/// Helper that updates the completeness of the current DIE based on the
/// completeness of one of its children. It depends on the incompleteness of
/// the children already being computed.
static void updateChildIncompleteness(const DWARFDie &Die, CompileUnit &CU,
                                      CompileUnit::DIEInfo &ChildInfo) { … }

/// Helper that updates the completeness of the current DIE based on the
/// completeness of the DIEs it references. It depends on the incompleteness of
/// the referenced DIE already being computed.
static void updateRefIncompleteness(const DWARFDie &Die, CompileUnit &CU,
                                    CompileUnit::DIEInfo &RefInfo) { … }

/// Look at the children of the given DIE and decide whether they should be
/// kept.
void DWARFLinker::lookForChildDIEsToKeep(
    const DWARFDie &Die, CompileUnit &CU, unsigned Flags,
    SmallVectorImpl<WorklistItem> &Worklist) { … }

static bool isODRCanonicalCandidate(const DWARFDie &Die, CompileUnit &CU) { … }

void DWARFLinker::markODRCanonicalDie(const DWARFDie &Die, CompileUnit &CU) { … }

/// Look at DIEs referenced by the given DIE and decide whether they should be
/// kept. All DIEs referenced though attributes should be kept.
void DWARFLinker::lookForRefDIEsToKeep(
    const DWARFDie &Die, CompileUnit &CU, unsigned Flags,
    const UnitListTy &Units, const DWARFFile &File,
    SmallVectorImpl<WorklistItem> &Worklist) { … }

/// Look at the parent of the given DIE and decide whether they should be kept.
void DWARFLinker::lookForParentDIEsToKeep(
    unsigned AncestorIdx, CompileUnit &CU, unsigned Flags,
    SmallVectorImpl<WorklistItem> &Worklist) { … }

/// Recursively walk the \p DIE tree and look for DIEs to keep. Store that
/// information in \p CU's DIEInfo.
///
/// This function is the entry point of the DIE selection algorithm. It is
/// expected to walk the DIE tree in file order and (though the mediation of
/// its helper) call hasValidRelocation() on each DIE that might be a 'root
/// DIE' (See DwarfLinker class comment).
///
/// While walking the dependencies of root DIEs, this function is also called,
/// but during these dependency walks the file order is not respected. The
/// TF_DependencyWalk flag tells us which kind of traversal we are currently
/// doing.
///
/// The recursive algorithm is implemented iteratively as a work list because
/// very deep recursion could exhaust the stack for large projects. The work
/// list acts as a scheduler for different types of work that need to be
/// performed.
///
/// The recursive nature of the algorithm is simulated by running the "main"
/// algorithm (LookForDIEsToKeep) followed by either looking at more DIEs
/// (LookForChildDIEsToKeep, LookForRefDIEsToKeep, LookForParentDIEsToKeep) or
/// fixing up a computed property (UpdateChildIncompleteness,
/// UpdateRefIncompleteness).
///
/// The return value indicates whether the DIE is incomplete.
void DWARFLinker::lookForDIEsToKeep(AddressesMap &AddressesMap,
                                    const UnitListTy &Units,
                                    const DWARFDie &Die, const DWARFFile &File,
                                    CompileUnit &Cu, unsigned Flags) { … }

#ifndef NDEBUG
/// A broken link in the keep chain. By recording both the parent and the child
/// we can show only broken links for DIEs with multiple children.
struct BrokenLink {
  BrokenLink(DWARFDie Parent, DWARFDie Child) : Parent(Parent), Child(Child) {}
  DWARFDie Parent;
  DWARFDie Child;
};

/// Verify the keep chain by looking for DIEs that are kept but who's parent
/// isn't.
static void verifyKeepChain(CompileUnit &CU) {
  std::vector<DWARFDie> Worklist;
  Worklist.push_back(CU.getOrigUnit().getUnitDIE());

  // List of broken links.
  std::vector<BrokenLink> BrokenLinks;

  while (!Worklist.empty()) {
    const DWARFDie Current = Worklist.back();
    Worklist.pop_back();

    const bool CurrentDieIsKept = CU.getInfo(Current).Keep;

    for (DWARFDie Child : reverse(Current.children())) {
      Worklist.push_back(Child);

      const bool ChildDieIsKept = CU.getInfo(Child).Keep;
      if (!CurrentDieIsKept && ChildDieIsKept)
        BrokenLinks.emplace_back(Current, Child);
    }
  }

  if (!BrokenLinks.empty()) {
    for (BrokenLink Link : BrokenLinks) {
      WithColor::error() << formatv(
          "Found invalid link in keep chain between {0:x} and {1:x}\n",
          Link.Parent.getOffset(), Link.Child.getOffset());

      errs() << "Parent:";
      Link.Parent.dump(errs(), 0, {});
      CU.getInfo(Link.Parent).dump();

      errs() << "Child:";
      Link.Child.dump(errs(), 2, {});
      CU.getInfo(Link.Child).dump();
    }
    report_fatal_error("invalid keep chain");
  }
}
#endif

/// Assign an abbreviation number to \p Abbrev.
///
/// Our DIEs get freed after every DebugMapObject has been processed,
/// thus the FoldingSet we use to unique DIEAbbrevs cannot refer to
/// the instances hold by the DIEs. When we encounter an abbreviation
/// that we don't know, we create a permanent copy of it.
void DWARFLinker::assignAbbrev(DIEAbbrev &Abbrev) { … }

unsigned DWARFLinker::DIECloner::cloneStringAttribute(DIE &Die,
                                                      AttributeSpec AttrSpec,
                                                      const DWARFFormValue &Val,
                                                      const DWARFUnit &U,
                                                      AttributesInfo &Info) { … }

unsigned DWARFLinker::DIECloner::cloneDieReferenceAttribute(
    DIE &Die, const DWARFDie &InputDIE, AttributeSpec AttrSpec,
    unsigned AttrSize, const DWARFFormValue &Val, const DWARFFile &File,
    CompileUnit &Unit) { … }

void DWARFLinker::DIECloner::cloneExpression(
    DataExtractor &Data, DWARFExpression Expression, const DWARFFile &File,
    CompileUnit &Unit, SmallVectorImpl<uint8_t> &OutputBuffer,
    int64_t AddrRelocAdjustment, bool IsLittleEndian) { … }

unsigned DWARFLinker::DIECloner::cloneBlockAttribute(
    DIE &Die, const DWARFDie &InputDIE, const DWARFFile &File,
    CompileUnit &Unit, AttributeSpec AttrSpec, const DWARFFormValue &Val,
    bool IsLittleEndian) { … }

unsigned DWARFLinker::DIECloner::cloneAddressAttribute(
    DIE &Die, const DWARFDie &InputDIE, AttributeSpec AttrSpec,
    unsigned AttrSize, const DWARFFormValue &Val, const CompileUnit &Unit,
    AttributesInfo &Info) { … }

unsigned DWARFLinker::DIECloner::cloneScalarAttribute(
    DIE &Die, const DWARFDie &InputDIE, const DWARFFile &File,
    CompileUnit &Unit, AttributeSpec AttrSpec, const DWARFFormValue &Val,
    unsigned AttrSize, AttributesInfo &Info) { … }

/// Clone \p InputDIE's attribute described by \p AttrSpec with
/// value \p Val, and add it to \p Die.
/// \returns the size of the cloned attribute.
unsigned DWARFLinker::DIECloner::cloneAttribute(
    DIE &Die, const DWARFDie &InputDIE, const DWARFFile &File,
    CompileUnit &Unit, const DWARFFormValue &Val, const AttributeSpec AttrSpec,
    unsigned AttrSize, AttributesInfo &Info, bool IsLittleEndian) { … }

void DWARFLinker::DIECloner::addObjCAccelerator(CompileUnit &Unit,
                                                const DIE *Die,
                                                DwarfStringPoolEntryRef Name,
                                                OffsetsStringPool &StringPool,
                                                bool SkipPubSection) { … }

static bool
shouldSkipAttribute(bool Update,
                    DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
                    bool SkipPC) { … }

struct AttributeLinkedOffsetFixup { … };

DIE *DWARFLinker::DIECloner::cloneDIE(const DWARFDie &InputDIE,
                                      const DWARFFile &File, CompileUnit &Unit,
                                      int64_t PCOffset, uint32_t OutOffset,
                                      unsigned Flags, bool IsLittleEndian,
                                      DIE *Die) { … }

/// Patch the input object file relevant debug_ranges or debug_rnglists
/// entries and emit them in the output file. Update the relevant attributes
/// to point at the new entries.
void DWARFLinker::generateUnitRanges(CompileUnit &Unit, const DWARFFile &File,
                                     DebugDieValuePool &AddrPool) const { … }

void DWARFLinker::DIECloner::generateUnitLocations(
    CompileUnit &Unit, const DWARFFile &File,
    ExpressionHandlerRef ExprHandler) { … }

static void patchAddrBase(DIE &Die, DIEInteger Offset) { … }

void DWARFLinker::DIECloner::emitDebugAddrSection(
    CompileUnit &Unit, const uint16_t DwarfVersion) const { … }

/// Insert the new line info sequence \p Seq into the current
/// set of already linked line info \p Rows.
static void insertLineSequence(std::vector<DWARFDebugLine::Row> &Seq,
                               std::vector<DWARFDebugLine::Row> &Rows) { … }

static void patchStmtList(DIE &Die, DIEInteger Offset) { … }

void DWARFLinker::DIECloner::rememberUnitForMacroOffset(CompileUnit &Unit) { … }

void DWARFLinker::DIECloner::generateLineTableForUnit(CompileUnit &Unit) { … }

void DWARFLinker::emitAcceleratorEntriesForUnit(CompileUnit &Unit) { … }

/// Read the frame info stored in the object, and emit the
/// patched frame descriptions for the resulting file.
///
/// This is actually pretty easy as the data of the CIEs and FDEs can
/// be considered as black boxes and moved as is. The only thing to do
/// is to patch the addresses in the headers.
void DWARFLinker::patchFrameInfoForObject(LinkContext &Context) { … }

uint32_t DWARFLinker::DIECloner::hashFullyQualifiedName(DWARFDie DIE,
                                                        CompileUnit &U,
                                                        const DWARFFile &File,
                                                        int ChildRecurseDepth) { … }

static uint64_t getDwoId(const DWARFDie &CUDie) { … }

static std::string
remapPath(StringRef Path,
          const DWARFLinkerBase::ObjectPrefixMapTy &ObjectPrefixMap) { … }

static std::string
getPCMFile(const DWARFDie &CUDie,
           const DWARFLinkerBase::ObjectPrefixMapTy *ObjectPrefixMap) { … }

std::pair<bool, bool> DWARFLinker::isClangModuleRef(const DWARFDie &CUDie,
                                                    std::string &PCMFile,
                                                    LinkContext &Context,
                                                    unsigned Indent,
                                                    bool Quiet) { … }

bool DWARFLinker::registerModuleReference(const DWARFDie &CUDie,
                                          LinkContext &Context,
                                          ObjFileLoaderTy Loader,
                                          CompileUnitHandlerTy OnCUDieLoaded,
                                          unsigned Indent) { … }

Error DWARFLinker::loadClangModule(
    ObjFileLoaderTy Loader, const DWARFDie &CUDie, const std::string &PCMFile,
    LinkContext &Context, CompileUnitHandlerTy OnCUDieLoaded, unsigned Indent) { … }

uint64_t DWARFLinker::DIECloner::cloneAllCompileUnits(
    DWARFContext &DwarfContext, const DWARFFile &File, bool IsLittleEndian) { … }

void DWARFLinker::copyInvariantDebugSection(DWARFContext &Dwarf) { … }

void DWARFLinker::addObjectFile(DWARFFile &File, ObjFileLoaderTy Loader,
                                CompileUnitHandlerTy OnCUDieLoaded) { … }

Error DWARFLinker::link() { … }

Error DWARFLinker::cloneModuleUnit(LinkContext &Context, RefModuleUnit &Unit,
                                   DeclContextTree &ODRContexts,
                                   OffsetsStringPool &DebugStrPool,
                                   OffsetsStringPool &DebugLineStrPool,
                                   DebugDieValuePool &StringOffsetPool,
                                   unsigned Indent) { … }

void DWARFLinker::verifyInput(const DWARFFile &File) { … }

} // namespace llvm
llvm/llvm/lib/DWARFLinker/Classic/DWARFLinker.cpp
