<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 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:"MS Mincho";
panose-1:2 2 6 9 4 2 5 8 3 4;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"\@MS Mincho";
panose-1:2 2 6 9 4 2 5 8 3 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
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;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@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 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"><o:p> </o:p></span></p>
<p class="MsoNormal">>I can file a bug, no problem<span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><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>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Scott, Thanks. Please do. Feel free to assign it to me.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hideki<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><a name="_____replyseparator"></a><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Scott Manley [mailto:rscottmanley@gmail.com]
<br>
<b>Sent:</b> Thursday, May 02, 2019 4:56 PM<br>
<b>To:</b> Finkel, Hal J. <hfinkel@anl.gov><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org>; Craig Topper <craig.topper@gmail.com>; Saito, Hideki <hideki.saito@intel.com><br>
<b>Subject:</b> Re: [llvm-dev] llvm is illegally vectorizing with a recurrence on skylake<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">I can file a bug, no problem. I've just seen folks start on the list first.<br>
<br>
Cheers,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">Scott<br>
<br>
<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal">On Thu, May 2, 2019, 6:53 PM Finkel, Hal J. <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:black">Hi, Scott,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:black">Thanks for reporting this problem. We should get a bug filed on this issue at
<a href="http://bugs.llvm.org" target="_blank">bugs.llvm.org</a>. If you're not able to do this, please let us know, and someone else can take care of it.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:black"> -Hal<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div id="m_8185090449683026643Signature">
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory<o:p></o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="98%" align="center">
</div>
<div id="m_8185090449683026643divRplyFwdMsg">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:black">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:black"> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a>>
on behalf of Scott Manley via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Sent:</b> Thursday, May 2, 2019 4:14 PM<br>
<b>To:</b> llvm-dev<br>
<b>Subject:</b> [llvm-dev] llvm is illegally vectorizing with a recurrence on skylake</span>
<o:p></o:p></p>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal">Hi -- I have found a bug in an HPC code where llvm is vectorizing a loop on Skylake that has an obvious recurrence. I derived a small test case based on the original benchmark below:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">/*****************************************************************/<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal">static void __attribute__ ((always_inline)) one(<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> const int *restrict in, const int *const end,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> const unsigned shift, int *const restrict index,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int *const restrict out)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">{<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> do {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int a_idx = *in>>shift;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int b_idx = index[a_idx]; <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> out[b_idx] = *in; // <-- reccurence as index[a_idx] can be the<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> index[a_idx]++; // same and incremented within the vector<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> } while(++in!=end); // which leads to incorrect results<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">#ifndef NO_TWO<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">static void __attribute__ ((noinline)) two(<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> const int *restrict in, const int *const end,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> const unsigned shift, int *const restrict index,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int *const restrict out)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">{<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> do out[index[(*in>>shift)]++]=*in; while(++in!=end);<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">#endif<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">void parent(<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int digits, int n, int *restrict work, int * restrict idx,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int *restrict shift, int **restrict indicies)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">{<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int *in = work;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int *dst = work+n;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">// int *indicies[1024];<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">// int shift[1024];<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int d;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> for(d=1;d!=digits-1;++d) {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> int *t;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> one(in,in+n,shift[d],indicies[d],dst);<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> t=in,in=dst,dst=t;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">#ifndef NO_TWO<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> two(in,in+n,shift[d],indicies[d],idx);<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">#endif<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal">/*****************************************************************/<o:p></o:p></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><br>
clang -S -O2 -Rpass=loop-vectorize small.c -march=skylake-avx512<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">small.c:6:3: remark: vectorized loop (vectorization width: 16, interleaved count: 1) [-Rpass=loop-vectorize]<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> do {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> ^<o:p></o:p></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I believe the problem to be a issue with dependency information getting destroyed because if you remove the two() function (or compile one() on its own, or prevent inlining of one()), it correctly prevents vectorization. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal">clang -S -O2 -Rpass=loop-vectorize -Rpass-missed=loop-vectorize small.c -march=skylake-avx512 -DNO_TWO<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">small.c:6:3: remark: loop not vectorized [-Rpass-missed=loop-vectorize]<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> do {<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I did trace it down to possibly being something within DepChecker->areDepsSafe() as it returns true for the incorrect case.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Scott<o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</body>
</html>