Path: utzoo!utgpu!watserv1!watmath!att!att!linac!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!wuarchive!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Whether cc after f2c can optimize arrays as well as f77 can
Message-ID: <23333:Nov904:43:1390@kramden.acf.nyu.edu>
Date: 9 Nov 90 04:43:13 GMT
References: <2779:Nov608:20:1990@kramden.acf.nyu.edu> <5085@lanl.gov> <5243@lanl.gov>
Organization: IR
Lines: 96

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?

> 1) The number of different possible partitions is exponential in the
>    number of procedure arguments, and is further enlarged by additional
>    aliasing possibilities from the global variables.

I wish you would consider all possibly aliased variables, both arguments
and globals, together. ``The number of different possible partitions is
exponential in the number of possibly aliased variables.''

That is correct. Several months ago I posted the results up to 6
variables.

However, as I've said repeatedly, a compiler would never be crazy enough
to generate *all* possible aliasing possibilities. Probably the best
solution for individual programs is that adopted by Ultrix's -O3, or a
``feedback'' on the many compilers that can take it: generate a list of
all the partitions actually used, with some interprocedural analysis.

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.

(By the way, I'd appreciate it if you acknowledged the point in the
previous paragraph, and stopped the whining about a nonexistent
combinatorial explosion. In fact, the only reason I can think of that
you've continually failed to respond to the above point is that you want
to keep up that whining.)

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

> 2) I put the word 'advantage' in apostrophes above because I don't
>    really consider it an advantage.  Usually, when unexpected aliasing
>    occurs in a program it is an error.  Your scheme just goes ahead
>    and runs without giving any indication to the user that deep down
>    some aliasing has occurred.

That's a good point, but who says the compiler can't warn the user
whenever he calls the slow version of a routine? If you want to see
nonexistent error checking, look at how Convex handles aliasing. It
depends on the user for aliasing assertions, and it ``just goes ahead
and runs without giving any indication to the user that deep down some
alaising has occurred.''

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

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

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.

>    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. It's like Tarjan (et al., I
forget who his coauthors were) claiming in 1987 that he invented MSD
radix sort. If he had done his homework in Knuth's ACP, he would have
seen credit for ``his scheme'' as already being in wide use---by the
post office!

---Dan