COFF, ELF: ICF: Perform 2 rounds of relocation hash propagation.

[pcc]

Summary

LLD's performance on PGO instrumented Windows binaries was still not
great even with the fix in D56955; out of the 2m41s linker runtime,
around 2 minutes were still being spent in ICF. I looked into this more
closely and discovered that the vast majority of the runtime was being
spent segregating .pdata sections with the following relocation chain:

.pdata -> identical .text -> unique PGO counter (not eligible for ICF)

This patch causes us to perform 2 rounds of relocation hash
propagation, which allows the hash for the .pdata sections to
incorporate the identifier from the PGO counter. With that, the amount
of time spent in ICF was reduced to about 2 seconds. I also found that
the same change led to a significant ICF performance improvement in a
regular release build of Chromium's chrome_child.dll, where ICF time
was reduced from around 1s to around 700ms.

With the same change applied to the ELF linker, median of 100 runs
for lld-speed-test/chrome reduced from 4.53s to 4.45s on my machine.

I also experimented with increasing the number of propagation rounds
further, but I did not observe any further significant performance
improvements linking Chromium or Firefox.

[smeenai]

Is this worth picking over to 8.0 after it lands?

[pcc]

In D56986#1366859, @smeenai wrote:

Is this worth picking over to 8.0 after it lands?

I'm more ambivalent about this one since it's more of a perf improvement than a fix for a perf regression like D56955 is. But I have no strong objections to doing so.

[smeenai]

In D56986#1366874, @pcc wrote:

In D56986#1366859, @smeenai wrote:

Is this worth picking over to 8.0 after it lands?

I'm more ambivalent about this one since it's more of a perf improvement than a fix for a perf regression like D56955 is. But I have no strong objections to doing so.

That's fair; we can just cherry-pick it to our 8.0 branch internally if it doesn't end up merged here :) It's early in the release cycle though, so I figured it was okay for small-ish changes like this which result in big improvements to go in.

[rnk]

lgtm, nice!

[dmajor]

In D56986#1366881, @smeenai wrote:

In D56986#1366874, @pcc wrote:

In D56986#1366859, @smeenai wrote:

Is this worth picking over to 8.0 after it lands?

I'm more ambivalent about this one since it's more of a perf improvement than a fix for a perf regression like D56955 is. But I have no strong objections to doing so.

That's fair; we can just cherry-pick it to our 8.0 branch internally if it doesn't end up merged here :) It's early in the release cycle though, so I figured it was okay for small-ish changes like this which result in big improvements to go in.

FWIW I was hoping to see this be merged to 8.0 as well.

[pcc]

In D56986#1366939, @dmajor wrote:

In D56986#1366881, @smeenai wrote:

In D56986#1366874, @pcc wrote:

In D56986#1366859, @smeenai wrote:

Is this worth picking over to 8.0 after it lands?

I'm more ambivalent about this one since it's more of a perf improvement than a fix for a perf regression like D56955 is. But I have no strong objections to doing so.

That's fair; we can just cherry-pick it to our 8.0 branch internally if it doesn't end up merged here :) It's early in the release cycle though, so I figured it was okay for small-ish changes like this which result in big improvements to go in.

FWIW I was hoping to see this be merged to 8.0 as well.

Okay, let's go for it.

[pcc]

Merge requested in PR40416.

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.
   parallelForEach(Chunks, [&](SectionChunk *SC) {
-    SC->Class[1] = xxHash64(SC->getContents());
+    SC->Class[0] = xxHash64(SC->getContents());
   });
 
   // Combine the hashes of the sections referenced by each section into its
   // hash.
+  for (unsigned Cnt = 0; Cnt != 2; ++Cnt) {
     parallelForEach(Chunks, [&](SectionChunk *SC) {
-    uint32_t Hash = SC->Class[1];
+      uint32_t Hash = SC->Class[Cnt % 2];
       for (Symbol *B : SC->symbols())
         if (auto *Sym = dyn_cast_or_null<DefinedRegular>(B))
-        Hash += Sym->getChunk()->Class[1];
+          Hash += Sym->getChunk()->Class[Cnt % 2];
       // Set MSB to 1 to avoid collisions with non-hash classs.
-    SC->Class[0] = Hash | (1U << 31);
+      SC->Class[(Cnt + 1) % 2] = 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];
                    });
 

lld/trunk/ELF/ICF.cpp

if (Boundaries[I - 1] < Boundaries[I])
       forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
   });
   ++Cnt;
 }
 
 // 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];
+static void combineRelocHashes(unsigned Cnt, InputSection *IS,
+                               ArrayRef<RelTy> Rels) {
+  uint32_t Hash = IS->Class[Cnt % 2];
   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))
-        Hash += RelSec->Class[1];
+        Hash += RelSec->Class[Cnt % 2];
   }
   // Set MSB to 1 to avoid collisions with non-hash IDs.
-  IS->Class[0] = Hash | (1U << 31);
+  IS->Class[(Cnt + 1) % 2] = Hash | (1U << 31);
 }
 
 static void print(const Twine &S) {
   if (Config->PrintIcfSections)
     message(S);
 }
 
 // The main function of ICF.
 template <class ELFT> void ICF<ELFT>::run() {
   // Collect sections to merge.
   for (InputSectionBase *Sec : InputSections)
     if (auto *S = dyn_cast<InputSection>(Sec))
       if (isEligible(S))
         Sections.push_back(S);
 
   // Initially, we use hash values to partition sections.
   parallelForEach(Sections, [&](InputSection *S) {
-    S->Class[1] = xxHash64(S->data());
+    S->Class[0] = xxHash64(S->data());
   });
 
+  for (unsigned Cnt = 0; Cnt != 2; ++Cnt) {
     parallelForEach(Sections, [&](InputSection *S) {
       if (S->AreRelocsRela)
-      combineRelocHashes<ELFT>(S, S->template relas<ELFT>());
+        combineRelocHashes<ELFT>(Cnt, S, S->template relas<ELFT>());
       else
-      combineRelocHashes<ELFT>(S, S->template rels<ELFT>());
+        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.
   std::stable_sort(Sections.begin(), Sections.end(),
                    [](InputSection *A, InputSection *B) {
                      return A->Class[0] < B->Class[0];
                    });