[Support] Implement LLVM_ENABLE_REVERSE_ITERATION for StringMap

[MaskRay]

Summary

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.

[jhenderson]

Looks good from my point of view, but probably worth giving it more time for others to look at. Do we need some documentation for the new variable?

[MaskRay]

Thank you for favoring this patch:) You may notice that I have reported issues to two patches and I'd like them to be addressed first. At the very least I have to wait for the unit test from D149162 to be fixed as it cannot be worked around by UNSUPPORTED: reverse_iteration.

For the documentation, I am thinking of

**LLVM_ENABLE_REVERSE_ITERATION**:BOOL
  Some set-like containers (e.g., DenseMap, StringMap) have unspecified iteration order. Reverse the iteration order for them to catch accidental reliance. Defaults to OFF.

near LLVM_ENABLE_EXPENSIVE_CHECKS commit 0aa27cd29ba3f2cf98b1f48bc6e653d8a66630e8 (@RKSimon) for

[MaskRay]

llvm/test/CodeGen/MIR/AMDGPU/virtreg-uses-unallocatable-class.mir

2

@arsenm perhaps you can help fix this issue :)

[jhenderson]

https://llvm.org/docs/CMake.html documents "LLVM_REVERSE_ITERATION". Is this an error in the doc (it should be "LLVM_ENABLE_REVERSE_ITERATION")?

[MaskRay]

In D155789#4521423, @jhenderson wrote:

https://llvm.org/docs/CMake.html documents "LLVM_REVERSE_ITERATION". Is this an error in the doc (it should be "LLVM_ENABLE_REVERSE_ITERATION")?

It seems that both -DLLVM_REVERSE_ITERATION=1 and -DLLVM_ENABLE_REVERSE_ITERATION=1 are supported... I think this may not be intentional, and we probably should converge on one spelling for the CMake variable.

llvm-zorg has one instance of LLVM_REVERSE_ITERATION, so perhaps LLVM_REVERSE_ITERATION is preferred...

[foad]

llvm/test/CodeGen/MIR/AMDGPU/virtreg-uses-unallocatable-class.mir

2

MIRParserImpl::setupRegisterInfo iterates over the StringMap PerFunctionMIParsingState::VRegInfosNamed. This only seems to affect the order in which error messages are printed. We could fix the test with CHECK-DAG:.

[dblaikie]

llvm/lib/Support/StringMap.cpp

89–90

Does this actually cause reverse iteration? I'd guess it causes some other iteration, but not necessarily reverse? Maybe doesn't really matter, or maybe it'd be good to rename the reverse iteration thing?

(or maybe we could/should move to something more like Abseil that randomizes hash seeds/iteration order more aggressively/broadly, and doesn't require opt-in?)

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

1

Got bugs/outstanding reviews tracking these issues?

llvm/utils/lit/lit/llvm/config.py

123–125

Do you plan to remove this feature in a fairly short time frame? Might be good to have a bug or review identifier here to track cleaning this up?

[MaskRay]

llvm/lib/Support/StringMap.cpp

89–90

It's not.

89–90

It's approximate reverse iteration, so the commit message actually says:

... shuffle StringMap iteration order (actually flipping the hash so that elements not in the
same bucket are reversed) to catch violations,

If two elements are hashed to share the same low order bits, whether or not the hash is inverted, their iteration order will be decided by the insertion order (linear probing characteristic). This makes the approach worse than a full-blown approach that changes many places to do a reversed iteration. Personally I feel such a full-blown approach is probably going to make the code too complex...

llvm/test/CodeGen/MIR/AMDGPU/virtreg-uses-unallocatable-class.mir

2

Thank you for mentioning the fix. Filed https://github.com/llvm/llvm-project/issues/64085

Ideally diagnostics have the same order... I assume that MIRParser will not become slower if we add a llvm::sort

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

1

Filed https://github.com/llvm/llvm-project/issues/64085 Only 2 tests need to be fixed :)

llvm/utils/lit/lit/llvm/config.py

123–125

Replied on the other comment. Yes, this is hopefully short-term.

[dblaikie]

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

1

Would've thought it'd be better/easier to wait to fix 2 tests than to commit this with these additional UNSPPORTEDs and then remove them, etc. But ah well.

llvm/lib/Support/StringMap.cpp

 //===--- StringMap.cpp - String Hash table map implementation -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the StringMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/ReverseIteration.h"
 #include "llvm/Support/xxhash.h"
 
 using namespace llvm;
 
 /// Returns the number of buckets to allocate to ensure that the DenseMap can
 /// accommodate \p NumEntries without need to grow().
 static inline unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
   // Ensure that "NumEntries * 4 < NumBuckets * 3"

 /// 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);
+  if (shouldReverseIterate())
+    FullHashValue = ~FullHashValue;
   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);
