<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">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 class=""><br>
<br>
> -----Original Message-----<br>
> From: llvm-dev [mailto:<a href="mailto:llvm-dev-bounces@lists.llvm.org">llvm-dev-bounces@<wbr>lists.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">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=<wbr>ON.<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 class=""><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>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><br></div><div><br></div></div></div></div>