[llvm-dev] Uncovering non-determinism in LLVM - The Next Steps

[Grang, Mandeep Singh via llvm-dev]

Hi all,

Last year I had shared with the community my findings about instances of 
non-determinism in llvm codegen. The major source of which was the 
iteration of unordered containers resulting in non-deterministic 
iteration order. In order to uncover such instances we had introduced 
"reverse iteration" of unordered containers (currently only enabled for 
SmallPtrSet).
I would now like to take this effort forward and propose to do the 
following:

1. We are in the process of setting up an internal nightly buildbot 
which would build llvm with the cmake flag -DLLVM_REVERSE_ITERATION:BOOL=ON.
This will make all supported containers iterate in reverse order by 
default. We would then run "ninja check-all". Any failing unit test is a 
sign of a potential non-determinism.

2. With the toolchain built by the above buildbot we also want to run 
LNT tests and our entire internal testing suite. We then want to compare 
the objdump for every obj file against the obj file compiled by a 
forward/default iteration toolchain. We ideally want to compare rel vs 
rel+asserts vs debug with Linux vs Windows toolchains. Any differences 
in objdumps could signal a potential non-determinism.

3. Currently reverse iteration is enabled only for SmallPtrSet. I am in 
the process of implementing it for more containers. I have already put 
up a patch for DenseMap: https://reviews.llvm.org/D35043

4. Simply compiling with -mllvm -reverse-iterate will help us uncover 
non-determinism due to iteration order of containers. But once we have 
enabled reverse iteration for several containers then pinpointing the 
exact container causing the problem would be more tedious. So I propose 
to add an optional value field to this flag, like -mllvm 
-reverse-iterate=smallptrset -mllvm -reverse-iterate=densemap, etc.

I would like to hear the community's thoughts on these proposals.

Thanks,
Mandeep