Emit DW_RLE_base_addressx + DW_RLE_offset_pairs instead of DW_ELE_start_length in debug_rnglists section

[rastogishubham]

Summary

This patch tries to reduce the size of the debug_rnglist section by replacing the DW_RLE_start_length opcodes currently emitted by dsymutil in favor of using DW_RLE_base_addressx + DW_RLE_offset_pair instead.

The DW_RLE_start_length is one AddressSize followed by a ULEB per entry, whereas, the DW_RLE_base_addressx + DW_RLE_offset_pair will use one ULEB for the base address, and then the DW_RLE_offset_pair is a pair of ULEBs. This will be more efficient.

The size of the debug_rnglist section + debug_addr section in the clang.dSYM went from 12.22 MB to 12.08 MB in size

[aprantl]

llvm/lib/DWARFLinker/DWARFStreamer.cpp

508–509

This comment sounds wrong. What is being emitted here?

[avl]

LGTM , assuming Adrian comment is addressed.

[rastogishubham]

Fixed comment for end offset

llvm/include/llvm/DWARFLinker/DWARFLinker.h

public:
   /// Emit Apple type accelerator table.
   virtual void
   emitAppleTypes(AccelTable<AppleAccelTableStaticTypeData> &Table) = 0;
 
   /// Emit debug ranges (.debug_ranges, .debug_rnglists) header.
   virtual MCSymbol *emitDwarfDebugRangeListHeader(const CompileUnit &Unit) = 0;
 
   /// Emit debug ranges (.debug_ranges, .debug_rnglists) fragment.
-  virtual void
-  emitDwarfDebugRangeListFragment(const CompileUnit &Unit,
-                                  const AddressRanges &LinkedRanges,
-                                  PatchLocation Patch) = 0;
+  virtual void emitDwarfDebugRangeListFragment(
+      const CompileUnit &Unit, const AddressRanges &LinkedRanges,
+      PatchLocation Patch, DebugAddrPool &AddrPool) = 0;
 
   /// Emit debug ranges (.debug_ranges, .debug_rnglists) footer.
   virtual void emitDwarfDebugRangeListFooter(const CompileUnit &Unit,
                                              MCSymbol *EndLabel) = 0;
 
   /// Emit debug locations (.debug_loc, .debug_loclists) header.
   virtual MCSymbol *emitDwarfDebugLocListHeader(const CompileUnit &Unit) = 0;
 
private:
     void generateLineTableForUnit(CompileUnit &Unit);
   };
 
   /// Assign an abbreviation number to \p Abbrev
   void assignAbbrev(DIEAbbrev &Abbrev);
 
   /// Compute and emit debug ranges(.debug_aranges, .debug_ranges,
   /// .debug_rnglists) for \p Unit, patch the attributes referencing it.
-  void generateUnitRanges(CompileUnit &Unit, const DWARFFile &File) const;
+  void generateUnitRanges(CompileUnit &Unit, const DWARFFile &File,
+                          DebugAddrPool &AddrPool) const;
 
   /// Emit the accelerator entries for \p Unit.
   void emitAcceleratorEntriesForUnit(CompileUnit &Unit);
 
   /// Patch the frame info for an object file and emit it.
   void patchFrameInfoForObject(LinkContext &Context);
 
   /// FoldingSet that uniques the abbreviations.

llvm/include/llvm/DWARFLinker/DWARFStreamer.h

void emitSwiftReflectionSection(
       StringRef Buffer, uint32_t Alignment, uint32_t Size) override;
 
   /// Emit debug ranges(.debug_ranges, .debug_rnglists) header.
   MCSymbol *emitDwarfDebugRangeListHeader(const CompileUnit &Unit) override;
 
   /// Emit debug ranges(.debug_ranges, .debug_rnglists) fragment.
   void emitDwarfDebugRangeListFragment(const CompileUnit &Unit,
                                        const AddressRanges &LinkedRanges,
-                                       PatchLocation Patch) override;
+                                       PatchLocation Patch,
+                                       DebugAddrPool &AddrPool) override;
 
   /// Emit debug ranges(.debug_ranges, .debug_rnglists) footer.
   void emitDwarfDebugRangeListFooter(const CompileUnit &Unit,
                                      MCSymbol *EndLabel) override;
 
   /// Emit debug locations(.debug_loc, .debug_loclists) header.
   MCSymbol *emitDwarfDebugLocListHeader(const CompileUnit &Unit) override;
 
