[NFC][DWARFLinker] Refactor address emitting code.

[avl]

Summary

As a preparation for implementing DWARFv5 address ranges generation,
this patch refactors existing address ranges generation code:
Split emitUnitRangesEntries into two functions emitDwarfDebugArangesTable
and emitDwarfDebugRangesTableFragment. Use AddressRanges to prepare linked
address ranges. Refactor Unit.getLowPc(), to use std::nullopt as undefined value.

[JDevlieghere]

LGTM modulo a few small nits.

llvm/lib/DWARFLinker/DWARFLinker.cpp

1678–1679

Can this be hoisted outside the loop?

llvm/lib/DWARFLinker/DWARFStreamer.cpp

354–358

Do we need the index? IIRC AddressRanges class implemented iterators so we should be able to write:

for(AddressRange Range : LinkedRanges)

376

Similar comment here

415

And here I think

[avl]

addressed comments.

[avl]

llvm/lib/DWARFLinker/DWARFStreamer.cpp

415

In this place we need index as AddressRangesMap(FunctionRanges) does not have iterators.

llvm/include/llvm/DWARFLinker/DWARFLinker.h

public:
   /// Emit Apple Objective-C accelerator table.
   virtual void
   emitAppleObjc(AccelTable<AppleAccelTableStaticOffsetData> &Table) = 0;
 
   /// Emit Apple type accelerator table.
   virtual void
   emitAppleTypes(AccelTable<AppleAccelTableStaticTypeData> &Table) = 0;
 
-  /// Emit .debug_ranges for \p FuncRange by translating the
-  /// original \p Entries.
-  virtual void emitRangesEntries(
-      int64_t UnitPcOffset, uint64_t OrigLowPc,
-      std::optional<std::pair<AddressRange, int64_t>> FuncRange,
-      const std::vector<DWARFDebugRangeList::RangeListEntry> &Entries,
-      unsigned AddressSize) = 0;
+  /// Emit piece of .debug_ranges for \p Ranges.
+  virtual void
+  emitDwarfDebugRangesTableFragment(const CompileUnit &Unit,
+                                    const AddressRanges &LinkedRanges) = 0;
 
   /// Emit .debug_aranges entries for \p Unit and if \p DoRangesSection is true,
   /// also emit the .debug_ranges entries for the DW_TAG_compile_unit's
   /// DW_AT_ranges attribute.
   virtual void emitUnitRangesEntries(CompileUnit &Unit,
                                      bool DoRangesSection) = 0;
 
   /// Copy the .debug_line over to the updated binary while unobfuscating the

llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h

DIEInfo &getInfo(const DWARFDie &Die) {
     unsigned Idx = getOrigUnit().getDIEIndex(Die);
     return Info[Idx];
   }
 
   uint64_t getStartOffset() const { return StartOffset; }
   uint64_t getNextUnitOffset() const { return NextUnitOffset; }
   void setStartOffset(uint64_t DebugInfoSize) { StartOffset = DebugInfoSize; }
 
-  uint64_t getLowPc() const { return LowPc; }
+  std::optional<uint64_t> getLowPc() const { return LowPc; }
   uint64_t getHighPc() const { return HighPc; }
   bool hasLabelAt(uint64_t Addr) const { return Labels.count(Addr); }
 
   std::optional<PatchLocation> getUnitRangesAttribute() const {
     return UnitRangeAttribute;
   }
 
   const RangesTy &getFunctionRanges() const { return Ranges; }
private:
   unsigned ID;
   std::vector<DIEInfo> Info; ///< DIE info indexed by DIE index.
   std::optional<BasicDIEUnit> NewUnit;
   MCSymbol *LabelBegin = nullptr;
 
   uint64_t StartOffset;
   uint64_t NextUnitOffset;
 
-  uint64_t LowPc = std::numeric_limits<uint64_t>::max();
+  std::optional<uint64_t> LowPc;
   uint64_t HighPc = 0;
 
   /// A list of attributes to fixup with the absolute offset of
   /// a DIE in the debug_info section.
   ///
   /// The offsets for the attributes in this array couldn't be set while
   /// cloning because for cross-cu forward references the target DIE's offset
   /// isn't known you emit the reference attribute.

