On Fri, Dec 4, 2009 at 1:20 PM, Sebastian Pop <seb...@gmail.com> wrote:
> On Fri, Dec 4, 2009 at 11:08, Cédric Bastoul <cedric.bast...@inria.fr> wrote:
>> We usually call this case (parameter times IV) "fully parametric".
>> Armin Grosslinger looked at it before finding a more general solution,
>
> I don't want the more general solution: IV * IV doesn't commonly
> happen, but parameter * IV does, and ought to be handled separately.
>
>> it's not easy and typically it leads to a massive versioning :-/...
>
> In which cases do you see versioning? Do you have a paper that
> describes the problems you are speaking about?
No, it's based on my old knowledge of the first implementation by
Armin. AFAIR the trick was to rely on a fully parametric
Fourier-Motzkin elimination that could explode but worked in practice.
I think the best way is to let Armin enter the loop and let him
explain how we could handle the fully parametric case. He's clearly
the specialist of the question. Armin, did you write any report on
supporting the fully parametric case for code generation ? Here is one
specific case we would like to support :
[Anyway, extending CLooG to support this would *not* be trivial :-/]
On Fri, Dec 4, 2009 at 11:29 AM, Sebastian Pop <seb...@gmail.com> wrote:
> On Fri, Dec 4, 2009 at 09:41, Toon Moene <t...@moene.org> wrote:
>> I wonder if Graphite can do this one (or is planned to be able to):
>>
>> Another loop optimization that suggests itself
>> is the following, trying to eliminate unnecessary
>> loop constructs:
>> \begin{verbatim}
>> SUBROUTINE SUB(A, B, C, N, M)
>> REAL A(N, M), B(N, M), C(N, M)
>> DO J = 1, M
>> DO I = 1, N
>> C(I, J) = A(I, J) + B(I, J)
>> ENDDO
>> ENDDO
>> END
>> \end{verbatim}
>> If we could generate code that looks like what is
>> written below, we would have nothing but
>> {\em one} loop.
>> \begin{verbatim}
>> DO K = 1, M*N
>> C(K, 1) = A(K, 1) + B(K, 1)
>> ENDDO
>> \end{verbatim}
>> In this case, this transformation can be done
>> because the tuple $(i,j)$ forms an induction
>> variable $i+n*(j-1)$ in its own right
>> (replaced by $k$ in the {\em collapsed} loop).
>
> For the moment Graphite wouldn't do this kind of transform. But I think
> that this could be done: CLooG should generate the following code if we
> ask it to collapse the two loops:
>
> DO K = 1, M*N
> I = K mod N
> J = K / N
> C(I, J) = A(I, J) + B(I, J)
> ENDDO
>
> And then one would have to cleanup the scalar arithmetic to have
> linearized array accesses, and that should already be done by GCC in
> the lowering of memory accesses.
>
> Now a question for Cedric: how would you ask CLooG to generate this
> collapsed loop?
>
> Thanks,
> Sebastian
>
