Revert r301487: Replace HashString algorithm with xxHash64

This reverts commit r301487 to make buildbots green.

llvm-svn: 301491

10 files changed, 36 insertions, 42 deletions

diff --git a/clang/test/CodeGen/target-features-error-2.c b/clang/test/CodeGen/target-features-error-2.c
index 9ce829a48c8..683d9ab99ef 100644
--- a/clang/test/CodeGen/target-features-error-2.c
+++ b/clang/test/CodeGen/target-features-error-2.c
@@ -1,4 +1,4 @@
-// RUN: %clang_cc1 %s -triple=x86_64-linux-gnu -S -verify -o - -D NEED_SSE41
+// RUN: %clang_cc1 %s -triple=x86_64-linux-gnu -S -verify -o - -D NEED_SSE42
 // RUN: %clang_cc1 %s -triple=x86_64-linux-gnu -S -verify -o - -D NEED_AVX_1
 // RUN: %clang_cc1 %s -triple=x86_64-linux-gnu -S -verify -o - -D NEED_AVX_2
 // RUN: %clang_cc1 %s -triple=x86_64-linux-gnu -S -verify -o - -D NEED_AVX_3
@@ -7,12 +7,9 @@
 #define __MM_MALLOC_H
 #include <x86intrin.h>
 
-// Really, this needs AVX, but because targetting AVX includes all the SSE features too, and
-// features are sorted by hash function, and we just return the first missing feature, then we end
-// up returning the subfeature sse4.1 instead of avx.
-#if NEED_SSE41
+#if NEED_SSE42
 int baz(__m256i a) {
-  return _mm256_extract_epi32(a, 3); // expected-error {{always_inline function '_mm256_extract_epi32' requires target feature 'sse4.1', but would be inlined into function 'baz' that is compiled without support for 'sse4.1'}}
+  return _mm256_extract_epi32(a, 3); // expected-error {{always_inline function '_mm256_extract_epi32' requires target feature 'sse4.2', but would be inlined into function 'baz' that is compiled without support for 'sse4.2'}}
 }
 #endif
 
diff --git a/clang/test/CodeGen/target-features-error.c b/clang/test/CodeGen/target-features-error.c
index d4deabd66ba..518f6e6189e 100644
--- a/clang/test/CodeGen/target-features-error.c
+++ b/clang/test/CodeGen/target-features-error.c
@@ -3,5 +3,6 @@ int __attribute__((target("avx"), always_inline)) foo(int a) {
   return a + 4;
 }
 int bar() {
-  return foo(4); // expected-error {{always_inline function 'foo' requires target feature 'sse4.1', but would be inlined into function 'bar' that is compiled without support for 'sse4.1'}}
+  return foo(4); // expected-error {{always_inline function 'foo' requires target feature 'sse4.2', but would be inlined into function 'bar' that is compiled without support for 'sse4.2'}}
 }
+
diff --git a/clang/test/SemaCXX/typo-correction-delayed.cpp b/clang/test/SemaCXX/typo-correction-delayed.cpp
index 11d54006f3e..610d4397138 100644
--- a/clang/test/SemaCXX/typo-correction-delayed.cpp
+++ b/clang/test/SemaCXX/typo-correction-delayed.cpp
@@ -52,7 +52,6 @@ void testNoCandidates() {
 }
 
 class string {};
