Reverted due to an internally discovered lld crash due to the underlying
StringMap changes, which turned out to be an existing lld bug that got
tickled by the StringMap changes. That's addressed in
dee8786f70a3d62b639113343fa36ef55bdbad63 so let's have another go with
this change.

Original commit message:
    lldb was rehashing the string 3 times (once to determine which StringMap
    to use, once to query the StringMap, once to insert) on insertion (twice
    on successful lookup).

    This patch allows the lldb to benefit from hash improvements in LLVM
    (from djbHash to xxh3).

    Though further changes would be needed to cache this value to disk - we
    shouldn't rely on the StringMap::hash remaining the same in the
    future/this value should not be serialized to disk. If we want cache
    this value StringMap should take a hashing template parameter to allow
    for a fixed hash to be requested.

This reverts commit 5bc1adff69315dcef670e9fcbe04067b5d5963fb.
Effectively reapplying the original 2e197602305be18b963928e6ae024a004a95af6d.

Reverted due to an internally discovered lld crash, which turned out to
be an existing lld bug that got tickled by this changes. That's
addressed in dee8786f70a3d62b639113343fa36ef55bdbad63 so let's have
another go with this change.

Original commit message:
    Useful for lldb's const string pool, using the hash to determine which
    string map to lock and query/insert.

    Derived from https://reviews.llvm.org/D122974 by Luboš Luňák

This reverts commit f976719fb2cb23364957e5993f7fc3684ee15391.
Effectively reapplying 67c631d283fc96d652304199cd625be426b98f8e.

Crash identified internally in lld's use of StringMap in
`compareSections`. Will investigate offline before recommitting.

This reverts commit 67c631d283fc96d652304199cd625be426b98f8e.

Underlying StringMap API for providing a hash has caused some problems
(observed a crash in lld) - so reverting this until I can figure out/fix
what's going on there.

This reverts commit 52ba075571958e2fec8d871ddfa1ef56486b86d3.
This reverts commit 2e197602305be18b963928e6ae024a004a95af6d.

Useful for lldb's const string pool, using the hash to determine which
string map to lock and query/insert.

Derived from https://reviews.llvm.org/D122974 by Luboš Luňák

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 Erik Desjardins, an artificial benchmark of
Rust with very large constant strings improves by ~3% locally.

I have fixed all found issues (~20) 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.

Reviewed By: erikdesjardins

Differential Revision: https://reviews.llvm.org/D155781

ProgrammersManual.html says

> StringMap iteration order, however, is not guaranteed to be deterministic, so any uses which require that should instead use a std::map.

This patch makes -DLLVM_REVERSE_ITERATION=on (currently
-DLLVM_ENABLE_REVERSE_ITERATION=on works as well) shuffle StringMap
iteration order (actually flipping the hash so that elements not in the
same bucket are reversed) to catch violations, similar to D35043 for
DenseMap. This should help change the hash function (e.g., D142862,
D155781).

With a lot of fixes, there are still some violations. This patch
implements the "reverse_iteration" lit feature to skip such tests.
Eventually we should remove this feature.

`ninja check-{llvm,clang,clang-tools}` are clean with
`#define LLVM_ENABLE_REVERSE_ITERATION 1`.

Reviewed By: jhenderson

Differential Revision: https://reviews.llvm.org/D155789

This reverts commit 37eb9d13f891f7656f811516e765b929b169afe0.

Test failures have been fixed:

- ubsan failure fixed by 72eac42f21c0f45a27f3eaaff9364cbb5189b9e4
- warn-unsafe-buffer-usage-fixits-local-var-span.cpp fixed by
  03cc52dfd1dbb4a59b479da55e87838fb93d2067 (wasn't related)
- test-output-format.ll failure was spurious, build failed at
  https://lab.llvm.org/buildbot/#/builders/54/builds/3545 (b4431b2d945b6fc19b1a55ac6ce969a8e06e1e93)
  but passed at
  https://lab.llvm.org/buildbot/#/builders/54/builds/3546 (5ae99be0377248c74346096dc475af254a3fc799)
  which is before my revert
  https://github.com/llvm/llvm-project/compare/b4431b2d945b6fc19b1a55ac6ce969a8e06e1e93...5ae99be0377248c74346096dc475af254a3fc799

Original commit message:

    Depends on https://reviews.llvm.org/D142861.

    Alternative to https://reviews.llvm.org/D137601.

    xxHash is much faster than djbHash. This makes a simple Rust test case with a large constant string 10% faster to compile.

    Previous attempts at changing this hash function (e.g. https://reviews.llvm.org/D97396) had to be reverted due to breaking tests that depended on iteration order.
    No additional tests fail with this patch compared to `main` when running `check-all` with `-DLLVM_ENABLE_PROJECTS="all"` (on a Linux host), so I hope I found everything that needs to be changed.

    Differential Revision: https://reviews.llvm.org/D142862

This reverts commit d768b97424f9e1a0aae45440a18b99f21c4027ce.

Causes sanitizer failure: https://lab.llvm.org/buildbot/#/builders/238/builds/1114

```
/b/sanitizer-aarch64-linux-bootstrap-ubsan/build/llvm-project/llvm/lib/Support/xxhash.cpp:107:12: runtime error: applying non-zero offset 8 to null pointer
    #0 0xaaaab28ec6c8 in llvm::xxHash64(llvm::StringRef) /b/sanitizer-aarch64-linux-bootstrap-ubsan/build/llvm-project/llvm/lib/Support/xxhash.cpp:107:12
    #1 0xaaaab28cbd38 in llvm::StringMapImpl::LookupBucketFor(llvm::StringRef) /b/sanitizer-aarch64-linux-bootstrap-ubsan/build/llvm-project/llvm/lib/Support/StringMap.cpp:87:28
```

Probably causes test failure in `warn-unsafe-buffer-usage-fixits-local-var-span.cpp`: https://lab.llvm.org/buildbot/#/builders/60/builds/10619

Probably causes reverse-iteration test failure in `test-output-format.ll`: https://lab.llvm.org/buildbot/#/builders/54/builds/3545