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?
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):
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*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160809/805a72bf/attachment.html>
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> > 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 > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160809/ded5ece0/attachment.html>
(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)
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.
-- 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
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>