Reverse iteration bots

Project Infrastructure
1

CMake -DLLVM_ENABLE_REVERSE_ITERATION=on makes some LLVM containers (currently DenseMap (DenseSet) and StringMap (StringSet) (since D155789) to be iterated in a reversed order[1]. This is a good way to prevent reliance on the unspecified iteration order [2].

for (auto x : aStringMap) {
  // do something that is sensitive to the order. // bad pattern
}

Currently there is one builder reverse-iteration (maintained by @mgrang, thanks!) that checks these subprojects llvm;clang;polly.

I wonder whether we can have -DLLVM_ENABLE_REVERSE_ITERATION=on coverage for lld;flang;lldb;bolt;mlir. This will require adding -DLLVM_ENABLE_REVERSE_ITERATION=on to certain builders (buildbot/osuosl/master/config/builders.py?).

Unlike -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON, -DLLVM_ENABLE_REVERSE_ITERATION=on has no performance overhead.

BTW, -DLLVM_ENABLE_REVERSE_ITERATION=on and -DLLVM_REVERSE_ITERATION=on have the same effect. I wonder whether we should converge to one spelling. LLVM_ENABLE_REVERSE_ITERATION is also a C++ macro name, so I personally prefer -DLLVM_ENABLE_REVERSE_ITERATION=on more.

[1]: StringMap is not completely reversely iterated. For simplicity we just apply bitwise NOT to the hash value. To change xxHash64 (xxh64) to xxh3_64bits for StringMap, I have fixed ~20 bugs in llvm;clang;lld/wasm;lldb;flang.
[2]: https://llvm.org/docs/ProgrammersManual.html even says that the order can be non-deterministic.

1 Like
2

maintained by @mgrang, thanks

The bot is maintained by Qualcomm. @mgrang is no longer working at Qualcomm, so he can’t help you with the bot.

Not sure how much spare capacity we have on the hexagon-build-02/03 bots, but getting coverage for flang and lld would be useful for us. If you post a patch for the reverse-iteration config, I’ll help get it reviewed. (buildbot/osuosl/master/config/builders.py is the right path.)

3

Thank you! If the capacity is a problem, I am wondering whether we can get the coverage for mlir/flang by adding -DLLVM_ENABLE_REVERSE_ITERATION=on to some other builders.

For example, there are multiple builders named flang-aarch64-* on linaro-* workers (@DavidSpickett). We can add -DLLVM_ENABLE_REVERSE_ITERATION=on to one of the worker and then get coverage for check-flang.

Similarly, there are multiple mlir-* builders testing check-mlir. We can change one to use -DLLVM_ENABLE_REVERSE_ITERATION=on.

The reverse-iteration bot can possibly do additional check-lld. check-lld tests are very fast, so hopefully there will be no capacity problem.

4

I oversee the bots but flang isn’t my usual area, so we (Linaro) will talk it over internally. I/we will get back to you shortly.

5

Linaro will cover flang with LLVM_ENABLE_REVERSE_ITERATION. We just need some time to figure out what form that will take, new bot, or adding to an existing one.

Consider putting reverse_it in the name or tagging it if possible. Saves people digging into the cmake after a long time being confused why they can’t reproduce the issue.

6

https://reviews.llvm.org/D157274

7

The flang bot is online now Buildbot (pretty slow right now, it’ll catch up as the ccache fills up).

1 Like
8

Thank you!

If -DCMAKE_BUILD_TYPE=Debug builds are too slow, perhaps try -O1?

9

I could but the point is to keep checking the debug configuration as well. Times are up across the board for flang which is to be expected after a restart, debug reverse iteration isn’t an outlier anyway.

10

LLVM_ENABLE_REVERSE_ITERATION only applies to pointer-like types.

% cat llvm/include/llvm/Support/ReverseIteration.h
...
template<class T = void *>
bool shouldReverseIterate() {
#if LLVM_ENABLE_REVERSE_ITERATION
  return detail::IsPointerLike<T>::value;
#else
  return false;
#endif
}

Code might rely on the iteration order of DenseMap<StringRef, X> and making
DenseMap/hash_value(StringRef) replacement difficult.
Code might rely on hash_value(StringRef) and use it for on-disk serialization.

I’ve fixed quite a few issues in f8f4235612b9 c025bd1fdbbd 89e8e63f47ff
86eb6bf6715c eb8d03656549 0ea6b8e476c2 58d7a6e0e636 8ea31db27211
255986e27fcf.

This effort allows us to try replacing the algorithm in Hashing.h.
Using a non-deterministic seed for Hashing.h should help: [Hashing] Use a non-deterministic seed by MaskRay · Pull Request #96282 · llvm/llvm-project · GitHub

See also Determinism in hash tables · Issue #339 · abseil/abseil-cpp · GitHub

1 Like