llvm/include/llvm/DWARFLinker/DWARFStreamer.h

public:
   /// Emit the swift_ast section stored in \p Buffer.
   void emitSwiftAST(StringRef Buffer);
 
   /// Emit the swift reflection section stored in \p Buffer.
   void emitSwiftReflectionSection(
       llvm::binaryformat::Swift5ReflectionSectionKind ReflSectionKind,
       StringRef Buffer, uint32_t Alignment, uint32_t Size);
 
-  /// Emit debug_ranges for \p FuncRange by translating the
-  /// original \p Entries.
-  void emitRangesEntries(
-      int64_t UnitPcOffset, uint64_t OrigLowPc,
-      std::optional<std::pair<AddressRange, int64_t>> FuncRange,
-      const std::vector<DWARFDebugRangeList::RangeListEntry> &Entries,
-      unsigned AddressSize) override;
+  /// Emit piece of .debug_ranges for \p Ranges.
+  virtual void
+  emitDwarfDebugRangesTableFragment(const CompileUnit &Unit,
+                                    const AddressRanges &LinkedRanges) override;
 
   /// Emit debug_aranges entries for \p Unit and if \p DoRangesSection is true,
   /// also emit the debug_ranges entries for the DW_TAG_compile_unit's
   /// DW_AT_ranges attribute.
   void emitUnitRangesEntries(CompileUnit &Unit, bool DoRangesSection) override;
 
   uint64_t getRangesSectionSize() const override { return RangesSectionSize; }
 
private:
   inline void warn(const Twine &Warning, StringRef Context = "") {
     if (WarningHandler)
       WarningHandler(Warning, Context, nullptr);
   }
 
   void emitMacroTableImpl(const DWARFDebugMacro *MacroTable,
                           const Offset2UnitMap &UnitMacroMap,
                           OffsetsStringPool &StringPool, uint64_t &OutOffset);
+  void emitDwarfDebugArangesTable(const CompileUnit &Unit,
+                                  const AddressRanges &LinkedRanges);
 
   /// \defgroup MCObjects MC layer objects constructed by the streamer
   /// @{
   std::unique_ptr<MCRegisterInfo> MRI;
   std::unique_ptr<MCAsmInfo> MAI;
   std::unique_ptr<MCObjectFileInfo> MOFI;
   std::unique_ptr<MCContext> MC;
   MCAsmBackend *MAB; // Owned by MCStreamer

llvm/lib/DWARFLinker/DWARFLinker.cpp

