Path: utzoo!attcan!uunet!nih-csl!lhc!adm!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: <5483@lanl.gov>
Date: 9 Nov 90 20:55:28 GMT
References: <23333:Nov904:43:1390@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 147

From article <23333:Nov904:43:1390@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> In article <5243@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
>> Well, I've looked over your little proposal.  And, I'll have to admit
>> that it does "solve" the specific problem I posted.
> 
> Thank you! Do you also agree that I wasn't ``ignoring'' your repeated
> insistences otherwise in e-mail?

Well, you certainly addressed the examples themselves.  You have
still ignored nearly everything I actually _said_ about them.  As I
pointed out last time, if I had known the extent to which you were
misinterpreting what I was saying, I would have sent a different
example.  In any case, I did continually point out that the example
given was extremely simplified and that usually the aliasing problem
to be discovered was deep in the call chain and not simply resting on
top like the examples showed.  The next example I was going to post
was the one I gave in the last article (and you incorrectly analyse:
see below).

> [...]
> But an *adequate* job is done by merely choosing enough partitions to
> reasonably cover the cases actually needed. In fact, if a statement of
> yours is correct, ``enough'' means two. Viz., you said that there is no
> aliasing in most real programs. If you're right, then the compiler can
> generate two versions of the procedure: one that assumes no aliasing,
> and one that assumes lots of aliasing. The fast version will always, in
> practice, be selected.

No, you claim is only _almost_ true.  The true restatement of the
last line above is: the fast version will _usually_, in practice,
be selected.  As I have repeatedly admitted, aliasing is (on rare
occasions) actually desireable.  Given what you've said above, you
plan to give only two choices: fast or _very_ slow.  But, what I
have consistently insisted upon is for the code to only be slowed
down by the aliasing that is actually present.  This requires
explicit declaration of what aliasing to allow, which in turn
requires a call chain analysis to determine if these constraints
are satisfied by parameters (which can be passed arbitrary levels
deep).  But, your scheme doesn't do this.  Even if you do allow
explicit assertions about aliasing, you don't provide a call
chain analysis tool which will tell the user the deep effects
of those assertions.

In addition, you still have an exponential number of separate cases
to select since you don't know before hand what specific aliasing
assertions the user will make.  But, that's right, you want to
condemn anyone who uses _any_ aliasing to inefficient code which
assumes _all_ possible aliasing.

> [...]
>> Your
>>    scheme has the 'advantage' of automatically working even without
>>    these assertions.
> 
> Exactly. The compiler can do some---maybe not a lot, but some---aliasing
> analysis without help from the user. I wish you hadn't chopped off our
> e-mail conversations just because you didn't understand this point.

I understood completely.  The compiler can do an enormously useful
amount of analysis _locally_ (and a good thing too, I'm all for
it).  The compiler with your scheme can do a tiny amount of shallow
non-local analysis (at least, assuming the .h files are from the
same version of your library routines as your .o files are).  This
latter is indeed new to me, it would never have occurred to me to
use so much effort to achieve such a trifling result.

> [...]
>> This is the kind of obscure and hard
>>    to find error that was part of the motivation for the scheme that
>>    am proposing.
> 
> Agreed, it's always good to be able to check user assertions. But the
> error-checking issue is entirely orthogonal to the point of this thread.

Well, again maybe I've not been clear.  In _my_ view, error checking
was always an inherent part of this discussion.  It is not second to
efficiency.  In fact, it is _more_important_ that efficiency.  The
two issues are linked by the fact that the call chain analysis I
recommend achieves _both_ error detection from propagated procedure
arguments _and_ allows selection of efficient code.

> [...]
>> 3) The last of these objections to your scheme is the fact that the
>>    first counter-example I tried actually couldn't be done correctly
>>    by your method:
>   [ static int a; main() { ... sub(&a); ... } fcn((int *) x) { ... } ]
> 
> It *is* handled correctly. fcn's only partition is {{x}}---a cannot be
> included, because a is not visible outside the package. Hence it assumes
> that &a and x may be aliased, and it generates the slow code for this
> case.

That's just the thing!  I mean, it shouldn't, should it?  You stated
above: "The fast version will always, in practice, be selected."
What happened to that?  Certainly, Fortran would select the _fast_
version.  Your claim to always do as well as Fortran is slipping.

My scheme will select the fast version for most cases and generate
an error in the rare (I hope) case when &a is actually passed all
the way through to fcn().  My scheme also allows me to declare a
slow version of fcn() if I _want_ to allow &a all the way through.
I can even (with function overloading) have both the fast and slow
versions loaded with the same code and the slow version only show up
on those call chains where it is really necessary.  (My function
overloading allows two functions with the same name which differ
in any specifically declared way in the interface specification.)

> [...]
> I agree that this would be inefficient if x and &a actually weren't
> aliased, but so what? It has *nothing* to do with the C equivalent of
> Fortran, which is what I'm addressing (and have been since we started
> this discussion many months ago). See the subject line. I'm making the
> same claim that I made back then: C can optimize Fortran (-converted)
> array code as well as Fortran can. Here you're talking about static
> variables, which have no real (visibility) equivalent in Fortran.

And yet, the Fortran-like version of this code would pick the fast
compilation.  Certainly Fortran Extended (which _does_ have the
concept of private variables) would optimize this code as if there
were no aliasing through the call chain - Fortran disallows such
aliasing.  My scheme allows such aliasing (if explicitly requested)
_and_ detects and disallows it (when it's _not_ explicitly resuested).

> 
>>    This is one of the things that my scheme _can_ do.
> 
> Why do you call it ``your scheme''? It's not ``your scheme'' any more
> than it's ``my scheme.'' We both came up with it before mentioning it to
> the other, but there's hardly any chance that adding assertions to the
> procedure call interface is a new idea.  [...]

I use this terminology to differentiate between the two different
concepts we support with a short phrase.  Instead of being insulting
or ragging me about some supposed attempt on my part to take credit
for the ideas, why don't you propose some alternate set of short
phrases which express the different ideas?  Why must you style of
argument _always_ be confrontational?  I have that unfortunate trait
to a great extent myself, but I _try_ not to supress it.

Besides, it's not clear that the idea of using the loader to
propagate the constraints through the call chain _isn't_ an original
idea.  I _may_ have every right to call it "my scheme".  I don't
know.  But, since I don't take a proprietary view toward the idea,
the use of the phrase "my scheme" should be regarded as merely
shorthand.

J. Giles