Re: Common subexpression analysis (summary) (Dik T. Winter)
Mon, 13 Jul 1992 22:32:04 GMT

          From comp.compilers

Related articles
Common subexpression analysis (summary) (1992-06-26)
Re: Common subexpression analysis (summary) (1992-07-07)
Re: Common subexpression analysis (summary) (1992-07-13)
Re: Common subexpression analysis (summary) igor!voltaire!davidm@uunet.UU.NET (1992-07-13)
Re: Common subexpression analysis (summary) (1992-07-13)
Re: Common subexpression analysis (summary) (1992-07-12)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Dik T. Winter)
Organization: CWI, Amsterdam
Date: Mon, 13 Jul 1992 22:32:04 GMT
References: 92-06-135 92-07-028
Keywords: optimize

In article 92-07-028 writes:

At the end:
  > I'll bet if there are any compilers that can do this, they're probably
  > for FORTRAN :-)

I do not think so. The reason comes later.

  > (Sean Barrett) writes:
  > > TURN:
  > > while (y >= 0)
  > > if (x*x + y*y >= r*r)
  > > --y;
  > > else
  > > ++x;
  > > INTO:
  > > r2 = r*r;
  > > x2 = x*x;
  > > y2 = y*y;
  > > while (y >= 0)
  > > if (x2 + y2 > r2)
  > > --y, y2 = y*y;
  > > else
  > > ++x, x2 = x*x;

Well, I just checked the two very aggresive compilers, Cray C and Cray
Fortran. The Fortran compiler leaves it as is. The C compiler only puts
the r*r calculation outside the loop. On the other hand the Fortran
compiler sometimes performs amazing optimizations; but this one is not
worthwile. It would save 2 cycles from a loop that takes quite a bit
more. The optimization is only worthwile if multiplication is (much)
slower than addition, which is not always the case!

  > Why didn't you do strength reduction while you were at it?

This solution replaces one multiply by three adds, so is only worthwile
if a multiply is three times as slow as an add.

But the best optimization depends on whether x, y and r are ints or
floats. I think they are ints, in that case a full optimization is:

if(y >= 0) {
if(x < r && x >= -r) x = r;
y = 0;

So there must be more. Perchance Sean Barrett is calculating the number
of lattice points in a circle? That means that the value of x is used
within the loop, and Bruce Hoult's second optimized must be reviewed.
(Optimization is a bit more complex when the variables are float, but the
result is similar.)
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland
home: bovenover 215, 1025 jn amsterdam, nederland


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.