<div dir="ltr">Sorry for the email crossing...<br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 9, 2016 at 7:12 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">(Hit reply-all this time :) )<br>
<br>
I'm doing this on a old clang/llvm build (from June 29), but if I<br>
generate IR by<br>
<br>
clang -mllvm -unroll-threshold=0 -O3 -S -emit-llvm -fno-vectorize x.c -o x.ll<br>
<br>
(loop unrolling and vectorization both tend to obscure trip count<br>
computation)<br></blockquote><div>Excellent information. Indeed that seems to do the trick.</div><div>I was running the analysis on -O0 and it didn't give any results. Weird.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
then we are able to compute the trip counts in whatever loops that<br>
remain:<br>
<br>
Loop %for.cond8.preheader: backedge-taken count is {(-1 + %h),+,-1}<nw><%for.cond2.prehe<wbr>ader><br>
Loop %for.cond8.preheader: max backedge-taken count is -1<br>
Loop %for.cond2.preheader: backedge-taken count is (-1 + %w)<br>
Loop %for.cond2.preheader: max backedge-taken count is -1<br>
<br>
<br>
<br>
It isn't clear to me why indvars does not fold way all the loops out<br>
of existence (it is "clearly profitable" in this case).  I'll try to<br>
take a closer look tonight.<br></blockquote><div>It's a contrieved example, I don't actually need this optimization to happen on any actual code.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
-- Sanjoy<span class=""><br>
<br>
<br>
Michael Zolotukhin via llvm-dev wrote:<br>
><br>
> unsigned long kernel(long w, long h, long d) {<br>
> unsigned long count = 0;<br>
> for(int i = 0; i < w; ++i)<br>
> for(int j = i; j < h; ++j)<br>
> for(int k = j; k < d; ++k)<br>
> ++count;<br>
> return count;<br>
> }<br>
<br></span><span class="">
Michael Zolotukhin via llvm-dev wrote:<br>
</span><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
On Aug 9, 2016, at 6:39 PM, Alexandre Isoard via llvm-dev<br></span><div><div class="h5">
<<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> <mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.or<wbr>g</a>>> wrote:<br>
<br>
Hello,<br>
<br>
I was doing some experiments with SCEV and especially the loop trip count.<br>
Sorry for the dumb question, what is the easiest way to dump SCEV<br>
analysis results on a .bc file?<br>
</div></div></blockquote><div><div class="h5">
opt -analyze -scalar-evolution < file.bc<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
On a side note, I wanted to see if we could optimize this function:<br>
<br>
unsigned long kernel(long w, long h, long d) {<br>
unsigned long count = 0;<br>
for(int i = 0; i < w; ++i)<br>
for(int j = i; j < h; ++j)<br>
for(int k = j; k < d; ++k)<br>
++count;<br>
return count;<br>
}<br>
<br>
into this (it might not take into account overflows, it was generated<br>
using the barvinok library):<br>
</blockquote>
Looks like we can not, but I haven’t examined why. Overflows might<br>
indeed get into the way.<br>
<br>
Michael<br>
<br>
</div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5">
unsigned long kernel2(long w, long h, long d) {<br>
return<br>
(-1 + w >= 0 && -1 - w + h >= 0 && -1 - h + d >= 0)<br>
? (((((2 * w - 3 * w*w + w*w*w) + 3 * w * h + -3 * w * h*h) + ((3 * w<br>
- 3 * w*w) + 6 * w * h) * d))/6)<br>
: (-1 + w >= 0 && -1 - w + d >= 0 && h - d >= 0)<br>
? ((((2 * w - 3 * w*w + w*w*w) + (6 * w - 3 * w*w) * d + 3 * w * d*d))/6)<br>
: (-1 + h >= 0 && w - h >= 0 && -1 - h + d >= 0)<br>
? ((((2 * h - 2 * h*h*h) + (3 * h + 3 * h*h) * d))/6)<br>
: (-1 + d >= 0 && h - d >= 0 && w - d >= 0)<br>
? (((2 * d + 3 * d*d + d*d*d))/6)<br>
: 0;<br>
}<br>
<br>
I am not sure how advanced are SCEV-based trip counts.<br>
<br>
Best regards.<br>
<br>
--<br></div></div>
*Alexandre Isoard*<span class=""><br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
</span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a> <mailto:<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.or<wbr>g</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>
</blockquote><span class="">
<br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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>
</span></blockquote>
</blockquote></div><br>Best regards.<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>