[DWARFv5] Support FORM_strp in .debug_line.dwo

[probinson]

Summary

As a side effect, the .debug_line section will be dumped in physical
order, rather than in the order that compile units refer to their
associated portions of the .debug_line section. These are probably
always the same order anyway, and no tests noticed the difference.

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

213–217

Might make more sense for this function to return the map by value, rather than take it by reference, clear it, and populate it?

335

Probably be more specific/descriptive.

This also appears to be a regression - before your patch this code did the right thing (used the corresponding CU's address byte size for each CU) for non-DWO CUs, though it was probably wrong for DWO CUs by using this saved thing. But with your patch it now does the same sketchy thing for DWO and non-DWO CUs?

336–339

A loop that only runs once seems a bit odd, though I realize it's pretty compact.

[probinson]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

213–217

Agreed.

335

I had tried to fix this properly (allowing a v5 line table to be dumped with no Unit) but tripped over a different issue, and decided to defer it to the next patch. I think you are right that I could leave this set from the Unit whenever there is one, and pre-v5 basically there always has to be one.

336–339

Copied from the dwo case. Technically it could run zero times.
But if I set the size from the Unit, inside the dump loop, this goes away anyhow.

[probinson]

Address @dblaikie comments.

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

344–348

Would it make sense to sink this down into the LineTable parsing logic, so that the unit isn't looked up when it's not needed? (when using more recent line table formats that have a standalone description (if I'm understanding the DWARF5 line table support correctly))

[probinson]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

344–348

We need to look up the unit anyway. The unit is how the LineTable parsing finds the string section, and .debug_str_offsets (for FORM_strx). And the .debug_addr section, once I get to that. We could defer setting the data extractor's address size until we're down into LineTable, but we can't defer looking up the unit.

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

344–348

Hmm, then I'm confused - I had thought one of the goals of the new line table work was to make it standalone/parsable without the debug_info? Any idea if that has been a goal? Or just something I totally misunderstood?

[probinson]

(Moving the why-do-we-need-the-unit discussion out of the inline comments.)

I do have a goal of being able to handle a line table without a unit, when possible. However, there are constraints, and many times you still end up needing a unit. Sadly, the caller of the line-table parser doesn't know whether the unit will be needed.

In fact, for dumping a .debug_line.dwo, the unit should *not* be needed. A .dwo doesn't have any addresses in it, and won't be v2, so all it needs to know is the 32/64 format, which is in the line-table header. However, because of how libDebugInfo works, the string-section handles are in DWARFUnit. So, for a v5 line-table header that uses any indirect string form, the parser still needs the DWARFUnit even though it doesn't need the .debug_info compile/type unit. I tilted at that windmill several times, and the windmill won every time.

If we defer looking up the unit until the line-table parser needs to know it, then the parser will frequently end up doing the linear scan through the units until it finds the right one (O(N*N/2)). It seemed less inefficient to scan all the units once and do a map lookup each time instead (O(N+NlogN)). I am guessing it will be unusual for a line table *not* to need the unit, so the unconditional lookup seemed like the better choice. And the parser doesn't know whether it should search the normal or .dwo CUs, so.... might as well just do it up front in the caller.

This does not mean my prior work was wasted, because with v5 using forms in the line-table header, the FormParams had to be split out anyway. But even with v5, if the header uses FORM_strx, or the line-number program wants to use the .debug_addr table, we still need the unit. (And again, given how libDebugInfo works, even FORM_strp needs the DWARFUnit, even though it doesn't need anything from the actual compile unit.)

As I mentioned elsewhere, for my next trick I will conjure up a standalone v5 line table, and parse it without the assistance of any units. But it will have to use all inline strings, until I can come back around to tracking the string sections independently of the DWARFUnit.

[JDevlieghere]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

341

Why don't we need the address byte size here anymore? I'm super excited you got rid of the "sketchy loop" below, but I'd like to understand why we can do without it.

[probinson]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

341

Theoretically it can vary per unit. The address size is still set below, inside the while loop, after we look up the unit associated with this part of the line-table section.

[probinson]

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

341

Technically I should set the address size to zero for a .debug_line portion with no associated unit. If it's a v5 portion, we can establish the address size from the v5 header. If it's not a v5 portion, then we should still be able to parse/dump the header, but we'd have to skip over the line-number program. But I didn't want to get that far into things with this patch, there is some other lurking bug that will take a little time to track down.

[probinson]

Oh, head-smack! You don't need a unit to know the address size; the line table has always had that info, although indirectly.
DW_LNE_set_address (the only opcode that specifies an actual address) is an extended opcode, which has a ULEB telling you how long the operands are. Which is, one byte for the opcode, and.... the size of the address. Doh!

That means, DWARF v5 is the first time we actually *do* (sometimes) need a unit to parse the .debug_line section, instead of the first time we *don't* need it.

This patch is about one of the cases where we do need a DWARFUnit, so I think it's not particularly affected by this revelation, but there is likely to be some simplification that can be done as a follow-up.

[JDevlieghere]

In D39854#922574, @probinson wrote:

Oh, head-smack! You don't need a unit to know the address size; the line table has always had that info, although indirectly.
DW_LNE_set_address (the only opcode that specifies an actual address) is an extended opcode, which has a ULEB telling you how long the operands are. Which is, one byte for the opcode, and.... the size of the address. Doh!

That means, DWARF v5 is the first time we actually *do* (sometimes) need a unit to parse the .debug_line section, instead of the first time we *don't* need it.

This patch is about one of the cases where we do need a DWARFUnit, so I think it's not particularly affected by this revelation, but there is likely to be some simplification that can be done as a follow-up.

I missed the call to setAddressSize below, but I'm glad that I did. Thanks for explaining Paul!

[probinson]

Use address-size zero for the DWARFDataExtractor, in the .dwo section.
This required relaxing an assertion in the line-table parser. If there's no line-number program, the address size isn't needed, and if there is one, attempting to retrieve an address will assert farther down.

Technically we can derive the address size from the line-number program, but I wanted to leave that for the next patch.

[probinson]

Ping. I am moderately sure I addressed everything people asked about; if there are still questions please remind me.

[JDevlieghere]

Looks good to me!

(Adrian is out until after Thanksgiving, just in case you're waiting for his blessing)

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

while (offset < size) {
       const char *S = StrData.getCStr(&StringOffset);
       if (S)
         OS << format("\"%s\"", S);
       OS << "\n";
     }
   }
 }
 
+// We want to supply the Unit associated with a .debug_line[.dwo] table when
+// we dump it, if possible, but still dump the table even if there isn't a Unit.
+// Therefore, collect up handles on all the Units that point into the
+// line-table section.
+typedef std::map<uint64_t, DWARFUnit *> LineToUnitMap;
+
+static LineToUnitMap
+buildLineToUnitMap(DWARFContext::cu_iterator_range CUs,
+                   DWARFContext::tu_section_iterator_range TUSections) {
+  LineToUnitMap LineToUnit;
+  for (const auto &CU : CUs)
+    if (auto CUDIE = CU->getUnitDIE())
+      if (auto StmtOffset = toSectionOffset(CUDIE.find(DW_AT_stmt_list)))
+        LineToUnit.insert(std::make_pair(*StmtOffset, &*CU));
+  for (const auto &TUS : TUSections)
+    for (const auto &TU : TUS)
+      if (auto TUDIE = TU->getUnitDIE())
+        if (auto StmtOffset = toSectionOffset(TUDIE.find(DW_AT_stmt_list)))
+          LineToUnit.insert(std::make_pair(*StmtOffset, &*TU));
+  return LineToUnit;
+}
+
 void DWARFContext::dump(
     raw_ostream &OS, DIDumpOptions DumpOpts,
     std::array<Optional<uint64_t>, DIDT_ID_Count> DumpOffsets) {
 
   Optional<uint64_t> DumpOffset;
   uint64_t DumpType = DumpOpts.DumpType;
 
   StringRef Extension = sys::path::extension(DObj->getFileName());
if (shouldDump(Explicit, ".debug_aranges", DIDT_ID_DebugAranges,
                  DObj->getARangeSection())) {
     uint32_t offset = 0;
     DataExtractor arangesData(DObj->getARangeSection(), isLittleEndian(), 0);
     DWARFDebugArangeSet set;
     while (set.extract(arangesData, &offset))
       set.dump(OS);
   }
 
-  uint8_t savedAddressByteSize = 0;
   if (shouldDump(Explicit, ".debug_line", DIDT_ID_DebugLine,
                  DObj->getLineSection().Data)) {
-    for (const auto &CU : compile_units()) {
-      savedAddressByteSize = CU->getAddressByteSize();
-      auto CUDIE = CU->getUnitDIE();
-      if (!CUDIE)
-        continue;
-      if (auto StmtOffset = toSectionOffset(CUDIE.find(DW_AT_stmt_list))) {
-        if (DumpOffset && *StmtOffset != *DumpOffset)
-          continue;
-        DWARFDataExtractor lineData(*DObj, DObj->getLineSection(),
-                                    isLittleEndian(), savedAddressByteSize);
-        DWARFDebugLine::LineTable LineTable;
-        uint32_t Offset = *StmtOffset;
-        // Verbose dumping is done during parsing and not on the intermediate
-        // representation.
-        OS << "debug_line[" << format("0x%8.8x", Offset) << "]\n";
-        if (DumpOpts.Verbose) {
-          LineTable.parse(lineData, &Offset, &*CU, &OS);
-        } else {
-          LineTable.parse(lineData, &Offset, &*CU);
-          LineTable.dump(OS);
-        }
-      }
-    }
-  }
+    LineToUnitMap LineToUnit =
+        buildLineToUnitMap(compile_units(), type_unit_sections());
+    unsigned Offset = 0;
+    DWARFDataExtractor LineData(*DObj, DObj->getLineSection(), isLittleEndian(),
+                                0);
+    while (Offset < LineData.getData().size()) {
+      DWARFUnit *U = nullptr;
+      auto It = LineToUnit.find(Offset);
+      if (It != LineToUnit.end()) {
+        U = It->second;
+        LineData.setAddressSize(U->getAddressByteSize());
+      }
+      if (DumpOffset && Offset != *DumpOffset) {
+        // Find the size of this part of the line table section and skip it.
+        unsigned OldOffset = Offset;
+        LineTable.Prologue.parse(LineData, &Offset, U);
+        Offset = OldOffset + LineTable.Prologue.TotalLength +
+                 LineTable.Prologue.sizeofTotalLength();
+        continue;
+      }
+        LineTable.parse(LineData, &Offset, U, &OS);
+        LineTable.parse(LineData, &Offset, U);
 
-  // FIXME: This seems sketchy.
-  for (const auto &CU : compile_units()) {
-    savedAddressByteSize = CU->getAddressByteSize();
-    break;
-  }
   if (shouldDump(ExplicitDWO, ".debug_line.dwo", DIDT_ID_DebugLine,
                  DObj->getLineDWOSection().Data)) {
-    unsigned stmtOffset = 0;
-    DWARFDataExtractor lineData(*DObj, DObj->getLineDWOSection(),
-                                isLittleEndian(), savedAddressByteSize);
+    LineToUnitMap LineToUnit =
+        buildLineToUnitMap(dwo_compile_units(), dwo_type_unit_sections());
+    unsigned Offset = 0;
+    DWARFDataExtractor LineData(*DObj, DObj->getLineDWOSection(),
+                                isLittleEndian(), 0);
+    while (Offset < LineData.getData().size()) {
+      DWARFUnit *U = nullptr;
+      auto It = LineToUnit.find(Offset);
+      if (It != LineToUnit.end())
+        U = It->second;
       DWARFDebugLine::LineTable LineTable;
-    while (LineTable.Prologue.parse(lineData, &stmtOffset, nullptr)) {
+      if (!LineTable.Prologue.parse(LineData, &Offset, U))
+        break;
       LineTable.dump(OS);
-      LineTable.clear();
     }
   }
 
   if (shouldDump(Explicit, ".debug_cu_index", DIDT_ID_DebugCUIndex,
                  DObj->getCUIndexSection())) {
     getCUIndex().dump(OS);
   }
 
void DWARFContext::dump(
 
   if (shouldDump(Explicit, ".debug_ranges", DIDT_ID_DebugRanges,
                  DObj->getRangeSection().Data)) {
     // In fact, different compile units may have different address byte
     // sizes, but for simplicity we just use the address byte size of the
     // last compile unit (there is no easy and fast way to associate address
     // range list and the compile unit it describes).
     // FIXME: savedAddressByteSize seems sketchy.
+    uint8_t savedAddressByteSize = 0;
+    for (const auto &CU : compile_units()) {
+      savedAddressByteSize = CU->getAddressByteSize();
+      break;
+    }
     DWARFDataExtractor rangesData(*DObj, DObj->getRangeSection(),
                                   isLittleEndian(), savedAddressByteSize);
     uint32_t offset = 0;
     DWARFDebugRangeList rangeList;
     while (rangeList.extract(rangesData, &offset))
       rangeList.dump(OS);
   }
 

llvm/lib/DebugInfo/DWARF/DWARFDebugLine.cpp

if (TotalLength == UINT32_MAX) {
     return false;
   }
   FormParams.Version = DebugLineData.getU16(OffsetPtr);
   if (getVersion() < 2)
     return false;
 
   if (getVersion() >= 5) {
     FormParams.AddrSize = DebugLineData.getU8(OffsetPtr);
-    assert(getAddressSize() == DebugLineData.getAddressSize() &&
+    assert((DebugLineData.getAddressSize() == 0 ||
+            DebugLineData.getAddressSize() == getAddressSize()) &&
            "Line table header and data extractor disagree");
     SegSelectorSize = DebugLineData.getU8(OffsetPtr);
   }
 
   PrologueLength = DebugLineData.getUnsigned(OffsetPtr, sizeofPrologueLength());
   const uint64_t EndPrologueOffset = PrologueLength + *OffsetPtr;
   MinInstLength = DebugLineData.getU8(OffsetPtr);
   if (getVersion() >= 4)

llvm/test/DebugInfo/X86/dwarfdump-header.s

 str_LT_5a:
         .asciz "Directory5a"
 str_LT_5b:
         .asciz "Directory5b"
 
         .section .debug_str.dwo,"MS",@progbits,1
 dwo_TU_5:
         .asciz "V5_split_type_unit"
+dwo_producer:
+        .asciz "Handmade DWO producer"
+dwo_CU_5:
+        .asciz "V5_dwo_compile_unit"
+dwo_LT_5a:
+        .asciz "DWODirectory5a"
+dwo_LT_5b:
+        .asciz "DWODirectory5b"
 
 # All CUs/TUs use the same abbrev section for simplicity.
         .section .debug_abbrev,"",@progbits
         .byte 0x01  # Abbrev code
         .byte 0x11  # DW_TAG_compile_unit
         .byte 0x00  # DW_CHILDREN_no
         .byte 0x25  # DW_AT_producer
         .byte 0x0e  # DW_FORM_strp
# And a .dwo copy for the .dwo sections.
         .section .debug_abbrev.dwo,"",@progbits
         .byte 0x01  # Abbrev code
         .byte 0x11  # DW_TAG_compile_unit
         .byte 0x00  # DW_CHILDREN_no
         .byte 0x25  # DW_AT_producer
         .byte 0x0e  # DW_FORM_strp
         .byte 0x03  # DW_AT_name
         .byte 0x0e  # DW_FORM_strp
+        .byte 0x10  # DW_AT_stmt_list
+        .byte 0x17  # DW_FORM_sec_offset
         .byte 0x00  # EOM(1)
         .byte 0x00  # EOM(2)
         .byte 0x02  # Abbrev code
         .byte 0x41  # DW_TAG_type_unit
         .byte 0x01  # DW_CHILDREN_yes
         .byte 0x03  # DW_AT_name
         .byte 0x0e  # DW_FORM_strp
         .byte 0x00  # EOM(1)
# The compile-unit DIE, with DW_AT_producer, DW_AT_name, DW_AT_stmt_list.
         .long str_CU_5
         .long LH_5_start
         .byte 0 # NULL
 CU_5_end:
 
 # CHECK: 0x00000019: Compile Unit: length = 0x00000016 version = 0x0005 unit_type = DW_UT_compile abbr_offset = 0x0000 addr_size = 0x08 (next unit at 0x00000033)
 # CHECK: 0x00000025: DW_TAG_compile_unit
 
+        .section .debug_info.dwo,"",@progbits
+# CHECK-LABEL: .debug_info.dwo
+
+# DWARF v5 split CU header.
+        .long  CU_split_5_end-CU_split_5_version # Length of Unit
+CU_split_5_version:
+        .short 5                # DWARF version number
+        .byte 5                 # DWARF Unit Type
+        .byte 8                 # Address Size (in bytes)
+        .long .debug_abbrev.dwo # Offset Into Abbrev. Section
+# The split compile-unit DIE, with DW_AT_producer, DW_AT_name, DW_AT_stmt_list.
+        .byte 1
+        .long dwo_producer
+        .long dwo_CU_5
+        .long dwo_LH_5_start
+        .byte 0 # NULL
+CU_split_5_end:
+
+# CHECK: 0x00000000: Compile Unit: length = 0x00000016 version = 0x0005 unit_type = DW_UT_split_compile abbr_offset = 0x0000 addr_size = 0x08 (next unit at 0x0000001a)
+# CHECK: 0x0000000c: DW_TAG_compile_unit
+# CHECK-NEXT: DW_AT_producer {{.*}} "Handmade DWO producer"
+# CHECK-NEXT: DW_AT_name {{.*}} "V5_dwo_compile_unit"
+
         .section .debug_types,"",@progbits
 # CHECK-LABEL: .debug_types contents:
 
 # DWARF v4 Type unit header. Normal/split are identical so we do only one.
 TU_4_start:
         .long  TU_4_end-TU_4_version  # Length of Unit
 TU_4_version:
         .short 4               # DWARF version number

 # CHECK: seg_select_size: 0
 # CHECK: max_ops_per_inst: 1
 # CHECK: include_directories[  1] = 'Directory5a'
 # CHECK: include_directories[  2] = 'Directory5b'
 # CHECK-NOT: include_directories
 # CHECK: file_names[  1]    1 0x00000051 0x00000052 File5a{{$}}
 # CHECK: file_names[  2]    2 0x00000053 0x00000054 File5b{{$}}
 # CHECK-NOT: file_names
+
+  .section .debug_line.dwo,"",@progbits
+# CHECK-LABEL: .debug_line.dwo
+
+# DWARF v5 DWO line-table header.
+dwo_LH_5_start:
+        .long   dwo_LH_5_end-dwo_LH_5_version   # Length of Unit
+dwo_LH_5_version:
+        .short  5               # DWARF version number
+        .byte   8               # Address Size
+        .byte   0               # Segment Selector Size
+        .long   dwo_LH_5_header_end-dwo_LH_5_params # Length of Prologue
+dwo_LH_5_params:
+        .byte   1               # Minimum Instruction Length
+        .byte   1               # Maximum Operations per Instruction
+        .byte   1               # Default is_stmt
+        .byte   -5              # Line Base
+        .byte   14              # Line Range
+        .byte   13              # Opcode Base
+        .byte   0               # Standard Opcode Lengths
+        .byte   1
+        .byte   1
+        .byte   1
+        .byte   1
+        .byte   0
+        .byte   0
+        .byte   0
+        .byte   1
+        .byte   0
+        .byte   0
+        .byte   1
+        # Directory table format
+        .byte   1               # One element per directory entry
+        .byte   1               # DW_LNCT_path
+        .byte   0x0e            # DW_FORM_strp (-> .debug_str.dwo)
+        # Directory table entries
+        .byte   2               # Two directories
+        .long   dwo_LT_5a
+        .long   dwo_LT_5b
+        # File table format
+        .byte   4               # Four elements per file entry
+        .byte   1               # DW_LNCT_path
+        .byte   0x08            # DW_FORM_string
+        .byte   2               # DW_LNCT_directory_index
+        .byte   0x0b            # DW_FORM_data1
+        .byte   3               # DW_LNCT_timestamp
+        .byte   0x0f            # DW_FORM_udata
+        .byte   4               # DW_LNCT_size
+        .byte   0x0f            # DW_FORM_udata
+        # File table entries
+        .byte   2               # Two files
+        .asciz "DWOFile5a"
+        .byte   1
+        .byte   0x15
+        .byte   0x25
+        .asciz "DWOFile5b"
+        .byte   2
+        .byte   0x35
+        .byte   0x45
+dwo_LH_5_header_end:
+        # Line number program, which is empty.
+dwo_LH_5_end:
+
+# CHECK: Line table prologue:
+# CHECK: version: 5
+# CHECK: address_size: 8
+# CHECK: seg_select_size: 0
+# CHECK: max_ops_per_inst: 1
+# CHECK: include_directories[  1] = 'DWODirectory5a'
+# CHECK: include_directories[  2] = 'DWODirectory5b'
+# CHECK-NOT: include_directories
+# CHECK: file_names[  1]    1 0x00000015 0x00000025 DWOFile5a{{$}}
+# CHECK: file_names[  2]    2 0x00000035 0x00000045 DWOFile5b{{$}}
+# CHECK-NOT: file_names