[WIP][Debuginfo][LLD] Remove obsolete debug info while garbage collecting.

[avl]

Summary

Remove obsolete debug info while garbage collecting.

This patch is an illustration for llvm-dev thread:
http://lists.llvm.org/pipermail/llvm-dev/2019-September/135068.html

It does "Proof of Concept" implementation for the "removing obsolete debug info while garbage collecting" problem.
It implements two features "Remove obsolete debug info" and "Alternative implementation for the types deduplication":

1. Remove obsolete debug info.
   
   Currently when the linker does garbage collection a lot of abandoned debug info is left behind. The patch skips the debug info (subprograms, address ranges, line sentences) that corresponds to the dead sections.
   
   Command-line option is added to lld: --gc-debuginfo. It removes pieces of debug information related to the discarded sections.
   
   Short description of the implementation:
   1. Examine compile unit`s address ranges, check whether they resolved into live section and put the corresponding subprogram into live subprograms list.
      
      For .debug_info section:
   2. Parse abbreviations and note attributes of lld/test/ELF/reference type. DIE with references should be patched, since offsets could become incorrect if some parts of .debug_info sections would be removed.
   3. Go through the list and parse live subprograms, scan through all references and mark reached DIEs as live.
   4. Scan all compile unit`s DIEs in continuous order, mark live DIEs for copying into the output section.
   5. After the whole marking finished: scan for .debug_info references and patch them according to the new section layout.
      
      For .debug_ranges/debug_rnglists
   6. Mark address entries related to live sections for copying into the output section.
      
      For .debug_line section:
   7. Mark line program pieces related to live sections for copying into the output section.
      
      Result(for gc-debuginfo-wo-types.s):
      
      A. .debug_info section:

            w/o -gc-debuginfo:                 |         with -gc-debuginfo:
                                               |
                                               |
0x0000000b: DW_TAG_compile_unit                | 0x0000000b: DW_TAG_compile_unit
  DW_AT_name        ("mod1.cpp")               |   DW_AT_name        ("mod1.cpp")
  DW_AT_low_pc      (0x0000000000000000)       |   DW_AT_low_pc      (0x0000000000000000)
  DW_AT_ranges      (0x00000000                |   DW_AT_ranges      (0x00000000
     [0x0000000000201010, 0x0000000000201018)  |     [0x0000000000201010, 0x0000000000201018))
     [0x0000000000000000, 0x0000000000000008)) |
                                               |
0x0000002a:   DW_TAG_subprogram                | 0x0000002a:   DW_TAG_subprogram
  DW_AT_low_pc    (0x0000000000201010)         |   DW_AT_low_pc    (0x0000000000201010)
  DW_AT_high_pc   (0x0000000000201018)         |   DW_AT_high_pc   (0x0000000000201018)
  DW_AT_name      ("func_mod1_used")           |   DW_AT_name      ("func_mod1_used")
  DW_AT_type      (0x00000082 "int")           |   DW_AT_type      (0x00000056 "int")
                                               |
0x00000047:     DW_TAG_formal_parameter        | 0x00000047:     DW_TAG_formal_parameter
  DW_AT_name    ("p1")                         |   DW_AT_name    ("p1")
  DW_AT_type    (0x00000082 "int")             |   DW_AT_type    (0x00000056 "int")
                                               |
0x00000055:     NULL                           | 0x00000055:     NULL
                                               |
0x00000056:   DW_TAG_subprogram                | 0x00000056:   DW_TAG_base_type
  DW_AT_low_pc    (0x0000000000000000)         |   DW_AT_name      ("int")
  DW_AT_high_pc   (0x0000000000000008)         |
  DW_AT_name      ("func_mod1_not_used")       | 0x0000005d:   NULL
  DW_AT_type      (0x00000082 "int")           |
                                               |
0x00000073:     DW_TAG_formal_parameter        |
  DW_AT_name    ("p1")                         |
  DW_AT_type    (0x00000082 "int")             |
                                               | 
0x00000081:     NULL                           |
                                               |
0x00000082:   DW_TAG_base_type                 |
  DW_AT_name      ("int")                      |
                                               |
0x00000089:   NULL                             |

B. .debug_ranges section:

            w/o -gc-debuginfo:                 |       with -gc-debuginfo:
                                               |
00000000 0000000000201010 0000000000201018     | 00000000 0000000000201010 0000000000201018 
00000000 0000000000000000 0000000000000008     | 00000000 <End of list>
00000000 <End of list>                         | 00000020 0000000000201020 0000000000201033
00000030 0000000000201020 0000000000201033     | 00000020 <End of list>
00000030 0000000000000000 000000000000000c     |
00000030 <End of list>                         |

C. .debug_line section:

w/o -gc-debuginfo:

debug_line[0x0000005c]
.....
Address            Line   Column File   ISA Discriminator Flags
------------------ ------ ------ ------ --- ------------- -------------
0x0000000000201010      3      0      1   0             0  is_stmt
0x0000000000201014      4     15      1   0             0  is_stmt prologue_end
0x0000000000201017      4      5      1   0             0 
0x0000000000201018      4      5      1   0             0  end_sequence
0x0000000000000000      7      0      1   0             0  is_stmt
0x0000000000000004      8     15      1   0             0  is_stmt prologue_end
0x0000000000000007      8      5      1   0             0 
0x0000000000000008      8      5      1   0             0  end_sequence

with -gc-debuginfo:

debug_line[0x0000005c]
.....
Address            Line   Column File   ISA Discriminator Flags
------------------ ------ ------ ------ --- ------------- -------------
0x0000000000201010      3      0      1   0             0  is_stmt
0x0000000000201014      4     15      1   0             0  is_stmt prologue_end
0x0000000000201017      4      5      1   0             0 
0x0000000000201018      4      5      1   0             0  end_sequence

2. Alternative implementation for the types deduplication.
   
   There already exists implementation for types deduplication: -fdebug-types-section. This patch uses another solution : parse DWARF, cut out duplicated types, patch type references to point to the single type definition.
   
   Command-line option is added to lld: --gc-debuginfo-types. It does alternative type deduplication while doing --gc-debuginfo.
   
   Short description of the implementation:
   1. Parse abbreviations and note attributes of reference type. references of DW_FORM_ref4 kind pointing to the types would be changed into DW_FORM_ref_addr.
   2. Scan all compile unit`s DIEs in continuous order, calculate type hash for types. Mark new type descriptions as live and put it`s offset into type map. Skip type descriptions which already have matching entry in the type map.
   3. After the whole marking finished: scan for type references and patch them according to the created type offsets map. Also scan for .debug_info references and patch them according to the new section layout.
      
      Result(for gc-debuginfo-with-types.s):

0x00000000: Compile Unit: length = 0x0000005a           | 0x00000000: Compile Unit: length = 0x0000005a 
                                                        |
0x0000000b: DW_TAG_compile_unit                         | 0x0000000b: DW_TAG_compile_unit
  DW_AT_name        ("mod1.cpp")                        |   DW_AT_name        ("mod1.cpp")
                                                        |
0x0000002a:   DW_TAG_subprogram                         | 0x0000002a:   DW_TAG_subprogram 
  DW_AT_name      ("func_mod1_used")                    |   DW_AT_name      ("func_mod1_used")
  DW_AT_type      (0x00000056 "int")                    |   DW_AT_type      (0x0000000000000056 "int")
                                                        |
0x00000047:     DW_TAG_formal_parameter                 | 0x00000047:     DW_TAG_formal_parameter
  DW_AT_name    ("p1")                                  |   DW_AT_name    ("p1")
  DW_AT_type    (0x00000056 "int")                      |   DW_AT_type    (0x0000000000000056 "int")
                                                        |
0x00000055:     NULL                                    | 0x00000055:     NULL
                                                        |
0x00000056:   DW_TAG_base_type                          | 0x00000056:   DW_TAG_base_type
  DW_AT_name      ("int")                               |   DW_AT_name      ("int")
                                                        |
0x0000005d:   NULL                                      | 0x0000005d:   NULL
                                                        |
0x0000005e: Compile Unit: length = 0x000000a7           | 0x0000005e: Compile Unit: length = 0x000000a0
                                                        |
0x00000069: DW_TAG_compile_unit                         | 0x00000069: DW_TAG_compile_unit
  DW_AT_name        ("mod2.cpp")                        |   DW_AT_name        ("mod2.cpp")
                                                        |
0x00000088:   DW_TAG_subprogram                         | 0x00000088:   DW_TAG_subprogram
  DW_AT_name      ("func_mod2_used")                    |   DW_AT_name      ("func_mod2_used")
  DW_AT_type      (0x000000c2 "int")                    |   DW_AT_type      (0x0000000000000056 "int")          
                                                        |
0x000000a5:     DW_TAG_formal_parameter                 | 0x000000a5:     DW_TAG_formal_parameter
  DW_AT_name    ("p1")                                  |   DW_AT_name    ("p1")
  DW_AT_type    (0x000000c9 "SS")                       |   DW_AT_type    (0x00000000000000c2 "SS")
                                                        |
0x000000b3:     DW_TAG_variable                         | 0x000000b3:     DW_TAG_variable
  DW_AT_name    ("is")                                  |   DW_AT_name    ("is")
  DW_AT_type    (0x000000ea "inner_SS")                 |   DW_AT_type    (0x00000000000000e3 "inner_SS")
                                                        |
0x000000c1:     NULL                                    | 0x000000c1:     NULL
                                                        |
0x000000c2:   DW_TAG_base_type                          |
  DW_AT_name      ("int")                               |
                                                        |
0x000000c9:   DW_TAG_structure_type                     | 0x000000c2:   DW_TAG_structure_type
  DW_AT_name      ("SS")                                |   DW_AT_name      ("SS")
                                                        |
0x000000d2:     DW_TAG_member                           | 0x000000cb:     DW_TAG_member
  DW_AT_name    ("a1")                                  |   DW_AT_name    ("a1")
  DW_AT_type    (0x000000c2 "int")                      |   DW_AT_type    (0x0000000000000056 "int")
                                                        |
0x000000de:     DW_TAG_member                           | 0x000000d7:     DW_TAG_member
  DW_AT_name    ("a2")                                  |   DW_AT_name    ("a2")
  DW_AT_type    (0x00000101 "float")                    |   DW_AT_type    (0x00000000000000fa "float")
                                                        |
0x000000ea:     DW_TAG_structure_type                   | 0x000000e3:     DW_TAG_structure_type
  DW_AT_name    ("inner_SS")                            |   DW_AT_name    ("inner_SS")
                                                        |
0x000000f3:       DW_TAG_member                         | 0x000000ec:       DW_TAG_member
  DW_AT_name  ("a1")                                    |   DW_AT_name  ("a1")
  DW_AT_type  (0x000000c2 "int")                        |   DW_AT_type  (0x0000000000000056 "int")
                                                        |
0x000000ff:       NULL                                  | 0x000000f8:       NULL
                                                        |
0x00000100:     NULL                                    | 0x000000f9:     NULL
                                                        |
0x00000101:   DW_TAG_base_type                          | 0x000000fa:   DW_TAG_base_type
  DW_AT_name      ("float")                             |   DW_AT_name      ("float")
                                                        |
0x00000108:   NULL                                      | 0x00000101:   NULL
                                                        |
0x00000109: Compile Unit: length = 0x000000a3           | 0x00000102: Compile Unit: length = 0x0000005d
                                                        |
0x00000114: DW_TAG_compile_unit                         | 0x0000010d: DW_TAG_compile_unit
  DW_AT_name        ("main.cpp")                        |   DW_AT_name        ("main.cpp")
                                                        |
0x00000133:   DW_TAG_subprogram                         | 0x0000012c:   DW_TAG_subprogram
  DW_AT_name      ("main")                              |   DW_AT_name      ("main")
  DW_AT_type      (0x00000169 "int")                    |   DW_AT_type      (0x0000000000000056 "int")
                                                        |
0x0000014c:     DW_TAG_variable                         | 0x00000145:     DW_TAG_variable
  DW_AT_name    ("s")                                   |   DW_AT_name    ("s")
  DW_AT_type    (0x00000170 "SS")                       |   DW_AT_type    (0x00000000000000c2 "SS")
                                                        |
0x0000015a:     DW_TAG_variable                         | 0x00000153:     DW_TAG_variable
  DW_AT_name    ("is")                                  |   DW_AT_name    ("is")
  DW_AT_type    (0x00000191 "inner_SS")                 |   DW_AT_type    (0x00000000000000e3 "inner_SS")
                                                        |
0x00000168:     NULL                                    | 0x00000161:     NULL
                                                        |
0x00000169:   DW_TAG_base_type                          | 0x00000162:   NULL
                DW_AT_name      ("int")                 |
                                                        |
0x00000170:   DW_TAG_structure_type                     |
                DW_AT_name      ("SS")                  |
                                                        |
0x00000179:     DW_TAG_member                           |
                  DW_AT_name    ("a1")                  |
                  DW_AT_type    (0x00000169 "int")      |
                                                        |
0x00000185:     DW_TAG_member                           |
                  DW_AT_name    ("a2")                  |
                  DW_AT_type    (0x000001a8 "float")    |
                                                        |
0x00000191:     DW_TAG_structure_type                   |
                  DW_AT_name    ("inner_SS")            |
                                                        |
0x0000019a:       DW_TAG_member                         |
                    DW_AT_name  ("a1")                  |
                    DW_AT_type  (0x00000169 "int")      |
                                                        |
0x000001a6:       NULL                                  |
                                                        |
0x000001a7:     NULL                                    |
                                                        |
0x000001a8:   DW_TAG_base_type                          |
                DW_AT_name      ("float")               |
                                                        |
0x000001af:   NULL                                      |

Files description :

lld/ELF/MarkDebuginfo.h (20 lines)
lld/ELF/MarkDebuginfo.cpp (98 lines)

main routine: markUsedDebuginfo().

lld/ELF/MarkDebugSectionInfo.h (197 lines)
lld/ELF/MarkDebugSectionInfo.cpp (639 lines)

  Parses .debug_info

lld/ELF/MarkDebugSectionLines.h (142 lines)

  Parses .debug_line

lld/ELF/MarkDebugSectionRanges.h (212 lines)

Parses .debug_ranges and /debug_rnglists

lld/ELF/MarkDebuginfoTypeHash.h (95 lines)
lld/ELF/MarkDebuginfoTypeHash.cpp (404 lines)

Implements type hash, for types comparison.

lld/ELF/InputSection.h

Implements DebugInputSection.

[avl]

Please note, this patch is not for integrating. This is for illustrative purpose for the thread on llvm-dev. http://lists.llvm.org/pipermail/llvm-dev/2019-September/135068.html

[avl]

That patch was a prototype. Currently there is another implementation which uses code extracted from dsymutil - https://reviews.llvm.org/D74169. I abandone this patch in favor to https://reviews.llvm.org/D74169.

lld/ELF/CMakeLists.txt

