<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>Everyone,<br>
</p>
<p>The following patch to reverse iterate SmallPtrSet's has now been
merged:<br>
<a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D26718">https://reviews.llvm.org/D26718</a></p>
<p>This is how LLVM behavior will change due to this patch:<br>
- In LLVM builds with <b>assertions enabled</b>, SmallPtrSet's
would always be reverse iterated by default.<br>
This default behavior can be overridden via the flag "-mllvm
-reverse-iterate=<true/false>".<br>
</p>
<p>- In LLVM builds with <b>assertions disabled</b>, SmallPtrSet's
would continue to be always forward iterated.<br>
This behavior cannot be overridden as the above flag is
available only in builds with assertions enabled.</p>
<p>Currently, the following unit tests are failing in
Release+Asserts mode due to the difference in SmallPtrSet
iteration order:<br>
Clang :: Analysis/keychainAPI.m<br>
Clang :: Analysis/malloc.c<br>
Clang :: Rewriter/objc-modern-metadata-visibility.mm<br>
Clang :: SemaCXX/warn-loop-analysis.cpp<br>
LLVM :: Transforms/SimplifyCFG/bug-25299.ll</p>
<p>Next Steps:<br>
I plan to extend this behavior to the iteration of other unordered
containers (like DenseMap, etc).<br>
</p>
<p>Thanks,<br>
Mandeep<br>
</p>
<div class="moz-cite-prefix">On 11/15/2016 3:06 PM, Grang, Mandeep
Singh wrote:<br>
</div>
<blockquote
cite="mid:754d1791-cca8-d48a-e8b9-e9b1c174031c@codeaurora.org"
type="cite">
<meta http-equiv="content-type" content="text/html; charset=utf-8">
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 moz-do-not-send="true" class="moz-txt-link-freetext"
href="https://reviews.llvm.org/D26703">https://reviews.llvm.org/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/objc-modern-metadata-visibility.mm</i><i><br>
</i><i> Clang :: SemaCXX/warn-loop-analysis.cpp</i><i><br>
</i><i> LLVM ::
Transforms/LoopVectorize/consecutive-ptr-uniforms.ll</i><i><br>
</i><i> LLVM :: Transforms/SimplifyCFG/bug-25299.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/cyclicphi.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/many-dom-backedge.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/many-doms.ll</i><i><br>
</i><i> LLVM :: Transforms/Util/MemorySSA/phi-translation.ll</i><br>
<br>
I have posted the following patches which fix some of the above
failures by changing SmallPtrSet to SmallSetVector:<br>
<b><a moz-do-not-send="true" class="moz-txt-link-freetext"
href="https://reviews.llvm.org/D26704">https://reviews.llvm.org/D26704</a></b><b><br>
</b><b><a moz-do-not-send="true" class="moz-txt-link-freetext"
href="https://reviews.llvm.org/D26705">https://reviews.llvm.org/D26705</a></b><b><br>
</b><b><a moz-do-not-send="true" class="moz-txt-link-freetext"
href="https://reviews.llvm.org/D26706">https://reviews.llvm.org/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>
</blockquote>
<br>
</body>
</html>