[LLD][ELF] Fix inconsistencies with ICF equality class

[andrewng]

Summary

There appears to be an inconsistent approach to the setting of the
InputSection eqClass in ICF which could cause incorrect equivalence
class equality.

It would appear that this has not caused any issues, but making it
consistent and therefore more deterministic feels safer.

[andrewng]

I may be missing something about how the ICF code works, but whilst looking at a separate ICF performance issue, I noticed these oddities in the code. I haven't actually seen any issues myself but reading through the code, it feels like there could be issues. Although I suspect they would be highly unlikely or perhaps not possible in actual practice.

[MaskRay]

lld/ELF/ICF.cpp

225

There is indeed one existing 1U << 31 ... but there is no accompanying & 0x7fffffff I would expect.. So I start to wonder its merit..

476

This is unneeded. combineRelocHashes updates eqClass[1]

[andrewng]

lld/ELF/ICF.cpp

225

Setting the MSB avoids this eqClass being equal to an eqClass that was initialized via uniqueId on line 476. This was one of my concerns regarding a possible incorrect equality. However, this all does assume that both the number of sections in sections and uniqueId are less than (1U << 31).

The setting of the MSB elsewhere is to avoid a hash collision which is probably useful but not as important.

476

AFAIK, combineRelocHashes only acts on sections and the sections that have had eqClass[0] assigned via uniqueId will not be in sections (see line 481).

[andrewng]

Abandoning due to lack of interest and in favour of D88830 which requires these changes.

lld/ELF/ICF.cpp

auto bound =
                               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.
+    // Set MSB to 1 to avoid equality with "unique" IDs.
+    uint32_t eqClass = mid | (1U << 31);
     for (size_t i = begin; i < mid; ++i)
-      sections[i]->eqClass[next] = mid;
+      sections[i]->eqClass[next] = eqClass;
 
     // If we created a group, we need to iterate the main loop again.
     if (mid != end)
       repeat = true;
 
     begin = mid;
   }
 }
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)
       sections.push_back(s);
   }
 
   // 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 non-hash 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>());