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

[Grang, Mandeep Singh via llvm-dev]

Thanks a lot for all your valuable suggestions/comments/opinions. For 
now, we will go ahead and set up our internal buildbot and 
infrastructure to uncover non-determinism and share our findings with 
the community. We can then decide whether we want to fix any "bugs" on a 
case-by-case basis. I think having the capability/infrastructure to 
uncover such "non-determinism" is a nice feature. Whether we want to 
actually fix the supposed "bugs" is a different discussion altogether :)

Thanks,
Mandeep

On 7/6/2017 9:32 AM, David Blaikie wrote:
>
>
> On Wed, Jul 5, 2017 at 11:56 PM Grang, Mandeep Singh via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
>     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
>
>
> As mentioned on the review thread (discussion may be better here, but 
> perhaps since it's already started on the review (sorry I didn't see 
> this thread earlier/discuss more here)... dunno):
>
> SmallPtrSet not only has unspecified iteration order, it also is keyed 
> off only pointers and pointers change run-over-run of the compiler. 
> Unspecified iteration order/hashing currently does not change and 
> wouldn't unless it was done deliberately to flush out issues like this.
>
> So I can see a solid argument for reverse iteration triggering on any 
> pointer keyed container (even those with guaranteed ordering, in fact 
> - because, again, the pointer values aren't guaranteed).
>
> I suppose what we'd really want (not realistic, but at least a 
> hypothetical) is for std::less<T*> in containers to invert its 
> comparison under this flag... (then even cases of pointer ordering in 
> non-containers could be flushed out, if everything actually used 
> std::less<T*>)
>
> I wonder if we could create a compiler flag that would compile < on 
> pointers to > instead? Hmm, I guess that would break range checks, 
> though... :(
>
> Ah well, maybe just reversing iteration in containers with unspecified 
> ordering and pointer keys is enough.
>
>
> It's possible we could flush out all dependence on hash container 
> ordering, but that may not be worthwhile in a small-ish project like 
> LLVM (it'd make sense if we, say, had a dependence on Boost containers 
> - to ensure it was easy to upgrade to a newer Boost container 
> implementation, it might be worthwhile ensuring we didn't grow 
> dependence on the container's ordering even over non-pointer keys, etc)
>
>
>
>     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
>
>
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170707/fe4d19ef/attachment.html>