Re: Preliminary patch for PR23820 and PR24309

["Sebastian Pop" <sebpop at gmail dot com>]

Thanks Ayal, Ira and Victor for raising these problems.

On 10/17/07, Ayal Zaks <ZAKS@il.ibm.com> wrote:
>
> 1. Are the statistics gathered by gather_interchange_stats() invariant, in
> the sense that you can pre-gather them once per loop and cache them,
> instead of re-gathering them twice for each pair of loops? This may save
> compile time.
>

Yes, the information gathered is supposed to be invariant if the
function is called twice on the exact same loop.  After a loop
transformation, the information should be different.

With Jan Sjodin, we also started to look at how to gather this
information from the lambda representation instead of gathering it
from the gimple/data-ref representation.  This is something that we
have to address if we want to compose lamdba transforms (for example
implement skewing followed by interchange), as otherwise we have to
transform the code back to gimple, then start again the data-ref
analysis, and finally gather the info.

> 2. The priority function
> >     if (dependence_steps_i < dependence_steps_j
> >         || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
> >         || double_int_ucmp (access_strides_i, access_strides_j) < 0)
>
> is not 'stable' in the sense that you may prefer to interchange i with j,
> and if asked again prefer to interchange back. If point 1 above is true,
> you are (bubble) sorting the loops according to their priorities, using
> unstable comparisons. (Don't iterate until convergence ;-).
>

Right.  The intended effects of the priority function are multiple:

	/* Heuristics for loop interchange profitability:

	   1. (spatial locality) Inner loops should have smallest
              dependence steps.

	   2. (spatial locality) Inner loops should contain more
	   dependence relations not carried by the loop.

	   3. (temporal locality) Inner loops should have smallest
	      array access strides.
	*/

It can be true that a decision for better spatial locality harms the
temporal locality, and vice versa, and so you don't want to iterate
until convergence ;-), unless you define an order on the effects,
stating your preferences between spatial and temporal locality.

> 3. Can dist
> >       else if (dist < 0)
> >         (*dependence_steps) += -dist;
>
> be negative?
>

int dist = DDR_DIST_VECT (ddr, j)[loop_depth (loop) - loop_depth (first_loop)];

Yes dist can be negative, as dist is one of the components of the
distance vector, not necessarily the loop that carries the dependence.
For example, for the distance vector (1, -1), dist = -1 if we're
looking at the inner loop.

>
> 4. Not too clear an example ...:
>

Could you hint me at how to improve it?  The intent of the example is
to illustrate the inputs and outputs of the function.  IIRC the
example is adapted from the swim cpu2000 benchmark: ltrans-1.c.

> >    Example: for the following loop,
> >
> >    | loop_1 runs 1335 times
> >    |   loop_2 runs 1335 times
> >    |     A[{{0, +, 1}_1, +, 1335}_2]
> >    |     B[{{0, +, 1}_1, +, 1335}_2]
> >    |   endloop_2
> >    |   A[{0, +, 1336}_1]
> >    | endloop_1
> >
> >    gather_interchange_stats (in loop_1) will return
> >    DEPENDENCE_STEPS = 3002
> >    NB_DEPS_NOT_CARRIED_BY_LOOP = 5
> >    ACCESS_STRIDES = 10694
> >
> >    gather_interchange_stats (in loop_2) will return
> >    DEPENDENCE_STEPS = 3000
> >    NB_DEPS_NOT_CARRIED_BY_LOOP = 7
> >    ACCESS_STRIDES = 8010
>

-- 
Sebastian dot Pop at AMD dot com