Re: Common subexpression analysis (summary)

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

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