🚀 go-pugleaf

In article <4869@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> From article <1990Nov2.183359.6761@maths.nott.ac.uk>, by anw@maths.nott.ac.uk (Dr A. N. Walker):
> > [...stuff that shows that _sombody_ finally understands what I'm saying...]

As you know, I've said the same things before in e-mail, so you don't
have to act so amazingly relieved.

The crux of this side issue is whether the compiler can optimize possibly
aliased functions without asking the programmer. Below I quote an e-mail
message from me to you in June, with interpretations for comp.lang.misc
readers (who are missing the extensive context of the message).

> Exactly the problem I kept trying to point out to someone via private
> email (and the reason I don't deal with that person over email any
> more - he ignored the point and kept claiming that the compiler by
> itself could do all).

I admire your productive attitude.

---Dan

: From brnstnd Wed Jun 13 00:23:57 1990
: Return-Path: <brnstnd>
: Received:  by stealth.acf.nyu.edu (5.51/25-eef)
: 	id AA00647; Wed, 13 Jun 90 00:23:54 CDT
: Date: Wed, 13 Jun 90 00:23:54 CDT
: From: Dan Bernstein <brnstnd>
: Full-Name: Dan Bernstein
: Message-Id: <9006130523.AA00647@stealth.acf.nyu.edu>
: To: dan, jlg%woodsy@lanl.gov
: Subject: Re:  aliasing again ...
: Status: O
: 
: Gaaaargh.

This was after your repeated insistence that proper aliasing analysis
could not be performed by the compiler.

:   [ file1: int a; int b; main() { ... sub(&a); ... } ]
:   [ file2: extern int a; sub(x) int *x; { ... } ]
:   [ file3: extern int b; sub(x) int *x; { ... } ]

You had just said something like ``file2 and file3 are symmetric with
respect to global variables a and b, so aliasing analysis is
impossible!''

: 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.
: 
: 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?

I was getting a little ticked at having to explain the same thing to you
so many times, particularly when TCMITS understood exactly what I was
saying.

Do any readers understand what's going on here? Walker assumed that
without outside help, the compiler cannot easily test for interference
at run time (let alone compile time), and hence cannot decide which
version of the compiled code to execute. But here I'm showing you
exactly how it can be done, for the case you care about (array
manipulations as in Fortran).

: Hopefully this will elicit an ``Oh, now I understand!'' from you.
: Presumably you'll continue with ``But it's making the wrong decision for
: file3, because file3 can't see a!'' I repeat my original claim: The
: compiler can trivially perform a sufficiently good aliasing analysis
: that the translation of a Fortran program without aliasing will end up
: with the unaliased compiled C code.

That's what you're looking for, right? C array manipulations optimized
as effectively as those in Fortran? Indeed, in the simplified model
above, file3 has to account for aliasing where that aliasing cannot in
fact exist. But that can never happen in the translation of a Fortran
program. And see below.

: 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.'' And so on. You made some incorrect statements in
: comp.lang.misc about the nature of the combinatorial explosion if you
: enumerate *all* possibilities; it's actually quite feasible for normal
: code.
: 
: 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 does Nemesis, as you then told me. But that has nothing to do with
current real-world languages like C. I still claim that a C compiler can
detect and avoid the aliasing problems of a Fortran-converted piece of
code at compile time.

Please do not pervert my claim into the following: ``A C compiler can
detect and avoid all aliasing problems at compile time with no help from
the programmer.'' That simply isn't true: pointers in general are much
more flexible than Fortran arrays, and some tests simply have to be
performed at run time. I agree entirely (and in fact told you in several
messages) that the compiler has to get assertions from the programmer if
it wants to deal with general aliasing problems properly.

---Dan