<html>
<head>
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>I'd be happy to review a patch, but you need to make sure you
have buy in from the original patch author. I'm not entirely sure
of the licensing implications of you submitting someone elses
code, so it's best to avoid the discussion if we can. (If anyone
can give a conclusive answer here, please chime in.)<br>
</p>
<p>Philip<br>
</p>
<div class="moz-cite-prefix">On 8/16/19 6:44 AM, Danila Malyutin
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:MN2PR12MB38405C247E03648FC7C175A7B8AF0@MN2PR12MB3840.namprd12.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<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:"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:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
p.xmsonormal, li.xmsonormal, div.xmsonormal
{mso-style-name:x_msonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
color:black;}
span.EmailStyle22
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle23
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle24
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:56.7pt 42.5pt 56.7pt 85.05pt;}
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]-->
<div class="WordSection1">
<p class="MsoNormal"><span style="color:windowtext">Thanks. I’ve
rebased this patch on top of the recent LLVM (it was
straightforward) and applied it in my fork.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:windowtext">It seems to
have solved one of the problems I was having. Would LLVM be
interested if I submit the updated version for the review?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:windowtext"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span style="color:windowtext">--<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:windowtext">Danila<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="color:windowtext"><o:p> </o:p></span></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 #E1E1E1
1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="color:windowtext">From:</span></b><span
style="color:windowtext"> Philip Reames
[<a class="moz-txt-link-freetext" href="mailto:listmail@philipreames.com">mailto:listmail@philipreames.com</a>]
<br>
<b>Sent:</b> Tuesday, August 13, 2019 19:01<br>
<b>To:</b> Danila Malyutin
<a class="moz-txt-link-rfc2396E" href="mailto:Danila.Malyutin@synopsys.com"><Danila.Malyutin@synopsys.com></a>; Finkel, Hal J.
<a class="moz-txt-link-rfc2396E" href="mailto:hfinkel@anl.gov"><hfinkel@anl.gov></a><br>
<b>Cc:</b> <a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [llvm-dev] How to best deal with
undesirable Induction Variable Simplification?<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p>Wasn't aware of this patch. No, I don't see an obvious
reason why it wasn't followed up on.<o:p></o:p></p>
<p>Philip<o:p></o:p></p>
<div>
<p class="MsoNormal">On 8/13/19 8:25 AM, Danila Malyutin
wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span style="color:windowtext">I’ve
noticed that there was an attempt to mitigate ExitValues
problem in
<a
href="https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D12494&d=DwMD-g&c=DPL6_X_6JkXFx7AXWqB0tg&r=VEV8gWVf26SDOqiMtTxnBloZmItAauQlSqznsCc0KxY&m=dG9EWNnpejxa8ub7_ajgnN50pG20wvSyA7WI9jWEv2Q&s=XRJmqJsGpSvBiRcYTKFYc_m94KMv3dQ6FFLsfF7GR1Y&e="
moz-do-not-send="true">
https://reviews.llvm.org/D12494</a> that went nowhere.
Were there particular issues with that approach?</span><o:p></o:p></p>
<p class="MsoNormal"><span style="color:windowtext"> </span><o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="color:windowtext">--</span><o:p></o:p></p>
<p class="MsoNormal"><span style="color:windowtext">Danila</span><o:p></o:p></p>
</div>
<p class="MsoNormal"><span style="color:windowtext"> </span><o:p></o:p></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 #E1E1E1
1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="color:windowtext">From:</span></b><span
style="color:windowtext"> Philip Reames [<a
href="mailto:listmail@philipreames.com"
moz-do-not-send="true">mailto:listmail@philipreames.com</a>]
<br>
<b>Sent:</b> Saturday, August 10, 2019 02:05<br>
<b>To:</b> Danila Malyutin <a
href="mailto:Danila.Malyutin@synopsys.com"
moz-do-not-send="true"><Danila.Malyutin@synopsys.com></a>;
Finkel, Hal J.
<a href="mailto:hfinkel@anl.gov"
moz-do-not-send="true"><hfinkel@anl.gov></a><br>
<b>Cc:</b> <a
href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [llvm-dev] How to best deal
with undesirable Induction Variable
Simplification?</span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"> <o:p></o:p></p>
<p> <o:p></o:p></p>
<div>
<p class="MsoNormal">On 8/9/19 8:27 AM, Danila Malyutin
via llvm-dev wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal">Hi Hal,<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">I see. So LSR could theoretically
counteract undesirable Ind Var transformations but
it’s not implemented at the moment?<br>
<br>
I think I’ve managed to come up with a small
reproducer that can also exhibit similar problem on
x86, here it is:
<a
href="https://urldefense.proofpoint.com/v2/url?u=https-3A__godbolt.org_z_-5Fwxzut&d=DwMD-g&c=DPL6_X_6JkXFx7AXWqB0tg&r=VEV8gWVf26SDOqiMtTxnBloZmItAauQlSqznsCc0KxY&m=xzJTtah1fNUz56fRe1yh10OCSBFg7IbzUhFcn8BPyJk&s=-qhi7IRwOrqjcv_cxlhP6lbVWspNKWeDT4amCIHR1sU&e="
moz-do-not-send="true">
https://godbolt.org/z/_wxzut</a><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">As you can see, when
rewriteLoopExitValues is not disabled Clang generates
worse code due to additional spills, because Ind Vars
rewrites all exit values of ‘a’ to recompute it’s
value instead of reusing the value from the loop body.
This requires extra registers for the new “a after the
loop” value (since it’s not simply reused) and also to
store the new “offset”, which leads to the extra
spills since they all live across big loop body. When
exit values are not rewritten ‘a’ stays in it’s `r15d`
register with no extra costs.<o:p></o:p></p>
</blockquote>
<p>This hits on a point I've thought some about, but
haven't tried to implement.<o:p></o:p></p>
<p>I think there might be room for a late pass which
undoes the exit value rewriting. As an analogy, we have
MachineLICM which sometimes undoes the transforms
performed by LICM, but we still want the IR form to
hoist aggressively for ease of optimization and
analysis. <o:p></o:p></p>
<p>Maybe this should be part of LSR, or maybe separate.
Haven't thought about that part extensively.<o:p></o:p></p>
<p>It's worth noting that the SCEVs for the exit value of
the value inside the loop and the rewritten exit value
should be identical. So recognizing the case for
potential rewriting is quite straight-forward. The
profitability reasoning might be more involved, but the
legality part should essentially be handled by SCEV, and
should be able to reuse exactly the same code as RLEV.
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"> <o:p></o:p></p>
<div>
<p class="MsoNormal">--<o:p></o:p></p>
<p class="MsoNormal">Danila<o:p></o:p></p>
</div>
<p class="MsoNormal"> <o:p></o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1
1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> Finkel, Hal J. [<a
href="mailto:hfinkel@anl.gov"
moz-do-not-send="true">mailto:hfinkel@anl.gov</a>]
<br>
<b>Sent:</b> Thursday, August 8, 2019 21:24<br>
<b>To:</b> Danila Malyutin <a
href="mailto:Danila.Malyutin@synopsys.com"
moz-do-not-send="true"><Danila.Malyutin@synopsys.com></a><br>
<b>Subject:</b> Re: [llvm-dev] How to best deal
with undesirable Induction Variable
Simplification?<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"> <o:p></o:p></p>
<div id="divtagdefaultwrapper">
<p><span style="font-size:12.0pt">Hi, Danila,</span><o:p></o:p></p>
<p><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p><span style="font-size:12.0pt">Regarding the first
case, this is certainly a problem that has come up
before. As I recall, and I believe this is still
true, LoopStrengthReduce, where we reason about
induction variables while accounting for register
pressure, won't currently add new PHIs. People
have talked about extending LSR to consider adding
new PHIs in the past.</span><o:p></o:p></p>
<p><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p><span style="font-size:12.0pt">Regarding the second
case, could you post a more-detailed description?
I don't quite understand the issue.</span><o:p></o:p></p>
<p><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p><span style="font-size:12.0pt"> -Hal</span><o:p></o:p></p>
<p><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<div id="Signature">
<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</span><o:p></o:p></p>
</div>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span
style="font-size:12.0pt"> </span><o:p></o:p></p>
<div>
<div class="MsoNormal" style="text-align:center"
align="center"><span style="font-size:12.0pt">
<hr width="98%" size="2" align="center">
</span></div>
<div id="divRplyFwdMsg">
<p class="MsoNormal"><b>From:</b> llvm-dev <<a
href="mailto:llvm-dev-bounces@lists.llvm.org"
moz-do-not-send="true">llvm-dev-bounces@lists.llvm.org</a>>
on behalf of Danila Malyutin via llvm-dev <<a
href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>><br>
<b>Sent:</b> Thursday, August 8, 2019 12:36 PM<br>
<b>To:</b> <a
href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>
<<a href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> [llvm-dev] How to best deal with
undesirable Induction Variable Simplification?<span
style="font-size:12.0pt">
</span><o:p></o:p></p>
<div>
<p class="MsoNormal"><span
style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="xmsonormal"><span
style="font-size:12.0pt">Hello,<br>
Recently I’ve come across two instances
where Induction Variable Simplification lead
to noticable performance regressions.</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt">In one case, the
removal of extra IV lead to the inability to
reschedule instructions in a tight loop to
reduce stalls. In that case, there were
enough registers to spare, so using extra
register for extra induction variable was
preferable since it reduced dependencies in
the loop.<br>
In the second case, there was a big nested
loop made even bigger after unswitching.
However, the inner loop body was rather
simple, of the form:</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt">loop {</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt"> p+=n;</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt">…</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt"> p+=n;</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt">…</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt">}<br>
use p.</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt">Due to unswitching
there were several such loops each with the
different number of p+=n ops, so when the
IndVars pass rewrote all exit values, it
added a lot of slightly different offsets to
the main loop header that couldn’t fit in
the available registers which lead to
unnecessary spills/reloads.<br>
<br>
I am wondering what is the usual strategy
for dealing with such “pessimizations”? Is
it possible to somehow modify the
IndVarSimplify pass to take those issues
into account (for example, tell it that
adding offset computation + gep is
potentially more expensive than simply
reusing last var from the loop) or should it
be recovered in some later pass? If so, is
there an easy way to revert IV elimination?
Have anyone dealt with similar issues
before?</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt">--</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt">Danila</span><o:p></o:p></p>
<p class="xmsonormal"><span
style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><br>
<br>
<br>
<o:p></o:p></p>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>LLVM Developers mailing list<o:p></o:p></pre>
<pre><a href="mailto:llvm-dev@lists.llvm.org" moz-do-not-send="true">llvm-dev@lists.llvm.org</a><o:p></o:p></pre>
<pre><a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwMD-g&c=DPL6_X_6JkXFx7AXWqB0tg&r=VEV8gWVf26SDOqiMtTxnBloZmItAauQlSqznsCc0KxY&m=xzJTtah1fNUz56fRe1yh10OCSBFg7IbzUhFcn8BPyJk&s=yx8qR1CqElqmkWtFEZai6IE4tZr66rXpt7QYSVvsv6Q&e=" moz-do-not-send="true">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></pre>
</blockquote>
</div>
</blockquote>
</div>
</div>
</blockquote>
</body>
</html>