COFF: ICF: Include contents of referenced sections in initial partitioning hash. NFCI.

[pcc]

Summary

Previously we were taking over 13 minutes to link Firefox's xul.dll
on ARM64; this reduces link time to around 18s on my machine.

The root cause of the problem was that all of the input .pdata sections
had the same unrelocated section data and therefore the same hash,
which made segregation quadratic in the number of .pdata sections. The
reason why we weren't observing this on other architectures was that
ARM has a different .pdata format. On non-ARM the format is (start
address, end address, .xdata), which caused the size of the function
to appear in the unrelocated section data where the end address field
is. However, the ARM format omits the end address field.

Fixes PR39667.

[rnk]

lgtm, I agree ICF will produce the same results if to do one level of symbol resolution when building a content hash.

[ruiu]

Very interesting. Maybe we should do the same thing for ELF?

[pcc]

In D54809#1308430, @ruiu wrote:

Very interesting. Maybe we should do the same thing for ELF?

D54773 :)

lld/trunk/COFF/ICF.cpp

void ICF::run(ArrayRef<Chunk *> Vec) {
   // Make sure that ICF doesn't merge sections that are being handled by string
   // tail merging.
   for (auto &P : MergeChunk::Instances)
     for (SectionChunk *SC : P.second->Sections)
       SC->Class[0] = NextId++;
 
   // Initially, we use hash values to partition sections.
   for_each(parallel::par, Chunks.begin(), Chunks.end(), [&](SectionChunk *SC) {
+    SC->Class[1] = xxHash64(SC->getContents());
+  });
+
+  // Combine the hashes of the sections referenced by each section into its
+  // hash.
+  for_each(parallel::par, Chunks.begin(), Chunks.end(), [&](SectionChunk *SC) {
+    uint32_t Hash = SC->Class[1];
+    for (Symbol *B : SC->symbols())
+      if (auto *Sym = dyn_cast_or_null<DefinedRegular>(B))
+        Hash ^= Sym->getChunk()->Class[1];
     // Set MSB to 1 to avoid collisions with non-hash classs.
-    SC->Class[0] = xxHash64(SC->getContents()) | (1 << 31);
+    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) {
                      return A->Class[0] < B->Class[0];
                    });