DWARFDebugLoclists: Move to a incremental parsing model

Summary:
This patch stems from the discussion D68270 (including some offline
talks). The idea is to provide an "incremental" api for parsing location
lists, which will avoid caching or materializing parsed data. An
additional goal is to provide a high level location list api, which
abstracts the differences between different encoding schemes, and can be
used by users which don't care about those (such as LLDB).

This patch implements the first part. It implements a call-back based
"visitLocationList" api. This function parses a single location list,
calling a user-specified callback for each entry. This is going to be
the base api, which other location list functions (right now, just the
dumping code) are going to be based on.

Future patches will do something similar for the v4 location lists, and
add a mechanism to translate raw entries into concrete address ranges.

Reviewers: dblaikie, probinson, JDevlieghere, aprantl, SouraVX

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D69672

3 files changed, 120 insertions, 123 deletions

diff --git a/llvm/lib/DebugInfo/DWARF/DWARFContext.cpp b/llvm/lib/DebugInfo/DWARF/DWARFContext.cpp
index c5766b4440d..e13b3836b13 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFContext.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFContext.cpp
@@ -300,11 +300,21 @@ static void dumpLoclistsSection(raw_ostream &OS, DIDumpOptions DumpOpts,
 
     Header.dump(OS, DumpOpts);
 
-    DWARFDebugLoclists Loclists;
     uint64_t EndOffset = Header.length() + Header.getHeaderOffset();
     Data.setAddressSize(Header.getAddrSize());
-    Loclists.parse(Data, Offset, EndOffset, Header.getVersion());
-    Loclists.dump(OS, 0, MRI, DumpOpts, DumpOffset);
+    if (DumpOffset) {
+      if (DumpOffset >= Offset && DumpOffset < EndOffset) {
+        Offset = *DumpOffset;
+        DWARFDebugLoclists::dumpLocationList(Data, &Offset, Header.getVersion(),
+                                             OS, /*BaseAddr=*/0, MRI, nullptr,
+                                             DumpOpts, /*Indent=*/0);
+        OS << "\n";
+        return;
+      }
+    } else {
+      DWARFDebugLoclists::dumpRange(Data, Offset, EndOffset - Offset,
+                                    Header.getVersion(), OS, 0, MRI, DumpOpts);
+    }
     Offset = EndOffset;
   }
 }
