COFF, ELF: Adjust ICF hash computation to account for self relocations.

[pcc]

Summary

It turns out that sections in PGO instrumented object files on Windows
contain a large number of relocations pointing to themselves. With
r347429 this can cause many sections to receive the same hash (usually
zero) as a result of a section's hash being xor'ed with itself.

This patch causes the COFF and ELF linkers to avoid this problem
by adding the hash of the relocated section instead of xor'ing it.
On my machine this causes the regressing test case
provided by Mozilla to terminate in 2m41s.

[grimar]

I think this is OK. Please wait for Rui's opinion.

[smeenai]

When this lands, is it worth cherry-picking to 8.0?

[pcc]

In D56955#1366854, @smeenai wrote:

When this lands, is it worth cherry-picking to 8.0?

Yes, that's what my plan was.

[ruiu]

Or maybe we can simply add hashes instead of xor'ing?

[pcc]

In D56955#1366983, @ruiu wrote:

Or maybe we can simply add hashes instead of xor'ing?

Yeah, that could work too. Although my first thought was that combining hashes that way could end up losing entropy, it doesn't seem like we'd be losing too much in practice because if you have (say) 31 self relocations you would only end up losing 5 bits of entropy,. I'll do an experiment to see how well that works.

[pcc]

• Add instead of xoring

[pcc]

Done. Benchmark numbers appear the same for Chrome and Firefox (including with D56986, which would mean losing twice as much entropy (I think)).

[ruiu]

LGTM

[pcc]

Merge requested in PR40416.

lld/COFF/ICF.cpp

void ICF::run(ArrayRef<Chunk *> Vec) {
   parallelForEach(Chunks, [&](SectionChunk *SC) {
     SC->Class[1] = xxHash64(SC->getContents());
   });
 
   // Combine the hashes of the sections referenced by each section into its
   // hash.
   parallelForEach(Chunks, [&](SectionChunk *SC) {
     uint32_t Hash = SC->Class[1];
-    for (Symbol *B : SC->symbols())
-      if (auto *Sym = dyn_cast_or_null<DefinedRegular>(B))
+    for (Symbol *B : SC->symbols()) {
+      if (auto *Sym = dyn_cast_or_null<DefinedRegular>(B)) {
+        // Rotate the hash by 1 to prevent it from being cancelled out by a
+        // self-relocation.
+        Hash = (Hash << 1) | (Hash >> 31);
         Hash ^= Sym->getChunk()->Class[1];
+      }
+    }
     // Set MSB to 1 to avoid collisions with non-hash classs.
     SC->Class[0] = Hash | (1U << 31);
   });
 
   // From now on, sections in Chunks are ordered so that sections in
   // the same group are consecutive in the vector.
   std::stable_sort(Chunks.begin(), Chunks.end(),
                    [](SectionChunk *A, SectionChunk *B) {

lld/ELF/ICF.cpp

 
 // Combine the hashes of the sections referenced by the given section into its
 // hash.
 template <class ELFT, class RelTy>
 static void combineRelocHashes(InputSection *IS, ArrayRef<RelTy> Rels) {
   uint32_t Hash = IS->Class[1];
   for (RelTy Rel : Rels) {
     Symbol &S = IS->template getFile<ELFT>()->getRelocTargetSym(Rel);
-    if (auto *D = dyn_cast<Defined>(&S))
-      if (auto *RelSec = dyn_cast_or_null<InputSection>(D->Section))
+    if (auto *D = dyn_cast<Defined>(&S)) {
+      if (auto *RelSec = dyn_cast_or_null<InputSection>(D->Section)) {
+        // Rotate the hash by 1 to prevent it from being cancelled out by a
+        // self-relocation.
+        Hash = (Hash << 1) | (Hash >> 31);
         Hash ^= RelSec->Class[1];
       }
+    }
+  }
   // Set MSB to 1 to avoid collisions with non-hash IDs.
   IS->Class[0] = Hash | (1U << 31);
 }
 
 static void print(const Twine &S) {
   if (Config->PrintIcfSections)
     message(S);
 }