[graphite] data dependence analysis revival

[Konrad Trifunovic]

2009/3/2 Sebastian Pop <sebpop@gmail.com>:
> Hi Konrad,
>
>> -
>> -       /* FIXME: At this point the DRs should always have an affine
>> -          form.  For the moment this fails as build_access_matrix
>> -          does not build matrices with parameters.  */
>> -       gcc_assert (res);
>> +          if (!res)
>> +            DR_ACCESS_MATRIX (dr) = NULL;
>
> You should not remove the gcc_assert here.
>
> All the data references should have a known polyhedral representation
> at this point.  This still fails at this point because of an data ref
> analysis problem that we did not fixed in scop detection.

I understand that this assumption is the fundamental one if we want to
represent a SCoP in PCP abstraction?

Then, if it fails there, that means there is a bug in SCoP detection.
SCoP is detected, even though
there are data references that cannot be represented in the form of
affine access matrix.
I have been debugging SCoP detection issues while working on that
problem. There are
things in SCoP detection that I did not like:

1. In the function stmt_simple_for_scop_p we analyze the assignments
(GIMPLE_ASSIGN case) and evolutions of data references. But we do not
check for the types.

It is safe to dereference a pointer if the address the pointer is
pointing into is
itself affine:

int *A;

for i ....
  ... = A[i]; (A[i] might be on left hand side also)

this would actually give the following Gimple code:

int *D.1;

D.1 = A + i; (the expression type is pointer type)
... = *D.1; (the expression type is integer type)

but:

int **A;

for i
  for j
... = A[i][j]

is actually split as:

int ** D.12;
int * D.13;
int * D.14;

D.12 = A + i (the expression type is pointer to pointer.)
D.13 = *D.12 (the expression type is pointer to int, but we read in
the address from memory!)

D.14 = D.13 + offset
... = *D.14

We should not allow reading in the addresses from memory (dereferencing double
pointers). (though this might be too conservative).

2. Actually point (1) could be solved if in function
'stmt_simple_for_scop_p' we called 'is_simple_operand' with a LOOP parameter
that is the outermost LOOP in the scop, not the loop that actually
contains the statement.
Then the result would be 'scev_unknown'. But I'm not sure if we know which
loop is the outermost in a SCoP if we are in the middle of detecting a SCoP.

Konrad

> Sebastian
>