@@ -393,7 +403,19 @@ void DWARFContext::dump(
   if (const auto *Off =
           shouldDump(ExplicitDWO, ".debug_loc.dwo", DIDT_ID_DebugLoc,
                      DObj->getLocDWOSection().Data)) {
-    getDebugLocDWO()->dump(OS, 0, getRegisterInfo(), DumpOpts, *Off);
+    DWARFDataExtractor Data(*DObj, DObj->getLocDWOSection(), isLittleEndian(),
+                            4);
+    if (*Off) {
+      uint64_t Offset = **Off;
+      DWARFDebugLoclists::dumpLocationList(Data, &Offset, /*Version=*/4, OS,
+                                           /*BaseAddr=*/0, getRegisterInfo(),
+                                           nullptr, DumpOpts, /*Indent=*/0);
+      OS << "\n";
+    } else {
+      DWARFDebugLoclists::dumpRange(Data, 0, Data.getData().size(),
+                                    /*Version=*/4, OS, /*BaseAddr=*/0,
+                                    getRegisterInfo(), DumpOpts);
+    }
   }
 
   if (const auto *Off = shouldDump(Explicit, ".debug_frame", DIDT_ID_DebugFrame,
@@ -724,23 +746,6 @@ const DWARFDebugLoc *DWARFContext::getDebugLoc() {
   return Loc.get();
 }
 
-const DWARFDebugLoclists *DWARFContext::getDebugLocDWO() {
-  if (LocDWO)
-    return LocDWO.get();
-
-  LocDWO.reset(new DWARFDebugLoclists());
-  // Assume all compile units have the same address byte size.
-  // FIXME: We don't need AddressSize for split DWARF since relocatable
-  // addresses cannot appear there. At the moment DWARFExpression requires it.
-  DWARFDataExtractor LocData(*DObj, DObj->getLocDWOSection(), isLittleEndian(),
-                             4);
-  // Use version 4. DWO does not support the DWARF v5 .debug_loclists yet and
-  // that means we are parsing the new style .debug_loc (pre-standatized version
-  // of the .debug_loclists).
-  LocDWO->parse(LocData, 0, LocData.getData().size(), 4 /* Version */);
-  return LocDWO.get();
-}
-
 const DWARFDebugAranges *DWARFContext::getDebugAranges() {
   if (Aranges)
     return Aranges.get();
diff --git a/llvm/lib/DebugInfo/DWARF/DWARFDebugLoc.cpp b/llvm/lib/DebugInfo/DWARF/DWARFDebugLoc.cpp
index 032feb9088c..e0faaed035d 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFDebugLoc.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFDebugLoc.cpp
@@ -139,19 +139,19 @@ void DWARFDebugLoc::parse(const DWARFDataExtractor &data) {
   }
 }
 
-Expected<DWARFDebugLoclists::LocationList>
-DWARFDebugLoclists::parseOneLocationList(const DWARFDataExtractor &Data,
-                                         uint64_t *Offset, unsigned Version) {
-  LocationList LL;
-  LL.Offset = *Offset;
-  DataExtractor::Cursor C(*Offset);
+Error DWARFDebugLoclists::visitLocationList(
+    const DWARFDataExtractor &Data, uint64_t *Offset, uint16_t Version,
+    llvm::function_ref<bool(const Entry &)> F) {
 
-  // dwarf::DW_LLE_end_of_list_entry is 0 and indicates the end of the list.
-  while (auto Kind = Data.getU8(C)) {
+  DataExtractor::Cursor C(*Offset);
+  bool Continue = true;
+  while (Continue) {
     Entry E;
-    E.Kind = Kind;
-    E.Offset = C.tell() - 1;
-    switch (Kind) {
+    E.Offset = C.tell();
+    E.Kind = Data.getU8(C);
+    switch (E.Kind) {
+    case dwarf::DW_LLE_end_of_list:
+      break;
     case dwarf::DW_LLE_base_addressx:
       E.Value0 = Data.getULEB128(C);
       break;
@@ -164,10 +164,6 @@ DWARFDebugLoclists::parseOneLocationList(const DWARFDataExtractor &Data,
       else
         E.Value1 = Data.getULEB128(C);
       break;
-    case dwarf::DW_LLE_start_length:
-      E.Value0 = Data.getRelocatedAddress(C);
-      E.Value1 = Data.getULEB128(C);
-      break;
     case dwarf::DW_LLE_offset_pair:
       E.Value0 = Data.getULEB128(C);
       E.Value1 = Data.getULEB128(C);
@@ -175,53 +171,62 @@ DWARFDebugLoclists::parseOneLocationList(const DWARFDataExtractor &Data,
     case dwarf::DW_LLE_base_address:
       E.Value0 = Data.getRelocatedAddress(C);
       break;
+    case dwarf::DW_LLE_start_length:
+      E.Value0 = Data.getRelocatedAddress(C);
+      E.Value1 = Data.getULEB128(C);
+      break;
+    case dwarf::DW_LLE_startx_endx:
+    case dwarf::DW_LLE_default_location:
+    case dwarf::DW_LLE_start_end:
     default:
       cantFail(C.takeError());
       return createStringError(errc::illegal_byte_sequence,
-                               "LLE of kind %x not supported", (int)Kind);
+                               "LLE of kind %x not supported", (int)E.Kind);
     }
 
-    if (Kind != dwarf::DW_LLE_base_address &&
-        Kind != dwarf::DW_LLE_base_addressx) {
+    if (E.Kind != dwarf::DW_LLE_base_address &&
+        E.Kind != dwarf::DW_LLE_base_addressx &&
+        E.Kind != dwarf::DW_LLE_end_of_list) {
       unsigned Bytes = Version >= 5 ? Data.getULEB128(C) : Data.getU16(C);
       // A single location description describing the location of the object...
       Data.getU8(C, E.Loc, Bytes);
     }
 
-    LL.Entries.push_back(std::move(E));
+    if (!C)
+      return C.takeError();
+    Continue = F(E) && E.Kind != dwarf::DW_LLE_end_of_list;
   }
-  if (Error Err = C.takeError())
-    return std::move(Err);
-  Entry E;
-  E.Kind = dwarf::DW_LLE_end_of_list;
-  E.Offset = C.tell() - 1;
-  LL.Entries.push_back(E);
   *Offset = C.tell();
-  return LL;
+  return Error::success();
 }
 
-void DWARFDebugLoclists::parse(const DWARFDataExtractor &data, uint64_t Offset,
-                               uint64_t EndOffset, uint16_t Version) {
-  IsLittleEndian = data.isLittleEndian();
-  AddressSize = data.getAddressSize();
-
-  while (Offset < EndOffset) {
-    if (auto LL = parseOneLocationList(data, &Offset, Version))
-      Locations.push_back(std::move(*LL));
-    else {
-      logAllUnhandledErrors(LL.takeError(), WithColor::error());
-      return;
-    }
+bool DWARFDebugLoclists::dumpLocationList(const DWARFDataExtractor &Data,
+                                          uint64_t *Offset, uint16_t Version,
+                                          raw_ostream &OS, uint64_t BaseAddr,
+                                          const MCRegisterInfo *MRI,
+                                          DWARFUnit *U, DIDumpOptions DumpOpts,
+                                          unsigned Indent) {
+  size_t MaxEncodingStringLength = 0;
+  if (DumpOpts.Verbose) {
+#define HANDLE_DW_LLE(ID, NAME)                                                \
+  MaxEncodingStringLength = std::max(MaxEncodingStringLength,                  \
+                                     dwarf::LocListEncodingString(ID).size());
+#include "llvm/BinaryFormat/Dwarf.def"
   }
-}
 
-DWARFDebugLoclists::LocationList const *
-DWARFDebugLoclists::getLocationListAtOffset(uint64_t Offset) const {
-  auto It = partition_point(
-      Locations, [=](const LocationList &L) { return L.Offset < Offset; });
-  if (It != Locations.end() && It->Offset == Offset)
-    return &(*It);
-  return nullptr;
+  OS << format("0x%8.8" PRIx64 ": ", *Offset);
+  Error E = visitLocationList(Data, Offset, Version, [&](const Entry &E) {
+    E.dump(OS, BaseAddr, Data.isLittleEndian(), Data.getAddressSize(), MRI, U,
+           DumpOpts, Indent, MaxEncodingStringLength);
+    return true;
+  });
+  if (E) {
+    OS << "\n";
+    OS.indent(Indent);
+    OS << "error: " << toString(std::move(E));
+    return false;
+  }
+  return true;
 }
 
 void DWARFDebugLoclists::Entry::dump(raw_ostream &OS, uint64_t &BaseAddr,
@@ -297,44 +302,25 @@ void DWARFDebugLoclists::Entry::dump(raw_ostream &OS, uint64_t &BaseAddr,
 
   dumpExpression(OS, Loc, IsLittleEndian, AddressSize, MRI, U);
 }
-void DWARFDebugLoclists::LocationList::dump(raw_ostream &OS, uint64_t BaseAddr,
-                                            bool IsLittleEndian,
-                                            unsigned AddressSize,
-                                            const MCRegisterInfo *MRI,
-                                            DWARFUnit *U,
-                                            DIDumpOptions DumpOpts, 
-                                            unsigned Indent) const {
-  size_t MaxEncodingStringLength = 0;
-  if (DumpOpts.Verbose)
-    for (const auto &Entry : Entries)
-      MaxEncodingStringLength =
-          std::max(MaxEncodingStringLength,
-                   dwarf::LocListEncodingString(Entry.Kind).size());
-
-  for (const Entry &E : Entries)
-    E.dump(OS, BaseAddr, IsLittleEndian, AddressSize, MRI, U, DumpOpts, Indent,
-           MaxEncodingStringLength);
-}
-
-void DWARFDebugLoclists::dump(raw_ostream &OS, uint64_t BaseAddr,
-                              const MCRegisterInfo *MRI, DIDumpOptions DumpOpts, 
-                              Optional<uint64_t> Offset) const {
-  auto DumpLocationList = [&](const LocationList &L) {
-    OS << format("0x%8.8" PRIx64 ": ", L.Offset);
-    L.dump(OS, BaseAddr, IsLittleEndian, AddressSize, MRI, nullptr, DumpOpts,
-           /*Indent=*/12);
-    OS << "\n";
-  };
 
-  if (Offset) {
-    if (auto *L = getLocationListAtOffset(*Offset))
-      DumpLocationList(*L);
+void DWARFDebugLoclists::dumpRange(const DWARFDataExtractor &Data,
+                                   uint64_t StartOffset, uint64_t Size,
+                                   uint16_t Version, raw_ostream &OS,
+                                   uint64_t BaseAddr, const MCRegisterInfo *MRI,
+                                   DIDumpOptions DumpOpts) {
+  if (!Data.isValidOffsetForDataOfSize(StartOffset, Size))  {
+    OS << "Invalid dump range\n";
     return;
   }
-
-  for (const LocationList &L : Locations) {
-    DumpLocationList(L);
-    if (&L != &Locations.back())
-      OS << '\n';
+  uint64_t Offset = StartOffset;
+  StringRef Separator;
+  bool CanContinue = true;
+  while (CanContinue && Offset < StartOffset + Size) {
+    OS << Separator;
+    Separator = "\n";
+
+    CanContinue = dumpLocationList(Data, &Offset, Version, OS, BaseAddr, MRI,
+                                   nullptr, DumpOpts, /*Indent=*/12);
+    OS << '\n';
   }
 }
diff --git a/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp b/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
index f278a7a205e..ebc8cc565f3 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFDie.cpp
@@ -91,30 +91,32 @@ static void dumpLocation(raw_ostream &OS, DWARFFormValue &FormValue,
     return;
   }
 
-  FormValue.dump(OS, DumpOpts);
-  const auto &DumpLL = [&](auto ExpectedLL) {
-    if (ExpectedLL) {
-      uint64_t BaseAddr = 0;
-      if (Optional<object::SectionedAddress> BA = U->getBaseAddress())
-        BaseAddr = BA->Address;
-      auto LLDumpOpts = DumpOpts;
-      LLDumpOpts.Verbose = false;
-      ExpectedLL->dump(OS, BaseAddr, Ctx.isLittleEndian(), Obj.getAddressSize(),
-                       MRI, U, LLDumpOpts, Indent);
-    } else {
-      OS << '\n';
-      OS.indent(Indent);
-      OS << formatv("error extracting location list: {0}",
-                    fmt_consume(ExpectedLL.takeError()));
-    }
-  };
   if (FormValue.isFormClass(DWARFFormValue::FC_SectionOffset)) {
     uint64_t Offset = *FormValue.getAsSectionOffset();
+    uint64_t BaseAddr = 0;
+    if (Optional<object::SectionedAddress> BA = U->getBaseAddress())
+      BaseAddr = BA->Address;
+    auto LLDumpOpts = DumpOpts;
+    LLDumpOpts.Verbose = false;
+
     if (!U->isDWOUnit() && !U->getLocSection()->Data.empty()) {
       DWARFDebugLoc DebugLoc;
       DWARFDataExtractor Data(Obj, *U->getLocSection(), Ctx.isLittleEndian(),
                               Obj.getAddressSize());
-      DumpLL(DebugLoc.parseOneLocationList(Data, &Offset));
+
+      FormValue.dump(OS, DumpOpts);
+      OS << ": ";
+
+      if (Expected<DWARFDebugLoc::LocationList> LL =
+              DebugLoc.parseOneLocationList(Data, &Offset)) {
+        LL->dump(OS, BaseAddr, Ctx.isLittleEndian(), Obj.getAddressSize(), MRI,
+                 U, LLDumpOpts, Indent);
+      } else {
+        OS << '\n';
+        OS.indent(Indent);
+        OS << formatv("error extracting location list: {0}",
+                      fmt_consume(LL.takeError()));
+      }
       return;
     }
 
@@ -131,10 +133,14 @@ static void dumpLocation(raw_ostream &OS, DWARFFormValue &FormValue,
       // Modern locations list (.debug_loclists) are used starting from v5.
       // Ideally we should take the version from the .debug_loclists section
       // header, but using CU's version for simplicity.
-      DumpLL(DWARFDebugLoclists::parseOneLocationList(
-          Data, &Offset, UseLocLists ? U->getVersion() : 4));
+      DWARFDebugLoclists::dumpLocationList(
+          Data, &Offset, UseLocLists ? U->getVersion() : 4, OS, BaseAddr, MRI,
+          U, LLDumpOpts, Indent);
     }
+    return;
   }
+
+  FormValue.dump(OS, DumpOpts);
 }
 
 /// Dump the name encoded in the type tag.