Re: [patch] Predictive commoning, updated

[Zdenek Dvorak <rakdver at kam dot mff dot cuni dot cz>]

Hello,

> Second, about:
> >    However, this second analysis delivers somewhat different results (it
> >    only analyses the behavior of the memory reference in the innermost
> >    loop, not any deeper loop nest);
> 
> this is something I just discovered in the context of outer-loop
> vectorization, and that surprized me too. I thought the intention is that
> find_data_references_in_loop(loop) would compute the DRs relative to the
> loop in question, rather than always relative to the immediately containing
> loop. We'd certainly need that for the outer-loop work. E.g., for the
> following testcase (operating, say, on shorts):
> 
>       loop1: for (i=0; i<N; i++)
>       loop2:     for (j=0; j<M; j+=4)
>                      s += in[i+j];
> 
> the DR for in[i+j] when computed relative to the inner loop (by
> find_data_references_in_loop(loop2)) would look roughly like this:
>       DR_BASE:    &in
>       DR_OFFSET:  i*2B
>       DR_STEP:    16B
> 
> and the DR for in[i+j] when computed relative to the outer loop (by
> find_data_references_in_loop(loop1)) would look roughly like this:
>       DR_BASE:    &in
>       DR_OFFSET:  0
>       DR_STEP:    2B

the problem is that this description does not seem to be quite correct;
the evolution of the index of this memory reference is
{{&in, +, 2B}_1, +, 8B}_2,  and there is no way how to express this just
relatively to the outer loop.  I.e., if you want to process a nest of
loops, you must take this evolution, and obtain the information relative
to each of the loop using functions like evolution_part_in_loop_num
and initial_condition_in_loop_num.

Alternatively, you can analyze the reference with respect to the inner
loop, obtaining evolution

{&in + 2B*i, +, 8B}_2

and then analyze the base (&in + 2B*i) with respect to the outer loop,
obtaining

{&in, +, 2B}_1

Such results then can be decomposed into BASE/OFFSET/INIT/STEP as we do
now, if you find this easier to work with.

Zdenek