A prototype loop reverser for the scalarizer

[THOMAS Paul Richard 169137]

I have spent a couple of lunch hours playing with a prototype loop
reverser for scalarized assignments.  It uses gfc_dep_resolver to
loops that could be reversed, to avoid making a temporary, and does
the loop reversal and modification of the array references in
gfc_conv_loop_setup.  The attached test, time_test.f90, produces the
following output in the unpatched case, with -O3:

 a(1:N) = b(2:(N+1)) takes   0.1210938
 a(2:(N+1)) = b(1:N) takes   0.1250000
 a(1:N) = a(2:(N+1)) takes   8.9843750E-02

 a(2:(N+1)) = a(1:N) takes   0.3437500
 a((N+1):2:-1) = a(N:1:-1) takes   8.9843750E-02

 a(2:(N+1)) = b(1:N)*factor1 takes   0.1250000       a(10) =    2.000000
 a(2:(N+1)) = b(1:N)*factor1*factor2 takes   0.1250000       a(10) =    4.000000
 a(2:(N+1)) = b(1:N)/(factor1*factor2) takes   0.1250000       a(10) =   0.2500000
 a(1:N) = b(1:N)/a(1:N) takes   0.3867188       a(10) =    4.000000

Note the 0.34 seconds for the case that requires the temporary, to be
compared with the same, reversed by hand, which takes 0.90s.

With the patch, which is attached, the results are:

 a(1:N) = b(2:(N+1)) takes   0.1367188
 a(2:(N+1)) = b(1:N) takes   0.1210938
 a(1:N) = a(2:(N+1)) takes   9.3750000E-02

 a(2:(N+1)) = a(1:N) takes   9.3750000E-02
 a((N+1):2:-1) = a(N:1:-1) takes   8.9843750E-02

 a(2:(N+1)) = b(1:N)*factor1 takes   0.1250000       a(10) =    2.000000
 a(2:(N+1)) = b(1:N)*factor1*factor2 takes   0.1250000       a(10) =    4.000000
 a(2:(N+1)) = b(1:N)/(factor1*factor2) takes   0.1250000       a(10) =   0.2500000
 a(1:N) = b(1:N)/a(1:N) takes   0.3867188       a(10) =    4.000000

...which is quite gratifying!

Unoptimized, a factor of two is gained, which could still be improved by
another factor of 1.5, relative to the hand reversed case.  This latter
difference comes from a difference in the resulting code for the two
loops, which is eliminated by the optimizer:

AUTOMATIC REVERSAL:
{
  int4 S.8;

  S.8 = 0;
  while (1)
    {
      if (S.8 > 19999999) goto L.6; else (void) 0;
      a[S.8 * -1 + 20000000] = a[S.8 * -1 + 19999999];
      S.8 = S.8 + 1;
    }
  L.6:;
}

HANDCRAFTED REVERSAL:
  {
    int4 S.10;

    S.10 = 0;
    while (1)
      {
        if (S.10 > 19999999) goto L.7; else (void) 0;
        a[20000000 - S.10] = a[19999999 - S.10];
        S.10 = S.10 + 1;
      }
    L.7:;
  }

I cannot see where the difference in the index arithmetic comes
from; Steven, Paul, can you give me a pointer, please?

The constant mutliplier and divisor results are interesting, since
there is a big difference for unoptimized code.

This clearly is in prototype form and could stand tidying up and
more rigorous testing.  Is there anybody out there that is keen
that I complete this?

Paul
-------------- next part --------------
A non-text attachment was scrubbed...
Name: time_test.f90
Type: application/octet-stream
Size: 1418 bytes
Desc: time_test.f90
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20061006/4e3e9131/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: depedency.c.diff
Type: application/octet-stream
Size: 1573 bytes
Desc: depedency.c.diff
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20061006/4e3e9131/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: depedency.h.diff
Type: application/octet-stream
Size: 110 bytes
Desc: depedency.h.diff
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20061006/4e3e9131/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: trans.h.diff
Type: application/octet-stream
Size: 122 bytes
Desc: trans.h.diff
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20061006/4e3e9131/attachment-0003.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: trans-array.c.diff
Type: application/octet-stream
Size: 974 bytes
Desc: trans-array.c.diff
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20061006/4e3e9131/attachment-0004.obj>