<div dir="ltr">If count > MAX_UINT-4 your loop loops indefinitely with an increment of 4, I think.<br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Oct 13, 2016 at 4:42 PM, Charith Mendis via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">So, I tried unrolling the following simple loop.<div><br></div><div><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo;color:rgb(187,44,162)"><span style="font-variant-ligatures:no-common-ligatures">int</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> unroll(</span><span style="font-variant-ligatures:no-common-ligatures">unsigned</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> * a, </span><span style="font-variant-ligatures:no-common-ligatures">unsigned</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> * b, </span><span style="font-variant-ligatures:no-common-ligatures">unsigned</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> *c, </span><span style="font-variant-ligatures:no-common-ligatures">unsigned</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> count){</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures"> </span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(187,44,162)">for</span><span style="font-variant-ligatures:no-common-ligatures">(</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(187,44,162)">unsigned</span><span style="font-variant-ligatures:no-common-ligatures"> i=</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">0</span><span style="font-variant-ligatures:no-common-ligatures">; i<count; i++</span><span style="font-variant-ligatures:no-common-ligatures">){</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures"> a[i] = b[i]*c[i-</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">1</span><span style="font-variant-ligatures:no-common-ligatures">];</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures"> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo;color:rgb(187,44,162)"><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> </span><span style="font-variant-ligatures:no-common-ligatures">return</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> </span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">0</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)">;</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">}</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures"><br></span></p><p style="margin:0px;line-height:normal">Then, the unroller is able to unroll it by 2 even though it doesn't know about the range of count. SCEV of backedge taken count is (-1 + %count)</p><p style="margin:0px;line-height:normal"><br></p><p style="margin:0px;line-height:normal">But, when I change the increment to 4, as in </p><p style="margin:0px;line-height:normal"><br></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo;color:rgb(187,44,162)"><span style="font-variant-ligatures:no-common-ligatures">int</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> unroll(</span><span style="font-variant-ligatures:no-common-ligatures">unsigned</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> * a, </span><span style="font-variant-ligatures:no-common-ligatures">unsigned</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> * b, </span><span style="font-variant-ligatures:no-common-ligatures">unsigned</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> *c, </span><span style="font-variant-ligatures:no-common-ligatures">unsigned</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> <wbr>count){</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures"> </span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(187,44,162)">for</span><span style="font-variant-ligatures:no-common-ligatures">(</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(187,44,162)">unsigned</span><span style="font-variant-ligatures:no-common-ligatures"> i=</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">0</span><span style="font-variant-ligatures:no-common-ligatures">; i<count; <span style="background-color:rgb(255,0,0)">i+=4</span></span><span style="font-variant-ligatures:no-common-ligatures">){</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures"> a[i] = b[i]*c[i-</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">1</span><span style="font-variant-ligatures:no-common-ligatures">];</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures"> }</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo;color:rgb(187,44,162)"><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> </span><span style="font-variant-ligatures:no-common-ligatures">return</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)"> </span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">0</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,0,0)">;</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">}</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures"><br></span></p><p style="margin:0px;line-height:normal"> The unroller cannot compute the backedge taken count. Therefore, it seems like the problem is not with the range of "count", can't the unroller compute it as (- 1 + %count / 4)? </p></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Oct 12, 2016 at 11:28 PM, Charith Mendis <span dir="ltr"><<a href="mailto:char.mendis1989@gmail.com" target="_blank">char.mendis1989@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Thanks for the explanation. But I am a little confused with the following fact. Can't LLVM keep vectorizable_elements as a symbolic value and convert the loop to say;<div><br></div><div>for(unsigned i = 0; i < vectorizable_elements ; i += 2){</div><div> //main loop</div><div>}</div><div><br></div><div>for(unsigned i=0 ; i < vectorizable_elements % 2; i++){</div><div> //fix up</div><div>}</div><div><br></div><div>Why does it have to reason about the range of vectorizable_elements? Even if vectorizable_elements == SIZE_MAX the above decomposition would work?</div></div><div class="gmail_extra"><div><div class="m_-1434563249859877477h5"><br><div class="gmail_quote">On Wed, Oct 12, 2016 at 8:25 PM, Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"><span>
<div class="m_-1434563249859877477m_-1211829831076901921m_1300953538867614572moz-cite-prefix">On 10/12/2016 4:35 PM, Charith Mendis
via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hi all,
<div><br>
</div>
<div>Attached herewith is a simple vectorized function with
loops performing a simple shuffle.</div>
<div><br>
</div>
<div>I want all loops (inner and outer) to be unrolled by 2 and
as such used -unroll-count=2</div>
<div>The inner loops(with k as the induction variable and having
constant trip counts) unroll fully, but the outer loop with
(j) fails to unroll. </div>
<div><br>
</div>
<div>The llvm code is also attached with inner loops fully
unrolled.</div>
<div><br>
</div>
<div>To inspect further, I added the following to the
PassManagerBuilder.cpp to run some canonicalization routines
and redo unrolling again. I have set partial unrolling on +
have a huge threshold + allows expensive loop trip counts.
Still it didn't unroll by 2.</div>
<div><br>
</div>
<div>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">MPM.add(createLoopUnrollPass()<wbr>);</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">MPM.add(createCFGSimplificatio<wbr>nPass()); </span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">MPM.add(createLoopSimplifyPass<wbr>()); </span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">MPM.add(createLoopRotatePass(S<wbr>izeLevel
== </span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">2</span><span style="font-variant-ligatures:no-common-ligatures"> ? </span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">0</span><span style="font-variant-ligatures:no-common-ligatures"> : -</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(39,42,216)">1</span><span style="font-variant-ligatures:no-common-ligatures">));</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">MPM.add(createLCSSAPass());</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">MPM.add(createIndVarSimplifyPa<wbr>ss());
</span><span style="font-variant-ligatures:no-common-ligatures;color:rgb(0,132,0)">//
Canonicalize indvars</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:menlo"><span style="font-variant-ligatures:no-common-ligatures">MPM.add(createLoopUnrollPass()<wbr>);</span></p>
</div>
<div><br>
</div>
<div><br>
</div>
<div>Digging deeper I found, that it fails in
UnrollRuntimeLoopRemainder function, where it is unable to
calculate the BackEdge taken amount.</div>
<div><br>
</div>
<div>Can anybody explain what is need to get the outer loop
unrolled by 2? It would be a great help.</div>
</div>
</blockquote>
<br></span>
Well, I can at least explain what is happening... runtime unrolling
needs to be able to symbolically compute the trip count to avoid
inserting a branch after every iteration. SCEV isn't able to prove
that your loop isn't an infinite loop (consider the case of
vectorizable_elements==SIZE_MA<wbr>X), therefore it can't compute the
trip count. Therefore, we don't unroll.<br>
<br>
There's a few different angles you could use to attack this: you
could teach the unroller to unroll loops with an uncomputable trip
count, or you can make the trip count of your loop computable
somehow. Changing the unroller is probably straightforward (see the
recently committed r284044). Making the trip count computable is
more complicated... it's probably possible to teach SCEV to reason
about the overflow in the pointer computation, or maybe you could
version the loop.<span class="m_-1434563249859877477m_-1211829831076901921HOEnZb"><font color="#888888"><br>
<br>
-Eli<br>
<pre class="m_-1434563249859877477m_-1211829831076901921m_1300953538867614572moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div></div></div><span>-- <br><div class="m_-1434563249859877477m_-1211829831076901921gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div>Kind regards,<br>Charith Mendis<br><br>Graduate Student,<div>CSAIL,<br><div>Massachusetts Institute of Technology</div></div></div></div></div>
</span></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="m_-1434563249859877477gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div>Kind regards,<br>Charith Mendis<br><br>Graduate Student,<div>CSAIL,<br><div>Massachusetts Institute of Technology</div></div></div></div></div>
</div>
</div></div><br>______________________________<wbr>_________________<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" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><b>Alexandre Isoard</b><br></div></div>
</div></div>