path: root/contrib/libs/llvm12/tools/dsymutil/DwarfLinkerForBinary.cpp

//===- tools/dsymutil/DwarfLinkerForBinary.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 "DwarfLinkerForBinary.h" 
#include "BinaryHolder.h" 
#include "DebugMap.h" 
#include "MachOUtils.h" 
#include "dsymutil.h" 
#include "llvm/ADT/ArrayRef.h" 
#include "llvm/ADT/BitVector.h" 
#include "llvm/ADT/DenseMap.h" 
#include "llvm/ADT/DenseMapInfo.h" 
#include "llvm/ADT/DenseSet.h" 
#include "llvm/ADT/FoldingSet.h" 
#include "llvm/ADT/Hashing.h" 
#include "llvm/ADT/IntervalMap.h" 
#include "llvm/ADT/None.h" 
#include "llvm/ADT/Optional.h" 
#include "llvm/ADT/PointerIntPair.h" 
#include "llvm/ADT/STLExtras.h" 
#include "llvm/ADT/SmallString.h" 
#include "llvm/ADT/StringMap.h" 
#include "llvm/ADT/StringRef.h" 
#include "llvm/ADT/Triple.h" 
#include "llvm/ADT/Twine.h" 
#include "llvm/BinaryFormat/Dwarf.h" 
#include "llvm/BinaryFormat/MachO.h" 
#include "llvm/CodeGen/AccelTable.h" 
#include "llvm/CodeGen/AsmPrinter.h" 
#include "llvm/CodeGen/DIE.h" 
#include "llvm/CodeGen/NonRelocatableStringpool.h" 
#include "llvm/Config/config.h" 
#include "llvm/DWARFLinker/DWARFLinkerDeclContext.h" 
#include "llvm/DebugInfo/DIContext.h" 
#include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h" 
#include "llvm/DebugInfo/DWARF/DWARFContext.h" 
#include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h" 
#include "llvm/DebugInfo/DWARF/DWARFDebugLine.h" 
#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h" 
#include "llvm/DebugInfo/DWARF/DWARFDie.h" 
#include "llvm/DebugInfo/DWARF/DWARFFormValue.h" 
#include "llvm/DebugInfo/DWARF/DWARFSection.h" 
#include "llvm/DebugInfo/DWARF/DWARFUnit.h" 
#include "llvm/MC/MCAsmBackend.h" 
#include "llvm/MC/MCAsmInfo.h" 
#include "llvm/MC/MCCodeEmitter.h" 
#include "llvm/MC/MCContext.h" 
#include "llvm/MC/MCDwarf.h" 
#include "llvm/MC/MCInstrInfo.h" 
#include "llvm/MC/MCObjectFileInfo.h" 
#include "llvm/MC/MCObjectWriter.h" 
#include "llvm/MC/MCRegisterInfo.h" 
#include "llvm/MC/MCSection.h" 
#include "llvm/MC/MCStreamer.h" 
#include "llvm/MC/MCSubtargetInfo.h" 
#include "llvm/MC/MCTargetOptions.h" 
#include "llvm/Object/MachO.h" 
#include "llvm/Object/ObjectFile.h" 
#include "llvm/Object/SymbolicFile.h" 
#include "llvm/Support/Allocator.h" 
#include "llvm/Support/Casting.h" 
#include "llvm/Support/Compiler.h" 
#include "llvm/Support/DJB.h" 
#include "llvm/Support/DataExtractor.h" 
#include "llvm/Support/Error.h" 
#include "llvm/Support/ErrorHandling.h" 
#include "llvm/Support/ErrorOr.h" 
#include "llvm/Support/FileSystem.h" 
#include "llvm/Support/Format.h" 
#include "llvm/Support/LEB128.h" 
#include "llvm/Support/MathExtras.h" 
#include "llvm/Support/MemoryBuffer.h" 
#include "llvm/Support/Path.h" 
#include "llvm/Support/TargetRegistry.h" 
#include "llvm/Support/ThreadPool.h" 
#include "llvm/Support/ToolOutputFile.h" 
#include "llvm/Support/WithColor.h" 
#include "llvm/Support/raw_ostream.h" 
#include "llvm/Target/TargetMachine.h" 
#include "llvm/Target/TargetOptions.h" 
#include "llvm/MC/MCTargetOptionsCommandFlags.h" 
#include <algorithm> 
#include <cassert> 
#include <cinttypes> 
#include <climits> 
#include <cstdint> 
#include <cstdlib> 
#include <cstring> 
#include <limits> 
#include <map> 
#include <memory> 
#include <string> 
#include <system_error> 
#include <tuple> 
#include <utility> 
#include <vector> 
 
