ELF: Do not ICF SHF_LINK_ORDER sections.

[pcc]

Summary

We are already ICF'ing these sections as a unit with their dependent
sections, so they don't need to be considered for ICF individually.

This change also "fixes" slowness caused by our quadratic-in-group-size
relocation segregation algorithm on 32-bit ARM platforms with unwind
data and ICF on rodata. In this scenario almost every function's
.ARM.exidx is identical except for the targets of the relocations
that refer to the function and its .ARM.extab, which causes almost
all of the program's .ARM.exidx sections to be initially added to the
same class, which causes us to compare every such section with every
other such section.

[peter.smith]

I definitely think that it is the right thing to do to consider the section and the SHF_LINK_ORDER section as a unit. I'm assuming that no merging of the code sections is done if the SHF_LINK_ORDER sections are different.

lld/test/ELF/icf-link-order.s

3 ↗

(On Diff #156963)

Some suggestions for additional cases:

• Two identical executable sections but only one of the sections has a SHF_LINK_ORDER section, for example -fno-exceptions in a subset of the files.
• Two identical executable sections but two different SHF_LINK_ORDER sections. I don't think that this is likely with Arm exception tables but it may be possible with other uses of SHF_LINK_ORDER.

[ruiu]

LGTM

[pcc]

In D49716#1173198, @peter.smith wrote:

I'm assuming that no merging of the code sections is done if the SHF_LINK_ORDER sections are different.

That's something that I think we should do (we do something equivalent in the COFF linker for Windows EH sections) but don't currently do. I'll file a bug about that.

[pcc]

Looks like we already have https://bugs.llvm.org/show_bug.cgi?id=36272 about this.

lld/trunk/ELF/ICF.cpp

if (!S->Live || S->KeepUnique || !(S->Flags & SHF_ALLOC))
     return false;
 
   // Don't merge writable sections. .data.rel.ro sections are marked as writable
   // but are semantically read-only.
   if ((S->Flags & SHF_WRITE) && S->Name != ".data.rel.ro" &&
       !S->Name.startswith(".data.rel.ro."))
     return false;
 
+  // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections,
+  // so we don't consider them for ICF individually.
+  if (S->Flags & SHF_LINK_ORDER)
+    return false;
+
   // Don't merge synthetic sections as their Data member is not valid and empty.
   // The Data member needs to be valid for ICF as it is used by ICF to determine
   // the equality of section contents.
   if (isa<SyntheticSection>(S))
     return false;
 
   // .init and .fini contains instructions that must be executed to initialize
   // and finalize the process. They cannot and should not be merged.

lld/trunk/test/ELF/icf-link-order.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t --icf=all --print-icf-sections | count 0
+
+.section .foo,"a",@progbits,unique,1
+foo1:
+.byte 1
+
+.section .foo,"a",@progbits,unique,2
+foo2:
+.byte 2
+
+.section .bar,"ao",@progbits,foo1,unique,1
+.byte 3
+
+.section .bar,"ao",@progbits,foo2,unique,2
+.byte 3