Matrix layout transpose based on profile information

[Revital Eres <ERES at il dot ibm dot com>]

Hello,

I intend to implement matrix layout transpose
based on profile information.

For example consider the following program:

double **a;

int
foo()
{
for (i = 0; i < n; i++)
     for (j = 0 ; j < m; j++)
         a[i][j]
}

int
main()
{
 int i, j, n, m;

a = (double **)malloc(n * sizeof(double *));
for (i = 0;i < n; i++)
     a[i] = (double *)malloc(m * sizeof(double));

 for (i = 0; i < m; i++)
     for (j = 0 ; j < n; j++)
         a[j][i]
}

If based on profile information we discover that
statement a[j][i] in main () been executed more times
than a[i][j] in foo (); transposing the layout of
matrix a will improve data locality.

As for the implementation -

Information concerning the memory reference in
loops is needed.
Because this optimization needs the whole programs view
it is taking place early - before the analyzing of tree loops.
I do not familiar with other utilities to extract loop information in
that phase and I appreciate it if someone has an idea ...

Although the framework of this optimization
should be very similar to the struct peeling
optimization in struct-reorg branch; the above
issue could influence the branch I'll eventually choose
to work on.

Thanks,
Revital