WIP: DebugInfo: Use base address and offset pairs in debug_loc.dwo to reduce required relocations

[dblaikie]

Summary

This isn't quite finished, but a prototype that reduces the number of
debug_addr relocs in a large internal optimized binary by 40% substantially
reducing total object file size, which would be nice.

1. Needs testing (updating existing test cases, maybe adding more - could check

about the number of relocations, etc)

2. Needs work either way once determined if a debug location address range

could start at the very beginning of a function (then a range might be shorter
using startx_length than base_address+offset_pair)

3. Maybe it's simpler to have two separate implementations rather than

generalizing the debug_ranges handling (especially if there's currently no
debug_loc generated for global variables (or no other way a variable could have
live ranges in more than one section))

4. Comments

5. Should DwarfDebug use MCStreamer directly for the ULEB label difference

(that's what it's doing in this version) or should it use an
AsmPrinter/MCStreamer API to match the non-ULEB label difference (I've
prototyped the MCStreamer/AsmPrinter APIs in this change - though they're not
wired up to DwarfDebug - just to show the rough scale of the code, mostly it's
just copy/pasted from the non-ULEB label difference codepath)

Oh, and Paul: This'll probably come in handy/can be reused for the rnglist
support (& generalized further for all the DWARF5 forms for use in loclist -
though I imagine we'll still only need to generate a subset of the forms -
maybe still only these 2 or 3 depending on what's being proritized (object
size, executable size, number of relocations)

[dblaikie]

(oh, bother - looks like GDB can't parse this, even if it were in debug_loclists.dwo (but it could handle it in debug_loclists) :/ - so this might be a bit before its time & have to wait... still wouldn't mind figuring out the right design)

[tberghammer]

I checked LLDB and it doesn't have support for base address entries neither in .debug_loc nor in .debug_loc.dwo sections and it doesn't support reading .debug_loclists or .debug_loclists.dwo entries either. I will try to add support for them but it will require some refactoring so it will take some time.

[dblaikie]

Well... guess I don't learn from the past sometimes.

I reimplemented this a slightly different way (patch attached) only to
learn, again, that GDB doesn't support this... which makes me sad.

Sent email to the gdb development list because weirdly the DWARFv5 support
in GDB currently seems to /only/ support the base+offset_pair form -
strangely mutually exclusive. Would be great to have more full support in
both the DWARF 4/pre-standard Fission, and the v5 standardized loclists.

Added a better comment in r345326 so hopefully I don't try to fix this
again only to learn the same thing...

• Dave
  • loc_base_address_offset_pair.diff7 KBDownload

include/llvm/CodeGen/AsmPrinter.h

public:
   void EmitInt32(int Value) const;
 
   /// Emit something like ".long Hi-Lo" where the size in bytes of the directive
   /// is specified by Size and Hi/Lo specify the labels.  This implicitly uses
   /// .set if it is available.
   void EmitLabelDifference(const MCSymbol *Hi, const MCSymbol *Lo,
                            unsigned Size) const;
 
+  void EmitULEB128LabelDifference(const MCSymbol *Hi, const MCSymbol *Lo) const;
+
   /// Emit something like ".long Label+Offset" where the size in bytes of the
   /// directive is specified by Size and Label specifies the label.  This
   /// implicitly uses .set if it is available.
   void EmitLabelPlusOffset(const MCSymbol *Label, uint64_t Offset,
                            unsigned Size, bool IsSectionRelative = false) const;
 
   /// Emit something like ".long Label" where the size in bytes of the directive
   /// is specified by Size and Label specifies the label.

