<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 6, 2017 at 10:20 AM, Daniel Berlin via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="h5">On Thu, Jul 6, 2017 at 8:02 AM, Robinson, Paul via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span><br>
<br>
> -----Original Message-----<br>
> From: llvm-dev [mailto:<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists<wbr>.llvm.org</a>] On Behalf Of<br>
> Grang, Mandeep Singh via llvm-dev<br>
> Sent: Thursday, July 06, 2017 2:56 AM<br>
> To: <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> Subject: [llvm-dev] Uncovering non-determinism in LLVM - The Next Steps<br>
><br>
> 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 -<br>
> DLLVM_REVERSE_ITERATION:BOOL=O<wbr>N.<br>
> This will make all supported containers iterate in reverse order by<br>
<br>
</span>I hope you mean all supported *unordered* containers here. :-)<br>
<span><br>
> default. We would then run "ninja check-all". Any failing unit test is a<br>
> sign of a potential non-determinism.<br>
<br>
</span>When you did this with SmallPtrSet, were there tests that failed but<br>
did not actually indicate non-determinism?<br></blockquote><div><br></div></div></div><div>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.</div><div>This is "non-deterministic" in the sense that the textual form is different, but has the same semantic meaning either way.</div><div>(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)</div><div><br></div><div>Whether you consider this non-deterministic depends on your goal.</div><div><br></div><div>I would argue that any pass that behaves differently given </div><div>phi [[1, block 1], [2, block 2]]</div><div>and </div><div>phi [[2, block 2], [1, block 1]] </div><div><br></div><div>is just flat out broken (and we have some that break due to poor design, etc)</div><div><br></div><div>So i wouldn't consider the above to be non-deterministic in any meaningful sense, despite it outputting different textual form.</div></div></div></div></blockquote><div><br></div><div>One of our definitions of non-determinism is simply "output from command line tools should always be bit identical given identical inputs", which is suitable for content-based caching build systems like Bazel.</div><div><br></div><div>I don't know how our bitcode encoding compares to the textual IR in the case of your phi example, but assuming that that difference makes it into the bitcode too, it would cause e.g. ThinLTO bitcode artifacts to violate the content-based caching assumptions, even if semantically to the compiler the difference is immaterial. I know that Richard has mentioned in the past at least for Clang the intention is bit-identical output for bit-identical input.</div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div><br></div></div></div></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">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/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div></div>