[dsymutil][DWARFLinker][NFC] make AddressManager not depending on the order of checks for relocations.

[avl]

Summary

Current dsymutil implementation of hasLiveMemoryLocation()/hasLiveAddressRange()
and applyValidRelocs() assume that calls should be done in certain order
(from first Dies to last). Multi-thread implementation might call these methods
in other order(it might process compilation units in order other than they are physically
located), so we remove restriction that searching for relocations should be done
in ascending order. This change does not introduce noticable performance degradation.
The testing results for clang binary:

golden-dsymutil/dsymutil 23787992
clang MD5: 5efa8fd9355ebf81b65f24db5375caa2
elapsed time=91sec

build-Release/bin/dsymutil 23855616
clang MD5: 5efa8fd9355ebf81b65f24db5375caa2
elapsed time=91sec

[avl]

ping

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinkerForBinary.h

93

Can we return a list of relocations as an alternative to using a callback?

[avl]

llvm/tools/dsymutil/DwarfLinkerForBinary.h

93

I like that callback approach since it allows not to move/copy/resize/fill containers. But if you think it would be better to return list of found relocations then I would change it accordingly.

[JDevlieghere]

llvm/tools/dsymutil/DwarfLinkerForBinary.h

93

Personally I find callbacks always make it harder to reason about things. If there's not measurable performance overhead I'd prefer returning a list, but otherwise I'm find with a callback.

[avl]

llvm/tools/dsymutil/DwarfLinkerForBinary.h

93

In this concrete case there is no performance difference. So I changed to the container.

[avl]

rebased. changed enumerator to the container.

[avl]

ping.

[avl]

ping.

[JDevlieghere]

LGTM

llvm/include/llvm/DebugInfo/DWARF/DWARFUnit.h

309

Newline

llvm/include/llvm/DWARFLinker/DWARFLinker.h

public:
   virtual ~AddressesMap();
 
   /// Returns true if represented addresses are from linked file.
   /// Returns false if represented addresses are from not-linked
   /// object file.
   virtual bool areRelocationsResolved() const = 0;
 
   /// Checks that there are valid relocations against a .debug_info
-  /// section. Reset current relocation pointer if neccessary.
-  virtual bool hasValidRelocs(bool ResetRelocsPtr = true) = 0;
+  /// section.
+  virtual bool hasValidRelocs() = 0;
 
   /// Checks that the specified DIE has a DW_AT_Location attribute
-  /// that references into a live code section. This function
-  /// must be called with DIE offsets in strictly ascending order.
+  /// that references into a live code section.
+  ///
+  /// \returns true and sets Info.InDebugMap if it is the case.
   virtual bool hasLiveMemoryLocation(const DWARFDie &DIE,
                                      CompileUnit::DIEInfo &Info) = 0;
 
   /// Checks that the specified DIE has a DW_AT_Low_pc attribute
-  /// that references into a live code section. This function
-  /// must be called with DIE offsets in strictly ascending order.
+  /// that references into a live code section.
+  ///
+  /// \returns true and sets Info.InDebugMap if it is the case.
   virtual bool hasLiveAddressRange(const DWARFDie &DIE,
                                    CompileUnit::DIEInfo &Info) = 0;
 
   /// Apply the valid relocations to the buffer \p Data, taking into
   /// account that Data is at \p BaseOffset in the debug_info section.
   ///
-  /// This function must be called with monotonic \p BaseOffset values.
-  ///
   /// \returns true whether any reloc has been applied.
   virtual bool applyValidRelocs(MutableArrayRef<char> Data, uint64_t BaseOffset,
                                 bool IsLittleEndian) = 0;
 
   /// Relocate the given address offset if a valid relocation exists.
-  virtual llvm::Expected<uint64_t> relocateIndexedAddr(uint64_t Offset) = 0;
+  virtual llvm::Expected<uint64_t> relocateIndexedAddr(uint64_t StartOffset,
+                                                       uint64_t EndOffset) = 0;
 
   /// Returns all valid functions address ranges(i.e., those ranges
   /// which points to sections with code).
   virtual RangesTy &getValidAddressRanges() = 0;
 
   /// Erases all data.
   virtual void clear() = 0;
 };

llvm/include/llvm/DebugInfo/DWARF/DWARFUnit.h

public:
   const DWARFSection &getStringOffsetSection() const {
     return StringOffsetSection;
   }
 
   void setAddrOffsetSection(const DWARFSection *AOS, uint64_t Base) {
     AddrOffsetSection = AOS;
     AddrOffsetSectionBase = Base;
   }
 
+  Optional<uint64_t> getAddrOffsetSectionBase() const {
+    return AddrOffsetSectionBase;
+  }
+
   /// Recursively update address to Die map.
   void updateAddressDieMap(DWARFDie Die);
 
   void setRangesSection(const DWARFSection *RS, uint64_t Base) {
     RangeSection = RS;
     RangeSectionBase = Base;
   }
 

llvm/lib/DWARFLinker/DWARFLinker.cpp

unsigned DWARFLinker::DIECloner::cloneBlockAttribute(
 
   Die.addValue(DIEAlloc, Value);
   return AttrSize;
 }
 
 unsigned DWARFLinker::DIECloner::cloneAddressAttribute(
     DIE &Die, AttributeSpec AttrSpec, const DWARFFormValue &Val,
     const CompileUnit &Unit, AttributesInfo &Info) {
-  dwarf::Form Form = AttrSpec.Form;
-  uint64_t Addr = *Val.getAsAddress();
-
   if (LLVM_UNLIKELY(Linker.Options.Update)) {
     if (AttrSpec.Attr == dwarf::DW_AT_low_pc)
       Info.HasLowPc = true;
     Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
-                 dwarf::Form(AttrSpec.Form), DIEInteger(Addr));
+                 dwarf::Form(AttrSpec.Form), DIEInteger(Val.getRawUValue()));
     return Unit.getOrigUnit().getAddressByteSize();
   }
 