add_lld_library(lldELF
   EhFrame.cpp
   ICF.cpp
   InputFiles.cpp
   InputSection.cpp
   LTO.cpp
   LinkerScript.cpp
   MapFile.cpp
   MarkLive.cpp
+  MarkDebuginfo.cpp
+  MarkDebuginfoTypeHash.cpp
+  MarkDebugSectionInfo.cpp
   OutputSections.cpp
   Relocations.cpp
   ScriptLexer.cpp
   ScriptParser.cpp
   SymbolTable.cpp
   Symbols.cpp
   SyntheticSections.cpp
   Target.cpp

lld/ELF/Config.h

struct Configuration {
   bool enableNewDtags;
   bool executeOnly;
   bool exportDynamic;
   bool fixCortexA53Errata843419;
   bool forceBTI;
   bool formatBinary = false;
   bool requireCET;
   bool gcSections;
+  bool gcDebuginfo;
+  bool gcDebuginfoDoTypes;
   bool gdbIndex;
   bool gnuHash = false;
   bool gnuUnique;
   bool hasDynamicList = false;
   bool hasDynSymTab;
   bool ignoreDataAddressEquality;
   bool ignoreFunctionAddressEquality;
   bool ltoCSProfileGenerate;

lld/ELF/Driver.cpp

 //===----------------------------------------------------------------------===//
 
 #include "Driver.h"
 #include "Config.h"
 #include "ICF.h"
 #include "InputFiles.h"
 #include "InputSection.h"
 #include "LinkerScript.h"
+#include "MarkDebuginfo.h"
 #include "MarkLive.h"
 #include "OutputSections.h"
 #include "ScriptParser.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "Writer.h"
static void checkOptions() {
   if (config->zText && config->zIfuncNoplt)
     error("-z text and -z ifunc-noplt may not be used together");
 
   if (config->relocatable) {
     if (config->shared)
       error("-r and -shared may not be used together");
     if (config->gcSections)
       error("-r and --gc-sections may not be used together");
+    if (config->gcDebuginfo)
+      error("-r and --gc-debuginfo may not be used together");
+    if (config->gcDebuginfoDoTypes)
+      error("-r and --gc-debuginfo-types may not be used together");
     if (config->gdbIndex)
       error("-r and --gdb-index may not be used together");
     if (config->icf != ICFLevel::None)
       error("-r and --icf may not be used together");
     if (config->pie)
       error("-r and -pie may not be used together");
   }
 
static void readConfigs(opt::InputArgList &args) {
   config->exportDynamic =
       args.hasFlag(OPT_export_dynamic, OPT_no_export_dynamic, false);
   config->filterList = args::getStrings(args, OPT_filter);
   config->fini = args.getLastArgValue(OPT_fini, "_fini");
   config->fixCortexA53Errata843419 = args.hasArg(OPT_fix_cortex_a53_843419);
   config->forceBTI = args.hasArg(OPT_force_bti);
   config->requireCET = args.hasArg(OPT_require_cet);
   config->gcSections = args.hasFlag(OPT_gc_sections, OPT_no_gc_sections, false);
+  config->gcDebuginfo =
+      args.hasFlag(OPT_gc_debuginfo, OPT_no_gc_debuginfo, false);
+  config->gcDebuginfoDoTypes =
+      args.hasFlag(OPT_gc_debuginfo_types, OPT_no_gc_debuginfo_types, false);
   config->gnuUnique = args.hasFlag(OPT_gnu_unique, OPT_no_gnu_unique, true);
   config->gdbIndex = args.hasFlag(OPT_gdb_index, OPT_no_gdb_index, false);
   config->icf = getICF(args);
   config->ignoreDataAddressEquality =
       args.hasArg(OPT_ignore_data_address_equality);
   config->ignoreFunctionAddressEquality =
       args.hasArg(OPT_ignore_function_address_equality);
   config->init = args.getLastArgValue(OPT_init, "_init");
template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
 
   // Replace common symbols with regular symbols.
   replaceCommonSymbols();
 
   // Do size optimizations: garbage collection, merging of SHF_MERGE sections
   // and identical code folding.
   splitSections<ELFT>();
   markLive<ELFT>();
+  // If -gc-debuginfo specified remove unused debug data
+  markUsedDebuginfo<ELFT>();
   demoteSharedSymbols();
   mergeSections();
 
   // Make copies of any input sections that need to be copied into each
   // partition.
   copySectionsIntoPartitions();
 
   // Create synthesized sections such as .got and .plt. This is called before

lld/ELF/InputFiles.cpp

InputSectionBase *ObjFile<ELFT>::createInputSection(const Elf_Shdr &sec) {
   // The linker merges EH (exception handling) frames and creates a
   // .eh_frame_hdr section for runtime. So we handle them with a special
   // class. For relocatable outputs, they are just passed through.
   if (name == ".eh_frame" && !config->relocatable)
     return make<EhInputSection>(*this, sec, name);
 
   if (shouldMerge(sec))
     return make<MergeInputSection>(*this, sec, name);
+
+  if (name.startswith(".debug") || name.startswith(".zdebug"))
+    return make<DebugInputSection>(*this, sec, name);
+
   return make<InputSection>(*this, sec, name);
 }
 
 template <class ELFT>
 StringRef ObjFile<ELFT>::getSectionName(const Elf_Shdr &sec) {
   return CHECK(getObj().getSectionName(&sec, sectionStringTable), this);
 }
 

lld/ELF/InputSection.h

 //===- InputSection.h -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_INPUT_SECTION_H
 #define LLD_ELF_INPUT_SECTION_H
 
 #include "Config.h"
+#include "DWARF.h"
 #include "Relocations.h"
 #include "Thunks.h"
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/TinyPtrVector.h"
+#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
 #include "llvm/Object/ELF.h"
 
 namespace lld {
 namespace elf {
 
 class Symbol;
 struct SectionPiece;
 

 
 private:
   template <class ELFT, class RelTy>
   void copyRelocations(uint8_t *buf, llvm::ArrayRef<RelTy> rels);
 
   template <class ELFT> void copyShtGroup(uint8_t *buf);
 };
 
+// this structure describes fragment which should be copied from
+// source section into output section. It differs from SectionPiece
+// in that sence that represent non-continious data(size could not be
+// calculated from next fragment).
+struct DebugSectionPiece {
+  // offset in original(not fragmented) section
+  uint64_t inputOff;
+
+  // size of piece
+  uint64_t size;
+
+  // value which used to calculate offset in the fragmented section.
+  // FragmentedOffset = inputOff - destOffsetFixupValue
+  uint64_t destOffsetFixupValue;
+
+  static bool orderByAddress(const DebugSectionPiece &lhs,
+                             const DebugSectionPiece &rhs) {
+    return lhs.inputOff < rhs.inputOff;
+  }
+  bool containsOffset(uint64_t off) const {
+    return inputOff <= off && off < (inputOff + size);
+  }
+};
+
+class DebugInputSection;
+
+// this structure describes patch for section contents.
+struct DebugSectionPatchElement {
+
+  // offset to patched element. This offset in original
+  // not fragmented section.
+  uint64_t offset;
+
+  // Form of data
+  llvm::dwarf::Form form;
+
+  // value which should be written into patched section.
+  uint64_t value;
+
+  // for DW_FORM_ref4 value we need to add output section offset
+  DebugInputSection *referencedSection;
+};
+
+/// base class for all .debug* sections which could be fragmented,
+/// by garbage collection.
+class DebugInputSection : public InputSection {
+public:
+  template <class ELFT>
+  DebugInputSection(ObjFile<ELFT> &f, const typename ELFT::Shdr &header,
+                    StringRef name);
+  static bool classof(const SectionBase *s) {
+    return s->name.startswith(".debug") || s->name.startswith(".zdebug");
+  }
+
+  template <class ELFT> void writeTo(uint8_t *buf);
+
+  size_t getSize() const;
+
+  llvm::Optional<uint64_t> getOffset(uint64_t offset) const;
+
+  // This function converts offset from original section
+  // into offset in the fragmented section. If conversion
+  // is not possible then returns llvm::None.
+  llvm::Optional<uint64_t>
+  original2FragmentedSectionOffset(uint64_t offset) const;
+
+  /// This routine adds section piece into live pieces list.
+  void markSectionPieceAsLive(uint64_t startOffset, uint64_t endOffset,
+                              uint64_t &destOffset);
+
+  // This routuine should be called after all live pieces marked
+  void finalizeSectionMarking();
+
+  void addPatch(const DebugSectionPatchElement &patch) {
+    patches.push_back(patch);
+  }
+
+protected:
+  // this function applies patch to the destination data.
+  bool applySectionPatchElement(const DebugSectionPatchElement &patchElement,
+                                uint8_t *dest_data);
+
+  // list of live pieces, which should be copied
+  // into output section.
+  std::vector<DebugSectionPiece> pieces;
+
+  size_t finalSectionSize = 0;
+
+  // list of modifications which should be done for
+  // output section contents.
+  std::vector<DebugSectionPatchElement> patches;
+};
+
 // The list of all input sections.
 extern std::vector<InputSectionBase *> inputSections;
 
 } // namespace elf
 
 std::string toString(const elf::InputSectionBase *);
 } // namespace lld
 
 #endif

lld/ELF/InputSection.cpp

if (hdr.sh_addralign > UINT32_MAX)
     fatal(toString(&file) + ": section sh_addralign is too large");
 }
 
 size_t InputSectionBase::getSize() const {
   if (auto *s = dyn_cast<SyntheticSection>(this))
     return s->getSize();
   if (uncompressedSize >= 0)
     return uncompressedSize;
+  if (auto *d = dyn_cast<DebugInputSection>(this))
+    return d->getSize();
   return rawData.size();
 }
 
 void InputSectionBase::uncompress() const {
   size_t size = uncompressedSize;
   char *uncompressedBuf;
   {
     static std::mutex mu;
for (const RelTy &rel : rels) {
 
     // GCC 8.0 or earlier have a bug that they emit R_386_GOTPC relocations
     // against _GLOBAL_OFFSET_TABLE_ for .debug_info. The bug has been fixed
     // in 2017 (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82630), but we
     // need to keep this bug-compatible code for a while.
     if (config->emachine == EM_386 && type == R_386_GOTPC)
       continue;
 
-    uint64_t offset = getOffset(rel.r_offset);
+    uint64_t offset = rel.r_offset;
+
+    if (auto *d = dyn_cast<DebugInputSection>(this)) {
+      if (auto off = d->getOffset(offset))
+        offset = *off;
+      else
+        continue;
+    } else
+      offset = getOffset(offset);
+
     uint8_t *bufLoc = buf + offset;
     int64_t addend = getAddend<ELFT>(rel);
     if (!RelTy::IsRela)
       addend += target->getImplicitAddend(bufLoc, type);
 
     Symbol &sym = getFile<ELFT>()->getRelocTargetSym(rel);
     RelExpr expr = target->getRelExpr(type, sym, bufLoc);
     if (expr == R_NONE)
template <class ELFT> void InputSection::writeTo(uint8_t *buf) {
   if (type == SHT_NOBITS)
     return;
 
   if (auto *s = dyn_cast<SyntheticSection>(this)) {
     s->writeTo(buf + outSecOff);
     return;
   }
 
+  if (auto *s = dyn_cast<DebugInputSection>(this)) {
+    s->writeTo<ELFT>(buf);
+    return;
+  }
+
   // If -r or --emit-relocs is given, then an InputSection
   // may be a relocation section.
   if (type == SHT_RELA) {
     copyRelocations<ELFT>(buf + outSecOff, getDataAs<typename ELFT::Rela>());
     return;
   }
   if (type == SHT_REL) {
     copyRelocations<ELFT>(buf + outSecOff, getDataAs<typename ELFT::Rel>());
uint64_t MergeInputSection::getParentOffset(uint64_t offset) const {
   // If Offset is not at beginning of a section piece, it is not in the map.
   // In that case we need to search from the original section piece vector.
   const SectionPiece &piece =
       *(const_cast<MergeInputSection *>(this)->getSectionPiece (offset));
   uint64_t addend = offset - piece.inputOff;
   return piece.outputOff + addend;
 }
 
+template <class ELFT>
+DebugInputSection::DebugInputSection(ObjFile<ELFT> &f,
+                                     const typename ELFT::Shdr &header,
+                                     StringRef name)
+    : InputSection(f, header, name) {}
+
+template <class ELFT> void DebugInputSection::writeTo(uint8_t *buf) {
+
+  uint8_t *bufEnd = nullptr;
+
+  if (pieces.size() > 0) {
+    uint64_t destOffset = 0;
+    for (auto curPiece : pieces) {
+      memcpy(buf + outSecOff + destOffset, data().data() + curPiece.inputOff,
+             curPiece.size);
+      destOffset += curPiece.size;
+    }
+    bufEnd = buf + outSecOff + destOffset;
+    assert(destOffset == finalSectionSize);
+  } else {
+    // Copy section contents from source object file to output file
+    // and then apply relocations.
+    memcpy(buf + outSecOff, data().data(), data().size());
+    bufEnd = buf + outSecOff + data().size();
+  }
+  assert(bufEnd);
+
+  for (auto curPatch : patches)
+    applySectionPatchElement(curPatch, buf + outSecOff);
+
+  relocate<ELFT>(buf, bufEnd);
+}
+
+bool DebugInputSection::applySectionPatchElement(
+    const DebugSectionPatchElement &patchElement, uint8_t *dest_data) {
+
+  // TODO: LittleEndian/BigEndian
+  uint64_t offset = patchElement.offset;
+  if (pieces.size() > 0) {
+    if (auto DestOffsetOrErr =
+            original2FragmentedSectionOffset(patchElement.offset)) {
+      offset = *DestOffsetOrErr;
+    } else {
+      return false;
+    }
+  }
+
+  switch (patchElement.form) {
+
+  case llvm::dwarf::DW_FORM_ref1:
+  case llvm::dwarf::DW_FORM_data1: {
+    uint64_t Data = patchElement.value;
+    memcpy(dest_data + offset, &(Data), 1);
+    return true;
+  }
+
+  case llvm::dwarf::DW_FORM_ref2:
+  case llvm::dwarf::DW_FORM_data2: {
+    uint64_t Data = patchElement.value;
+    memcpy(dest_data + offset, &(Data), 2);
+    return true;
+  }
+
+  case llvm::dwarf::DW_FORM_ref_udata:
+  case llvm::dwarf::DW_FORM_ref4:
+  case llvm::dwarf::DW_FORM_data4: {
+    uint64_t Data = patchElement.value;
+
+    // for !config->gcDebuginfoNoTypes case we change DW_FORM_ref4
+    // into DW_FORM_ref_addr. Thus we need to create proper insection offset.
+    // Add referencedSection->outSecOff value which was not known
+    // when we create a patch to DW_FORM_ref_addr.
+    if (config->gcDebuginfoDoTypes &&
+        patchElement.form == llvm::dwarf::DW_FORM_ref4 &&
+        patchElement.referencedSection)
+      Data += patchElement.referencedSection->outSecOff;
+
+    memcpy(dest_data + offset, &(Data), 4);
+    return true;
+  }
+
+  case llvm::dwarf::DW_FORM_ref8:
+  case llvm::dwarf::DW_FORM_data8: {
+    uint64_t Data = patchElement.value;
+    memcpy(dest_data + offset, &(Data), 8);
+    return true;
+  }
+
+  default: {
+    assert(false);
+  }
+  };
+
+  return false;
+}
+
+size_t DebugInputSection::getSize() const {
+  if (pieces.size() == 0) {
+    if (uncompressedSize >= 0)
+      return uncompressedSize;
+    else
+      return rawData.size();
+  }
+
+  return finalSectionSize;
+}
+
+llvm::Optional<uint64_t> DebugInputSection::getOffset(uint64_t offset) const {
+  if (pieces.size() == 0)
+    return outSecOff + offset;
+  else if (auto fragmentedOffset = original2FragmentedSectionOffset(offset))
+    return outSecOff + *fragmentedOffset;
+
+  return llvm::None;
+}
+
+void DebugInputSection::finalizeSectionMarking() {
+  uint64_t destOffset;
+  if (pieces.size() == 0)
+    markSectionPieceAsLive(0, 0, destOffset);
+
+  llvm::sort(pieces, DebugSectionPiece::orderByAddress);
+}
+
+void DebugInputSection::markSectionPieceAsLive(uint64_t startOffset,
+                                               uint64_t endOffset,
+                                               uint64_t &destOffset) {
+
+  assert(startOffset <= endOffset);
+
+  uint64_t len = endOffset - startOffset;
+
+  if (pieces.size() > 0 &&
+      (pieces.back().inputOff + pieces.back().size) == startOffset) {
+    pieces.back().size += len;
+  } else {
+    pieces.push_back({startOffset, len, startOffset - destOffset});
+  }
+
+  destOffset += len;
+  finalSectionSize += len;
+}
+
+// This function converts offset from original section
+// into offset in the fragmented section. If conversion
+// is not possible then returns llvm::None.
+llvm::Optional<uint64_t>
+DebugInputSection::original2FragmentedSectionOffset(uint64_t offset) const {
+
+  assert(pieces.size() != 0);
+
+  DebugSectionPiece secFragment;
+  secFragment.inputOff = offset;
+
+  std::vector<DebugSectionPiece>::const_iterator it =
+      llvm::upper_bound(pieces, secFragment, DebugSectionPiece::orderByAddress);
+  if (it == pieces.begin())
+    return llvm::None;
+
+  it--;
+
+  if (it->containsOffset(offset)) {
+    assert(offset >= it->destOffsetFixupValue);
+    return offset - it->destOffsetFixupValue;
+  } else
+    return llvm::None;
+}
+
 template InputSection::InputSection(ObjFile<ELF32LE> &, const ELF32LE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF32BE> &, const ELF32BE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF64LE> &, const ELF64LE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF64BE> &, const ELF64BE::Shdr &,
                                     StringRef);
template EhInputSection::EhInputSection(ObjFile<ELF64LE> &,
                                         const ELF64LE::Shdr &, StringRef);
 template EhInputSection::EhInputSection(ObjFile<ELF64BE> &,
                                         const ELF64BE::Shdr &, StringRef);
 
 template void EhInputSection::split<ELF32LE>();
 template void EhInputSection::split<ELF32BE>();
 template void EhInputSection::split<ELF64LE>();
 template void EhInputSection::split<ELF64BE>();
+
+template DebugInputSection::DebugInputSection(ObjFile<ELF32LE> &,
+                                              const ELF32LE::Shdr &, StringRef);
+template DebugInputSection::DebugInputSection(ObjFile<ELF32BE> &,
+                                              const ELF32BE::Shdr &, StringRef);
+template DebugInputSection::DebugInputSection(ObjFile<ELF64LE> &,
+                                              const ELF64LE::Shdr &, StringRef);
+template DebugInputSection::DebugInputSection(ObjFile<ELF64BE> &,
+                                              const ELF64BE::Shdr &, StringRef);
+
+template void DebugInputSection::writeTo<ELF32LE>(uint8_t *);
+template void DebugInputSection::writeTo<ELF32BE>(uint8_t *);
+template void DebugInputSection::writeTo<ELF64LE>(uint8_t *);
+template void DebugInputSection::writeTo<ELF64BE>(uint8_t *);

lld/ELF/MarkDebugSectionInfo.h

+//===- MarkLive.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_MARK_DEBUGINFO_INFO_H
+#define LLD_ELF_MARK_DEBUGINFO_INFO_H
+
+#include "InputSection.h"
+#include "MarkDebuginfoCommon.h"
+#include "MarkDebuginfoTypeHash.h"
+
+namespace lld {
+namespace elf {
+
+/// this CUState structure keeps data related to the current Compilation Unit.
+struct CUState {
+  CUState(llvm::DWARFUnit &u)
+      : cu(u), canRemoveDuplicatedTypes(true), canGCCurrentCU(true) {}
+
+  llvm::DWARFUnit &cu;
+
+  /// this keeps map from original offset(inside current section)
+  /// into global offset(could be in another .debug_info section).
+  /// The destination object could be original object or replacement type.
+  localOffset2GlobalOffsetMap local2GlobalOffsetsMap;
+
+  /// list of Attributes, which is a reference into
+  /// .debug_info section and then should be patched.
+  AbbrRefAttrs abbrRefs;
+
+  /// this flag controls whether duplicated types would
+  /// be removed or not.
+  bool canRemoveDuplicatedTypes;
+
+  /// this flags controls whether current compilation unit would be
+  /// garbage collected or not.
+  bool canGCCurrentCU;
+};
+
+typedef std::vector<uint64_t> LiveDiesOffsets;
+typedef llvm::DenseSet<uint64_t> VisitedDies;
+
+struct SubprogramOffsets {
+  uint64_t startOffset;
+  llvm::DWARFUnit *cunit;
+};
+typedef std::vector<SubprogramOffsets> Subprograms;
+typedef llvm::DenseSet<uint64_t> CUOffsets;
+
+template <class ELFT> class DebugInfoSectionMarker {
+public:
+  DebugInfoSectionMarker(ObjFile<ELFT> *of, const llvm::DWARFSection &sec,
+                         GlobalState &s)
+      : objectFile(of), state(s) {
+    infoSection = dyn_cast_or_null<DebugInputSection>(
+        static_cast<const LLDDWARFSection &>(sec).sec);
+
+    allUnits.addUnitsForSection(*state.dwarf, sec, llvm::DW_SECT_INFO);
+  }
+  virtual ~DebugInfoSectionMarker() {}
+
+  // .debug_info
+  //
+  // 1. Examine compile unit`s address ranges, check whether they
+  //    resolved into live section and put the corresponding subprogram
+  //    into live subprograms list.
+  // 2. Parse abbreviations and note attributes of reference type.
+  //    DIE with references should be patched, since some parts of
+  //    .debug_info sections would be removed.
+  // 3. Go through the list and parse live subprograms, scan through
+  //    all references and mark reached DIEs as live.
+  // 4. Scan all compile unit`s DIEs in continuous order mark live DIEs
+  //    for copying into the output section.
+  // 5. If type deduplication should be done, then calculate type hash,
+  //    for types. Remove types with matched hash.
+  // 6. After the whole marking finished, scan for references and patch them
+  //    according to the new section layout.
+
+  virtual void mark() {
+    if (!infoSection)
+      return;
+
+    for (auto &CU : allUnits) {
+      Expected<llvm::DWARFAddressRangesVector> aRanges =
+          CU->getUnitDIE().getAddressRanges();
+
+      // Examine compile unit`s address ranges, check whether they
+      // resolved into live section and put the corresponding subprogram
+      // into live subprograms list.
+      bool hasLiveAddressRanges = false;
+      if (aRanges) {
+        for (auto range : *aRanges) {
+          InputSectionBase *Sec =
+              infoSection->getFile<ELFT>()->getSections()[range.SectionIndex];
+
+          if (Sec->isLive()) {
+            llvm::DWARFDie subRoutine =
+                CU->getSubroutineForAddress(range.LowPC);
+
+            if (subRoutine.isValid()) {
+              liveSubprograms.push_back({subRoutine.getOffset(), CU.get()});
+              hasLiveAddressRanges = true;
+            }
+          }
+        }
+      }
+
+      if (!hasLiveAddressRanges)
+        emptyCUList.insert(CU->getOffset());
+    }
+
+    for (std::unique_ptr<llvm::DWARFUnit> &cu : allUnits) {
+      CUState currentCUState(*cu);
+
+      currentCUState.canRemoveDuplicatedTypes = config->gcDebuginfoDoTypes;
+      currentCUState.canGCCurrentCU = true;
+
+      // Parse abbreviations and note attributes of reference type.
+      // DIE with references should be patched, since some parts of
+      // .debug_info sections would be removed.
+      markDebugAbbrevSection(currentCUState);
+
+      // Go through the list and parse live subprograms, scan through
+      // all references and mark reached DIEs as live.
+      collectLiveDIEs(currentCUState);
+
+      // Scan all compile unit`s DIEs in continuous order mark live DIEs
+      // for copying into the output section.
+      markDebugInfoSection(currentCUState);
+    }
+  }
+
+protected:
+  void markDebugInfoSection(CUState &currentCUState);
+  void markDebugAbbrevSection(CUState &cuState);
+
+  void markDIEsForCopyAndReplaceDuplicatedTypes(
+      CUState &cuState, llvm::DWARFDie &die, ParentsList &parents,
+      bool alreadyStoredByParent, uint64_t owningParentOffset,
+      uint64_t owningParentHASH, uint64_t &destOffset, bool parse_deleted_type);
+  void patchDIEReferencesOffsets(const llvm::DWARFDie &die, CUState &cuState);
+  bool canDIE_BeDeleted(llvm::DWARFUnit &cu, const llvm::DWARFDie &die);
+
+  void reportReferenceError(const llvm::DWARFDie &die,
+                            uint64_t broken_reference, const char *message);
+
+  void collectLiveDiesForSubprograms(CUState &currentCUState,
+                                     llvm::DWARFDie &die);
+  void collectLiveDIEs(CUState &cuState);
+  void checkAttributesForTypeRefs(CUState &cuState, const llvm::DWARFDie &die);
+  void parseForDiesReferences(CUState &cuState, const llvm::DWARFDie &die);
+
+  void addParent(ParentsList &parents, llvm::DWARFDie &die);
+  void removeParent(ParentsList &parents);
+  void addTypeToGlobalMap(const llvm::DWARFDie &die, uint64_t owningParentHASH,
+                          uint64_t owningParentOffset, uint64_t typeHashValue,
+                          bool parseDeletedType);
+  void mapRefToReplacementType(CUState &cuState, const llvm::DWARFDie &die,
+                               uint64_t owningParentOffset,
+                               bool alreadyStoredByParent);
+
+  void markDIEAsLive(const llvm::DWARFDie &die);
+  bool isLiveDIE(const llvm::DWARFDie &die);
+  bool needToPutIntoTypeMap(CUState &cuState, llvm::DWARFDie &die);
+  uint32_t sizeofCULengthField() { return 4; }
+
+  ObjFile<ELFT> *objectFile = nullptr;
+  GlobalState &state;
+
+  llvm::DWARFUnitVector allUnits;
+
+  // list of live subprograms
+  Subprograms liveSubprograms;
+
+  // list of DIEs which could be reached from live subprograms
+  LiveDiesOffsets liveDies;
+
+  VisitedDies visited;
+
+  // Cache for type hashes
+  HashCache hashCache;
+
+  // list of compile units which does not have live address ranges
+  CUOffsets emptyCUList;
+
+  DebugInputSection *infoSection = nullptr;
+};
+
+} // namespace elf
+} // namespace lld
+
+#endif // LLD_ELF_MARK_DEBUGINFO_INFO_H

lld/ELF/MarkDebugSectionInfo.cpp

+//===- MarkLive.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "MarkDebugSectionInfo.h"
+#include "MarkDebuginfoTypeHash.h"
+
+using namespace llvm;
+using namespace llvm::ELF;
+using namespace llvm::object;
+
+using namespace lld;
+using namespace lld::elf;
+
+/// this routines parses .debug_abbrev table. It changes types format and
+/// analyzes whether deduplicating of data types is possible. It changes
+/// DW_FORM_ref4 references into DW_FORM_ref_addr(so that we were able to
+/// reference data type record from another compilation unit).
+/// If Abbreviations for specified compilation unit have DW_FORM_ref1,
+/// DW_FORM_ref2, DW_FORM_ref8 types then we could not change them into
+/// DW_FORM_ref_addr and then we could not deduplicate this Compilation unit.
+/// Set CanRemoveDuplicatedTypes into "false" then.
+///
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::markDebugAbbrevSection(CUState &cuState) {
+
+  DebugInputSection *abbrevSection = nullptr;
+
+  for (InputSectionBase *sec : objectFile->getSections()) {
+    if (sec && (sec->name.equals(".debug_abbrev") ||
+                sec->name.equals(".zdebug_abbrev"))) {
+      abbrevSection = dyn_cast_or_null<DebugInputSection>(sec);
+      break;
+    }
+  }
+
+  if (!abbrevSection)
+    return;
+
+  if (const DWARFAbbreviationDeclarationSet *declSet =
+          cuState.cu.getAbbreviations()) {
+
+    std::for_each(
+        declSet->begin(), declSet->end(),
+        [abbrevSection, &cuState](const DWARFAbbreviationDeclaration &decl) {
+          SmallDenseSet<uint16_t, 0x40> refAttrs;
+
+          for (auto attr : decl.attributes()) {
+
+            switch (attr.Form) {
+            case llvm::dwarf::DW_FORM_ref1:
+            case llvm::dwarf::DW_FORM_ref2:
+            case llvm::dwarf::DW_FORM_ref8:
+              cuState.canRemoveDuplicatedTypes = false;
+              refAttrs.insert(attr.Attr);
+              break;
+            case llvm::dwarf::DW_FORM_ref4:
+              refAttrs.insert(attr.Attr);
+              if (config->gcDebuginfoDoTypes)
+                abbrevSection->addPatch(
+                    {attr.FormOffset, llvm::dwarf::DW_FORM_data1,
+                     llvm::dwarf::DW_FORM_ref_addr, nullptr});
+              break;
+            case llvm::dwarf::DW_FORM_ref_addr:
+              refAttrs.insert(attr.Attr);
+              break;
+
+            default:
+              // nothing to do
+              break;
+            }
+          }
+
+          if (refAttrs.size() > 0) {
+            cuState.abbrRefs.insert(
+                std::pair<uint32_t, SmallDenseSet<uint16_t, 0x40>>(
+                    decl.getCode(), std::move(refAttrs)));
+          }
+        });
+  }
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::markDebugInfoSection(
+    CUState &currentCUState) {
+
+  uint64_t destOffset = 0;
+
+  if (currentCUState.cu.isTypeUnit() || !currentCUState.canGCCurrentCU) {
+    infoSection->markSectionPieceAsLive(currentCUState.cu.getOffset(),
+                                        currentCUState.cu.getNextUnitOffset(),
+                                        destOffset);
+  } else if (emptyCUList.count(currentCUState.cu.getOffset()) != 0 ||
+             !currentCUState.cu.getUnitDIE().hasChildren()) {
+    // skip entire compile unit
+  } else {
+    infoSection->markSectionPieceAsLive(
+        currentCUState.cu.getOffset(),
+        currentCUState.cu.getUnitDIE().getFirstChild().getOffset(), destOffset);
+
+    ParentsList typeParents;
+    typeParents.reserve(allUnits.size());
+
+    // check subprograms and mark for keeping only those which points to
+    // Live sections.
+    for (auto cuChild : currentCUState.cu.getUnitDIE().children())
+      markDIEsForCopyAndReplaceDuplicatedTypes(
+          currentCUState, cuChild, typeParents, false, 0, 0, destOffset, false);
+
+    infoSection->markSectionPieceAsLive(
+        currentCUState.cu.getUnitDIE().getLastChild().getOffset(),
+        currentCUState.cu.getNextUnitOffset(), destOffset);
+
+    // sizeofCULengthField should be subtracted because length does not include
+    // the length of field itself
+    infoSection->addPatch(
+        {currentCUState.cu.getOffset(), llvm::dwarf::DW_FORM_data4,
+         uint64_t(destOffset - sizeofCULengthField()), nullptr});
+  }
+
+  infoSection->finalizeSectionMarking();
+
+  for (const auto &DIE : currentCUState.cu.dies())
+    patchDIEReferencesOffsets(DWARFDie(&currentCUState.cu, &DIE),
+                              currentCUState);
+
+  return;
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::addParent(ParentsList &parents,
+                                             DWARFDie &die) {
+
+  if (const char *name = die.getName(DINameKind::ShortName))
+    parents.push_back({die.getTag(), StringRef(name)});
+  else
+    parents.push_back({die.getTag(), ""});
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::removeParent(ParentsList &parents) {
+  parents.pop_back();
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::addTypeToGlobalMap(
+    const DWARFDie &die, uint64_t owningParentHASH, uint64_t owningParentOffset,
+    uint64_t typeHashValue, bool parseDeletedType) {
+
+  // Assumption : offsets to the same elements match for this type and it`s copy
+
+  assert(die.isValid());
+
+  if (parseDeletedType) {
+    DataTypesMap::iterator curTypeEntry =
+        state.globalTypeMap.find(owningParentHASH);
+
+    assert(curTypeEntry != state.globalTypeMap.end());
+    assert(die.getOffset() >= owningParentOffset);
+
+    uint64_t delta = die.getOffset() - owningParentOffset;
+
+    OffsetSectionPair typeOffset = curTypeEntry->second;
+    typeOffset.offset += delta;
+
+    state.globalTypeMap.insert({typeHashValue, typeOffset});
+  } else {
+    state.globalTypeMap.insert({typeHashValue, {die.getOffset(), infoSection}});
+  }
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::mapRefToReplacementType(
+    CUState &cuState, const DWARFDie &die, uint64_t owningParentOffset,
+    bool alreadyStoredByParent) {
+
+  // Assumption : offsets to the same elements match for this type and it`s copy
+
+  assert(die.isValid());
+
+  if (!alreadyStoredByParent) {
+    cuState.local2GlobalOffsetsMap.insert(
+        {die.getOffset(), {die.getOffset(), infoSection}});
+  } else {
+    assert(die.getOffset() >= owningParentOffset);
+    uint64_t delta = die.getOffset() - owningParentOffset;
+
+    localOffset2GlobalOffsetMap::iterator local2GlobalMapForParent =
+        cuState.local2GlobalOffsetsMap.find(owningParentOffset);
+    assert(local2GlobalMapForParent != cuState.local2GlobalOffsetsMap.end());
+
+    OffsetSectionPair newDTOffset = local2GlobalMapForParent->second;
+    newDTOffset.offset += delta;
+
+    cuState.local2GlobalOffsetsMap.insert({die.getOffset(), newDTOffset});
+  }
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::markDIEsForCopyAndReplaceDuplicatedTypes(
+    CUState &cuState, DWARFDie &die, ParentsList &parents,
+    bool alreadyStoredByParent, uint64_t owningParentOffset,
+    uint64_t owningParentHASH, uint64_t &destOffset, bool parse_deleted_type) {
+
+  assert(die.getTag() != dwarf::DW_TAG_compile_unit &&
+         die.getTag() != dwarf::DW_TAG_type_unit);
+
+  if (!die.isValid())
+    return;
+
+  assert(owningParentOffset < die.getOffset());
+
+  if (!isLiveDIE(die) && canDIE_BeDeleted(cuState.cu, die))
+    return;
+
+  if (needToPutIntoTypeMap(cuState, die) && isLiveDIE(die)) {
+
+    uint64_t typeHashValue = TypeHash(allUnits, cuState.cu, hashCache)
+                                 .computeTypeSignature(die, parents);
+
+    DataTypesMap::iterator curTypeEntry =
+        state.globalTypeMap.find(typeHashValue);
+
+    if (curTypeEntry == state.globalTypeMap.end()) {
+
+      addTypeToGlobalMap(die, owningParentHASH, owningParentOffset,
+                         typeHashValue, parse_deleted_type);
+
+      mapRefToReplacementType(cuState, die, owningParentOffset,
+                              alreadyStoredByParent);
+
+      if (!alreadyStoredByParent) {
+        if (!parse_deleted_type)
+          infoSection->markSectionPieceAsLive(
+              die.getOffset(), die.getSibling().getOffset(), destOffset);
+        else {
+          dbgs() << "\nError: deleted type which is not added into "
+                    "GlobalTypeMap yet, offset ";
+          dbgs().write_hex(die.getOffset());
+          dbgs() << " ";
+        }
+      }
+
+    } else {
+      parse_deleted_type = true;
+      cuState.local2GlobalOffsetsMap.insert(
+          {die.getOffset(), curTypeEntry->second});
+    }
+
+    if (die.hasChildren()) {
+      addParent(parents, die);
+      for (auto CurChild : die.children())
+        markDIEsForCopyAndReplaceDuplicatedTypes(
+            cuState, CurChild, parents, true, die.getOffset(), typeHashValue,
+            destOffset, parse_deleted_type);
+      removeParent(parents);
+    }
+
+  } else if (alreadyStoredByParent) {
+
+    mapRefToReplacementType(cuState, die, owningParentOffset,
+                            alreadyStoredByParent);
+
+    if (die.hasChildren()) {
+      addParent(parents, die);
+      for (auto CurChild : die.children())
+        markDIEsForCopyAndReplaceDuplicatedTypes(
+            cuState, CurChild, parents, alreadyStoredByParent,
+            owningParentOffset, owningParentHASH, destOffset,
+            parse_deleted_type);
+      removeParent(parents);
+    }
+
+  } else {
+    if (die.hasChildren()) {
+      if (!alreadyStoredByParent)
+        infoSection->markSectionPieceAsLive(
+            die.getOffset(), die.getFirstChild().getOffset(), destOffset);
+
+      addParent(parents, die);
+      for (auto CurChild : die.children())
+        markDIEsForCopyAndReplaceDuplicatedTypes(
+            cuState, CurChild, parents, alreadyStoredByParent,
+            owningParentOffset, owningParentHASH, destOffset,
+            parse_deleted_type);
+      removeParent(parents);
+
+      if (!alreadyStoredByParent)
+        infoSection->markSectionPieceAsLive(die.getLastChild().getOffset(),
+                                            die.getSibling().getOffset(),
+                                            destOffset);
+    } else {
+      if (!alreadyStoredByParent)
+        infoSection->markSectionPieceAsLive(
+            die.getOffset(), die.getSibling().getOffset(), destOffset);
+    }
+  }
+
+  return;
+}
+
+/// this routine changes data type references. Instead of local in-compilation
+/// unit offset it set global in-.debug_info section offset.
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::patchDIEReferencesOffsets(
+    const DWARFDie &die, CUState &cuState) {
+
+  if (!die.isValid() || !die.getAbbreviationDeclarationPtr() ||
+      !infoSection->original2FragmentedSectionOffset(die.getOffset()))
+    return;
+
+  // get list of attributes which should be patched(all references inside
+  // .debug_info section should be patched) that list of attributes was prepared
+  // while marking .debug_abbrev section
+  AbbrRefAttrs::iterator die_Attrs =
+      cuState.abbrRefs.find(die.getAbbreviationDeclarationPtr()->getCode());
+
+  if (die_Attrs == cuState.abbrRefs.end())
+    return;
+
+  for (auto attr : die_Attrs->second) {
+
+    Optional<std::pair<DWARFFormValue, uint64_t>> valueOrErr =
+        die.findWithOffset(static_cast<dwarf::Attribute>(attr));
+
+    if (valueOrErr) {
+
+      // check that ValueOrErr is a reference
+      if (Optional<DWARFFormValue::UnitOffset> ref =
+              valueOrErr->first.getAsRelativeReference()) {
+
+        uint64_t refInSectionOffset =
+            ref->Unit ? ref->Unit->getOffset() + ref->Offset : ref->Offset;
+
+        // check that reference points into valid piece of Info section.
+        // if it points into valid piece of section then it points into
+        // non-deleted DIE. In that case we need to add
+        // DestDebugInfoSectionOffset and that`s all.
+        if (auto newTypeOffsetOrErr =
+                infoSection->original2FragmentedSectionOffset(
+                    refInSectionOffset)) {
+
+          // this reference could point to any type of DIE
+          // (i.e. it could be data type DIE and other DIE.)
+
+          if (config->gcDebuginfoDoTypes &&
+              valueOrErr->first.getForm() == llvm::dwarf::DW_FORM_ref4) {
+
+            infoSection->addPatch({valueOrErr->second,
+                                   valueOrErr->first.getForm(),
+                                   *newTypeOffsetOrErr, infoSection});
+
+          } else {
+            uint64_t offsetInCompileUnit =
+                *newTypeOffsetOrErr - (ref->Unit ? ref->Unit->getOffset() : 0);
+
+            infoSection->addPatch({valueOrErr->second,
+                                   valueOrErr->first.getForm(),
+                                   offsetInCompileUnit, nullptr});
+          }
+
+        } else {
+          // if it points into deleted piece of Info section then we need to
+          // check whether there is a conversion from original offset into new
+          // offset of replaced type
+
+          // this reference should point into type DIE only
+
+          // convert from InSection offset int InCompileUnit offset
+          uint64_t refInUnitOffset = refInSectionOffset;
+
+          if (!ref->Unit) {
+            if (cuState.cu.getOffset() <= ref->Offset &&
+                ref->Offset < cuState.cu.getNextUnitOffset()) {
+              refInUnitOffset -= cuState.cu.getOffset();
+            } else {
+              reportReferenceError(
+                  die, valueOrErr->first.getRawUValue(),
+                  "absolute references(ref_addr, ref_sig) are not "
+                  "supported yet");
+            }
+          } else {
+            refInUnitOffset -= ref->Unit->getOffset();
+          }
+
+          localOffset2GlobalOffsetMap::iterator offsetMap =
+              cuState.local2GlobalOffsetsMap.find(refInUnitOffset);
+
+          // check whether we need to replace current offset
+          // into other debug_info section offset. i.e. whether we need to
+          // replace referenced type with it`s global copy.
+          if (offsetMap == cuState.local2GlobalOffsetsMap.end()) {
+            reportReferenceError(die, valueOrErr->first.getRawUValue(),
+                                 "reference does not have replacement type");
+          } else {
+            assert(offsetMap->second.section != nullptr);
+            if (auto newTypeOffsetOrErr =
+                    offsetMap->second.section->original2FragmentedSectionOffset(
+                        offsetMap->second.offset)) {
+
+              // patch src offset with offsetToGlobalType value
+              infoSection->addPatch(
+                  {valueOrErr->second, llvm::dwarf::DW_FORM_ref4,
+                   *newTypeOffsetOrErr, offsetMap->second.section});
+            } else {
+              reportReferenceError(die, offsetMap->second.offset,
+                                   "reference has replacement type which "
+                                   "points into deleted piece of section");
+            }
+          }
+        }
+      } else {
+        reportReferenceError(die, valueOrErr->first.getRawUValue(),
+                             " is not a reference.");
+      }
+
+    } else {
+      // we should have the specified attribute
+      assert(false);
+    }
+  }
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::reportReferenceError(
+    const DWARFDie &die, uint64_t broken_reference, const char *message) {
+  dbgs() << "\n============================================== ";
+  dbgs() << "\nError: " << message << ".\n";
+  dbgs() << "\nbad reference \"";
+  dbgs().write_hex(broken_reference);
+  dbgs() << "\"\n";
+
+  if (die.isValid()) {
+    dbgs() << "\nDIE("
+           << ((canDIE_BeDeleted(*die.getDwarfUnit(), die)) ? "deleted"
+                                                            : "live")
+           << ")";
+    die.dump(dbgs());
+    dbgs() << "\nParents: ";
+    for (DWARFDie curDIE = die.getParent();
+         curDIE.isValid() && curDIE.getParent().isValid();
+         curDIE = curDIE.getParent()) {
+      dbgs() << "\n("
+             << ((canDIE_BeDeleted(*curDIE.getDwarfUnit(), curDIE)) ? "deleted"
+                                                                    : "live")
+             << ")";
+      curDIE.dump(dbgs());
+    }
+    DWARFDie refDIE = die.getDwarfUnit()->getDIEForOffset(broken_reference);
+    if (refDIE.isValid()) {
+      if (refDIE.isNULL()) {
+        dbgs() << "Referrenced DIE is NULL.";
+      } else {
+        dbgs() << "\nReferrenced DIE("
+               << ((canDIE_BeDeleted(*refDIE.getDwarfUnit(), refDIE))
+                       ? "deleted"
+                       : "live")
+               << ")";
+        refDIE.dump(dbgs());
+
+        dbgs() << "\nParents of referrenced DIE: \n";
+        for (DWARFDie curDIE = refDIE.getParent();
+             curDIE.isValid() && curDIE.getParent().isValid();
+             curDIE = curDIE.getParent()) {
+          dbgs() << "\n  ("
+                 << ((canDIE_BeDeleted(*curDIE.getDwarfUnit(), curDIE))
+                         ? "deleted"
+                         : "live")
+                 << ")";
+          curDIE.dump(dbgs());
+        }
+      }
+    } else {
+      dbgs() << "Referrenced DIE is invalid.";
+    }
+
+  } else {
+    dbgs() << "\nInvalid DIE";
+  }
+
+  dbgs() << "\n============================================== ";
+}
+
+template <class ELFT>
+bool DebugInfoSectionMarker<ELFT>::canDIE_BeDeleted(DWARFUnit &cu,
+                                                    const DWARFDie &die) {
+
+  uint64_t inSectionOffsetStartOfDIE = die.getOffset();
+  uint64_t inSectionOffsetNextDIE =
+      cu.getOffset() + die.getSibling().getOffset();
+
+  LiveDiesOffsets::iterator offsetGreaterOrEqualStartOfDIEPos =
+      std::lower_bound(liveDies.begin(), liveDies.end(),
+                       inSectionOffsetStartOfDIE);
+
+  if (offsetGreaterOrEqualStartOfDIEPos == liveDies.end())
+    return true;
+
+  return *offsetGreaterOrEqualStartOfDIEPos >= inSectionOffsetNextDIE;
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::collectLiveDIEs(CUState &cuState) {
+
+  for (SubprogramOffsets &subprogramOffset : liveSubprograms) {
+
+    assert(subprogramOffset.startOffset > subprogramOffset.cunit->getOffset());
+    DWARFDie subprogram = subprogramOffset.cunit->getDIEForOffset(
+        subprogramOffset.startOffset - subprogramOffset.cunit->getOffset());
+
+    parseForDiesReferences(cuState, subprogram);
+  }
+
+  // Following is a prerequisite for canDIE_BeDeleted
+  liveDies.reserve(visited.size());
+  for (uint64_t VisitedOffset : visited)
+    liveDies.push_back(VisitedOffset);
+
+  llvm::sort(liveDies, [](uint64_t lhs, uint64_t rhs) { return lhs < rhs; });
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::checkAttributesForTypeRefs(
+    CUState &cuState, const DWARFDie &die) {
+
+  if (!die.getAbbreviationDeclarationPtr())
+    return;
+
+  // get list of attributes which should be patched(all references inside
+  // .debug_info section should be patched)
+  AbbrRefAttrs::iterator die_Attrs =
+      cuState.abbrRefs.find(die.getAbbreviationDeclarationPtr()->getCode());
+
+  if (die_Attrs == cuState.abbrRefs.end()) {
+    return;
+  }
+
+  die.getAbbreviationDeclarationPtr()->enumerateAttributesWithValues(
+      die.getOffset(), *(die.getDwarfUnit()), die_Attrs->second,
+      [&](const dwarf::Attribute attr, const DWARFFormValue &value) {
+        if (Optional<DWARFFormValue::UnitOffset> reference =
+                value.getAsRelativeReference()) {
+
+          // detect unit which contains referenced DIE
+          DWARFUnit *containingUnit =
+              reference->Unit ? reference->Unit
+                              : allUnits.getUnitForOffset(reference->Offset);
+
+          if (containingUnit) {
+            uint64_t inUnitTypeOffset =
+                reference->Unit
+                    ? reference->Offset
+                    : reference->Offset - containingUnit->getOffset();
+            assert(reference->Offset >= inUnitTypeOffset);
+
+            DWARFDie referencedDIE =
+                containingUnit->getDIEForOffset(inUnitTypeOffset);
+
+            parseForDiesReferences(cuState, referencedDIE);
+
+            // keep containing structure
+            DWARFDie curDIE = referencedDIE;
+            DWARFDie nextDIE = referencedDIE.getParent();
+            while (nextDIE.isValid() &&
+                   nextDIE.getTag() != dwarf::DW_TAG_compile_unit &&
+                   nextDIE.getTag() != dwarf::DW_TAG_type_unit &&
+                   nextDIE.getTag() != dwarf::DW_TAG_namespace &&
+                   !isLiveDIE(nextDIE)) {
+              curDIE = nextDIE;
+              nextDIE = nextDIE.getParent();
+            }
+
+            parseForDiesReferences(cuState, curDIE);
+          } else {
+            dbgs() << "\nError: Invalid compilation unit for offset: ";
+            dbgs().write_hex(reference->Offset);
+            dbgs() << "\n";
+          }
+        }
+      });
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::parseForDiesReferences(CUState &cuState,
+                                                          const DWARFDie &die) {
+
+  if (!die.isValid())
+    return;
+
+  if (isLiveDIE(die))
+    return;
+  else
+    markDIEAsLive(die);
+
+  checkAttributesForTypeRefs(cuState, die);
+
+  for (auto child : die.children())
+    parseForDiesReferences(cuState, child);
+}
+
+template <class ELFT>
+void DebugInfoSectionMarker<ELFT>::markDIEAsLive(const DWARFDie &die) {
+  visited.insert(die.getOffset());
+}
+
+template <class ELFT>
+bool DebugInfoSectionMarker<ELFT>::isLiveDIE(const DWARFDie &die) {
+  return visited.count(die.getOffset()) > 0;
+}
+
+template <class ELFT>
+bool DebugInfoSectionMarker<ELFT>::needToPutIntoTypeMap(CUState &cuState,
+                                                        DWARFDie &die) {
+
+  if (dwarf::isType(die.getTag())) {
+
+    if (!cuState.canRemoveDuplicatedTypes)
+      return false;
+
+    if (Optional<DWARFFormValue> atDeclaration =
+            die.find(llvm::dwarf::DW_AT_declaration)) {
+      if (atDeclaration->getRawUValue())
+        return false;
+    }
+
+    return true;
+  }
+
+  return false;
+}
+
+template class elf::DebugInfoSectionMarker<ELF32LE>;
+template class elf::DebugInfoSectionMarker<ELF32BE>;
+template class elf::DebugInfoSectionMarker<ELF64LE>;
+template class elf::DebugInfoSectionMarker<ELF64BE>;

lld/ELF/MarkDebugSectionLines.h

+//===- MarkLive.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_MARK_DEBUGINFO_LINES_H
+#define LLD_ELF_MARK_DEBUGINFO_LINES_H
+
+#include "InputSection.h"
+#include "MarkDebuginfoCommon.h"
+
+namespace lld {
+namespace elf {
+
+// .debug_line
+//
+// 1. Enumerate sequences for compilation unit.
+//    For each sequence check whether it points
+//    into live section. Mark live ranges for copying.
+
+template <class ELFT> class DebugLineSectionMarker {
+public:
+  DebugLineSectionMarker(GlobalState &S) : state(S) {
+    debugLineSection = dyn_cast_or_null<InputSection>(
+        static_cast<const LLDDWARFSection &>(
+            state.dwarf->getDWARFObj().getLineSection())
+            .sec);
+  }
+  virtual ~DebugLineSectionMarker() {}
+
+  virtual void mark(llvm::DWARFUnit &cu) {
+
+    if (cu.isTypeUnit())
+      return;
+
+    DebugInputSection *debugLineSection = nullptr;
+
+    debugLineSection = dyn_cast_or_null<DebugInputSection>(
+        static_cast<const LLDDWARFSection &>(
+            state.dwarf->getDWARFObj().getLineSection())
+            .sec);
+
+    if (!debugLineSection)
+      return;
+
+    auto report = [](Error Err) {
+      handleAllErrors(std::move(Err),
+                      [](llvm::ErrorInfoBase &Info) { warn(Info.message()); });
+    };
+
+    Expected<const llvm::DWARFDebugLine::LineTable *> expectedLT =
+        state.dwarf->getLineTableForUnit(&cu, report);
+
+    const llvm::DWARFDebugLine::LineTable *lineTable = nullptr;
+    if (expectedLT)
+      lineTable = *expectedLT;
+    else
+      report(expectedLT.takeError());
+
+    if (!lineTable)
+      return;
+
+    uint64_t prevOffset = 0;
+    uint64_t curOffset = 0;
+    uint64_t destOffset = 0;
+
+    bool hasLiveSequencies = false;
+    for (auto curSecuence : lineTable->SequenceBoundaries) {
+      if (curSecuence.SectionIndex !=
+          llvm::object::SectionedAddress::UndefSection) {
+        InputSectionBase *sec = debugLineSection->getFile<ELFT>()
+                                    ->getSections()[curSecuence.SectionIndex];
+
+        if (sec->isLive()) {
+          hasLiveSequencies = true;
+          break;
+        }
+      }
+    }
+
+    if (hasLiveSequencies) {
+      // store header
+      curOffset += lineTable->Prologue.getLength();
+      debugLineSection->markSectionPieceAsLive(prevOffset, curOffset,
+                                               destOffset);
+
+      for (auto curSecuence : lineTable->SequenceBoundaries) {
+        if (curOffset < curSecuence.StartOffset) {
+          debugLineSection->markSectionPieceAsLive(
+              curOffset, curSecuence.StartOffset, destOffset);
+          curOffset = curSecuence.StartOffset;
+        }
+
+        if (curSecuence.SectionIndex !=
+            llvm::object::SectionedAddress::UndefSection) {
+          InputSectionBase *sec = debugLineSection->getFile<ELFT>()
+                                      ->getSections()[curSecuence.SectionIndex];
+
+          if (sec->isLive()) {
+            debugLineSection->markSectionPieceAsLive(
+                curSecuence.StartOffset, curSecuence.EndOffset, destOffset);
+          }
+
+          curOffset = curSecuence.EndOffset;
+        }
+      }
+
+      if (curOffset < (lineTable->Prologue.TotalLength +
+                       lineTable->Prologue.sizeofTotalLength())) {
+        debugLineSection->markSectionPieceAsLive(
+            curOffset,
+            lineTable->Prologue.TotalLength +
+                lineTable->Prologue.sizeofTotalLength(),
+            destOffset);
+      }
+
+      // update header with new size of DebugLineTable
+      // Prologue.sizeofTotalLength() should be subtracted because length does
+      // not include the length of field itself
+      debugLineSection->addPatch(
+          {cu.getOffset(), llvm::dwarf::DW_FORM_data4,
+           uint64_t(destOffset - lineTable->Prologue.sizeofTotalLength()),
+           nullptr});
+    }
+
+    debugLineSection->finalizeSectionMarking();
+
+    return;
+  }
+
+protected:
+  GlobalState &state;
+  InputSection *debugLineSection = nullptr;
+};
+
+} // namespace elf
+} // namespace lld
+
+#endif // LLD_ELF_MARK_DEBUGINFO_LINES_H

lld/ELF/MarkDebugSectionRanges.h

+//===- MarkLive.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_MARK_DEBUGINFO_RANGES_H
+#define LLD_ELF_MARK_DEBUGINFO_RANGES_H
+
+#include "InputSection.h"
+#include "MarkDebuginfoCommon.h"
+
+namespace lld {
+namespace elf {
+
+// .debug_ranges
+//
+// 1. Enumerate address ranges for Compilation unit.
+//    For each address range check whether it points
+//    into Live section. Mark live ranges for copying.
+
+template <class ELFT> class DebugRangesSectionMarker {
+public:
+  DebugRangesSectionMarker(GlobalState &S) : state(S) {
+    debugRangesSection = dyn_cast_or_null<DebugInputSection>(
+        static_cast<const LLDDWARFSection &>(
+            state.dwarf->getDWARFObj().getRangesSection())
+            .sec);
+  }
+  virtual ~DebugRangesSectionMarker<ELFT>() {}
+
+  // Parse .debug_ranges section, mark used ranges, so that they would be copied
+  // in the output section later.
+  virtual void mark(llvm::DWARFUnit &cu) {
+
+    if (!debugRangesSection)
+      return;
+
+    uint64_t destOffset = 0;
+
+    if (llvm::Optional<std::pair<llvm::DWARFFormValue, uint64_t>> ranges =
+            cu.getUnitDIE().findWithOffset(llvm::dwarf::DW_AT_ranges)) {
+
+      uint8_t addressSize = cu.getAddressByteSize();
+      if (addressSize != 4 && addressSize != 8)
+        return;
+
+      llvm::DWARFDataExtractor rangesData(
+          state.dwarf->getDWARFObj(),
+          state.dwarf->getDWARFObj().getRangesSection(),
+          state.dwarf->getDWARFObj().isLittleEndian(), addressSize);
+
+      uint64_t offset = ranges->first.getRawUValue();
+      uint64_t *offset_ptr = &offset;
+
+      while (*offset_ptr < debugRangesSection->data().size()) {
+        uint64_t sectionIndex = llvm::object::SectionedAddress::UndefSection;
+        uint64_t prevOffset = *offset_ptr;
+
+        uint64_t startAddress = rangesData.getRelocatedAddress(offset_ptr);
+        uint64_t endAddress =
+            rangesData.getRelocatedAddress(offset_ptr, &sectionIndex);
+
+        if (sectionIndex != llvm::object::SectionedAddress::UndefSection) {
+
+          InputSectionBase *sec =
+              debugRangesSection->getFile<ELFT>()->getSections()[sectionIndex];
+
+          if (sec->isLive())
+            debugRangesSection->markSectionPieceAsLive(prevOffset, *offset_ptr,
+                                                       destOffset);
+        }
+
+        // Check that both values were extracted correctly.
+        if (*offset_ptr != prevOffset + 2 * addressSize) {
+          llvm::dbgs()
+              << "\nError: .debug_ranges values were extracted incorrectly";
+          return;
+        }
+        if ((startAddress == 0) && (endAddress == 0)) {
+          debugRangesSection->markSectionPieceAsLive(prevOffset, *offset_ptr,
+                                                     destOffset);
+          break;
+        }
+      }
+    }
+
+    debugRangesSection->finalizeSectionMarking();
+  }
+
+protected:
+  GlobalState &state;
+  DebugInputSection *debugRangesSection = nullptr;
+};
+
+// .debug_rnglists
+//
+// 1. Enumerate address ranges for Compilation unit.
+//    For each address range check whether it points
+//    into Live section. Mark live ranges for copying.
+
+template <class ELFT> class DebugRnglistsSectionMarker {
+public:
+  DebugRnglistsSectionMarker(GlobalState &S) : state(S) {
+    debugRnglistsSection = dyn_cast_or_null<DebugInputSection>(
+        static_cast<const LLDDWARFSection &>(
+            state.dwarf->getDWARFObj().getRnglistsSection())
+            .sec);
+  }
+  virtual ~DebugRnglistsSectionMarker() {}
+
+  // Parse .debug_rnglist section, mark used ranges, so that they would be
+  // copied in the output section later.
+  virtual void mark(llvm::DWARFUnit &cu) {
+
+    if (cu.isTypeUnit())
+      return;
+
+    if (!debugRnglistsSection)
+      return;
+
+    uint64_t prevOffset = 0;
+    uint64_t curOffset = 0;
+    uint64_t destOffset = 0;
+
+    // parse header and segment selector.
+    prevOffset = curOffset;
+    SimpleRnglistParser rnglistParser(
+        state.dwarf->getDWARFObj(),
+        state.dwarf->getDWARFObj().getRnglistsSection(), &curOffset,
+        debugRnglistsSection->getSize());
+
+    // mark header and segment selector to be saved.
+    debugRnglistsSection->markSectionPieceAsLive(prevOffset, curOffset,
+                                                 destOffset);
+
+    // enumerate ranges and mark address ranges pointing to live section
+    // to be copied into output section.
+    // It is assumed that Address Ranges enumarated in the same order
+    // as they phisically located in .debug_rnglists section.
+    Expected<llvm::DWARFAddressRangesVector> aRanges =
+        cu.getUnitDIE().getAddressRanges();
+    if (aRanges)
+      for (auto Range : *aRanges) {
+        prevOffset = curOffset;
+
+        if (Error E = rnglistParser.shiftToNextEntry())
+          break;
+
+        InputSectionBase *Sec = debugRnglistsSection->getFile<ELFT>()
+                                    ->getSections()[Range.SectionIndex];
+
+        if (Sec->isLive())
+          debugRnglistsSection->markSectionPieceAsLive(prevOffset, curOffset,
+                                                       destOffset);
+      }
+
+    // mark end of list pointer to be copied into output section.
+    debugRnglistsSection->markSectionPieceAsLive(curOffset, curOffset + 0x1,
+                                                 destOffset);
+    curOffset += 0x1; // 0x1 is the size of DW_RLE_end_of_list attribute
+
+    // update header with new size of range list
+    // sizeofRangeListLengthField should be subtracted because length does not
+    // include the length of field itself
+    debugRnglistsSection->addPatch({cu.getOffset(), llvm::dwarf::DW_FORM_data4,
+                                    destOffset - sizeofRangeListLengthField(),
+                                    nullptr});
+
+    debugRnglistsSection->finalizeSectionMarking();
+
+    return;
+  }
+
+protected:
+  class SimpleRnglistParser {
+  public:
+    SimpleRnglistParser(const llvm::DWARFObject &Obj,
+                        const llvm::DWARFSection &Section, uint64_t *OPtr,
+                        size_t E)
+        : rnglistData(Obj, Section, Obj.isLittleEndian(), 0), offsetPtr(OPtr),
+          end(E) {
+
+      llvm::DWARFDebugRnglistTable rnglists;
+
+      if (Error err = rnglists.extractHeaderAndOffsets(rnglistData, offsetPtr))
+        return;
+
+      rnglistData.setAddressSize(rnglists.getAddrSize());
+    }
+
+    Error shiftToNextEntry() {
+      return llvm::RangeListEntry().extract(rnglistData, end, offsetPtr);
+    }
+
+    llvm::DWARFDataExtractor rnglistData;
+    uint64_t *offsetPtr;
+    size_t end;
+  };
+
+  uint32_t sizeofRangeListLengthField() { return 4; }
+
+  GlobalState &state;
+  DebugInputSection *debugRnglistsSection = nullptr;
+};
+
+} // namespace elf
+} // namespace lld
+
+#endif // LLD_ELF_MARK_DEBUGINFO_RANGES_H

lld/ELF/MarkDebuginfo.h

+//===- MarkLive.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_MARK_DEBUGINFO_H
+#define LLD_ELF_MARK_DEBUGINFO_H
+
+namespace lld {
+namespace elf {
+
+template <class ELFT> void markUsedDebuginfo();
+
+} // namespace elf
+} // namespace lld
+
+#endif // LLD_ELF_MARK_DEBUGINFO_H

lld/ELF/MarkDebuginfo.cpp

+//===- MarkDebuginfo.cpp
+//-------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//
+//===----------------------------------------------------------------------===//
+
+#include "MarkDebuginfo.h"
+#include "DWARF.h"
+#include "InputSection.h"
+#include "LinkerScript.h"
+#include "MarkDebugSectionInfo.h"
+#include "MarkDebugSectionLines.h"
+#include "MarkDebugSectionRanges.h"
+#include "MarkDebuginfoCommon.h"
+#include "MarkDebuginfoTypeHash.h"
+#include "OutputSections.h"
+#include "SymbolTable.h"
+#include "Symbols.h"
+#include "Target.h"
+#include "llvm/DebugInfo/DWARF/DWARFDie.h"
+#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
+#include "llvm/Object/ELF.h"
+#include <functional>
+#include <set>
+#include <vector>
+
+using namespace llvm;
+using namespace llvm::ELF;
+using namespace llvm::object;
+
+using namespace lld;
+using namespace lld::elf;
+
+template <class ELFT> class GlobalDebugInfoMarker {
+public:
+  GlobalDebugInfoMarker() {}
+  virtual ~GlobalDebugInfoMarker() {}
+
+  virtual void mark(ObjFile<ELFT> *ObjectFile) {
+
+    state.dwarf = std::make_unique<DWARFContext>(
+        std::make_unique<LLDDwarfObj<ELFT>>(ObjectFile));
+
+    state.dwarf->getDWARFObj().forEachInfoSections(
+        [&](const DWARFSection &sec) {
+          DebugInfoSectionMarker<ELFT> DebugInfoSectionMarker(ObjectFile, sec,
+                                                              state);
+
+          DebugInfoSectionMarker.mark();
+        });
+
+    DebugRangesSectionMarker<ELFT> debugRangesSectionMarker(state);
+
+    DebugRnglistsSectionMarker<ELFT> debugRnglistsSectionMarker(state);
+
+    DebugLineSectionMarker<ELFT> debugLineSectionMarker(state);
+
+    // it is assumed that units enumerated in the same order as they
+    // phisically located in .dwarf_info section
+    for (std::unique_ptr<DWARFUnit> &cu : state.dwarf->normal_units()) {
+      debugRangesSectionMarker.mark(*cu);
+
+      debugRnglistsSectionMarker.mark(*cu);
+
+      debugLineSectionMarker.mark(*cu);
+    }
+
+    delete state.dwarf.release();
+  }
+
+protected:
+  GlobalState state;
+};
+
+template <class ELFT> void elf::markUsedDebuginfo() {
+
+  if (!config->gcDebuginfo)
+    return;
+
+  GlobalDebugInfoMarker<ELFT> gdiMarker;
+
+  // for each object file : mark debug info
+  for (InputFile *File : objectFiles) {
+    if (ObjFile<ELFT> *obj = cast<ObjFile<ELFT>>(File))
+      gdiMarker.mark(obj);
+  }
+}
+
+template void elf::markUsedDebuginfo<ELF32LE>();
+template void elf::markUsedDebuginfo<ELF32BE>();
+template void elf::markUsedDebuginfo<ELF64LE>();
+template void elf::markUsedDebuginfo<ELF64BE>();

lld/ELF/MarkDebuginfoCommon.h

+//===- MarkLive.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_MARK_DEBUGINFO_GLOBAL_H
+#define LLD_ELF_MARK_DEBUGINFO_GLOBAL_H
+
+#include "DWARF.h"
+#include "InputSection.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/DebugInfo/DIContext.h"
+#include "llvm/DebugInfo/DWARF/DWARFDie.h"
+#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
+
+namespace lld {
+namespace elf {
+
+// this structure keeps additional information for referenced DIE:
+// offset : offset to the DIE
+// section : section which owns DIE
+struct OffsetSectionPair {
+  uint64_t offset;
+  DebugInputSection *section;
+};
+
+typedef llvm::DenseMap<uint64_t, OffsetSectionPair> DataTypesMap;
+typedef llvm::DenseMap<uint64_t, OffsetSectionPair> localOffset2GlobalOffsetMap;
+typedef llvm::DenseMap<uint64_t, llvm::SmallDenseSet<uint16_t, 0x40>>
+    AbbrRefAttrs;
+
+struct GlobalState {
+  // map from type hash into data types.
+  DataTypesMap globalTypeMap;
+
+  std::unique_ptr<llvm::DWARFContext> dwarf;
+};
+
+} // namespace elf
+} // namespace lld
+
+#endif // LLD_ELF_MARK_DEBUGINFO_GLOBAL_H

lld/ELF/MarkDebuginfoTypeHash.h

+//===- MarkLive.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_ELF_MARK_DEBUGINFO_TYPEHASH_H
+#define LLD_ELF_MARK_DEBUGINFO_TYPEHASH_H
+
+#include "DWARF.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/DebugInfo/DIContext.h"
+#include "llvm/DebugInfo/DWARF/DWARFDie.h"
+#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
+
+/// Following TypeHash class is an implementation of type signature computation
+/// described in DWARF5 7.32 Type Signature Computation.
+/// This type signature used to compare types.
+
+namespace lld {
+
+struct DieTypeName {
+  llvm::dwarf::Tag dieTag;
+  StringRef dieName;
+};
+typedef SmallVector<DieTypeName, 0x10> ParentsList;
+typedef llvm::DenseMap<uint64_t, uint64_t> HashCache;
+
+class TypeHash {
+
+public:
+  TypeHash(llvm::DWARFUnitVector &au, llvm::DWARFUnit &unit, HashCache &hc)
+      : allUnits(au), cu(unit), refsHashes(hc) {}
+  TypeHash(llvm::DWARFUnitVector &au, llvm::DWARFUnit &cu, HashCache &hc,
+           llvm::DenseMap<const llvm::DWARFDebugInfoEntry *, unsigned> num)
+      : numbering(num), allUnits(au), cu(cu), refsHashes(hc) {}
+
+  /// Computes the type signature.
+  uint64_t computeTypeSignature(const llvm::DWARFDie &die,
+                                const ParentsList &parents);
+
+  // Helper routines to process parts of a DIE.
+private:
+  /// Adds the parent context of \param Parent to the hash.
+  void addParentContext(const ParentsList &parents);
+
+  /// Adds the attributes of \param Die to the hash.
+  void addAttributes(const llvm::DWARFDie &die);
+
+  /// Computes the full DWARF4 7.27 hash of the DIE.
+  void computeHash(const llvm::DWARFDie &die);
+
+  // Routines that add DIEValues to the hash.
+  /// Adds \param Value to the hash.
+  void update(uint8_t value) { hash.update(value); }
+
+  /// Encodes and adds \param Value to the hash as a ULEB128.
+  void addULEB128(uint64_t value);
+
+  /// Encodes and adds \param Value to the hash as a SLEB128.
+  void addSLEB128(int64_t value);
+
+  /// Adds \param Str to the hash and includes a NULL byte.
+  void addString(StringRef Str);
+
+  /// Hashes an individual attribute.
+  void hashAttribute(llvm::dwarf::Attribute attribute,
+                     const llvm::DWARFFormValue &value, llvm::dwarf::Tag tag);
+
+  void hashNestedType(const llvm::DWARFDie &die, StringRef name);
+
+  /// Hashes an attribute that refers to another DIE.
+  void hashDIEEntry(llvm::dwarf::Attribute attribute, llvm::dwarf::Tag tag,
+                    const llvm::DWARFDie &entry);
+  /// Hashes a reference to a previously referenced type DIE.
+  void hashRepeatedTypeReference(llvm::dwarf::Attribute attribute,
+                                 unsigned dieNumber);
+  void hashShallowTypeReference(llvm::dwarf::Attribute attribute,
+                                StringRef name, ParentsList &parents);
+
+  llvm::MD5 hash;
+  llvm::DenseMap<const llvm::DWARFDebugInfoEntry *, unsigned> numbering;
+  llvm::DWARFUnitVector &allUnits;
+  llvm::DWARFUnit &cu;
+  HashCache &refsHashes;
+
+  static llvm::SmallDenseSet<uint16_t, 0x40> dieAttributesToExtract;
+};
+
+} // namespace lld
+
+#endif // LLD_ELF_MARK_DEBUGINFO_TYPEHASH_H

lld/ELF/MarkDebuginfoTypeHash.cpp

+//===- MarkLive.h -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "MarkDebuginfoTypeHash.h"
+
+using namespace llvm;
+using namespace llvm::ELF;
+using namespace llvm::object;
+
+using namespace lld;
+using namespace lld::elf;
+
+SmallDenseSet<uint16_t, 0x40> TypeHash::dieAttributesToExtract = {
+    dwarf::DW_AT_name,
+    dwarf::DW_AT_accessibility,
+    dwarf::DW_AT_address_class,
+    dwarf::DW_AT_allocated,
+    dwarf::DW_AT_artificial,
+    dwarf::DW_AT_associated,
+    dwarf::DW_AT_binary_scale,
+    dwarf::DW_AT_bit_offset,
+    dwarf::DW_AT_bit_size,
+    dwarf::DW_AT_bit_stride,
+    dwarf::DW_AT_byte_size,
+    dwarf::DW_AT_byte_stride,
+    dwarf::DW_AT_const_expr,
+    dwarf::DW_AT_const_value,
+    dwarf::DW_AT_containing_type,
+    dwarf::DW_AT_count,
+    dwarf::DW_AT_data_bit_offset,
+    dwarf::DW_AT_data_location,
+    dwarf::DW_AT_data_member_location,
+    dwarf::DW_AT_decimal_scale,
+    dwarf::DW_AT_decimal_sign,
+    dwarf::DW_AT_default_value,
+    dwarf::DW_AT_digit_count,
+    dwarf::DW_AT_discr,
+    dwarf::DW_AT_discr_list,
+    dwarf::DW_AT_discr_value,
+    dwarf::DW_AT_encoding,
+    dwarf::DW_AT_enum_class,
+    dwarf::DW_AT_endianity,
+    dwarf::DW_AT_explicit,
+    dwarf::DW_AT_is_optional,
+    dwarf::DW_AT_location,
+    dwarf::DW_AT_lower_bound,
+    dwarf::DW_AT_mutable,
+    dwarf::DW_AT_ordering,
+    dwarf::DW_AT_picture_string,
+    dwarf::DW_AT_prototyped,
+    dwarf::DW_AT_small,
+    dwarf::DW_AT_segment,
+    dwarf::DW_AT_string_length,
+    dwarf::DW_AT_threads_scaled,
+    dwarf::DW_AT_upper_bound,
+    dwarf::DW_AT_use_location,
+    dwarf::DW_AT_use_UTF8,
+    dwarf::DW_AT_variable_parameter,
+    dwarf::DW_AT_virtuality,
+    dwarf::DW_AT_visibility,
+    dwarf::DW_AT_vtable_elem_location,
+    dwarf::DW_AT_type};
+
+void TypeHash::hashNestedType(const DWARFDie &die, StringRef name) {
+  // 7.27 Step 7
+  // ... append the letter 'S',
+  addULEB128('S');
+
+  // the tag of C,
+  addULEB128(die.getTag());
+
+  // and the name.
+  addString(name);
+}
+
+uint64_t TypeHash::computeTypeSignature(const DWARFDie &die,
+                                        const ParentsList &parents) {
+
+  if (numbering.size() == 0) {
+    numbering[die.getDebugInfoEntry()] = 1;
+  }
+
+  addParentContext(parents);
+
+  // Hash the DIE.
+  computeHash(die);
+
+  // Now return the result.
+  MD5::MD5Result result;
+  hash.final(result);
+
+  return result.low();
+}
+
+void TypeHash::computeHash(const DWARFDie &die) {
+  // Append the letter 'D', followed by the DWARF tag of the DIE.
+  addULEB128('D');
+  addULEB128(die.getTag());
+
+  // Add each of the attributes of the DIE.
+  addAttributes(die);
+
+  // Then hash each of the children of the DIE.
+  for (auto &c : die.children()) {
+    // 7.27 Step 7
+    // If C is a nested type entry or a member function entry, ...
+    if (/* isType(C.getTag()) || */ c.getTag() == dwarf::DW_TAG_subprogram) {
+      const char *Name = c.getName(DINameKind::ShortName);
+      // ... and has a DW_AT_name attribute
+      if (Name && (*Name)) {
+        hashNestedType(c, Name);
+        continue;
+      }
+    }
+    computeHash(c);
+  }
+
+  // Following the last (or if there are no children), append a zero byte.
+  hash.update('\0');
+}
+
+/// Including \p Parent adds the context of Parent to the hash..
+void TypeHash::addParentContext(const ParentsList &parents) {
+
+  // [7.27.2] For each surrounding type or namespace beginning with the
+  // outermost such construct...
+  // Reverse iterate over our list to go from the outermost construct to the
+  // innermost.
+  for (auto &parent : parents) {
+    // for (Parents::iterator I = ParentsList.begin(), E = ParentsList.end(); I
+    // != E; ++I) {
+
+    // ... Append the letter "C" to the sequence...
+    addULEB128('C');
+
+    // ... Followed by the DWARF tag of the construct...
+    addULEB128(parent.dieTag);
+
+    // ... Then the name, taken from the DW_AT_name attribute.
+    if (parent.dieName.size() > 0) {
+      addString(parent.dieName);
+    }
+  }
+}
+
+void TypeHash::addULEB128(uint64_t value) {
+  do {
+    uint8_t Byte = value & 0x7f;
+    value >>= 7;
+    if (value != 0)
+      Byte |= 0x80; // Mark this byte to show that more bytes will follow.
+    hash.update(Byte);
+  } while (value != 0);
+}
+
+void TypeHash::addSLEB128(int64_t value) {
+  bool More;
+  do {
+    uint8_t Byte = value & 0x7f;
+    value >>= 7;
+    More = !((((value == 0) && ((Byte & 0x40) == 0)) ||
+              ((value == -1) && ((Byte & 0x40) != 0))));
+    if (More)
+      Byte |= 0x80; // Mark this byte to show that more bytes will follow.
+    hash.update(Byte);
+  } while (More);
+}
+
+void TypeHash::addString(StringRef str) {
+  hash.update(str);
+  hash.update('\0');
+}
+
+void TypeHash::addAttributes(const DWARFDie &die) {
+
+  if (!die.isValid())
+    return;
+
+  die.getAbbreviationDeclarationPtr()->enumerateAttributesWithValues(
+      die.getOffset(), *(die.getDwarfUnit()), dieAttributesToExtract,
+      [&, die](const dwarf::Attribute attr, const DWARFFormValue &value) {
+        hashAttribute(attr, value, die.getTag());
+      });
+}
+
+// Hash an individual attribute \param Attr based on the type of attribute and
+// the form.
+// DWARFFormValue
+void TypeHash::hashAttribute(dwarf::Attribute attribute,
+                             const DWARFFormValue &value, dwarf::Tag tag) {
+  if (value.isFormClass(DWARFFormValue::FC_Unknown)) {
+    llvm_unreachable("Expected valid DWARFFormValue");
+  } else if (value.isFormClass(DWARFFormValue::FC_Reference)) {
+    addULEB128(dwarf::DW_FORM_sdata);
+
+    switch (value.getForm()) {
+    case dwarf::DW_FORM_ref1:
+    case dwarf::DW_FORM_ref2:
+    case dwarf::DW_FORM_ref4:
+    case dwarf::DW_FORM_ref8:
+    case dwarf::DW_FORM_ref_udata:
+      if (auto UnitOffset = value.getAsRelativeReference()) {
+        assert(UnitOffset->Unit);
+        assert(UnitOffset->Unit == &cu);
+
+        DWARFDie refDIE =
+            cu.getDIEForOffset(static_cast<uint32_t>(UnitOffset->Offset));
+
+        hashDIEEntry(attribute, tag, refDIE);
+      }
+      break;
+
+    case dwarf::DW_FORM_ref_addr:
+      if (auto InsectionOffset = value.getAsRelativeReference()) {
+        if (DWARFUnit *Unit = allUnits.getUnitForOffset(
+                static_cast<uint32_t>(InsectionOffset->Offset)))
+          hashDIEEntry(attribute, tag,
+                       Unit->getDIEForOffset(Unit->getOffset()));
+      }
+      break;
+
+    case dwarf::DW_FORM_ref_sig8:
+    case dwarf::DW_FORM_GNU_ref_alt:
+      addSLEB128(static_cast<int64_t>(value.getRawUValue()));
+      break;
+    case dwarf::DW_FORM_ref_sup4:
+    case dwarf::DW_FORM_ref_sup8:
+      // TODO: implement cross object files references
+      addSLEB128(static_cast<int64_t>(value.getRawUValue()));
+      break;
+
+    default:
+      // nothing to do
+      break;
+    };
+  } else if (value.isFormClass(DWARFFormValue::FC_SectionOffset)) {
+    if (value.getForm() == dwarf::Form::DW_FORM_strp ||
+        value.getForm() == dwarf::Form::DW_FORM_line_strp) {
+      addULEB128('A');
+      addULEB128(attribute);
+      addULEB128(dwarf::DW_FORM_string);
+      if (Optional<const char *> str = value.getAsCString())
+        addString(*str);
+    } else {
+      addULEB128('A');
+      addULEB128(attribute);
+      switch (value.getForm()) {
+      case dwarf::DW_FORM_data1:
+      case dwarf::DW_FORM_data2:
+      case dwarf::DW_FORM_data4:
+      case dwarf::DW_FORM_data8:
+      case dwarf::DW_FORM_udata:
+      case dwarf::DW_FORM_sdata:
+        addULEB128(dwarf::DW_FORM_sdata);
+        addSLEB128(static_cast<int64_t>(value.getRawUValue()));
+        break;
+      default:
+        // nothing to do
+        break;
+      };
+    }
+  } else if (value.isFormClass(DWARFFormValue::FC_Constant) ||
+             value.isFormClass(DWARFFormValue::FC_Address)) {
+    addULEB128('A');
+    addULEB128(attribute);
+    switch (value.getForm()) {
+    case dwarf::DW_FORM_data1:
+    case dwarf::DW_FORM_data2:
+    case dwarf::DW_FORM_data4:
+    case dwarf::DW_FORM_data8:
+    case dwarf::DW_FORM_udata:
+    case dwarf::DW_FORM_sdata:
+      addULEB128(dwarf::DW_FORM_sdata);
+      addSLEB128(static_cast<int64_t>(value.getRawUValue()));
+      break;
+    default:
+      // nothing to do
+      break;
+    };
+  } else if (value.isFormClass(DWARFFormValue::FC_Flag)) {
+    addULEB128(dwarf::DW_FORM_flag);
+    addULEB128(value.getRawUValue());
+  } else if (value.isFormClass(DWARFFormValue::FC_String)) {
+    addULEB128('A');
+    addULEB128(attribute);
+    addULEB128(dwarf::DW_FORM_string);
+    if (Optional<const char *> str = value.getAsCString())
+      addString(*str);
+  } else if (value.isFormClass(DWARFFormValue::FC_Block) ||
+             value.isFormClass(DWARFFormValue::FC_Exprloc)) {
+    addULEB128('A');
+    addULEB128(attribute);
+    addULEB128(dwarf::DW_FORM_block);
+    if (auto BlockData = value.getAsBlock()) {
+      addULEB128(BlockData->size());
+      hash.update(*BlockData);
+    } else
+      addULEB128(0);
+  } else {
+    // Value.isFormClass(DWARFFormValue::FC_Indirect)
+    llvm_unreachable("Not yet implemented");
+  }
+}
+
+void TypeHash::hashDIEEntry(dwarf::Attribute attribute, dwarf::Tag tag,
+                            const DWARFDie &entry) {
+
+  assert(tag != dwarf::DW_TAG_friend && "No current LLVM clients emit friend "
+                                        "tags. Add support here when there's "
+                                        "a use case");
+
+  if (!entry.isValid())
+    return;
+
+  // Step 5
+  // If the tag in Step 3 is one of [the below tags]
+  if ((tag == dwarf::DW_TAG_pointer_type ||
+       tag == dwarf::DW_TAG_reference_type ||
+       tag == dwarf::DW_TAG_rvalue_reference_type ||
+       tag == dwarf::DW_TAG_ptr_to_member_type) &&
+      // and the referenced type (via the [below attributes])
+      // FIXME: This seems overly restrictive, and causes hash mismatches
+      // there's a decl/def difference in the containing type of a
+      // ptr_to_member_type, but it's what DWARF says, for some reason.
+      attribute == dwarf::DW_AT_type) {
+    // ... has a DW_AT_name attribute,
+    const char *Name = entry.getName(DINameKind::ShortName);
+    if (Name && *Name) {
+      ParentsList parents;
+      hashShallowTypeReference(attribute, Name, parents);
+      return;
+    }
+  }
+
+  unsigned &dieNumber = numbering[entry.getDebugInfoEntry()];
+
+  if (dieNumber) {
+    hashRepeatedTypeReference(attribute, dieNumber);
+    return;
+  } else {
+    dieNumber = numbering.size();
+
+    // otherwise, b) use the letter 'T' as the marker, ...
+    addULEB128('T');
+
+    addULEB128(attribute);
+
+    ParentsList parents;
+    uint64_t entryOffset = entry.getOffset();
+    HashCache::iterator cachedHash = refsHashes.find(entryOffset);
+
+    if (cachedHash == refsHashes.end()) {
+      uint64_t hashValue = TypeHash(allUnits, cu, refsHashes, numbering)
+                               .computeTypeSignature(entry, parents);
+      refsHashes[entryOffset] = hashValue;
+
+      addULEB128(hashValue);
+    } else
+      addULEB128(cachedHash->second);
+  }
+}
+
+void TypeHash::hashShallowTypeReference(dwarf::Attribute attribute,
+                                        StringRef name, ParentsList &parents) {
+  // append the letter 'N'
+  addULEB128('N');
+
+  // the DWARF attribute code (DW_AT_type or DW_AT_friend),
+  addULEB128(attribute);
+
+  // the context of the tag,
+  addParentContext(parents);
+
+  // the letter 'E',
+  addULEB128('E');
+
+  // and the name of the type.
+  addString(name);
+
+  // Currently DW_TAG_friends are not used by Clang, but if they do become so,
+  // here's the relevant spec text to implement:
+  //
+  // For DW_TAG_friend, if the referenced entry is the DW_TAG_subprogram,
+  // the context is omitted and the name to be used is the ABI-specific name
+  // of the subprogram (e.g., the mangled linker name).
+}
+
+void TypeHash::hashRepeatedTypeReference(dwarf::Attribute attribute,
+                                         unsigned dieNumber) {
+  // a) If T is in the list of [previously hashed types], use the letter
+  // 'R' as the marker
+  addULEB128('R');
+
+  addULEB128(attribute);
+
+  // and use the unsigned LEB128 encoding of [the index of T in the
+  // list] as the attribute value;
+  addULEB128(dieNumber);
+}

lld/ELF/Options.td

 
 defm format: Eq<"format", "Change the input format of the inputs following this option">,
   MetaVarName<"[default,elf,binary]">;
 
 defm gc_sections: B<"gc-sections",
     "Enable garbage collection of unused sections",
     "Disable garbage collection of unused sections (default)">;
 
+defm gc_debuginfo: B<"gc-debuginfo",
+    "Enable garbage collection of unused debug information",
+    "Disable garbage collection of unused debug information (default)">;
+
+defm gc_debuginfo_types: B<"gc-debuginfo-types",
+    "Deduplicate types while doing garbage collection of unused sections",
+    "Do not deduplicate types while doing garbage collection of unused sections(default)">;
+
 defm gdb_index: B<"gdb-index",
     "Generate .gdb_index section",
     "Do not generate .gdb_index section (default)">;
 
 defm gnu_unique: B<"gnu-unique",
   "Enable STB_GNU_UNIQUE symbol binding (default)",
   "Disable STB_GNU_UNIQUE symbol binding">;
 

lld/test/ELF/Inputs/gc-debuginfo-main.ll

+
+; generated from the following(-g -O):
+;
+; func.h  
+;
+; struct SS {
+;     int   a1;
+;     float a2;
+;
+;     struct inner_SS {
+;       int a1;
+;     };
+; };
+; 
+; int func_mod1_used ( int p1 );
+; int func_mod1_not_used ( int p1 );
+; int func_mod2_used ( SS p1 );
+; int func_mod2_not_used ( SS p1 );
+;
+; main.cpp
+;
+; #include "func.h"
+;
+; int main ( void ) {
+;    SS s;
+;    SS::inner_SS is;
+;
+;    is.a1 = 3;
+;    s.a1 += 3 + is.a1;
+;
+;    func_mod1_used(s.a1);
+;
+;    func_mod2_used(s);
+; }
+;
+
+; ModuleID = 'main.cpp'
+source_filename = "main.cpp"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.SS = type { i32, float }
+%"struct.SS::inner_SS" = type { i32 }
+
+; Function Attrs: noinline norecurse optnone uwtable
+define dso_local i32 @main() #0 !dbg !7 {
+  %1 = alloca %struct.SS, align 4
+  %2 = alloca %"struct.SS::inner_SS", align 4
+  %3 = alloca %struct.SS, align 4
+  call void @llvm.dbg.declare(metadata %struct.SS* %1, metadata !11, metadata !DIExpression()), !dbg !18
+  call void @llvm.dbg.declare(metadata %"struct.SS::inner_SS"* %2, metadata !19, metadata !DIExpression()), !dbg !23
+  %4 = getelementptr inbounds %"struct.SS::inner_SS", %"struct.SS::inner_SS"* %2, i32 0, i32 0, !dbg !24
+  store i32 3, i32* %4, align 4, !dbg !25
+  %5 = getelementptr inbounds %"struct.SS::inner_SS", %"struct.SS::inner_SS"* %2, i32 0, i32 0, !dbg !26
+  %6 = load i32, i32* %5, align 4, !dbg !26
+  %7 = add nsw i32 3, %6, !dbg !27
+  %8 = getelementptr inbounds %struct.SS, %struct.SS* %1, i32 0, i32 0, !dbg !28
+  %9 = load i32, i32* %8, align 4, !dbg !29
+  %10 = add nsw i32 %9, %7, !dbg !29
+  store i32 %10, i32* %8, align 4, !dbg !29
+  %11 = getelementptr inbounds %struct.SS, %struct.SS* %1, i32 0, i32 0, !dbg !30
+  %12 = load i32, i32* %11, align 4, !dbg !30
+  %13 = call i32 @_Z14func_mod1_usedi(i32 %12), !dbg !31
+  %14 = bitcast %struct.SS* %3 to i8*, !dbg !32
+  %15 = bitcast %struct.SS* %1 to i8*, !dbg !32
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %14, i8* align 4 %15, i64 8, i1 false), !dbg !32
+  %16 = bitcast %struct.SS* %3 to i64*, !dbg !33
+  %17 = load i64, i64* %16, align 4, !dbg !33
+  %18 = call i32 @_Z14func_mod2_used2SS(i64 %17), !dbg !33
+  ret i32 0, !dbg !34
+}
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+declare dso_local i32 @_Z14func_mod1_usedi(i32) #2
+
+declare dso_local i32 @_Z14func_mod2_used2SS(i64) #2
+
+; Function Attrs: argmemonly nounwind willreturn
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1 immarg) #3
+
+attributes #0 = { nounwind ssp uwtable }
+attributes #1 = { nounwind readnone }
+attributes #2 = { nounwind readnone }
+attributes #3 = { nounwind readnone }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, nameTableKind: None)
+!1 = !DIFile(filename: "main.cpp", directory: "function-sections")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang"}
+!7 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !DILocalVariable(name: "s", scope: !7, file: !1, line: 4, type: !12)
+!12 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "SS", file: !13, line: 2, size: 64, flags: DIFlagTypePassByValue, elements: !14, identifier: "_ZTS2SS")
+!13 = !DIFile(filename: "./func.h", directory: "function-sections")
+!14 = !{!15, !16}
+!15 = !DIDerivedType(tag: DW_TAG_member, name: "a1", scope: !12, file: !13, line: 3, baseType: !10, size: 32)
+!16 = !DIDerivedType(tag: DW_TAG_member, name: "a2", scope: !12, file: !13, line: 4, baseType: !17, size: 32, offset: 32)
+!17 = !DIBasicType(name: "float", size: 32, encoding: DW_ATE_float)
+!18 = !DILocation(line: 4, column: 7, scope: !7)
+!19 = !DILocalVariable(name: "is", scope: !7, file: !1, line: 5, type: !20)
+!20 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "inner_SS", scope: !12, file: !13, line: 6, size: 32, flags: DIFlagTypePassByValue, elements: !21, identifier: "_ZTSN2SS8inner_SSE")
+!21 = !{!22}
+!22 = !DIDerivedType(tag: DW_TAG_member, name: "a1", scope: !20, file: !13, line: 7, baseType: !10, size: 32)
+!23 = !DILocation(line: 5, column: 17, scope: !7)
+!24 = !DILocation(line: 7, column: 7, scope: !7)
+!25 = !DILocation(line: 7, column: 10, scope: !7)
+!26 = !DILocation(line: 8, column: 19, scope: !7)
+!27 = !DILocation(line: 8, column: 14, scope: !7)
+!28 = !DILocation(line: 8, column: 6, scope: !7)
+!29 = !DILocation(line: 8, column: 9, scope: !7)
+!30 = !DILocation(line: 10, column: 21, scope: !7)
+!31 = !DILocation(line: 10, column: 4, scope: !7)
+!32 = !DILocation(line: 12, column: 19, scope: !7)
+!33 = !DILocation(line: 12, column: 4, scope: !7)
+!34 = !DILocation(line: 13, column: 1, scope: !7)

lld/test/ELF/Inputs/gc-debuginfo-mod1.ll

+;
+; generated from the following(-g -O):
+;
+; func.h  
+;
+; struct SS {
+;     int   a1;
+;     float a2;
+;
+;     struct inner_SS {
+;       int a1;
+;     };
+; };
+; 
+; int func_mod1_used ( int p1 );
+; int func_mod1_not_used ( int p1 );
+; int func_mod2_used ( SS p1 );
+; int func_mod2_not_used ( SS p1 );
+;
+; mod1.cpp
+;
+; #include "func.h"
+;
+; int func_mod1_used ( int p1 ) {
+;     return p1 + 10;
+; }
+;
+; int func_mod1_not_used ( int p1 ) {
+;     return p1 + 10;
+; }
+;
+
+; ModuleID = 'mod1.cpp'
+source_filename = "mod1.cpp"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: noinline nounwind optnone uwtable
+define dso_local i32 @_Z14func_mod1_usedi(i32) #0 !dbg !7 {
+  %2 = alloca i32, align 4
+  store i32 %0, i32* %2, align 4
+  call void @llvm.dbg.declare(metadata i32* %2, metadata !11, metadata !DIExpression()), !dbg !12
+  %3 = load i32, i32* %2, align 4, !dbg !13
+  %4 = add nsw i32 %3, 10, !dbg !14
+  ret i32 %4, !dbg !15
+}
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+; Function Attrs: noinline nounwind optnone uwtable
+define dso_local i32 @_Z18func_mod1_not_usedi(i32) #0 !dbg !16 {
+  %2 = alloca i32, align 4
+  store i32 %0, i32* %2, align 4
+  call void @llvm.dbg.declare(metadata i32* %2, metadata !17, metadata !DIExpression()), !dbg !18
+  %3 = load i32, i32* %2, align 4, !dbg !19
+  %4 = add nsw i32 %3, 10, !dbg !20
+  ret i32 %4, !dbg !21
+}
+
+attributes #0 = { nounwind ssp uwtable }
+attributes #1 = { nounwind readnone }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, nameTableKind: None)
+!1 = !DIFile(filename: "mod1.cpp", directory: "function-sections")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang"}
+!7 = distinct !DISubprogram(name: "func_mod1_used", linkageName: "_Z14func_mod1_usedi", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10, !10}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !DILocalVariable(name: "p1", arg: 1, scope: !7, file: !1, line: 3, type: !10)
+!12 = !DILocation(line: 3, column: 26, scope: !7)
+!13 = !DILocation(line: 4, column: 12, scope: !7)
+!14 = !DILocation(line: 4, column: 15, scope: !7)
+!15 = !DILocation(line: 4, column: 5, scope: !7)
+!16 = distinct !DISubprogram(name: "func_mod1_not_used", linkageName: "_Z18func_mod1_not_usedi", scope: !1, file: !1, line: 7, type: !8, scopeLine: 7, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!17 = !DILocalVariable(name: "p1", arg: 1, scope: !16, file: !1, line: 7, type: !10)
+!18 = !DILocation(line: 7, column: 30, scope: !16)
+!19 = !DILocation(line: 8, column: 12, scope: !16)
+!20 = !DILocation(line: 8, column: 15, scope: !16)
+!21 = !DILocation(line: 8, column: 5, scope: !16)

lld/test/ELF/Inputs/gc-debuginfo-mod2.ll

+;
+; generated from the following(-g -O):
+;
+; func.h 
+;
+; struct SS {
+;     int   a1;
+;     float a2;
+;
+;     struct inner_SS {
+;       int a1;
+;     };
+; };
+; 
+; int func_mod1_used ( int p1 );
+; int func_mod1_not_used ( int p1 );
+; int func_mod2_used ( SS p1 );
+; int func_mod2_not_used ( SS p1 );
+;
+; mod2.cpp
+;
+; #include "func.h"
+;
+; int func_mod2_used ( SS p1 ) {
+;
+;     SS::inner_SS is;
+;
+;     is.a1 = 10 + p1.a1;
+;
+;     return is.a1 + 10;
+; }
+;
+;
+; int func_mod2_not_used ( SS p1 ) {
+;     return p1.a1 + 10;
+; }
+
+; ModuleID = 'mod2.cpp'
+source_filename = "mod2.cpp"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.SS = type { i32, float }
+%"struct.SS::inner_SS" = type { i32 }
+
+; Function Attrs: noinline nounwind optnone uwtable
+define dso_local i32 @_Z14func_mod2_used2SS(i64) #0 !dbg !7 {
+  %2 = alloca %struct.SS, align 4
+  %3 = alloca %"struct.SS::inner_SS", align 4
+  %4 = bitcast %struct.SS* %2 to i64*
+  store i64 %0, i64* %4, align 4
+  call void @llvm.dbg.declare(metadata %struct.SS* %2, metadata !17, metadata !DIExpression()), !dbg !18
+  call void @llvm.dbg.declare(metadata %"struct.SS::inner_SS"* %3, metadata !19, metadata !DIExpression()), !dbg !23
+  %5 = getelementptr inbounds %struct.SS, %struct.SS* %2, i32 0, i32 0, !dbg !24
+  %6 = load i32, i32* %5, align 4, !dbg !24
+  %7 = add nsw i32 10, %6, !dbg !25
+  %8 = getelementptr inbounds %"struct.SS::inner_SS", %"struct.SS::inner_SS"* %3, i32 0, i32 0, !dbg !26
+  store i32 %7, i32* %8, align 4, !dbg !27
+  %9 = getelementptr inbounds %"struct.SS::inner_SS", %"struct.SS::inner_SS"* %3, i32 0, i32 0, !dbg !28
+  %10 = load i32, i32* %9, align 4, !dbg !28
+  %11 = add nsw i32 %10, 10, !dbg !29
+  ret i32 %11, !dbg !30
+}
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+; Function Attrs: noinline nounwind optnone uwtable
+define dso_local i32 @_Z18func_mod2_not_used2SS(i64) #0 !dbg !31 {
+  %2 = alloca %struct.SS, align 4
+  %3 = bitcast %struct.SS* %2 to i64*
+  store i64 %0, i64* %3, align 4
+  call void @llvm.dbg.declare(metadata %struct.SS* %2, metadata !32, metadata !DIExpression()), !dbg !33
+  %4 = getelementptr inbounds %struct.SS, %struct.SS* %2, i32 0, i32 0, !dbg !34
+  %5 = load i32, i32* %4, align 4, !dbg !34
+  %6 = add nsw i32 %5, 10, !dbg !35
+  ret i32 %6, !dbg !36
+}
+
+attributes #0 = { nounwind ssp uwtable }
+attributes #1 = { nounwind readnone }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, nameTableKind: None)
+!1 = !DIFile(filename: "mod2.cpp", directory: "function-sections")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang"}
+!7 = distinct !DISubprogram(name: "func_mod2_used", linkageName: "_Z14func_mod2_used2SS", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10, !11}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "SS", file: !12, line: 2, size: 64, flags: DIFlagTypePassByValue, elements: !13, identifier: "_ZTS2SS")
+!12 = !DIFile(filename: "./func.h", directory: "function-sections")
+!13 = !{!14, !15}
+!14 = !DIDerivedType(tag: DW_TAG_member, name: "a1", scope: !11, file: !12, line: 3, baseType: !10, size: 32)
+!15 = !DIDerivedType(tag: DW_TAG_member, name: "a2", scope: !11, file: !12, line: 4, baseType: !16, size: 32, offset: 32)
+!16 = !DIBasicType(name: "float", size: 32, encoding: DW_ATE_float)
+!17 = !DILocalVariable(name: "p1", arg: 1, scope: !7, file: !1, line: 3, type: !11)
+!18 = !DILocation(line: 3, column: 25, scope: !7)
+!19 = !DILocalVariable(name: "is", scope: !7, file: !1, line: 5, type: !20)
+!20 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "inner_SS", scope: !11, file: !12, line: 6, size: 32, flags: DIFlagTypePassByValue, elements: !21, identifier: "_ZTSN2SS8inner_SSE")
+!21 = !{!22}
+!22 = !DIDerivedType(tag: DW_TAG_member, name: "a1", scope: !20, file: !12, line: 7, baseType: !10, size: 32)
+!23 = !DILocation(line: 5, column: 18, scope: !7)
+!24 = !DILocation(line: 7, column: 21, scope: !7)
+!25 = !DILocation(line: 7, column: 16, scope: !7)
+!26 = !DILocation(line: 7, column: 8, scope: !7)
+!27 = !DILocation(line: 7, column: 11, scope: !7)
+!28 = !DILocation(line: 9, column: 15, scope: !7)
+!29 = !DILocation(line: 9, column: 18, scope: !7)
+!30 = !DILocation(line: 9, column: 5, scope: !7)
+!31 = distinct !DISubprogram(name: "func_mod2_not_used", linkageName: "_Z18func_mod2_not_used2SS", scope: !1, file: !1, line: 12, type: !8, scopeLine: 12, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!32 = !DILocalVariable(name: "p1", arg: 1, scope: !31, file: !1, line: 12, type: !11)
+!33 = !DILocation(line: 12, column: 29, scope: !31)
+!34 = !DILocation(line: 13, column: 15, scope: !31)
+!35 = !DILocation(line: 13, column: 18, scope: !31)
+!36 = !DILocation(line: 13, column: 5, scope: !31)

lld/test/ELF/gc-debuginfo-with-types.s

+
+# REQUIRES: x86
+
+# RUN: echo '.global _start; _start: jmp main;' \
+# RUN:   | llvm-mc --filetype=obj --triple=x86_64-unknown-linux - -o %t.o
+# RUN: llc --mtriple=x86_64-- --function-sections --filetype=obj -o %t1.o %p/Inputs/gc-debuginfo-mod1.ll
+# RUN: llc --mtriple=x86_64-- --function-sections --filetype=obj -o %t2.o %p/Inputs/gc-debuginfo-mod2.ll
+# RUN: llc --mtriple=x86_64-- --function-sections --filetype=obj -o %t3.o %p/Inputs/gc-debuginfo-main.ll
+
+# RUN: ld.lld -gc-sections -gc-debuginfo -gc-debuginfo-types %t.o %t1.o %t2.o %t3.o -o %t4.out
+
+# RUN: llvm-dwarfdump --verify %t4.out | FileCheck --check-prefix=VERIFY %s
+
+# RUN: llvm-dwarfdump --a %t4.out | FileCheck %s
+
+# VERIFY: No errors
+
+# CHECK: .debug_info contents
+# CHECK: DW_TAG_compile_unit
+# CHECK: DW_AT_name        ("mod1.cpp")
+# CHECK: DW_AT_stmt_list   (0x{{0*}}[[LINETBL_MOD1_OFF:[0-9A-Fa-f]+]])
+# CHECK: DW_AT_ranges (0x{{[0-9A-Fa-f]+}}
+# CHECK-NEXT: [0x[[MOD1_LOW_PC:[0-9A-Fa-f]+]], 0x[[MOD1_HIGH_PC:[0-9A-Fa-f]+]]))
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_low_pc (0x[[MOD1_LOW_PC]])
+# CHECK: DW_AT_high_pc (0x[[MOD1_HIGH_PC]])
+# CHECK: DW_AT_name      ("func_mod1_used")
+# CHECK: DW_AT_type      (0x{{0*}}[[BASE_INT_OFF:[0-9A-Fa-f]+]] "int")
+# CHECK: DW_TAG_formal_parameter
+# CHECK: DW_AT_type      (0x{{0*}}[[BASE_INT_OFF]] "int")
+# CHECK: NULL
+# CHECK: 0x{{0*}}[[BASE_INT_OFF]]: DW_TAG_base_type
+# CHECK-NEXT: DW_AT_name      ("int")
+# CHECK: NULL
+# CHECK: DW_TAG_compile_unit
+# CHECK: DW_AT_name        ("mod2.cpp")
+# CHECK: DW_AT_stmt_list   (0x{{0*}}[[LINETBL_MOD2_OFF:[0-9A-Fa-f]+]])
+# CHECK: DW_AT_ranges (0x{{[0-9A-Fa-f]+}}
+# CHECK-NEXT: [0x[[MOD2_LOW_PC:[0-9A-Fa-f]+]], 0x[[MOD2_HIGH_PC:[0-9A-Fa-f]+]]))
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_low_pc (0x[[MOD2_LOW_PC]])
+# CHECK: DW_AT_high_pc (0x[[MOD2_HIGH_PC]])
+# CHECK: DW_AT_name      ("func_mod2_used")
+# CHECK: DW_AT_type      (0x{{0*}}[[BASE_INT_OFF]] "int")
+# CHECK: DW_TAG_formal_parameter
+# CHECK: DW_AT_name    ("p1")
+# CHECK: DW_AT_type    (0x{{0*}}[[STRUCT_SS_OFF:[0-9A-Fa-f]+]] "SS")
+# CHECK: DW_TAG_variable
+# CHECK: DW_AT_name    ("is")
+# CHECK: DW_AT_type    (0x{{0*}}[[STRUCT_INNER_SS_OFF:[0-9A-Fa-f]+]] "inner_SS")
+# CHECK: NULL
+# CHECK-NOT: DW_TAG_base_type
+# CHECK: 0x{{0*}}[[STRUCT_SS_OFF]]: DW_TAG_structure_type
+# CHECK: DW_AT_name      ("SS")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name    ("a1")
+# CHECK: DW_AT_type    (0x{{0*}}[[BASE_INT_OFF]] "int")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name    ("a2")
+# CHECK: DW_AT_type    (0x{{0*}}[[BASE_FLOAT_OFF:[0-9A-Fa-f]+]] "float")
+# CHECK: 0x{{0*}}[[STRUCT_INNER_SS_OFF]]: DW_TAG_structure_type
+# CHECK: DW_AT_name    ("inner_SS")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name  ("a1")
+# CHECK: DW_AT_type    (0x{{0*}}[[BASE_INT_OFF]] "int")
+# CHECK: NULL
+# CHECK: NULL
+# CHECK: 0x{{0*}}[[BASE_FLOAT_OFF]]: DW_TAG_base_type
+# CHECK-NEXT: DW_AT_name      ("float")
+# CHECK: NULL
+# CHECK: DW_TAG_compile_unit
+# CHECK: DW_AT_name        ("main.cpp")
+# CHECK: DW_AT_stmt_list   (0x{{0*}}[[LINETBL_MOD3_OFF:[0-9A-Fa-f]+]])
+# CHECK: DW_AT_low_pc      (0x[[MOD3_LOW_PC:[0-9A-Fa-f]+]])
+# CHECK: DW_AT_high_pc     (0x[[MOD3_HIGH_PC:[0-9A-Fa-f]+]])
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_low_pc    (0x[[MOD3_LOW_PC]])
+# CHECK: DW_AT_high_pc   (0x[[MOD3_HIGH_PC]])
+# CHECK: DW_AT_name      ("main")
+# CHECK: DW_AT_type      (0x{{0*}}[[BASE_INT_OFF]] "int")
+# CHECK: DW_TAG_variable
+# CHECK: DW_AT_name    ("s")
+# CHECK: DW_AT_type    (0x{{0*}}[[STRUCT_SS_OFF]] "SS")
+# CHECK: DW_TAG_variable
+# CHECK: DW_AT_name    ("is")
+# CHECK: DW_AT_type    (0x{{0*}}[[STRUCT_INNER_SS_OFF]] "inner_SS")
+# CHECK: NULL
+# CHECK-NOT: DW_TAG_structure_type
+# CHECK: NULL
+# CHECK: debug_line contents
+# CHECK: debug_line[0x{{0*}}[[LINETBL_MOD1_OFF]]]
+# CHECK: Address
+# CHECK: 0x{{0*}}[[MOD1_LOW_PC]]
+# CHECK-NOT: 0x{{0* }}
+# CHECK: debug_line[0x{{0*}}[[LINETBL_MOD2_OFF]]]
+# CHECK: Address
+# CHECK: 0x{{0*}}[[MOD2_LOW_PC]]
+# CHECK-NOT: 0x{{0* }} 
+# CHECK: debug_line[0x{{0*}}[[LINETBL_MOD3_OFF]]]
+# CHECK: Address
+# CHECK: 0x{{0*}}[[MOD3_LOW_PC]]
+# CHECK-NOT: 0x{{0* }}
+# CHECK: debug_ranges contents:
+# CHECK: {{0*}} {{0*}}[[MOD1_LOW_PC]] {{0*}}[[MOD1_HIGH_PC]]
+# CHECK: {{0*}} <End of list>
+# CHECK: {{0*}} {{0*}}[[MOD2_LOW_PC]] {{0*}}[[MOD2_HIGH_PC]]
+# CHECK: {{0*}} <End of list>
+
+

lld/test/ELF/gc-debuginfo-wo-types.s

+
+# REQUIRES: x86
+
+# RUN: echo '.global _start; _start: jmp main;' \
+# RUN:   | llvm-mc --filetype=obj --triple=x86_64-unknown-linux - -o %t.o
+# RUN: llc --mtriple=x86_64-- --function-sections --filetype=obj -o %t1.o %p/Inputs/gc-debuginfo-mod1.ll
+# RUN: llc --mtriple=x86_64-- --function-sections --filetype=obj -o %t2.o %p/Inputs/gc-debuginfo-mod2.ll
+# RUN: llc --mtriple=x86_64-- --function-sections --filetype=obj -o %t3.o %p/Inputs/gc-debuginfo-main.ll
+
+# RUN: ld.lld -gc-sections -gc-debuginfo %t.o %t1.o %t2.o %t3.o -o %t4.out
+
+# RUN: llvm-dwarfdump --verify %t4.out | FileCheck --check-prefix=VERIFY %s
+
+# RUN: llvm-dwarfdump --a %t4.out | FileCheck %s
+
+# VERIFY: No errors
+
+# CHECK: .debug_info contents
+# CHECK: DW_TAG_compile_unit
+# CHECK: DW_AT_name        ("mod1.cpp")
+# CHECK: DW_AT_stmt_list   (0x{{0*}}[[LINETBL_MOD1_OFF:[0-9A-Fa-f]+]])
+# CHECK: DW_AT_ranges (0x{{[0-9A-Fa-f]+}}
+# CHECK-NEXT: [0x[[MOD1_LOW_PC:[0-9A-Fa-f]+]], 0x[[MOD1_HIGH_PC:[0-9A-Fa-f]+]]))
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_low_pc (0x[[MOD1_LOW_PC]])
+# CHECK: DW_AT_high_pc (0x[[MOD1_HIGH_PC]])
+# CHECK: DW_AT_name      ("func_mod1_used")
+# CHECK: DW_AT_type      (0x{{0*}}[[MOD1_BASE_INT_OFF:[0-9A-Fa-f]+]] "int")
+# CHECK: DW_TAG_formal_parameter
+# CHECK: DW_AT_type      (0x{{0*}}[[MOD1_BASE_INT_OFF]] "int")
+# CHECK: NULL
+# CHECK: 0x{{0*}}[[MOD1_BASE_INT_OFF]]: DW_TAG_base_type
+# CHECK-NEXT: DW_AT_name      ("int")
+# CHECK: NULL
+# CHECK: DW_TAG_compile_unit
+# CHECK: DW_AT_name        ("mod2.cpp")
+# CHECK: DW_AT_stmt_list   (0x{{0*}}[[LINETBL_MOD2_OFF:[0-9A-Fa-f]+]])
+# CHECK: DW_AT_ranges (0x{{[0-9A-Fa-f]+}}
+# CHECK-NEXT: [0x[[MOD2_LOW_PC:[0-9A-Fa-f]+]], 0x[[MOD2_HIGH_PC:[0-9A-Fa-f]+]]))
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_low_pc (0x[[MOD2_LOW_PC]])
+# CHECK: DW_AT_high_pc (0x[[MOD2_HIGH_PC]])
+# CHECK: DW_AT_name      ("func_mod2_used")
+# CHECK: DW_AT_type      (0x{{0*}}[[MOD2_BASE_INT_OFF:[0-9A-Fa-f]+]] "int")
+# CHECK: DW_TAG_formal_parameter
+# CHECK: DW_AT_name    ("p1")
+# CHECK: DW_AT_type    (0x{{0*}}[[STRUCT_SS_OFF:[0-9A-Fa-f]+]] "SS")
+# CHECK: DW_TAG_variable
+# CHECK: DW_AT_name    ("is")
+# CHECK: DW_AT_type    (0x{{0*}}[[STRUCT_INNER_SS_OFF:[0-9A-Fa-f]+]] "inner_SS")
+# CHECK: NULL
+# CHECK: 0x{{0*}}[[MOD2_BASE_INT_OFF]]: DW_TAG_base_type
+# CHECK-NEXT: DW_AT_name      ("int")
+# CHECK: 0x{{0*}}[[STRUCT_SS_OFF]]: DW_TAG_structure_type
+# CHECK: DW_AT_name      ("SS")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name    ("a1")
+# CHECK: DW_AT_type    (0x{{0*}}[[MOD2_BASE_INT_OFF]] "int")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name    ("a2")
+# CHECK: DW_AT_type    (0x{{0*}}[[BASE_FLOAT_OFF:[0-9A-Fa-f]+]] "float")
+# CHECK: 0x{{0*}}[[STRUCT_INNER_SS_OFF]]: DW_TAG_structure_type
+# CHECK: DW_AT_name    ("inner_SS")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name  ("a1")
+# CHECK: DW_AT_type    (0x{{0*}}[[MOD2_BASE_INT_OFF]] "int")
+# CHECK: NULL
+# CHECK: NULL
+# CHECK: 0x{{0*}}[[BASE_FLOAT_OFF]]: DW_TAG_base_type
+# CHECK-NEXT: DW_AT_name      ("float")
+# CHECK: NULL
+# CHECK: DW_TAG_compile_unit
+# CHECK: DW_AT_name        ("main.cpp")
+# CHECK: DW_AT_stmt_list   (0x{{0*}}[[LINETBL_MOD3_OFF:[0-9A-Fa-f]+]])
+# CHECK: DW_AT_low_pc      (0x[[MOD3_LOW_PC:[0-9A-Fa-f]+]])
+# CHECK: DW_AT_high_pc     (0x[[MOD3_HIGH_PC:[0-9A-Fa-f]+]])
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_low_pc    (0x[[MOD3_LOW_PC]])
+# CHECK: DW_AT_high_pc   (0x[[MOD3_HIGH_PC]])
+# CHECK: DW_AT_name      ("main")
+# CHECK: DW_AT_type      (0x{{0*}}[[MOD3_BASE_INT_OFF:[0-9A-Fa-f]+]] "int")
+# CHECK: DW_TAG_variable
+# CHECK: DW_AT_name    ("s")
+# CHECK: DW_AT_type    (0x{{0*}}[[MOD3_STRUCT_SS_OFF:[0-9A-Fa-f]+]] "SS")
+# CHECK: DW_TAG_variable
+# CHECK: DW_AT_name    ("is")
+# CHECK: DW_AT_type    (0x{{0*}}[[MOD3_STRUCT_INNER_SS_OFF:[0-9A-Fa-f]+]] "inner_SS")
+# CHECK: NULL
+# CHECK: 0x{{0*}}[[MOD3_BASE_INT_OFF]]: DW_TAG_base_type
+# CHECK-NEXT: DW_AT_name      ("int")
+# CHECK: 0x{{0*}}[[MOD3_STRUCT_SS_OFF]]: DW_TAG_structure_type
+# CHECK: DW_AT_name      ("SS")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name    ("a1")
+# CHECK: DW_AT_type    (0x{{0*}}[[MOD3_BASE_INT_OFF]] "int")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name    ("a2")
+# CHECK: DW_AT_type    (0x{{0*}}[[MOD3_BASE_FLOAT_OFF:[0-9A-Fa-f]+]] "float")
+# CHECK: 0x{{0*}}[[MOD3_STRUCT_INNER_SS_OFF]]: DW_TAG_structure_type
+# CHECK: DW_AT_name    ("inner_SS")
+# CHECK: DW_TAG_member
+# CHECK: DW_AT_name  ("a1")
+# CHECK: DW_AT_type    (0x{{0*}}[[MOD3_BASE_INT_OFF]] "int")
+# CHECK: NULL
+# CHECK: NULL
+# CHECK: 0x{{0*}}[[MOD3_BASE_FLOAT_OFF]]: DW_TAG_base_type
+# CHECK-NEXT: DW_AT_name      ("float")
+# CHECK: NULL
+# CHECK: debug_line contents
+# CHECK: debug_line[0x{{0*}}[[LINETBL_MOD1_OFF]]]
+# CHECK: Address
+# CHECK: 0x{{0*}}[[MOD1_LOW_PC]]
+# CHECK-NOT: 0x{{0* }}
+# CHECK: debug_line[0x{{0*}}[[LINETBL_MOD2_OFF]]]
+# CHECK: Address
+# CHECK: 0x{{0*}}[[MOD2_LOW_PC]]
+# CHECK-NOT: 0x{{0* }} 
+# CHECK: debug_line[0x{{0*}}[[LINETBL_MOD3_OFF]]]
+# CHECK: Address
+# CHECK: 0x{{0*}}[[MOD3_LOW_PC]]
+# CHECK-NOT: 0x{{0* }}
+# CHECK: debug_ranges contents:
+# CHECK: {{0*}} {{0*}}[[MOD1_LOW_PC]] {{0*}}[[MOD1_HIGH_PC]]
+# CHECK: {{0*}} <End of list>
+# CHECK: {{0*}} {{0*}}[[MOD2_LOW_PC]] {{0*}}[[MOD2_HIGH_PC]]
+# CHECK: {{0*}} <End of list>
+
+

llvm/include/llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h

 //===- DWARFAbbreviationDeclaration.h ---------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_DWARFABBREVIATIONDECLARATION_H
 #define LLVM_DEBUGINFO_DWARFABBREVIATIONDECLARATION_H
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/Support/DataExtractor.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 
 namespace llvm {
 
 class DWARFFormValue;
 class DWARFUnit;
 class raw_ostream;
 
 class DWARFAbbreviationDeclaration {
 public:
   struct AttributeSpec {
-    AttributeSpec(dwarf::Attribute A, dwarf::Form F, int64_t Value)
-        : Attr(A), Form(F), Value(Value) {
+    AttributeSpec(dwarf::Attribute A, dwarf::Form F, int64_t Value, uint64_t FO)
+        : Attr(A), Form(F), FormOffset(FO), Value(Value) {
       assert(isImplicitConst());
     }
-    AttributeSpec(dwarf::Attribute A, dwarf::Form F, Optional<uint8_t> ByteSize)
-        : Attr(A), Form(F) {
+    AttributeSpec(dwarf::Attribute A, dwarf::Form F, Optional<uint8_t> ByteSize,
+                  uint64_t FO)
+        : Attr(A), Form(F), FormOffset(FO) {
       assert(!isImplicitConst());
       this->ByteSize.HasByteSize = ByteSize.hasValue();
       if (this->ByteSize.HasByteSize)
         this->ByteSize.ByteSize = *ByteSize;
     }
 
     dwarf::Attribute Attr;
     dwarf::Form Form;
+    uint64_t FormOffset;
 
   private:
     /// The following field is used for ByteSize for non-implicit_const
     /// attributes and as value for implicit_const ones, indicated by
     /// Form == DW_FORM_implicit_const.
     /// The following cases are distinguished:
     /// * Form != DW_FORM_implicit_const and HasByteSize is true:
     ///     ByteSize contains the fixed size in bytes for the Form in this
public:
   ///
   /// Extract an attribute value for a DWARFUnit given the DIE offset and the
   /// attribute.
   ///
   /// \param DIEOffset the DIE offset that points to the ULEB128 abbreviation
   /// code in the .debug_info data.
   /// \param Attr DWARF attribute to search for.
   /// \param U the DWARFUnit the contains the DIE.
-  /// \returns Optional DWARF form value if the attribute was extracted.
-  Optional<DWARFFormValue> getAttributeValue(const uint64_t DIEOffset,
-                                             const dwarf::Attribute Attr,
-                                             const DWARFUnit &U) const;
+  /// \returns Optional DWARF form value if the attribute was extracted
+  /// \returns and it`s offset.
+  Optional<std::pair<DWARFFormValue, uint64_t>>
+  getAttributeValue(const uint64_t DIEOffset, const dwarf::Attribute Attr,
 
+  void enumerateAttributesWithValues(
+      const uint64_t DIEOffset, const DWARFUnit &U,
+      SmallDenseSet<uint16_t, 0x40> &DieAttributesToExtract,
+      std::function<void(const dwarf::Attribute, const DWARFFormValue &)>
+          Handler) const;
+
   bool extract(DataExtractor Data, uint64_t* OffsetPtr);
   void dump(raw_ostream &OS) const;
 
   // Return an optional byte size of all attribute data in this abbreviation
   // if a constant byte size can be calculated given a DWARFUnit. This allows
   // DWARF parsing to be faster as many DWARF DIEs have a fixed byte size.
   Optional<size_t> getFixedAttributesByteSize(const DWARFUnit &U) const;
 

llvm/include/llvm/DebugInfo/DWARF/DWARFDebugLine.h

struct Sequence {
     uint64_t HighPC;
     /// If relocation information is present then this is the index of the
     /// section which contains above addresses. Otherwise this is
     /// object::SectionedAddress::Undef value.
     uint64_t SectionIndex;
     unsigned FirstRowIndex;
     unsigned LastRowIndex;
     bool Empty;
-
     void reset();
 
     static bool orderByHighPC(const Sequence &LHS, const Sequence &RHS) {
       return std::tie(LHS.SectionIndex, LHS.HighPC) <
              std::tie(RHS.SectionIndex, RHS.HighPC);
     }
 
     bool isValid() const {
       return !Empty && (LowPC < HighPC) && (FirstRowIndex < LastRowIndex);
     }
 
     bool containsPC(object::SectionedAddress PC) const {
       return SectionIndex == PC.SectionIndex &&
              (LowPC <= PC.Address && PC.Address < HighPC);
     }
   };
+  struct SequenceBoundaries {
+    /// Start offset of sequence inside .debug_line sections
+    uint64_t StartOffset;
+    uint64_t EndOffset;
+    uint64_t SectionIndex;
+
+    void reset() {
+      StartOffset = 0;
+      EndOffset = 0;
+      SectionIndex = 0;
+    }
+  };
 
   struct LineTable {
     LineTable();
 
     /// Represents an invalid row
     const uint32_t UnknownRowIndex = UINT32_MAX;
 
     void appendRow(const DWARFDebugLine::Row &R) { Rows.push_back(R); }
Error parse(
         const DWARFContext &Ctx, const DWARFUnit *U,
         std::function<void(Error)> RecoverableErrorCallback,
         raw_ostream *OS = nullptr);
 
     using RowVector = std::vector<Row>;
     using RowIter = RowVector::const_iterator;
     using SequenceVector = std::vector<Sequence>;
     using SequenceIter = SequenceVector::const_iterator;
+    using SequenceBoundariesVector = std::vector<SequenceBoundaries>;
 
     struct Prologue Prologue;
     RowVector Rows;
     SequenceVector Sequences;
+    SequenceBoundariesVector SequenceBoundaries;
 
   private:
     uint32_t findRowInSeq(const DWARFDebugLine::Sequence &Seq,
                           object::SectionedAddress Address) const;
     Optional<StringRef>
     getSourceByIndex(uint64_t FileIndex,
                      DILineInfoSpecifier::FileLineInfoKind Kind) const;
 
private:
     bool Done = false;
   };
 
 private:
   struct ParsingState {
     ParsingState(struct LineTable *LT);
 
     void resetRowAndSequence();
-    void appendRowToMatrix();
+    void appendRowToMatrix(uint32_t Offset);
 
     /// Line table we're currently parsing.
     struct LineTable *LineTable;
     struct Row Row;
     struct Sequence Sequence;
+    struct SequenceBoundaries SequenceBoundaries;
   };
 
   using LineTableMapTy = std::map<uint64_t, LineTable>;
   using LineTableIter = LineTableMapTy::iterator;
   using LineTableConstIter = LineTableMapTy::const_iterator;
 
   LineTableMapTy LineTableMap;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARFDEBUGLINE_H

llvm/include/llvm/DebugInfo/DWARF/DWARFDie.h

public:
 
   /// Extract the specified attribute from this DIE.
   ///
   /// Extract an attribute value from this DIE only. This call doesn't look
   /// for the attribute value in any DW_AT_specification or
   /// DW_AT_abstract_origin referenced DIEs.
   ///
   /// \param Attr the attribute to extract.
-  /// \returns an optional DWARFFormValue that will have the form value if the
-  /// attribute was successfully extracted.
+  /// \returns an optional DWARFFormValue that will have the form value
+  /// and its offset if the attribute was successfully extracted.
   Optional<DWARFFormValue> find(dwarf::Attribute Attr) const;
 
+  Optional<std::pair<DWARFFormValue, uint64_t>>
+  findWithOffset(dwarf::Attribute Attr) const;
+
   /// Extract the first value of any attribute in Attrs from this DIE.
   ///
   /// Extract the first attribute that matches from this DIE only. This call
   /// doesn't look for the attribute value in any DW_AT_specification or
   /// DW_AT_abstract_origin referenced DIEs. The attributes will be searched
   /// linearly in the order they are specified within Attrs.
   ///
   /// \param Attrs an array of DWARF attribute to look for.

llvm/include/llvm/DebugInfo/DWARF/DWARFUnit.h

class DWARFUnit {
 
   /// A table of range lists (DWARF v5 and later).
   Optional<DWARFDebugRnglistTable> RngListTable;
 
   mutable const DWARFAbbreviationDeclarationSet *Abbrevs;
   llvm::Optional<object::SectionedAddress> BaseAddr;
   /// The compile unit debug information entry items.
   std::vector<DWARFDebugInfoEntry> DieArray;
+  std::vector<uint32_t> DieParentsArray;
 
   /// Map from range's start address to end address and corresponding DIE.
   /// IntervalMap does not support range removal, as a result, we use the
   /// std::map::upper_bound for address range lookup.
   std::map<uint64_t, std::pair<uint64_t, DWARFDie>> AddrDieMap;
 
   using die_iterator_range =
       iterator_range<std::vector<DWARFDebugInfoEntry>::iterator>;
private:
   }
 
   /// extractDIEsIfNeeded - Parses a compile unit and indexes its DIEs if it
   /// hasn't already been done
   void extractDIEsIfNeeded(bool CUDieOnly);
 
   /// extractDIEsToVector - Appends all parsed DIEs to a vector.
   void extractDIEsToVector(bool AppendCUDie, bool AppendNonCUDIEs,
-                           std::vector<DWARFDebugInfoEntry> &DIEs) const;
+                           std::vector<DWARFDebugInfoEntry> &DIEs,
+                           std::vector<uint32_t> &DieParentsArray) const;
 
   /// clearDIEs - Clear parsed DIEs to keep memory usage low.
   void clearDIEs(bool KeepCUDie);
 
   /// parseDWO - Parses .dwo file for current compile unit. Returns true if
   /// it was actually constructed.
   bool parseDWO();
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARF_DWARFUNIT_H

llvm/lib/DebugInfo/DWARF/DWARFAbbreviationDeclaration.cpp

DWARFAbbreviationDeclaration::extract(DataExtractor Data,
   // Assign a value to our optional FixedAttributeSize member variable. If
   // this member variable still has a value after the while loop below, then
   // all attribute data in this abbreviation declaration has a fixed byte size.
   FixedAttributeSize = FixedSizeInfo();
 
   // Read all of the abbreviation attributes and forms.
   while (true) {
     auto A = static_cast<Attribute>(Data.getULEB128(OffsetPtr));
+    uint64_t FormOffset = *OffsetPtr;
     auto F = static_cast<Form>(Data.getULEB128(OffsetPtr));
     if (A && F) {
       bool IsImplicitConst = (F == DW_FORM_implicit_const);
       if (IsImplicitConst) {
         int64_t V = Data.getSLEB128(OffsetPtr);
-        AttributeSpecs.push_back(AttributeSpec(A, F, V));
+        AttributeSpecs.push_back(AttributeSpec(A, F, V, FormOffset));
         continue;
       }
       Optional<uint8_t> ByteSize;
       // If this abbrevation still has a fixed byte size, then update the
       // FixedAttributeSize as needed.
       switch (F) {
       case DW_FORM_addr:
         if (FixedAttributeSize)
if (A && F) {
         }
         // Indicate we no longer have a fixed byte size for this
         // abbreviation by clearing the FixedAttributeSize optional value
         // so it doesn't have a value.
         FixedAttributeSize.reset();
         break;
       }
       // Record this attribute and its fixed size if it has one.
-      AttributeSpecs.push_back(AttributeSpec(A, F, ByteSize));
+      AttributeSpecs.push_back(AttributeSpec(A, F, ByteSize, FormOffset));
     } else if (A == 0 && F == 0) {
       // We successfully reached the end of this abbreviation declaration
       // since both attribute and form are zero.
       break;
     } else {
       // Attribute and form pairs must either both be non-zero, in which case
       // they are added to the abbreviation declaration, or both be zero to
       // terminate the abbrevation declaration. In this case only one was

 DWARFAbbreviationDeclaration::findAttributeIndex(dwarf::Attribute Attr) const {
   for (uint32_t i = 0, e = AttributeSpecs.size(); i != e; ++i) {
     if (AttributeSpecs[i].Attr == Attr)
       return i;
   }
   return None;
 }
 
-Optional<DWARFFormValue> DWARFAbbreviationDeclaration::getAttributeValue(
-    const uint64_t DIEOffset, const dwarf::Attribute Attr,
+void DWARFAbbreviationDeclaration::enumerateAttributesWithValues(
+    const uint64_t DIEOffset, const DWARFUnit &U,
+    SmallDenseSet<uint16_t, 0x40> &DieAttributesToExtract,
+    std::function<void(const dwarf::Attribute, const DWARFFormValue &)> Handler)
+    const {
+
+  auto DebugInfoData = U.getDebugInfoExtractor();
+
+  // Add the byte size of ULEB that for the abbrev Code so we can start
+  // skipping the attribute data.
+  uint64_t Offset = DIEOffset + CodeByteSize;
+  uint32_t extractedAttrsNum = 0;
+  for (const auto &Spec : AttributeSpecs) {
+
+    if (extractedAttrsNum >= DieAttributesToExtract.size())
+      break;
+
+    if (DieAttributesToExtract.count(Spec.Attr)) {
+      // We have arrived at the attribute to extract, extract if from Offset.
+      if (Spec.isImplicitConst()) {
+        Handler(Spec.Attr, DWARFFormValue::createFromSValue(
+                               Spec.Form, Spec.getImplicitConstValue()));
+      } else {
+        DWARFFormValue FormValue(Spec.Form);
+        if (FormValue.extractValue(DebugInfoData, &Offset, U.getFormParams(),
+                                   &U))
+          Handler(Spec.Attr, FormValue);
+      }
+
+      extractedAttrsNum++;
+    } else {
+      // March Offset along until we get to the attribute we want.
+      if (auto FixedSize = Spec.getByteSize(U))
+        Offset += *FixedSize;
+      else
+        DWARFFormValue::skipValue(Spec.Form, DebugInfoData, &Offset,
+                                  U.getFormParams());
+    }
+  }
+}
+
+Optional<std::pair<DWARFFormValue, uint64_t>>
+DWARFAbbreviationDeclaration::getAttributeValue(const uint64_t DIEOffset,
+                                                const dwarf::Attribute Attr,
                                                 const DWARFUnit &U) const {
   Optional<uint32_t> MatchAttrIndex = findAttributeIndex(Attr);
   if (!MatchAttrIndex)
     return None;
 
   auto DebugInfoData = U.getDebugInfoExtractor();
 
   // Add the byte size of ULEB that for the abbrev Code so we can start
   // skipping the attribute data.
   uint64_t Offset = DIEOffset + CodeByteSize;
   uint32_t AttrIndex = 0;
   for (const auto &Spec : AttributeSpecs) {
     if (*MatchAttrIndex == AttrIndex) {
+      uint64_t StartOffset = Offset;
+
       // We have arrived at the attribute to extract, extract if from Offset.
       if (Spec.isImplicitConst())
-        return DWARFFormValue::createFromSValue(Spec.Form,
-                                                Spec.getImplicitConstValue());
+        return std::make_pair(DWARFFormValue::createFromSValue(
+                                  Spec.Form, Spec.getImplicitConstValue()),
+                              Offset);
 
       DWARFFormValue FormValue(Spec.Form);
       if (FormValue.extractValue(DebugInfoData, &Offset, U.getFormParams(), &U))
-        return FormValue;
+        return std::make_pair(FormValue, StartOffset);
     }
     // March Offset along until we get to the attribute we want.
     if (auto FixedSize = Spec.getByteSize(U))
       Offset += *FixedSize;
     else
       DWARFFormValue::skipValue(Spec.Form, DebugInfoData, &Offset,
                                 U.getFormParams());
     ++AttrIndex;

llvm/lib/DebugInfo/DWARF/DWARFDebugLine.cpp

if (!Rows.empty()) {
     }
   }
 }
 
 void DWARFDebugLine::LineTable::clear() {
   Prologue.clear();
   Rows.clear();
   Sequences.clear();
+  SequenceBoundaries.clear();
 }
 
 DWARFDebugLine::ParsingState::ParsingState(struct LineTable *LT)
     : LineTable(LT) {
   resetRowAndSequence();
 }
 
 void DWARFDebugLine::ParsingState::resetRowAndSequence() {
   Row.reset(LineTable->Prologue.DefaultIsStmt);
   Sequence.reset();
 }
 
-void DWARFDebugLine::ParsingState::appendRowToMatrix() {
+void DWARFDebugLine::ParsingState::appendRowToMatrix(uint32_t Offset) {
   unsigned RowNumber = LineTable->Rows.size();
   if (Sequence.Empty) {
     // Record the beginning of instruction sequence.
     Sequence.Empty = false;
     Sequence.LowPC = Row.Address.Address;
     Sequence.FirstRowIndex = RowNumber;
+    SequenceBoundaries.StartOffset = Offset;
   }
   LineTable->appendRow(Row);
   if (Row.EndSequence) {
     // Record the end of instruction sequence.
     Sequence.HighPC = Row.Address.Address;
     Sequence.LastRowIndex = RowNumber + 1;
     Sequence.SectionIndex = Row.Address.SectionIndex;
-    if (Sequence.isValid())
+    SequenceBoundaries.EndOffset = Offset;
+    SequenceBoundaries.SectionIndex = Row.Address.SectionIndex;
+    if (Sequence.isValid()) {
       LineTable->appendSequence(Sequence);
+      LineTable->SequenceBoundaries.push_back(SequenceBoundaries);
+    }
     Sequence.reset();
+    SequenceBoundaries.reset();
   }
   Row.postAppend();
 }
 
 const DWARFDebugLine::LineTable *
 DWARFDebugLine::getLineTable(uint64_t Offset) const {
   LineTableConstIter Pos = LineTableMap.find(Offset);
   if (Pos != LineTableMap.end())
Error DWARFDebugLine::LineTable::parse(
   // See if we should tell the data extractor the address size.
   if (DebugLineData.getAddressSize() == 0)
     DebugLineData.setAddressSize(Prologue.getAddressSize());
   else
     assert(Prologue.getAddressSize() == 0 ||
            Prologue.getAddressSize() == DebugLineData.getAddressSize());
 
   ParsingState State(this);
-
   while (*OffsetPtr < EndOffset) {
     if (OS)
       *OS << format("0x%08.08" PRIx64 ": ", *OffsetPtr);
 
+    uint32_t StartOffset = *OffsetPtr;
+
     uint8_t Opcode = DebugLineData.getU8(OffsetPtr);
 
     if (OS)
       *OS << format("%02.02" PRIx8 " ", Opcode);
 
     if (Opcode == 0) {
       // Extended Opcodes always start with a zero opcode followed by
       // a uleb128 length so you can skip ones you don't know about
if (Opcode == 0) {
         // Set the end_sequence register of the state machine to true and
         // append a row to the matrix using the current values of the
         // state-machine registers. Then reset the registers to the initial
         // values specified above. Every statement program sequence must end
         // with a DW_LNE_end_sequence instruction which creates a row whose
         // address is that of the byte after the last target machine instruction
         // of the sequence.
         State.Row.EndSequence = true;
-        State.appendRowToMatrix();
+        State.appendRowToMatrix(*OffsetPtr);
         if (OS) {
           *OS << "\n";
           OS->indent(12);
           State.Row.dump(*OS);
         }
         State.resetRowAndSequence();
+        StartOffset = *OffsetPtr;
         break;
 
       case DW_LNE_set_address:
         // Takes a single relocatable address as an operand. The size of the
         // operand is the size appropriate to hold an address on the target
         // machine. Set the address register to the value given by the
         // relocatable address. All of the other statement program opcodes
         // that affect the address register add a delta to it. This instruction
if (Opcode == 0) {
         // Takes no arguments. Append a row to the matrix using the
         // current values of the state-machine registers.
         if (OS) {
           *OS << "\n";
           OS->indent(12);
           State.Row.dump(*OS);
           *OS << "\n";
         }
-        State.appendRowToMatrix();
+        State.appendRowToMatrix(StartOffset);
         break;
 
       case DW_LNS_advance_pc:
         // Takes a single unsigned LEB128 operand, multiplies it by the
         // min_inst_length field of the prologue, and adds the
         // result to the address register of the state machine.
         {
           uint64_t AddrOffset =
if (Opcode == 0) {
 
       if (OS) {
         *OS << "address += " << AddrOffset << ",  line += " << LineOffset
             << "\n";
         OS->indent(12);
         State.Row.dump(*OS);
       }
 
-      State.appendRowToMatrix();
+      State.appendRowToMatrix(StartOffset);
     }
     if(OS)
       *OS << "\n";
   }
 
   if (!State.Sequence.Empty)
     RecoverableErrorCallback(
         createStringError(errc::illegal_byte_sequence,

llvm/lib/DebugInfo/DWARF/DWARFDie.cpp

 bool DWARFDie::isSubprogramDIE() const { return getTag() == DW_TAG_subprogram; }
 
 bool DWARFDie::isSubroutineDIE() const {
   auto Tag = getTag();
   return Tag == DW_TAG_subprogram || Tag == DW_TAG_inlined_subroutine;
 }
 
 Optional<DWARFFormValue> DWARFDie::find(dwarf::Attribute Attr) const {
+
+  Optional<std::pair<DWARFFormValue, uint64_t>> ResOrErr = findWithOffset(Attr);
+
+  if (ResOrErr)
+    return ResOrErr->first;
+
+  return None;
+}
+
+Optional<std::pair<DWARFFormValue, uint64_t>>
+DWARFDie::findWithOffset(dwarf::Attribute Attr) const {
   if (!isValid())
     return None;
   auto AbbrevDecl = getAbbreviationDeclarationPtr();
   if (AbbrevDecl)
     return AbbrevDecl->getAttributeValue(getOffset(), Attr, *U);
   return None;
 }
 
 Optional<DWARFFormValue>
 DWARFDie::find(ArrayRef<dwarf::Attribute> Attrs) const {
   if (!isValid())
     return None;
   auto AbbrevDecl = getAbbreviationDeclarationPtr();
   if (AbbrevDecl) {
     for (auto Attr : Attrs) {
       if (auto Value = AbbrevDecl->getAttributeValue(getOffset(), Attr, *U))
-        return Value;
+        return Value->first;
     }
   }
   return None;
 }
 
 Optional<DWARFFormValue>
 DWARFDie::findRecursively(ArrayRef<dwarf::Attribute> Attrs) const {
   std::vector<DWARFDie> Worklist;

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

void DWARFUnit::clear() {
   clearDIEs(false);
   DWO.reset();
 }
 
 const char *DWARFUnit::getCompilationDir() {
   return dwarf::toString(getUnitDIE().find(DW_AT_comp_dir), nullptr);
 }
 
-void DWARFUnit::extractDIEsToVector(
-    bool AppendCUDie, bool AppendNonCUDies,
-    std::vector<DWARFDebugInfoEntry> &Dies) const {
+void DWARFUnit::extractDIEsToVector(bool AppendCUDie, bool AppendNonCUDies,
+                                    std::vector<DWARFDebugInfoEntry> &Dies,
+                                    std::vector<uint32_t> &DieParents) const {
   if (!AppendCUDie && !AppendNonCUDies)
     return;
 
   // Set the offset to that of the first DIE and calculate the start of the
   // next compilation unit header.
   uint64_t DIEOffset = getOffset() + getHeaderSize();
   uint64_t NextCUOffset = getNextUnitOffset();
+  std::vector<uint64_t> Parents;
   DWARFDebugInfoEntry DIE;
   DWARFDataExtractor DebugInfoData = getDebugInfoExtractor();
   uint32_t Depth = 0;
   bool IsCUDie = true;
 
   while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
                          Depth)) {
     if (IsCUDie) {
-      if (AppendCUDie)
+      if (AppendCUDie) {
         Dies.push_back(DIE);
+        DieParents.push_back(UINT32_MAX);
+      }
       if (!AppendNonCUDies)
         break;
       // The average bytes per DIE entry has been seen to be
       // around 14-20 so let's pre-reserve the needed memory for
       // our DIE entries accordingly.
       Dies.reserve(Dies.size() + getDebugInfoSize() / 14);
+      DieParents.reserve(Dies.capacity());
       IsCUDie = false;
     } else {
       Dies.push_back(DIE);
+      if (Parents.size() > 0) {
+        DieParents.push_back(Parents.back());
+      } else {
+        DieParents.push_back(UINT32_MAX);
+      }
     }
 
     if (const DWARFAbbreviationDeclaration *AbbrDecl =
             DIE.getAbbreviationDeclarationPtr()) {
       // Normal DIE
-      if (AbbrDecl->hasChildren())
+      if (AbbrDecl->hasChildren()) {
         ++Depth;
+        assert(Dies.size() > 0);
+        Parents.push_back(Dies.size() - 1);
+      }
     } else {
       // NULL DIE.
-      if (Depth > 0)
+      if (Depth > 0) {
         --Depth;
+        assert(Parents.size() > 0);
+        Parents.pop_back();
+      }
       if (Depth == 0)
         break;  // We are done with this compile unit!
     }
   }
 
+  assert(Dies.size() == DieParentsArray.size());
+
   // Give a little bit of info if we encounter corrupt DWARF (our offset
   // should always terminate at or before the start of the next compilation
   // unit header).
   if (DIEOffset > NextCUOffset)
     WithColor::warning() << format("DWARF compile unit extends beyond its "
                                    "bounds cu 0x%8.8" PRIx64 " "
                                    "at 0x%8.8" PRIx64 "\n",
                                    getOffset(), DIEOffset);
 }
 
 void DWARFUnit::extractDIEsIfNeeded(bool CUDieOnly) {
   if (Error e = tryExtractDIEsIfNeeded(CUDieOnly))
     WithColor::error() << toString(std::move(e));
 }
 
 Error DWARFUnit::tryExtractDIEsIfNeeded(bool CUDieOnly) {
   if ((CUDieOnly && !DieArray.empty()) ||
       DieArray.size() > 1)
     return Error::success(); // Already parsed.
 
   bool HasCUDie = !DieArray.empty();
-  extractDIEsToVector(!HasCUDie, !CUDieOnly, DieArray);
+  extractDIEsToVector(!HasCUDie, !CUDieOnly, DieArray, DieParentsArray);
 
   if (DieArray.empty())
     return Error::success();
 
   // If CU DIE was just parsed, copy several attribute values from it.
   if (HasCUDie)
     return Error::success();
 
bool DWARFUnit::parseDWO() {
   return true;
 }
 
 void DWARFUnit::clearDIEs(bool KeepCUDie) {
   if (DieArray.size() > (unsigned)KeepCUDie) {
     DieArray.resize((unsigned)KeepCUDie);
     DieArray.shrink_to_fit();
   }
+  if (DieParentsArray.size() > (unsigned)KeepCUDie) {
+    DieParentsArray.resize((unsigned)KeepCUDie);
+    DieParentsArray.shrink_to_fit();
+  }
 }
 
 Expected<DWARFAddressRangesVector>
 DWARFUnit::findRnglistFromOffset(uint64_t Offset) {
   if (getVersion() <= 4) {
     DWARFDebugRangeList RangeList;
     if (Error E = extractRangeList(Offset, RangeList))
       return std::move(E);
DWARFDie DWARFUnit::getParent(const DWARFDebugInfoEntry *Die) {
   const uint32_t Depth = Die->getDepth();
   // Unit DIEs always have a depth of zero and never have parents.
   if (Depth == 0)
     return DWARFDie();
   // Depth of 1 always means parent is the compile/type unit.
   if (Depth == 1)
     return getUnitDIE();
   // Look for previous DIE with a depth that is one less than the Die's depth.
-  const uint32_t ParentDepth = Depth - 1;
-  for (uint32_t I = getDIEIndex(Die) - 1; I > 0; --I) {
-    if (DieArray[I].getDepth() == ParentDepth)
-      return DWARFDie(this, &DieArray[I]);
+
+  uint32_t ParentIdx = DieParentsArray[getDIEIndex(Die)];
+  if (ParentIdx != UINT32_MAX) {
+    return getDIEAtIndex(ParentIdx);
   }
+
   return DWARFDie();
 }
 
 DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
   if (!Die)
     return DWARFDie();
   uint32_t Depth = Die->getDepth();
   // Unit DIEs always have a depth of zero and never have siblings.

llvm/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

for(auto it = Abbrevs->begin(); it != Abbrevs->end(); ++it) {
     if (it->getNumAttributes() == 0)
       continue; // root abbrev for DW_TAG_compile_unit
 
     auto A = it->getAttrByIndex(0);
     EXPECT_EQ(A, Attr);
 
     auto FormValue = it->getAttributeValue(/* offset */ 0, A, *U);
     EXPECT_TRUE((bool)FormValue);
-    EXPECT_EQ(FormValue->getForm(), dwarf::DW_FORM_implicit_const);
+    EXPECT_EQ(FormValue->first.getForm(), dwarf::DW_FORM_implicit_const);
 
-    const auto V = FormValue->getAsSignedConstant();
+    const auto V = FormValue->first.getAsSignedConstant();
     EXPECT_TRUE((bool)V);
 
     auto VerifyAbbrevDump = [&V](AbbrevIt it) {
       std::string S;
       llvm::raw_string_ostream OS(S);
       it->dump(OS);
       auto FormPos = OS.str().find("DW_FORM_implicit_const");
       EXPECT_NE(FormPos, std::string::npos);