Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!haven!adm!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 2: to point or not to point
Message-ID: <3652@lanl.gov>
Date: 23 Oct 90 21:14:38 GMT
References: <14271@goofy.megatest.UUCP>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 73

From article <14271@goofy.megatest.UUCP>, by djones@megatest.UUCP (Dave Jones):
> [...]
> I've seen a few compilers, and more than a few compiler books, and
> unless my memory fails me, every algorithm I've ever seen that takes
> advantage of the "useful semantic properties" does so by first turning
> all the control-statements into gotos, then analyzing that. What
> "rediscovery" are you thinking of that may be "completely intractable"?
> I'm baffled.

I'm sorry I was not clear on this.  Procedure calls are a form of
flow control.  As such, they can also be replaced by GOTOs.  If the
procedure call mechanism is replaced with GOTOs (especially with
recursive procedures present) the rediscovery of the main flow
properties of the program can indeed be very difficult.

None the less, you are right in pointing out that recovering the
semantic properties of flow control is comparitively easy to the
problem of recovering the semantic properties of data structures
once information about them has been lost.  And indeed, some
compilers do throw away _some_ flow control information in order
to process the control information in a canonical way.  It's hard
to imagine doing the same for data structures though.

For example (and this is one of the more trivial ones where there
_is_ a solution):

      x(1,:) = x(2,:)

This is an array assignment in the Fortran Extended (the new name
for Fortran 8x, which became Fortran 90, etc.).  The compiler can
easily determine that this assignment doesn't alias or overlap the
source as destinations - so it can optimize (the statement simply
copies the second column into the first).  The same statement done
pointers might be:

      p = &x;
      q = p + N;
      for (i=0;i<N;i++) *p++ = *q++;

Well, clearly the compiler _can_ resolve this, it only requires the
solution of a fairly simple Diaphantine problem showing that the
'p's never overlap any of the 'q's during the execution of the
loop.  Notice, in the C version I have switched the array around
so the C code is copying the second _row_ to the first _row_ and
is not copying between columns.  This is the obvious change since
C arrays are row-wise and Fortran's are column-wise.  But, suppose
for other reasons that the C code _needed_ to do the column move:

      p = &x;
      q = p + 1;
      for (i=0;i<M;i++,p+=M,q+=M) *p = *q;

Now the two pointers interleave each other in the loop - the compiler
will have a much harder analysis to solve in order to determine that
the two are indeed still not overlapped.  In the case with arrays,
going "against the grain" is as simple as the original case was:

      x(:,1) = x(:,2)

Still easy to determine not to be overlapped.

But, if the array notation was simply _preprocessed_ into the pointer
notation (as was suggested), the compiler would have to solve the
analysis I showed above.  The general problem of array indexing in
multiple dimensions is not completely intractable, but it is more
difficult than the specific case I've shown here.  Why force the
compiler to do all that work?  The time the compiler spends on this
could have been used to optimize other parts of the code.  The time
the compiler _writer_ spends on getting this part of the compiler
done could have been spent on developing other language features -
or at least improving the compiler's efficiency.

J. Giles