llvm dev - Jul 2017 - Uncovering non-determinism in LLVM - The Next Steps

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

> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
> Grang, Mandeep Singh via llvm-dev
> Sent: Thursday, July 06, 2017 2:56 AM
> To: llvm-dev at lists.llvm.org
> Subject: [llvm-dev] Uncovering non-determinism in LLVM - The Next Steps
> 
> 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
I hope you mean all supported *unordered* containers here. :-)
> default. We would then run "ninja check-all". Any failing unit
test is a
> sign of a potential non-determinism.
When you did this with SmallPtrSet, were there tests that failed but
did not actually indicate 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.
Sounds like a plan.
> 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.
You might want to do this part first, partly because you can do it
today with no further patches to LLVM.  I would not be surprised if
the set of differences between rel/rel+asserts was non-empty, as
(I think) +asserts enables some things that actually do different
computations, and not just add some internal-consistency checks.
Also doing this first would let you smoke out any infrastructure
issues in the mechanics of comparing the output of two different
compilers, without the complication of a (relatively) untried option.

My team has done something like your proposal, but comparing with/without 
-g and -S.  In those cases there are a number of innocuous differences 
that we have had to teach our comparison tool to ignore.  But we also 
found some real bugs and that was very satisfying.

When you start talking about Linux vs Windows, though... I assume you
mean comparing the output from different *hosts* but the same *target.*
Is LNT set up to do cross-compilation?  This is just my ignorance of 
LNT asking.

There might also be differences across hosts that you just have to live
with.  I remember a compiler that had different output depending on
whether it was a 32-bit or 64-bit host, because the constant folder
depended on host arithmetic.  (The compiled programs *worked* identically,
but the one compiled on a 32-bit host was a tiny bit less optimized.)
I don't know that LLVM has any issues like this, but it's something to 
be aware of.
> 
> 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.
Seems quite reasonable.
> 
> I would like to hear the community's thoughts on these proposals.
I think it's great.  There's the obvious potential for combinatoric
explosion of test runs you *could* compare, and I think some of the
other possibilities (+/-asserts, different hosts) are equally
interesting, but I'm really pleased to see this kind of creative
approach to testing.

Thanks!
--paulr
> 
> Thanks,
> Mandeep
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On 6 July 2017 at 11:02, Robinson, Paul via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Grang, Mandeep Singh wrote:
>> I would like to hear the community's thoughts on these proposals.
>From the perspective of the recent focused effort on reproducible
builds, I think this is excellent.
>> 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.
>
> You might want to do this part first, partly because you can do it
> today with no further patches to LLVM. ...
>
> My team has done something like your proposal, but comparing with/without
> -g and -S.  In those cases there are a number of innocuous differences
> that we have had to teach our comparison tool to ignore.  But we also
> found some real bugs and that was very satisfying.
It does seem like a good idea to start with comparing output compiled
on 32- and 64-bit hosts, or on Windows and Linux. Out of curiosity
what kinds of changes arise from the presence/absence of -g? (It's not
just the expected presence/absence of the debug info?)
> There might also be differences across hosts that you just have to live
> with.
Being able to build identical objects using the same version of Clang
built with different host compilers on different operating systems is
nice in that it allows use of techniques from diverse double
compilation to improve confidence in the toolchain. It would be great
to at least know if / how objects currently differ when compiled in
cases like this.

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>

On Thu, Jul 6, 2017 at 8:02 AM, Robinson, Paul via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
>
> > -----Original Message-----
> > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf
Of
> > Grang, Mandeep Singh via llvm-dev
> > Sent: Thursday, July 06, 2017 2:56 AM
> > To: llvm-dev at lists.llvm.org
> > Subject: [llvm-dev] Uncovering non-determinism in LLVM - The Next
Steps
> >
> > 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
>
> I hope you mean all supported *unordered* containers here. :-)
>
> > default. We would then run "ninja check-all". Any failing
unit test is a
> > sign of a potential non-determinism.
>
> When you did this with SmallPtrSet, were there tests that failed but
> did not actually indicate non-determinism?
>
An example of this is the order of predecessors in the IR in phi nodes.
There are passes that will create them in different orders depending on
smallptrset iteration.
This is "non-deterministic" in the sense that the textual form is
different, but has the same semantic meaning either way.
(Let's put aside the fact that allowing them  to have a different order
than the actual block predecessors is a pointless waste of time :P)

Whether you consider this non-deterministic depends on your goal.

I would argue that any pass that behaves differently given
phi [[1, block 1], [2, block 2]]
and
phi [[2, block 2], [1, block 1]]

is just flat out broken (and we have some that break due to poor design,
etc)

So i wouldn't consider the above to be non-deterministic in any meaningful
sense, despite it outputting different textual form.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170706/1188e387/attachment.html>

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>