<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Nov 15, 2016 at 3:06 PM, Grang, Mandeep Singh 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 bgcolor="#FFFFFF" text="#000000">
Everyone,<br>
<br>
There is non-determinism in LLVM codegen in the following scenarios:<br>
<br>
1. Between back-to-back runs of the same LLVM toolchain<br>
2. Between Release vs Release+Asserts toolchains<br>
3. Between Linux vs Windows toolchains<br>
<br>
The main reasons for the non-determinism in codegen are:<br>
<br>
1. Iteration of unordered containers (like SmallPtrSet, DenseMap,
etc) where the iteration order is undefined<br>
2. Use of non-stable sorts (like std:sort which uses quicksort)
where the relative order of elements with the same key is undefined<br>
<br>
I wanted a way to uncover instances where iteration of unordered
containers results in different codegen.<br>
So I have written the following patch:<br>
<b><a class="m_-4875662011915647096moz-txt-link-freetext" href="https://reviews.llvm.org/D26703" target="_blank">https://reviews.llvm.org/<wbr>D26703</a></b><br>
<br>
Given a flag (-mllvm -reverse-iterate) this patch will enable
iteration of SmallPtrSet in reverse order. The idea is to compile
the same source with and without this flag and expect the code to
not change.<br>
If there is a difference in codegen then it would mean that the
codegen is sensitive to the iteration order of SmallPtrSet.<br>
<br>
I ran make check-all with and without my patch and I see the
following additional failures due to iteration of SmallPtrSet in
reverse order:<br>
<i> Clang :: Analysis/keychainAPI.m</i><i><br>
</i><i> Clang :: Analysis/malloc.c</i><i><br>
</i><i> Clang :: Rewriter/<a href="http://objc-modern-metadata-visibility.mm" target="_blank">objc-modern-metadata-<wbr>visibility.mm</a></i><i><br>
</i><i> Clang :: SemaCXX/warn-loop-analysis.cpp</i><i><br>
</i><i> LLVM ::
Transforms/LoopVectorize/<wbr>consecutive-ptr-uniforms.ll</i><i><br>
</i><i> LLVM :: Transforms/SimplifyCFG/bug-<wbr>25299.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/<wbr>cyclicphi.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/<wbr>many-dom-backedge.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/<wbr>many-doms.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/phi-<wbr>translation.ll</i></div></blockquote><div><br></div><div>I am reviewing the change you made, but i do not understand why it solves the problem in MemorySSA, so i'm taking a deeper look.</div><div>I'll comment on the review </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><br>
<br>
I have posted the following patches which fix some of the above
failures by changing SmallPtrSet to SmallSetVector:<br>
<b><a class="m_-4875662011915647096moz-txt-link-freetext" href="https://reviews.llvm.org/D26704" target="_blank">https://reviews.llvm.org/<wbr>D26704</a></b><b><br>
</b><b><a class="m_-4875662011915647096moz-txt-link-freetext" href="https://reviews.llvm.org/D26705" target="_blank">https://reviews.llvm.org/<wbr>D26705</a></b><b><br>
</b><b><a class="m_-4875662011915647096moz-txt-link-freetext" href="https://reviews.llvm.org/D26706" target="_blank">https://reviews.llvm.org/<wbr>D26706</a></b><br>
<br>
Here are the next steps which I would like to do:<br>
1. Replicate this patch for other containers (like DenseMap)<br>
2. Somehow enable reverse iteration in the lit framework for all
tests so that we can uncover these issues quickly<br>
<br>
Please feel free to review my patch for reverse iteration. I would
welcome comments/suggestions for improving/extending the patch and
enabling it in lit.<br>
<br>
Thanks,<br>
Mandeep<br>
<br>
<br>
<br>
</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>