[ELF] Use llvm::xxh3_64bits for MergeInputSection::splitStrings

[MaskRay]

Summary

See D154812 for the speedup.

[MaskRay]

MergeInputSection::splitNonStrings requires fixing 6 more tests. I haven't done that in this patch. I'll do that after this patch lands. MergeInputSection::splitNonStrings takes negligible time (output .rodata.cst4 is just 0x11c bytes) compared with MergeInputSection::splitStrings

[PiotrZSL]

Looks like dependency between patches is not set, and thats why build fails with 'error C3861: 'xxh3_64bits': identifier not found'

[PiotrZSL]

LGTM, but probably someone else should look into this also.

[MaskRay]

In D154813#4511058, @PiotrZSL wrote:

LGTM, but probably someone else should look into this also.

Thank you! I think this is a non-controversial change. The benefit for Linux x86-64 can be "significant" (e.g., 2%).
I am a primary maintainer of lld/ELF and I'll land this soon before the release/17.x branch...

lld/ELF/InputSection.cpp

void MergeInputSection::splitStrings(StringRef s, size_t entSize) {
   const bool live = !(flags & SHF_ALLOC) || !config->gcSections;
   const char *p = s.data(), *end = s.data() + s.size();
   if (!std::all_of(end - entSize, end, [](char c) { return c == 0; }))
     fatal(toString(this) + ": string is not null terminated");
   if (entSize == 1) {
     // Optimize the common case.
     do {
       size_t size = strlen(p);
-      pieces.emplace_back(p - s.begin(), xxHash64(StringRef(p, size)), live);
+      pieces.emplace_back(p - s.begin(), xxh3_64bits(StringRef(p, size)), live);
       p += size + 1;
     } while (p != end);
   } else {
     do {
       size_t size = findNull(StringRef(p, end - p), entSize);
-      pieces.emplace_back(p - s.begin(), xxHash64(StringRef(p, size)), live);
+      pieces.emplace_back(p - s.begin(), xxh3_64bits(StringRef(p, size)), live);
       p += size + entSize;
     } while (p != end);
   }
 }
 
 // Split non-SHF_STRINGS section. Such section is a sequence of
 // fixed size records.
 void MergeInputSection::splitNonStrings(ArrayRef<uint8_t> data,

lld/test/ELF/comment-gc.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/comment-gc.s -o %t2.o
 # RUN: ld.lld %t.o %t2.o -o %t1 --gc-sections -shared
 # RUN: llvm-objdump -s %t1 | FileCheck %s
 
 # CHECK:      Contents of section .comment:
-# CHECK-NEXT: .LLD 1.0.foo.bar
+# CHECK-NEXT: foo..LLD 1.0.bar
+# CHECK-NEXT: .{{$}}
 
 .ident "foo"
 
 .globl _start
 _start:
   nop

lld/test/ELF/compress-debug-sections-zstd.s

 # REQUIRES: x86, zstd
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64 --compress-debug-sections=zstd %s -o %t.o
 
 # RUN: ld.lld %t.o -o %t.so -shared
 # RUN: llvm-readelf -S -x .debug_str %t.so | FileCheck %s
 
 # CHECK:      .debug_str    PROGBITS [[#%x,]] [[#%x,]] [[#%x,]] 01 MS  0 0  1
 # CHECK:      Hex dump of section '.debug_str':
-# CHECK-NEXT: 0x00000000 756e7369 676e6564 20696e74 00636861 unsigned int.cha
-# CHECK-NEXT: 0x00000010 7200756e 7369676e 65642063 68617200 r.unsigned char.
-# CHECK-NEXT: 0x00000020 73686f72 7420756e 7369676e 65642069 short unsigned i
-# CHECK-NEXT: 0x00000030 6e74006c 6f6e6720 756e7369 676e6564 nt.long unsigned
+# CHECK-NEXT: 0x00000000 73686f72 7420756e 7369676e 65642069 short unsigned i
+# CHECK-NEXT: 0x00000010 6e740075 6e736967 6e656420 63686172 nt.unsigned char
+# CHECK-NEXT: 0x00000020 00636861 72006c6f 6e672075 6e736967 .char.long unsig
+# CHECK-NEXT: 0x00000030 6e656420 696e7400 756e7369 676e6564 ned int.unsigned
 # CHECK-NEXT: 0x00000040 20696e74 00                          int.
 
 # RUN: ld.lld %t.o -o %t.so -shared --compress-debug-sections=zstd
 # RUN: llvm-readelf -S %t.so | FileCheck %s --check-prefix=OUTPUT-SEC
 # RUN: llvm-objcopy --decompress-debug-sections %t.so
 # RUN: llvm-readelf -S -x .debug_str %t.so | FileCheck %s
 
 # OUTPUT-SEC: .debug_str    PROGBITS [[#%x,]] [[#%x,]] [[#%x,]] 01 MSC 0 0  1

lld/test/ELF/compressed-debug-input.s

 # DATA-NEXT:   Address: 0x0
 # DATA-NEXT:   Offset:
 # DATA-NEXT:   Size: 69
 # DATA-NEXT:   Link: 0
 # DATA-NEXT:   Info: 0
 # DATA-NEXT:   AddressAlignment: 1
 # DATA-NEXT:   EntrySize: 1
 # DATA-NEXT:   SectionData (
-# DATA-NEXT:     0000: 756E7369 676E6564 20696E74 00636861  |unsigned int.cha|
-# DATA-NEXT:     0010: 7200756E 7369676E 65642063 68617200  |r.unsigned char.|
-# DATA-NEXT:     0020: 73686F72 7420756E 7369676E 65642069  |short unsigned i|
-# DATA-NEXT:     0030: 6E74006C 6F6E6720 756E7369 676E6564  |nt.long unsigned|
+# DATA-NEXT:     0000: 73686F72 7420756E 7369676E 65642069  |short unsigned i|
+# DATA-NEXT:     0010: 6E740075 6E736967 6E656420 63686172  |nt.unsigned char|
+# DATA-NEXT:     0020: 00636861 72006C6F 6E672075 6E736967  |.char.long unsig|
+# DATA-NEXT:     0030: 6E656420 696E7400 756E7369 676E6564  |ned int.unsigned|
 # DATA-NEXT:     0040: 20696E74 00                          | int.|
 # DATA-NEXT:   )
 # DATA-NEXT: }
 
 .section .debug_str,"MS",@progbits,1
 .LASF2:
  .string "short unsigned int"
 .LASF3:
  .string "unsigned int"
 .LASF0:
  .string "long unsigned int"
 .LASF8:
  .string "char"
 .LASF1:
  .string "unsigned char"

lld/test/ELF/gc-sections-string.s

 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local (0x0)
 // CHECK-NEXT:     Type: None (0x0)
 // CHECK-NEXT:     Other: 0
 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
 // CHECK-NEXT:     Name: s3
-// CHECK-NEXT:     Value: 0x200120
+// CHECK-NEXT:     Value: 0x200125
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local (0x0)
 // CHECK-NEXT:     Type: Object (0x1)
 // CHECK-NEXT:     Other: 0
 // CHECK-NEXT:     Section: .rodata (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
 // CHECK-NEXT:     Name: s1
-// CHECK-NEXT:     Value: 0x200125
+// CHECK-NEXT:     Value: 0x200120
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local (0x0)
 // CHECK-NEXT:     Type: Object (0x1)
 // CHECK-NEXT:     Other [ (0x2)
 // CHECK-NEXT:       STV_HIDDEN (0x2)
 // CHECK-NEXT:     ]
 // CHECK-NEXT:     Section: .rodata (0x1)
 // CHECK-NEXT:   }