include/llvm/DebugInfo/DWARF/DWARFDebugLoc.h

 //===- DWARFDebugLoc.h ------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_DWARF_DWARFDEBUGLOC_H
 #define LLVM_DEBUGINFO_DWARF_DWARFDEBUGLOC_H
 
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
 #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
 #include <cstdint>
 
 namespace llvm {
 
 class raw_ostream;
 
public:
 
   /// Parse the debug_loc section accessible via the 'data' parameter using the
   /// address size also given in 'data' to interpret the address ranges.
   void parse(const DWARFDataExtractor &data);
 };
 
 class DWARFDebugLocDWO {
   struct Entry {
-    uint64_t Start;
-    uint32_t Length;
+    dwarf::LocationListEntry Kind;
+    uint64_t First;
+    uint32_t Second;
     SmallVector<unsigned char, 4> Loc;
   };
 
   struct LocationList {
     unsigned Offset;
     SmallVector<Entry, 2> Entries;
   };
 

include/llvm/MC/MCObjectStreamer.h

public:
   ///
   /// Emit the absolute difference between \c Hi and \c Lo, as long as we can
   /// compute it.  Currently, that requires that both symbols are in the same
   /// data fragment.  Otherwise, do nothing and return \c false.
   ///
   /// \pre Offset of \c Hi is greater than the offset \c Lo.
   void emitAbsoluteSymbolDiff(const MCSymbol *Hi, const MCSymbol *Lo,
                               unsigned Size) override;
+  void emitULEB128AbsoluteSymbolDiff(const MCSymbol *Hi,
+                                     const MCSymbol *Lo) override;
 
   bool mayHaveInstructions(MCSection &Sec) const override;
 };
 
 } // end namespace llvm
 
 #endif

include/llvm/MC/MCStreamer.h

public:
   virtual void EmitCVFileChecksumsDirective() {}
 
   /// Emit the absolute difference between two symbols.
   ///
   /// \pre Offset of \c Hi is greater than the offset \c Lo.
   virtual void emitAbsoluteSymbolDiff(const MCSymbol *Hi, const MCSymbol *Lo,
                                       unsigned Size);
 
+  virtual void emitULEB128AbsoluteSymbolDiff(const MCSymbol *Hi,
+                                             const MCSymbol *Lo);
+
   virtual MCSymbol *getDwarfLineTableSymbol(unsigned CUID);
   virtual void EmitCFISections(bool EH, bool Debug);
   void EmitCFIStartProc(bool IsSimple);
   void EmitCFIEndProc();
   virtual void EmitCFIDefCfa(int64_t Register, int64_t Offset);
   virtual void EmitCFIDefCfaOffset(int64_t Offset);
   virtual void EmitCFIDefCfaRegister(int64_t Register);
   virtual void EmitCFIOffset(int64_t Register, int64_t Offset);

lib/CodeGen/AsmPrinter/AsmPrinter.cpp

 /// Emit something like ".long Hi-Lo" where the size in bytes of the directive
 /// is specified by Size and Hi/Lo specify the labels. This implicitly uses
 /// .set if it avoids relocations.
 void AsmPrinter::EmitLabelDifference(const MCSymbol *Hi, const MCSymbol *Lo,
                                      unsigned Size) const {
   OutStreamer->emitAbsoluteSymbolDiff(Hi, Lo, Size);
 }
 
