Re: Common subexpression analysis (summary)

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

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