Xref: utzoo comp.lang.fortran:862 comp.lang.c:11069
Path: utzoo!attcan!uunet!husc6!bloom-beacon!think!ames!hc!lanl!beta!jlg
From: jlg@beta.lanl.gov (Jim Giles)
Newsgroups: comp.lang.fortran,comp.lang.c
Subject: Re: Should I convert FORTRAN code to C?
Message-ID: <20519@beta.lanl.gov>
Date: 1 Jul 88 16:29:58 GMT
References: <20454@beta.lanl.gov> <6067@megaron.arizona.edu>
Organization: Los Alamos National Laboratory
Lines: 47

In article <6067@megaron.arizona.edu>, mike@arizona.edu (Mike Coffin) writes:
> From article <20454@beta.lanl.gov>, by jlg@beta.lanl.gov (Jim Giles):
> > By the way, I've not seen any C compilers which optimize static 2-d
> > arrays anyway.  An early step in the compiler usually turns the array
> > reference into a linear function on the indices - this throws out the
> > dependency information.
> 
> This is not true.  How can information be lost by changing "a[i]" to
> "*(a+i)"?  In fact at least one very fancy FORTRAN compiler converts
> array references to exactly that form to extract dependency
> information that is difficult to recognize otherwise.  See
> "Interprocedural Dependency Analysis and Parallelization" by Michael
> Burke and Ron Cytron, in the 1986 SIGPLAN Symposium on Compiler
> Construction, pp 162-175.
> 
Most simple compilers (read 'C compilers') can't vectorize the following
(assume i is a loop index):

  A[i+N] = A[i+M]

regardless of the values of N or M.  However the following expression
might have been the source of the above expression:

A[4][i] = A[5][i]

This clearly has no dependencies and even a simple compiler (read 'some
Fortran compilers') can vectorize this (ie. A(i,4)=A(i,5)).  Turning
the references above into *(A+i+4*dim2) = *(A+I+5*dim2) which, after
constant folding, is the expression I started out with is what causes
the C compiler to incorrectly identify a dependency.

Now, it is true that with careful analysis of M, N, and the range if i,
the compiler could still have compiled this efficiently.  No C compilers
that I've seen do this very well.

Thank you for the reference.  I have always been convinced that dependency
analysis should TRY the kind of stuff you suggest, but only if simplistic
analysis fails to get rid of the dependencies (compiler speed should
be considered too).  The problem is that C doesn't use either analysis
technique very well.  C actually CAN'T analyse those dynamic multi-
dimensional arrays (pointer-to-pointer) because it can't assume the
pointers have any specific relationships.  It is probably for this
reason that it doesn't bother for static arrays either.  (vote for
'noalias', that should help.)

J. Giles
Los Alamos