[ELF] Speed up SHF_MERGE|SHF_STRINGS split

[MaskRay]

Summary

Splitting SHF_MERGE|SHF_STRINGS with sh_entsize=1 is a bottleneck linking a
program with large .debug_str in -O1/-O2 mode. This patch picks up D45571 with
small changes to speed up splitting.
We could also use other algorithms like weakened poly1305 but I am unsure the complexity
justifies.

Old:

jq -r '.traceEvents[] | select(.name|startswith("Total")) | "\(.dur/1000000) \(.name)"'
4.45245 Total ExecuteLinker
4.446075 Total Link
2.896229 Total Merge/finalize input sections
0.768235 Total Write output file
0.220198 Total Parse input files

New:

3.659616 Total ExecuteLinker
3.653682 Total Link
2.15211 Total Merge/finalize input sections
0.775001 Total Write output file
0.22633 Total Parse input files

I have adjusted some tests to demonstrate the effects.
If accepted I'll fix all the remaining tests.

[MaskRay]

simplify

[MaskRay]

Pushed a simplified form. Computing length along with hash does not seem to improve performance.

lld/ELF/InputSection.h

public:
   SectionPiece *getSectionPiece(uint64_t offset);
   const SectionPiece *getSectionPiece(uint64_t offset) const {
     return const_cast<MergeInputSection *>(this)->getSectionPiece(offset);
   }
 
   SyntheticSection *getParent() const;
 
 private:
+  void splitStrings1(ArrayRef<uint8_t> a);
   void splitStrings(ArrayRef<uint8_t> a, size_t size);
   void splitNonStrings(ArrayRef<uint8_t> a, size_t size);
 };
 
 struct EhSectionPiece {
   EhSectionPiece(size_t off, InputSectionBase *sec, uint32_t size,
                  unsigned firstRelocation)
       : inputOff(off), sec(sec), size(size), firstRelocation(firstRelocation) {}

lld/ELF/InputSection.cpp

static size_t findNull(StringRef s, size_t entSize) {
   }
   return StringRef::npos;
 }
 
 SyntheticSection *MergeInputSection::getParent() const {
   return cast_or_null<SyntheticSection>(parent);
 }
 
+// Compute both string size and hash value.
+static inline std::pair<size_t, uint32_t> findSizeAndHash(StringRef s) {
+  const char *p = s.data(), *end = p + s.size();
+  uint64_t h = 5381;
+  for (; end - p >= 8; p += 8) {
+    const uint64_t word = read64le(p);
+    // Break if any byte is NUL.
+    if ((word - 0x0101010101010101) & ~word & 0x8080808080808080)
+      break;
+    // Similar to djb2 but applies to a 64-bit word.
+    h = h * 33 + word;
+  }
+
+  // Hash all bytes before the NUL byte in the original djb2 way.
+  for (; *p; p++)
+    h = h * 33 + *p;
+  return {p - s.data() + 1, uint32_t((h >> 32) ^ h)};
+}
+
+void MergeInputSection::splitStrings1(ArrayRef<uint8_t> a) {
+  if (a.empty() || a.back() != 0)
+    fatal(toString(this) + ": string is not null terminated");
+
+  size_t off = 0;
+  const bool live = !(flags & SHF_ALLOC) || !config->gcSections;
+  StringRef s = toStringRef(a);
+  while (!s.empty()) {
+    size_t size;
+    uint32_t hash;
+    std::tie(size, hash) = findSizeAndHash(s);
+    pieces.emplace_back(off, hash, live);
+    s = s.substr(size);
+    off += size;
+  }
+}
+
 // Split SHF_STRINGS section. Such section is a sequence of
 // null-terminated strings.
 void MergeInputSection::splitStrings(ArrayRef<uint8_t> data, size_t entSize) {
   size_t off = 0;
   const bool live = !(flags & SHF_ALLOC) || !config->gcSections;
   StringRef s = toStringRef(data);
 
   while (!s.empty()) {

 // that need to be linked. This is responsible to split section contents
 // into small chunks for further processing.
 //
 // Note that this function is called from parallelForEach. This must be
 // thread-safe (i.e. no memory allocation from the pools).
 void MergeInputSection::splitIntoPieces() {
   assert(pieces.empty());
 
-  if (flags & SHF_STRINGS)
-    splitStrings(data(), entsize);
-  else
+  if (!(flags & SHF_STRINGS))
     splitNonStrings(data(), entsize);
+  else if (entsize == 1)
+    splitStrings1(data());
+  else
+    splitStrings(data(), entsize);
 }
 
 SectionPiece *MergeInputSection::getSectionPiece(uint64_t offset) {
   if (this->data().size() <= offset)
     fatal(toString(this) + ": offset is outside the section");
 
   // If Offset is not at beginning of a section piece, it is not in the map.
   // In that case we need to  do a binary search of the original section piece vector.

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: foo..LLD 1.0.bar
+# CHECK-NEXT: .foo.bar.LLD 1.0{{$}}
 
 .ident "foo"
 
 .globl _start
 _start:
   nop

lld/test/ELF/debug-gc.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: ld.lld %t.o -o %t1 --gc-sections
 # RUN: llvm-objdump -s %t1 | FileCheck %s
 
 # CHECK:      Contents of section .debug_str:
-# CHECK-NEXT:  0000 41414100 43434300 42424200           AAA.CCC.BBB.
+# CHECK-NEXT:  0000 41414100 42424200 43434300           AAA.BBB.CCC.
 # CHECK:      Contents of section .foo:
 # CHECK-NEXT:  0000 2a000000
 # CHECK:      Contents of section .debug_info:
-# CHECK-NEXT:  0000 00000000 08000000
+# CHECK-NEXT:  0000 00000000 04000000 ........
 
 .globl _start
 _start:
 
 .section .debug_str,"MS",@progbits,1
 .Linfo_string0:
   .asciz "AAA"
 .Linfo_string1:

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:   }