<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 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 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;}
p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
{mso-style-priority:99;
mso-style-link:"Balloon Text Char";
margin:0in;
margin-bottom:.0001pt;
font-size:8.0pt;
font-family:"Tahoma","sans-serif";}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.BalloonTextChar
{mso-style-name:"Balloon Text Char";
mso-style-priority:99;
mso-style-link:"Balloon Text";
font-family:"Tahoma","sans-serif";}
.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 Mehdi,<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 actually wanted to know how to proceed with fixing all the issues I found.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">I realize now that it wasn’t clear from the wording
</span><span style="font-size:11.0pt;font-family:Wingdings;color:#1F497D">J</span><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"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Thanks for the links though!<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">-Pankaj
<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 #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> mehdi.amini@apple.com [mailto:mehdi.amini@apple.com]
<br>
<b>Sent:</b> Wednesday, July 06, 2016 11:49 AM<br>
<b>To:</b> Chawla, Pankaj<br>
<b>Cc:</b> Sanjoy Das; llvm-dev@lists.llvm.org<br>
<b>Subject:</b> Re: [llvm-dev] Regarding ScalarEvolution's loop backedge computation<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<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 5, 2016, at 6:01 PM, Chawla, Pankaj via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">Hi Sanjoy,<br>
<br>
The following trivial change in howManyLessThans() seems to resolve the problem with the original loop-<br>
<br>
// Avoid negative or zero stride values<br>
- if (!isKnownPositive(Stride))<br>
+ if (!NoWrap && !isKnownPositive(Stride))<br>
return getCouldNotCompute();<br>
<br>
However, I was experimenting with a few variants of the loop I posted and they seem to have different issues which may require more involved fixes. I am listing them here-<br>
<br>
1) Changing the loop control condition from '<' to '<='.<br>
<br>
The canonical form of this loop is something like this-<br>
<br>
if (0 < N) {<br>
i = 0;<br>
do {<br>
a[i]++;<br>
i += s; // NSW add<br>
} while (! (i > N)); // sgt compare<br>
}<br>
<br>
The 'sgt' compare is inverted to 'sle' for analysis. ScalarEvolution isn't really expecting 'sle' in canonicalized loops so it reverts to brute force exit count computation using computeExitCountExhaustively() which doesn't work. This looks like a canonicalization
issue.<br>
<br>
2) Variants with '>' and '>='. For example-<br>
<br>
for(i=n; i>=0; i-=s) {<br>
A[i]++;<br>
}<br>
<br>
In this case the SCEV form of IV does not have 'nsw' flag- <br>
{%n,+,(-1 * %s)}<%for.body><br>
<br>
<br>
For now, I can submit a patch which fixes the issue with the original loop. <br>
Please let me know how to proceed.<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">If you’re asking about how to submit a patch to LLVM, this may help: <a href="http://llvm.org/docs/DeveloperPolicy.html#making-and-submitting-a-patch">http://llvm.org/docs/DeveloperPolicy.html#making-and-submitting-a-patch</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">(And possibly this: <a href="http://llvm.org/docs/Phabricator.html">http://llvm.org/docs/Phabricator.html</a> )<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">— <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Mehdi<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>
<div>
<div>
<p class="MsoNormal"><br>
Thanks,<br>
Pankaj<br>
<br>
-----Original Message-----<br>
From: Chawla, Pankaj <br>
Sent: Thursday, June 30, 2016 12:13 PM<br>
To: 'Sanjoy Das'<br>
Cc: <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
Subject: RE: [llvm-dev] Regarding ScalarEvolution's loop backedge computation<br>
<br>
Hi Sanjoy,<br>
<br>
Thank you for the clarification!<br>
I will give it a try and put up the changes for review.<br>
<br>
-Pankaj<br>
<br>
-----Original Message-----<br>
From: Sanjoy Das [<a href="mailto:sanjoy@playingwithpointers.com">mailto:sanjoy@playingwithpointers.com</a>]
<br>
Sent: Wednesday, June 29, 2016 5:02 PM<br>
To: Chawla, Pankaj<br>
Cc: <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
Subject: Re: [llvm-dev] Regarding ScalarEvolution's loop backedge computation<br>
<br>
Hi Pankaj,<br>
<br>
Chawla, Pankaj via llvm-dev wrote:<br>
<br>
<o:p></o:p></p>
<p class="MsoNormal">It looks like ScalarEvolution bails out of loop backedge computation if > it cannot prove the IV stride as either positive or negative (based on > loop control condition). I think this logic can be refined for signed IVs.<br>
<br>
Consider this simple loop-<br>
<br>
void foo(int *A, int n, int s) {<br>
<br>
int i;<br>
<br>
for(i=0; i<n; i += s) {<br>
<br>
A[i]++;<br>
<br>
}<br>
<br>
}<br>
<br>
The IV of this loop has this SCEV form- > > {0,+,%s}<nsw><%for.body><o:p></o:p></p>
<p class="MsoNormal"><br>
This looks valid -- we already do things like this for<br>
<br>
for (i = A; i != B; i += 5)<br>
...<br>
<br>
and compute the backedge taken count as "(B - A) / 5" (roughly :) ) since if (B - A) is not divisible by 5 then we have UB due to overflow. We just have to be careful around cases like:<br>
<br>
for(i = 0; i < 60; i += s) {<br>
may_exit();<br>
}<br>
<br>
"s" can be (say) -3 and the loop can take 160 backedges and then "exit(0)", avoiding the undefined behavior due to underflow. "s" can also be zero, in which case the loop can potentially take an infinite number of backedges.<br>
<br>
However, in the example you gave (written in LLVM's canonical rotated<br>
form):<br>
<br>
if (0 < N) {<br>
i = 0;<br>
do {<br>
a[i]++;<br>
i += s; // NSW add<br>
} while (i < N);<br>
}<br>
<br>
For any s <= 0 we have undefined behavior, so it is sound to assume s > 0.<br>
<br>
Do you want to take a crack at fixing this? I'm traveling till the 10th of July, but I can review your change once I'm back.<br>
<br>
-- Sanjoy<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</div>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>