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

[pcc]

Summary

On my machine this reduced median link time of lld-speed-test/chrome
from 2.68s to 2.41s. It also reduces link time of Chrome for Android
with a prototype compiler change that causes the compiler to create
large numbers of identical (modulo relocations) sections from >15
minutes to a few seconds.

[grimar]

This LGTM. Please wait for Rui's opinion too.

[ruiu]

LGTM. Thanks!

ELF/ICF.cpp

private:
 
   size_t findBoundary(size_t Begin, size_t End);
 
   void forEachClassRange(size_t Begin, size_t End,
                          llvm::function_ref<void(size_t, size_t)> Fn);
 
   void forEachClass(llvm::function_ref<void(size_t, size_t)> Fn);
 
+  template <class RelTy>
+  void combineRelocHashes(InputSection *IS, ArrayRef<RelTy> Rels);
+
   std::vector<InputSection *> Sections;
 
   // We repeat the main loop while `Repeat` is true.
   std::atomic<bool> Repeat;
 
   // The main loop counter.
   int Cnt = 0;
 
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> Fn) {
 
   parallelForEachN(1, NumShards + 1, [&](size_t I) {
     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>
+template <class RelTy>
+void ICF<ELFT>::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))
+        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);
 }
 
 // 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) {
-    // Set MSB to 1 to avoid collisions with non-hash IDs.
-    S->Class[0] = xxHash64(S->data()) | (1U << 31);
+    S->Class[1] = xxHash64(S->data());
+  });
+
+  parallelForEach(Sections, [&](InputSection *S) {
+    if (S->AreRelocsRela)
+      combineRelocHashes(S, S->template relas<ELFT>());
+    else
+      combineRelocHashes(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];
                    });