[Support] Change StringMap hash function from xxHash64 to xxh3_64bits

[MaskRay]

Summary

Similar to D142862.

xxh3 is significantly faster than xxh64. Switch to xxh3, as we did for
for lld and llvm-dwarfutil to increase performance (D154813 D155675).
While I think StringMap is not a bottleneck for most applications, it
seems good to eliminate the slower xxh64. In addition, according to
D142862, Rust with a large constant string is sensitive to the StringMap
performance.

I have fixed all found issues separately, but one is remaining:

• ExecutionEngine/RuntimeDyld/ARM/MachO_ARM_PIC_relocations.s has a failure due to StringMap iteration order. It now passes with LLVM_ENABLE_REVERSE_ITERATION=on while failing with LLVM_ENABLE_REVERSE_ITERATION=off.

[erikdesjardins]

FYI, I ran this against the Rust compiler performance test suite and it didn't make a noticeable difference compared to the initial switch from DJB -> xxhash. (Which makes sense--DJB is so slow that it's hard to make an improvement that's anywhere close to that.)
It does seem to improve an artificial benchmark with very large constant strings by ~3% locally.

It of course still makes sense to do this, even if only to remove the old xxh64.

LGTM with the noted issues resolved.

[MaskRay]

rebase

[MaskRay]

In D155781#4524570, @erikdesjardins wrote:

FYI, I ran this against the Rust compiler performance test suite and it didn't make a noticeable difference compared to the initial switch from DJB -> xxhash. (Which makes sense--DJB is so slow that it's hard to make an improvement that's anywhere close to that.)
It does seem to improve an artificial benchmark with very large constant strings by ~3% locally.

Thank you for testing this patch! ~3% is still good.

It of course still makes sense to do this, even if only to remove the old xxh64.

Exactly, to make it clear that xxh64 is only for exceptions and only granted very carefully. Generally xxh3 should be used.

LGTM with the noted issues resolved.

I've managed to fix 10+ instances that relied on the iteration order. D155789 is now in place (tested by [[ https://lab.llvm.org/buildbot/#/builders/54 | a bot named reverse-iteration for llvm;clang;polly ]]) to prevent back sliding.
This patch is now as simple as changing just the StringMap code:)

[erikdesjardins]

Thanks!

[MaskRay]

flip the condition of llvm/test/ExecutionEngine/RuntimeDyld/ARM/MachO_ARM_PIC_relocations.s

llvm/lib/ExecutionEngine/Orc/DebugUtils.cpp