private:
   /// Emit piece of .debug_ranges for \p LinkedRanges.
   void emitDwarfDebugRangesTableFragment(const CompileUnit &Unit,
                                          const AddressRanges &LinkedRanges,
                                          PatchLocation Patch);
 
   /// Emit piece of .debug_rnglists for \p LinkedRanges.
   void emitDwarfDebugRngListsTableFragment(const CompileUnit &Unit,
                                            const AddressRanges &LinkedRanges,
-                                           PatchLocation Patch);
+                                           PatchLocation Patch,
+                                           DebugAddrPool &AddrPool);
 
   /// Emit piece of .debug_loc for \p LinkedRanges.
   void emitDwarfDebugLocTableFragment(
       const CompileUnit &Unit,
       const DWARFLocationExpressionsVector &LinkedLocationExpression,
       PatchLocation Patch);
 
   /// Emit piece of .debug_loclists for \p LinkedRanges.

llvm/lib/DWARFLinker/DWARFLinker.cpp

DIE *DWARFLinker::DIECloner::cloneDIE(const DWARFDie &InputDIE,
   // Update our size.
   Die->setSize(OutOffset - Die->getOffset());
   return 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) const {
+void DWARFLinker::generateUnitRanges(CompileUnit &Unit, const DWARFFile &File,
+                                     DebugAddrPool &AddrPool) const {
   if (LLVM_UNLIKELY(Options.Update))
     return;
 
   const auto &FunctionRanges = Unit.getFunctionRanges();
 
   // Build set of linked address ranges for unit function ranges.
   AddressRanges LinkedFunctionRanges;
   for (const AddressRangeValuePair &Range : FunctionRanges)
for (PatchLocation &AttributePatch : AllRngListAttributes) {
                                Range.HighPC + CachedRange->Value});
         }
       } else {
         llvm::consumeError(OriginalRanges.takeError());
         reportWarning("invalid range list ignored.", File);
       }
 
       // Emit linked ranges.
