[Support] Implement LLVM_ENABLE_REVERSE_ITERATION for StringMap
authorFangrui Song <i@maskray.me>
Fri, 21 Jul 2023 15:46:51 +0000 (08:46 -0700)
committerFangrui Song <i@maskray.me>
Fri, 21 Jul 2023 15:46:51 +0000 (08:46 -0700)
commit9996e71f2d73a76dc62eb12fc3012aae91014b27
treefbe41b37c4adff027c74da0fa14ed9c799745940
parent6de59222e2ed90c9ab6d7e9703f4f3dcd8bdc627
[Support] Implement LLVM_ENABLE_REVERSE_ITERATION for StringMap

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
llvm/lib/Support/StringMap.cpp
llvm/test/CMakeLists.txt
llvm/test/CodeGen/MIR/AMDGPU/virtreg-uses-unallocatable-class.mir
llvm/test/ExecutionEngine/RuntimeDyld/ARM/MachO_ARM_PIC_relocations.s
llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td
llvm/test/lit.site.cfg.py.in
llvm/utils/lit/lit/llvm/config.py