raw_ostream &operator<<(raw_ostream &OS, const SymbolState &S) {
   case SymbolState::Ready:
     return OS << "Ready";
   }
   llvm_unreachable("Invalid state");
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolStringPool &SSP) {
   std::lock_guard<std::mutex> Lock(SSP.PoolMutex);
+  SmallVector<std::pair<StringRef, int>, 0> Vec;
   for (auto &KV : SSP.Pool)
-    OS << KV.first() << ": " << KV.second << "\n";
+    Vec.emplace_back(KV.first(), KV.second);
+  llvm::sort(Vec, less_first());
+  for (auto &[K, V] : Vec)
+    OS << K << ": " << V << "\n";
   return OS;
 }
 
 DumpObjects::DumpObjects(std::string DumpDir, std::string IdentifierOverride)
     : DumpDir(std::move(DumpDir)),
       IdentifierOverride(std::move(IdentifierOverride)) {
 
   /// Discard any trailing separators.

llvm/lib/Support/StringMap.cpp

 /// up in.  If it already exists as a key in the map, the Item pointer for the
 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
 /// case, the FullHashValue field of the bucket will be set to the hash value
 /// of the string.
 unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
   // Hash table unallocated so far?
   if (NumBuckets == 0)
     init(16);
-  unsigned FullHashValue = xxHash64(Name);
+  unsigned FullHashValue = xxh3_64bits(Name);
   unsigned BucketNo = FullHashValue & (NumBuckets - 1);
   unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   int FirstTombstone = -1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return it.

 }
 
 /// FindKey - Look up the bucket that contains the specified key. If it exists
 /// in the map, return the bucket number of the key.  Otherwise return -1.
 /// This does not modify the map.
 int StringMapImpl::FindKey(StringRef Key) const {
   if (NumBuckets == 0)
     return -1; // Really empty table?
-  unsigned FullHashValue = xxHash64(Key);
+  unsigned FullHashValue = xxh3_64bits(Key);
   unsigned BucketNo = FullHashValue & (NumBuckets - 1);
   unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return.
     if (LLVM_LIKELY(!BucketItem))

llvm/test/DebugInfo/X86/gnu-public-names-gmlt.ll

 ;   $ clang++ -gmlt %s -emit-llvm -S
 
 ; GPUB: Compile Unit
 ; GPUB: DW_AT_GNU_pubnames
 
 ; GPUB: .debug_gnu_pubnames contents:
 ; GPUB-NEXT: unit_offset = 0x00000000
 ; GPUB-NEXT: Name
-; GPUB-NEXT: "f3"
 ; GPUB-NEXT: "f2"
+; GPUB-NEXT: "f3"
 
 ; GPUB: .debug_gnu_pubtypes contents:
 ; GPUB-NEXT: length = 0x0000000e, format = DWARF32, version = 0x0002, unit_offset = 0x00000000
 ; GPUB-NEXT: Name
 
 ; NONE-NOT: .debug_pubnames contents:
 ; NONE-NOT: .debug_pubtypes contents:
 ; NONE-NOT: .debug_gnu_pubnames contents:

llvm/test/DebugInfo/X86/gnu-public-names.ll

 ; int f7() {
 ;   return i + *f3() + inner::b + outer::c;
 ; }
 
 ; ASM: .section        .debug_gnu_pubnames
 ; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
 ; ASM-NEXT: .asciz  "ns::global_namespace_variable"       # External Name
 ; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
+; ASM-NEXT: .asciz  "C::static_member_variable"           # External Name
+; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
+; ASM-NEXT: .asciz  "ns::d"                               # External Name
+; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
 ; ASM-NEXT: .asciz  "global_variable"       # External Name
 
 ; ASM: .section        .debug_gnu_pubtypes
 ; ASM: .byte   16                      # Attributes: TYPE, EXTERNAL
 ; ASM-NEXT: .asciz  "C"                     # External Name
 
 ; CHECK: .debug_info contents:
 ; CHECK: DW_TAG_compile_unit

 ; CHECK:   DW_TAG_imported_declaration
 ; CHECK:   DW_TAG_pointer_type
 ; CHECK:   DW_TAG_pointer_type
 ; CHECK:   NULL
 
 ; 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:  [[UNNAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "unnamed_enum_enumerator"
-; CHECK-NEXT:  [[GLOBAL_F7]] EXTERNAL FUNCTION "f7"
-; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
+; CHECK-NEXT:  [[NS]] EXTERNAL TYPE     "ns"
+; CHECK-NEXT:  [[ANON_INNER]] EXTERNAL TYPE "(anonymous namespace)::inner"
 ; FIXME: GCC produces enumerators as EXTERNAL, not STATIC
 ; CHECK-NEXT:  [[NAMED_ENUM_CLASS_ENUMERATOR]] STATIC VARIABLE  "named_enum_class_enumerator"
-; 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:  [[NAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "named_enum_enumerator"
+; CHECK-NEXT:  [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable"
 ; 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:  [[GLOBAL_F7]] EXTERNAL FUNCTION "f7"
 ; 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:  [[F3]] EXTERNAL FUNCTION "f3"
+; CHECK-NEXT:  [[ANON_INNER_B]] STATIC VARIABLE "(anonymous namespace)::inner::b"
+; CHECK-NEXT:  [[MEM_FUNC]] EXTERNAL FUNCTION "C::member_function"
+; CHECK-NEXT:  [[UNNAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "unnamed_enum_enumerator"
+; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
+; CHECK-NEXT:  [[GLOBAL_FUNC]] EXTERNAL FUNCTION "global_function"
+; CHECK-NEXT:  [[D_VAR]] EXTERNAL VARIABLE "ns::d"
 ; 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:  [[OUTER]] EXTERNAL TYPE "outer"
+; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
+; CHECK-NEXT:  [[NAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "named_enum_enumerator"
+; CHECK-NEXT:  [[F3]] EXTERNAL FUNCTION "f3"
+; CHECK-NEXT:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
+; CHECK-NEXT:  [[GLOB_VAR]] EXTERNAL VARIABLE "global_variable"
 
 ; CHECK-LABEL: debug_gnu_pubtypes contents:
 ; CHECK: Offset     Linkage  Kind     Name
-; CHECK-NEXT:  [[INT]] STATIC   TYPE     "int"
 ; CHECK-NEXT:  [[C]] EXTERNAL TYPE     "C"
 ; CHECK-NEXT:  [[UNSIGNED_INT]] STATIC   TYPE     "unsigned int"
 ; CHECK-NEXT:  [[NAMED_ENUM]] EXTERNAL TYPE     "named_enum"
+; CHECK-NEXT:  [[INT]] STATIC   TYPE     "int"
 ; CHECK-NEXT:  [[NAMED_ENUM_CLASS]] EXTERNAL TYPE     "named_enum_class"
 ; CHECK-NEXT:  [[D]] EXTERNAL TYPE     "ns::D"
 
 %struct.C = type { i8 }
 %"struct.ns::D" = type { i32 }
 
 @_ZN1C22static_member_variableE = dso_local global i32 0, align 4, !dbg !0
 @global_variable = dso_local global %struct.C zeroinitializer, align 1, !dbg !18

llvm/test/ExecutionEngine/RuntimeDyld/ARM/MachO_ARM_PIC_relocations.s

+# XFAIL: *
 # RUN: rm -rf %t && mkdir -p %t
 # RUN: llvm-mc -triple=armv7s-apple-ios7.0.0 -filetype=obj -o %t/foo.o %s
 # RUN: llvm-rtdyld -triple=armv7s-apple-ios7.0.0 -verify -check=%s %t/foo.o
 
         .syntax unified
         .section        __TEXT,__text,regular,pure_instructions
         .globl  bar
         .align  2