[llvm-dev] SCEV LoopTripCount

[Alexandre Isoard via llvm-dev]

Sorry for the email crossing...

On Tue, Aug 9, 2016 at 7:12 PM, Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:

> (Hit reply-all this time :) )
>
> I'm doing this on a old clang/llvm build (from June 29), but if I
> generate IR by
>
> clang -mllvm -unroll-threshold=0 -O3 -S -emit-llvm -fno-vectorize x.c -o
> x.ll
>
> (loop unrolling and vectorization both tend to obscure trip count
> computation)
>
Excellent information. Indeed that seems to do the trick.
I was running the analysis on -O0 and it didn't give any results. Weird.

>
> then we are able to compute the trip counts in whatever loops that
> remain:
>
> Loop %for.cond8.preheader: backedge-taken count is {(-1 +
> %h),+,-1}<nw><%for.cond2.preheader>
> Loop %for.cond8.preheader: max backedge-taken count is -1
> Loop %for.cond2.preheader: backedge-taken count is (-1 + %w)
> Loop %for.cond2.preheader: max backedge-taken count is -1
>
>
>
> It isn't clear to me why indvars does not fold way all the loops out
> of existence (it is "clearly profitable" in this case).  I'll try to
> take a closer look tonight.
>
It's a contrieved example, I don't actually need this optimization to
happen on any actual code.

>
> -- Sanjoy
>
>
> Michael Zolotukhin via llvm-dev wrote:
> >
> > unsigned long kernel(long w, long h, long d) {
> > unsigned long count = 0;
> > for(int i = 0; i < w; ++i)
> > for(int j = i; j < h; ++j)
> > for(int k = j; k < d; ++k)
> > ++count;
> > return count;
> > }
>
> Michael Zolotukhin via llvm-dev wrote:
>
>> Hi,
>>
>> On Aug 9, 2016, at 6:39 PM, Alexandre Isoard via llvm-dev
>>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>>
>>> Hello,
>>>
>>> I was doing some experiments with SCEV and especially the loop trip
>>> count.
>>> Sorry for the dumb question, what is the easiest way to dump SCEV
>>> analysis results on a .bc file?
>>>
>> opt -analyze -scalar-evolution < file.bc
>>
>>
>>> On a side note, I wanted to see if we could optimize this function:
>>>
>>> unsigned long kernel(long w, long h, long d) {
>>> unsigned long count = 0;
>>> for(int i = 0; i < w; ++i)
>>> for(int j = i; j < h; ++j)
>>> for(int k = j; k < d; ++k)
>>> ++count;
>>> return count;
>>> }
>>>
>>> into this (it might not take into account overflows, it was generated
>>> using the barvinok library):
>>>
>> Looks like we can not, but I haven’t examined why. Overflows might
>> indeed get into the way.
>>
>> Michael
>>
>> unsigned long kernel2(long w, long h, long d) {
>>> return
>>> (-1 + w >= 0 && -1 - w + h >= 0 && -1 - h + d >= 0)
>>> ? (((((2 * w - 3 * w*w + w*w*w) + 3 * w * h + -3 * w * h*h) + ((3 * w
>>> - 3 * w*w) + 6 * w * h) * d))/6)
>>> : (-1 + w >= 0 && -1 - w + d >= 0 && h - d >= 0)
>>> ? ((((2 * w - 3 * w*w + w*w*w) + (6 * w - 3 * w*w) * d + 3 * w * d*d))/6)
>>> : (-1 + h >= 0 && w - h >= 0 && -1 - h + d >= 0)
>>> ? ((((2 * h - 2 * h*h*h) + (3 * h + 3 * h*h) * d))/6)
>>> : (-1 + d >= 0 && h - d >= 0 && w - d >= 0)
>>> ? (((2 * d + 3 * d*d + d*d*d))/6)
>>> : 0;
>>> }
>>>
>>> I am not sure how advanced are SCEV-based trip counts.
>>>
>>> Best regards.
>>>
>>> --
>>> *Alexandre Isoard*
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
Best regards.

-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160809/6879f341/attachment.html>