[LLD][ELF] Improve ICF for relocations to ineligible sections via "aliases"

[andrewng]

Summary

ICF was not able to merge equivalent sections because of relocations to
sections ineligible for ICF that use alternative symbols, e.g. symbol
aliases or section relative relocations.

Merging in this scenario has been enabled by giving the sections that
are ineligigle for ICF a unique ID, i.e. an equivalence class of their
own. This approach also provides another benefit as it improves the
hashing that is used to perform the initial equivalance grouping for
ICF. This is because the ICF ineligible sections can now contribute a
unique value towards the hashes instead of the same value of zero. This
has been seen to reduce link time with ICF by ~68% for objects compiled
with -fprofile-instr-generate.

In order to facilitate this use of a unique ID, the existing
inconsistent approach to the setting of the InputSection eqClass in ICF
has been changed so that there is a clear distinction between the
eqClass values of ICF eligible sections and those of the ineligible
sections that have a unique ID. This inconsistency could have caused
incorrect equivalence class equality in the past, although it appears
that no issues were encountered in actual use.

[MaskRay]

The description can be shortened a bit. The important part is that variableEq returns false if two relocations reference a pair of aliased symbols in an ineligible section.

lld/ELF/ICF.cpp

227

Here this actually computes non-hash IDs. Clearing the MSB (the original code) is better.

357–358

This comment is stale. This code may be deletable.

476

Same comment: this is unneeded. combineRelocHashes updates eqClass[1]

485

This needs a comment. Ineligible sections are assigned unique IDs so that two sections referencing different ineligible sections can be separated.

[MaskRay]

lld/ELF/ICF.cpp

227

hmm. the idea is to make this distinct from a uniqueID.

Let uniqueId start from inputSections.size()?

[MaskRay]

lld/test/ELF/icf18.s

1 ↗