+  dwarf::Form Form = AttrSpec.Form;
+  uint64_t Addr = 0;
+  if (Form == dwarf::DW_FORM_addrx) {
+    if (Optional<uint64_t> AddrOffsetSectionBase =
+            Unit.getOrigUnit().getAddrOffsetSectionBase()) {
+      uint64_t StartOffset = *AddrOffsetSectionBase + Val.getRawUValue();
+      uint64_t EndOffset =
+          StartOffset + Unit.getOrigUnit().getAddressByteSize();
+      if (llvm::Expected<uint64_t> RelocAddr =
+              ObjFile.Addresses->relocateIndexedAddr(StartOffset, EndOffset))
+        Addr = *RelocAddr;
+      else
+        Linker.reportWarning(toString(RelocAddr.takeError()), ObjFile);
+    } else
+      Linker.reportWarning("no base offset for address table", ObjFile);
+
+    // If this is an indexed address emit the debug_info address.
+    Form = dwarf::DW_FORM_addr;
+  } else
+    Addr = *Val.getAsAddress();
+
   if (AttrSpec.Attr == dwarf::DW_AT_low_pc) {
     if (Die.getTag() == dwarf::DW_TAG_inlined_subroutine ||
         Die.getTag() == dwarf::DW_TAG_lexical_block)
       // The low_pc of a block or inline subroutine might get
       // relocated because it happens to match the low_pc of the
       // enclosing subprogram. To prevent issues with that, always use
       // the low_pc from the input DIE if relocations have been applied.
       Addr = (Info.OrigLowPc != std::numeric_limits<uint64_t>::max()
if (Die.getTag() == dwarf::DW_TAG_call_site)
       Addr = (Info.OrigCallReturnPc ? Info.OrigCallReturnPc : Addr) +
              Info.PCOffset;
   } else if (AttrSpec.Attr == dwarf::DW_AT_call_pc) {
     // Relocate the address of a branch instruction within a call site entry.
     if (Die.getTag() == dwarf::DW_TAG_call_site)
       Addr = (Info.OrigCallPc ? Info.OrigCallPc : Addr) + Info.PCOffset;
   }
 
-  // If this is an indexed address emit the relocated address.
-  if (Form == dwarf::DW_FORM_addrx) {
-    if (llvm::Expected<uint64_t> RelocAddr =
-            ObjFile.Addresses->relocateIndexedAddr(Addr)) {
-      Addr = *RelocAddr;
-      Form = dwarf::DW_FORM_addr;
-    } else {
-      Linker.reportWarning(toString(RelocAddr.takeError()), ObjFile);
-    }
-  }
-
   Die.addValue(DIEAlloc, static_cast<dwarf::Attribute>(AttrSpec.Attr),
                static_cast<dwarf::Form>(Form), DIEInteger(Addr));
   return Unit.getOrigUnit().getAddressByteSize();
 }
 
 unsigned DWARFLinker::DIECloner::cloneScalarAttribute(
     DIE &Die, const DWARFDie &InputDIE, const DWARFFile &File,
     CompileUnit &Unit, AttributeSpec AttrSpec, const DWARFFormValue &Val,

llvm/test/tools/dsymutil/X86/dwarf5.test

 DWARF:   DW_AT_comp_dir    ("/private/tmp/dwarf5")
 DWARF:   DW_AT_low_pc      (0x0000000100003f80)
 DWARF:   DW_AT_high_pc     (0x0000000100003fb1)
 DWARF:   DW_AT_addr_base   (0x00000008)
 DWARF:   DW_TAG_subprogram
 DWARF:     DW_AT_name      ("foo")
 DWARF:     DW_AT_decl_file (0x00)
 DWARF:     DW_AT_decl_line (2)
-DWARF:     DW_AT_type      (0x0000006c "int")
+DWARF:     DW_AT_type      (0x00000091 "int")
 DWARF:     DW_AT_external  (true)
 DWARF:     DW_TAG_variable
 DWARF:       DW_AT_name    ("i")
 DWARF:       DW_AT_decl_file       (0x00)
 DWARF:       DW_AT_decl_line       (3)
-DWARF:       DW_AT_type    (0x00000073 "volatile int")
+DWARF:       DW_AT_type    (0x00000098 "volatile int")
 DWARF:   DW_TAG_subprogram
 DWARF:     DW_AT_name      ("main")
 DWARF:     DW_AT_decl_file (0x00)
 DWARF:     DW_AT_decl_line (7)
 DWARF:     DW_AT_prototyped        (true)
-DWARF:     DW_AT_type      (0x0000006c "int")
+DWARF:     DW_AT_type      (0x00000091 "int")
 DWARF:     DW_AT_external  (true)
 DWARF:     DW_TAG_formal_parameter
 DWARF:       DW_AT_name    ("argc")
 DWARF:       DW_AT_decl_file       (0x00)
 DWARF:       DW_AT_decl_line       (7)
-DWARF:       DW_AT_type    (0x0000006c "int")
+DWARF:       DW_AT_type    (0x00000091 "int")
 DWARF:     DW_TAG_formal_parameter
 DWARF:       DW_AT_name    ("argv")
 DWARF:       DW_AT_decl_file       (0x00)
 DWARF:       DW_AT_decl_line       (7)
-DWARF:       DW_AT_type    (0x00000078 "char**")
+DWARF:       DW_AT_type    (0x0000009d "char**")

llvm/tools/dsymutil/DwarfLinkerForBinary.h

class AddressManager : public AddressesMap {
 
     /// The valid relocations for the current DebugMapObject.
     /// This vector is sorted by relocation offset.
     /// {
     std::vector<ValidReloc> ValidDebugInfoRelocs;
     std::vector<ValidReloc> ValidDebugAddrRelocs;
     /// }
 
-    /// Index into ValidRelocs of the next relocation to consider. As we walk
-    /// the DIEs in acsending file offset and as ValidRelocs is sorted by file
-    /// offset, keeping this index up to date is all we have to do to have a
-    /// cheap lookup during the root DIE selection and during DIE cloning.
-    unsigned NextValidReloc = 0;
-
     RangesTy AddressRanges;
 
+    StringRef SrcFileName;
+
+    /// Returns list of valid relocations from \p Relocs,
+    /// between \p StartOffset and \p NextOffset.
+    ///
+    /// \returns true if any relocation is found.
+    std::vector<ValidReloc>
+    getRelocations(const std::vector<ValidReloc> &Relocs, uint64_t StartPos,
+                   uint64_t EndPos);
+
+    /// Resolve specified relocation \p Reloc.
+    ///
+    /// \returns resolved value.
+    uint64_t relocate(const ValidReloc &Reloc) const;
+
+    /// Fill \p Info with address information for the specified \p Reloc.
+    void fillDieInfo(const ValidReloc &Reloc, CompileUnit::DIEInfo &Info);
+
+    /// Print contents of debug map entry for the specified \p Reloc.
+    void printReloc(const ValidReloc &Reloc);
+
   public:
     AddressManager(DwarfLinkerForBinary &Linker, const object::ObjectFile &Obj,
                    const DebugMapObject &DMO)
-        : Linker(Linker) {
+        : Linker(Linker), SrcFileName(DMO.getObjectFilename()) {
       findValidRelocsInDebugSections(Obj, DMO);
 
       // Iterate over the debug map entries and put all the ones that are
       // functions (because they have a size) into the Ranges map. This map is
       // very similar to the FunctionRanges that are stored in each unit, with 2
       // notable differences:
       //
       //  1. Obviously this one is global, while the other ones are per-unit.
AddressManager(DwarfLinkerForBinary &Linker, const object::ObjectFile &Obj,
               *Mapping.ObjectAddress + Mapping.Size,
               int64_t(Mapping.BinaryAddress) - *Mapping.ObjectAddress);
       }
     }
     virtual ~AddressManager() override { clear(); }
 
     virtual bool areRelocationsResolved() const override { return true; }
 
-    bool hasValidRelocs(bool ResetRelocsPtr = true) override {
-      if (ResetRelocsPtr)
-        NextValidReloc = 0;
+    bool hasValidRelocs() override {
       return !ValidDebugInfoRelocs.empty() || !ValidDebugAddrRelocs.empty();
     }
 
     /// \defgroup FindValidRelocations Translate debug map into a list
     /// of relevant relocations
     ///
     /// @{
     bool findValidRelocsInDebugSections(const object::ObjectFile &Obj,
                                         const DebugMapObject &DMO);
 
     bool findValidRelocs(const object::SectionRef &Section,
                          const object::ObjectFile &Obj,
                          const DebugMapObject &DMO,
                          std::vector<ValidReloc> &ValidRelocs);
 
     void findValidRelocsMachO(const object::SectionRef &Section,
                               const object::MachOObjectFile &Obj,
                               const DebugMapObject &DMO,
                               std::vector<ValidReloc> &ValidRelocs);
     /// @}
 
-    /// Checks that there is a relocation in the debug_addr section  against a
+    /// Checks that there is a relocation in the \p Relocs array against a
     /// debug map entry between \p StartOffset and \p NextOffset.
     ///
-    /// This function must be called with offsets in strictly ascending order
-    /// because it never looks back at relocations it already 'went past'.
     /// \returns true and sets Info.InDebugMap if it is the case.
-    bool hasValidDebugInfoRelocationAt(uint64_t StartOffset, uint64_t EndOffset,
-                                       CompileUnit::DIEInfo &Info);
+    bool hasValidRelocationAt(const std::vector<ValidReloc> &Relocs,
+                              uint64_t StartOffset, uint64_t EndOffset,
 
-    /// Checks that there is a relocation in the debug_addr section against a
-    /// debug map entry at the given offset.
-    bool hasValidDebugAddrRelocationAt(uint64_t Offset);
-
     bool hasLiveMemoryLocation(const DWARFDie &DIE,
                                CompileUnit::DIEInfo &Info) override;
     bool hasLiveAddressRange(const DWARFDie &DIE,
                              CompileUnit::DIEInfo &Info) override;
 
     bool applyValidRelocs(MutableArrayRef<char> Data, uint64_t BaseOffset,
                           bool IsLittleEndian) override;
 
-    llvm::Expected<uint64_t> relocateIndexedAddr(uint64_t Offset) override;
+    llvm::Expected<uint64_t> relocateIndexedAddr(uint64_t StartOffset,
+                                                 uint64_t EndOffset) override;
 
     RangesTy &getValidAddressRanges() override { return AddressRanges; }
 
     void clear() override {
       AddressRanges.clear();
       ValidDebugInfoRelocs.clear();
       ValidDebugAddrRelocs.clear();
-      NextValidReloc = 0;
     }
   };
 
 private:
   /// \defgroup Helpers Various helper methods.
   ///
   /// @{
   bool createStreamer(const Triple &TheTriple, raw_fd_ostream &OutFile);

llvm/tools/dsymutil/DwarfLinkerForBinary.cpp

if (SectionName == "debug_info")
           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 = lower_bound(ValidDebugAddrRelocs, 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;
+std::vector<DwarfLinkerForBinary::AddressManager::ValidReloc>
+DwarfLinkerForBinary::AddressManager::getRelocations(
+    const std::vector<ValidReloc> &Relocs, uint64_t StartPos, uint64_t EndPos) {
+  std::vector<DwarfLinkerForBinary::AddressManager::ValidReloc> Res;
 
-  uint64_t RelocOffset = ValidDebugInfoRelocs[NextValidReloc].Offset;
+  auto CurReloc = partition_point(Relocs, [StartPos](const ValidReloc &Reloc) {
+    return Reloc.Offset < StartPos;
+  });
 
-  // 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;
+  while (CurReloc != Relocs.end() && CurReloc->Offset >= StartPos &&
+         CurReloc->Offset < EndPos) {
+    Res.push_back(*CurReloc);
+    CurReloc++;
+  }
 
-  if (RelocOffset < StartOffset || RelocOffset >= EndOffset)
-    return false;
+  return Res;
+}
 
-  const auto &ValidReloc = ValidDebugInfoRelocs[NextValidReloc++];
-  const auto &Mapping = ValidReloc.Mapping->getValue();
-  const uint64_t BinaryAddress = Mapping.BinaryAddress;
+void DwarfLinkerForBinary::AddressManager::printReloc(const ValidReloc &Reloc) {
+  const auto &Mapping = Reloc.Mapping->getValue();
   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);
+
+  outs() << "Found valid debug map entry: " << Reloc.Mapping->getKey() << "\t"
+                   uint64_t(Mapping.BinaryAddress));
+}
 
-  Info.AddrAdjust = BinaryAddress + ValidReloc.Addend;
-  if (Mapping.ObjectAddress)
-    Info.AddrAdjust -= ObjectAddress;
+void DwarfLinkerForBinary::AddressManager::fillDieInfo(
+    const ValidReloc &Reloc, CompileUnit::DIEInfo &Info) {
+  Info.AddrAdjust = relocate(Reloc);
+  if (Reloc.Mapping->getValue().ObjectAddress)
+    Info.AddrAdjust -= uint64_t(*Reloc.Mapping->getValue().ObjectAddress);
   Info.InDebugMap = true;
+}
+
+bool DwarfLinkerForBinary::AddressManager::hasValidRelocationAt(
+    const std::vector<ValidReloc> &AllRelocs, uint64_t StartOffset,
+    uint64_t EndOffset, CompileUnit::DIEInfo &Info) {
+  std::vector<ValidReloc> Relocs =
+      getRelocations(AllRelocs, StartOffset, EndOffset);
+
+  if (Relocs.size() == 0)
+    return false;
+
+  if (Linker.Options.Verbose)
+    printReloc(Relocs[0]);
+  fillDieInfo(Relocs[0], Info);
+
   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.
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);
+  return hasValidRelocationAt(ValidDebugInfoRelocs, 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);
+    return hasValidRelocationAt(ValidDebugInfoRelocs, LowPcOffset,
+                                LowPcEndOffset, MyInfo);
   }
 
   if (Form == dwarf::DW_FORM_addrx) {
     Optional<DWARFFormValue> AddrValue = DIE.find(dwarf::DW_AT_low_pc);
-    return hasValidDebugAddrRelocationAt(*AddrValue->getAsAddress());
+    if (Optional<uint64_t> AddrOffsetSectionBase =
+            DIE.getDwarfUnit()->getAddrOffsetSectionBase()) {
+      uint64_t StartOffset = *AddrOffsetSectionBase + AddrValue->getRawUValue();
+      uint64_t EndOffset =
+          StartOffset + DIE.getDwarfUnit()->getAddressByteSize();
+      return hasValidRelocationAt(ValidDebugAddrRelocs, StartOffset, EndOffset,
+                                  MyInfo);
+    } else
+      Linker.reportWarning("no base offset for address table", SrcFileName);
   }
 
   return false;
 }
