<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 14 (filtered medium)">
<style><!--
/* Font Definitions */
@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;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@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">Hi all,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">It looks like the induction variable simplification pass prefers doing a zero-extension to compute the wider trip count of loops when extending the IV. This can sometimes result in loss of information making ScalarEvolution’s analysis conservative
which can lead to missed performance opportunities.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">For example, consider this loopnest-<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> int i, j; <o:p></o:p></p>
<p class="MsoNormal"> for(i=0; i< 40; i++)<o:p></o:p></p>
<p class="MsoNormal"> for(j=0; j< i-1; j++)<o:p></o:p></p>
<p class="MsoNormal"> A[i+j] = j;<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">We are mainly interested in the backedge taken count of the inner loop.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Before indvars, the backedge information computed by ScalarEvolution is as follows-<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Outer loop-<o:p></o:p></p>
<p class="MsoNormal">backedge-taken count is 39<o:p></o:p></p>
<p class="MsoNormal">max backedge-taken count is 39<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Inner loop-<o:p></o:p></p>
<p class="MsoNormal">backedge-taken count is {-2,+,1}<nsw><%for.cond1.preheader><o:p></o:p></p>
<p class="MsoNormal">max backedge-taken count is 37<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">After indvars, the backedge information computed by ScalarEvolution is as follows-<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Outer loop-<o:p></o:p></p>
<p class="MsoNormal">backedge-taken count is 39<o:p></o:p></p>
<p class="MsoNormal">max backedge-taken count is 39<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Inner loop-<o:p></o:p></p>
<p class="MsoNormal">backedge-taken count is (-1 + (zext i32 {-1,+,1}<nsw><%for.cond1.preheader> to i64))<nsw><o:p></o:p></p>
<p class="MsoNormal">max backedge-taken count is -1<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">If we generate sext instead of zext, the information computed by ScalarEvolution is as follows-<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Outer loop-<o:p></o:p></p>
<p class="MsoNormal">backedge-taken count is 39<o:p></o:p></p>
<p class="MsoNormal">max backedge-taken count is 39<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Inner loop-<o:p></o:p></p>
<p class="MsoNormal">backedge-taken count is {-2,+,1}<nw><%for.cond1.preheader><o:p></o:p></p>
<p class="MsoNormal">max backedge-taken count is -2<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">We now have a simplified backedge taken count for the inner loop which is almost as precise as before indvars, except for the <nw> flag instead of <nsw> flag. I think ScalarEvolution should be able to precisely deduce wrap flags in the
presence of sext but this may require a separate fix. The reason for the conservative max backedge taken count may be the same.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal">Pankaj<o:p></o:p></p>
</div>
</body>
</html>