+  if (shouldReverseIterate())
+    FullHashValue = ~FullHashValue;
   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/CMakeLists.txt

llvm_canonicalize_cmake_booleans(
   LLVM_ENABLE_PLUGINS
   LLVM_BYE_LINK_INTO_TOOLS
   LLVM_EXAMPLEIRTRANSFORMS_LINK_INTO_TOOLS
   LLVM_HAVE_TF_AOT
   LLVM_HAVE_TFLITE
   LLVM_INLINER_MODEL_AUTOGENERATED
   LLVM_RAEVICT_MODEL_AUTOGENERATED
   LLVM_ENABLE_EXPENSIVE_CHECKS
+  LLVM_ENABLE_REVERSE_ITERATION
   LLVM_INCLUDE_DXIL_TESTS
   LLVM_TOOL_LLVM_DRIVER_BUILD
   )
 
 configure_lit_site_cfg(
   ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.py.in
   ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg.py
   MAIN_CONFIG

llvm/test/CodeGen/MIR/AMDGPU/virtreg-uses-unallocatable-class.mir

+# UNSUPPORTED: reverse_iteration
 # RUN: not llc -mtriple=amdgcn-- -mcpu=gfx900 -run-pass=none -o - %s 2>&1 | FileCheck %s
 
 # Check a diagnostic is emitted if non-allocatable classes are used
 # with virtual registers, and there's no assert.
 
 # CHECK: error: {{.*}}: Cannot use non-allocatable class 'TTMP_32' for virtual register named_use in function 'virtreg_unallocatable'
 # CHECK: error: {{.*}}: Cannot use non-allocatable class 'TTMP_32' for virtual register named_def in function 'virtreg_unallocatable'
 # CHECK: error: {{.*}}: Cannot use non-allocatable class 'TTMP_32' for virtual register 0 in function 'virtreg_unallocatable'
 # CHECK: error: {{.*}}: Cannot use non-allocatable class 'TTMP_32' for virtual register 2 in function 'virtreg_unallocatable'

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

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

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td

+// UNSUPPORTED: reverse_iteration
 // RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
 // RUN:     -gicombiner-stop-after-parse -combiners=MyCombiner %s | \
 // RUN: FileCheck %s
 
 include "llvm/Target/Target.td"
 include "llvm/Target/GlobalISel/Combine.td"
 
 def MyTargetISA : InstrInfo;

llvm/test/lit.site.cfg.py.in

 config.has_plugins = @LLVM_ENABLE_PLUGINS@
 config.linked_bye_extension = @LLVM_BYE_LINK_INTO_TOOLS@
 config.linked_exampleirtransforms_extension = @LLVM_EXAMPLEIRTRANSFORMS_LINK_INTO_TOOLS@
 config.have_tf_aot = @LLVM_HAVE_TF_AOT@
 config.have_tflite = @LLVM_HAVE_TFLITE@
 config.llvm_inliner_model_autogenerated = @LLVM_INLINER_MODEL_AUTOGENERATED@
 config.llvm_raevict_model_autogenerated = @LLVM_RAEVICT_MODEL_AUTOGENERATED@
 config.expensive_checks = @LLVM_ENABLE_EXPENSIVE_CHECKS@
+config.reverse_iteration = @LLVM_ENABLE_REVERSE_ITERATION@
 config.dxil_tests = @LLVM_INCLUDE_DXIL_TESTS@
 config.have_llvm_driver = @LLVM_TOOL_LLVM_DRIVER_BUILD@
 
 import lit.llvm
 lit.llvm.initialize(lit_config, config)
 
 # Let the main config do the real work.
 lit_config.load_config(
     config, os.path.join(config.llvm_src_root, "test/lit.cfg.py"))

llvm/utils/lit/lit/llvm/config.py

def __init__(self, lit_config, config):
 
         have_zlib = getattr(config, "have_zlib", None)
         if have_zlib:
             features.add("zlib")
         have_zstd = getattr(config, "have_zstd", None)
         if have_zstd:
             features.add("zstd")
 
+        if getattr(config, "reverse_iteration", None):
+            features.add("reverse_iteration")
+
         # Check if we should run long running tests.
         long_tests = lit_config.params.get("run_long_tests", None)
         if lit.util.pythonize_bool(long_tests):
             features.add("long_tests")
 
         if target_triple:
             if re.match(r"^x86_64.*-apple", target_triple):
                 features.add("x86_64-apple")