+void AsmPrinter::EmitULEB128LabelDifference(const MCSymbol *Hi,
+                                            const MCSymbol *Lo) const {
+  OutStreamer->emitULEB128AbsoluteSymbolDiff(Hi, Lo);
+}
+
 /// EmitLabelPlusOffset - Emit something like ".long Label+Offset"
 /// where the size in bytes of the directive is specified by Size and Label
 /// specifies the label.  This implicitly uses .set if it is available.
 void AsmPrinter::EmitLabelPlusOffset(const MCSymbol *Label, uint64_t Offset,
                                      unsigned Size,
                                      bool IsSectionRelative) const {
   if (MAI->needsDwarfSectionOffsetDirective() && IsSectionRelative) {
     OutStreamer->EmitCOFFSecRel32(Label, Offset);

lib/CodeGen/AsmPrinter/DwarfDebug.h

class DwarfDebug : public DebugHandlerBase {
   DwarfAccelTable AccelNames;
   DwarfAccelTable AccelObjC;
   DwarfAccelTable AccelNamespace;
   DwarfAccelTable AccelTypes;
 
   // Identify a debugger for "tuning" the debug info.
   DebuggerKind DebuggerTuning;
 
+  DenseMap<const MCSection *, const MCSymbol *> FirstAddresses;
+
   /// \defgroup DebuggerTuning Predicates to tune DWARF for a given debugger.
   ///
   /// Returns whether we are "tuning" for a given debugger.
   /// Should be used only within the constructor, to set feature flags.
   /// @{
   bool tuneForGDB() const { return DebuggerTuning == DebuggerKind::GDB; }
   bool tuneForLLDB() const { return DebuggerTuning == DebuggerKind::LLDB; }
   bool tuneForSCE() const { return DebuggerTuning == DebuggerKind::SCE; }

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

 void DwarfDebug::beginFunctionImpl(const MachineFunction *MF) {
   CurFn = MF;
 
   auto *SP = MF->getFunction()->getSubprogram();
   assert(LScopes.empty() || SP == LScopes.getCurrentFunctionScope()->getScopeNode());
   if (SP->getUnit()->getEmissionKind() == DICompileUnit::NoDebug)
     return;
 
+  const MCSymbol *BeginSym = Asm->getFunctionBegin();
+  FirstAddresses.insert(std::make_pair(&BeginSym->getSection(), BeginSym));
   DwarfCompileUnit &CU = getOrCreateDwarfCompileUnit(SP->getUnit());
 
   // Set DwarfDwarfCompileUnitID in MCContext to the Compile Unit this function
   // belongs to so that we add to the correct per-cu line table in the
   // non-asm case.
   if (Asm->OutStreamer->hasRawTextSupport())
     // Use a single line table if we are generating assembly.
     Asm->OutStreamer->getContext().setDwarfCompileUnitID(0);
for (const auto &Entry : DebugLocs.getEntries(List)) {
 
       emitDebugLocEntryLocation(Entry);
     }
     Asm->OutStreamer->EmitIntValue(0, Size);
     Asm->OutStreamer->EmitIntValue(0, Size);
   }
 }
 
+template <typename Range, typename StartGetter, typename BaseFilter,
+          typename BaseEmitter, typename EntryEmitter,
+          typename BaselessEntryEmitter>
+static void emitBasedRanges(const DwarfCompileUnit &CU, const Range &R,
+                            StartGetter getStart, BaseFilter shouldUseBase,
+                            BaseEmitter emitBase, EntryEmitter emitEntry,
+                            BaselessEntryEmitter emitBaselessEntry) {
+  // Gather all the ranges that apply to the same section so they can
+  // share a base address entry.
+  MapVector<const MCSection *, std::vector<decltype(&*R.begin())>> MV;
+  for (const auto &SR : R)
+    MV[&getStart(SR)->getSection()].push_back(&SR);
+
+  auto *CUBase = CU.getBaseAddress();
+  bool BaseIsSet = false;
+  for (const auto &P : MV) {
+    auto Base = CUBase;
+    if (!Base && shouldUseBase(P.second)) {
+      BaseIsSet = true;
+      Base = getStart(*P.second.front());
+      emitBase(Base);
+    } else if (BaseIsSet) {
+      BaseIsSet = false;
+      emitBase(nullptr);
+    }
+
+    for (const auto *RS : P.second)
+      Base ? emitEntry(Base, *RS) : emitBaselessEntry(*RS);
+  }
+}
+
 void DwarfDebug::emitDebugLocDWO() {
   Asm->OutStreamer->SwitchSection(
       Asm->getObjFileLowering().getDwarfLocDWOSection());
   for (const auto &List : DebugLocs.getLists()) {
     Asm->OutStreamer->EmitLabel(List.Label);
-    for (const auto &Entry : DebugLocs.getEntries(List)) {
-      // Just always use start_length for now - at least that's one address
-      // rather than two. We could get fancier and try to, say, reuse an
-      // address we know we've emitted elsewhere (the start of the function?
-      // The start of the CU or CU subrange that encloses this range?)
+    emitBasedRanges(*List.CU, DebugLocs.getEntries(List),
+                    [&](const DebugLocStream::Entry &E) {
+                      return FirstAddresses[&E.BeginSym->getSection()];
+                    },
+                    [](const std::vector<const DebugLocStream::Entry *> &v) {
+                      return true;
+                    },
+                    [&](const MCSymbol *Base) {
+                      Asm->EmitInt8(dwarf::DW_LLE_base_addressx);
+                      unsigned idx = AddrPool.getIndex(Base);
+                      Asm->EmitULEB128(idx);
+                    },
+                    [&](const MCSymbol *Base, const DebugLocStream::Entry &E) {
+                      Asm->EmitInt8(dwarf::DW_LLE_offset_pair);
+                      auto &Context = Asm->OutStreamer->getContext();
+                      Asm->OutStreamer->EmitULEB128Value(
+                          MCBinaryExpr::createSub(
+                              MCSymbolRefExpr::create(E.BeginSym, Context),
+                              MCSymbolRefExpr::create(Base, Context), Context));
+                      Asm->OutStreamer->EmitULEB128Value(
+                          MCBinaryExpr::createSub(
+                              MCSymbolRefExpr::create(E.EndSym, Context),
+                              MCSymbolRefExpr::create(Base, Context), Context));
+                      emitDebugLocEntryLocation(E);
+                    },
+                    [&](const DebugLocStream::Entry &E) {
                       Asm->EmitInt8(dwarf::DW_LLE_startx_length);
-      unsigned idx = AddrPool.getIndex(Entry.BeginSym);
+                      unsigned idx = AddrPool.getIndex(E.BeginSym);
                       Asm->EmitULEB128(idx);
-      Asm->EmitLabelDifference(Entry.EndSym, Entry.BeginSym, 4);
-
-      emitDebugLocEntryLocation(Entry);
-    }
+                      Asm->EmitLabelDifference(E.EndSym, E.BeginSym, 4);
+                      emitDebugLocEntryLocation(E);
+                    });
     Asm->EmitInt8(dwarf::DW_LLE_end_of_list);
   }
 }
 
 struct ArangeSpan {
   const MCSymbol *Start, *End;
 };
 
for (const auto &I : CUMap) {
     if (auto *Skel = TheCU->getSkeleton())
       TheCU = Skel;
 
     // Iterate over the misc ranges for the compile units in the module.
     for (const RangeSpanList &List : TheCU->getRangeLists()) {
       // Emit our symbol so we can find the beginning of the range.
       Asm->OutStreamer->EmitLabel(List.getSym());
 
-      // Gather all the ranges that apply to the same section so they can share
-      // a base address entry.
-      MapVector<const MCSection *, std::vector<const RangeSpan *>> MV;
-      for (const RangeSpan &Range : List.getRanges()) {
-        MV[&Range.getStart()->getSection()].push_back(&Range);
-      }
-
-      auto *CUBase = TheCU->getBaseAddress();
-      bool BaseIsSet = false;
-      for (const auto &P : MV) {
-        // Don't bother with a base address entry if there's only one range in
-        // this section in this range list - for example ranges for a CU will
-        // usually consist of single regions from each of many sections
-        // (-ffunction-sections, or just C++ inline functions) except under LTO
-        // or optnone where there may be holes in a single CU's section
-        // contrubutions.
-        auto *Base = CUBase;
-        if (!Base && P.second.size() > 1 &&
-            UseDwarfRangesBaseAddressSpecifier) {
-          BaseIsSet = true;
-          // FIXME/use care: This may not be a useful base address if it's not
-          // the lowest address/range in this object.
-          Base = P.second.front()->getStart();
-          Asm->OutStreamer->EmitIntValue(-1, Size);
-          Asm->OutStreamer->EmitSymbolValue(Base, Size);
-        } else if (BaseIsSet) {
-          BaseIsSet = false;
+      emitBasedRanges(*TheCU, List.getRanges(),
+                      [](const RangeSpan &R) { return R.getStart(); },
+                      [](const std::vector<const RangeSpan *> &V) {
+                        return V.size() > 1 &&
+                               UseDwarfRangesBaseAddressSpecifier;
+                      },
+                      [&](const MCSymbol *Base) {
                         Asm->OutStreamer->EmitIntValue(-1, Size);
-          Asm->OutStreamer->EmitIntValue(0, Size);
-        }
-
-        for (const auto *RS : P.second) {
-          const MCSymbol *Begin = RS->getStart();
-          const MCSymbol *End = RS->getEnd();
-          assert(Begin && "Range without a begin symbol?");
-          assert(End && "Range without an end symbol?");
                         if (Base) {
-            Asm->EmitLabelDifference(Begin, Base, Size);
-            Asm->EmitLabelDifference(End, Base, Size);
+                          Asm->OutStreamer->EmitSymbolValue(Base, Size);
                         } else {
-            Asm->OutStreamer->EmitSymbolValue(Begin, Size);
-            Asm->OutStreamer->EmitSymbolValue(End, Size);
-          }
-        }
+                          Asm->OutStreamer->EmitIntValue(0, Size);
                         }
-
+                      },
+                      [&](const MCSymbol *Base, const RangeSpan &RS) {
+                        Asm->EmitLabelDifference(RS.getStart(), Base, Size);
+                        Asm->EmitLabelDifference(RS.getEnd(), Base, Size);
+                      },
+                      [&](const RangeSpan &RS) {
+                        Asm->OutStreamer->EmitSymbolValue(RS.getStart(), Size);
+                        Asm->OutStreamer->EmitSymbolValue(RS.getEnd(), Size);
+                      });
       // And terminate the list with two 0 values.
       Asm->OutStreamer->EmitIntValue(0, Size);
       Asm->OutStreamer->EmitIntValue(0, Size);
     }
   }
 }
 
 void DwarfDebug::handleMacroNodes(DIMacroNodeArray Nodes, DwarfCompileUnit &U) {

lib/DebugInfo/DWARF/DWARFDebugLoc.cpp

void DWARFDebugLocDWO::parse(DataExtractor data) {
   while (data.isValidOffset(Offset)) {
     Locations.resize(Locations.size() + 1);
     LocationList &Loc = Locations.back();
     Loc.Offset = Offset;
     dwarf::LocationListEntry Kind;
     while ((Kind = static_cast<dwarf::LocationListEntry>(
                 data.getU8(&Offset))) != dwarf::DW_LLE_end_of_list) {
 
-      if (Kind != dwarf::DW_LLE_startx_length) {
+      if (Kind != dwarf::DW_LLE_startx_length &&
+          Kind != dwarf::DW_LLE_offset_pair &&
+          Kind != dwarf::DW_LLE_base_addressx) {
         errs() << "error: dumping support for LLE of kind " << (int)Kind
                << " not implemented\n";
         return;
       }
 
-      Entry E;
+      Loc.Entries.emplace_back();
+      Entry &E = Loc.Entries.back();
 
-      E.Start = data.getULEB128(&Offset);
-      E.Length = data.getU32(&Offset);
+      E.Kind = Kind;
+      E.First = data.getULEB128(&Offset);
+      if (Kind == dwarf::DW_LLE_base_addressx)
+        continue;
+      E.Second = Kind == dwarf::DW_LLE_offset_pair ? data.getULEB128(&Offset)
+                                                   : data.getU32(&Offset);
 
       unsigned Bytes = data.getU16(&Offset);
       // A single location description describing the location of the object...
       StringRef str = data.getData().substr(Offset, Bytes);
       Offset += Bytes;
       E.Loc.resize(str.size());
       std::copy(str.begin(), str.end(), E.Loc.begin());
-
-      Loc.Entries.push_back(std::move(E));
     }
   }
 }
 
 void DWARFDebugLocDWO::dump(raw_ostream &OS) const {
   for (const LocationList &L : Locations) {
     OS << format("0x%8.8x: ", L.Offset);
     const unsigned Indent = 12;
     for (const Entry &E : L.Entries) {
       if (&E != L.Entries.begin())
         OS.indent(Indent);
-      OS << "Beginning address index: " << E.Start << '\n';
-      OS.indent(Indent) << "                 Length: " << E.Length << '\n';
-      OS.indent(Indent) << "   Location description: ";
+      if (E.Kind == dwarf::DW_LLE_base_addressx) {
+        OS << "     Base address index: " << E.First << "\n\n";
+        continue;
+      }
+      OS << (E.Kind == dwarf::DW_LLE_offset_pair ? "       Starting offset: "
+                                                 : "Starting address index: ")
+         << E.First << '\n';
+      OS.indent(Indent) << (E.Kind == dwarf::DW_LLE_offset_pair
+                                ? "         Ending offset: "
+                                : "                Length: ")
+                        << E.Second << '\n';
+      OS.indent(Indent) << "  Location description: ";
       for (unsigned char Loc : E.Loc)
         OS << format("%2.2x ", Loc);
       OS << "\n\n";
     }
   }
 }

lib/MC/MCObjectStreamer.cpp

void MCObjectStreamer::flushPendingLabels(MCFragment *F, uint64_t FOffset) {
   }
   for (MCSymbol *Sym : PendingLabels) {
     Sym->setFragment(F);
     Sym->setOffset(FOffset);
   }
   PendingLabels.clear();
 }
 
+void MCObjectStreamer::emitULEB128AbsoluteSymbolDiff(const MCSymbol *Hi,
+                                                     const MCSymbol *Lo) {
+  // If not assigned to the same (valid) fragment, fallback.
+  if (!Hi->getFragment() || Hi->getFragment() != Lo->getFragment() ||
+      Hi->isVariable() || Lo->isVariable()) {
+    MCStreamer::emitULEB128AbsoluteSymbolDiff(Hi, Lo);
+    return;
+  }
+
+  EmitULEB128IntValue(Hi->getOffset() - Lo->getOffset());
+}
+
 void MCObjectStreamer::emitAbsoluteSymbolDiff(const MCSymbol *Hi,
                                               const MCSymbol *Lo,
                                               unsigned Size) {
   // If not assigned to the same (valid) fragment, fallback.
   if (!Hi->getFragment() || Hi->getFragment() != Lo->getFragment() ||
       Hi->isVariable() || Lo->isVariable()) {
     MCStreamer::emitAbsoluteSymbolDiff(Hi, Lo, Size);
     return;

lib/MC/MCStreamer.cpp

 void MCStreamer::EmitInstruction(const MCInst &Inst, const MCSubtargetInfo &STI,
                                  bool) {
   // Scan for values.
   for (unsigned i = Inst.getNumOperands(); i--;)
     if (Inst.getOperand(i).isExpr())
       visitUsedExpr(*Inst.getOperand(i).getExpr());
 }
 
+void MCStreamer::emitULEB128AbsoluteSymbolDiff(const MCSymbol *Hi,
+                                               const MCSymbol *Lo) {
+  const MCExpr *Diff =
+      MCBinaryExpr::createSub(MCSymbolRefExpr::create(Hi, Context),
+                              MCSymbolRefExpr::create(Lo, Context), Context);
+
+  const MCAsmInfo *MAI = Context.getAsmInfo();
+  if (!MAI->doesSetDirectiveSuppressReloc()) {
+    EmitULEB128Value(Diff);
+    return;
+  }
+
+  // Otherwise, emit with .set (aka assignment).
+  MCSymbol *SetLabel = Context.createTempSymbol("set", true);
+  EmitAssignment(SetLabel, Diff);
+  EmitULEB128Value(MCSymbolRefExpr::create(SetLabel, getContext()));
+}
+
 void MCStreamer::emitAbsoluteSymbolDiff(const MCSymbol *Hi, const MCSymbol *Lo,
                                         unsigned Size) {
   // Get the Hi-Lo expression.
   const MCExpr *Diff =
       MCBinaryExpr::createSub(MCSymbolRefExpr::create(Hi, Context),
                               MCSymbolRefExpr::create(Lo, Context), Context);
 
   const MCAsmInfo *MAI = Context.getAsmInfo();