<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>[+Sanjoy]</p>
<p>The fact that we lose information by widening during
induction-variable simplification is certainly a known problem. I
don't recall if we've ever really decided on a path forward. I
personally suspect that, as an information-destroying
transformation, the widening should be moved to the lowering phase
(i.e. near where we do vectorization, etc.). Unless the widening
itself enables other transformations, I don't see why we should do
it early. The one exception I can think of is where it might
enable us to collapse redundant PHIs, as is:</p>
int i = 0; long j = 0;<br>
for (; i < n; ++i, ++j) { ... using i and j ... }<br>
<br>
but that seems like a special case we could handle separately.<br>
<br>
-Hal<br>
<br>
<div class="moz-cite-prefix">On 04/12/2017 07:21 PM, Chawla, Pankaj
via llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:609AA37F9A388E41A993A4EFFFF6E116555DE6E6@ORSMSX105.amr.corp.intel.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<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]-->
<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>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>