[lld-macho] Switch to xxh3_64bits

[MaskRay]

Summary

xxh3 is substantially faster than xxh64.
For lld/ELF, there is substantial speedup in .debug_str duplicate
elimination (D154813). Use xxh3 for lld-macho as well.

[oontvoo]

LG!

lld/MachO/ICF.cpp

if (isFoldable) {
       // unique ID to everything else.
       isec->icfEqClass[0] = ++icfUniqueID;
     }
   }
   parallelForEach(foldable, [](ConcatInputSection *isec) {
     assert(isec->icfEqClass[0] == 0); // don't overwrite a unique ID!
     // Turn-on the top bit to guarantee that valid hashes have no collisions
     // with the small-integer unique IDs for ICF-ineligible sections
-    isec->icfEqClass[0] = xxHash64(isec->data) | (1ull << 31);
+    isec->icfEqClass[0] = xxh3_64bits(isec->data) | (1ull << 31);
   });
   // Now that every input section is either hashed or marked as unique, run the
   // segregation algorithm to detect foldable subsections.
   ICF(foldable).run();
 }

lld/MachO/InputSection.cpp

 
 void CStringInputSection::splitIntoPieces() {
   size_t off = 0;
   StringRef s = toStringRef(data);
   while (!s.empty()) {
     size_t end = s.find(0);
     if (end == StringRef::npos)
       fatal(getLocation(off) + ": string is not null terminated");
-    uint32_t hash = deduplicateLiterals ? xxHash64(s.take_front(end)) : 0;
+    uint32_t hash = deduplicateLiterals ? xxh3_64bits(s.take_front(end)) : 0;
     pieces.emplace_back(off, hash);
     size_t size = end + 1; // include null terminator
     s = s.substr(size);
     off += size;
   }
 }
 
 StringPiece &CStringInputSection::getStringPiece(uint64_t off) {

lld/MachO/SyntheticSections.cpp

for (const auto &p : stringOffsetMap) {
     if (!data.empty())
       memcpy(buf + off, data.data(), data.size());
   }
 }
 
 DeduplicatedCStringSection::StringOffset
 DeduplicatedCStringSection::getStringOffset(StringRef str) const {
   // StringPiece uses 31 bits to store the hashes, so we replicate that
-  uint32_t hash = xxHash64(str) & 0x7fffffff;
+  uint32_t hash = xxh3_64bits(str) & 0x7fffffff;
   auto offset = stringOffsetMap.find(CachedHashStringRef(str, hash));
   assert(offset != stringOffsetMap.end() &&
          "Looked-up strings should always exist in section");
   return offset->second;
 }
 
 // This section is actually emitted as __TEXT,__const by ld64, but clang may
 // emit input sections of that name, and LLD doesn't currently support mixing

lld/MachO/Writer.cpp

void Writer::writeUuid() {
   size_t chunkSize = (data.size() + chunkCount - 1) / chunkCount;
   std::vector<ArrayRef<uint8_t>> chunks = split(data, chunkSize);
   // Leave one slot for filename
   std::vector<uint64_t> hashes(chunks.size() + 1);
   SmallVector<std::shared_future<void>> threadFutures;
   threadFutures.reserve(chunks.size());
   for (size_t i = 0; i < chunks.size(); ++i)
     threadFutures.emplace_back(threadPool.async(
-        [&](size_t j) { hashes[j] = xxHash64(chunks[j]); }, i));
+        [&](size_t j) { hashes[j] = xxh3_64bits(chunks[j]); }, i));
   for (std::shared_future<void> &future : threadFutures)
     future.wait();
   // Append the output filename so that identical binaries with different names
   // don't get the same UUID.
-  hashes[chunks.size()] = xxHash64(sys::path::filename(config->finalOutput));
-  uint64_t digest = xxHash64({reinterpret_cast<uint8_t *>(hashes.data()),
+  hashes[chunks.size()] = xxh3_64bits(sys::path::filename(config->finalOutput));
+  uint64_t digest = xxh3_64bits({reinterpret_cast<uint8_t *>(hashes.data()),
                                  hashes.size() * sizeof(uint64_t)});
   uuidCommand->writeUuid(digest);
 }
 
 // This is step 5 of the algorithm described in the class comment of
 // ChainedFixupsSection.
 void Writer::buildFixupChains() {
   if (!config->emitChainedFixups)
     return;