This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
[lno] Swim loop reduced and heuristics problem
- From: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- To: Daniel Berlin <dberlin at dberlin dot org>, Andrew Pinski <apinski at apple dot com>
- Cc: gcc at gcc dot gnu dot org
- Date: Fri, 3 Sep 2004 00:21:02 +0200
- Subject: [lno] Swim loop reduced and heuristics problem
- References: <FDE45A16-FD24-11D8-AD1D-000D93B1B044@dberlin.org>
If you have only the loops:
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
sum = sum + u[i + 1335 * j];
u[1336 * i] *= 2;
}
there are not enough data access steps in the inner loop: basically
you have two references to u[1336 * i] and a single reference to u[i +
1335 * j], ie. for the outer loop the sum of the strides of all the
data references is 2*1336 + 1 whereas for the inner loop the sum of
the steps is 1335. In this case the implemented heuristic is not
enough accurate.
Why should we interchange this loop anyway?
Because for the inner loop we have on the original code steps like
u[0], u[1335], u[1335*2], ...
u[1], u[1336], u[1335*2+1], ...
...
and we would like to have smaller steps for the inner loop, like that:
u[0], u[1], u[2], ..., u[1335]
u[1335], u[1336], u[1337], ...
...
That means that I have to look at the strides of the data accesses
only in the inner loop without looking at the accesses of the outer
loop: ie. I will end with sum of steps for outer loop = 1, and sum of
steps for the inner loop = 1335, and consequently I have to
interchange loops.
I will prepare a patch for this.
Sebastian