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: Aggressive optimization
Message-ID: <5491@lanl.gov>
Date: 9 Nov 90 21:40:52 GMT
References: <24232:Nov905:50:0690@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 53

From article <24232:Nov905:50:0690@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> [...]
> That's exactly what I'm talking about! The i's and j's and other
> integers used to index the arrays are *added* together. The program
> could have x[i + j - 17] and lots of other weird expressions, all
> evaluated conditionally through the control structure of the program.
> [...]

Ok.  So how do _you_ propose to optimize this using pointers?  Do you
plan to do the following:

   p = &x + i + j - 17;
   /*... lots of code ...*/
   a = *p

If that's what you plan, then I will do:

   ii = i + j - 17
   /*... lots of code ...*/
   a = x[ii]

And the optimizer can promote the add of the base of 'x' back to the
point where 'ii' was computed.  Well, maybe you plan to do:

   if (some_condition)
      p = &x + an_expression
   else
      p = &x + another_expression;
   /*... lots of code ...*/
   a = *p

Then I'll do this:

   if (some_condition)
      ii = an_expression
   else
      ii = another_expression;
   /*... lots of code ...*/
   a = x[ii]

And the compiler can promote the add to the place where the two
if branches reconverge - or even up each branch!  This promotion
problem is O[N] in the number of basic blocks if the language is
"structured".

The fact is, no matter _how_ you precompute the pointer value, the
array index can be precomputes _exactly_ the same way except for
the add of the array base - which can be promoted back to where
the rest of the calculation if the compiler writer wants it to be.
Of course, in the case of static arrays, you usually don't want it
to be - at least on most mainframes.

J. Giles