if (Die.getTag() == dwarf::DW_TAG_inlined_subroutine ||
       // 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()
                   ? Info.OrigLowPc
                   : Addr) +
              Info.PCOffset;
     } else if (Die.getTag() == dwarf::DW_TAG_compile_unit) {
-      Addr = Unit.getLowPc();
-      if (Addr == std::numeric_limits<uint64_t>::max())
+      if (std::optional<uint64_t> LowPC = Unit.getLowPc())
+        Addr = *LowPC;
+      else
         return 0;
     }
     Info.HasLowPc = true;
   } else if (AttrSpec.Attr == dwarf::DW_AT_high_pc) {
     if (Die.getTag() == dwarf::DW_TAG_compile_unit) {
       if (uint64_t HighPc = Unit.getHighPc())
         Addr = HighPc;
       else
if (AttrSpec.Attr == dwarf::DW_AT_declaration && Value)
       Info.IsDeclaration = true;
     Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
                  dwarf::Form(AttrSpec.Form), DIEInteger(Value));
     return AttrSize;
   }
 
   if (AttrSpec.Attr == dwarf::DW_AT_high_pc &&
       Die.getTag() == dwarf::DW_TAG_compile_unit) {
-    if (Unit.getLowPc() == -1ULL)
+    std::optional<uint64_t> LowPC = Unit.getLowPc();
+    if (!LowPC)
       return 0;
     // Dwarf >= 4 high_pc is an size, not an address.
-    Value = Unit.getHighPc() - Unit.getLowPc();
+    Value = Unit.getHighPc() - *LowPC;
   } else if (AttrSpec.Form == dwarf::DW_FORM_sec_offset)
     Value = *Val.getAsSectionOffset();
   else if (AttrSpec.Form == dwarf::DW_FORM_sdata)
     Value = *Val.getAsSignedConstant();
   else if (auto OptionalValue = Val.getAsUnsignedConstant())
     Value = *OptionalValue;
   else {
     Linker.reportWarning(
void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
                                      DWARFContext &OrigDwarf,
                                      const DWARFFile &File) const {
   DWARFDebugRangeList RangeList;
   const auto &FunctionRanges = Unit.getFunctionRanges();
   unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
   DWARFDataExtractor RangeExtractor(OrigDwarf.getDWARFObj(),
                                     OrigDwarf.getDWARFObj().getRangesSection(),
                                     OrigDwarf.isLittleEndian(), AddressSize);
-  std::optional<std::pair<AddressRange, int64_t>> CurrRange;
+  std::optional<std::pair<AddressRange, int64_t>> CachedRange;
   DWARFUnit &OrigUnit = Unit.getOrigUnit();
   auto OrigUnitDie = OrigUnit.getUnitDIE(false);
-  uint64_t OrigLowPc =
-      dwarf::toAddress(OrigUnitDie.find(dwarf::DW_AT_low_pc), -1ULL);
-  // Ranges addresses are based on the unit's low_pc. Compute the
-  // offset we need to apply to adapt to the new unit's low_pc.
-  int64_t UnitPcOffset = 0;
-  if (OrigLowPc != -1ULL)
-    UnitPcOffset = int64_t(OrigLowPc) - Unit.getLowPc();
+  uint64_t UnitBaseAddress =
+      dwarf::toAddress(OrigUnitDie.find(dwarf::DW_AT_low_pc), 0);
 
   for (const auto &RangeAttribute : Unit.getRangesAttributes()) {
     uint64_t Offset = RangeAttribute.get();
     RangeAttribute.set(TheDwarfEmitter->getRangesSectionSize());
     if (Error E = RangeList.extract(RangeExtractor, &Offset)) {
       llvm::consumeError(std::move(E));
       reportWarning("invalid range list ignored.", File);
       RangeList.clear();
     }
     const auto &Entries = RangeList.getEntries();
+
+    uint64_t BaseAddress = UnitBaseAddress;
+    AddressRanges LinkedRanges;
+
     if (!Entries.empty()) {
-      const DWARFDebugRangeList::RangeListEntry &First = Entries.front();
+      for (const auto &Range : Entries) {
+        if (Range.isBaseAddressSelectionEntry(
+                Unit.getOrigUnit().getAddressByteSize())) {
+          BaseAddress = Range.EndAddress;
+          continue;
+        }
 
-      if (!CurrRange ||
-          !CurrRange->first.contains(First.StartAddress + OrigLowPc)) {
-        CurrRange = FunctionRanges.getRangeValueThatContains(
-            First.StartAddress + OrigLowPc);
-        if (!CurrRange) {
-          reportWarning("no mapping for range.", File);
+        if (!CachedRange ||
+            !CachedRange->first.contains(Range.StartAddress + BaseAddress))
+          CachedRange = FunctionRanges.getRangeValueThatContains(
+              Range.StartAddress + BaseAddress);
+
+        // All range entries should lie in the function range.
+        if (!CachedRange) {
+          reportWarning("inconsistent range data.", File);
           continue;
         }
+
+        LinkedRanges.insert(
+            {Range.StartAddress + BaseAddress + CachedRange->second,
+             Range.EndAddress + BaseAddress + CachedRange->second});
       }
     }
 
-    TheDwarfEmitter->emitRangesEntries(UnitPcOffset, OrigLowPc, CurrRange,
-                                       Entries, AddressSize);
+    TheDwarfEmitter->emitDwarfDebugRangesTableFragment(Unit, LinkedRanges);
   }
 }
 
 /// Generate the debug_aranges entries for \p Unit and if the
 /// unit has a DW_AT_ranges attribute, also emit the debug_ranges
 /// contribution for this attribute.
 /// FIXME: this could actually be done right in patchRangesForUnit,
 /// but for the sake of initial bit-for-bit compatibility with legacy

llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp

 
 void CompileUnit::addLabelLowPc(uint64_t LabelLowPc, int64_t PcOffset) {
   Labels.insert({LabelLowPc, PcOffset});
 }
 
 void CompileUnit::addFunctionRange(uint64_t FuncLowPc, uint64_t FuncHighPc,
                                    int64_t PcOffset) {
   Ranges.insert({FuncLowPc, FuncHighPc}, PcOffset);
-  this->LowPc = std::min(LowPc, FuncLowPc + PcOffset);
+  if (LowPc)
+    LowPc = std::min(*LowPc, FuncLowPc + PcOffset);
+  else
+    LowPc = FuncLowPc + PcOffset;
   this->HighPc = std::max(HighPc, FuncHighPc + PcOffset);
 }
 
 void CompileUnit::noteRangeAttribute(const DIE &Die, PatchLocation Attr) {
   if (Die.getTag() != dwarf::DW_TAG_compile_unit)
     RangeAttributes.push_back(Attr);
   else
     UnitRangeAttribute = Attr;

llvm/lib/DWARFLinker/DWARFStreamer.cpp

MCSection *ReflectionSection =
       MOFI->getSwift5ReflectionSection(ReflSectionKind);
   if (ReflectionSection == nullptr)
     return;
   ReflectionSection->setAlignment(Align(Alignment));
   MS->switchSection(ReflectionSection);
   MS->emitBytes(Buffer);
 }
 
-/// Emit the debug_range section contents for \p FuncRange by
-/// translating the original \p Entries. The debug_range section
-/// format is totally trivial, consisting just of pairs of address
-/// sized addresses describing the ranges.
-void DwarfStreamer::emitRangesEntries(
-    int64_t UnitPcOffset, uint64_t OrigLowPc,
-    std::optional<std::pair<AddressRange, int64_t>> FuncRange,
-    const std::vector<DWARFDebugRangeList::RangeListEntry> &Entries,
-    unsigned AddressSize) {
-  MS->switchSection(MC->getObjectFileInfo()->getDwarfRangesSection());
-
-  // Offset each range by the right amount.
-  int64_t PcOffset =
-      (Entries.empty() || !FuncRange) ? 0 : FuncRange->second + UnitPcOffset;
-  for (const auto &Range : Entries) {
-    if (Range.isBaseAddressSelectionEntry(AddressSize)) {
-      warn("unsupported base address selection operation",
-           "emitting debug_ranges");
-      break;
-    }
-    // Do not emit empty ranges.
-    if (Range.StartAddress == Range.EndAddress)
-      continue;
-
-    // All range entries should lie in the function range.
-    if (!FuncRange->first.contains(Range.StartAddress + OrigLowPc))
-      warn("inconsistent range data.", "emitting debug_ranges");
-    MS->emitIntValue(Range.StartAddress + PcOffset, AddressSize);
-    MS->emitIntValue(Range.EndAddress + PcOffset, AddressSize);
-    RangesSectionSize += 2 * AddressSize;
-  }
-
-  // Add the terminator entry.
-  MS->emitIntValue(0, AddressSize);
-  MS->emitIntValue(0, AddressSize);
-  RangesSectionSize += 2 * AddressSize;
-}
-
-/// Emit the debug_aranges contribution of a unit and
-/// if \p DoDebugRanges is true the debug_range contents for a
-/// compile_unit level DW_AT_ranges attribute (Which are basically the
-/// same thing with a different base address).
-/// Just aggregate all the ranges gathered inside that unit.
-void DwarfStreamer::emitUnitRangesEntries(CompileUnit &Unit,
-                                          bool DoDebugRanges) {
+void DwarfStreamer::emitDwarfDebugArangesTable(
+    const CompileUnit &Unit, const AddressRanges &LinkedRanges) {
   unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
-  // Gather the ranges in a vector, so that we can simplify them. The
-  // IntervalMap will have coalesced the non-linked ranges, but here
-  // we want to coalesce the linked addresses.
-  std::vector<std::pair<uint64_t, uint64_t>> Ranges;
-  const RangesTy &FunctionRanges = Unit.getFunctionRanges();
-  for (size_t Idx = 0; Idx < FunctionRanges.size(); Idx++) {
-    std::pair<AddressRange, int64_t> CurRange = FunctionRanges[Idx];
 
-    Ranges.push_back(std::make_pair(CurRange.first.start() + CurRange.second,
-                                    CurRange.first.end() + CurRange.second));
-  }
-
-  // The object addresses where sorted, but again, the linked
-  // addresses might end up in a different order.
-  llvm::sort(Ranges);
-
-  if (!Ranges.empty()) {
-    MS->switchSection(MC->getObjectFileInfo()->getDwarfARangesSection());
+  // Make .debug_aranges to be current section.
 
-    MCSymbol *BeginLabel = Asm->createTempSymbol("Barange");
-    MCSymbol *EndLabel = Asm->createTempSymbol("Earange");
+  // Emit Header.
 
-    unsigned HeaderSize =
-        sizeof(int32_t) + // Size of contents (w/o this field
-        sizeof(int16_t) + // DWARF ARange version number
-        sizeof(int32_t) + // Offset of CU in the .debug_info section
-        sizeof(int8_t) +  // Pointer Size (in bytes)
-        sizeof(int8_t);   // Segment Size (in bytes)
 
-    unsigned TupleSize = AddressSize * 2;
-    unsigned Padding = offsetToAlignment(HeaderSize, Align(TupleSize));
 
-    Asm->emitLabelDifference(EndLabel, BeginLabel, 4); // Arange length
-    Asm->OutStreamer->emitLabel(BeginLabel);
-    Asm->emitInt16(dwarf::DW_ARANGES_VERSION); // Version number
-    Asm->emitInt32(Unit.getStartOffset());     // Corresponding unit's offset
-    Asm->emitInt8(AddressSize);                // Address size
-    Asm->emitInt8(0);                          // Segment size
 
-    Asm->OutStreamer->emitFill(Padding, 0x0);
 
-    for (auto Range = Ranges.begin(), End = Ranges.end(); Range != End;
-         ++Range) {
-      uint64_t RangeStart = Range->first;
-      MS->emitIntValue(RangeStart, AddressSize);
-      while ((Range + 1) != End && Range->second == (Range + 1)->first)
-        ++Range;
-      MS->emitIntValue(Range->second - RangeStart, AddressSize);
-    }
+  // Emit linked ranges.
+  for (const AddressRange &Range : LinkedRanges) {
+    MS->emitIntValue(Range.start(), AddressSize);
+    MS->emitIntValue(Range.end() - Range.start(), AddressSize);
 
-    // Emit terminator
-    Asm->OutStreamer->emitIntValue(0, AddressSize);
-    Asm->OutStreamer->emitIntValue(0, AddressSize);
-    Asm->OutStreamer->emitLabel(EndLabel);
-  }
+  // Emit terminator.
 
-  if (!DoDebugRanges)
-    return;
+void DwarfStreamer::emitDwarfDebugRangesTableFragment(
+    const CompileUnit &Unit, const AddressRanges &LinkedRanges) {
+  unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
 
+  // Make .debug_ranges to be current section.
   MS->switchSection(MC->getObjectFileInfo()->getDwarfRangesSection());
-  // Offset each range by the right amount.
-  int64_t PcOffset = -Unit.getLowPc();
-  // Emit coalesced ranges.
-  for (auto Range = Ranges.begin(), End = Ranges.end(); Range != End; ++Range) {
-    MS->emitIntValue(Range->first + PcOffset, AddressSize);
-    while (Range + 1 != End && Range->second == (Range + 1)->first)
-      ++Range;
-    MS->emitIntValue(Range->second + PcOffset, AddressSize);
-    RangesSectionSize += 2 * AddressSize;
+
+  // Emit ranges.
+  uint64_t BaseAddress = 0;
+  if (std::optional<uint64_t> LowPC = Unit.getLowPc())
+    BaseAddress = *LowPC;
+
+  for (const AddressRange &Range : LinkedRanges) {
+    MS->emitIntValue(Range.start() - BaseAddress, AddressSize);
+    MS->emitIntValue(Range.end() - BaseAddress, AddressSize);
+
+    RangesSectionSize += AddressSize;
+    RangesSectionSize += AddressSize;
   }
 
   // Add the terminator entry.
   MS->emitIntValue(0, AddressSize);
   MS->emitIntValue(0, AddressSize);
-  RangesSectionSize += 2 * AddressSize;
+
+  RangesSectionSize += AddressSize;
+  RangesSectionSize += AddressSize;
+}
+
+/// Emit the debug_aranges contribution of a unit and
+/// if \p DoDebugRanges is true the debug_range contents for a
+/// compile_unit level DW_AT_ranges attribute (Which are basically the
+/// same thing with a different base address).
+/// Just aggregate all the ranges gathered inside that unit.
+void DwarfStreamer::emitUnitRangesEntries(CompileUnit &Unit,
+                                          bool DoDebugRanges) {
+  const RangesTy &FunctionRanges = Unit.getFunctionRanges();
+
+  // Linked addresses might end up in a different order.
+  // Build linked address ranges.
+  AddressRanges LinkedRanges;
+  for (size_t Idx = 0; Idx < FunctionRanges.size(); Idx++)
+    LinkedRanges.insert(
+        {FunctionRanges[Idx].first.start() + FunctionRanges[Idx].second,
+         FunctionRanges[Idx].first.end() + FunctionRanges[Idx].second});
+
+  if (!FunctionRanges.empty())
+    emitDwarfDebugArangesTable(Unit, LinkedRanges);
+
+  if (DoDebugRanges)
+    emitDwarfDebugRangesTableFragment(Unit, LinkedRanges);
 }
 
 /// Emit location lists for \p Unit and update attributes to point to the new
 /// entries.
 void DwarfStreamer::emitLocationsForUnit(
     const CompileUnit &Unit, DWARFContext &Dwarf,
     std::function<void(StringRef, SmallVectorImpl<uint8_t> &)> ProcessExpr) {
   const auto &Attributes = Unit.getLocationAttributes();
 
   if (Attributes.empty())
     return;
 
   MS->switchSection(MC->getObjectFileInfo()->getDwarfLocSection());
 
   unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
   uint64_t BaseAddressMarker = (AddressSize == 8)
                                    ? std::numeric_limits<uint64_t>::max()
                                    : std::numeric_limits<uint32_t>::max();
   const DWARFSection &InputSec = Dwarf.getDWARFObj().getLocSection();
   DataExtractor Data(InputSec.Data, Dwarf.isLittleEndian(), AddressSize);
   DWARFUnit &OrigUnit = Unit.getOrigUnit();
   auto OrigUnitDie = OrigUnit.getUnitDIE(false);
   int64_t UnitPcOffset = 0;
-  if (auto OrigLowPc = dwarf::toAddress(OrigUnitDie.find(dwarf::DW_AT_low_pc)))
-    UnitPcOffset = int64_t(*OrigLowPc) - Unit.getLowPc();
+  if (auto OrigLowPc =
+          dwarf::toAddress(OrigUnitDie.find(dwarf::DW_AT_low_pc))) {
+    assert(Unit.getLowPc());
+    UnitPcOffset = int64_t(*OrigLowPc) - *Unit.getLowPc();
+  }
 
   SmallVector<uint8_t, 32> Buffer;
   for (const auto &Attr : Attributes) {
     uint64_t Offset = Attr.first.get();
     Attr.first.set(LocSectionSize);
     // This is the quantity to add to the old location address to get
     // the correct address for the new one.
     int64_t LocPcOffset = Attr.second + UnitPcOffset;