namespace llvm { 
 
static mc::RegisterMCTargetOptionsFlags MOF; 
 
namespace dsymutil { 
 
static Error copySwiftInterfaces( 
    const std::map<std::string, std::string> &ParseableSwiftInterfaces, 
    StringRef Architecture, const LinkOptions &Options) { 
  std::error_code EC; 
  SmallString<128> InputPath; 
  SmallString<128> Path; 
  sys::path::append(Path, *Options.ResourceDir, "Swift", Architecture); 
  if ((EC = sys::fs::create_directories(Path.str(), true, 
                                        sys::fs::perms::all_all))) 
    return make_error<StringError>( 
        "cannot create directory: " + toString(errorCodeToError(EC)), EC); 
  unsigned BaseLength = Path.size(); 
 
  for (auto &I : ParseableSwiftInterfaces) { 
    StringRef ModuleName = I.first; 
    StringRef InterfaceFile = I.second; 
    if (!Options.PrependPath.empty()) { 
      InputPath.clear(); 
      sys::path::append(InputPath, Options.PrependPath, InterfaceFile); 
      InterfaceFile = InputPath; 
    } 
    sys::path::append(Path, ModuleName); 
    Path.append(".swiftinterface"); 
    if (Options.Verbose) 
      outs() << "copy parseable Swift interface " << InterfaceFile << " -> " 
             << Path.str() << '\n'; 
 
    // copy_file attempts an APFS clone first, so this should be cheap. 
    if ((EC = sys::fs::copy_file(InterfaceFile, Path.str()))) 
      warn(Twine("cannot copy parseable Swift interface ") + InterfaceFile + 
           ": " + toString(errorCodeToError(EC))); 
    Path.resize(BaseLength); 
  } 
  return Error::success(); 
} 
 
/// Report a warning to the user, optionally including information about a 
/// specific \p DIE related to the warning. 
void DwarfLinkerForBinary::reportWarning(const Twine &Warning, 
                                         StringRef Context, 
                                         const DWARFDie *DIE) const { 
 
  warn(Warning, Context); 
 
  if (!Options.Verbose || !DIE) 
    return; 
 
  DIDumpOptions DumpOpts; 
  DumpOpts.ChildRecurseDepth = 0; 
  DumpOpts.Verbose = Options.Verbose; 
 
  WithColor::note() << "    in DIE:\n"; 
  DIE->dump(errs(), 6 /* Indent */, DumpOpts); 
} 
 
bool DwarfLinkerForBinary::createStreamer(const Triple &TheTriple, 
                                          raw_fd_ostream &OutFile) { 
  if (Options.NoOutput) 
    return true; 
 
  Streamer = std::make_unique<DwarfStreamer>( 
      Options.FileType, OutFile, Options.Translator, Options.Minimize, 
      [&](const Twine &Error, StringRef Context, const DWARFDie *) { 
        error(Error, Context); 
      }, 
      [&](const Twine &Warning, StringRef Context, const DWARFDie *) { 
        warn(Warning, Context); 
      }); 
  return Streamer->init(TheTriple); 
} 
 
ErrorOr<const object::ObjectFile &> 
DwarfLinkerForBinary::loadObject(const DebugMapObject &Obj, 
                                 const Triple &Triple) { 
  auto ObjectEntry = 
      BinHolder.getObjectEntry(Obj.getObjectFilename(), Obj.getTimestamp()); 
  if (!ObjectEntry) { 
    auto Err = ObjectEntry.takeError(); 
    reportWarning(Twine(Obj.getObjectFilename()) + ": " + 
                      toString(std::move(Err)), 
                  Obj.getObjectFilename()); 
    return errorToErrorCode(std::move(Err)); 
  } 
 
  auto Object = ObjectEntry->getObject(Triple); 
  if (!Object) { 
    auto Err = Object.takeError(); 
    reportWarning(Twine(Obj.getObjectFilename()) + ": " + 
                      toString(std::move(Err)), 
                  Obj.getObjectFilename()); 
    return errorToErrorCode(std::move(Err)); 
  } 
 
  return *Object; 
} 
 
static Error remarksErrorHandler(const DebugMapObject &DMO, 
                                 DwarfLinkerForBinary &Linker, 
                                 std::unique_ptr<FileError> FE) { 
  bool IsArchive = DMO.getObjectFilename().endswith(")"); 
  // Don't report errors for missing remark files from static 
  // archives. 
  if (!IsArchive) 
    return Error(std::move(FE)); 
 
  std::string Message = FE->message(); 
  Error E = FE->takeError(); 
  Error NewE = handleErrors(std::move(E), [&](std::unique_ptr<ECError> EC) { 
    if (EC->convertToErrorCode() != std::errc::no_such_file_or_directory) 
      return Error(std::move(EC)); 
 
    Linker.reportWarning(Message, DMO.getObjectFilename()); 
    return Error(Error::success()); 
  }); 
 
  if (!NewE) 
    return Error::success(); 
 
  return createFileError(FE->getFileName(), std::move(NewE)); 
} 
 
static Error emitRemarks(const LinkOptions &Options, StringRef BinaryPath, 
                         StringRef ArchName, const remarks::RemarkLinker &RL) { 
  // Make sure we don't create the directories and the file if there is nothing 
  // to serialize. 
  if (RL.empty()) 
    return Error::success(); 
 
  SmallString<128> InputPath; 
  SmallString<128> Path; 
  // Create the "Remarks" directory in the "Resources" directory. 
  sys::path::append(Path, *Options.ResourceDir, "Remarks"); 
  if (std::error_code EC = sys::fs::create_directories(Path.str(), true, 
                                                       sys::fs::perms::all_all)) 
    return errorCodeToError(EC); 
 
  // Append the file name. 
  // For fat binaries, also append a dash and the architecture name. 
  sys::path::append(Path, sys::path::filename(BinaryPath)); 
  if (Options.NumDebugMaps > 1) { 
    // More than one debug map means we have a fat binary. 
    Path += '-'; 
    Path += ArchName; 
  } 
 
  std::error_code EC; 
  raw_fd_ostream OS(Options.NoOutput ? "-" : Path.str(), EC, sys::fs::OF_None); 
  if (EC) 
    return errorCodeToError(EC); 
 
  if (Error E = RL.serialize(OS, Options.RemarksFormat)) 
    return E; 
 
  return Error::success(); 
} 
 
ErrorOr<DWARFFile &>
DwarfLinkerForBinary::loadObject(const DebugMapObject &Obj, 
                                 const DebugMap &DebugMap, 
                                 remarks::RemarkLinker &RL) { 
  auto ErrorOrObj = loadObject(Obj, DebugMap.getTriple()); 
 
  if (ErrorOrObj) { 
    ContextForLinking.push_back( 
        std::unique_ptr<DWARFContext>(DWARFContext::create(*ErrorOrObj))); 
    AddressMapForLinking.push_back( 
        std::make_unique<AddressManager>(*this, *ErrorOrObj, Obj)); 
 
    ObjectsForLinking.push_back(std::make_unique<DWARFFile>(
        Obj.getObjectFilename(), ContextForLinking.back().get(), 
        AddressMapForLinking.back().get(), 
        Obj.empty() ? Obj.getWarnings() : EmptyWarnings)); 
 
    Error E = RL.link(*ErrorOrObj); 
    if (Error NewE = handleErrors( 
            std::move(E), [&](std::unique_ptr<FileError> EC) -> Error { 
              return remarksErrorHandler(Obj, *this, std::move(EC)); 
            })) 
      return errorToErrorCode(std::move(NewE)); 
 
    return *ObjectsForLinking.back(); 
  } 
 
  return ErrorOrObj.getError(); 
} 
 
bool DwarfLinkerForBinary::link(const DebugMap &Map) { 
  if (!createStreamer(Map.getTriple(), OutFile)) 
    return false; 
 
  ObjectsForLinking.clear(); 
  ContextForLinking.clear(); 
  AddressMapForLinking.clear(); 
 
  DebugMap DebugMap(Map.getTriple(), Map.getBinaryPath()); 
 
  DWARFLinker GeneralLinker(Streamer.get(), DwarfLinkerClient::Dsymutil); 
 
  remarks::RemarkLinker RL; 
  if (!Options.RemarksPrependPath.empty()) 
    RL.setExternalFilePrependPath(Options.RemarksPrependPath); 
  GeneralLinker.setObjectPrefixMap(&Options.ObjectPrefixMap); 
 
  std::function<StringRef(StringRef)> TranslationLambda = [&](StringRef Input) { 
    assert(Options.Translator); 
    return Options.Translator(Input); 
  }; 
 
  GeneralLinker.setVerbosity(Options.Verbose); 
  GeneralLinker.setStatistics(Options.Statistics); 
  GeneralLinker.setNoOutput(Options.NoOutput); 
  GeneralLinker.setNoODR(Options.NoODR); 
  GeneralLinker.setUpdate(Options.Update); 
  GeneralLinker.setNumThreads(Options.Threads); 
  GeneralLinker.setAccelTableKind(Options.TheAccelTableKind); 
  GeneralLinker.setPrependPath(Options.PrependPath); 
  if (Options.Translator) 
    GeneralLinker.setStringsTranslator(TranslationLambda); 
  GeneralLinker.setWarningHandler( 
      [&](const Twine &Warning, StringRef Context, const DWARFDie *DIE) { 
        reportWarning(Warning, Context, DIE); 
      }); 
  GeneralLinker.setErrorHandler( 
      [&](const Twine &Error, StringRef Context, const DWARFDie *) { 
        error(Error, Context); 
      }); 
  GeneralLinker.setObjFileLoader( 
      [&DebugMap, &RL, this](StringRef ContainerName, 
                             StringRef Path) -> ErrorOr<DWARFFile &> {
        auto &Obj = DebugMap.addDebugMapObject( 
            Path, sys::TimePoint<std::chrono::seconds>(), MachO::N_OSO); 
 
        if (auto ErrorOrObj = loadObject(Obj, DebugMap, RL)) { 
          return *ErrorOrObj; 
        } else { 
          // Try and emit more helpful warnings by applying some heuristics. 
          StringRef ObjFile = ContainerName; 
          bool IsClangModule = sys::path::extension(Path).equals(".pcm"); 
          bool IsArchive = ObjFile.endswith(")"); 
 
          if (IsClangModule) { 
            StringRef ModuleCacheDir = sys::path::parent_path(Path); 
            if (sys::fs::exists(ModuleCacheDir)) { 
              // If the module's parent directory exists, we assume that the 
              // module cache has expired and was pruned by clang.  A more 
              // adventurous dsymutil would invoke clang to rebuild the module 
              // now. 
              if (!ModuleCacheHintDisplayed) { 
                WithColor::note() 
                    << "The clang module cache may have expired since " 
                       "this object file was built. Rebuilding the " 
                       "object file will rebuild the module cache.\n"; 
                ModuleCacheHintDisplayed = true; 
              } 
            } else if (IsArchive) { 
              // If the module cache directory doesn't exist at all and the 
              // object file is inside a static library, we assume that the 
              // static library was built on a different machine. We don't want 
              // to discourage module debugging for convenience libraries within 
              // a project though. 
              if (!ArchiveHintDisplayed) { 
                WithColor::note() 
                    << "Linking a static library that was built with " 
                       "-gmodules, but the module cache was not found.  " 
                       "Redistributable static libraries should never be " 
                       "built with module debugging enabled.  The debug " 
                       "experience will be degraded due to incomplete " 
                       "debug information.\n"; 
                ArchiveHintDisplayed = true; 
              } 
            } 
          } 
 
          return ErrorOrObj.getError(); 
        } 
 
        llvm_unreachable("Unhandled DebugMap object"); 
      }); 
  GeneralLinker.setSwiftInterfacesMap(&ParseableSwiftInterfaces); 
 
  for (const auto &Obj : Map.objects()) { 
    // N_AST objects (swiftmodule files) should get dumped directly into the 
    // appropriate DWARF section. 
    if (Obj->getType() == MachO::N_AST) { 
      if (Options.Verbose) 
        outs() << "DEBUG MAP OBJECT: " << Obj->getObjectFilename() << "\n"; 
 
      StringRef File = Obj->getObjectFilename(); 
      auto ErrorOrMem = MemoryBuffer::getFile(File); 
      if (!ErrorOrMem) { 
        warn("Could not open '" + File + "'\n"); 
        continue; 
      } 
      sys::fs::file_status Stat; 
      if (auto Err = sys::fs::status(File, Stat)) { 
        warn(Err.message()); 
        continue; 
      } 
      if (!Options.NoTimestamp) { 
        // The modification can have sub-second precision so we need to cast 
        // away the extra precision that's not present in the debug map. 
        auto ModificationTime = 
            std::chrono::time_point_cast<std::chrono::seconds>( 
                Stat.getLastModificationTime()); 
        if (ModificationTime != Obj->getTimestamp()) { 
          // Not using the helper here as we can easily stream TimePoint<>. 
          WithColor::warning()
              << File << ": timestamp mismatch between swift interface file ("
              << sys::TimePoint<>(Obj->getTimestamp()) << ") and debug map ("
              << sys::TimePoint<>(Obj->getTimestamp()) << ")\n";
          continue; 
        } 
      } 
 
      // Copy the module into the .swift_ast section. 
      if (!Options.NoOutput) 
        Streamer->emitSwiftAST((*ErrorOrMem)->getBuffer()); 
 
      continue; 
    } 
 
    if (auto ErrorOrObj = loadObject(*Obj, Map, RL)) 
      GeneralLinker.addObjectFile(*ErrorOrObj); 
    else { 
      ObjectsForLinking.push_back(std::make_unique<DWARFFile>(
          Obj->getObjectFilename(), nullptr, nullptr, 
          Obj->empty() ? Obj->getWarnings() : EmptyWarnings)); 
      GeneralLinker.addObjectFile(*ObjectsForLinking.back()); 
    } 
  } 
 
  // link debug info for loaded object files. 
  GeneralLinker.link(); 
 
  StringRef ArchName = Map.getTriple().getArchName(); 
  if (Error E = emitRemarks(Options, Map.getBinaryPath(), ArchName, RL)) 
    return error(toString(std::move(E))); 
 
  if (Options.NoOutput) 
    return true; 
 
  if (Options.ResourceDir && !ParseableSwiftInterfaces.empty()) { 
    StringRef ArchName = Triple::getArchTypeName(Map.getTriple().getArch()); 
    if (auto E = 
            copySwiftInterfaces(ParseableSwiftInterfaces, ArchName, Options)) 
      return error(toString(std::move(E))); 
  } 
 
  if (Map.getTriple().isOSDarwin() && !Map.getBinaryPath().empty() && 
      Options.FileType == OutputFileType::Object) 
    return MachOUtils::generateDsymCompanion( 
        Options.VFS, Map, Options.Translator, 
        *Streamer->getAsmPrinter().OutStreamer, OutFile); 
 
  Streamer->finish(); 
  return true; 
} 
 
static bool isMachOPairedReloc(uint64_t RelocType, uint64_t Arch) { 
  switch (Arch) { 
  case Triple::x86: 
    return RelocType == MachO::GENERIC_RELOC_SECTDIFF || 
           RelocType == MachO::GENERIC_RELOC_LOCAL_SECTDIFF; 
  case Triple::x86_64: 
    return RelocType == MachO::X86_64_RELOC_SUBTRACTOR; 
  case Triple::arm: 
  case Triple::thumb: 
    return RelocType == MachO::ARM_RELOC_SECTDIFF || 
           RelocType == MachO::ARM_RELOC_LOCAL_SECTDIFF || 
           RelocType == MachO::ARM_RELOC_HALF || 
           RelocType == MachO::ARM_RELOC_HALF_SECTDIFF; 
  case Triple::aarch64: 
    return RelocType == MachO::ARM64_RELOC_SUBTRACTOR; 
  default: 
    return false; 
  } 
} 
 
/// Iterate over the relocations of the given \p Section and 
/// store the ones that correspond to debug map entries into the 
/// ValidRelocs array. 
void DwarfLinkerForBinary::AddressManager::findValidRelocsMachO( 
    const object::SectionRef &Section, const object::MachOObjectFile &Obj, 
    const DebugMapObject &DMO, std::vector<ValidReloc> &ValidRelocs) {
  Expected<StringRef> ContentsOrErr = Section.getContents(); 
  if (!ContentsOrErr) { 
    consumeError(ContentsOrErr.takeError()); 
    Linker.reportWarning("error reading section", DMO.getObjectFilename()); 
    return; 
  } 
  DataExtractor Data(*ContentsOrErr, Obj.isLittleEndian(), 0); 
  bool SkipNext = false; 
 
  for (const object::RelocationRef &Reloc : Section.relocations()) { 
    if (SkipNext) { 
      SkipNext = false; 
      continue; 
    } 
 
    object::DataRefImpl RelocDataRef = Reloc.getRawDataRefImpl(); 
    MachO::any_relocation_info MachOReloc = Obj.getRelocation(RelocDataRef); 
 
    if (isMachOPairedReloc(Obj.getAnyRelocationType(MachOReloc), 
                           Obj.getArch())) { 
      SkipNext = true; 
      Linker.reportWarning("unsupported relocation in " + *Section.getName() +
                               " section.",
                           DMO.getObjectFilename()); 
      continue; 
    } 
 
    unsigned RelocSize = 1 << Obj.getAnyRelocationLength(MachOReloc); 
    uint64_t Offset64 = Reloc.getOffset(); 
    if ((RelocSize != 4 && RelocSize != 8)) { 
      Linker.reportWarning("unsupported relocation in " + *Section.getName() +
                               " section.",
                           DMO.getObjectFilename()); 
      continue; 
    } 
    uint64_t OffsetCopy = Offset64; 
    // Mach-o uses REL relocations, the addend is at the relocation offset. 
    uint64_t Addend = Data.getUnsigned(&OffsetCopy, RelocSize); 
    uint64_t SymAddress; 
    int64_t SymOffset; 
 
    if (Obj.isRelocationScattered(MachOReloc)) { 
      // The address of the base symbol for scattered relocations is 
      // stored in the reloc itself. The actual addend will store the 
      // base address plus the offset. 
      SymAddress = Obj.getScatteredRelocationValue(MachOReloc); 
      SymOffset = int64_t(Addend) - SymAddress; 
    } else { 
      SymAddress = Addend; 
      SymOffset = 0; 
    } 
 
    auto Sym = Reloc.getSymbol(); 
    if (Sym != Obj.symbol_end()) { 
      Expected<StringRef> SymbolName = Sym->getName(); 
      if (!SymbolName) { 
        consumeError(SymbolName.takeError()); 
        Linker.reportWarning("error getting relocation symbol name.", 
                             DMO.getObjectFilename()); 
        continue; 
      } 
      if (const auto *Mapping = DMO.lookupSymbol(*SymbolName)) 
        ValidRelocs.emplace_back(Offset64, RelocSize, Addend, Mapping); 
    } else if (const auto *Mapping = DMO.lookupObjectAddress(SymAddress)) { 
      // Do not store the addend. The addend was the address of the symbol in 
      // the object file, the address in the binary that is stored in the debug 
      // map doesn't need to be offset. 
      ValidRelocs.emplace_back(Offset64, RelocSize, SymOffset, Mapping); 
    } 
  } 
} 
 
/// Dispatch the valid relocation finding logic to the 
/// appropriate handler depending on the object file format. 
bool DwarfLinkerForBinary::AddressManager::findValidRelocs( 
    const object::SectionRef &Section, const object::ObjectFile &Obj, 
    const DebugMapObject &DMO, std::vector<ValidReloc> &Relocs) {
  // Dispatch to the right handler depending on the file type. 
  if (auto *MachOObj = dyn_cast<object::MachOObjectFile>(&Obj)) 
    findValidRelocsMachO(Section, *MachOObj, DMO, Relocs);
  else 
    Linker.reportWarning(Twine("unsupported object file type: ") + 
                             Obj.getFileName(), 
                         DMO.getObjectFilename()); 
  if (Relocs.empty())
    return false; 
 
  // Sort the relocations by offset. We will walk the DIEs linearly in 
  // the file, this allows us to just keep an index in the relocation 
  // array that we advance during our walk, rather than resorting to 
  // some associative container. See DwarfLinkerForBinary::NextValidReloc. 
  llvm::sort(Relocs);
  return true; 
} 
 
/// Look for relocations in the debug_info and debug_addr section that match
/// entries in the debug map. These relocations will drive the Dwarf link by
/// indicating which DIEs refer to symbols present in the linked binary.
/// \returns whether there are any valid relocations in the debug info. 
bool DwarfLinkerForBinary::AddressManager::findValidRelocsInDebugSections(
    const object::ObjectFile &Obj, const DebugMapObject &DMO) { 
  // Find the debug_info section. 
  bool FoundValidRelocs = false;
  for (const object::SectionRef &Section : Obj.sections()) { 
    StringRef SectionName; 
    if (Expected<StringRef> NameOrErr = Section.getName()) 
      SectionName = *NameOrErr; 
    else 
      consumeError(NameOrErr.takeError()); 
 
    SectionName = SectionName.substr(SectionName.find_first_not_of("._")); 
    if (SectionName == "debug_info")
      FoundValidRelocs |=
          findValidRelocs(Section, Obj, DMO, ValidDebugInfoRelocs);
    if (SectionName == "debug_addr")
      FoundValidRelocs |=
          findValidRelocs(Section, Obj, DMO, ValidDebugAddrRelocs);
  } 
  return FoundValidRelocs;
} 
 
bool DwarfLinkerForBinary::AddressManager::hasValidDebugAddrRelocationAt(
    uint64_t Offset) {
  auto It = std::lower_bound(ValidDebugAddrRelocs.begin(),
                             ValidDebugAddrRelocs.end(), Offset);
  return It != ValidDebugAddrRelocs.end();
}

bool DwarfLinkerForBinary::AddressManager::hasValidDebugInfoRelocationAt(
    uint64_t StartOffset, uint64_t EndOffset, CompileUnit::DIEInfo &Info) { 
  assert(NextValidReloc == 0 || 
         StartOffset > ValidDebugInfoRelocs[NextValidReloc - 1].Offset);
  if (NextValidReloc >= ValidDebugInfoRelocs.size())
    return false; 
 
  uint64_t RelocOffset = ValidDebugInfoRelocs[NextValidReloc].Offset;
 
  // We might need to skip some relocs that we didn't consider. For 
  // example the high_pc of a discarded DIE might contain a reloc that 
  // is in the list because it actually corresponds to the start of a 
  // function that is in the debug map. 
  while (RelocOffset < StartOffset &&
         NextValidReloc < ValidDebugInfoRelocs.size() - 1)
    RelocOffset = ValidDebugInfoRelocs[++NextValidReloc].Offset;
 
  if (RelocOffset < StartOffset || RelocOffset >= EndOffset) 
    return false; 
 
  const auto &ValidReloc = ValidDebugInfoRelocs[NextValidReloc++];
  const auto &Mapping = ValidReloc.Mapping->getValue(); 
  const uint64_t BinaryAddress = Mapping.BinaryAddress; 
  const uint64_t ObjectAddress = Mapping.ObjectAddress 
                                     ? uint64_t(*Mapping.ObjectAddress) 
                                     : std::numeric_limits<uint64_t>::max(); 
  if (Linker.Options.Verbose) 
    outs() << "Found valid debug map entry: " << ValidReloc.Mapping->getKey() 
           << "\t" 
           << format("0x%016" PRIx64 " => 0x%016" PRIx64 "\n", ObjectAddress, 
                     BinaryAddress); 
 
  Info.AddrAdjust = BinaryAddress + ValidReloc.Addend; 
  if (Mapping.ObjectAddress) 
    Info.AddrAdjust -= ObjectAddress; 
  Info.InDebugMap = true; 
  return true; 
} 
 
/// Get the starting and ending (exclusive) offset for the
/// attribute with index \p Idx descibed by \p Abbrev. \p Offset is
/// supposed to point to the position of the first attribute described
/// by \p Abbrev.
/// \return [StartOffset, EndOffset) as a pair.
static std::pair<uint64_t, uint64_t>
getAttributeOffsets(const DWARFAbbreviationDeclaration *Abbrev, unsigned Idx,
                    uint64_t Offset, const DWARFUnit &Unit) {
  DataExtractor Data = Unit.getDebugInfoExtractor();

  for (unsigned I = 0; I < Idx; ++I)
    DWARFFormValue::skipValue(Abbrev->getFormByIndex(I), Data, &Offset,
                              Unit.getFormParams());

  uint64_t End = Offset;
  DWARFFormValue::skipValue(Abbrev->getFormByIndex(Idx), Data, &End,
                            Unit.getFormParams());

  return std::make_pair(Offset, End);
}

bool DwarfLinkerForBinary::AddressManager::hasLiveMemoryLocation(
    const DWARFDie &DIE, CompileUnit::DIEInfo &MyInfo) {
  const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();

  Optional<uint32_t> LocationIdx =
      Abbrev->findAttributeIndex(dwarf::DW_AT_location);
  if (!LocationIdx)
    return false;

  uint64_t Offset = DIE.getOffset() + getULEB128Size(Abbrev->getCode());
  uint64_t LocationOffset, LocationEndOffset;
  std::tie(LocationOffset, LocationEndOffset) =
      getAttributeOffsets(Abbrev, *LocationIdx, Offset, *DIE.getDwarfUnit());

  // FIXME: Support relocations debug_addr.
  return hasValidDebugInfoRelocationAt(LocationOffset, LocationEndOffset,
                                       MyInfo);
}

bool DwarfLinkerForBinary::AddressManager::hasLiveAddressRange(
    const DWARFDie &DIE, CompileUnit::DIEInfo &MyInfo) {
  const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();

  Optional<uint32_t> LowPcIdx = Abbrev->findAttributeIndex(dwarf::DW_AT_low_pc);
  if (!LowPcIdx)
    return false;

  dwarf::Form Form = Abbrev->getFormByIndex(*LowPcIdx);

  if (Form == dwarf::DW_FORM_addr) {
    uint64_t Offset = DIE.getOffset() + getULEB128Size(Abbrev->getCode());
    uint64_t LowPcOffset, LowPcEndOffset;
    std::tie(LowPcOffset, LowPcEndOffset) =
        getAttributeOffsets(Abbrev, *LowPcIdx, Offset, *DIE.getDwarfUnit());
    return hasValidDebugInfoRelocationAt(LowPcOffset, LowPcEndOffset, MyInfo);
  }

  if (Form == dwarf::DW_FORM_addrx) {
    Optional<DWARFFormValue> AddrValue = DIE.find(dwarf::DW_AT_low_pc);
    return hasValidDebugAddrRelocationAt(*AddrValue->getAsAddress());
  }

  return false;
}
/// Apply the valid relocations found by findValidRelocs() to 
/// the buffer \p Data, taking into account that Data is at \p BaseOffset 
/// in the debug_info section. 
/// 
/// Like for findValidRelocs(), this function must be called with 
/// monotonic \p BaseOffset values. 
/// 
/// \returns whether any reloc has been applied. 
bool DwarfLinkerForBinary::AddressManager::applyValidRelocs( 
    MutableArrayRef<char> Data, uint64_t BaseOffset, bool IsLittleEndian) { 
  assert(areRelocationsResolved()); 
  assert((NextValidReloc == 0 || 
          BaseOffset > ValidDebugInfoRelocs[NextValidReloc - 1].Offset) &&
         "BaseOffset should only be increasing."); 
  if (NextValidReloc >= ValidDebugInfoRelocs.size())
    return false; 
 
  // Skip relocs that haven't been applied. 
  while (NextValidReloc < ValidDebugInfoRelocs.size() &&
         ValidDebugInfoRelocs[NextValidReloc].Offset < BaseOffset)
    ++NextValidReloc; 
 
  bool Applied = false; 
  uint64_t EndOffset = BaseOffset + Data.size(); 
  while (NextValidReloc < ValidDebugInfoRelocs.size() &&
         ValidDebugInfoRelocs[NextValidReloc].Offset >= BaseOffset &&
         ValidDebugInfoRelocs[NextValidReloc].Offset < EndOffset) {
    const auto &ValidReloc = ValidDebugInfoRelocs[NextValidReloc++];
    assert(ValidReloc.Offset - BaseOffset < Data.size()); 
    assert(ValidReloc.Offset - BaseOffset + ValidReloc.Size <= Data.size()); 
    char Buf[8]; 
    uint64_t Value = ValidReloc.Mapping->getValue().BinaryAddress; 
    Value += ValidReloc.Addend; 
    for (unsigned I = 0; I != ValidReloc.Size; ++I) { 
      unsigned Index = IsLittleEndian ? I : (ValidReloc.Size - I - 1); 
      Buf[I] = uint8_t(Value >> (Index * 8)); 
    } 
    assert(ValidReloc.Size <= sizeof(Buf)); 
    memcpy(&Data[ValidReloc.Offset - BaseOffset], Buf, ValidReloc.Size); 
    Applied = true; 
  } 
 
  return Applied; 
} 
 
llvm::Expected<uint64_t>
DwarfLinkerForBinary::AddressManager::relocateIndexedAddr(uint64_t Offset) {
  auto It = std::lower_bound(ValidDebugAddrRelocs.begin(),
                             ValidDebugAddrRelocs.end(), Offset);
  if (It == ValidDebugAddrRelocs.end())
    return createStringError(
        std::make_error_code(std::errc::invalid_argument),
        "no relocation for offset %llu in debug_addr section", Offset);
  return It->Mapping->getValue().BinaryAddress + It->Addend;
}

bool linkDwarf(raw_fd_ostream &OutFile, BinaryHolder &BinHolder, 
               const DebugMap &DM, LinkOptions Options) { 
  DwarfLinkerForBinary Linker(OutFile, BinHolder, std::move(Options)); 
  return Linker.link(DM); 
} 
 
} // namespace dsymutil 
} // namespace llvm