ELF: Make --print-icf-sections output deterministic.

[pcc]

Summary

The icf-safe.s test currently fails on 32-bit platforms because it uses
the --print-icf-sections flag and depends on the output appearing in
a specific order. However, this flag causes the output to depend on
the order of the sections in the Sections array, which depends on the
hash values returned from hash_combine, which happen to be different
for that test between 32-bit and 64-bit platforms.

This change makes the output deterministic by textually sorting the
printed messages.

[ruiu]

I think we should use a deterministic hash function such as xxHash64 instead of hash_combine to fix this issue, as I believe it's easier and more robust.

[pcc]

In D49877#1177432, @ruiu wrote:

I think we should use a deterministic hash function such as xxHash64 instead of hash_combine to fix this issue, as I believe it's easier and more robust.

So hashing the section contents instead of contents + flags etc like we're currently doing? Seems reasonable, I'll give that a try.

[ruiu]

If there's an easy way of mixing flags and other info to a hash value of contents, I think there's no reason not to do that, but perhaps just hashing contents is enough.

[pcc]

• Switch to xxhash

[ruiu]

LGTM

[pcc]

I suspect that we aren't gaining much from the flags/relocation count/section size because all of these properties typically depend on the section contents anyway, so I left them out.

lld/trunk/ELF/ICF.cpp

 
 #include "ICF.h"
 #include "Config.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Writer.h"
 #include "lld/Common/Threads.h"
-#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Object/ELF.h"
+#include "llvm/Support/xxhash.h"
 #include <algorithm>
 #include <atomic>
 
 using namespace lld;
 using namespace lld::elf;
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
private:
   // because we can safely read the next class without worrying about race
   // conditions. Using the same location makes this algorithm converge
   // faster because it uses results of the same iteration earlier.
   int Current = 0;
   int Next = 0;
 };
 }
 
-// Returns a hash value for S. Note that the information about
-// relocation targets is not included in the hash value.
-template <class ELFT> static uint32_t getHash(InputSection *S) {
-  return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
-}
-
 // Returns true if section S is subject of ICF.
 static bool isEligible(InputSection *S) {
   if (!S->Live || S->KeepUnique || !(S->Flags & SHF_ALLOC))
     return false;
 
   // Don't merge writable sections. .data.rel.ro sections are marked as writable
   // but are semantically read-only.
   if ((S->Flags & SHF_WRITE) && S->Name != ".data.rel.ro" &&
template <class ELFT> void ICF<ELFT>::run() {
   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] = getHash<ELFT>(S) | (1U << 31);
+    S->Class[0] = xxHash64(toStringRef(S->Data)) | (1U << 31);
   });
 
   // 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];
                    });

lld/trunk/test/ELF/icf-safe.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
 # RUN: llvm-objcopy %t1.o %t1copy.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/icf-safe.s -o %t2.o
 # RUN: ld.lld %t1.o %t2.o -o %t2 --icf=safe --print-icf-sections | FileCheck %s
 # RUN: ld.lld %t1.o %t2.o -o %t3 --icf=safe --print-icf-sections -shared | FileCheck --check-prefix=EXPORT %s
 # RUN: ld.lld %t1.o %t2.o -o %t3 --icf=safe --print-icf-sections --export-dynamic | FileCheck --check-prefix=EXPORT %s
 # RUN: ld.lld %t1.o %t2.o -o %t2 --icf=all --print-icf-sections | FileCheck --check-prefix=ALL %s
 # RUN: ld.lld %t1.o %t2.o -o %t2 --icf=all --print-icf-sections --export-dynamic | FileCheck --check-prefix=ALL-EXPORT %s
 # RUN: ld.lld %t1copy.o -o %t4 --icf=safe 2>&1 | FileCheck --check-prefix=OBJCOPY %s
 
-# CHECK-NOT: selected section {{.*}}:(.rodata.l1)
-# CHECK: selected section {{.*}}:(.rodata.l3)
-# CHECK:   removing identical section {{.*}}:(.rodata.l4)
-
 # CHECK-NOT: selected section {{.*}}:(.text.f1)
 # CHECK: selected section {{.*}}:(.text.f3)
 # CHECK:   removing identical section {{.*}}:(.text.f4)
 
 # CHECK-NOT: selected section {{.*}}:(.rodata.h1)
 # CHECK: selected section {{.*}}:(.rodata.h3)
 # CHECK:   removing identical section {{.*}}:(.rodata.h4)
 
+# CHECK-NOT: selected section {{.*}}:(.rodata.l1)
+# CHECK: selected section {{.*}}:(.rodata.l3)
+# CHECK:   removing identical section {{.*}}:(.rodata.l4)
+
 # CHECK-NOT: selected section {{.*}}:(.rodata.g1)
 # CHECK: selected section {{.*}}:(.rodata.g3)
 # CHECK:   removing identical section {{.*}}:(.rodata.g4)
 
 # CHECK-NOT: selected section {{.*}}:(.text.non_addrsig{{.}})
 
 # With --icf=all address-significance implies keep-unique only for rodata, not
 # text.
