From a42b3bcae4ec4bb2fb9d6e5981f99cf853407b4b Mon Sep 17 00:00:00 2001
From: Rafael Espindola <rafael.espindola@gmail.com>
Date: Tue, 27 Sep 2016 16:43:49 +0000
Subject: [PATCH] Use xxhash for fast --build-id.

The speed improvements I got were:

firefox
  master 7.050784981
  patch  6.842361079 0.970439617353
chromium
  master 4.260626249
  patch  4.183148025 0.981815296749
chromium fast
  master 1.829028591
  patch  1.806439277 0.987649556649
the gold plugin
  master 0.336154128
  patch  0.331893374 0.987324998728
clang
  master 0.561869781
  patch  0.558640828 0.994253200458
llvm-as
  master 0.034025959
  patch  0.033984389 0.99877828572
the gold plugin fsds
  master 0.360710529
  patch  0.356483564 0.988281559145
clang fsds
  master 0.640518422
  patch  0.632329874 0.987215749432
llvm-as fsds
  master 0.031569416
  patch  0.030822055 0.976326423017
scylla
  master 3.154770529
  patch  3.11982016 0.988921422754

llvm-svn: 282505
---
 lld/ELF/OutputSections.cpp | 54 ++++------------------------------------------
 1 file changed, 4 insertions(+), 50 deletions(-)

diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index 039b047..7bc09ef 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -18,8 +18,9 @@
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
-#include "llvm/Support/SHA1.h"
 #include "llvm/Support/RandomNumberGenerator.h"
+#include "llvm/Support/SHA1.h"
+#include "llvm/Support/xxhash.h"
 
 using namespace llvm;
 using namespace llvm::dwarf;
@@ -1681,59 +1682,12 @@ template <class ELFT> void BuildIdSection<ELFT>::writeTo(uint8_t *Buf) {
   HashBuf = Buf + 16;
 }
 
-static uint64_t murmurHash64A(const void *Key, int Len) {
-  uint64_t Seed = 0;
-  const uint64_t M = 0xc6a4a7935bd1e995LLU;
-  const int R = 47;
-
-  uint64_t H = Seed ^ (Len * M);
-
-  const uint64_t *Data = (const uint64_t *)Key;
-  const uint64_t *End = Data + (Len / 8);
-
-  while (Data != End) {
-    uint64_t K = *Data++;
-
-    K *= M;
-    K ^= K >> R;
-    K *= M;
-
-    H ^= K;
-    H *= M;
-  }
-
-  const unsigned char *Data2 = (const unsigned char *)Data;
-  switch (Len & 7) {
-  case 7:
-    H ^= uint64_t(Data2[6]) << 48;
-  case 6:
-    H ^= uint64_t(Data2[5]) << 40;
-  case 5:
-    H ^= uint64_t(Data2[4]) << 32;
-  case 4:
-    H ^= uint64_t(Data2[3]) << 24;
-  case 3:
-    H ^= uint64_t(Data2[2]) << 16;
-  case 2:
-    H ^= uint64_t(Data2[1]) << 8;
-  case 1:
-    H ^= uint64_t(Data2[0]);
-    H *= M;
-  };
-
-  H ^= H >> R;
-  H *= M;
-  H ^= H >> R;
-
-  return H;
-}
-
 template <class ELFT>
 void BuildIdFastHash<ELFT>::writeBuildId(ArrayRef<uint8_t> Buf) {
   const endianness E = ELFT::TargetEndianness;
 
-  // 64-bit murmur2 hash
-  uint64_t Hash = murmurHash64A(Buf.data(), Buf.size());
+  // 64-bit xxhash
+  uint64_t Hash = xxHash64(StringRef((const char *)Buf.data(), Buf.size()));
   write64<E>(this->HashBuf, Hash);
 }
 
-- 
2.7.4