<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">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">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">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div></div>