# Re: Common subexpression analysis (summary)

## buzzard@eng.umd.edu (Sean Barrett)Tue, 7 Jul 1992 05:07:37 GMT

From comp.compilers

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)
| List of all articles for this month |

 Newsgroups: comp.compilers From: buzzard@eng.umd.edu (Sean Barrett) Organization: Fraternity of Avian Deists Date: Tue, 7 Jul 1992 05:07:37 GMT Keywords: optimize References: 92-06-135

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--it's related to induction variable elimination,
invariant code motion, and common subexpression elimination, with the
former as the most obvious thing; in my head I refer to it as value
caching, as the idea derived from an unrelated thing I was working on
which required only partial reevaluation of trees.

If you have detailed profiling information available (branch counts more
than execution time), it should be possible to do quite a lot with it, but
even without, you can do something like:

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;

A more interesting example would involve moving something around that is
calculated from two different variables.

It's related to common subexpression elimintation because you could have
multiple occurences of the expression to be moved around (as long as all
are dominated properly).

Sean Barrett
--

Post a followup to this message