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

[David Blaikie via llvm-dev]

On Wed, Jul 5, 2017 at 11:56 PM Grang, Mandeep Singh via llvm-dev <
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
> 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/20170706/a28364f4/attachment-0001.html>