<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><br>
</p>
<div class="moz-cite-prefix">On 02/27/2017 12:41 PM, Michael
Kuperstein wrote:<br>
</div>
<blockquote
cite="mid:CAL_y90nvWRN8XyFdcLTNKoLXrVzJCj5nzhFLDzemrYk0jGOitA@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div dir="ltr">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 :-) )
<div><br>
<div>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.</div>
</div>
</div>
</blockquote>
<br>
We should really improve this as well.<br>
<br>
<blockquote
cite="mid:CAL_y90nvWRN8XyFdcLTNKoLXrVzJCj5nzhFLDzemrYk0jGOitA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>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.</div>
</div>
</blockquote>
<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>
-Hal<br>
<br>
<blockquote
cite="mid:CAL_y90nvWRN8XyFdcLTNKoLXrVzJCj5nzhFLDzemrYk0jGOitA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>Michael</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Feb 27, 2017 at 10:11 AM, Hal
Finkel <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</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"><span class="">
<p><br>
</p>
<div class="m_6905833519341383885moz-cite-prefix">On
02/27/2017 11:47 AM, Adam Nemet wrote:<br>
</div>
<blockquote type="cite"> <br>
<div>
<blockquote type="cite">
<div>On Feb 27, 2017, at 9:39 AM, Daniel Berlin
<<a moz-do-not-send="true"
href="mailto:dberlin@dberlin.org"
target="_blank">dberlin@dberlin.org</a>>
wrote:</div>
<br
class="m_6905833519341383885Apple-interchange-newline">
<div>
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Feb 27,
2017 at 9:29 AM, Adam Nemet <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:anemet@apple.com"
target="_blank">anemet@apple.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div style="word-wrap:break-word"><br>
<div><span
class="m_6905833519341383885gmail-">
<blockquote type="cite">
<div>On Feb 27, 2017, at 7:27
AM, Hal Finkel <<a
moz-do-not-send="true"
href="mailto:hfinkel@anl.gov"
target="_blank">hfinkel@anl.gov</a>>
wrote:</div>
<br
class="m_6905833519341383885gmail-m_8239107560126363242Apple-interchange-newline">
<div>
<div
class="m_6905833519341383885gmail-m_8239107560126363242moz-cite-prefix"
style="font-family:helvetica;font-size:10px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)"><br
class="m_6905833519341383885gmail-m_8239107560126363242Apple-interchange-newline">
On 02/27/2017 06:29 AM,
Nema, Ashutosh wrote:<br>
</div>
<blockquote type="cite"
style="font-family:helvetica;font-size:10px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)">
<div
class="m_6905833519341383885gmail-m_8239107560126363242WordSection1">
<div>Thanks for looking
into this.</div>
<div> </div>
<div>1) Issues with re
running vectorizer:</div>
<div>Vectorizer might
generate redundant alias
checks while vectorizing
epilog loop.</div>
<div>Redundant alias
checks are expensive, we
like to reuse the
results of already
computed alias checks.</div>
<div>With metadata we can
limit the width of
epilog loop, but not
sure about reusing alias
check result.</div>
<div>Any thoughts on
rerunning vectorizer
with reusing the alias
check result ?</div>
</div>
</blockquote>
<br
style="font-family:helvetica;font-size:10px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)">
<span
style="font-family:helvetica;font-size:10px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);float:none;display:inline">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><br
style="font-family:helvetica;font-size:10px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)">
</div>
</blockquote>
<div><br>
</div>
</span>
<div>+Danny</div>
<div><br>
</div>
<div>Isn’t Extended SSA supposed to
help with this?</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>Yes, it will solve this with no issue
already. GVN probably does already too.</div>
<div><br>
</div>
<div>even if if you have</div>
<div><br>
</div>
<div>if (a == b)</div>
<div>
<div>if (a == c)</div>
</div>
<div>
<div> if (a == d)</div>
</div>
<div>
<div> if (a == e)</div>
</div>
<div>
<div> if (a == g)</div>
</div>
<div><br>
</div>
<div><br>
</div>
<div>and we can prove a ... g equivalent,
newgvn will eliminate them all and set
all the branches true.</div>
<div><br>
</div>
<div>If you need a simpler clean up pass,
we could run it on sub-graphs.</div>
</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>Yes we probably don’t want to run a full GVN
after the “loop-scheduling” passes.</div>
</div>
</blockquote>
<br>
</span> 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
class="HOEnZb"><font color="#888888"><br>
<br>
-Hal</font></span><span class=""><br>
<br>
<blockquote type="cite">
<div>
<div><br>
</div>
<div>I guess the pipeline to experiment with for now
is opt -loop-vectorize -loop-vectorize -newgvn.</div>
<div><br>
</div>
<div>Adam</div>
<br>
<blockquote type="cite">
<div>
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div>The only thing you'd have to do is
write some code to set "live on entry"
subgraph variables in their own
congruence classes.</div>
<div>We already do this for incoming
arguments.</div>
<div><br>
</div>
<div>Otherwise, it's trivial to make it
only walk things in the subgraph.</div>
<div><br>
</div>
<div><br>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</blockquote>
<br>
</span><span class="">
<pre class="m_6905833519341383885moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</span></div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>