[lld][ELF] Rewrite ICF-folded references rather than tombstoning them

[phosek]

Summary

This modifies the logic introduced in D82828 to address the case that
was brought up in PR47150.

Currently, we use tombstone value for all discarded references in
.debug_line section, but we rewrite ICF references in other debug
sections. This introduces inconsistency between .debug_line and
.debug_info data which is a problem for consumers such as GSYM.

This change modifies the behavior to be more consistent: we always
rewrite the reference for ICF folded case across all debug sections,
and we always use the tombstone value for all other cases.

[phosek]

In PR47150, @dblaikie suggested reopening the discussion with reviewers on D82828 which is the purpose of this change in addition to also implementing the solution proposed there.

[jhenderson]

Added two colleagues from my team who have been working on our downstream version of this and I think might have slightly better insight than me.

[MaskRay]

We decided to use a tombstone value because multiple CUs with overlapping address ranges and shared entities are problematic (PR47150#comment3).
The main reason we exclude .debug_info is because breaking points do not work on folded functions (D82828).

The patch will revert all ICF related behavior and make us go back to square one (if we do this, I don't see the value of !isDebug) and cause confusion to DWARF consumers.
Do we need this? From https://bugs.llvm.org//show_bug.cgi?id=47150#c5 this is a bug in llvm-gsymutil.

[bd1976llvm]

I plan to investigate this further after the weekend; but, I wanted to say that the current scheme is known to be compatible with gdb and with Sony's proprietary debugger and yields a reasonable, if not ideal, debugging experience.

What testing has been performed for consumers with this proposed patch?

[dblaikie]

Does anyone have examples of common DWARF consumers producing CUs with overlapping ranges? Might help inform this feature/implementation choice.

In D89099#2322029, @MaskRay wrote:

We decided to use a tombstone value because multiple CUs with overlapping address ranges and shared entities are problematic (PR47150#comment3).
The main reason we exclude .debug_info is because breaking points do not work on folded functions (D82828).

Though in doing so we created another inconsistency - where instructions described in debug_line overlap, but aren't covered by the debug_info CU's address range description (DW_AT_low/high_pc or DW_AT_ranges).

The patch will revert all ICF related behavior and make us go back to square one (if we do this, I don't see the value of !isDebug) and cause confusion to DWARF consumers.
Do we need this? From https://bugs.llvm.org//show_bug.cgi?id=47150#c5 this is a bug in llvm-gsymutil.

Sounds like @phosek is looking to address things on a few different fronts - trying to make the DWARF more consistent (though not without other problems of more significantly overlapping CUs) while also pursuing an llvm-gsymutil improvement as well.

[bd1976llvm]

Apologies that I haven't had much time to look into this. I tried this style of patching with Sony's proprietary debugger and the user experience w.r.t. source locations and setting breakpoints was degraded. When I find time I will try to determine what is theoretically best here and whether the degradation in the debugging experience that I saw is an artefact of our proprietary debuggers implementation or if it points to something important. We should try with other consumers as well.

lld/ELF/InputSection.cpp

 // So, we handle relocations for non-alloc sections directly in this
 // function as a performance optimization.
 template <class ELFT, class RelTy>
 void InputSection::relocateNonAlloc(uint8_t *buf, ArrayRef<RelTy> rels) {
   const unsigned bits = sizeof(typename ELFT::uint) * 8;
   const bool isDebug = isDebugSection(*this);
   const bool isDebugLocOrRanges =
       isDebug && (name == ".debug_loc" || name == ".debug_ranges");
-  const bool isDebugLine = isDebug && name == ".debug_line";
   Optional<uint64_t> tombstone;
   for (const auto &patAndValue : llvm::reverse(config->deadRelocInNonAlloc))
     if (patAndValue.first.match(this->name)) {
       tombstone = patAndValue.second;
       break;
     }
 
   for (const RelTy &rel : rels) {
if (tombstone ||
       //
       // R_DTPREL type relocations represent an offset into the dynamic thread
       // vector. The computed value is st_value plus a non-negative offset.
       // Negative values are invalid, so -1 can be used as the tombstone value.
       //
       // If the referenced symbol is discarded (made Undefined), or the
       // section defining the referenced symbol is garbage collected,
       // sym.getOutputSection() is nullptr. `ds->section->repl != ds->section`
-      // catches the ICF folded case. However, resolving a relocation in
-      // .debug_line to -1 would stop debugger users from setting breakpoints on
-      // the folded-in function, so exclude .debug_line.
+      // catches the ICF folded case where using tombstone value is undesirable
+      // because it would prevent detecting this case on the consumer side.
       //
       // For pre-DWARF-v5 .debug_loc and .debug_ranges, -1 is a reserved value
       // (base address selection entry), use 1 (which is used by GNU ld for
       // .debug_ranges).
       //
       // TODO To reduce disruption, we use 0 instead of -1 as the tombstone
       // value. Enable -1 in a future release.
       auto *ds = dyn_cast<Defined>(&sym);
       if (!sym.getOutputSection() ||
-          (ds && ds->section->repl != ds->section && !isDebugLine)) {
+          (ds && ds->section->repl != ds->section && !isDebug)) {
         // If -z dead-reloc-in-nonalloc= is specified, respect it.
         const uint64_t value = tombstone ? SignExtend64<bits>(*tombstone)
                                          : (isDebugLocOrRanges ? 1 : 0);
         target->relocateNoSym(bufLoc, type, value);
         continue;
       }
     }
     target->relocateNoSym(bufLoc, type, SignExtend64<bits>(sym.getVA(addend)));

lld/test/ELF/dead-reloc-in-nonalloc.s

 # REQUIRES: x86
 ## Test that -z dead-reloc-in-nonalloc= can customize the tombstone value we
 ## use for an absolute relocation referencing a discarded symbol.
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
 # RUN: ld.lld --icf=all -z dead-reloc-in-nonalloc=.debug_info=0xaaaaaaaa \
 # RUN:   -z dead-reloc-in-nonalloc=.not_debug=0xbbbbbbbb %t.o -o %t
 # RUN: llvm-objdump -s %t | FileCheck %s --check-prefixes=COMMON,AA
 ## 0xaaaaaaaa == 2863311530
 # RUN: ld.lld --icf=all -z dead-reloc-in-nonalloc=.debug_info=2863311530 \
 # RUN:   -z dead-reloc-in-nonalloc=.not_debug=0xbbbbbbbb %t.o -o - | cmp %t -
 
 # COMMON:      Contents of section .debug_addr:
-# COMMON-NEXT:  0000 [[ADDR:[0-9a-f]+]] 00000000 00000000 00000000
+# COMMON-NEXT:  0000 [[ADDR:[0-9a-f]+]] 00000000
+# COMMON-SAME:                                   [[ADDR]] 00000000
 
 # AA:          Contents of section .debug_info:
-# AA-NEXT:      0000 [[ADDR]] 00000000 aaaaaaaa 00000000
+# AA-NEXT:      0000 [[ADDR]] 00000000 [[ADDR]] 00000000
 # AA:          Contents of section .not_debug:
 # AA-NEXT:      0000 bbbbbbbb
 
 ## Specifying zero can get a behavior similar to GNU ld.
 # RUN: ld.lld --icf=all -z dead-reloc-in-nonalloc=.debug_info=0 %t.o -o %tzero
 # RUN: llvm-objdump -s %tzero | FileCheck %s --check-prefixes=COMMON,ZERO
 
 # ZERO:        Contents of section .debug_info:
-# ZERO-NEXT:    0000 {{[0-9a-f]+}}000 00000000 00000000 00000000
+# ZERO-NEXT:    0000 [[ADDR:[0-9a-f]+]] 00000000
+# ZERO-SAME:                                     [[ADDR]] 00000000
 
 ## Glob works.
 # RUN: ld.lld --icf=all -z dead-reloc-in-nonalloc='.debug_i*=0xaaaaaaaa' \
 # RUN:   -z dead-reloc-in-nonalloc='[.]not_debug=0xbbbbbbbb' %t.o -o - | cmp %t -
 
 ## If a section matches multiple option. The last option wins.
 # RUN: ld.lld --icf=all -z dead-reloc-in-nonalloc='.debug_info=1' \
 # RUN:   -z dead-reloc-in-nonalloc='.debug_i*=0' %t.o -o - | cmp %tzero -

lld/test/ELF/debug-dead-reloc-icf.s

 # REQUIRES: x86
 ## Test we resolve symbolic relocations in .debug_* sections to a tombstone
 ## value if the referenced section symbol is folded into another section by ICF.
 ## Otherwise, we would leave entries in multiple CUs claiming ownership of the
 ## same range of code, which can confuse consumers.
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
 # RUN: ld.lld --icf=all %t.o -o %t
 # RUN: llvm-objdump -s %t | FileCheck %s
 
 # CHECK:      Contents of section .debug_info:
-# CHECK-NEXT:  0000 {{[0-9a-f]+}}000 00000000 00000000 00000000
+# CHECK-NEXT:  0000 [[ADDR:[0-9a-f]+]] 00000000
+# CHECK-SAME:                                   [[ADDR]] 00000000
 # CHECK:      Contents of section .debug_line:
 # CHECK-NEXT:  0000 [[ADDR:[0-9a-f]+]] 00000000
 # CHECK-SAME:                                   [[ADDR]] 00000000
 
 .globl _start
 _start:
   ret