Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Whether cc after f2c can optimize arrays as well as f77 can
Message-ID: <5085@lanl.gov>
Date: 6 Nov 90 21:02:26 GMT
References: <2779:Nov608:20:1990@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 99

It would actually never occur to me to post something out of a private
email conversation onto the net without the other person's permission.
But, since you have done so, I will continue the discussion in a public
venue.  In fact, I was wondering how to introduce this topic onto the
net myself.

From article <2779:Nov608:20:1990@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> In article <4869@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> [...]
> :   [ file1: int a; int b; main() { ... sub(&a); ... } ]
> :   [ file2: extern int a; sub(x) int *x; { ... } ]
> :   [ file3: extern int b; sub(x) int *x; { ... } ]

These three separate file descriptions I sent (in a somewhat more
legible form) as an example of the fact that _some_ decision _must_
be made at load time with respect to aliasing.  As can be seen, the
main code has a global called 'a' and sends it (call-by-reference)
to a procedure called 'sub'.  The other two files give two alternate
definitions of the procedure.  If the main code is loaded with the
version of 'sub' in file2, then the argument and the global would be
aliased in that context - either slow code or unsafe optimizations
must be accepted.  If the version of 'sub' from file3 is loaded,
then this problem doesn't arise and we would prefer the optimized
version.

> [...]
> : The compiler expands file2's sub() into two functions:
> : 
> :   subf(x) int *x; /* possibly */ aliased global, x; { ... }
> :   subg(x) int *x; /* no aliasing allowed */ { ... }
> : 
> : Similarly for file3.

This was his proposed solution which he claims solves the problem
without any loader intervention (indeed, without load-time action
of any kind).  Presumably, this produces 4 object files (or at least
4 object versions of 'sub').  For convenience, let's call these
'subf2.o', 'subg2.o' (both from the definition in file2), 'subf3.o'
and 'subg3.o' (both from the definition of file3).

> : 
> : The compiler compiles file1's main() into two functions, only one of
> : which will be used:
> : 
> :   main() /* no aliasing allowed */ { ... subf(x) ... }
> : 
> : Must I keep explaining?

Yes, I think you must.  At this point, you have 6 object modules.
The two from file1 are presumably identical since there is no
hidden aliasing possible in 'main' (not any shown in the example
anyway).  Let us call this 'main.o' since it doesn't matter which
of the 'main' versions I use.

Now, to load and run the code, I do what?  Well, somehow, I must decide
which of the four versions of 'sub' to load with 'main'.  Half of this
decision is the same as always, I must decide whether I want the version
from file2 of the one from file3.  But, the next decision is more
difficult: which of 'subf.o' and 'subg.o' should I load?  Well, a
quick examination of the files shows me that I should either use
'subf2.o' (the one from file2 that allows aliasing) or I should
use 'subg3.o' (the one from file3 which is optimized).

But, wait a minute!!  How did I decide that?  I did it by looking the
the relevant code in the caller and the callee (an interprocedural
analysis - I always said there'd be one of those).  And, I made the
decision at load-time (exactly the time I always said the decision
would be made).  Further, the loader itself could have made the
decision if the compiler passed the right information along (which
is what I always recommended).

> [...]
> : To do a better job, of course, you can add more levels between ``all
> : variables may be aliased'' and ``no variables are aliased.'' For
> : example: ``Any parameter may be aliased with a.'' ``Any parameter may be
> : aliased with b.'' [...]

I pointed out repeatedly in email that many compilers already have
this feature: it doesn't solve or even address the problem, which
was (as Walker put it), HOW DOES THE USER _KNOW_ what to assert
with all these declaraions?  It requires an interprocedural analysis.

> [...]
> : The most flexible (and arguably the best) solution is to let the
> : programmer assert the lack of aliasing between any variables at any
> : time. Q provides sufficiently general mechanisms for this.

As long as the _LOADER_ checks the consistency of these assertions
across procedure calls, this is indeed adequate.  Feedback from such
_LOADER_ tests would be sufficient to tell the user the interprocedural
information needed (though, through trial and error).

By the way, as I've pointed out before, the _LACK_ of aliasing
should be the default - the presence of possible aliasing should
require the assertion.  It makes sense to make the most commonly
desired configuration be the default.  You always ask for the
reverse of that.

J. Giles