Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 1: TeX
Message-ID: <24149:Nov905:42:0990@kramden.acf.nyu.edu>
Date: 9 Nov 90 05:42:09 GMT
References: <12614:Nov801:02:4990@kramden.acf.nyu.edu> <5344@lanl.gov>
Organization: IR
Lines: 85

In article <5344@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> Well, let's try it shall we?  I have a program with 5 parameters.
> Let's call the parameters 'a' through 'e'.  The possible partitions
> of these 6 are below:

Hmmm. Did you start with 6, decide it was too much, and edit it down to
5? Gee. Back in April, when I addressed the same issue, I went up to 6.
See below.

> Well, there are 52 of these

At least you got that right. (I wrote them out by hand. Took a few
minutes. You?)

As a matter of fact, most of my responses to this article are contained
in that article back from April, which you never responded to. How about
giving it a try? It's quoted below. Pay attention to the last paragraph.

> No matter which ones you pick, I can give
> explicit assertions (remember _your_ scheme permits these) that
> describe one that's not on your list of 20 - so you have to
> have a consistent way of giving this new version a name.

Sorry, my answer to this bit is contained in the article starting the
f2c-cc-f77 thread. Note that this can be applied to optimizers for the
current C language, which cannot express such assertions; so you're
making a huge assumption here. I really am talking about cc, not qc or
nemesis95.

Okay, I'll be nice and let you off from doing your homework. What I said
about calling the function:

> When the compiler is compiling a call to the function: It now uses the
> partitions as requirements, with the same meaning for aliasing as above.
> If it thinks all the x's might be aliased, it has to generate code that
> calls the simplest version. The crucial point is that in a correct
> translation of a correct Fortran program, it knows that none of the
> arguments are aliased, so it can choose code that calls the
> all-elements-separated version.

You will also note that I required the partitions to be chosen by a
fixed method not depending on any other outside information, so the
compiler knows what choices are available. If there are several possible
partitions, it'll choose the strongest ones (expressing the strongest
anti-aliasing requirements), then choose any way it wants from those.

---Dan

From cmcl2!stealth.acf.nyu.edu!brnstnd Thu Apr 12 19:40:55 CST 1990
Article 5307 of comp.lang.misc:
Path: cmcl2!stealth.acf.nyu.edu!brnstnd
>From: brnstnd@stealth.acf.nyu.edu
Newsgroups: comp.lang.misc
Subject: The number of aliasing patterns for N arrays
Message-ID: <548:Apr1221:38:3790@stealth.acf.nyu.edu>
Date: 12 Apr 90 21:38:37 GMT
References: <20080@megaron.cs.arizona.edu> <14332@lambda.UUCP>
Reply-To: brnstnd@stealth.acf.nyu.edu (Dan Bernstein)
Distribution: usa
Organization: IR
Lines: 22
X-Original-Subject: Re: Pointers as 3-tuples

In article <14332@lambda.UUCP> jlg@lambda.UUCP (Jim Giles) writes:
> From article <20080@megaron.cs.arizona.edu>, by gudeman@cs.arizona.edu (David Gudeman):
> > Actually, it increases exponentially with the number of aliasing
> > patterns in the arguments of the functions.  For a function of 3
> > array arguments, the maximum number of versions needed is 2^3 = 8.
> No, the number increases combinatorially.  Aliasing occurs pairwise
> between arguments (an/or global data).  So, the number of potentially
> aliased pairs is N choose 2, ie. a binomial coefficient.
  [ implying that the number of versions is 2^(N choose 2), not 2^N ]

Hmmm, this doesn't sound right. After all, if A and B could be aliased,
and B and C could be aliased, then A and C could be aliased. (This is
why the natural keyword is ``alias,'' not ``noalias.'')

I count 2 for 2, 5 for 3, 15 for 4, 52 for 5, 218 for 6. Go figure.

Anyway, this is all irrelevant, because as Jim loves to remind us,
aliasing is rarely useful. (It can't be---otherwise Fortran would allow
it.) Therefore you only need two versions: the amazingly fast one for no
aliasing, and the slow one for the rare cases. Right, Jim?

---Dan