From mboxrd@z Thu Jan  1 00:00:00 1970
From: Toon Moene <toon@moene.indiv.nluug.nl>
To: egcs@cygnus.com
Subject: More than you ever wanted to know about Fortran array indexing ;-)
Date: Sun, 05 Oct 1997 05:02:00 -0000
Message-id: <9710051153.AA02261@moene.indiv.nluug.nl>
X-SW-Source: 1997-10/msg00198.html

[ The secret hope behind all this is that someone gets so fed up  
with my mails that s/he solves the problem, saving the documentation  
for later ... ]

All this pertains to the Alpha platform, dealing with array index  
calculations in a different mode than the final address expressions.

Consider the following two examples:

      subroutine a(x, y, n)
      dimension x(n), y(n)
      do i = 2, n-1
         x(i) = (y(i-1) + 2 * y(i) + y(i+1))/3
      enddo
      end

and

      subroutine b(x, y, n, m)
      dimension x(n, m), y(n, m)
      do j = 1, n
         do i = 1, m
            x(i, j) = y(i, j)
         enddo
      enddo
      end

Up til now, it looked like rank 1 examples were compiled to  
efficient code (using Richard Henderson's "expr.c" patch) and rank >  
1 examples inefficiently.

These new examples show that that is not the correct way of looking  
at this poblem.

The loop of the first looks like this:

$37:
        lds $f1,0($4)
        addl $3,$31,$1
        adds $f1,$f1,$f1
        s4addq $1,$17,$1
        lds $f10,-4($1)
        adds $f10,$f1,$f10
        s4addq $5,$17,$1
        lds $f1,0($1)
        adds $f10,$f1,$f10
        divs $f10,$f11,$f10
        addq $4,4,$4
        addq $3,1,$3
        subl $2,1,$2
        addl $5,1,$5
        sts $f10,0($16)
        addq $16,4,$16
        bge $2,$37

and the inner loop of the second:

$41:
        lds $f1,0($1)
        subl $3,1,$3
        addq $1,4,$1
        sts $f1,0($4)
        addq $4,4,$4
        bge $3,$41

Apparently, in the last case, the backend is able to get rid of the  
multiplications and divisions entirely.  In the fist case, although  
from first principles one knows that there are only three loads,  
one store and four addq's necessary, we still see two s4adds and  
several {add.sub}l's which means that not all integer computations  
have been converted to `sizetype' mode (on an Alpha: 64 bits, i.e.  
*q*uadword).

The conclusion here is very simple:  This cannot be solved in the  
backend completely.  The ....l instructions result fom the  
frontend's i-1 and i+1 calculations, which cannot be relegated to  
the backend.

So, we find ourselves in a nice cave, surrounded by a twisty maze  
of little passages, all inpenetrable ...

"Wie 't weet, mag 't zeggen"

Cheers,
Toon.