<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman","serif";
color:black;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body bgcolor="white" lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Do you have fixes for all of these problems ready to go? If not, please make the flag off by default always.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">You can put it back to default-on for Release+Asserts after all the problems are fixed.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">--paulr<o:p></o:p></span></p>
<p class="MsoNormal"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></a></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:windowtext"> llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Grang, Mandeep Singh via llvm-dev<br>
<b>Sent:</b> Tuesday, December 13, 2016 4:58 PM<br>
<b>To:</b> llvm-dev@lists.llvm.org; zinob@codeaurora.org<br>
<b>Subject:</b> Re: [llvm-dev] Non-determinism in LLVM codegen<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p>Everyone,<o:p></o:p></p>
<p>The following patch to reverse iterate SmallPtrSet's has now been merged:<br>
<a href="https://reviews.llvm.org/D26718">https://reviews.llvm.org/D26718</a><o:p></o:p></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>".<o:p></o:p></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.<o:p></o:p></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<o:p></o:p></p>
<p>Next Steps:<br>
I plan to extend this behavior to the iteration of other unordered containers (like DenseMap, etc).<o:p></o:p></p>
<p>Thanks,<br>
Mandeep<o:p></o:p></p>
<div>
<p class="MsoNormal">On 11/15/2016 3:06 PM, Grang, Mandeep Singh wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="margin-bottom:12.0pt">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 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<br>
Clang :: Analysis/malloc.c<br>
Clang :: Rewriter/objc-modern-metadata-visibility.mm<br>
Clang :: SemaCXX/warn-loop-analysis.cpp<br>
LLVM :: Transforms/LoopVectorize/consecutive-ptr-uniforms.ll<br>
LLVM :: Transforms/SimplifyCFG/bug-25299.ll<br>
LLVM :: Transforms/Util/MemorySSA/cyclicphi.ll<br>
LLVM :: Transforms/Util/MemorySSA/many-dom-backedge.ll<br>
LLVM :: Transforms/Util/MemorySSA/many-doms.ll<br>
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 href="https://reviews.llvm.org/D26704">https://reviews.llvm.org/D26704</a><br>
<a href="https://reviews.llvm.org/D26705">https://reviews.llvm.org/D26705</a><br>
<a 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>
<o:p></o:p></p>
</blockquote>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>