<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:"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: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.apple-converted-space
{mso-style-name:apple-converted-space;}
span.EmailStyle18
{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: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">Hi,<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">Thanks a lot for the replies.<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">As I said in my previous email, I got LSR to work on my multiply nested loop example (which I think has optimization opportunities even in outer loops) by ignoring
LSRUses with no associated formulae. The code generated is functionally correct, but runs slower.<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">I think there are rewriter issues that need to be fixed to get rid of the performance problems. We have manually created code with LSR working for outer loops
which gives good performance. I guess I can compare the two pieces of code to identify the performance issues in LLVM generated code.<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">Regards,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Venu.<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>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><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"> qcolombet@apple.com [mailto:qcolombet@apple.com]
<br>
<b>Sent:</b> Thursday, August 03, 2017 12:19 AM<br>
<b>To:</b> Raghavan, Venugopal <Venugopal.Raghavan@amd.com><br>
<b>Cc:</b> llvm-dev@lists.llvm.org; Madhur Amilkanthwar <madhur13490@gmail.com><br>
<b>Subject:</b> Re: [llvm-dev] LLVM's loop strength reduction module<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Hi,<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On Jul 31, 2017, at 1:15 AM, Raghavan, Venugopal <<a href="mailto:Venugopal.Raghavan@amd.com">Venugopal.Raghavan@amd.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hi,</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Sorry I took a long time to reply as it took me some time to get some understanding of the code even to ask some specific questions (I have a test case in which
LSR does not kick in and wanted to understand the code to figure out why it was not kicking in).</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Here are some specific questions I have:</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">1)</span><span style="font-size:7.0pt;color:#1F497D"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">It
appears that LSR works only for the inner-most loop. Is this correct?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Yes, that is correct.<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Can you tell me why this is so?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"> The rationale was that supporting outer-loops complicates the whole implementation whereas most of the performance gain are within the inner-most loop. Therefore we decided it was not worth the complexity.<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">I believe SCEV works for nested loops, right?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I believe that is correct.<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">2)</span><span style="font-size:7.0pt;color:#1F497D"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Can
LSR work for those LSR uses in a nested loop whose associated formulae themselves do not span multiple loops, ie. the formulae do not have references to loops other that the one that is being processed currently?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">In theory, yes.<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Of course, we first need to get rid of the checks which currently restrict LSR only to the innermost loop</span><o:p></o:p></p>
</div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">3)</span><span style="font-size:7.0pt;color:#1F497D"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Why
do we compute “chains” upfront in the CollectChains() function and then generate all the LSR uses with the associated formulae, prune the formulae, compute the solution and then finally refer to the chains computed in the first step to implement the solution?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">That’s a very good question!<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">I believe this is a historical accident before the time we started to prune the search space. We could probably be smarter here.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Can the chains somehow drive the LSR use and formulae generation process to restrict the latter to only those that are “interesting”
for the chains computed?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">4)</span><span style="font-size:7.0pt;color:#1F497D"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">I
may have mis-understood the code, but it seems that the function SolveRecurse() succeeds in computing a solution only if every LSR use has at least one formula associated with it. For example, if all the formulae associated with an LSR use get filtered away,
it appears that the SolveRecurse() function would not compute a solution and instead say “No Satisfactory Solution”. In my example, an LSR use has all the formulae associated with it filtered away as they are all “loser” formulae and I do not get a solution
from the SolveRecurse() function. Is it correct for the SolveRecurse() function to ignore LSR uses without any associated formulae and come up with a solution that involves the other LSR uses?
</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">That is correct.<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Maybe, this will create an inefficient solution, but would it create an incorrect solution?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I believe the rewriter logic is not ready for that, so that would be incorrect, but if we solve that would just be inefficient.<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Right now, SolveRecurse() seems to take an all-or-nothing approach. My apologies if I have completely mis-understood the concepts of
LSR use and formulae but I am just trying to understand all this from the code and that is proving very difficult to do</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">5)</span><span style="font-size:7.0pt;color:#1F497D"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Given
the current implementation in SolveRecurse() function, why not check if there are LSR uses with no associated formulae and not even execute the SolveRecurse() function? This would avoid some compile time overhead, wouldn’t? SolveRecurse() does not need to
be called if an LSR use has an empty formulae set associated with it because even if you called it you would not get a solution from it, right?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal">That’s correct too.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Though I would have expected we reject those cases earlier.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Cheers,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">-Quentin<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Thanks.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Regards,</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Venugopal Raghavan</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<div>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span class="apple-converted-space"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> </span></span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><a href="mailto:qcolombet@apple.com">qcolombet@apple.com</a>
[<a href="mailto:qcolombet@apple.com">mailto:qcolombet@apple.com</a>]<span class="apple-converted-space"> </span><br>
<b>Sent:</b><span class="apple-converted-space"> </span>Friday, July 07, 2017 2:16 AM<br>
<b>To:</b><span class="apple-converted-space"> </span>Raghavan, Venugopal <<a href="mailto:Venugopal.Raghavan@amd.com">Venugopal.Raghavan@amd.com</a>><br>
<b>Cc:</b><span class="apple-converted-space"> </span><a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>; Madhur Amilkanthwar <<a href="mailto:madhur13490@gmail.com">madhur13490@gmail.com</a>><br>
<b>Subject:</b><span class="apple-converted-space"> </span>Re: [llvm-dev] LLVM's loop strength reduction module</span><o:p></o:p></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Hi Raghavan,<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">I concur no specific docs.<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">What do you want to know specifically?<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">Cheers,<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">-Quentin<o:p></o:p></p>
</div>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal">On Jul 5, 2017, at 11:16 PM, Madhur Amilkanthwar via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org"><span style="color:purple">llvm-dev@lists.llvm.org</span></a>> wrote:<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<div>
<div>
<p class="MsoNormal">AFAIK, no official doc.<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal">You can probably get better help if you ask specific questions (which part of the code you don't understand).<o:p></o:p></p>
</div>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal">On Thu, Jul 6, 2017 at 9:53 AM, Raghavan, Venugopal via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><span style="color:purple">llvm-dev@lists.llvm.org</span></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-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<div>
<p class="MsoNormal">Hi,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">My name is Venugopal Raghavan and I work in AMD. I was trying to understand the code in the file LoopStrengthReduce.cpp but I am making very slow progress.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Is there any additional documentation available that would help me understand the code, like a PPT presentation or a design document or maybe a paper? I did not find anything on the Internet.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">There are comments interspersed in the code which are helpful but don’t seem sufficient for me to get a good understanding of the code.<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">Regards,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Venu.<o:p></o:p></p>
</div>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org"><span style="color:purple">llvm-dev@lists.llvm.org</span></a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank"><span style="color:purple">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></a><o:p></o:p></p>
</blockquote>
</div>
<div>
<p class="MsoNormal"><br>
<br clear="all">
<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal">--<span class="apple-converted-space"> </span><o:p></o:p></p>
</div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><i><span style="font-size:9.5pt">Disclaimer: Views, concerns, thoughts, questions, ideas expressed in this mail are of my own and my employer has no take in it. </span></i><o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">Thank You.<br>
Madhur D. Amilkanthwar<o:p></o:p></p>
</div>
</div>
</div>
</div>
<div>
<p class="MsoNormal">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org"><span style="color:purple">llvm-dev@lists.llvm.org</span></a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"><span style="color:purple">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></a><o:p></o:p></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>