Replace PRETEND logic with a tombstone value (was: Range lists, zero-length functions, linker gc)

[Fangrui Song]

On 2020-06-03, David Blaikie wrote:
>On Tue, Jun 2, 2020 at 8:10 PM Alan Modra <amodra@gmail.com> wrote:
>>
>> On Tue, Jun 02, 2020 at 11:06:10AM -0700, David Blaikie via Binutils wrote:
>> > On Tue, Jun 2, 2020 at 9:50 AM Mark Wielaard <mark@klomp.org> wrote:
>> > > where I
>> > > would argue the compiler simply needs to make sure that if it generates
>> > > code in separate sections it also should create the DWARF separate
>> > > section (groups).
>> >
>> > I don't think that's practical - the overhead, I believe, is too high.
>> > Headers for each section contribution (ELF headers but DWARF headers
>> > moreso - having a separate .debug_addr, .debug_line, etc section for
>> > each function would be very expensive) would make for very large
>> > object files.
>>
>> With a little linker magic I don't see the neccesity of duplicating
>> the DWARF headers.  Taking .debug_line as an example, a compiler could
>> emit the header, opcode, directory and file tables to a .debug_line
>> section with line statements for function foo emitted to
>> .debug_line.foo and for bar to .debug_line.bar, trusting that the
>> linker will combine these sections in order to create an output
>> .debug_line section.  If foo code is excluded then .debug_line.foo
>> info will also be dropped if section groups are used.
>
>I don't think this would apply to debug_addr - where the entries are
>referenced from elsewhere via index, or debug_rnglist where the
>rnglist header (or the debug_info directly) contains offsets into this
>section, so taking chunks out would break those offsets. (or to the
>file/directory name part of debug_line - where you might want to
>remove file/line entries that were eliminated as dead code - but
>that'd throw off the indexes)

In another thread David reminded me of GNU ld's PRETEND logic.
See bfd/elflink.c:11092 PRETEND and _bfd_elf_check_kept_section.

>a.cc cat <<e
  inline void f1() { }
  void f2() { f1(); }
e
>b.cc cat <<e
  inline void f1() { }
  void f2();
  int main() {
    f1();
    f2();
  }
e
g++ -fuse-ld=bfd -z noseparate-code -g a.cc b.cc -o a.bfd
g++ -fuse-ld=gold -g a.cc b.cc -o a.gold
diff -u <(llvm-dwarfdump a.bfd) <(llvm-dwarfdump a.gold)

...
a.cc is identical except a DW_AT_producer difference.
...
b.cc is different
...
  0x0000006f: DW_TAG_compile_unit
-              DW_AT_producer   ("GNU C++14 9.3.0 -mtune=generic -march=x86-64 -g -fuse-ld=bfd -fasynchronous-unwind-tables")
+              DW_AT_producer   ("GNU C++14 9.3.0 -mtune=generic -march=x86-64 -g -fuse-ld=gold -fasynchronous-unwind-tables")
                DW_AT_language   (DW_LANG_C_plus_plus)
                DW_AT_name       ("b.cc")
                DW_AT_comp_dir   ("/tmp/c")
                DW_AT_ranges     (0x00000030
                   [0x00000000000005f8, 0x000000000000060d)
-                 [0x00000000000005f1, 0x00000000000005f8))
+                 [0x0000000000000000, 0x0000000000000007))
                DW_AT_low_pc     (0x0000000000000000)
                DW_AT_stmt_list  (0x00000054)
  
@@ -76,8 +76,8 @@
                  DW_AT_decl_line        (1)
                  DW_AT_decl_column      (0x0e)
                  DW_AT_linkage_name     ("_Z2f1v")
-                DW_AT_low_pc   (0x00000000000005f1)
-                DW_AT_high_pc  (0x00000000000005f8)
+                DW_AT_low_pc   (0x0000000000000000)
+                DW_AT_high_pc  (0x0000000000000007)
                  DW_AT_frame_base       (DW_OP_call_frame_cfa)
                  DW_AT_GNU_all_call_sites       (true)

Note, the notable difference is that:

* gold resolves a relocation referencing (a STT_SECTION symbol defined in a non-prevailing section group) to 0+addend
   (in the output: DW_AT_low_pc and .debug_ranges entries)
* GNU ld resolves a relocation referencing (a STT_SECTION symbol defined in a non-prevailing section group) to prevailing_section_symbol+addend

(
Note 1, the relocations are of type R_X86_64_64.
Note 2, technically R_X86_64_64 referencing STT_SECTION is in violation of the ELF specification:
> A symbol table entry with STB_LOCAL binding that is defined relative to one of a group's sections, and that is contained in a symbol table section that is not part of the group, must be discarded if the group members are discarded. References to this symbol table entry from outside the group are not allowed.
But we should define the behavior in practice.
)

GNU finds a prevailing replacement for the non-prevailing STT_SECTION symbol. This
requires the text sections in a.o and b.o to have the same size (_bfd_elf_check_kept_section)

Can the proposed tombstone value simplify the PRETEND logic?  See
bfd_elf_match_symbols_in_sections, this function seems to have a very high time complexity.