<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=us-ascii">
<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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-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;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
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;}
p.xxmsonormal, li.xxmsonormal, div.xxmsonormal
{mso-style-name:x_xmsonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle22
{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]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">I’ve reported the bug at <a href="https://bugs.llvm.org/show_bug.cgi?id=42965">
https://bugs.llvm.org/show_bug.cgi?id=42965</a><o:p></o:p></p>
<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 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>From:</b> Finkel, Hal J. [mailto:hfinkel@anl.gov] <br>
<b>Sent:</b> Friday, August 9, 2019 20:00<br>
<b>To:</b> Danila Malyutin <Danila.Malyutin@synopsys.com><br>
<b>Cc:</b> llvm-dev@lists.llvm.org; Michael Kruse <llvmdev@meinersbur.de><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;color:black">> I see. So LSR could theoretically counteract undesirable Ind Var transformations but it’s not implemented at the moment?<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p><span style="font-size:12.0pt;color:black">I believe that's correct.<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p><span style="font-size:12.0pt;color:black">> 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=DwMF-g&c=DPL6_X_6JkXFx7AXWqB0tg&r=VEV8gWVf26SDOqiMtTxnBloZmItAauQlSqznsCc0KxY&m=Db9EGiCP80Ab6eLYo3qr3V_HHoGjwa-Pv-6-sixxNUQ&s=SM_9aS7m7NFl6bUVmq31QHKhqVu-33jcfCCWVme1myU&e=">https://godbolt.org/z/_wxzut</a><o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<p><span style="font-size:12.0pt;color:black">Thanks. Can you please file a bug on <a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__bugs.llvm.org_&d=DwMF-g&c=DPL6_X_6JkXFx7AXWqB0tg&r=VEV8gWVf26SDOqiMtTxnBloZmItAauQlSqznsCc0KxY&m=Db9EGiCP80Ab6eLYo3qr3V_HHoGjwa-Pv-6-sixxNUQ&s=b7RsuQp7icCev64E3JFJ8pyVSZ0C0yzzb25ybygRj3Q&e=">https://bugs.llvm.org/</a>?
(if you can't, let us know, and one of us can do it).<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p><span style="font-size:12.0pt;color:black"> -Hal<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<div id="Signature">
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;color:black">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>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<div>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-size:12.0pt;color:black">
<hr size="2" width="98%" align="center">
</span></div>
<div id="divRplyFwdMsg">
<p class="MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> Danila Malyutin <<a href="mailto:Danila.Malyutin@synopsys.com">Danila.Malyutin@synopsys.com</a>><br>
<b>Sent:</b> Friday, August 9, 2019 10:27 AM<br>
<b>To:</b> Finkel, Hal J. <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>>; Michael Kruse <<a href="mailto:llvmdev@meinersbur.de">llvmdev@meinersbur.de</a>><br>
<b>Subject:</b> RE: [llvm-dev] How to best deal with undesirable Induction Variable Simplification?</span><span style="font-size:12.0pt;color:black">
<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
</div>
</div>
<div>
<div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black">Hi Hal,<o:p></o:p></span></p>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black">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=DwMF-g&c=DPL6_X_6JkXFx7AXWqB0tg&r=VEV8gWVf26SDOqiMtTxnBloZmItAauQlSqznsCc0KxY&m=Db9EGiCP80Ab6eLYo3qr3V_HHoGjwa-Pv-6-sixxNUQ&s=SM_9aS7m7NFl6bUVmq31QHKhqVu-33jcfCCWVme1myU&e=">
https://godbolt.org/z/_wxzut</a><o:p></o:p></span></p>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black">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></span></p>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black">--<o:p></o:p></span></p>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black">Danila<o:p></o:p></span></p>
</div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="xmsonormal"><b><span style="font-size:12.0pt;color:black">From:</span></b><span style="font-size:12.0pt;color:black"> Finkel, Hal J. [<a href="mailto:hfinkel@anl.gov">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">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></span></p>
</div>
</div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<div id="x_divtagdefaultwrapper">
<p><span style="font-size:12.0pt;color:black">Hi, Danila,<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black">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.<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black">Regarding the second case, could you post a more-detailed description? I don't quite understand the issue.<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"> -Hal<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<div id="x_Signature">
<div>
<div>
<p class="xmsonormal"><span style="font-size:10.0pt;color:black">Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory</span><span style="font-size:12.0pt;color:black"><o:p></o:p></span></p>
</div>
</div>
</div>
<p class="xmsonormal" style="margin-bottom:12.0pt"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<div>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-size:12.0pt;color:black">
<hr size="2" width="98%" align="center">
</span></div>
<div id="x_divRplyFwdMsg">
<p class="xmsonormal"><b><span style="font-size:12.0pt;color:black">From:</span></b><span style="font-size:12.0pt;color:black"> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org">llvm-dev-bounces@lists.llvm.org</a>> on behalf of Danila Malyutin via
llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">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">llvm-dev@lists.llvm.org</a> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> [llvm-dev] How to best deal with undesirable Induction Variable Simplification?
<o:p></o:p></span></p>
<div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
</div>
</div>
<div>
<div>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">Hello,<br>
Recently I’ve come across two instances where Induction Variable Simplification lead to noticable performance regressions.<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">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:<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">loop {<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black"> p+=n;<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">…<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black"> p+=n;<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">…<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">}<br>
use p.<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">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?<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">--<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black">Danila<o:p></o:p></span></p>
<p class="xxmsonormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>