<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)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 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:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
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:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman",serif;
color:black;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
span.m6905833519341383885gmail-
{mso-style-name:m_6905833519341383885gmail-;}
span.hoenzb
{mso-style-name:hoenzb;}
span.EmailStyle22
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle23
{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:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
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" style="margin-left:36.0pt">On 02/27/2017 04:19 PM, Zaks, Ayal wrote:<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="margin-left:72.0pt">On 02/27/2017 12:41 PM, Michael Kuperstein wrote:<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-left:72.0pt">There's another issue with re-running the vectorizer (which I support, btw - I'm just saying there are more problems to solve on the way :-) )
<o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">Historically, we haven't even tried to evaluate the cost of the "constant" (not per-iteration) vectorization overhead - things like alias checks. Instead, we have hard bounds - we won't perform alias checks that
are "too expensive", and, more importantly, we don't even try to vectorize loops with known low iteration counts. The bound right now is 16, IIRC. That means we don't have a good way to evaluate whether vectorizing a loop with a low iteration count is profitable
or not.<o:p></o:p></p>
</div>
</div>
</div>
</blockquote>
<p class="MsoNormal" style="margin-left:72.0pt"><br>
We should really improve this as well.<br>
<br>
<br>
<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">@Michael: OTOH, we should reach the same decision again (i.e., that of performing the alias checks) when encountering the remainder
loop as we did with the original loop, given that hard bounds are used ;-).</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">But agreed, it is better to evaluate the cost of these bounds along with the overall estimated cost instead.</span><o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">This also makes me wary of the "we can clean up redundant alias checks later" approach. When trying to decide whether to vectorize by 4 a loop that has no more than 8 iterations (because we just vectorized by
8 and it's the remainder loop), we really want to know if the alias checks we're introducing are going to survive a not.<o:p></o:p></p>
</div>
</div>
</blockquote>
<p class="MsoNormal" style="margin-left:72.0pt"><br>
It occurs to me that, if SCEV's known-predicate logic were smart enough, it would seem practical to not introduce redundant checks in the first place (although it would imply some gymnastics when examining the control flow around the loop and then restructuring
things when we generate the code for the loop).<br>
<br>
<br>
<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">The scalar remainder loop, when reached from the vectorized loop, is already known to be vectorizable to a VF larger than EpilogVF.</span><o:p></o:p></p>
</blockquote>
<p class="MsoNormal" style="margin-left:36.0pt"><br>
I was not under the impression we had a remainder loop separate from the loop used for scalar computation. Don't we use the same loop in cases where the vectorization is not legal?<br>
<br>
<span style="color:#1F497D"><o:p></o:p></span></p>
<pre><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">We sure do. That’s why this vectorizability property is path-sensitive, as in “when reached” above and “except that” below. See also “</span>o The scalar loop serves two purposes…<span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">” aspect raised earlier.</span><o:p></o:p></pre>
<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">Ayal.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:36.0pt"><br>
-Hal<br>
<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">No need to introduce again any potential aliasing, wrapping or whatnot checks, even if this redundancy can later be eliminated, if
instead this vectorizability property could be recorded somehow. Similar to having annotated the remainder loop with “#pragma clang loop vectorize(assume_safety)”, except that this vectorizability property does not hold when reaching the remainder loop along
the other path – that which fails these checks for the main loop...</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Ayal.</span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:72.0pt"><br>
-Hal<br>
<br>
<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">Michael<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">On Mon, Feb 27, 2017 at 10:11 AM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-right:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<p style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">On 02/27/2017 11:47 AM, Adam Nemet wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-left:72.0pt">On Feb 27, 2017, at 9:39 AM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">On Mon, Feb 27, 2017 at 9:29 AM, Adam Nemet <<a href="mailto:anemet@apple.com" target="_blank">anemet@apple.com</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-right:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-left:72.0pt">On Feb 27, 2017, at 7:27 AM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt;background:white"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif"><br>
On 02/27/2017 06:29 AM, Nema, Ashutosh wrote:</span><o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt;font-variant-caps:normal;text-align:start;word-spacing:0px">
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt;background:white"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif">Thanks for looking into this.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt;background:white"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt;background:white"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif">1) Issues with re running vectorizer:</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt;background:white"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif">Vectorizer might generate redundant alias checks while vectorizing epilog loop.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt;background:white"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif">Redundant alias checks are expensive, we like to reuse the results of already computed alias checks.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt;background:white"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif">With metadata we can limit the width of epilog loop, but not sure about reusing alias check result.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt;background:white"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif">Any thoughts on rerunning vectorizer with reusing the alias check result ?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<p class="MsoNormal" style="margin-left:72.0pt"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif"><br>
<span style="background:white">One way of looking at this is: Reusing the alias-check result is really just a conditional propagation problem; if we don't already have an optimization that can combine these after the fact, then we should.</span></span><o:p></o:p></p>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">+Danny<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">Isn’t Extended SSA supposed to help with this?<o:p></o:p></p>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">Yes, it will solve this with no issue already. GVN probably does already too.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">even if if you have<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">if (a == b)<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">if (a == c)<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> if (a == d)<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> if (a == e)<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> if (a == g)<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">and we can prove a ... g equivalent, newgvn will eliminate them all and set all the branches true.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">If you need a simpler clean up pass, we could run it on sub-graphs.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">Yes we probably don’t want to run a full GVN after the “loop-scheduling” passes.<o:p></o:p></p>
</div>
</div>
</blockquote>
<p class="MsoNormal" style="margin-left:72.0pt"><br>
FWIW, we could, just without the memory-dependence analysis enabled (i.e. set the NoLoads constructor parameter to true). GVN is pretty fast in that mode.<span style="color:#888888"><br>
<br>
<span class="hoenzb"> -Hal</span></span><br>
<br>
<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">I guess the pipeline to experiment with for now is opt -loop-vectorize -loop-vectorize -newgvn.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">Adam<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-left:72.0pt"><br>
<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">The only thing you'd have to do is write some code to set "live on entry" subgraph variables in their own congruence classes.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">We already do this for incoming arguments.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt">Otherwise, it's trivial to make it only walk things in the subgraph.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</blockquote>
<p class="MsoNormal" style="margin-left:72.0pt"><br>
<br>
<br>
<o:p></o:p></p>
<pre style="margin-left:72.0pt">-- <o:p></o:p></pre>
<pre style="margin-left:72.0pt">Hal Finkel<o:p></o:p></pre>
<pre style="margin-left:72.0pt">Lead, Compiler Technology and Programming Languages<o:p></o:p></pre>
<pre style="margin-left:72.0pt">Leadership Computing Facility<o:p></o:p></pre>
<pre style="margin-left:72.0pt">Argonne National Laboratory<o:p></o:p></pre>
</div>
</blockquote>
</div>
<p class="MsoNormal" style="margin-left:72.0pt"> <o:p></o:p></p>
</div>
</blockquote>
<p class="MsoNormal" style="margin-left:72.0pt"><br>
<br>
<br>
<o:p></o:p></p>
<pre style="margin-left:72.0pt">-- <o:p></o:p></pre>
<pre style="margin-left:72.0pt">Hal Finkel<o:p></o:p></pre>
<pre style="margin-left:72.0pt">Lead, Compiler Technology and Programming Languages<o:p></o:p></pre>
<pre style="margin-left:72.0pt">Leadership Computing Facility<o:p></o:p></pre>
<pre style="margin-left:72.0pt">Argonne National Laboratory<o:p></o:p></pre>
<p style="margin-left:36.0pt">---------------------------------------------------------------------<br>
Intel Israel (74) Limited<o:p></o:p></p>
<p style="margin-left:36.0pt">This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.<o:p></o:p></p>
</blockquote>
<p class="MsoNormal" style="margin-left:36.0pt"><br>
<br>
<o:p></o:p></p>
<pre style="margin-left:36.0pt">-- <o:p></o:p></pre>
<pre style="margin-left:36.0pt">Hal Finkel<o:p></o:p></pre>
<pre style="margin-left:36.0pt">Lead, Compiler Technology and Programming Languages<o:p></o:p></pre>
<pre style="margin-left:36.0pt">Leadership Computing Facility<o:p></o:p></pre>
<pre style="margin-left:36.0pt">Argonne National Laboratory<o:p></o:p></pre>
</div>
<p>---------------------------------------------------------------------<br>
Intel Israel (74) Limited</p>
<p>This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</p></body>
</html>