-
 struct Item {
   void Nest();
   string text();
@@ -89,16 +88,12 @@ void f(LinkedNode *node) {
 struct NestedNode {
   NestedNode* Nest();
   NestedNode* next();
-  // Note, this test is dependent on the order in which identifiers are passed
-  // to the typo corrector, which is based on the hash function used.  For
-  // consistency, I am making the next keyword the first identifier returned.
-  string eext() const;
+  string text() const;
 };
 void f(NestedNode *node) {
   // There are two equidistant, usable corrections for Next: next and Nest
   NestedNode *next = node->Next();  // expected-error-re {{no member named 'Next' in 'initializerCorrections::NestedNode'{{$}}}}
 }
-
 }
 
 namespace PR21669 {
diff --git a/clang/unittests/Tooling/CompilationDatabaseTest.cpp b/clang/unittests/Tooling/CompilationDatabaseTest.cpp
index 5d4ed20603b..1a6fffec939 100644
--- a/clang/unittests/Tooling/CompilationDatabaseTest.cpp
+++ b/clang/unittests/Tooling/CompilationDatabaseTest.cpp
@@ -81,10 +81,10 @@ TEST(JSONCompilationDatabase, GetAllFiles) {
 
   std::vector<std::string> expected_files;
   SmallString<16> PathStorage;
-  llvm::sys::path::native("//net/dir/file2", PathStorage);
-  expected_files.push_back(PathStorage.str());
   llvm::sys::path::native("//net/dir/file1", PathStorage);
   expected_files.push_back(PathStorage.str());
+  llvm::sys::path::native("//net/dir/file2", PathStorage);
+  expected_files.push_back(PathStorage.str());
   EXPECT_EQ(expected_files,
             getAllFiles("[{\"directory\":\"//net/dir\","
                         "\"command\":\"command\","
diff --git a/llvm/include/llvm/ADT/StringExtras.h b/llvm/include/llvm/ADT/StringExtras.h
index 225e456bc72..26f11924b77 100644
--- a/llvm/include/llvm/ADT/StringExtras.h
+++ b/llvm/include/llvm/ADT/StringExtras.h
@@ -16,7 +16,6 @@
 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/DataTypes.h"
-#include "llvm/Support/xxhash.h"
 #include <iterator>
 
 namespace llvm {
@@ -152,11 +151,15 @@ void SplitString(StringRef Source,
 
 /// HashString - Hash function for strings.
 ///
-/// Just fall back on xxHash64.  Yes we drop the high bits on platforms where
-/// unsigned == 4 bytes (which includes x86_64), but xxHash64 already has good
-/// avalanching, so we wouldn't gain much if anything.
-static inline unsigned HashString(StringRef Str, unsigned Seed = 0) {
-  return xxHash64(Str, Seed);
+/// This is the Bernstein hash function.
+//
+// FIXME: Investigate whether a modified bernstein hash function performs
+// better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
+//   X*33+c -> X*33^c
+static inline unsigned HashString(StringRef Str, unsigned Result = 0) {
+  for (StringRef::size_type i = 0, e = Str.size(); i != e; ++i)
+    Result = Result * 33 + (unsigned char)Str[i];
+  return Result;
 }
 
 /// Returns the English suffix for an ordinal integer (-st, -nd, -rd, -th).
diff --git a/llvm/include/llvm/Support/xxhash.h b/llvm/include/llvm/Support/xxhash.h
index cbd9730717e..f7ca460188a 100644
--- a/llvm/include/llvm/Support/xxhash.h
+++ b/llvm/include/llvm/Support/xxhash.h
@@ -41,7 +41,7 @@
 #include "llvm/ADT/StringRef.h"
 
 namespace llvm {
-uint64_t xxHash64(llvm::StringRef Data, uint64_t Seed = 0);
+uint64_t xxHash64(llvm::StringRef Data);
 }
 
 #endif
diff --git a/llvm/lib/Support/xxhash.cpp b/llvm/lib/Support/xxhash.cpp
index ca3120df4bc..a7d990bf6a4 100644
--- a/llvm/lib/Support/xxhash.cpp
+++ b/llvm/lib/Support/xxhash.cpp
@@ -68,8 +68,9 @@ static uint64_t mergeRound(uint64_t Acc, uint64_t Val) {
   return Acc;
 }
 
-uint64_t llvm::xxHash64(StringRef Data, uint64_t Seed) {
+uint64_t llvm::xxHash64(StringRef Data) {
   size_t Len = Data.size();
+  uint64_t Seed = 0;
   const char *P = Data.data();
   const char *const BEnd = P + Len;
   uint64_t H64;
diff --git a/llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll b/llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll
index ff2e3425e7c..505477c8211 100644
--- a/llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll
+++ b/llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll
@@ -27,12 +27,12 @@
 
 ; Check that all the names are present in the output
 ; CHECK:  Hash = 0x00597841
-; CHECK:    Name: {{[0-9a-f]*}} "k1"
 ; CHECK:    Name: {{[0-9a-f]*}} "is"
+; CHECK:    Name: {{[0-9a-f]*}} "k1"
 
 ; CHECK: Hash = 0xa4b42a1e
-; CHECK:    Name: {{[0-9a-f]*}} "_ZN4llvm16DenseMapIteratorIPNS_10MDLocationENS_6detail13DenseSetEmptyENS_10MDNodeInfoIS1_EENS3_12DenseSetPairIS2_EELb0EE23AdvancePastEmptyBucketsEv"
 ; CHECK:    Name: {{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE"
+; CHECK:    Name: {{[0-9a-f]*}} "_ZN4llvm16DenseMapIteratorIPNS_10MDLocationENS_6detail13DenseSetEmptyENS_10MDNodeInfoIS1_EENS3_12DenseSetPairIS2_EELb0EE23AdvancePastEmptyBucketsEv"
 
 ; CHECK: Hash = 0xeee7c0b2
 ; CHECK:    Name: {{[0-9a-f]*}} "_ZNK4llvm12LivePhysRegs5printERNS_11raw_ostreamE"
diff --git a/llvm/test/DebugInfo/PDB/pdbdump-headers.test b/llvm/test/DebugInfo/PDB/pdbdump-headers.test
index f5c4f7fe52f..4152f0f9da0 100644
--- a/llvm/test/DebugInfo/PDB/pdbdump-headers.test
+++ b/llvm/test/DebugInfo/PDB/pdbdump-headers.test
@@ -73,8 +73,8 @@
 ; EMPTY-NEXT:   Guid: {0B355641-86A0-A249-896F-9988FAE52FF0}
 ; EMPTY-NEXT:   Features: 0x1
 ; EMPTY-NEXT:   Named Streams {
-; EMPTY-NEXT:     /LinkInfo: 5
 ; EMPTY-NEXT:     /names: 13
+; EMPTY-NEXT:     /LinkInfo: 5
 ; EMPTY-NEXT:     /src/headerblock: 9
 ; EMPTY-NEXT:   }
 ; EMPTY-NEXT: }
@@ -1837,8 +1837,8 @@
 ; BIG-NEXT:   Guid: {880ECC89-DF81-0B4F-839C-58CBD052E937}
 ; BIG-NEXT:   Features: 0x1
 ; BIG-NEXT:   Named Streams {
-; BIG-NEXT:     /LinkInfo: 5
 ; BIG-NEXT:     /names: 13
+; BIG-NEXT:     /LinkInfo: 5
 ; BIG-NEXT:     /src/headerblock: 61
 ; BIG-NEXT:   }
 ; BIG-NEXT: }
diff --git a/llvm/test/DebugInfo/X86/gnu-public-names.ll b/llvm/test/DebugInfo/X86/gnu-public-names.ll
index cd603bc23b9..44cf0c5cea9 100644
--- a/llvm/test/DebugInfo/X86/gnu-public-names.ll
+++ b/llvm/test/DebugInfo/X86/gnu-public-names.ll
@@ -66,7 +66,6 @@
 
 ; ASM: .section        .debug_gnu_pubnames
 ; ASM: .byte   32                      # Kind: VARIABLE, EXTERNAL
-; ASM: .byte   32                      # Kind: VARIABLE, EXTERNAL
 ; ASM-NEXT: .asciz  "global_variable"       # External Name
 
 ; ASM: .section        .debug_gnu_pubtypes
@@ -198,29 +197,27 @@
 ; CHECK-LABEL: .debug_gnu_pubnames contents:
 ; CHECK-NEXT: length = {{.*}} version = 0x0002 unit_offset = 0x00000000 unit_size = {{.*}}
 ; CHECK-NEXT: Offset     Linkage  Kind     Name
-; CHECK-NEXT:  [[ANON_INNER_B]] STATIC VARIABLE "(anonymous namespace)::inner::b"
-; CHECK-NEXT:  [[MEM_FUNC]] EXTERNAL FUNCTION "C::member_function"
-; CHECK-NEXT:  [[OUTER]] EXTERNAL TYPE "outer"
-; CHECK-NEXT:  [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable"
-; CHECK-NEXT:  [[GLOB_VAR]] EXTERNAL VARIABLE "global_variable"
-; CHECK-NEXT:  EXTERNAL FUNCTION "f7"
-; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
 ; CHECK-NEXT:  [[GLOBAL_FUNC]] EXTERNAL FUNCTION "global_function"
-; CHECK-NEXT:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
 ; CHECK-NEXT:  [[NS]] EXTERNAL TYPE     "ns"
-; CHECK-NEXT:  [[ANON]] EXTERNAL TYPE "(anonymous namespace)"
 ; CHECK-NEXT:  [[OUTER_ANON_C]] STATIC VARIABLE "outer::(anonymous namespace)::c"
-; CHECK-NEXT:  [[D_VAR]] EXTERNAL VARIABLE "ns::d"
-; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
-; CHECK-NEXT:  [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable"
 ; CHECK-NEXT:  [[ANON_I]] STATIC VARIABLE "(anonymous namespace)::i"
-; CHECK-NEXT:  [[ANON_INNER]] EXTERNAL TYPE "(anonymous namespace)::inner"
-; CHECK-NEXT:  EXTERNAL FUNCTION "f3"
 ; GCC Doesn't put local statics in pubnames, but it seems not unreasonable and
 ; comes out naturally from LLVM's implementation, so I'm OK with it for now. If
 ; it's demonstrated that this is a major size concern or degrades debug info
 ; consumer behavior, feel free to change it.
 ; CHECK-NEXT:  [[F3_Z]] STATIC VARIABLE "f3::z"
+; CHECK-NEXT:  [[ANON]] EXTERNAL TYPE "(anonymous namespace)"
+; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
+; CHECK-NEXT:  [[ANON_INNER_B]] STATIC VARIABLE "(anonymous namespace)::inner::b"
+; CHECK-NEXT:  [[OUTER]] EXTERNAL TYPE "outer"
+; CHECK-NEXT:  [[MEM_FUNC]] EXTERNAL FUNCTION "C::member_function"
+; CHECK-NEXT:  [[GLOB_VAR]] EXTERNAL VARIABLE "global_variable"
+; CHECK-NEXT:  [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable"
+; CHECK-NEXT:  [[ANON_INNER]] EXTERNAL TYPE "(anonymous namespace)::inner"
+; CHECK-NEXT:  [[D_VAR]] EXTERNAL VARIABLE "ns::d"
+; CHECK-NEXT:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
+; CHECK-NEXT:  [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable"
+; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
 
 ; CHECK-LABEL: debug_gnu_pubtypes contents:
 ; CHECK: Offset     Linkage  Kind     Name