Re: Common subexpression analysis (summary)

In article 92-07-028 Bruce.Hoult@bbs.actrix.gen.nz 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.


  > buzzard@eng.umd.edu (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
dik@cwi.nl


--

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