Mon, 13 Jul 1992 22:32:04 GMT

Related articles |
---|

Common subexpression analysis (summary) mernst@theory.lcs.mit.edu (1992-06-26) |

Re: Common subexpression analysis (summary) buzzard@eng.umd.edu (1992-07-07) |

Re: Common subexpression analysis (summary) Bruce.Hoult@bbs.actrix.gen.nz (1992-07-13) |

Re: Common subexpression analysis (summary) igor!voltaire!davidm@uunet.UU.NET (1992-07-13) |

Re: Common subexpression analysis (summary) Dik.Winter@cwi.nl (1992-07-13) |

Re: Common subexpression analysis (summary) preston@dawn.cs.rice.edu (1992-07-12) |

Newsgroups: | comp.compilers |

From: | Dik.Winter@cwi.nl (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 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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.