ELF: Make sections with KeepUnique bit eligible for ICF.

[pcc]

Summary

The only restriction is that we cannot merge more than one KeepUnique
section together. This matches gold's behaviour and reduces code size
when using --icf=safe.

[ruiu]

lld/ELF/ICF.cpp

471 ↗

(On Diff #156628)

I guess this could be a bit simpler:

for (size_t I = Begin + 1; I < End; ++I) {
  if (Sections[Begin]->KeepUnique && Sections[I]->KeepUnique)
    Begin = I;
  else
    Sections[Begin]->replace(Sections[I]);
}

[pcc]

lld/ELF/ICF.cpp

471 ↗

(On Diff #156628)

It doesn't look like this is correct. With this input:

.globl _start
_start:
call f1
call f2
call f3

.section .text.f1,"ax"
.globl f1
f1:
ret

.section .text.f2,"ax"
.globl f2
f2:
ret

.section .text.f3,"ax"
.globl f3
f3:
ret

I get:

$ ra/bin/ld.lld foo.o --icf=all --print-icf-sections --keep-unique=f2 --keep-unique=f3
$ nm a.out
000000000020100f T f1
000000000020100f T f2
000000000020100f T f3
0000000000201000 T _start

I'll add some comments to my version.

[pcc]

Add comment

[ruiu]

LGTM

[bd1976llvm]

Hi Peter,

Thanks for your address significance tables work!

Specific to this change:

I was under the impression that the intention of --keep-unique was to prevent *all* folding?

I found this open bug against gold that supports this interpretation: https://sourceware.org/bugzilla/show_bug.cgi?id=18865

If I --keep-unique a symbol it seems like I am asking for a strong guarantee on the address of the symbol. The original behaviour matches this strong guarantee.

ELF/ICF.cpp

 // Returns a hash value for S. Note that the information about
 // relocation targets is not included in the hash value.
 template <class ELFT> static uint32_t getHash(InputSection *S) {
   return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
 }
 
 // Returns true if section S is subject of ICF.
 static bool isEligible(InputSection *S) {
-  if (!S->Live || S->KeepUnique || !(S->Flags & SHF_ALLOC))
+  if (!S->Live || !(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;
 
template <class ELFT> void ICF<ELFT>::run() {
   } while (Repeat);
 
   log("ICF needed " + Twine(Cnt) + " iterations");
 
   // Merge sections by the equivalence class.
   forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
     if (End - Begin == 1)
       return;
-    print("selected section " + toString(Sections[Begin]));
-    for (size_t I = Begin + 1; I < End; ++I) {
+    InputSection *Target = nullptr;
+    bool SeenUnique = false, Replaced = false;
+    for (size_t I = Begin; I < End; ++I) {
+      // We aren't allowed to merge two KeepUnique sections as this would break
+      // the guarantees provided by --keep-unique and --icf=safe, but there's
+      // no reason why we can't merge a non-KeepUnique section with a KeepUnique
+      // section. We implement this by only considering the first KeepUnique
+      // section in the equivalence class for merging. If we see any more
+      // KeepUnique sections, we ignore them.
+      if (Sections[I]->KeepUnique) {
+        if (SeenUnique)
+          continue;
+        SeenUnique = true;
+      }
+      if (!Target) {
+        Target = Sections[I];
+        continue;
+      }
+      if (!Replaced)
+        print("selected section " + toString(Target));
       print("  removing identical section " + toString(Sections[I]));
-      Sections[Begin]->replace(Sections[I]);
+      Target->replace(Sections[I]);
+      Replaced = true;
 
       // At this point we know sections merged are fully identical and hence
       // we want to remove duplicate implicit dependencies such as link order
       // and relocation sections.
       for (InputSection *IS : Sections[I]->DependentSections)
         IS->Live = false;
     }
   });

test/ELF/icf-keep-unique.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: ld.lld %t -o %t2 --icf=all --print-icf-sections | FileCheck %s
 # RUN: ld.lld %t -o %t2 --keep-unique f2 --keep-unique f4 --keep-unique f5 --icf=all --print-icf-sections 2>&1 | FileCheck %s -check-prefix=CHECK-KEEP
 
 // Base case, expect only .text.f1 to be kept
 // CHECK: selected section {{.*}}:(.text.f1)
 // CHECK-NEXT:   removing identical section {{.*}}:(.text.f2)
 // CHECK-NEXT:   removing identical section {{.*}}:(.text.f3)
 // CHECK-NEXT:   removing identical section {{.*}}:(.text.f4)
 // CHECK-NEXT:   removing identical section {{.*}}:(.text.f5)
 
-// With --keep-unique f2, f4 and f5 we expect only f3 and f5 to be removed.
+// With --keep-unique f2, f4 and f5 we expect only f2, f3 and f5 to be removed.
+// f2 can be removed despite being --keep-unique because all sections that are
+// merged into it are not --keep-unique.
 // f5 is not matched by --keep-unique as it is a local symbol.
 // CHECK-KEEP: warning: could not find symbol f5 to keep unique
 // CHECK-KEEP: selected section {{.*}}:(.text.f1)
+// CHECK-KEEP-NEXT:   removing identical section {{.*}}:(.text.f2)
 // CHECK-KEEP-NEXT:   removing identical section {{.*}}:(.text.f3)
 // CHECK-KEEP-NEXT:   removing identical section {{.*}}:(.text.f5)
  .globl _start, f1, f2, f3, f4
 _start:
  ret
 
  .section .text.f1, "ax"
 f1: