[llvm-dev] SCEV LoopTripCount

[Alexandre Isoard via llvm-dev]

Thank you for the fast answer.

On Tue, Aug 9, 2016 at 6:51 PM, Michael Zolotukhin <mzolotukhin at apple.com>
wrote:

> Hi,
>
> On Aug 9, 2016, at 6:39 PM, Alexandre Isoard via llvm-dev <
> 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
>
Perfect. Thank you.

>
> 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.
>
Also I wrongfully used int as induction variables instead of long.
But even after this correction, playing with unsignedness does not improve
the situation. (even with all signed or all unsigned)

However, I came to realise that the first code could be improved into:

long kernel2(long w, long h, long d) {
using std::min;
long count = 0;
for (long i = 0; i < min(min(w, h), d); ++i)
for (long j = i; j < min(h, d); ++j)
for (long k = j; k < d; ++k)
++count;
return count;
}

That is, removing dead loop iterations. Do we perform this kind of
transformation? (when we can compute SCEV)

>
> 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
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
Regards.

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