-      TheDwarfEmitter->emitDwarfDebugRangeListFragment(Unit, LinkedRanges,
-                                                       AttributePatch);
+      TheDwarfEmitter->emitDwarfDebugRangeListFragment(
+          Unit, LinkedRanges, AttributePatch, AddrPool);
     }
 
     // Emit ranges for Unit AT_ranges attribute.
     if (UnitRngListAttribute.has_value())
       TheDwarfEmitter->emitDwarfDebugRangeListFragment(
-          Unit, LinkedFunctionRanges, *UnitRngListAttribute);
+          Unit, LinkedFunctionRanges, *UnitRngListAttribute, AddrPool);
 
     // Emit ranges footer.
     TheDwarfEmitter->emitDwarfDebugRangeListFooter(Unit, EndLabel);
   }
 }
 
 void DWARFLinker::DIECloner::generateUnitLocations(
     CompileUnit &Unit, const DWARFFile &File,
if (Emitter != nullptr) {
 
       generateLineTableForUnit(*CurrentUnit);
 
       Linker.emitAcceleratorEntriesForUnit(*CurrentUnit);
 
       if (LLVM_UNLIKELY(Linker.Options.Update))
         continue;
 
-      Linker.generateUnitRanges(*CurrentUnit, File);
+      Linker.generateUnitRanges(*CurrentUnit, File, AddrPool);
 
       auto ProcessExpr = [&](SmallVectorImpl<uint8_t> &SrcBytes,
                              SmallVectorImpl<uint8_t> &OutBytes,
                              int64_t RelocAdjustment) {
         DWARFUnit &OrigUnit = CurrentUnit->getOrigUnit();
         DataExtractor Data(SrcBytes, IsLittleEndian,
                            OrigUnit.getAddressByteSize());
         cloneExpression(Data,

llvm/lib/DWARFLinker/DWARFStreamer.cpp

DwarfStreamer::emitDwarfDebugRangeListHeader(const CompileUnit &Unit) {
   MS->emitInt32(0);
   RngListsSectionSize += sizeof(uint32_t);
 
   return EndLabel;
 }
 
 void DwarfStreamer::emitDwarfDebugRangeListFragment(
     const CompileUnit &Unit, const AddressRanges &LinkedRanges,
-    PatchLocation Patch) {
+    PatchLocation Patch, DebugAddrPool &AddrPool) {
   if (Unit.getOrigUnit().getVersion() < 5) {
     emitDwarfDebugRangesTableFragment(Unit, LinkedRanges, Patch);
     return;
   }
 
-  emitDwarfDebugRngListsTableFragment(Unit, LinkedRanges, Patch);
+  emitDwarfDebugRngListsTableFragment(Unit, LinkedRanges, Patch, AddrPool);
 }
 
 void DwarfStreamer::emitDwarfDebugRangeListFooter(const CompileUnit &Unit,
                                                   MCSymbol *EndLabel) {
   if (Unit.getOrigUnit().getVersion() < 5)
     return;
 
   // Make .debug_rnglists to be current section.
   MS->switchSection(MC->getObjectFileInfo()->getDwarfRnglistsSection());
 
   if (EndLabel != nullptr)
     Asm->OutStreamer->emitLabel(EndLabel);
 }
 
 void DwarfStreamer::emitDwarfDebugRngListsTableFragment(
     const CompileUnit &Unit, const AddressRanges &LinkedRanges,
-    PatchLocation Patch) {
+    PatchLocation Patch, DebugAddrPool &AddrPool) {
   Patch.set(RngListsSectionSize);
 
   // Make .debug_rnglists to be current section.
   MS->switchSection(MC->getObjectFileInfo()->getDwarfRnglistsSection());
-
-  unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
+  std::optional<uint64_t> BaseAddress;
 
   for (const AddressRange &Range : LinkedRanges) {
+
+    if (!BaseAddress) {
+      BaseAddress = Range.start();
+
+      // Emit base address.
+      MS->emitInt8(dwarf::DW_RLE_base_addressx);
+      RngListsSectionSize += 1;
+      RngListsSectionSize +=
+          MS->emitULEB128IntValue(AddrPool.getAddrIndex(*BaseAddress));
+    }
+
     // Emit type of entry.
-    MS->emitInt8(dwarf::DW_RLE_start_length);
+    MS->emitInt8(dwarf::DW_RLE_offset_pair);
     RngListsSectionSize += 1;
 
-    // Emit start address.
-    MS->emitIntValue(Range.start(), AddressSize);
-    RngListsSectionSize += AddressSize;
+    // Emit start offset relative to base address.
+    RngListsSectionSize +=
+        MS->emitULEB128IntValue(Range.start() - *BaseAddress);
 
-    // Emit length of the range.
-    RngListsSectionSize += MS->emitULEB128IntValue(Range.end() - Range.start());
+    // Emit end offset relative to base address.
+    RngListsSectionSize += MS->emitULEB128IntValue(Range.end() - *BaseAddress);
   }
 
   // Emit the terminator entry.
   MS->emitInt8(dwarf::DW_RLE_end_of_list);
   RngListsSectionSize += 1;
 }
 
 /// Emit debug locations(.debug_loc, .debug_loclists) header.

llvm/test/tools/dsymutil/ARM/dwarf5-dwarf4-combination-macho.test

 CHECK: .debug_line_str contents:
 CHECK-NEXT: 0x00000000: "/Users/shubham/Development/test109275485"
 CHECK-NEXT: 0x00000029: "a.cpp"
 
 CHECK: .debug_ranges contents:
 CHECK-NEXT: 00000000 [[#sub(RANGE_START,RANGE_LOWPC)]] [[#sub(RANGE_END,RANGE_LOWPC)]]
 
 CHECK: .debug_rnglists contents:
-CHECK-NEXT: 0x00000000: range list header: length = 0x00000013, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00, offset_entry_count = 0x00000000
+CHECK-NEXT: 0x00000000: range list header: length = 0x0000000e, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00, offset_entry_count = 0x00000000
 CHECK-NEXT: ranges:
-CHECK-NEXT: [[RANGELIST_OFFSET]]: [DW_RLE_start_length]: {{.*}}[0x[[RANGELIST_OFFSET_START]], 0x[[RANGELIST_OFFSET_END]])
+CHECK-NEXT: [[RANGELIST_OFFSET]]: [DW_RLE_base_addressx]:  0x0000000000000000
+CHECK-NEXT: 0x0000000e: [DW_RLE_offset_pair  ]: {{.*}}[0x[[RANGELIST_OFFSET_START]], 0x[[RANGELIST_OFFSET_END]])
+CHECK-NEXT: 0x00000011: [DW_RLE_end_of_list  ]
 
 CHECK: .debug_names contents:
 CHECK-NEXT: Name Index @ 0x0 {
 CHECK-NEXT:   Header {
 CHECK-NEXT:     Length: 0xBC
 CHECK-NEXT:     Format: DWARF32
 CHECK-NEXT:     Version: 5
 CHECK-NEXT:     CU count: 2
 CHECK-NEXT:     Local TU count: 0
 CHECK-NEXT:     Foreign TU count: 0
 CHECK-NEXT:     Bucket count: 5
 CHECK-NEXT:     Name count: 5
 CHECK-NEXT:     Abbreviations table size: 0x11
 CHECK-NEXT:     Augmentation: 'LLVM0700'
 CHECK-NEXT:   }

llvm/test/tools/dsymutil/ARM/dwarf5-macho.test

 
 CHECK: .debug_str contents:
 
 CHECK: .debug_line_str contents:
 CHECK-NEXT: 0x00000000: "/Users/shubham/Development/test109275485"
 CHECK-NEXT: 0x00000029: "a.cpp"
 
 CHECK: .debug_rnglists contents:
-CHECK-NEXT: 0x00000000: range list header: length = 0x00000013, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00, offset_entry_count = 0x00000000
+CHECK-NEXT: 0x00000000: range list header: length = 0x0000000e, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00, offset_entry_count = 0x00000000
 CHECK-NEXT: ranges:
-CHECK-NEXT: [[RANGELIST_OFFSET]]: [DW_RLE_start_length]: {{.*}}[0x[[RANGELIST_OFFSET_START]], 0x[[RANGELIST_OFFSET_END]])
+CHECK-NEXT: [[RANGELIST_OFFSET]]: [DW_RLE_base_addressx]:  0x0000000000000000
+CHECK-NEXT: 0x0000000e: [DW_RLE_offset_pair  ]: {{.*}}[0x[[RANGELIST_OFFSET_START]], 0x[[RANGELIST_OFFSET_END]])
+CHECK-NEXT: 0x00000011: [DW_RLE_end_of_list  ]
 
 CHECK: .debug_names contents:
 CHECK-NEX:T Name Index @ 0x0 {
 CHECK-NEX:T   Header {
 CHECK-NEX:T     Length: 0x7C
 CHECK-NEX:T     Format: DWARF32
 CHECK-NEX:T     Version: 5
 CHECK-NEX:T     CU count: 1
 CHECK-NEX:T     Local TU count: 0
 CHECK-NEX:T     Foreign TU count: 0
 CHECK-NEX:T     Bucket count: 3
 CHECK-NEX:T     Name count: 3
 CHECK-NEX:T     Abbreviations table size: 0xD
 CHECK-NEX:T     Augmentation: 'LLVM0700'
 CHECK-NEX:T   }

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

 
 #DWARF-CHECK: DW_TAG_compile_unit
 #DWARF-CHECK:   DW_AT_addr_base [DW_FORM_sec_offset]      (0x00000008)
 #DWARF-CHECK: DW_TAG_lexical_block
 #DWARF-CHECK:   DW_AT_ranges [DW_FORM_sec_offset]     (0x0000000c
 #DWARF-CHECK:      [0x0000000100000f79, 0x0000000100000f96)
 #DWARF-CHECK:      [0x0000000100000fad, 0x0000000100000fb4))
 #DWARF-CHECK: .debug_rnglists contents:
-#DWARF-CHECK: 0x00000000: range list header: length = 0x0000001d, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00, offset_entry_count = 0x00000000
+#DWARF-CHECK: 0x00000000: range list header: length = 0x00000011, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00, offset_entry_count = 0x00000000
 #DWARF-CHECK: ranges:
-#DWARF-CHECK: 0x0000000c: [DW_RLE_start_length]:  0x0000000100000f79, 0x000000000000001d => [0x0000000100000f79, 0x0000000100000f96)
-#DWARF-CHECK: 0x00000016: [DW_RLE_start_length]:  0x0000000100000fad, 0x0000000000000007 => [0x0000000100000fad, 0x0000000100000fb4)
-#DWARF-CHECK: 0x00000020: [DW_RLE_end_of_list ]
+#DWARF-CHECK: 0x0000000c: [DW_RLE_base_addressx]:  0x0000000000000003
+#DWARF-CHECK: 0x0000000e: [DW_RLE_offset_pair  ]:  0x0000000000000000, 0x000000000000001d => [0x0000000100000f79, 0x0000000100000f96)
+#DWARF-CHECK: 0x00000011: [DW_RLE_offset_pair  ]:  0x0000000000000034, 0x000000000000003b => [0x0000000100000fad, 0x0000000100000fb4)
+#DWARF-CHECK: 0x00000014: [DW_RLE_end_of_list  ]
 #
 #UPD-DWARF-CHECK: DW_TAG_compile_unit
 #UPD-DWARF-CHECK:   DW_AT_addr_base [DW_FORM_sec_offset]      (0x00000008)
 #UPD-DWARF-CHECK: DW_TAG_lexical_block
 #UPD-DWARF-CHECK:   DW_AT_ranges [DW_FORM_rnglistx]       (indexed (0x0) rangelist = 0x00000010
 #UPD-DWARF-CHECK:     [0x0000000000000009, 0x0000000000000026)
 #UPD-DWARF-CHECK:     [0x000000000000003d, 0x0000000000000044))
 #UPD-DWARF-CHECK: .debug_addr contents:

llvm/test/tools/llvm-dwarfutil/ELF/X86/dwarf5-rnglists.test

 #DWARF-CHECK: 0x00000000: Address table header: length = 0x00000024, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00
 #DWARF-CHECK: Addrs: [
 #DWARF-CHECK: 0x0000000000001130
 #DWARF-CHECK: 0x0000000000001140
 #DWARF-CHECK: 0x0000000000001150
 #DWARF-CHECK: 0x0000000000001160
 #DWARF-CHECK: ]
 #DWARF-CHECK: .debug_rnglists contents:
-#DWARF-CHECK: 0x00000000: range list header: length = 0x0000003f, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00, offset_entry_count = 0x00000000
+#DWARF-CHECK: 0x00000000: range list header: length = 0x00000026, format = DWARF32, version = 0x0005, addr_size = 0x08, seg_size = 0x00, offset_entry_count = 0x00000000
 #DWARF-CHECK: ranges:
-#DWARF-CHECK: 0x[[F1RANGE_OFF]]: [DW_RLE_start_length]:  0x0000000000001130, 0x0000000000000010 => [0x0000000000001130, 0x0000000000001140)
-#DWARF-CHECK: {{.*}} [DW_RLE_end_of_list ]
-#DWARF-CHECK: 0x[[F2RANGE_OFF]]: [DW_RLE_start_length]:  0x0000000000001140, 0x0000000000000010 => [0x0000000000001140, 0x0000000000001150)
-#DWARF-CHECK: {{.*}} [DW_RLE_end_of_list ]
-#DWARF-CHECK: 0x[[F3RANGE_OFF]]: [DW_RLE_start_length]:  0x0000000000001150, 0x0000000000000010 => [0x0000000000001150, 0x0000000000001160)
-#DWARF-CHECK: {{.*}} [DW_RLE_end_of_list ]
-#DWARF-CHECK: 0x[[F4RANGE_OFF]]: [DW_RLE_start_length]:  0x0000000000001160, 0x0000000000000010 => [0x0000000000001160, 0x0000000000001170)
-#DWARF-CHECK: {{.*}} [DW_RLE_end_of_list ]
-#DWARF-CHECK: 0x[[CURANGE_OFF]]: [DW_RLE_start_length]:  0x0000000000001130, 0x0000000000000040 => [0x0000000000001130, 0x0000000000001170)
-#DWARF-CHECK: {{.*}} [DW_RLE_end_of_list ]
+#DWARF-CHECK: 0x[[F1RANGE_OFF]]: [DW_RLE_base_addressx]:  0x0000000000000000
+#DWARF-CHECK: {{.}}: [DW_RLE_offset_pair  ]:  0x0000000000000000, 0x0000000000000010 => [0x0000000000001130, 0x0000000000001140)
+#DWARF-CHECK: {{.}}: [DW_RLE_end_of_list  ]
+#DWARF-CHECK: 0x[[F2RANGE_OFF]]: [DW_RLE_base_addressx]:  0x0000000000000001
+#DWARF-CHECK: {{.}}: [DW_RLE_offset_pair  ]:  0x0000000000000000, 0x0000000000000010 => [0x0000000000001140, 0x0000000000001150)
+#DWARF-CHECK: {{.}}: [DW_RLE_end_of_list  ]
+#DWARF-CHECK: 0x[[F3RANGE_OFF]]: [DW_RLE_base_addressx]:  0x0000000000000002
+#DWARF-CHECK: {{.}}: [DW_RLE_offset_pair  ]:  0x0000000000000000, 0x0000000000000010 => [0x0000000000001150, 0x0000000000001160)
+#DWARF-CHECK: {{.}}: [DW_RLE_end_of_list  ]
+#DWARF-CHECK: 0x[[F4RANGE_OFF]]: [DW_RLE_base_addressx]:  0x0000000000000003
+#DWARF-CHECK: {{.}}: [DW_RLE_offset_pair  ]:  0x0000000000000000, 0x0000000000000010 => [0x0000000000001160, 0x0000000000001170)
+#DWARF-CHECK: {{.}}: [DW_RLE_end_of_list  ]
+#DWARF-CHECK 0x[[CURANGE_OFF]]: [DW_RLE_base_addressx]:  0x0000000000000000
+#DWARF-CHECK: {{.}}: [DW_RLE_offset_pair  ]:  0x0000000000000000, 0x0000000000000040 => [0x0000000000001130, 0x0000000000001170)
+#DWARF-CHECK: {{.}}: [DW_RLE_end_of_list  ]
 
 #UPD-DWARF-CHECK: DW_TAG_compile_unit
 #UPD-DWARF-CHECK:   DW_AT_name {{.*}}"CU1"
 #UPD-DWARF-CHECK:   DW_AT_low_pc [DW_FORM_addrx]      (indexed (00000000) address = 0x0000000000001130)
 #UPD-DWARF-CHECK:   DW_AT_ranges [DW_FORM_rnglistx] (indexed (0x4) rangelist = 0x0000003e
 #UPD-DWARF-CHECK:      [0x0000000000001130, 0x0000000000001170))
 #UPD-DWARF-CHECK:   DW_TAG_subprogram
 #UPD-DWARF-CHECK:     DW_AT_name  {{.*}}"foo1"