<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
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 :)<br>
<br>
Thanks,<br>
Mandeep<br>
<br>
<div class="moz-cite-prefix">On 7/6/2017 9:32 AM, David Blaikie
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAENS6Evn7+_VB9wkOg3wOQB+JzScNDSG=HPvjTbJE6D6FY3MTg@mail.gmail.com">
<div dir="ltr"><br>
<br>
<div class="gmail_quote">
<div dir="ltr">On Wed, Jul 5, 2017 at 11:56 PM Grang, Mandeep
Singh via llvm-dev <<a
href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br>
<br>
Last year I had shared with the community my findings about
instances of<br>
non-determinism in llvm codegen. The major source of which
was the<br>
iteration of unordered containers resulting in
non-deterministic<br>
iteration order. In order to uncover such instances we had
introduced<br>
"reverse iteration" of unordered containers (currently only
enabled for<br>
SmallPtrSet).<br>
I would now like to take this effort forward and propose to
do the<br>
following:<br>
<br>
1. We are in the process of setting up an internal nightly
buildbot<br>
which would build llvm with the cmake flag
-DLLVM_REVERSE_ITERATION:BOOL=ON.<br>
This will make all supported containers iterate in reverse
order by<br>
default. We would then run "ninja check-all". Any failing
unit test is a<br>
sign of a potential non-determinism.<br>
<br>
2. With the toolchain built by the above buildbot we also
want to run<br>
LNT tests and our entire internal testing suite. We then
want to compare<br>
the objdump for every obj file against the obj file compiled
by a<br>
forward/default iteration toolchain. We ideally want to
compare rel vs<br>
rel+asserts vs debug with Linux vs Windows toolchains. Any
differences<br>
in objdumps could signal a potential non-determinism.<br>
<br>
3. Currently reverse iteration is enabled only for
SmallPtrSet. I am in<br>
the process of implementing it for more containers. I have
already put<br>
up a patch for DenseMap: <a
href="https://reviews.llvm.org/D35043" rel="noreferrer"
target="_blank" moz-do-not-send="true">https://reviews.llvm.org/D35043</a></blockquote>
<div><br>
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):<br>
<br>
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.<br>
<br>
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).<br>
<br>
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*>)<br>
<br>
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... :( <br>
<br>
Ah well, maybe just reversing iteration in containers with
unspecified ordering and pointer keys is enough.<br>
<br>
<br>
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)<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
<br>
4. Simply compiling with -mllvm -reverse-iterate will help
us uncover<br>
non-determinism due to iteration order of containers. But
once we have<br>
enabled reverse iteration for several containers then
pinpointing the<br>
exact container causing the problem would be more tedious.
So I propose<br>
to add an optional value field to this flag, like -mllvm<br>
-reverse-iterate=smallptrset -mllvm
-reverse-iterate=densemap, etc.<br>
<br>
I would like to hear the community's thoughts on these
proposals.<br>
<br>
Thanks,<br>
Mandeep<br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a><br>
<a
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer" target="_blank" moz-do-not-send="true">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote>
</div>
</div>
</blockquote>
<br>
</body>
</html>