(On Diff #296166)

The test name can be improved. Consider merging this test with icf-non-mergeable.s

[andrewng]

Address review comments.

lld/ELF/ICF.cpp

227

Yes, the intention is to make the equivalence class IDs distinct from the unique IDs, otherwise it might be possible (although very unlikely) for incorrect equality to occur.

I have come up with an alternative solution that uses a base offset derived from uniqueId.

357–358

I have updated the comment, as I believe the code is still applicable.

476

Same reply: combineRelocHashes() only updates the sections that are in the vector sections. The sections that are assigned a unique ID here will not be added to the sections vector, as they are considered ineligible. Therefore, eqClass[1] should also be set to the same unique ID.

lld/test/ELF/icf18.s

1 ↗

(On Diff #296166)

Had a look at icf-non-mergeable.s which checks for no merging, so decided just to rename to icf-ineligible.s. Hope that's OK.

[andrewng]

In D88830#2313269, @MaskRay wrote:

The description can be shortened a bit. The important part is that variableEq returns false if two relocations reference a pair of aliased symbols in an ineligible section.

Actually, the key difference in this patch is that variableEq returns true for two relocations to a pair of "aliased" symbols that reference the same section which is ineligible for ICF. This patch actually came about from the investigation into the ICF link performance issue with objects compiled with -fprofile-instr-generate. It was during this investigation that I noticed some of these shortcomings.

[MaskRay]

lld/ELF/ICF.cpp

226

How about making uniqueId in the main function start from inputSections.size(). The variable eqClassBase can be avoided.

There is a gap between used values but that is not a problem: [0, sections.size()) ... [inputSections.size(), inputSections.size()+sections.size())

lld/test/ELF/icf-ineligible.s

2

You can delete icf-non-mergeable.s by adding some lines to this file.

[andrewng]

lld/ELF/ICF.cpp

226

I did consider this, but I thought it would be better to not have the gap, particularly as eqClass is "only" 32-bit. Also having unqueId start from a higher value, brings it closer to hash collisions given the current code which sets the MSB to avoid such collisions. It's unlikely that this is going to make a practical difference, but it just feels better. What are your thoughts?

Whilst on this topic, do you think we should add some checks for these "range" constraints (in separate patch)?

lld/test/ELF/icf-ineligible.s

2

I actually thought that keeping the tests separate would be better, as in the icf-non-mergable.s test no sections are merged where as this test is expecting all sections to merge. But if you want me to combine the tests, I can do that. If so, which test name would be your preference?

[andrewng]

Ping.

[MaskRay]

One last nit.

lld/ELF/ICF.cpp

227

Inline the variable eqClass

[andrewng]

lld/ELF/ICF.cpp

227

Just to clarify, you want me to replace eqClass with the expression eqClassBase + mid, i.e. bring the addition inside the for loop?

[MaskRay]

lld/ELF/ICF.cpp

227

Yes. This is optimizable by the compiler

[andrewng]

lld/ELF/ICF.cpp

227

OK, no problem, although I have to admit this goes against my instinctive coding approach. But I guess that might be because most projects with which I've been involved, have put at least some importance towards the run-time performance of unoptimized debug builds. But if this is the "LLVM" way, then so be it.

[grimar]

lld/ELF/ICF.cpp

227

OK, no problem, although I have to admit this goes against my instinctive coding approach.

FWIW I agree with it. I also prefer to precalculate values outside of the loop, it looks and reads cleaner usually.

But if this is the "LLVM" way, then so be it.

I don't think it is, I guess the idea was to get rid of a "excessive variable" to make the code a bit shorter.
I have no strong opinion about this particular place, because it is a very short/simple loop, though personally I would not do it too.

lld/ELF/ICF.cpp

 using namespace lld::elf;
 
 namespace {
 template <class ELFT> class ICF {
 public:
   void run();
 
 private:
-  void segregate(size_t begin, size_t end, bool constant);
+  void segregate(size_t begin, size_t end, uint32_t eqClassBase, bool constant);
 
   template <class RelTy>
   bool constantEq(const InputSection *a, ArrayRef<RelTy> relsA,
                   const InputSection *b, ArrayRef<RelTy> relsB);
 
   template <class RelTy>
   bool variableEq(const InputSection *a, ArrayRef<RelTy> relsA,
                   const InputSection *b, ArrayRef<RelTy> relsB);
static bool isEligible(InputSection *s) {
   if (isValidCIdentifier(s->name))
     return false;
 
   return true;
 }
 
 // Split an equivalence class into smaller classes.
 template <class ELFT>
-void ICF<ELFT>::segregate(size_t begin, size_t end, bool constant) {
+void ICF<ELFT>::segregate(size_t begin, size_t end, uint32_t eqClassBase,
+                          bool constant) {
   // This loop rearranges sections in [Begin, End) so that all sections
   // that are equal in terms of equals{Constant,Variable} are contiguous
   // in [Begin, End).
   //
   // The algorithm is quadratic in the worst case, but that is not an
   // issue in practice because the number of the distinct sections in
   // each range is usually very small.
 
   while (begin < end) {
     // Divide [Begin, End) into two. Let Mid be the start index of the
     // second group.
     auto bound =
         std::stable_partition(sections.begin() + begin + 1,
                               sections.begin() + end, [&](InputSection *s) {
                                 if (constant)
                                   return equalsConstant(sections[begin], s);
                                 return equalsVariable(sections[begin], s);
                               });
     size_t mid = bound - sections.begin();
 
     // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
-    // updating the sections in [Begin, Mid). We use Mid as an equivalence
-    // class ID because every group ends with a unique index.
+    // updating the sections in [Begin, Mid). We use Mid as the basis for
+    // the equivalence class ID because every group ends with a unique index.
+    // Add this to eqClassBase to avoid equality with unique IDs.
     for (size_t i = begin; i < mid; ++i)
-      sections[i]->eqClass[next] = mid;
+      sections[i]->eqClass[next] = eqClassBase + mid;
 
     // If we created a group, we need to iterate the main loop again.
     if (mid != end)
       repeat = true;
 
     begin = mid;
   }
 }
for (size_t i = 0; i < ra.size(); ++i) {
     // constantEq, and for InputSections we have already checked everything
     // except the equivalence class.
     if (!da->section)
       continue;
     auto *x = dyn_cast<InputSection>(da->section);
     if (!x)
       continue;
     auto *y = cast<InputSection>(db->section);
 
-    // Ineligible sections are in the special equivalence class 0.
-    // They can never be the same in terms of the equivalence class.
+    // Sections that are in the special equivalence class 0, can never be the
+    // same in terms of the equivalence class.
     if (x->eqClass[current] == 0)
       return false;
     if (x->eqClass[current] != y->eqClass[current])
       return false;
   };
 
   return true;
 }
static void combineRelocHashes(unsigned cnt, InputSection *isec,
                                ArrayRef<RelTy> rels) {
   uint32_t hash = isec->eqClass[cnt % 2];
   for (RelTy rel : rels) {
     Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel);
     if (auto *d = dyn_cast<Defined>(&s))
       if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
         hash += relSec->eqClass[cnt % 2];
   }
-  // Set MSB to 1 to avoid collisions with non-hash IDs.
+  // Set MSB to 1 to avoid collisions with unique IDs.
   isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
 }
 
 static void print(const Twine &s) {
   if (config->printIcfSections)
     message(s);
 }
 
template <class ELFT> void ICF<ELFT>::run() {
   // eligible. This is implemented by iterating over CIE/FDE and setting
   // eqClass[0] to the referenced text section from a live FDE.
   //
   // If two .gcc_except_table have identical semantics (usually identical
   // content with PC-relative encoding), we will lose folding opportunity.
   uint32_t uniqueId = 0;
   for (Partition &part : partitions)
     part.ehFrame->iterateFDEWithLSDA<ELFT>(
-        [&](InputSection &s) { s.eqClass[0] = ++uniqueId; });
+        [&](InputSection &s) { s.eqClass[0] = s.eqClass[1] = ++uniqueId; });
 
   // Collect sections to merge.
   for (InputSectionBase *sec : inputSections) {
     auto *s = cast<InputSection>(sec);
-    if (isEligible(s) && s->eqClass[0] == 0)
+    if (s->eqClass[0] == 0) {
+      if (isEligible(s))
         sections.push_back(s);
+      else
+        // Ineligible sections are assigned unique IDs, i.e. each section
+        // belongs to an equivalence class of its own.
+        s->eqClass[0] = s->eqClass[1] = ++uniqueId;
+    }
   }
 
   // Initially, we use hash values to partition sections.
-  parallelForEach(
-      sections, [&](InputSection *s) { s->eqClass[0] = xxHash64(s->data()); });
+  parallelForEach(sections, [&](InputSection *s) {
+    // Set MSB to 1 to avoid collisions with unique IDs.
+    s->eqClass[0] = xxHash64(s->data()) | (1U << 31);
+  });
 
   // Perform 2 rounds of relocation hash propagation. 2 is an empirical value to
   // reduce the average sizes of equivalence classes, i.e. segregate() which has
   // a large time complexity will have less work to do.
   for (unsigned cnt = 0; cnt != 2; ++cnt) {
     parallelForEach(sections, [&](InputSection *s) {
       if (s->areRelocsRela)
         combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
       else
         combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
     });
   }
 
   // From now on, sections in Sections vector are ordered so that sections
   // in the same equivalence class are consecutive in the vector.
   llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
     return a->eqClass[0] < b->eqClass[0];
   });
 
-  // Compare static contents and assign unique IDs for each static content.
-  forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
+  // Compare static contents and assign unique equivalence class IDs for each
+  // static content. Use a base offset for these IDs to ensure no overlap with
+  // the unique IDs already assigned.
+  uint32_t eqClassBase = ++uniqueId;
+  forEachClass([&](size_t begin, size_t end) {
+    segregate(begin, end, eqClassBase, true);
+  });
 
   // Split groups by comparing relocations until convergence is obtained.
   do {
     repeat = false;
-    forEachClass(
-        [&](size_t begin, size_t end) { segregate(begin, end, false); });
+    forEachClass([&](size_t begin, size_t end) {
+      segregate(begin, end, eqClassBase, false);
+    });
   } 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;

lld/test/ELF/icf-ineligible.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: ld.lld %t.o -o /dev/null --keep-unique fu --icf=all --print-icf-sections | FileCheck %s
+
+## Check that ICF is able to merge equivalent sections with relocations to
+## different symbols, e.g. aliases, that refer to the same section which is
+## ineligible for ICF.
+
+# CHECK: selected section {{.*}}:(.text.f1)
+# CHECK:   removing identical section {{.*}}:(.text.f2)
+# CHECK:   removing identical section {{.*}}:(.text.f3)
+# CHECK: selected section {{.*}}:(.text.f4)
+# CHECK:   removing identical section {{.*}}:(.text.f5)
+
+.globl d, d_alias, fu, f1, f2, f3, f4, f5
+
+.section .data.d,"aw",@progbits
+d:
+d_alias:
+.long 42
+
+.section .text.fu,"ax",@progbits
+fu:
+  nop
+
+.section .text.f1,"ax",@progbits
+f1:
+.quad d
+
+.section .text.f2,"ax",@progbits
+f2:
+.quad d_alias
+
+.section .text.f3,"ax",@progbits
+f3:
+.quad .data.d
+
+.section .text.f4,"ax",@progbits
+f4:
+.quad fu
+
+.section .text.f5,"ax",@progbits
+f5:
+.quad .text.fu