[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/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);
   if (shouldReverseIterate())
     FullHashValue = ~FullHashValue;
   unsigned BucketNo = FullHashValue & (NumBuckets - 1);
   unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   int FirstTombstone = -1;
   while (true) {

 }
 
 /// 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);
   if (shouldReverseIterate())
     FullHashValue = ~FullHashValue;
   unsigned BucketNo = FullHashValue & (NumBuckets - 1);
   unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];

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

-# UNSUPPORTED: reverse_iteration
+# REQUIRES: reverse_iteration
 # 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