-# ALL-NOT: selected section {{.*}}:(.rodata.l1)
-# ALL: selected section {{.*}}:(.rodata.l3)
-# ALL:   removing identical section {{.*}}:(.rodata.l4)
-
 # ALL: selected section {{.*}}:(.text.f3)
 # ALL:   removing identical section {{.*}}:(.text.f4)
 
+# ALL-NOT: selected section {{.*}}:(.rodata.h1)
+# ALL: selected section {{.*}}:(.rodata.h3)
+# ALL:   removing identical section {{.*}}:(.rodata.h4)
+
 # ALL: selected section {{.*}}:(.text.f1)
 # ALL:   removing identical section {{.*}}:(.text.f2)
 # ALL:   removing identical section {{.*}}:(.text.non_addrsig1)
 # ALL:   removing identical section {{.*}}:(.text.non_addrsig2)
 
-# ALL-NOT: selected section {{.*}}:(.rodata.h1)
-# ALL: selected section {{.*}}:(.rodata.h3)
-# ALL:   removing identical section {{.*}}:(.rodata.h4)
+# ALL-NOT: selected section {{.*}}:(.rodata.l1)
+# ALL: selected section {{.*}}:(.rodata.l3)
+# ALL:   removing identical section {{.*}}:(.rodata.l4)
 
 # ALL-NOT: selected section {{.*}}:(.rodata.g1)
 # ALL: selected section {{.*}}:(.rodata.g3)
 # ALL:   removing identical section {{.*}}:(.rodata.g4)
 
 # llvm-mc normally emits an empty .text section into every object file. Since
 # nothing actually refers to it via a relocation, it doesn't have any associated
 # symbols (thus nor can anything refer to it via a relocation, making it safe to
 # merge with the empty section in the other input file). Here we check that the
 # only two sections merged are the two empty sections and the sections with only
 # STB_LOCAL or STV_HIDDEN symbols. The dynsym entries should have prevented
 # anything else from being merged.
 # EXPORT-NOT: selected section
-# EXPORT: selected section {{.*}}:(.rodata.l3)
-# EXPORT:   removing identical section {{.*}}:(.rodata.l4)
-# EXPORT-NOT: selected section
 # EXPORT: selected section {{.*}}:(.rodata.h3)
 # EXPORT:   removing identical section {{.*}}:(.rodata.h4)
 # EXPORT-NOT: selected section
 # EXPORT: selected section {{.*}}:(.text)
 # EXPORT:   removing identical section {{.*}}:(.text)
 # EXPORT-NOT: selected section
+# EXPORT: selected section {{.*}}:(.rodata.l3)
+# EXPORT:   removing identical section {{.*}}:(.rodata.l4)
+# EXPORT-NOT: selected section
 
 # If --icf=all is specified when exporting we can also merge the exported text
 # sections, but not the exported rodata.
 # ALL-EXPORT-NOT: selected section
-# ALL-EXPORT: selected section {{.*}}:(.rodata.l3)
-# ALL-EXPORT:   removing identical section {{.*}}:(.rodata.l4)
-# ALL-EXPORT-NOT: selected section
 # ALL-EXPORT: selected section {{.*}}:(.text.f3)
 # ALL-EXPORT:   removing identical section {{.*}}:(.text.f4)
 # ALL-EXPORT-NOT: selected section
+# ALL-EXPORT: selected section {{.*}}:(.rodata.h3)
+# ALL-EXPORT:   removing identical section {{.*}}:(.rodata.h4)
+# ALL-EXPORT-NOT: selected section
 # ALL-EXPORT: selected section {{.*}}:(.text.f1)
 # ALL-EXPORT:   removing identical section {{.*}}:(.text.f2)
 # ALL-EXPORT:   removing identical section {{.*}}:(.text.non_addrsig1)
 # ALL-EXPORT:   removing identical section {{.*}}:(.text.non_addrsig2)
 # ALL-EXPORT-NOT: selected section
-# ALL-EXPORT: selected section {{.*}}:(.rodata.h3)
-# ALL-EXPORT:   removing identical section {{.*}}:(.rodata.h4)
-# ALL-EXPORT-NOT: selected section
 # ALL-EXPORT: selected section {{.*}}:(.text)
 # ALL-EXPORT:   removing identical section {{.*}}:(.text)
 # ALL-EXPORT-NOT: selected section
+# ALL-EXPORT: selected section {{.*}}:(.rodata.l3)
+# ALL-EXPORT:   removing identical section {{.*}}:(.rodata.l4)
+# ALL-EXPORT-NOT: selected section
 
 # OBJCOPY: --icf=safe is incompatible with object files created using objcopy or ld -r
 
 .section .text.f1,"ax",@progbits
 .globl f1
 f1:
 ret