Questions about dependency analysis

[Janne Blomqvist]

On Jan 22, 2008 12:05 AM, Dominique Dhumieres <dominiq@lps.ens.fr> wrote:
> (1) Is the dependency in gfortran documented somewhere?
> or only in the comments of gcc/fortran/dependency.*?

Not that I know of. You might want to search the mailing list archives
for patches by Roger Sayle, IIRC he has contributed most of the array
expression optimizations. E.g.:

http://gcc.gnu.org/ml/fortran/2006-03/msg00028.html

> (2) Am I correct to understand that this analysis is quite
> elementary and very conservative: non dependency is found
on't know if the middle-end can remove the/some unneeded temporaries.
>
> integer, parameter :: n = 10
> integer :: i
> real :: a(0:n+1) => for simple (generic) cases, if not a dependency is assumed?

Yes. How could you do it otherwise? There's a potentially unbounded
number of array expressions requiring temporaries, so you can't just
assume that you don't need a temporary, and hope to enumerate the
cases where you need one.

That is, the default behaviour is to always use a temporary. Only if
it can be proved that the temporary is not needed can one get rid of
it.

> (3) If a dependency is assumed the RHS is stored in a temporary
> with the same size as the LHS array, then copied back to it?

I haven't looked at it in detail, but it would be very surprising if
this isn't the case?

> A standard trick reduces the size of the temporary to two scalars (which can be
> eliminated from the loop by the middle-end):
>
> tmp = a(0)
> do i=1,n
>   res = (tmp+a(i+1))/2.0
>   tmp = a(i)
>   a(i) = res
> end do
>
> This extends to higher dimensions of the LHS, the bottom line being that the
> temporary needed is the rank of the LHS minus one.  For a 100**3 array, this
> reduces the temporary form 1,000,000 elements to 10,000, having a chance to
> stay in the cache of modern CPUs and reducing the memory footprint and
> bandwith usage (limiting factor in this kind of code).

Yes. Another trick I've seen, and used myself, is to use two arrays
and swap between them for each iteration.

> I think the dependency analysis is a rather elementary number theory problem
> (I know most of the answers for only one index) and reducing the size of the
> temporary seems doable, though I don't know how difficult it would be.
>
> Is there any interest around to continue in this direction?

I certainly think contributions in this area would be welcome, yes.
The hard part AFAIK is that noone has figured out how to create an
optimizer that magically can figure out all kinds of array
expressions, rather it looks at the code and sees if it matches a list
of patterns it knows about. Bob Corbett from Sun has occasionally
commented on this in comp.lang.fortran:

http://coding.derkeiler.com/Archive/Fortran/comp.lang.fortran/2007-01/msg00214.html

IIRC he has also (co?)authored some paper(s) about array expression
optimizations, but I don't seem to find them at the moment.

A starting point is

Gerald Roth, Advanced Scalarization of Array Syntax, Lecture Notes in
Computer Science, 2000

and references therein. If you are at a university, you should be able
to access the article at
http://www.springerlink.com/content/gdmd1hj29k7wgf5f/


-- 
Janne Blomqvist