Sun, 12 Jul 1992 17:00:29 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: | preston@dawn.cs.rice.edu (Preston Briggs) |

Organization: | Rice University, Houston |

Date: | Sun, 12 Jul 1992 17:00:29 GMT |

References: | 92-06-135 92-07-021 |

Keywords: | optimize |

buzzard@eng.umd.edu (Sean Barrett) writes:

*>Recently I noticed a cute little optimization thing; I'm wondering if it's*

*>well known, and if so, if it's been found to be worth doing. I'm not sure*

*>what it would be called*

*>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;*

I would call it an _unsafe_ form of partial redundancy elimination.

The basic reference is

Global Optimization by Suppression of Partial Redundancies

Etienne Morel and Claude Renvoise

Communications of the ACM

February 1979, Volume 22, number 2

The way the code is written, it will run slower in some cases, e.g.,

when y is initially < 0. Better is to rewrite the while loop first.

if (y >= 0) {

do {

if (x*x + y*y >= r*r) {

y--;

}

else {

x++;

}

} while (y >= 0);

}

which, with enough work, turns into

if (y >= 0) {

x2 = x * x;

y2 = y * y;

sum = x2 + y2;

r2 = r * r;

loop {

if (sum >= r2) {

y--;

if (y < 0) break;

y2 = y * y;

sum = x2 + y2;

gte = sum >= r2;

}

else {

x++;

x2 = x * x;

sum = x2 + y2;

gte = sum >= r2;

}

}

}

Note that no path has been lengthened and no computation appears on a

path where it was not originally present. Therefore, we could just as

easily handle division or other potentially trapping operations.

Of course, the computations of x*x and y*y inside the loop are subject

to strength reduction. The result would look like

if (y >= 0) {

x2 = x * x;

x21 = 2 * x + 1;

y2 = y * y;

y21 = 1 - 2 * y;

sum = x2 + y2;

r2 = r * r;

loop {

if (sum >= r2) {

y--;

if (y < 0) break;

y2 += y21;

y21 += 2;

sum = x2 + y2;

}

else {

x++;

x2 += x21;

x21 += 2;

sum = x2 + y2;

}

}

}

In this case, we have lengthed some paths (e.g., computing 2*x+1

when it might not ever be needed). Th is is just a characteristic of

strength reduction.

A really good strength reducer would reduce the computation

of sum, thusly

if (y >= 0) {

x2 = x * x;

x21 = 2 * x + 1;

y2 = y * y;

y21 = 1 - 2 * y;

sum = x2 + y2;

r2 = r * r;

loop {

if (sum >= r2) {

y = y - 1;

if (y < 0) break;

sum += y21;

y21 += 2;

}

else {

x++;

sum += x21;

x21 += 2;

}

}

}

Finally, if the result of x is not required after the loop, we can

eliminate the increment.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.