<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:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@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="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal">If you look at the SCEV output (opt -analyze -scalar-evolution) on the optimized loop without vectorization/unrolling, it looks something like this:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Determining loop execution counts for: @test<o:p></o:p></p>
<p class="MsoNormal">Loop %for.body: backedge-taken count is (-4 + (zext i3 (trunc i64 %b to i3) to i64))<nsw><o:p></o:p></p>
<p class="MsoNormal">Loop %for.body: max backedge-taken count is -2<o:p></o:p></p>
<p class="MsoNormal">Loop %for.body: Predicated backedge-taken count is (-4 + (zext i3 (trunc i64 %b to i3) to i64))<nsw><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">If you exclude the guard outside the loop, the max backedge-taken count is completely unknown: the trip count can be -1UL, -2UL, -3UL, or -4UL (i.e. numbers close to ULONG_MAX). But there’s important information outside the loop: there’s
a guard “icmp ugt i64 %and, 3”, which excludes all those cases. SCEV currently has some very limited support for reducing the max backedge-taken count based on conditions outside the loop; see ScalarEvolution::howFarToZero, in particular, the bit that calls
isLoopEntryGuardedByCond. But that support isn’t very complete; it could definitely be improved.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">As far as I know, nobody is working on this at the moment.<o:p></o:p></p>
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoNormal">-Eli<o:p></o:p></p>
<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> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Nemanja Ivanovic via llvm-dev<br>
<b>Sent:</b> Friday, March 22, 2019 11:51 AM<br>
<b>To:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> [EXT] [llvm-dev] Is SCEV unable to determine obvious max trip count?<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal">Given a simple test where the maximum trip count is quite obvious, we end up producing a vectorized loop (or excessively complex control flow) seemingly because we are unable to determine the maximum trip count of the loop.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Here's an example:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">#ifndef _START<br>
#define _START 3<br>
#endif<br>
unsigned long test(unsigned long *a, unsigned long b) {<br>
for (unsigned long i = _START; i < (b & 7); i++)<br>
a[i] = b;<br>
return b;<br>
}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">If we compile that with -D_START=0, the loop is fully unrolled with a comparison and exit if the result of the and is equal to any of the 7 possible values at each unrolled iteration.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">However, if we do not have that define (i.e. loop doesn't start from zero), we will vectorize the loop. There's even a "min.iters" check that is very obviously redundant:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">%and = and i64 %b, 7<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">%0 = add nsw i64 %and, -3<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">%min.iters.check = icmp ult i64 %0, 24<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">The constant here will be different on different targets, but redundant nonetheless.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Does anyone think this is important to fix this or have any ideas on how to improve the handling here?<o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>