+
+uint64_t
+DwarfLinkerForBinary::AddressManager::relocate(const ValidReloc &Reloc) const {
+  return Reloc.Mapping->getValue().BinaryAddress + Reloc.Addend;
+}
+
 /// 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;
+  std::vector<ValidReloc> Relocs = getRelocations(
+      ValidDebugInfoRelocs, BaseOffset, BaseOffset + Data.size());
 
-  // 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());
+  for (const ValidReloc &CurReloc : Relocs) {
+    assert(CurReloc.Offset - BaseOffset < Data.size());
+    assert(CurReloc.Offset - BaseOffset + CurReloc.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);
+    uint64_t Value = relocate(CurReloc);
+    for (unsigned I = 0; I != CurReloc.Size; ++I) {
+      unsigned Index = IsLittleEndian ? I : (CurReloc.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;
+    assert(CurReloc.Size <= sizeof(Buf));
+    memcpy(&Data[CurReloc.Offset - BaseOffset], Buf, CurReloc.Size);
   }
 
-  return Applied;
+  return Relocs.size() > 0;
 }
 
 llvm::Expected<uint64_t>
-DwarfLinkerForBinary::AddressManager::relocateIndexedAddr(uint64_t Offset) {
-  auto It = lower_bound(ValidDebugAddrRelocs, Offset);
-  if (It == ValidDebugAddrRelocs.end())
+DwarfLinkerForBinary::AddressManager::relocateIndexedAddr(uint64_t StartOffset,
+                                                          uint64_t EndOffset) {
+  std::vector<ValidReloc> Relocs =
+      getRelocations(ValidDebugAddrRelocs, StartOffset, EndOffset);
+  if (Relocs.size() == 0)
     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;
+        "no relocation for offset %llu in debug_addr section", StartOffset);
+
+  return relocate(Relocs[0]);
 }
 
 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